Hacker News new | past | comments | ask | show | jobs | submit login

Why would you want to make an in-memory data structure page-aligned instead of cache-line-aligned?



It's not that you would want to. It's that certain data structures (particularly in kernel land) naturally form around powers-of-2 sizing. Since the hashing in an n-way associative cache is done by masking away bits, you can get into this nasty situation where multiple elements of your data structure end up hashing to the same location set (the N in an N-way associative cache). You don't want that if you are going to walk the elements in your structure.

Either avoid walking the elements, or do whatever it takes to ensure that you don't end up getting stuck behind the N.

Hardware is inescapable.

It's also worth noting that you can use this to your advantage, ensuring that accesses to certain elements does not push much else out of the associative cache.


It's commonly done in memory allocators at various levels. You inherently want to manage pages, and you'll carve out the start of the page itself to hold its own data structure.

You can see an example of this technique here: https://github.com/scotts/streamflow/blob/master/streamflow....

This bit of code executes when a call to malloc() could not find any free memory, and it has to request more memory from the operating system. The function supermap() allocates a large chunk of memory from the kernel. We then write the meta-information to keep track of that chunk of memory directly to itself - that "meta-information" is the pageblock_t struct. In malloc(), we then use that chunk of memory to find a sub-chunk inside of it to return to the user.

Note that internal to malloc(), we will maintain lists of these pageblock_t structures, and they will all be page-aligned. So, anytime we want to search for free memory among the managed pages, we're going to access page-aligned structures.


You can do both ;-)




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: