| Age | Commit message (Collapse) | Author |
|---|
|
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>
|
|
Calls to writebarrierptr can simply be actual pointer writes. Calls to
writebarrierptr_prewrite need to go through the write barrier buffer.
Updates #22460.
Change-Id: I92cee4da98c5baa499f1977563757c76f95bf0ca
Reviewed-on: https://go-review.googlesource.com/92704
Run-TryBot: Austin Clements <austin@google.com>
Reviewed-by: Rick Hudson <rlh@golang.org>
|
|
The signature of the mapassign_fast* routines need to distinguish
the pointerness of their key argument. If the affected routines
suspend part way through, the object pointed to by the key might
get garbage collected because the key is typed as a uint{32,64}.
This is not a problem for mapaccess or mapdelete because the key
in those situations do not live beyond the call involved. If the
object referenced by the key is garbage collected prematurely, the
code still works fine. Even if that object is subsequently reallocated,
it can't be written to the map in time to affect the lookup/delete.
Fixes #22781
Change-Id: I0bbbc5e9883d5ce702faf4e655348be1191ee439
Reviewed-on: https://go-review.googlesource.com/79018
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
* Avoid calculating insertk until needed.
* Avoid a pointer into b.tophash and just track the insertion index.
This avoids b.tophash being marked as escaping to heap.
* Calculate val only once at the end of the mapassign functions.
Function sizes decrease slightly, e.g. for mapassign_faststr:
before "".mapassign_faststr STEXT size=1166 args=0x28 locals=0x78
after "".mapassign_faststr STEXT size=1080 args=0x28 locals=0x68
name old time/op new time/op delta
MapAssign/Int32/256-4 19.4ns ± 4% 19.5ns ±11% ~ (p=0.973 n=20+20)
MapAssign/Int32/65536-4 32.5ns ± 2% 32.4ns ± 3% ~ (p=0.078 n=20+19)
MapAssign/Int64/256-4 20.3ns ± 6% 17.6ns ± 5% -13.01% (p=0.000 n=20+20)
MapAssign/Int64/65536-4 33.3ns ± 2% 33.3ns ± 1% ~ (p=0.444 n=20+20)
MapAssign/Str/256-4 22.3ns ± 3% 22.4ns ± 3% ~ (p=0.343 n=20+20)
MapAssign/Str/65536-4 44.9ns ± 1% 43.9ns ± 1% -2.39% (p=0.000 n=20+19)
Change-Id: I2627bb8a961d366d9473b5922fa129176319eb22
Reviewed-on: https://go-review.googlesource.com/74870
Run-TryBot: Martin Möhrmann <moehrmann@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
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>
|
|
mapaccess and mapdelete functions are already optimized to prefer direct
key comparison instead of tophash checks when key comparison is cheap.
Extended version of golang.org/cl/55235.
AMD64:
name old time/op new time/op delta
MapPopulate/1 42.5ns ± 2% 40.3ns ± 2% -5.37% (p=0.000 n=9+10)
MapPopulate/10 558ns ± 1% 556ns ± 1% ~ (p=0.157 n=10+10)
MapPopulate/100 7.75µs ± 1% 7.66µs ± 2% -1.19% (p=0.001 n=10+10)
MapPopulate/1000 92.6µs ± 1% 92.0µs ± 1% -0.61% (p=0.016 n=10+8)
MapPopulate/10000 817µs ± 1% 814µs ± 1% ~ (p=0.247 n=10+10)
MapPopulate/100000 8.02ms ± 1% 7.90ms ± 2% -1.47% (p=0.007 n=10+10)
Change-Id: If0eca9931379cbbd37eb753e9bcd2888d8272153
Reviewed-on: https://go-review.googlesource.com/62050
Run-TryBot: Martin Möhrmann <moehrmann@google.com>
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
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>
|
|
Change-Id: I0360d294868ec4423e4ae036009fac4e72425c9c
Reviewed-on: https://go-review.googlesource.com/59152
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Maps with indirect values use the generic map routines.
Change-Id: Ib211e93f1dacefb988ba3d279f92a13065168079
Reviewed-on: https://go-review.googlesource.com/59135
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
Similar to CL 59110.
Change-Id: Ia2858541c86a44b105eacbca9a46b1044632c5ca
Reviewed-on: https://go-review.googlesource.com/59134
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
None of the mapfast key types are indirect.
Change-Id: I1fb2682257567ee69504082a6cdad63c99916671
Reviewed-on: https://go-review.googlesource.com/59133
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
All of the mapfast key types are reflexive.
Change-Id: I8595aed2a9d945cda1b5d08e2067dce0f1c0d585
Reviewed-on: https://go-review.googlesource.com/59132
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
Change-Id: I89c3c3b21d7a4acbc49b14a52ac8d9a5861c0c39
Reviewed-on: https://go-review.googlesource.com/59131
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
The newly added routines are exact copies of the generic routines,
except for the function names and that growWork_fastX calls evacuate_fastX.
Actual optimization will happen in subsequent CLs.
This is intended to ease reviewing.
Change-Id: I52ef7dd40b2bdfc9cba2496544c0604e6e71cf7f
Reviewed-on: https://go-review.googlesource.com/59130
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Prior to this change, we use typedmemmove to write the key
value to its new location in mapassign_fast32 and mapassign_fast64.
(The use of typedmemmove was a last-minute fix in the 1.9 cycle;
see #21297 and CL 53414.)
This is significantly less inefficient than direct assignment or
calling writebarrierptr directly.
Fortunately, there aren't many cases to consider.
On systems with 32 bit pointers:
* A 32 bit AMEM value either is a single pointer or has no pointers.
* A 64 bit AMEM value may contain a pointer at the beginning,
a pointer at 32 bits, or two pointers.
On systems with 64 bit pointers:
* A 32 bit AMEM value contains no pointers.
* A 64 bit AMEM value either is a single pointer or has no pointers.
All combinations except the 32 bit pointers / 64 bit AMEM value are
cheap and easy to handle, and the problematic case is likely rare.
The most popular map keys appear to be ints and pointers.
So we handle them exhaustively. The sys.PtrSize checks are constant branches
and are eliminated by the compiler.
An alternative fix would be to return a pointer to the key,
and have the calling code do the assignment, at which point the compiler
would have full type information.
Initial tests suggest that the performance difference between these
strategies is negligible, and this fix is considerably simpler,
and has much less impact on binary size.
Fixes #21321
Change-Id: Ib03200e89e2324dd3c76d041131447df66f22bfe
Reviewed-on: https://go-review.googlesource.com/59110
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
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>
|
|
Change-Id: Icfe24d5660666093f3e645f82d30b7687c8077be
Reviewed-on: https://go-review.googlesource.com/58370
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
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>
|
|
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>
|
|
Move the tophash checks after the equality/length checks.
For fast32/fast64, since we've done a full equality check already,
just check whether tophash is empty instead of checking tophash.
This is cheaper and allows us to skip calculating tophash.
These changes are modeled on the changes in CL 57590,
which were polished based on benchmarking.
Benchmarking directly is impeded by #21546.
Change-Id: I0e17163028e34720310d1bf8f95c5ef42d223e00
Reviewed-on: https://go-review.googlesource.com/57611
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
The compiler is now smart enough not to insert a bounds check.
Not only is this simpler, it eliminates a LEAQ from the
generated code.
Change-Id: Ie90cbd11584542edd99edd5456d9b02c406e8063
Reviewed-on: https://go-review.googlesource.com/53892
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
It appears that this was just missed
by accident in the original implementation.
Change-Id: Id87147bcb7a685d624eac7034342a305ad644e7a
Reviewed-on: https://go-review.googlesource.com/53891
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Avelino <t@avelino.xxx>
|
|
We need to make sure that when the key contains a pointer, we use
a write barrier to update the key.
Also mapdelete_* should use typedmemclr.
Fixes #21297
Change-Id: I63dc90bec1cb909c2c6e08676c9ec853d736cdf8
Reviewed-on: https://go-review.googlesource.com/53414
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
Currently we inline array comparisons for arrays with at most 4 elements.
Compare arrays with small size, but more than 4 elements (e. g. [16]byte)
with larger compares. This provides very slightly smaller binaries,
and results in faster code.
ArrayEqual-6 7.41ns ± 0% 3.17ns ± 0% -57.15% (p=0.000 n=10+10)
For go tool:
global text (code) = -559 bytes (-0.014566%)
This also helps mapaccess1_faststr, and maps in general:
MapDelete/Str/1-6 195ns ± 1% 186ns ± 2% -4.47% (p=0.000 n=10+10)
MapDelete/Str/2-6 211ns ± 1% 177ns ± 1% -16.01% (p=0.000 n=10+10)
MapDelete/Str/4-6 225ns ± 1% 183ns ± 1% -18.49% (p=0.000 n=8+10)
MapStringKeysEight_16-6 31.3ns ± 0% 28.6ns ± 0% -8.63% (p=0.000 n=6+9)
MapStringKeysEight_32-6 29.2ns ± 0% 27.6ns ± 0% -5.45% (p=0.000 n=10+10)
MapStringKeysEight_64-6 29.1ns ± 1% 27.5ns ± 0% -5.46% (p=0.000 n=10+10)
MapStringKeysEight_1M-6 29.1ns ± 1% 27.6ns ± 0% -5.49% (p=0.000 n=10+10)
Change-Id: I9ec98e41b233031e0e96c4e13d86a324f628ed4a
Reviewed-on: https://go-review.googlesource.com/40771
Run-TryBot: Ilya Tocar <ilya.tocar@intel.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
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>
|
|
Add benchmarks for map delete with int32/int64/string key
Benchmark results on darwin/amd64
name old time/op new time/op delta
MapDelete/Int32/1-8 151ns ± 8% 99ns ± 3% -34.39% (p=0.008 n=5+5)
MapDelete/Int32/2-8 128ns ± 2% 111ns ±15% -13.40% (p=0.040 n=5+5)
MapDelete/Int32/4-8 128ns ± 5% 114ns ± 2% -10.82% (p=0.008 n=5+5)
MapDelete/Int64/1-8 144ns ± 0% 104ns ± 3% -27.53% (p=0.016 n=4+5)
MapDelete/Int64/2-8 153ns ± 1% 126ns ± 3% -17.17% (p=0.008 n=5+5)
MapDelete/Int64/4-8 178ns ± 3% 136ns ± 2% -23.60% (p=0.008 n=5+5)
MapDelete/Str/1-8 187ns ± 3% 171ns ± 3% -8.54% (p=0.008 n=5+5)
MapDelete/Str/2-8 221ns ± 3% 206ns ± 4% -7.18% (p=0.016 n=5+4)
MapDelete/Str/4-8 256ns ± 5% 232ns ± 2% -9.36% (p=0.016 n=4+5)
name old time/op new time/op delta
BinaryTree17-8 2.78s ± 7% 2.70s ± 1% ~ (p=0.151 n=5+5)
Fannkuch11-8 3.21s ± 2% 3.19s ± 1% ~ (p=0.310 n=5+5)
FmtFprintfEmpty-8 49.1ns ± 3% 50.2ns ± 2% ~ (p=0.095 n=5+5)
FmtFprintfString-8 78.6ns ± 4% 80.2ns ± 5% ~ (p=0.460 n=5+5)
FmtFprintfInt-8 79.7ns ± 1% 81.0ns ± 3% ~ (p=0.103 n=5+5)
FmtFprintfIntInt-8 117ns ± 2% 119ns ± 0% ~ (p=0.079 n=5+4)
FmtFprintfPrefixedInt-8 153ns ± 1% 146ns ± 3% -4.19% (p=0.024 n=5+5)
FmtFprintfFloat-8 239ns ± 1% 237ns ± 1% ~ (p=0.246 n=5+5)
FmtManyArgs-8 506ns ± 2% 509ns ± 2% ~ (p=0.238 n=5+5)
GobDecode-8 7.06ms ± 4% 6.86ms ± 1% ~ (p=0.222 n=5+5)
GobEncode-8 6.01ms ± 5% 5.87ms ± 2% ~ (p=0.222 n=5+5)
Gzip-8 246ms ± 4% 236ms ± 1% -4.12% (p=0.008 n=5+5)
Gunzip-8 37.7ms ± 4% 37.3ms ± 1% ~ (p=0.841 n=5+5)
HTTPClientServer-8 64.9µs ± 1% 64.4µs ± 0% -0.80% (p=0.032 n=5+4)
JSONEncode-8 16.0ms ± 2% 16.2ms ±11% ~ (p=0.548 n=5+5)
JSONDecode-8 53.2ms ± 2% 53.1ms ± 4% ~ (p=1.000 n=5+5)
Mandelbrot200-8 4.33ms ± 2% 4.32ms ± 2% ~ (p=0.841 n=5+5)
GoParse-8 3.24ms ± 2% 3.27ms ± 4% ~ (p=0.690 n=5+5)
RegexpMatchEasy0_32-8 86.2ns ± 1% 85.2ns ± 3% ~ (p=0.286 n=5+5)
RegexpMatchEasy0_1K-8 198ns ± 2% 199ns ± 1% ~ (p=0.310 n=5+5)
RegexpMatchEasy1_32-8 82.6ns ± 2% 81.8ns ± 1% ~ (p=0.294 n=5+5)
RegexpMatchEasy1_1K-8 359ns ± 2% 354ns ± 1% -1.39% (p=0.048 n=5+5)
RegexpMatchMedium_32-8 123ns ± 2% 123ns ± 1% ~ (p=0.905 n=5+5)
RegexpMatchMedium_1K-8 38.2µs ± 2% 38.6µs ± 8% ~ (p=0.690 n=5+5)
RegexpMatchHard_32-8 1.92µs ± 2% 1.91µs ± 5% ~ (p=0.460 n=5+5)
RegexpMatchHard_1K-8 57.6µs ± 1% 57.0µs ± 2% ~ (p=0.310 n=5+5)
Revcomp-8 483ms ± 7% 441ms ± 1% -8.79% (p=0.016 n=5+4)
Template-8 58.0ms ± 1% 58.2ms ± 7% ~ (p=0.310 n=5+5)
TimeParse-8 324ns ± 6% 312ns ± 2% ~ (p=0.087 n=5+5)
TimeFormat-8 330ns ± 1% 329ns ± 1% ~ (p=0.968 n=5+5)
name old speed new speed delta
GobDecode-8 109MB/s ± 4% 112MB/s ± 1% ~ (p=0.222 n=5+5)
GobEncode-8 128MB/s ± 5% 131MB/s ± 2% ~ (p=0.222 n=5+5)
Gzip-8 78.9MB/s ± 4% 82.3MB/s ± 1% +4.25% (p=0.008 n=5+5)
Gunzip-8 514MB/s ± 4% 521MB/s ± 1% ~ (p=0.841 n=5+5)
JSONEncode-8 121MB/s ± 2% 120MB/s ±10% ~ (p=0.548 n=5+5)
JSONDecode-8 36.5MB/s ± 2% 36.6MB/s ± 4% ~ (p=1.000 n=5+5)
GoParse-8 17.9MB/s ± 2% 17.7MB/s ± 4% ~ (p=0.730 n=5+5)
RegexpMatchEasy0_32-8 371MB/s ± 1% 375MB/s ± 3% ~ (p=0.310 n=5+5)
RegexpMatchEasy0_1K-8 5.15GB/s ± 1% 5.13GB/s ± 1% ~ (p=0.548 n=5+5)
RegexpMatchEasy1_32-8 387MB/s ± 2% 391MB/s ± 1% ~ (p=0.310 n=5+5)
RegexpMatchEasy1_1K-8 2.85GB/s ± 2% 2.89GB/s ± 1% ~ (p=0.056 n=5+5)
RegexpMatchMedium_32-8 8.07MB/s ± 2% 8.06MB/s ± 1% ~ (p=0.730 n=5+5)
RegexpMatchMedium_1K-8 26.8MB/s ± 2% 26.6MB/s ± 7% ~ (p=0.690 n=5+5)
RegexpMatchHard_32-8 16.7MB/s ± 2% 16.7MB/s ± 5% ~ (p=0.421 n=5+5)
RegexpMatchHard_1K-8 17.8MB/s ± 1% 18.0MB/s ± 2% ~ (p=0.310 n=5+5)
Revcomp-8 527MB/s ± 6% 577MB/s ± 1% +9.44% (p=0.016 n=5+4)
Template-8 33.5MB/s ± 1% 33.4MB/s ± 7% ~ (p=0.310 n=5+5)
Updates #19495
Change-Id: Ib9ece1690813d9b4788455db43d30891e2138df5
Reviewed-on: https://go-review.googlesource.com/38172
Reviewed-by: Hugues Bruant <hugues.bruant@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Add benchmarks for map assignment with int32/int64/string key
Benchmark results on darwin/amd64
name old time/op new time/op delta
MapAssignInt32_255-8 24.7ns ± 3% 17.4ns ± 2% -29.75% (p=0.000 n=10+10)
MapAssignInt32_64k-8 45.5ns ± 4% 37.6ns ± 4% -17.18% (p=0.000 n=10+10)
MapAssignInt64_255-8 26.0ns ± 3% 17.9ns ± 4% -31.03% (p=0.000 n=10+10)
MapAssignInt64_64k-8 46.9ns ± 5% 38.7ns ± 2% -17.53% (p=0.000 n=9+10)
MapAssignStr_255-8 47.8ns ± 3% 24.8ns ± 4% -48.01% (p=0.000 n=10+10)
MapAssignStr_64k-8 83.0ns ± 3% 51.9ns ± 3% -37.45% (p=0.000 n=10+9)
name old time/op new time/op delta
BinaryTree17-8 3.11s ±19% 2.78s ± 3% ~ (p=0.095 n=5+5)
Fannkuch11-8 3.26s ± 1% 3.21s ± 2% ~ (p=0.056 n=5+5)
FmtFprintfEmpty-8 50.3ns ± 1% 50.8ns ± 2% ~ (p=0.246 n=5+5)
FmtFprintfString-8 82.7ns ± 4% 80.1ns ± 5% ~ (p=0.238 n=5+5)
FmtFprintfInt-8 82.6ns ± 2% 81.9ns ± 3% ~ (p=0.508 n=5+5)
FmtFprintfIntInt-8 124ns ± 4% 121ns ± 3% ~ (p=0.111 n=5+5)
FmtFprintfPrefixedInt-8 158ns ± 6% 160ns ± 2% ~ (p=0.341 n=5+5)
FmtFprintfFloat-8 249ns ± 2% 245ns ± 2% ~ (p=0.095 n=5+5)
FmtManyArgs-8 513ns ± 2% 519ns ± 3% ~ (p=0.151 n=5+5)
GobDecode-8 7.48ms ±12% 7.11ms ± 2% ~ (p=0.222 n=5+5)
GobEncode-8 6.25ms ± 1% 6.03ms ± 2% -3.56% (p=0.008 n=5+5)
Gzip-8 252ms ± 4% 252ms ± 4% ~ (p=1.000 n=5+5)
Gunzip-8 38.4ms ± 3% 38.6ms ± 2% ~ (p=0.690 n=5+5)
HTTPClientServer-8 76.9µs ±41% 66.4µs ± 6% ~ (p=0.310 n=5+5)
JSONEncode-8 16.5ms ± 3% 16.7ms ± 3% ~ (p=0.421 n=5+5)
JSONDecode-8 54.6ms ± 1% 54.3ms ± 2% ~ (p=0.548 n=5+5)
Mandelbrot200-8 4.45ms ± 3% 4.47ms ± 1% ~ (p=0.841 n=5+5)
GoParse-8 3.43ms ± 1% 3.32ms ± 2% -3.28% (p=0.008 n=5+5)
RegexpMatchEasy0_32-8 88.2ns ± 3% 89.4ns ± 2% ~ (p=0.333 n=5+5)
RegexpMatchEasy0_1K-8 205ns ± 1% 206ns ± 1% ~ (p=0.905 n=5+5)
RegexpMatchEasy1_32-8 85.1ns ± 1% 85.5ns ± 5% ~ (p=0.690 n=5+5)
RegexpMatchEasy1_1K-8 365ns ± 1% 371ns ± 9% ~ (p=1.000 n=5+5)
RegexpMatchMedium_32-8 129ns ± 2% 128ns ± 3% ~ (p=0.730 n=5+5)
RegexpMatchMedium_1K-8 39.8µs ± 0% 39.7µs ± 4% ~ (p=0.730 n=4+5)
RegexpMatchHard_32-8 1.99µs ± 3% 2.05µs ±16% ~ (p=0.794 n=5+5)
RegexpMatchHard_1K-8 59.3µs ± 1% 60.3µs ± 7% ~ (p=1.000 n=5+5)
Revcomp-8 1.36s ±63% 0.52s ± 5% ~ (p=0.095 n=5+5)
Template-8 62.6ms ±14% 60.5ms ± 5% ~ (p=0.690 n=5+5)
TimeParse-8 330ns ± 2% 324ns ± 2% ~ (p=0.087 n=5+5)
TimeFormat-8 350ns ± 3% 340ns ± 1% -2.86% (p=0.008 n=5+5)
name old speed new speed delta
GobDecode-8 103MB/s ±11% 108MB/s ± 2% ~ (p=0.222 n=5+5)
GobEncode-8 123MB/s ± 1% 127MB/s ± 2% +3.71% (p=0.008 n=5+5)
Gzip-8 77.1MB/s ± 4% 76.9MB/s ± 3% ~ (p=1.000 n=5+5)
Gunzip-8 505MB/s ± 3% 503MB/s ± 2% ~ (p=0.690 n=5+5)
JSONEncode-8 118MB/s ± 3% 116MB/s ± 3% ~ (p=0.421 n=5+5)
JSONDecode-8 35.5MB/s ± 1% 35.8MB/s ± 2% ~ (p=0.397 n=5+5)
GoParse-8 16.9MB/s ± 1% 17.4MB/s ± 2% +3.45% (p=0.008 n=5+5)
RegexpMatchEasy0_32-8 363MB/s ± 3% 358MB/s ± 2% ~ (p=0.421 n=5+5)
RegexpMatchEasy0_1K-8 4.98GB/s ± 1% 4.97GB/s ± 1% ~ (p=0.548 n=5+5)
RegexpMatchEasy1_32-8 376MB/s ± 1% 375MB/s ± 5% ~ (p=0.690 n=5+5)
RegexpMatchEasy1_1K-8 2.80GB/s ± 1% 2.76GB/s ± 9% ~ (p=0.841 n=5+5)
RegexpMatchMedium_32-8 7.73MB/s ± 1% 7.76MB/s ± 3% ~ (p=0.730 n=5+5)
RegexpMatchMedium_1K-8 25.8MB/s ± 0% 25.8MB/s ± 4% ~ (p=0.651 n=4+5)
RegexpMatchHard_32-8 16.1MB/s ± 3% 15.7MB/s ±14% ~ (p=0.794 n=5+5)
RegexpMatchHard_1K-8 17.3MB/s ± 1% 17.0MB/s ± 7% ~ (p=0.984 n=5+5)
Revcomp-8 273MB/s ±83% 488MB/s ± 5% ~ (p=0.095 n=5+5)
Template-8 31.1MB/s ±13% 32.1MB/s ± 5% ~ (p=0.690 n=5+5)
Updates #19495
Change-Id: I116e9a2a4594769318b22d736464de8a98499909
Reviewed-on: https://go-review.googlesource.com/38091
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
Consider repeatedly adding many items to a map
and then deleting them all, as in #16070. The map
itself doesn't need to grow above the high water
mark of number of items. However, due to random
collisions, the map can accumulate overflow
buckets.
Prior to this CL, those overflow buckets were
never removed, which led to a slow memory leak.
The problem with removing overflow buckets is
iterators. The obvious approach is to repack
keys and values and eliminate unused overflow
buckets. However, keys, values, and overflow
buckets cannot be manipulated without disrupting
iterators.
This CL takes a different approach, which is to
reuse the existing map growth mechanism,
which is well established, well tested, and
safe in the presence of iterators.
When a map has accumulated enough overflow buckets
we trigger map growth, but grow into a map of the
same size as before. The old overflow buckets will
be left behind for garbage collection.
For the code in #16070, instead of climbing
(very slowly) forever, memory usage now cycles
between 264mb and 483mb every 15 minutes or so.
To avoid increasing the size of maps,
the overflow bucket counter is only 16 bits.
For large maps, the counter is incremented
stochastically.
Fixes #16070
Change-Id: If551d77613ec6836907efca58bda3deee304297e
Reviewed-on: https://go-review.googlesource.com/25049
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
mapaccess{1,2} returns a pointer to the value. When the key
is not in the map, it returns a pointer to zeroed memory.
Currently, for large map values we have a complicated scheme which
dynamically allocates zeroed memory for this purpose. It is ugly
code and requires an atomic.Load in a bunch of places we'd rather
not have it.
Switch to a scheme where callsites of mapaccess{1,2} which expect
large return values pass in a pointer to zeroed memory that
mapaccess can return if the key is not found. This avoids the
atomic.Load on all map accesses with a few extra instructions only
for the large value acccesses, plus a bit of bss space.
There was a time (1.4 & 1.5?) where we did something like this but
all the tricks to make the right size zero value were done by the
linker. That scheme broke in the presence of dyamic linking.
The scheme in this CL works even when dynamic linking.
Fixes #12337
Change-Id: Ic2d0319944af33bbb59785938d9ab80958d1b4b1
Reviewed-on: https://go-review.googlesource.com/22221
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Michael Hudson-Doyle <michael.hudson@canonical.com>
|
|
The tree's pretty inconsistent about single space vs double space
after a period in documentation. Make it consistently a single space,
per earlier decisions. This means contributors won't be confused by
misleading precedence.
This CL doesn't use go/doc to parse. It only addresses // comments.
It was generated with:
$ perl -i -npe 's,^(\s*// .+[a-z]\.) +([A-Z]),$1 $2,' $(git grep -l -E '^\s*//(.+\.) +([A-Z])')
$ go test go/doc -update
Change-Id: Iccdb99c37c797ef1f804a94b22ba5ee4b500c4f7
Reviewed-on: https://go-review.googlesource.com/20022
Reviewed-by: Rob Pike <r@golang.org>
Reviewed-by: Dave Day <djd@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
They do the same thing, except memequal also has the short-circuit
check if the two pointers are equal.
A) We might as well always do the short-circuit check, it is only 2 instructions.
B) The extra function call (memequal->memeq) is expensive.
benchmark old ns/op new ns/op delta
BenchmarkArrayEqual-8 8.56 5.31 -37.97%
No noticeable affect on the former memeq user (maps).
Fixes #14302
Change-Id: I85d1ada59ed11e64dd6c54667f79d32cc5f81948
Reviewed-on: https://go-review.googlesource.com/19843
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
If reports like #13062 are really concurrent misuse of maps,
we can detect that, at least some of the time, with a cheap check.
There is an extra pair of memory writes for writing to a map,
but to the same cache line as h.count, which is often being modified anyway,
and there is an extra memory read for reading from a map,
but to the same cache line as h.count, which is always being read anyway.
So the check should be basically invisible and may help reduce the
number of "mysterious runtime crash due to map misuse" reports.
Change-Id: I0e71b0d92eaa3b7bef48bf41b0f5ab790092487e
Reviewed-on: https://go-review.googlesource.com/17501
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
|
|
runtime/internal/sys will hold system-, architecture- and config-
specific constants.
Updates #11647
Change-Id: I6db29c312556087a42e8d2bdd9af40d157c56b54
Reviewed-on: https://go-review.googlesource.com/16817
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
This change breaks out most of the atomics functions in the runtime
into package runtime/internal/atomic. It adds some basic support
in the toolchain for runtime packages, and also modifies linux/arm
atomics to remove the dependency on the runtime's mutex. The mutexes
have been replaced with spinlocks.
all trybots are happy!
In addition to the trybots, I've tested on the darwin/arm64 builder,
on the darwin/arm builder, and on a ppc64le machine.
Change-Id: I6698c8e3cf3834f55ce5824059f44d00dc8e3c2f
Reviewed-on: https://go-review.googlesource.com/14204
Run-TryBot: Michael Matloob <matloob@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
Instead of open-coding conversions from *string to unsafe.Pointer then
to *stringStruct, add a helper function to add some type safety.
Bonus: This caught two **string values being converted to
*stringStruct in heapdump.go.
While here, get rid of the redundant _string type, but add in a
stringStructDWARF type used for generating DWARF debug info.
Change-Id: I8882f8cca66ac45190270f82019a5d85db023bd2
Reviewed-on: https://go-review.googlesource.com/16131
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
|
|
Previously t.zero always pointed to runtime.zerovalue. Change the hashmap code
to always return a runtime pointer directly, and change that pointer to point
to a larger buffer if one is needed.
(It might be better to only copy from the pointer returned by the mapaccess
functions when the value type is small enough and have the compiler insert
explicit zeroing for larger value types, but I tried and failed to do this).
This removes all uses of the zero field of the type data; the field itself can
be removed in a separate change.
Fixes #11491
Change-Id: I5b81752ff4067d74a5a281c41e88f151bae0171e
Reviewed-on: https://go-review.googlesource.com/13784
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
The equal algorithm used to take the size
equal(p, q *T, size uintptr) bool
With this change, it does not
equal(p, q *T) bool
Similarly for the hash algorithm.
The size is rarely used, as most equal functions know the size
of the thing they are comparing. For instance f32equal already
knows its inputs are 4 bytes in size.
For cases where the size is not known, we allocate a closure
(one for each size needed) that points to an assembly stub that
reads the size out of the closure and calls generic code that
has a size argument.
Reduces the size of the go binary by 0.07%. Performance impact
is not measurable.
Change-Id: I6e00adf3dde7ad2974adbcff0ee91e86d2194fec
Reviewed-on: https://go-review.googlesource.com/2392
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
The goalg function was a holdover from when we had algorithm
tables in both C and Go. It is no longer needed.
Change-Id: Ia0c1af35bef3497a899f22084a1a7b42daae72a0
Reviewed-on: https://go-review.googlesource.com/2099
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
Pointers to zero-sized values may end up pointing to the next
object in memory, and possibly off the end of a span. This
can cause memory leaks and/or confuse the garbage collector.
By putting the overflow pointer at the end of the bucket, we
make sure that pointers to any zero-sized keys or values don't
accidentally point to the next object in memory.
fixes #9384
Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73
Reviewed-on: https://go-review.googlesource.com/1869
Reviewed-by: Russ Cox <rsc@golang.org>
|
|
Preparation was in CL 134570043.
This CL contains only the effect of 'hg mv src/pkg/* src'.
For more about the move, see golang.org/s/go14nopkg.
|
