> If you’re using a higher level language, you’re not going to have access to how the memory is laid out. A simple change, like removing indirection in our list, was an order of magnitude improvement in our latencies since there’s memory prefetching in the compiler and the CPU can anticipate which vectors are going to be loaded next in order to improve the memory footprint.
This is a common experience and I'm still surprised by the choice I constantly see to use a managed-memory languages to build a database - one of a very small set of special cases where having full control over the memory layout might just be a reasonable thing to want. In this universe (absent doing something completely absurd) it's not algorithmic complexity but managing data locality in the cache hierarchy (e.g. reading things from L3 vs main memory vs disk) that makes things orders of magnitude faster, especially if you're in the realm of doing things like SIMD operations to speed things up.
Perhaps there's some level of suck we're willing to tolerate for all the other benefits you get, but I've been noticing a pattern of "align things just so at the higher level and hope they mostly turn out the way you want at the lower level" (e.g. also with the Apache java-y databases like hadoop / hbase / cassandra which I guess were mostly supposed to derive their total throughput from massive scale rather than per-node performance) which is a bit funny.
But also it seems like part of Rust's promise was "low level but make it high level" which seems to be succeeding (zero-cost abstractions and whatnot), so I imagine this will get better over time - having not attempted a project like this myself, I'm not sure what the limitations you'd run up against are in terms of laying things out in memory in a favorable way - I imagine the kind of massive manually managed arena allocations and ad-hoc pointers going everywhere that one normally does doesn't really fly.