« first day (51 days earlier)      last day (264 days later) » 

12:00 AM
The `index` will be `0` if either `seq64` is `0`, OR if its last bit is `1`.
Is that the intention?
At first I thought that you are checking if **ANY** of the bits are set... That would simply be:
if(seq64)
 
12:27 AM
Generally, we are supposed to check the return of _BitScanForward() to see if it found any bits (it returns 0 otherwise). This goes to
void up(uint64_t* i, uint64_t* len)
too.
I guess we can check for 0 before calling _BitScanForward()...
 
12:39 AM
To summarize: your code can't tell the difference between 0 and xxx1, the index is 0 in both cases
 
 
3 hours later…
3:48 AM
Sent you minimally updated YOUR code from yesterday (Thursday).

When you decide about _BitScanForward ^^, can save another 0.75% :)
I simply don't understand the intent there...

One more thing. I tried the code I suggested above (to use atomic increment instead of your
if (start < stop) {
but got into exception when the "len" becomes "-1". I couldn't figure out - why. Looks like one of the compiler warnings (mix of signed/unsigned/32-bit/64-bit) was serious. Feels like we promote all-ones unsigned 32-bi int to 64-bit using int somewhere, so the high word is sign-expanded with all ones. Th
 
 
5 hours later…
8:26 AM
Yes the atomic int produces i = -1, I saw that too. But once we decide that 1 fragment is the best, we can get rid of this at all by giving the thread id to the back-tracking
Just as we did for the previous construction
_BitScanForward can indeed not tell difference between 00..00 and a sequence with a 1 somewhere. But, 00..00 is only once ever present (te first sequence). And for that sequence it is even better that it thinks last_curl = 3, because it should return krul = 4 because of all the 0's.
And for any other sequence, a 1 is present somewhere, and the BitScan works as intended
This was the easiest implementation I could think of to see if the last bit is either a 0 or a 1. If you know a better one, go ahead. Maybe a mask and AND, but may be slower, IDK
 
 
1 hour later…
9:55 AM
I think there is a minor mistake in the loop up to 85 bits. You wrote if curl >= last_curl. But if last_curl was 2, and curl = 2, we could still find a curl of 3, right? If i = 210 for example, there could be a repetition of 3*70
 
10:49 AM
Same goes for the comparison right above that loop, by the way
 
11:14 AM
I sent the code over to my brother. Based on my results, we might be able to pull 48 in just under 20 minutes! He only has time to go to 45, but we will see :)
I changed like two or three minor things, but I now got quite consistent 6% speed-up over my previous version
 
11:48 AM
Somehow we got slower timings... About 3%. Maybe something else was running meanwhile. Cannot confirm
 
 
4 hours later…
3:49 PM
Just did a rerun and saw an approx 4% increase :) 20m26s estimated time to 48
 
 
2 hours later…
5:24 PM
Just a couple of days ago you estimated 31 min - right? 20.5 is great!

Last night I had an idea on how to better utilize CPU: increase the thread count. Some threads would have to wait, but CPU is used 100% . Got major slowdown for 16 and 32 threads, each for 1, 8 and 16 fragments. Can’t explain...
 
Yes 20.5 is really awesome :)
Yes when launching more threads than available, it doesn't queue them up, but work all of them simultaneously. That massively decreases speed
 
I still don’t understand the requirement two have power-of-2 threads, especially if one of them finishes immediately. Do you know which one runs the longest? May be we can offload some work from it to another thread?
 
Well, the idea is that each thread starts with a given sequence. So, #1 has all sequences with 000, #2 has 001, #3 has 010, and so on
That requires power-of-2 threads, and power-of-2 fragments
But the 'problem' then is that #8 with 111 finishes right away, because all sequencss starting with 111 are invalid
Fragmentation uses the same idea: with 8 threads and 2 fragments, #1 has 0000, #2 has 0001, #3 has 0010 etc. We create twice as many starting points
And I inplemented fragmentation to use the same amount of threads (always fastest), but then when one finishes, it picks up another starting sequence and checks all the sequences that start with that value
 
 
4 hours later…
9:35 PM
Want to summarize my profiling. Looked at krul() and krul_large(). They took 75% combined. This is a short run of 42 (remember whet it was a LONG run?).
Building cache took 15%, so not counting that krul's took 75/85, or 88%. We should obviously concentrate on them.
Out of that 75%, 22% took cache retrieval and pre-fetching. Can revisit it, but I'm not sure there is anything to be saved. The packing I did earlier doesn't help with the speed, as the next key will [likely] never be in cache, but unpacking takes a little time.
Loop <32 takes 13.74%, and <63 - 3.34%. But they are very tight, not sure if we can squeeze anything from them.
in krul, there is a test:
if (i <= 64)
which can now be removed, I think (since we are not going over 64)
Then, <= limit_4 took 4.52%, <= limit_3 - 6.3%, and <= limit_2 - 2.43%. They all are pretty tight, too.
Combined from both kruls,
uint64_t mask = mask64[pattern_length];
takes 5.05%. There is another way to do that instead of reading from cache:
(1ull << pattern_length) - 1;
I know I tested it earlier, with no speed up, but may try to attempt again
I am afraid that from no on, our only hope is to eliminate some calls, not to speed them up.
 
10:40 PM
Yes the <= 64 test can be removed
There is almost nothing anymore that takes a significant amount of time... so indeed, we can only find faster code from thinking instead of programming
Oh by the way, on systems with more RAM than my laptop, we might try cache of up to 33, right? We did see a few %% increase when we used packed cache
That does require 17GB of free RAM, though, or 12, idk from the top of my head
My brother will be doing a run of 36 up to 50 while you sleep, BTW
 

« first day (51 days earlier)      last day (264 days later) »