]> Cypherpunks repositories - gostls13.git/commit
runtime: on bigger maps, start iterator at a random bucket.
authorKeith Randall <khr@golang.org>
Tue, 9 Sep 2014 00:42:21 +0000 (17:42 -0700)
committerKeith Randall <khr@golang.org>
Tue, 9 Sep 2014 00:42:21 +0000 (17:42 -0700)
commit55c458e05f35d0d5d539107da07b744ad96f268e
treed42d331a837fed9fe38c2d2b1fbbcfde48c540ae
parentd2788dc50308104ae642bd3fc043f2faf9bb413f
runtime: on bigger maps, start iterator at a random bucket.

This change brings the iter/delete pattern down to O(n lgn) from O(n^2).

Fixes #8412.

before:
BenchmarkMapPop100    50000      32498 ns/op
BenchmarkMapPop1000      500    3244851 ns/op
BenchmarkMapPop10000        5  270276855 ns/op

after:
BenchmarkMapPop100   100000      16169 ns/op
BenchmarkMapPop1000     5000     300416 ns/op
BenchmarkMapPop10000      300    5990814 ns/op

LGTM=iant
R=golang-codereviews, iant, khr
CC=golang-codereviews
https://golang.org/cl/141270043
src/runtime/hashmap.go
src/runtime/map_test.go