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…
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…
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…
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…
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…
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,…
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…
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.…
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…
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…
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…
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.…
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…
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…
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…
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…
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…
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…
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
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…
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…
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…
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…
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…
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,…
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…
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.…
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…
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…
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…
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.…
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…
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…
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…
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…
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…
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…
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