diff options
| -rw-r--r-- | src/runtime/mranges.go | 40 |
1 files changed, 33 insertions, 7 deletions
diff --git a/src/runtime/mranges.go b/src/runtime/mranges.go index 16acadcff1..84a2c06dbb 100644 --- a/src/runtime/mranges.go +++ b/src/runtime/mranges.go @@ -172,20 +172,46 @@ func (a *addrRanges) init(sysStat *sysMemStat) { a.totalBytes = 0 } -// findSucc returns the first index in a such that base is +// findSucc returns the first index in a such that addr is // less than the base of the addrRange at that index. func (a *addrRanges) findSucc(addr uintptr) int { - // TODO(mknyszek): Consider a binary search for large arrays. - // While iterating over these ranges is potentially expensive, - // the expected number of ranges is small, ideally just 1, - // since Go heaps are usually mostly contiguous. base := offAddr{addr} - for i := range a.ranges { + + // Narrow down the search space via a binary search + // for large addrRanges until we have at most iterMax + // candidates left. + const iterMax = 8 + bot, top := 0, len(a.ranges) + for top-bot > iterMax { + i := ((top - bot) / 2) + bot + if a.ranges[i].contains(base.addr()) { + // a.ranges[i] contains base, so + // its successor is the next index. + return i + 1 + } + if base.lessThan(a.ranges[i].base) { + // In this case i might actually be + // the successor, but we can't be sure + // until we check the ones before it. + top = i + } else { + // In this case we know base is + // greater than or equal to a.ranges[i].limit-1, + // so i is definitely not the successor. + // We already checked i, so pick the next + // one. + bot = i + 1 + } + } + // There are top-bot candidates left, so + // iterate over them and find the first that + // base is strictly less than. + for i := bot; i < top; i++ { if base.lessThan(a.ranges[i].base) { return i } } - return len(a.ranges) + return top } // findAddrGreaterEqual returns the smallest address represented by a |