Hacker News Reader

Comment by drv | Hacker News Reader

The article goes into more detail on the "why", but the "art" is not really that complicated or lost: sort structure elements by size/alignment, biggest first.

View on HN

Unfortunately it is not as simple when you have to account for different threads on different cores accessing the same structure, as mentioned in the article. [1] Or the performance implications of managing multiple instances of structures. [2] Or the alignment requirements for doing SIMD. [3]

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...

You seem to have missed the whole section in the article that begins: "While reordering by size is the simplest way to eliminate slop, it’s not necessarily the right thing."

> sort structure elements by size/alignment, biggest first

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).

I find this a very strange response: "this technique doesn't work if I have to comply with an external standard." Fine, then don't use the technique.

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.

You must not be familiar with the knapsack problem.

Perhaps you aren't? Unlike struct packing, the knapsack problem has a fixed upper limit. There's no limit on number of struct fields, and indeed, every solution consists of all of them.

I'm not saying it's exactly the knapsack problem, but it's quite related. Ordering from largest to smallest does not yield the optimal solution - period.

The article says throughout that sorting the fields in order of decreasing alignment requirement (i.e., size) minimizes slop. The proof for this is pretty straightforward. The article also discusses why you might not do this (e.g., structures might try to match layout of memory mapped devices).

Rudeness is a choice you make, by the way. You can change your behavior.

Reply on news.ycombinator.com