4 ms·
You must not be familiar with the knapsack problem.
by icedog 12y ago
You must not be familiar with the knapsack problem.
- tedunangst 12y agoPerhaps 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.
- icedog 12y agoI'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.
- ruggeri 12y agoThe 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.