Data Structures Part 3: Arrays of Arrays
ourmachinery.com
ourmachinery.com
You see this in C++'s std::string type, which leads some people to use it for storing binary data. [1] I'm not sure what common STL-ish implementations of the idea exist.
In Rust, there's SmallVec, which has configurable storage backing and spills onto the heap when there are too many elements. [2]
[1] https://stackoverflow.com/a/21710033/802794
[2] https://docs.rs/smallvec/0.6.10/smallvec/struct.SmallVec.htm...
https://github.com/facebook/folly/blob/master/folly/docs/sma...
High quality, and widely used inside Facebook. It's a shame folly isn't more widely used outside.
Compilers are definitely not allowed to insert a small buffer into an object. Nor even repurpose an int that’s not being utilized completely. Messing with your data under the hood is blasphemous.
Unfortunately data issues have been the top cause of performance problems for a long time and it’s only going to get worse. A cache miss is much, much more expensive than operations people are taught are slow, like divisions, square roots and branches. Meanwhile, in my dozens of interviews with junior programmers I’ve found that the vast majority are only vaguely aware that cache exists at all :(
As long as you match the intended semantics, you can inline a malloc call into an object if you want to.
Then there's the issue of writing a compiler that is smart enough to recognize that you allocate small arrays frequently enough that it's worth it to insert an "alignment wink-wink" buffer into your object :P
I do believe there is some work to elide allocations that are short-lived enough that the compiler can strongly guarantee their entire lifetime. For example: inside a small std::vector that lives on the stack (but it's internal buffer would normally be malloced). There's even work on getting this to work in constexpr so that you could have constexpr algorithms allocate temporary memory that does not live past the end of the compile-time algo.
However, I was knee-jerking against a wider complaint I've seen frequently along the lines of "Why can't the compiler just optimize my data structures for me to make it go more good?" in terms of AOS to SOA transformations, separating hot-cold data into different arrays, somehow magically getting rid of pointer indirections and other major re-writes. That's a research topic for some libraries and special-purpose languages. But, it's outside of the scope of the C++ compiler.
If I use the trick Niklas calls “array with holes” in part 1, will each hole larger than the cache frame result in a cache miss?
The `Vec` struct contains the capacity and used length integers, as well as a pointer to the heap-allocated storage.
The result is you can do O(1) access, O(sqrt(N)) insert and delete at arbitrary indices, and O(1) insert at head and tail.
In terms of big O this is strictly better than:
- arrays: O(1) access, O(N) insert/delete in middle, O(1) insert/delete at tail.
- circular arrays: O(1) access, O(N) insert/delete in middle, O(1) insert/delete at head and tail.
- fixed page size chunked circular arrays such as the c++ implementation of std:deque which is still O(N) for insert and delete. [2]
[1] https://news.ycombinator.com/item?id=20872696
[2] https://stackoverflow.com/questions/6292332/what-really-is-a...
So I did thread safe compacting from the end which works fine, but now I want to implement 8-neighbor sending on an array and that can easily be done with fixed over-sized boxes.
My question now is: if I use the trick Niklas calls “array with holes” in part 1, will each hole larger than the cache frame result in a cache miss?
Let’s assume you have an array of objects that are small enough that 4 can fit in a cache line.
You take advantage of locality by densely packing them into an array so that you can process 4 adjacent (and aligned) items for the price of only 1 cache miss. The array with holes can reduce your utilization by mixing live and dead data in a single cache line. Worst case would be 1 live item followed by a hole that means the next 3 in the cache line are dead bytes. That cache line only buys you 1 item to process. But, if the hole continues for several more cache lines it’s shouldn’t matter because you should have a means in place to skip all of that dead data and go straight to the next live item.
You take advantage of prefetching by processing your array linearly from start to finish so that the CPU will notice and start fetching cache lines further down the array before you even try to access them. Arrays with holes can mess this up by making your access pattern irregular. If your array is very sparse you will be accessing cache lines without a repeating pattern and the CPU won’t be able to figure out how to help. But, the goal is for your array to be fairly dense (or at least reasonably defragmented) so that you end up accessing long, continuous spans of cache lines that make the prefetcher happy. At a minimum, the goal is to do better than most multilevel/tree-based data structures.
Check out the writings and presentations of Martin Thompson (“mechanical sympathy” guy). He has made a career of getting good performance out of Java by coding it in the style of embedded-device C programs.