curiouscoding

Try measuring it! You'll quickly see that the latency of addressing n bytes of memory is definitely not O(1).

See eg "The Myth of RAM": https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

> they test lookup by sequential memory access, i.e., iterating buckets from 0 to n, and iterating from first to last element in each bucket

Yeah; that completely eliminates the cache misses / memory latency you'd have in practice. Of course eliminating that bottleneck is useful if you want to purely optimize CPU speed, but probably not quite as representative of real workloads. Also makes sense then that different array sizes give similar results: streaming tends to be fast anyway, regardless of the array size.

Another remark:

If you benchmark it as something like `for q in queries { contains(q); }`, especially the branchless variants are probably executed in parallel by the CPU, and you are measuring throughput instead of latency. That may or may not be relevant depending on the application.

Some questions/remarks:

- in the initial `Contains` code snippet (and all early-break variants), most performance is probably lost by branch misses on which element returns true. Probably much better is something like `table[0] == fp | table[1] == fp | table[2] == fp | table[3] == fp` (which might actually get optimized to int/SIMD anyway; who knows).

- What is shown in the table with benchmarks? I assume 'operations' is the number of lookups, but how large is the array? Memory latency is probably one of the big effects on overall runtime? - It's probably more useful to show time per lookup than mean 'total time'.

- Also, how do you run the benchmarks? If you make a fixed array of queries and query those many times, the same cachelines will be hit and you won't measure memory latency. Also, in this case the branchpredictor might learn all branches, so best is to only do each query once in your benchmark.

- You don't really comment on the differences between benches with different number of 'operations'. Are there any takeaways from this? (otherwise just don't show them?)

- Maybe you could try with some `u8x8` SIMD instructions as well? Although the bitmasking is also cute as-is :)

I don't think talks are being recorded, unfortunately.

I'd love to see some benchmarks/comparison on variable length strings. For strings with random length between 10 and 30, gxhash was significantly faster than xxhash for me. I would assume because it processes chunks of up to 32 chars at a time, avoiding branch misses.

Generally my feeling is that at these speeds, designing for branch-predictability for short strings might be more important than absolute throughput.

Nice overview of sorting methods, thanks for sharing!

I also looked a bit into radix and distribution sort at some point over the past year, but in the end high performance sorting is actually too big of a thing to just do quickly on the side, as your post well shows :") In fact I wasn't aware of the associativity issues for radix sort. That's definitely something to keep in mind and investigate.

Will definitely refer back to it once I'm looking at sorting again in more detail at some point!

Yeah exactly, pseudocode just doesn't cut it if what matters is exactly the implementation itself.

Indeed I did a bunch of competitive programming! But actually there my favourite topics are combinatorics, graph theory, and number theory. I'd usually leave the datastructure (read segtree) problems to my teammates.

I super enjoyed that, and indeed was looking for a PhD where I could do similar things (because my time at Google was boring in comparison -- mostly just software engineering), on the intersection of new theory and practical fast code. I decided on bioinformatics, because this is exactly a field that has a lot of data, and the amount of data is growing fast, so that fast algorithms&code are needed, both in theory (big-O) and practice. Generally I've been super excited working on various problems in this domain, and I'd say it quite closely matches my compprog experience :)

I've added a little motivation section on this :)

The final goal is to index DNA, say a human genome, or a bunch of them, and this is static data.

Then as new DNA comes in (eg is read by a DNA sequencer) we can efficiently query against the index built on the reference genome, and this reference is often fixed.

Jup. I've added to the future work section now that the plan is to use this to speed up suffix array searching. Suffix arrays are pretty regularly used to build indices over say a human genome, that can then be queried.

And since DNA sequencers are still increasing there throughput and accuracy, it's always good to have faster algorithms as well.

Thanks! I did spend some time fiddling with CSS to make the yellow highlights so that the titles stand out a bit more, and to improve the code blocks, but otherwise it's a relatively common theme for Hugo. (I think it's linked in the footer.)

You're absolutely right. At some point I spent so long working on the plotting code that I really couldn't be bothered anymore to make it prettier. Hopefully I eventually find some motivation to fix this.

At some point I was playing around with interpolation search on the human genome dataset, and it was really really terrible. It had some very bad worst case behaviour when the input data has big plateaus and you're searching for something around the edges of the plateau. This can be fixed by only using interpolation for the first few iterations and doing binary search for as long as needed afterwards, but that kills a lot of the predictability of the current approach. So while I really like it in theory, in practice I'm not quite convinced it can be made to work efficiently.

