curiouscoding

6 ms·

1.
by curiouscoding 11mo ago
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
2.
by curiouscoding 1y ago
> 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 pract
3.
by curiouscoding 1y ago
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
4.
by curiouscoding 1y ago
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 |
5.
by curiouscoding 1y ago
I don't think talks are being recorded, unfortunately.
6.
by curiouscoding 1y ago
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 ch
7.
by curiouscoding 2y ago
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 si
8.
by curiouscoding 2y ago
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 theo
9.
by curiouscoding 2y ago
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 agains
10.
by curiouscoding 2y ago
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 s
11.
by curiouscoding 2y ago
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
12.
by curiouscoding 2y ago
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.
13.
by curiouscoding 2y ago
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 someth
14.
by curiouscoding 2y ago
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.
15.
by curiouscoding 2y ago
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
16.
by curiouscoding 2y ago
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&
17.
by curiouscoding 2y ago
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
18.
by curiouscoding 2y ago
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 t
19.
by curiouscoding 2y ago
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 th
20.
by curiouscoding 2y ago
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 s
21.
by curiouscoding 2y ago
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.
22.
by curiouscoding 2y ago
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 th
23.
by curiouscoding 2y ago
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 document
24.
by curiouscoding 2y ago
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.
25.
by curiouscoding 2y ago
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
26.
by curiouscoding 2y ago
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-s