Why doesn't Go use span with no tail waste?

[Nghĩa Nguyễn]

---

As noted in the Go size classes table (source), size class 52 corresponds to objects of 9472 bytes each. Go allocates 7 pages (7 × 8192 = 57344 bytes) for a span of this size class, which fits 6 objects, leaving a tail waste of 512 bytes.

Why doesn’t Go allocate 37 pages for this size class instead? That would provide exactly 303104 bytes (37 × 8192), which fits exactly 32 objects of 9472 bytes with no waste. Wouldn't this be a more efficient use of memory?

[Axel Wagner]

I would say that depends on the allocation pattern?

If you allocate one value of size class 52 in your program, the current approach wastes 47K, while your suggestion wastes 293K.

In other words, your approach is only significantly more efficient, if the number of allocated object is just below a multiple of 37. It seems clearly more common, that the number is just below a multiple of 7. I don't find it at all hard to believe that this effect will usually outweigh the <1% overhead of allocating smaller spans.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/b2b8b688-c71f-4e5e-bbca-d819389b10e1n%40googlegroups.com.

[Peter Newcomb]

To dig deeper into how this part of the Go allocator works:

As described at mksizeclasses.go#L14-L19, the page count for a given size class is chosen to achieve a tail waste of no more than 12.5% (1/8).  512/57344 is much less than this at less than 1%.  The more interesting bit about size class 52 is a rule documented at mksizeclasses.go#L139-L144:

    // Increase object sizes if we can fit the same number of larger objects
    // into the same number of pages. For example, we choose size 8448 above
    // with 6 objects in 7 pages. But we can well use object size 9472,
    // which is also 6 objects in 7 pages but +1024 bytes (+12.12%).
    // We need to preserve at least largeSizeDiv alignment otherwise
    // sizeToClass won't work.

In other words, what's going on here is that the algorithm chose 8448 for size class 52 (because it's an alignment increment of 256 greater than size class 51 at 8192 bytes), then calculated the number of pages needed to achieve a tail waste of 12.5% or less (6 objects in 7 pages), then bumped up the allocation size for the class to the maximum multiple of the alignment size that still fits into the same number of pages: 9472.

Is it correct with respect to the documentation and algorithm?  Yes.  Is it optimal?  I believe it's close.  As Axel points out, unless you happen to be allocating a lot of objects in multiples of 37 with natural sizes between 9472 and 512/6 less than that (~9387), the effect from rounding up to 9472 will overwhelm the effect of tail waste.

-peter

To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfE%3D8ekgkEf_VCtFNek26M287uE3HUkgtrRvGx9BQLNfiw%40mail.gmail.com.