Re^7: [OT] The interesting problem of comparing bit-strings.

[salva]

locating a 1Mi bit needle near the end of a 1GiB buffer of random bits

Have you considered that using random test data may not be a good idea. You are never going to generate the performance-degrading worst cases.

For instance, it is very unlikely that you will find partial needle matches longer than a few bits.

[BrowserUk]

Have you considered that using random test data may not be a good idea.

I'm not really at the testing stage.

Still trying to cover off the edge cases without upsetting the compiler's ability to maintain the important values in registers, to avoid reloading values from memory.

The difference in performance between /Od (none) and /Ox (full) is currently over an order of magnitude -- about as big a difference as I ever recall seeing -- and I think I might be able to get two orders if I can move some of the conditional stuff out of the critical path; but it is all too easy to upset things badly by adding an extra test or two. (And I need an extra condition or two :()

For instance, it is very unlikely that you will find partial needle matches longer than a few bits.

Currently I'm generating a haystack of random quads and then extracting a needle of a specified size and (0..62) bit-offset from within that, somewhere close to the end.

This means I not only know that the needle exists, but where it should be found. More importantly, if it isn't found, then I can quickly detect patterns in the combinations of parameters that cause it to fail.

For example, it currently handles leading bit offsets, but not non-multiples of 64-bits. And that's because I tried (unsuccessfully) to move the terminating condition out of the main path of the code.