aboutsummaryrefslogtreecommitdiff
path: root/src/runtime/hashmap.go
AgeCommit message (Collapse)Author
2018-02-17runtime: rename map implementation and test files to use a common prefixMartin Möhrmann
Rename all map implementation and test files to use "map" as a file name prefix instead of "hashmap" for the implementation and "map" for the test file names. Change-Id: I7b317c1f7a660b95c6d1f1a185866f2839e69446 Reviewed-on: https://go-review.googlesource.com/90336 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2018-02-15runtime: use new instead of newobject to create hmap in makemapMartin Möhrmann
The runtime.hmap type is known at compile time. Using new(hmap) avoids loading the hmap type from the maptype supplied as an argument to makemap which is only known at runtime. This change makes makemap consistent with makemap_small by using new(hmap) instead of newobject in both functions. Change-Id: Ia47acfda527e8a71d15a1a7a4c2b54fb923515eb Reviewed-on: https://go-review.googlesource.com/91775 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-11-02cmd/compile: specialize map creation for small hint sizesMartin Möhrmann
Handle make(map[any]any) and make(map[any]any, hint) where hint <= BUCKETSIZE special to allow for faster map initialization and to improve binary size by using runtime calls with fewer arguments. Given hint is smaller or equal to BUCKETSIZE in which case overLoadFactor(hint, 0) is false and no buckets would be allocated by makemap: * If hmap needs to be allocated on the stack then only hmap's hash0 field needs to be initialized and no call to makemap is needed. * If hmap needs to be allocated on the heap then a new special makehmap function will allocate hmap and intialize hmap's hash0 field. Reduces size of the godoc by ~36kb. AMD64 name old time/op new time/op delta NewEmptyMap 16.6ns ± 2% 5.5ns ± 2% -66.72% (p=0.000 n=10+10) NewSmallMap 64.8ns ± 1% 56.5ns ± 1% -12.75% (p=0.000 n=9+10) Updates #6853 Change-Id: I624e90da6775afaa061178e95db8aca674f44e9b Reviewed-on: https://go-review.googlesource.com/61190 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-09-22runtime: remove getcallerpc argumentAustin Clements
Now that getcallerpc is a compiler intrinsic on x86 and non-x86 platforms don't need the argument, we can drop it. Sadly, this doesn't let us remove any dummy arguments since all of those cases also use getcallersp, which still takes the argument pointer, but this is at least an improvement. Change-Id: I9c34a41cf2c18cba57f59938390bf9491efb22d2 Reviewed-on: https://go-review.googlesource.com/65474 Run-TryBot: Austin Clements <austin@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: David Chase <drchase@google.com>
2017-09-13runtime: refactor hmap.extra.overflow array into two separate fieldsMartin Möhrmann
This makes it easier to deduce from the field names which overflow field corresponds to h.buckets and which to h.oldbuckets by aligning the naming with the buckets fields in hmap. Change-Id: I8d6a729229a190db0212bac012ead1a3c13cf5d0 Reviewed-on: https://go-review.googlesource.com/62411 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-09-13runtime: move evacuateX evacuateY relation check from makemap to evacuateMartin Möhrmann
Move the check near the code in evacuate that relies on the relation evacuateX+1 == evacuateY. If the relation is fullfilled the check is known to be true at compile time and removed by the compiler. Change-Id: I711b75e09047bf347819ccaeec41d244a5883867 Reviewed-on: https://go-review.googlesource.com/62410 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-09-06runtime: avoid redundant zeroing of hiterMartin Möhrmann
The compiler and reflect already zero hiter before mapiterinit. While here expand the documentation for mapiterinit. Change-Id: I78b05d4d14bf78e8091e5353cdac80ffed30ca1e Reviewed-on: https://go-review.googlesource.com/60673 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-09-05runtime: move map ismapkey check to the compilerMartin Möhrmann
Remove the runtime ismapkey check from makemap and add a check that the map key type supports comparison to the hmap construction in the compiler. Move the ismapkey check for the reflect code path into reflect_makemap. Change-Id: I718f79b0670c05b63ef31721e72408f59ec4ae86 Reviewed-on: https://go-review.googlesource.com/61035 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-09-02runtime: fix hashmap load factor computationKeith Randall
overLoadFactor wasn't really doing what it says it does. It was reporting overOrEqualToLoadFactor. That's actually what we want when adding an entry to a map, but it isn't what we want when constructing a map in the first place. The impetus for this change is that if you make a map with a hint of exactly 8 (which happens, for example, with the unitMap in time/format.go), we allocate 2 buckets for it instead of 1. Instead, make overLoadFactor really report when it is > the max allowed load factor, not >=. Adjust the callers who want to ensure that the map is no more than the max load factor after an insertion by adding a +1 to the current (pre-addition) size. Change-Id: Ie8d85344800a9a870036b637b1031ddd9e4b93f9 Reviewed-on: https://go-review.googlesource.com/61053 Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-08-30runtime: move dynamic makemap checks into cmd/compileMartin Möhrmann
Check map invariants, type size and alignments during compile time. Keep runtime checks for reflect by adding them to reflect_makemap. Change-Id: Ia28610626591bf7fafb7d5a1ca318da272e54879 Reviewed-on: https://go-review.googlesource.com/59914 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-24runtime: refactor walking of bucket overflowsJosh Bleecher Snyder
This eliminates a nil check of b while evaluating b.tophash, which is in the inner loop of many hot map functions. It also makes the code a bit clearer. Also remove some gotos in favor of labeled breaks. On non-x86 architectures, this change introduces a pointless reg-reg move, although the cause is well-understood (#21572). Change-Id: Ib7ee58b59ea5463b92e1590c8b8f5c0ef87d410a Reviewed-on: https://go-review.googlesource.com/58372 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-24runtime: mask shifts in map implementation on x86Josh Bleecher Snyder
This slightly improves the generated code on x86 architectures, including on many hot paths. It is a no-op on other architectures. Change-Id: I86336fd846bc5805a27bbec572e8c73dcbd0d567 Reviewed-on: https://go-review.googlesource.com/57411 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-23runtime: only clear pointer-containing memory during map deleteJosh Bleecher Snyder
When deleting entries from a map, only clear the key and value if they contain pointers. And use memclrHasPointers to do so. While we're here, specialize key clearing in mapdelete_faststr, and fix another missed usage of add in mapdelete. Benchmarking impeded by #21546. Change-Id: I3f6f924f738d6b899b722d6438e9e63f52359b84 Reviewed-on: https://go-review.googlesource.com/57630 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-23runtime: use add in mapdelete*Josh Bleecher Snyder
This better matches the style of the rest of the runtime. Change-Id: I6abb755df50eb3d9086678629c0d184177e1981f Reviewed-on: https://go-review.googlesource.com/57610 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-08-23runtime: strength reduce key pointer calculations in mapaccess*_fast*Josh Bleecher Snyder
While we're here, check string length before checking b.tophash. name old time/op new time/op delta MapStringKeysEight_16-8 11.4ns ±10% 7.0ns ± 2% -38.27% (p=0.000 n=29+28) MapStringKeysEight_32-8 10.9ns ± 2% 6.3ns ± 3% -41.89% (p=0.000 n=26+30) MapStringKeysEight_64-8 10.8ns ± 3% 6.3ns ± 2% -41.52% (p=0.000 n=28+27) MapStringKeysEight_1M-8 10.9ns ± 4% 6.3ns ± 2% -41.91% (p=0.000 n=29+29) IntMap-8 7.05ns ± 4% 6.77ns ± 3% -3.94% (p=0.000 n=29+30) Change-Id: I0f3dc3301bdf550e4ac5250e1e64e7f2a0ffb269 Reviewed-on: https://go-review.googlesource.com/57590 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-23runtime: fix makemap64 function signatureMartin Möhrmann
During rebase of golang.org/cl/55152 the bucket argument which was removed in golang.org/cl/56290 from makemap was not removed from the argument list of makemap64. This did lead to "pointer in unallocated span" errors on 32bit platforms since the compiler did only generate calls to makemap64 without the bucket argument. Fixes #21568 Change-Id: Ia964a3c285837cd901297f4e16e40402148f8c1c Reviewed-on: https://go-review.googlesource.com/57990 Reviewed-by: Cherry Zhang <cherryyz@google.com> Run-TryBot: Cherry Zhang <cherryyz@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
2017-08-22cmd/compile: generate makemap calls with int argumentsMartin Möhrmann
Where possible generate calls to runtime makemap with int hint argument during compile time instead of makemap with int64 hint argument. This eliminates converting the hint argument for calls to makemap with int64 hint argument for platforms where int64 values do not fit into an argument of type int. A similar optimization for makeslice was introduced in CL golang.org/cl/27851. 386: name old time/op new time/op delta NewEmptyMap 53.5ns ± 5% 41.9ns ± 5% -21.56% (p=0.000 n=10+10) NewSmallMap 182ns ± 1% 165ns ± 1% -8.92% (p=0.000 n=10+10) Change-Id: Ibd2b4c57b36f171b173bf7a0602b3a59771e6e44 Reviewed-on: https://go-review.googlesource.com/55142 Reviewed-by: Keith Randall <khr@golang.org>
2017-08-22cmd/compile: pass stack allocated bucket to makemap inside hmapMartin Möhrmann
name old time/op new time/op delta NewEmptyMap 53.2ns ± 7% 48.0ns ± 5% -9.77% (p=0.000 n=20+20) NewSmallMap 111ns ± 1% 106ns ± 2% -3.78% (p=0.000 n=20+19) Change-Id: I979d21ab16eae9f6893873becca517db57e054b5 Reviewed-on: https://go-review.googlesource.com/56290 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
2017-08-20runtime: don't clear pointer-free memory when growing mapsJosh Bleecher Snyder
If there are no pointers, then clearing memory doesn't help GC, and the memory is otherwise dead, so don't bother clearing it. Change-Id: I953f4a3264939f2825e82292030eda2e835cbb97 Reviewed-on: https://go-review.googlesource.com/57350 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-08-18runtime: make evacDst a top level typeJosh Bleecher Snyder
This will reduce duplication when evacuate is specialized. Change-Id: I34cdfb7103442d3e0ea908c970fb46334b86d5c4 Reviewed-on: https://go-review.googlesource.com/56934 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Reviewed-by: Avelino <t@avelino.xxx> Reviewed-by: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2017-08-18runtime: split advanceEvacuationMark from evacuateJosh Bleecher Snyder
Minor refactoring. This is a step towards specializing evacuate for mapfast key types. Change-Id: Icffe2759b7d38e5c008d03941918d5a912ce62f6 Reviewed-on: https://go-review.googlesource.com/56933 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-18runtime: tiny refactor in evacuateJosh Bleecher Snyder
Since oldbucket == h.nevacuate, we can just increment h.nevacuate here. This removes oldbucket from scope, which will be useful shortly. Change-Id: I70f81ec3995f17845ebf5d77ccd20ea4338f23e6 Reviewed-on: https://go-review.googlesource.com/56932 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Reviewed-by: Avelino <t@avelino.xxx> Reviewed-by: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2017-08-18runtime: don't cache t.key.alg in evacuateJosh Bleecher Snyder
The number of times that alg has to be spilled and restored makes it better to just reload it. Change-Id: I2674752a889ecad59dab54da1d68fad03db1ca85 Reviewed-on: https://go-review.googlesource.com/56931 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Daniel Martí <mvdan@mvdan.cc> Reviewed-by: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2017-08-18runtime: simplify evacuate's handling of NaNsJosh Bleecher Snyder
The new code is not quite equivalent to the old, in that if newbit was very large it might have altered the new tophash. The old behavior is unnecessary and probably undesirable. Change-Id: I7fb3222520cb61081a857adcddfbb9078ead7122 Reviewed-on: https://go-review.googlesource.com/56930 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-18runtime: no need to protect key/value increments against end of bucketKeith Randall
After the key and value arrays, we have an overflow pointer. So there's no way a past-the-end key or value pointer could point past the end of the containing bucket. So we don't need this additional protection. Update #21459 Change-Id: I7726140033b06b187f7a7d566b3af8cdcaeab0b0 Reviewed-on: https://go-review.googlesource.com/56772 Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com> Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: Avelino <t@avelino.xxx>
2017-08-17runtime: avoid zeroing hmap fields in makemap twiceMartin Möhrmann
Stack allocated hmap structs are explicitly zeroed before being passed by pointer to makemap. Heap allocated hmap structs are created with newobject which also zeroes on allocation. Therefore, setting the hmap fields to 0 or nil is redundant since they will have been zeroed when hmap was allocated. Change-Id: I5fc55b75e9dc5ba69f5e3588d6c746f53b45ba66 Reviewed-on: https://go-review.googlesource.com/56291 Reviewed-by: Keith Randall <khr@golang.org>
2017-08-15runtime: refactor out tophash calculationJosh Bleecher Snyder
No functional changes; tophash is inlined. Change-Id: Ic8ce95b3622eafbddcfbc97f8c630ab8c5bfe7ad Reviewed-on: https://go-review.googlesource.com/55233 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-15runtime: unify cases in mapiternextJosh Bleecher Snyder
The preceding cleanup made it clear that two cases (have golden data, unreachable key) are handled identically. Simplify the control flow to reflect that. Simplifies the code and generates shorter machine code. Change-Id: Id612e0da6679813e855506f47222c58ea6497d70 Reviewed-on: https://go-review.googlesource.com/55093 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-15runtime: mask a bounded slice access in hashmap evacuateJosh Bleecher Snyder
Shaves a few instructions off. Change-Id: I39f1b01ae7e770d632d5e77a6aa4b5a1f123b41a Reviewed-on: https://go-review.googlesource.com/55090 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-14runtime: refactor evacuate x/y handlingJosh Bleecher Snyder
This change unifies the x and y cases. It shrinks evacuate's machine code by ~25% and its stack size by ~15%. It also eliminates a critical branch. Whether an entry should go to x or y is designed to be unpredictable. As a result, half of the branch predictions for useX were wrong. Mispredicting that branch can easily incur an expensive cache miss. Switching to an xy array allows elimination of that branch, which in turn reduces cache misses. Change-Id: Ie9cef53744b96c724c377ac0985b487fc50b49b1 Reviewed-on: https://go-review.googlesource.com/54653 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-14runtime: calculate k only once in mapiternextJosh Bleecher Snyder
Make the calculation of k and v a bit lazier. None of the following code cares about indirect-vs-direct k, and it happens on all code paths, so check t.indirectkey earlier. Simplifies the code and reduces both machine code and stack size. Change-Id: I5ea4c0772848d7a4b15383baedb9a1f7feb47201 Reviewed-on: https://go-review.googlesource.com/55092 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-14runtime: use integer math for hashmap overLoadFactorJosh Bleecher Snyder
Change-Id: I92cf39a05e738a03d956779d7a1ab1ef8074b2ab Reviewed-on: https://go-review.googlesource.com/54655 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-14runtime: replace some uses of newarray with newobject for mapsMartin Möhrmann
This avoids the never triggered capacity checks in newarray. Change-Id: Ib72b204adcb9e3fd3ab963defe0cd40e22d5d492 Reviewed-on: https://go-review.googlesource.com/54731 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-08-14runtime: remove indentation in mapiternextJosh Bleecher Snyder
Invert the condition and continue, to remove indentation. Change-Id: Id62a5d9abc9a4df1193bcf15f95f70f2c2e2abac Reviewed-on: https://go-review.googlesource.com/55091 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-08-14runtime: simplify hashmap tooManyOverflowBucketsJosh Bleecher Snyder
This generates better code. Masking B in the return statement should be unnecessary, but the compiler is understandably not yet clever enough to see that. Someday, it'd also be nice for the compiler to generate a CMOV for the saturation if statement. Change-Id: Ie1c157b21f5212610da1f3c7823a93816b3b61b9 Reviewed-on: https://go-review.googlesource.com/54656 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-08-14runtime: CSE some function arguments in evacuateJosh Bleecher Snyder
Shrinks evacuate's machine code a little. Change-Id: I08874c92abdc7e621bc0737e22f2a6be31542cab Reviewed-on: https://go-review.googlesource.com/54652 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-08-14runtime: remove indentation in evacuateJosh Bleecher Snyder
Combine conditions into a single if statement. This is more readable. It should generate identical machine code, but it doesn't. The new code is shorter. Change-Id: I9bf52f8f288b0df97a2b9b4e4183f6ca74175e8a Reviewed-on: https://go-review.googlesource.com/54651 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Martin Möhrmann <moehrmann@google.com>
2017-05-02runtime: don't panic for bad size hint in hashmapFilip Gruszczynski
Because the hint parameter is supposed to be treated purely as a hint, if it doesn't meet the requirements we disregard it and continue as if there was no hint at all. Fixes #19926 Change-Id: I86e7f99472fad6b99ba4e2fd33e4a9e55d55115e Reviewed-on: https://go-review.googlesource.com/40854 Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-05-01runtime: use 64 bit calculation in overLoadFactorJosh Bleecher Snyder
overLoadFactor used a uintptr for its calculations. When the number of potential buckets was large, perhaps due to a coding error or corrupt/malicious user input leading to a very large map size hint, this led to overflow on 32 bit systems. This overflow resulted in an infinite loop. Prevent it by always using a 64 bit calculation. Updates #20195 Change-Id: Iaabc710773cd5da6754f43b913478cc5562d89a2 Reviewed-on: https://go-review.googlesource.com/42185 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-04-19runtime: preallocate some overflow bucketsJosh Bleecher Snyder
When allocating a non-small array of buckets for a map, also preallocate some overflow buckets. The estimate of the number of overflow buckets is based on a simulation of putting mid=(low+high)/2 elements into a map, where low is the minimum number of elements needed to reach this value of b (according to overLoadFactor), and high is the maximum number of elements possible to put in this value of b (according to overLoadFactor). This estimate is surprisingly reliable and accurate. The number of overflow buckets needed is quadratic, for a fixed value of b. Using this mid estimate means that we will overallocate a few too many overflow buckets when the actual number of elements is near low, and underallocate significantly too few overflow buckets when the actual number of elements is near high. The mechanism introduced in this CL can be re-used for other overflow bucket optimizations. For example, given an initial size hint, we could estimate quite precisely the number of overflow buckets. This is #19931. We could also change from "non-nil means end-of-list" to "pointer-to-hmap.buckets means end-of-list", and then create a linked list of reusable overflow buckets when they are freed by map growth. That is #19992. We could also use a similar mechanism to do bulk allocation of overflow buckets. All these uses can co-exist with only the one additional pointer in mapextra, given a little care. name old time/op new time/op delta MapPopulate/1-8 60.1ns ± 2% 60.3ns ± 2% ~ (p=0.278 n=19+20) MapPopulate/10-8 577ns ± 1% 578ns ± 1% ~ (p=0.140 n=20+20) MapPopulate/100-8 8.06µs ± 1% 8.19µs ± 1% +1.67% (p=0.000 n=20+20) MapPopulate/1000-8 104µs ± 1% 104µs ± 1% ~ (p=0.317 n=20+20) MapPopulate/10000-8 891µs ± 1% 888µs ± 1% ~ (p=0.101 n=19+20) MapPopulate/100000-8 8.61ms ± 1% 8.58ms ± 0% -0.34% (p=0.009 n=20+17) name old alloc/op new alloc/op delta MapPopulate/1-8 0.00B 0.00B ~ (all equal) MapPopulate/10-8 179B ± 0% 179B ± 0% ~ (all equal) MapPopulate/100-8 3.33kB ± 0% 3.38kB ± 0% +1.48% (p=0.000 n=20+16) MapPopulate/1000-8 55.5kB ± 0% 53.4kB ± 0% -3.84% (p=0.000 n=19+20) MapPopulate/10000-8 432kB ± 0% 428kB ± 0% -1.06% (p=0.000 n=19+20) MapPopulate/100000-8 3.65MB ± 0% 3.62MB ± 0% -0.70% (p=0.000 n=20+20) name old allocs/op new allocs/op delta MapPopulate/1-8 0.00 0.00 ~ (all equal) MapPopulate/10-8 1.00 ± 0% 1.00 ± 0% ~ (all equal) MapPopulate/100-8 18.0 ± 0% 17.0 ± 0% -5.56% (p=0.000 n=20+20) MapPopulate/1000-8 96.0 ± 0% 72.6 ± 1% -24.38% (p=0.000 n=20+20) MapPopulate/10000-8 625 ± 0% 319 ± 0% -48.86% (p=0.000 n=20+20) MapPopulate/100000-8 6.23k ± 0% 4.00k ± 0% -35.79% (p=0.000 n=20+20) Change-Id: I01f41cb1374bdb99ccedbc00d04fb9ae43daa204 Reviewed-on: https://go-review.googlesource.com/40979 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-04-19runtime: add bmap.setoverflowJosh Bleecher Snyder
bmap already has a overflow (getter) method. Add a setoverflow (setter) method, for readability. Updates #19931 Updates #19992 Change-Id: I00b3d94037c0d75508a7ebd51085c5c3857fb764 Reviewed-on: https://go-review.googlesource.com/40977 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-04-19runtime: convert hmap.overflow into hmap.extraJosh Bleecher Snyder
Any change to how we allocate overflow buckets will require some extra hmap storage, but we don't want hmap to grow, particular as small maps usually don't need overflow buckets. This CL converts the existing hmap overflow field, which is usually used for pointer-free maps, into a generic extra field. This extra field can be used to hold data that is optional. If it is valuable enough to do have special handling of overflow buckets, which are medium-sized, it is valuable enough to pay an extra alloc and two extra words for. Adding fields to extra would entail adding overhead to pointer-free maps; any mapextra fields added would need to be weighed against that. This CL is just rearrangement, though. Updates #19931 Updates #19992 Change-Id: If8537a206905b9d4dc6cd9d886184ece671b3f80 Reviewed-on: https://go-review.googlesource.com/40976 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-04-19runtime: refactor hmap setoverflow into newoverflowJosh Bleecher Snyder
This simplifies the code, as well as providing a single place to modify to change the allocation of new overflow buckets. Updates #19931 Updates #19992 Change-Id: I77070619f5c8fe449bbc35278278bca5eda780f2 Reviewed-on: https://go-review.googlesource.com/40975 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-04-04reflect: add MakeMapWithSize for creating maps with size hintFilip Gruszczyński
Providing size hint when creating a map allows avoiding re-allocating underlying data structure if we know how many elements are going to be inserted. This can be used for example during decoding maps in gob. Fixes #19599 Change-Id: I108035fec29391215d2261a73eaed1310b46bab1 Reviewed-on: https://go-review.googlesource.com/38335 Reviewed-by: Rob Pike <r@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org>
2017-03-02runtime: delay marking maps as writing until after first alg callJosh Bleecher Snyder
Fixes #19359 Change-Id: I196b47cf0471915b6dc63785e8542aa1876ff695 Reviewed-on: https://go-review.googlesource.com/37665 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2017-02-28runtime: evacuate old map buckets more consistentlyJosh Bleecher Snyder
During map growth, buckets are evacuated in two ways. When a value is altered, its containing bucket is evacuated. Also, an evacuation mark is maintained and advanced every time. Prior to this CL, the evacuation mark was always incremented, even if the next bucket to be evacuated had already been evacuated. This CL changes evacuation mark advancement to skip previously evacuated buckets. This has the effect of making map evacuation both more aggressive and more consistent. Aggressive map evacuation is good. While the map is growing, map accesses must check two buckets, which may be far apart in memory. Map growth also delays garbage collection. And if map evacuation is not aggressive enough, there is a risk that a populate-once read-many map may be stuck permanently in map growth. This CL does not eliminate that possibility, but it shrinks the window. There is minimal impact on map benchmarks: name old time/op new time/op delta MapPop100-8 12.4µs ±11% 12.4µs ± 7% ~ (p=0.798 n=15+15) MapPop1000-8 240µs ± 8% 235µs ± 8% ~ (p=0.217 n=15+14) MapPop10000-8 4.49ms ±10% 4.51ms ±15% ~ (p=1.000 n=15+13) MegMap-8 11.9ns ± 2% 11.8ns ± 0% -1.01% (p=0.000 n=15+11) MegOneMap-8 9.30ns ± 1% 9.29ns ± 1% ~ (p=0.955 n=14+14) MegEqMap-8 31.9µs ± 5% 31.9µs ± 3% ~ (p=0.935 n=15+15) MegEmptyMap-8 2.41ns ± 2% 2.41ns ± 0% ~ (p=0.594 n=12+14) SmallStrMap-8 12.8ns ± 1% 12.7ns ± 1% ~ (p=0.569 n=14+13) MapStringKeysEight_16-8 13.6ns ± 1% 13.7ns ± 2% ~ (p=0.100 n=13+15) MapStringKeysEight_32-8 12.1ns ± 1% 12.1ns ± 2% ~ (p=0.340 n=15+15) MapStringKeysEight_64-8 12.1ns ± 1% 12.1ns ± 2% ~ (p=0.582 n=15+14) MapStringKeysEight_1M-8 12.0ns ± 1% 12.1ns ± 1% ~ (p=0.267 n=15+14) IntMap-8 7.96ns ± 1% 7.97ns ± 2% ~ (p=0.991 n=15+13) RepeatedLookupStrMapKey32-8 15.8ns ± 2% 15.8ns ± 1% ~ (p=0.393 n=15+14) RepeatedLookupStrMapKey1M-8 35.3µs ± 2% 35.3µs ± 1% ~ (p=0.815 n=15+15) NewEmptyMap-8 36.0ns ± 4% 36.4ns ± 7% ~ (p=0.270 n=15+15) NewSmallMap-8 85.5ns ± 1% 85.6ns ± 1% ~ (p=0.674 n=14+15) MapIter-8 89.9ns ± 6% 90.8ns ± 6% ~ (p=0.467 n=15+15) MapIterEmpty-8 10.0ns ±22% 10.0ns ±25% ~ (p=0.846 n=15+15) SameLengthMap-8 4.18ns ± 1% 4.17ns ± 1% ~ (p=0.653 n=15+14) BigKeyMap-8 20.2ns ± 1% 20.1ns ± 1% -0.82% (p=0.002 n=15+15) BigValMap-8 22.5ns ± 8% 22.3ns ± 6% ~ (p=0.615 n=15+15) SmallKeyMap-8 15.3ns ± 1% 15.3ns ± 1% ~ (p=0.754 n=15+14) ComplexAlgMap-8 58.4ns ± 1% 58.7ns ± 1% +0.52% (p=0.000 n=14+15) There is a tiny but detectable difference in the compiler: name old time/op new time/op delta Template 218ms ± 5% 219ms ± 4% ~ (p=0.094 n=98+98) Unicode 93.6ms ± 5% 93.6ms ± 4% ~ (p=0.910 n=94+95) GoTypes 596ms ± 5% 598ms ± 6% ~ (p=0.533 n=98+100) Compiler 2.72s ± 3% 2.72s ± 4% ~ (p=0.238 n=100+99) SSA 4.11s ± 3% 4.11s ± 3% ~ (p=0.864 n=99+98) Flate 129ms ± 6% 129ms ± 4% ~ (p=0.522 n=98+96) GoParser 151ms ± 4% 151ms ± 4% -0.48% (p=0.017 n=96+96) Reflect 379ms ± 3% 376ms ± 4% -0.57% (p=0.011 n=99+99) Tar 112ms ± 5% 112ms ± 6% ~ (p=0.688 n=93+95) XML 214ms ± 4% 214ms ± 5% ~ (p=0.968 n=100+99) StdCmd 16.2s ± 2% 16.2s ± 2% -0.26% (p=0.048 n=99+99) name old user-ns/op new user-ns/op delta Template 252user-ms ± 4% 250user-ms ± 4% -0.63% (p=0.020 n=98+97) Unicode 113user-ms ± 7% 114user-ms ± 5% ~ (p=0.057 n=97+94) GoTypes 776user-ms ± 5% 777user-ms ± 5% ~ (p=0.375 n=97+96) Compiler 3.61user-s ± 3% 3.60user-s ± 3% ~ (p=0.445 n=98+93) SSA 5.84user-s ± 6% 5.85user-s ± 5% ~ (p=0.542 n=100+95) Flate 154user-ms ± 5% 154user-ms ± 5% ~ (p=0.699 n=99+99) GoParser 184user-ms ± 6% 183user-ms ± 4% ~ (p=0.557 n=98+95) Reflect 461user-ms ± 5% 462user-ms ± 4% ~ (p=0.853 n=97+99) Tar 130user-ms ± 5% 129user-ms ± 6% ~ (p=0.567 n=93+100) XML 257user-ms ± 6% 258user-ms ± 6% ~ (p=0.205 n=99+100) Change-Id: Id92dd54a152904069aac415e6aaaab5c67f5f476 Reviewed-on: https://go-review.googlesource.com/37011 Reviewed-by: Keith Randall <khr@golang.org> Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-10-28runtime, cmd/compile: rename memclr -> memclrNoHeapPointersAustin Clements
Since barrier-less memclr is only safe in very narrow circumstances, this commit renames memclr to avoid accidentally calling memclr on typed memory. This can cause subtle, non-deterministic bugs, so it's worth some effort to prevent. In the near term, this will also prevent bugs creeping in from any concurrent CLs that add calls to memclr; if this happens, whichever patch hits master second will fail to compile. This also adds the other new memclr variants to the compiler's builtin.go to minimize the churn on that binary blob. We'll use these in future commits. Updates #17503. Change-Id: I00eead049f5bd35ca107ea525966831f3d1ed9ca Reviewed-on: https://go-review.googlesource.com/31369 Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Rick Hudson <rlh@golang.org>
2016-10-28runtime: use typedmemclr for typed memoryAustin Clements
The hybrid barrier requires distinguishing typed and untyped memory even when zeroing because the *current* contents of the memory matters even when overwriting. This commit introduces runtime.typedmemclr and runtime.memclrHasPointers as a typed memory clearing functions parallel to runtime.typedmemmove. Currently these simply call memclr, but with the hybrid barrier we'll need to shade any pointers we're overwriting. These will provide us with the necessary hooks to do so. Updates #17503. Change-Id: I74478619f8907825898092aaa204d6e4690f27e6 Reviewed-on: https://go-review.googlesource.com/31366 Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Rick Hudson <rlh@golang.org>
2016-10-12cmd/compile,runtime: redo how map assignments workKeith Randall
To compile: m[k] = v instead of: mapassign(maptype, m, &k, &v), do do: *mapassign(maptype, m, &k) = v mapassign returns a pointer to the value slot in the map. It is just like mapaccess except that it will allocate a new slot if k is not already present in the map. This makes map accesses faster but potentially larger (codewise). It is faster because the write into the map is done when the compiler knows the concrete type, so it can be done with a few store instructions instead of calling typedmemmove. We also potentially avoid stack temporaries to hold v. The code can be larger when the map has pointers in its value type, since there is a write barrier call in addition to the mapassign call. That makes the code at the callsite a bit bigger (go binary is 0.3% bigger). This CL is in preparation for doing operations like m[k] += v with only a single runtime call. That will roughly double the speed of such operations. Update #17133 Update #5147 Change-Id: Ia435f032090a2ed905dac9234e693972fe8c2dc5 Reviewed-on: https://go-review.googlesource.com/30815 Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-10-03runtime: document bmap.tophashAustin Clements
In particular, it wasn't obvious that some values are special (unless you also found those special values), so document that it isn't necessarily a hash value. Change-Id: Iff292822b44408239e26cd882dc07be6df2c1d38 Reviewed-on: https://go-review.googlesource.com/30143 Run-TryBot: Austin Clements <austin@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
generated by cgit v1.3 (git 2.53.0) at 2026-04-15 21:01:45 +0000