Viewing profile — 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…

> 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 ca…

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 …

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

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…

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…

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 …

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 r…

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 …

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 relative…

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…

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 inpu…

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

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…

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 …

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 b…

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 p…

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 querie…

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 …

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 …

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