You're right about the mistake in the figure. Will fix soon, thanks :)

And yeah, maybe I should just label all of then with throughout for consistency.

Assuming this is going to save someone 10ns per query in the end and I spent 150h on coding and writing this up, we only(?) need around 10^14 queries to make it worth it!

But yes, as new technologies stack up, we achieve exponential growth in throughput in the end, which usually enables new science :)

You're right. While I wasn't very explicit about this (because algorithmica and the linked paper spend plenty of words on it already), the code snippet for Eytzinger does indeed do both the prefetching and the formula.

In fact, I'm pretty sure a similar formula could be made to work for higher branching factors, although it would surely be slower. (Probably it depends on the number of times 17 divides the final index it so, which is not great, but with B=15 it would be the number of factors of 16 which is easy again.) The more annoying issue with not storing everything in the final layer is that we have to keep a running-answer for each query as we go down the tree, which I suspect will add measurable runtime overhead. But maybe that's a tradeoff one is willing to make to avoid the 6.25% overhead.

Just fyi: the throughput numbers with batching are per _query_, not per _batch_, so I think the *8 is too optimistic ")

I suspect that at higher core counts, we can still saturate the full RAM bandwidth with only 4-5 cores, so that the marginal gains with additional cores will be very small. That's good though, because that gives CPU time to work on the bigger problem to determine the right queries, and to deal with the outputs (as long as that is not too memory bound in itself, although it probably is).

Ohh yes some good ideas there! I've thought about pretty much exactly this at some point but then didn't end up including it. But I do think it's quite promising, and most of the bookkeeping can be made to be branchless.

On the other hand, most of the latency is in the last few layers, and probably there isn't as much to be saved there.

The biggest problem might be that the bottom layer will anyway have to store full-width numbers, since we must be sure to have the low-order bits somewhere in case they weren't covered yet in earlier layers. Or we could have variable width encoding per node maybe (instead of per layer) but that does sound a bit iffy on the branch predictor.

In the end I guess I kinda like the simplicity and hence reliability of the 'just do the full tree and the first layers are cheap anyway' approach. Probably another factor 2 speedup is possible on specific datasets, but anything beyond this may not be reliably good on worst case inputs (like is the issue for the prefix partitioning methods).

Hmm, bitmaps is an interesting idea! If the data is dense enough, then yeah I guess a quick linear scan would work.

There's also the extreme of simply storing the answer for each possible query as a u32 and just index the array, but there the overhead is much larger.

Rank-select is also interesting, but I doubt it comes anywhere close in performance.

I happen to also be working on a minimal perfect hashing project that has way higher throughput than other methods (mostly because batching), see https://curiouscoding.nl/posts/ptrhash-paper/ and the first post linked from there.

Ah yes, I did consider sorting the queries at some point but I guess I then forgot about it again. If the queries are random and much less than the input size, probably most queries will hit different cache lines in the final layer, and I suspect benefits will be limited at maybe 2x best case since the last layer is where the bottleneck is.

Also (radix) sorting is very memory bound usually, and we probably need to sort in at 16^2=256 buckets or so to get sufficient reusing of the higher layers, but I don't have the numbers of what a round of radix sort takes. (My guess is order 1ns per query? Maybe I'll find time to investigate and add it to the post.)

Anything in particular that threw you off? I'd be happy to add a few words to briefly explain some of the less intuitive rust syntax.

Ohh yeah, don't get me started in big-O...

It was great while computers were not really a thing yet, but these days it's often so meaningless. We see papers with 2x speedup with a lot of novel algorithmic stuff that sell better than 10x speedup just by exploiting CPUs to the fullest.

Even myself I kinda think theoretical contributions are cooler, and we really need to get rid of that (slightly exaggerating).

The problem with pseudocode is that it's completely underspecified. And how would I ever write intrinsics in pseudocode? Much easier to do a proper language directly so people can actually Google things and read their official documentation.

Rust is great :")

But no, this is actually part of my PhD research. The next step will be to use this in a fast suffix-array search algorithm.

Yeah, I don't think python is the right tool here. C++ definitely would be an option though.

Anyway very happy that this is also showing off what rust can do

Thanks! It's somewhat tiring to not have loose ends, but I agree it pays off :)

Doing this stuff in Rust is absolutely possible, and I'd do it again since my C++ days are now past me, but the endless transmuting between portable-simd types, plain rust arrays, and intrinsic types is quite annoying.

Also rust is not made for convenient raw pointer arithmetic. There plain C would be much more to the point.