runtime: treap implementation of find() doesn't return the best-fit span

[mknyszek]

A week or so ago I discovered that the implementation of find() (formerly remove()) in mgclarge.go doesn't correspond to the comment above it.

For example, given the following treap layout (each node is labeled with the size of the span at that node in pages):

Calling find(5) on this today will return "5000" instead of one of the "5" nodes.

Note that this is a valid structure that may actually appear in practice because the treap is balanced randomly. The fact that it's not best-fit is also not strictly-speaking incorrect: the function still maintains all the invariants the calling code expects, the fact that it's not best-fit is not one of them.

While the current implementation is probably faster than a true best-fit allocation strategy, there are problematic fragmentation concerns associated with deviating from either best-fit or address-ordered first-fit (https://www.cs.tufts.edu/~nr/cs257/archive/paul-wilson/fragmentation.pdf).

This unusual allocation policy wasn't even noticeable prior to Go 1.12 because we had a set of linked-lists which would be checked in size order: spans of size <=128 would be allocated in best-fit order! Anything bigger would not.

As of Go 1.12 though, everything relies on this crazy ordering.

Many, many eyeballs have looked over that code, but it wasn't until I added treap tests in Go 1.13 that I actually noticed a problem. Also, some users have been reporting an increase in virtual memory usage in Go 1.12, which is likely related.

This should be fixed sooner rather than later. I'm still hoping to get a version of my proposal in for Go 1.13 (#30333) which would move us over to an address-ordered first-fit policy (that is tested) which would solve this (and is confirmed to reduce VSS growth issues).

CC @aclements

[gopherbot]

Change https://golang.org/cl/173479 mentions this issue: runtime: make mTreap.find actually find the best fit

[mknyszek]

@gopherbot please open a backport to 1.12. The VSS growth problem has been bad enough that it's prevented some users from being able to move to 1.12, since some of the heap metadata grows proportionally with the amount of mapped memory.

[gopherbot]

Backport issue(s) opened: #31677 (for 1.12).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases.