You should also check out the Maple Tree (https://docs.kernel.org/core-api/maple_tree.html).

It's the data structure used to track non-overlapping intervals in the Linux kernel's virtual memory subsystem.

If you don't mind sharing, what's your use case for such a data structure?

Company politics? According to this tweet, parts of Intel did know about this attack: https://twitter.com/bsdaemon/status/1688978152201015301

The Cuckoo Trie, an ordered index data structure explicitly designed to have memory-level parallelism, which out-of-order processors can exploit to execute DRAM accesses in parallel:

https://arxiv.org/pdf/2201.09331.pdf

Is this comparison work available?

With some luck, it will be published early in the new year.

I submitted an interesting response to this rant a while back.

It makes some good points, despite the inflammatory technique of characterizing Linus' rant as being caused by a "C-hacker syndrome".

http://news.ycombinator.com/item?id=3416863

You are assuming that all the objects that will be accessed are known up front, before any one of them is accessed. Is that what happens in Python?

What happens if you need to retransmit a packet?

Exactly right. SOCK_STREAM sockets can't unblock the process until it knows that it won't need that buffer again for a retransmission.

Do you think that is true even for modern allocators like Hoard?

In other words, I'm curious what are the underlying malloc() implementations that pool allocation so outperforms.

It seems reasonable that the people optimizing code and writing the most efficient infrastructure are not the same folks who actually write trading algorithms. Now, supposedly a big part of trading firm's success is that its algorithms are faster than the competition's. So are the low-level infrastructure people paid as well as the algorithm folks?

No is the basic answer. Low-level optimization while a valuable skill is more of a commodity, algorithm development tends to require a combination of skills in maths, finance, programming and creativity which is a much rarer combination.

Saying that people who are good at low-level optimizations are still pretty well paid.

It's the van Emde Boas layout. For example, see here http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli....

No, it's not. The van Emde Boas layout splits the data set into sqrt(n) chunks of sqrt(n) items. Then it recursively splits each of those chunks similarly.

This version simply divides the data set into page sized chunks. That has worse memory access complexity than the van Emde Boas layout, but is likely simpler to deal with in practice. It's not trivial to maintain the van Emde Boas layout under insertion and deletion for example.

(The post you link is a good one btw.)