Thanks for the pointer, it looks particularly interesting. I'm not good with the terminology and it always takes me a while to figure which properties we're talking about starting from a name. But the reported times in the article look pretty good and certainly interesting to consider. One difficulty I'm facing with ebtrees and strings is that I need the position of the first difference, that strcmp() doesn't return to you, and that if you reimplement yourself in multi-byte matches at once (I did it already), it will quickly upset valgrind and sanitizers for reading out of bounds. That makes such functions annoying to adopt in various projects as it requires more customizations. So I kept the hand-crafted one-byte-at-a-time comparison, but figured that other approaches based on just a comparison (strcmp, like used in rbtrees) could actually be a win for this reason.
I’m surprised the run time doesn’t spike harder than this as they exceed L1 and L2 cache sizes. I expected the 40 bytes per node algorithm to be punished more heavily.
Or maybe that calls the benchmarks into suspicion.
In case it's interesting to others: This piece is written by Willy Tarreau, who is also the author of the HAProxy software load balancer! I did a double take when I saw the page header.
Huh. I'd love to see B-trees thrown in there. Especially using some of the tricks in the excellent "Algorithms for Modern Hardware" book:
https://en.algorithmica.org/hpc/data-structures/b-tree/
Thanks for the pointer, it looks particularly interesting. I'm not good with the terminology and it always takes me a while to figure which properties we're talking about starting from a name. But the reported times in the article look pretty good and certainly interesting to consider. One difficulty I'm facing with ebtrees and strings is that I need the position of the first difference, that strcmp() doesn't return to you, and that if you reimplement yourself in multi-byte matches at once (I did it already), it will quickly upset valgrind and sanitizers for reading out of bounds. That makes such functions annoying to adopt in various projects as it requires more customizations. So I kept the hand-crafted one-byte-at-a-time comparison, but figured that other approaches based on just a comparison (strcmp, like used in rbtrees) could actually be a win for this reason.
I’m surprised the run time doesn’t spike harder than this as they exceed L1 and L2 cache sizes. I expected the 40 bytes per node algorithm to be punished more heavily.
Or maybe that calls the benchmarks into suspicion.
In case it's interesting to others: This piece is written by Willy Tarreau, who is also the author of the HAProxy software load balancer! I did a double take when I saw the page header.