The Lost Art of C Structure Packing
catb.org
catb.org
One thing I learned with Picasa (which is basically an in-memory database): if you're storing a lot of data in RAM, sometimes you should think of the data structures more as a database (with copy in/out, rather than reference). In multithreaded cases, this kind of approach unexpectedly gets you more parallelism and speed.
This is extremely beneficial when your tables have large number of columns, but you only want to do computations on a few of them. Columnar stores usually implemented using dictionaries which allow for efficient duplicate handling and blazing fast lookups. Often those dictionaries also contain run length optimizations, so values 1 through 100 are only stored using two values start-range 1 and end-range 100.
All in all, column stores are efficient at analytic workload, but struggle when a lot of inserts and updates need to happen.
[0] Using prefetch, properly aligned data, and likely other optimizations I am not thinking of.
I ran across this with Redis recently. Redis has an internal data structure called ziplist that's a doubly linked list with no pointers. It just uses byte offsets to the next element, so all elements are in one contiguous block of memory. It's great because you can store a lot of values compactly without needing 1 to 5 pointers (8 to 40 bytes) overhead per element in your data structure.
But, a problem shows up when you want to insert or delete items. Every insert or delete requires expanding or shrinking the entire solid-chunk-of-memory allocation, which isn't the fastest thing in the world when your allocation is large. Also, inserting into the HEAD requires copying the _entire_ ziplist up exactly one element position because the block of your memory layout just changed.
So, obviously these things are useful, but their usefulness degrades as your solid blocks of memory hit cache limits. Everything is super fast when your entire ziplist fits in L1, still about the same in L2, worse in L3, and horrible if your ziplist grows any larger.
But, what can we do? We can fix the entire problem by creating a traditional linked lists of solid memory block ziplists. Now, each ziplist can remain small (8 KB to 16 KB), and when we grow bigger, we just cut a new ziplist, pointer-attach it to the previous ziplist, and now we have a minimal-pointer, high-locality data structure with unlimited growth potential without performance defects. It doesn't buckle under inserting or updating arbitrary elements since each memory block is isolated to a maximum ~8 KB size (reminder: your L1 cache is 32 KB to 64 KB depending on architecture) and now your memory usage due to pointer overhead is now also _greatly_ reduced (assuming your data was small and dominated or matched by pointer overhead size in the first place).
As a double bonus, now when your data structure is a solid block of memory, you can compress individual contiguous memory blocks (usually with great compression ratios) because your contents will tend to be homogeneous in shape inside the same container. Result: huge reduction in pointer overhead + sequential access + compression = best of all possible worlds.
Other details/comparisons at https://matt.sh/redis-quicklist-visions
A wise man once said: Things have now gotten to the stage where I flinch slightly as I click on the "comments" link, bracing myself for the dismissive comment I know will be waiting for me at the top of the page.
Then why don't the popular scripting languages use B-trees for their sequence containers?
Both Perl and Python use arrays for this. Both pay the price of O(n) inserts mid-container.
1. Name array strongly implies that it has an underlying continuous memory location associated with it. All of modern scripting languages have some form of dictionary, map, set, or hashtable which is implemented using insert/update friendly approach.
1a. Typical workload for array is to iterate over it doing something with each element, B-Tree is strictly worse in iterating over all elements compared to static array.
2. Most instantiated dynamic arrays rarely perform deletes. Most common operation that could change size of array is push_back, and amortized cost for inserts is probably way less than chasing pointers in B-Tree.
3. B-Trees were created and optimized for HDD performance. With current SSD and memory trends, there are simply better data structures to use.
4. Pointer chasing got a lot more expensive relative to continuous memory scanning. This is mostly due to majority of memory performance increases coming from increased throughput as opposed to lower latency.
This does not mean B-Trees are bad, in fact they are still heavily utilized in databases because they scale extraordinarily well with data size. They are commonly used for indexes because membership testing (single value lookup) and range lookups are O(1), and updates/deletes are generally very fast as well.
Python calls the default sequence container a list. If you took that literally, it implies O(1) inserts.
http://kmike.ru/python-data-structures/
And:
hyc_symas’s comment seems a little confused because they are talking about doing binary search within B-tree pages. But if you’re using B-trees to implement dynamic non-sparse arrays, which seems to be the topic, you don’t need any binary searches. You can just subtract the beginning-of-page index from the index you’re indexing to in order to get the offset within the page.
That kind of comment, managing to be simultaneously ignorant and arrogantly dismissive, is why I don’t comment much on HN these days.
Yes, you can say "give me the 5th element of this array" but the discussion was about maps/dictionaries, where you're more often going to say "give me item foo that was inserted before".
When folks like you post while obviously not paying attention, yes, you elicit a dismissive response.
This would be vastly more cache friendly, and you would be fragmenting your heap dramatically slower. You could even mmap() a scheme like this, but that's another story!
Oh, it's actually worse than that because when inserting we do a realloc (which could require automatically copying the entire memory block), then (if inserting to the head) we memmove the entire contents down to the end of the new allocation. Fun!
Mainly we don't pre-allocate because it's built on top of existing components, and the existing components don't do that. The actual "max size" limit is configurable and we don't really want to allocate the full max size for each list up front. If you have 500,000 lists each with 3 40 byte elements (~60 MB total), it would be overkill to allocate 500,000 8 KB blocks (~4 GB total).
Ideally, we would automatically determine if the user is doing "big operations" then switch to a page-based approach versus smaller "store as much data as compactly as possible" approaches, but it's just not done yet.
2.you are saying it's good to use in-memory column-store for oltp?
Yes, that Picasa.
I guess the MATLAB folks call this "Array Programming"
Among other things, it incidentally solves the problem Yossi Kreinin identified in "I want a struct linker": http://yosefk.com/blog/i-want-a-struct-linker.html
OO as it is usually practiced (gross generalization I know) is often hell on memory layout and memory access which causes problems that never show up in unit testing but show up in deployment. Pattern fetishism exacerbates the problem.
But a data structure abstraction that hides the storage implementation is an ideal application of OO.
Moderation in all things....
Really opened my eyes to the many, many things that I didn't know.
The content of the article is more or less evergreen. Raymond's celebrity in a constellation of small worlds [deserved or not] makes it more likely to get treated so.
The joke is funny. If Knuth and Ritchie we're the domain for panels one and two though, panel three would get a much larger range. John Skeet, even maybe?
If you have the time, watch this series in which John Romero and (Bioshock level designer and apparent Doom fanboy) Jean-Paul LeBreton play through the first episode of Doom and analyze its level design in depth:
In American conversational English "this was discussed like a year ago" carries the connotation that another discussion is redundant. It reads in the voice of a teenager's critique.
Additionally, it sometimes makes sense to duplicate data to minimize cache misses. For example, translating/rotating/scaling entities in game engines. It makes sense to copy entity transforms (usually a matrix computed once) from a central manager to sub-managers for certain components. The memory overhead is traded for more efficient processing in sub-systems like rendering, animation, physics, etc.
---
[1]: http://en.wikipedia.org/wiki/False_sharing
[2]: https://software.intel.com/en-us/articles/a-case-study-compa...
[3]: https://software.intel.com/sites/products/documentation/docl...
This does not work if I'm using structure packing to align my structs with an existing protocol (i.e. a protocol that does not have the kind of "holes" that an unpacked struct might have).
Although, I believe the more common approach is to define two structs: one using the packed standardized layout, and one using a layout more suited for whatever you're actually doing. In that case, you may wish to consider sorting the elements by size and alignment for the internal use-only layout.
Rudeness is a choice you make, by the way. You can change your behavior.
VC++ has a couple of undocumented (but well known and discussed) options /d1reportAllClassLayout and /d1reportSingleClassLayout.
GCC has -fdump-class-hierarchy
CLANG has -cc1 -fdump-record-layouts
I have no experience with the others, I've just briefly read about them and assume they are similar. If they don't work in C and you would find the dumps useful, try compiling as C++.
That said, many non-trivial C codebases cannot simply be compiled with a C++ compiler.
There is a warning I added which does work in C (https://msdn.microsoft.com/en-us/library/t7khkyth.aspx). As I recall, this warning is sometimes useless (unless it's been improved upon), so it's best to turn it on only when you're investigating packing.
You make a good point about C code not compiling as C++ as much as it used to, but that's probably less true for VC code.
And I should point out - often, for the purposes of tuning, you can extract just what you need from some code, get that small chunk of code compiling as C++, and leverage your compiler's dumps.
Last thing - debuggers also know the layout of your objects. windbg's 'dt' command can show you the object layout - I'm sure other debuggers have a similar command.
However, helpful people have written an extension to gdb which does something roughly equivalent & lets gdb do all the heavy lifting of parsing the struct data from the binary debugging information.
pahole.py ships with Fedora, but since Debian doesn’t include it for some reason I’ve kept my own versions around based on something I grabbed from the gdb mailing lists some time ago:
Anyway, the problem with pahole is that it is heavily dependent on libdwarves, a custom wrapper around libdwarf by the pahole author. libdwarves has bitrotted since 2010-2011 and newer dwarf extensions produce aborts. Hurray.
I started a similar tool in C just using libdwarf directly. It's not complete and/or perfect, but it works on some binaries that pahole does not. See https://github.com/cemeyer/structhole . (And it's < 500 LoC and BSD-licensed. Please use as you will and contribute patches if you are interested in improving it.) Cheers.
I think Jonathan Blow mentioned some kind of language-level support for structure packing in the language he's designing.
I didn't graduate, but I did attend PUC-Rio for a while and I remember professor L. F. Bessa Seibel's lecture about that, as part of the INF1008 class (Introduction to Computers' Architecture), which is considered a basic first or second semester course for undergraduate CS students.
That was just 5 years ago.
Great class, great lecturer, btw
This is the situation where your solution calls for an array of structs that are contiguous in memory but aren't the same size. This happens oftenish in database, os, and compression tech. C99 and gcc have legalized the often used convention:
struct varb {
char *foo;
unsigned char age;
int number_of_bars;
char var[]; // it's something like var[0] in GCC, or var[1] in versions < c99
};
- the variable part must be declared last
- the struct may not appear in other structs or arrays
which totally makes sense, but doesn't help us implement a contiguous array of variable length structs. Also, the restriction of having the variable part of the struct come last may waste a lot of space if we have a structure where we would rather optimize the order of the struct ourselves, but that's another post!
Assume we are OK with the limitations of our struct varb, we now need to declare and malloc (or mmap) a char* (to hold all of our data) and lay out our varb structs fairly manually. Once we have found the start of a particular varb struct, we can cast it's char* address to a struct varb* and the compiler then can help us populate or interrogate our data. Note that we will need to keep track of detailed memory usage 'so far' when we are populating as well track padding, alignment of adjacent structs, as well as any reallocation when our struct array needs to grow.
This is great for the general programmer (someone who is not knowledgeable or caring about details like this.)
Unfortunately, this blows for people who do (someone like me.)
Or is it doing it suboptimally? (Say you want two fields in the same cache line, but the compiler sorts them away.)
In the end, however, my reservations are mostly due to a "get off my lawn" mentality.
Only when the difference in performance is end-user discernible. I do make sure the code is well crafted in those bounds though. There's no _valid_ excuse for crafting ugly code.
Coincidently my stuffed toy that I have kept throughout my childhood was named "Mel the Pal." I just noticed the irony of that. :)
One can opt-in to a fixed in-order layout with `#[repr(C)]` and even avoid padding for such a struct with `#[repr(C, packed)]`.
NB. in general it is impossible to pack a struct perfectly manually, e.g. generic structs can have their order for minimal size change depending on what types they're used with. It can even be somewhat platform specific, with e.g. pointers changing size/alignment on 32-bit vs. 64-bit computers (although pointers probably aren't problematic, since they're switching between two adjacent classes).
If the structure you are connecting with is packed you have to be aware of that or else you'll end up with data soup :)
Still, I must point out that using a signed 1-bit bitfield (there are lots of those in that article), is generally a bad idea. Consider for instance something like:
struct foo6 {
int bigfield:31; /* 32-bit word 1 begins */
int littlefield:1;
};
This is true, but locality also matters a lot more these days. Minimizing padding keeps more of your structs in a single cache line. That means doing this not only makes your program use less memory, but it can also be faster, in some cases significantly.
> many programs are written in other languages these days.
True, but most of those languages or their VMs are themselves written in C, so it still matters at some point. :)
https://wiki.php.net/phpng-int
http://nikic.github.io/2014/12/22/PHPs-new-hashtable-impleme...
Everyone likes to rag on PHP's chain, which is fair enough in some regards, but it has become a far better language recently, with more useful features, faster development cycles etc. People like nikic seem to be at the forefront of this.
Since PHP is a major part of my day job this all makes me very happy!
There are good reasons (as mentioned in the article) for this feature but it's not equivalent to manual structure packing.
http://jheriko-rtw.blogspot.co.uk/2011/02/know-your-cc-struc...
http://jheriko-rtw.blogspot.co.uk/2012/01/c-struct-layout-op...
If this wasn't the case, a significant amount of code would break. I've seen a good bit of code where there's a struct A, and then struct B begins with the same fields as in struct A. This allows you to treat either of them as a struct A, a kind of polymorphism. The compiler doesn't know whether you're going to do that, so it can't arbitrarily rearrange the members of the structs.
I thought in reality c2 starts after c. Instead of adding padding between each element, you will only need in boundaries
This is obviously not the default in C, but can be enabled via compiler extensions. It's also important that the compiler doesn't automatically do this since structs of the same type can be of different sizes. In order for this to work, the memory layout needs to be as originally defined in order to be correct. For an example of this see the simple dynamic string library used in redis.