• Michael Anthony Knyszek's avatar
    runtime: split spans during allocation without treap removal · 5c15ed64
    Michael Anthony Knyszek authored
    Now that the treap is first-fit, we can make a nice optimization.
    Mainly, since we know that span splitting doesn't modify the relative
    position of a span in a treap, we can actually modify a span in-place
    on the treap. The only caveat is that we need to update the relevant
    metadata.
    
    To enable this optimization, this change introduces a mutate method on
    the iterator which takes a callback that is passed the iterator's span.
    The method records some properties of the span before it calls into the
    callback and then uses those records to see what changed and update
    treap metadata appropriately.
    
    Change-Id: I74f7d2ee172800828434ba0194d3d78d3942acf2
    Reviewed-on: https://go-review.googlesource.com/c/go/+/174879
    Run-TryBot: Michael Knyszek <mknyszek@google.com>
    Reviewed-by: default avatarAustin Clements <austin@google.com>
    5c15ed64
mheap.go 60.2 KB