• Michael Anthony Knyszek's avatar
    runtime: merge all treaps into one implementation · 9baa4301
    Michael Anthony Knyszek authored
    This change modifies the treap implementation to support holding all
    spans in a single treap, instead of keeping them all in separate treaps.
    
    This improves ergonomics for nearly all treap-related callsites.
    With that said, iteration is now more expensive, but it never occurs on
    the fast path, only on scavenging-related paths.
    
    This change opens up the opportunity for further optimizations, such as
    splitting spans without treap removal (taking treap removal off the span
    allocator's critical path) as well as improvements to treap iteration
    (building linked lists for each iteration type and managing them on
    insert/removal, since those operations should be less frequent).
    
    For #30333.
    
    Change-Id: I3dac97afd3682a37fda09ae8656a770e1369d0a9
    Reviewed-on: https://go-review.googlesource.com/c/go/+/174398
    Run-TryBot: Michael Knyszek <mknyszek@google.com>
    TryBot-Result: Gobot Gobot <gobot@golang.org>
    Reviewed-by: default avatarAustin Clements <austin@google.com>
    9baa4301
mheap.go 59.2 KB