aboutsummaryrefslogtreecommitdiff
path: root/src/runtime/alg.go
AgeCommit message (Collapse)Author
2017-08-11runtime, cmd/compile: add intrinsic getclosureptrCholerae Hu
Intrinsic enabled on all architectures, runtime asm implementation removed on all architectures. Fixes #21258 Change-Id: I2cb86d460b497c2f287a5b3df5c37fdb231c23a7 Reviewed-on: https://go-review.googlesource.com/53411 Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: David Chase <drchase@google.com>
2017-05-01runtime: refactor cpu feature detection for 386 & amd64Martin Möhrmann
Changes all cpu features to be detected and stored in bools in rt0_go. Updates: #15403 Change-Id: I5a9961cdec789b331d09c44d86beb53833d5dc3e Reviewed-on: https://go-review.googlesource.com/41950 Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Ilya Tocar <ilya.tocar@intel.com> Reviewed-by: Keith Randall <khr@golang.org>
2017-03-24cmd/compile: simplify efaceeq and ifaceeqKeith Randall
Clean up code that does interface equality. Avoid doing checks in efaceeq/ifaceeq that we already did before calling those routines. No noticeable performance changes for existing benchmarks. name old time/op new time/op delta EfaceCmpDiff-8 604ns ± 1% 553ns ± 1% -8.41% (p=0.000 n=9+10) Fixes #18618 Change-Id: I3bd46db82b96494873045bc3300c56400bc582eb Reviewed-on: https://go-review.googlesource.com/38606 Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: David Chase <drchase@google.com>
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-08-30runtime: rename fastrand1 to fastrandJosh Bleecher Snyder
Change-Id: I37706ff0a3486827c5b072c95ad890ea87ede847 Reviewed-on: https://go-review.googlesource.com/28210 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
2016-08-04runtime: initialize hash algs before typemapDavid Crawshaw
When compiling with -buildmode=shared, a map[int32]*_type is created for each extra module mapping duplicate types back to a canonical object. This is done in the function typelinksinit, which is called before the init function that sets up the hash functions for the map implementation. The result is typemap becomes unusable after runtime initialization. The fix in this CL is to move algorithm init before typelinksinit in the runtime setup process. (For 1.8, we may want to turn typemap into a sorted slice of types and use binary search.) Manually tested on GOOS=linux with: GOHOSTARCH=386 GOARCH=386 ./make.bash && \ go install -buildmode=shared std && \ cd ../test && \ go run run.go -linkshared Fixes #16590 Change-Id: Idc08c50cc70d20028276fbf564509d2cd5405210 Reviewed-on: https://go-review.googlesource.com/25469 Run-TryBot: David Crawshaw <crawshaw@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2016-04-22cmd/compile, etc: use nameOff for rtype stringDavid Crawshaw
linux/amd64: cmd/go: -8KB (basically nothing) linux/amd64 PIE: cmd/go: -191KB (1.6%) jujud: -1.5MB (1.9%) Updates #6853 Fixes #15064 Change-Id: I0adbb95685e28be92e8548741df0e11daa0a9b5f Reviewed-on: https://go-review.googlesource.com/21777 Reviewed-by: Ian Lance Taylor <iant@golang.org>
2016-03-02all: single space after period.Brad Fitzpatrick
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>
2016-02-24cmd/compile: embed type string header in rtypeDavid Crawshaw
Reduces binary size of cmd/go by 1%. For #6853. Change-Id: I6f2992a4dd3699db1b532ab08683e82741b9c2e4 Reviewed-on: https://go-review.googlesource.com/19692 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: David Crawshaw <crawshaw@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-02-23runtime: unify memeq and memequalKeith Randall
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>
2016-02-21cmd/compile, runtime: eliminate unnecessary algorithm typesMatthew Dempsky
There's no need for 8 different ways to represent that a type is non-comparable. While here, move AMEM out of the runtime-known algorithm values since it's not needed at run-time, and get rid of the unused AUNK constant. Change-Id: Ie23972b692c6f27fc5f1a908561b3e26ef5a50e9 Reviewed-on: https://go-review.googlesource.com/19779 Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: David Crawshaw <crawshaw@golang.org>
2015-11-12runtime: break out system-specific constants into package sysMichael Matloob
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>
2015-10-21runtime: make iface/eface handling more type safeMatthew Dempsky
Change compiler-invoked interface functions to directly take iface/eface parameters instead of fInterface/interface{} to avoid needing to always convert. For the handful of functions that legitimately need to take an interface{} parameter, add efaceOf to type-safely convert *interface{} to *eface. Change-Id: I8928761a12fd3c771394f36adf93d3006a9fcf39 Reviewed-on: https://go-review.googlesource.com/16166 Run-TryBot: Matthew Dempsky <mdempsky@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org>
2015-10-08runtime: make aeshash more DOS-proofKeith Randall
Improve the aeshash implementation to make it harder to engineer collisions. 1) Scramble the seed before xoring with the input string. This makes it harder to cancel known portions of the seed (like the size) because it mixes the per-table seed into those other parts. 2) Use table-dependent seeds for all stripes when hashing >16 byte strings. For small strings this change uses 4 aesenc ops instead of 3, so it is somewhat slower. The first two can run in parallel, though, so it isn't 33% slower. benchmark old ns/op new ns/op delta BenchmarkHash64-12 10.2 11.2 +9.80% BenchmarkHash16-12 5.71 6.13 +7.36% BenchmarkHash5-12 6.64 7.01 +5.57% BenchmarkHashBytesSpeed-12 30.3 31.9 +5.28% BenchmarkHash65536-12 2785 2882 +3.48% BenchmarkHash1024-12 53.6 55.4 +3.36% BenchmarkHashStringArraySpeed-12 54.9 56.5 +2.91% BenchmarkHashStringSpeed-12 18.7 19.2 +2.67% BenchmarkHashInt32Speed-12 14.8 15.1 +2.03% BenchmarkHashInt64Speed-12 14.5 14.5 +0.00% Change-Id: I59ea124b5cb92b1c7e8584008257347f9049996c Reviewed-on: https://go-review.googlesource.com/14124 Reviewed-by: jcd . <jcd@golang.org> Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2015-04-21reflect: implement ArrayOfSebastien Binet
This change exposes reflect.ArrayOf to create new reflect.Type array types at runtime, when given a reflect.Type element. - reflect: implement ArrayOf - reflect: tests for ArrayOf - runtime: document that typeAlg is used by reflect and must be kept in synchronized Fixes #5996. Change-Id: I5d07213364ca915c25612deea390507c19461758 Reviewed-on: https://go-review.googlesource.com/4111 Reviewed-by: Keith Randall <khr@golang.org>
2015-04-15runtime: merge slice and sliceStructMichael Hudson-Doyle
By removing type slice, renaming type sliceStruct to type slice and whacking until it compiles. Has a pleasing net reduction of conversions. Fixes #10188 Change-Id: I77202b8df637185b632fd7875a1fdd8d52c7a83c Reviewed-on: https://go-review.googlesource.com/8770 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2015-01-07runtime: remove size argument from hash and equal algorithmsKeith Randall
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>
2015-01-07runtime: use some startup randomness in the fallback hashesKeith Randall
Fold in some startup randomness to make the hash vary across different runs. This helps prevent attackers from choosing keys that all map to the same bucket. Also, reorganize the hash a bit. Move the *m1 multiply to after the xor of the current hash and the message. For hash quality it doesn't really matter, but for DDOS resistance it helps a lot (any processing done to the message before it is merged with the random seed is useless, as it is easily inverted by an attacker). Update #9365 Change-Id: Ib19968168e1bbc541d1d28be2701bb83e53f1e24 Reviewed-on: https://go-review.googlesource.com/2344 Reviewed-by: Ian Lance Taylor <iant@golang.org>
2014-12-28runtime: get rid of goalg, no longer neededKeith Randall
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>
2014-12-22runtime: a better fallback hashKeith Randall
For arm and powerpc, as well as x86 without aes instructions. Contains a mixture of ideas from cityhash and xxhash. Compared to our old fallback on ARM, it's ~no slower on small objects and up to ~50% faster on large objects. More importantly, it is a much better hash function and thus has less chance of bad behavior. Fixes #8737 benchmark old ns/op new ns/op delta BenchmarkHash5 173 181 +4.62% BenchmarkHash16 252 212 -15.87% BenchmarkHash64 575 419 -27.13% BenchmarkHash1024 7173 3995 -44.31% BenchmarkHash65536 516940 313173 -39.42% BenchmarkHashStringSpeed 300 279 -7.00% BenchmarkHashBytesSpeed 478 424 -11.30% BenchmarkHashInt32Speed 217 207 -4.61% BenchmarkHashInt64Speed 262 231 -11.83% BenchmarkHashStringArraySpeed 609 631 +3.61% Change-Id: I0a9335028f32b10ad484966e3019987973afd3eb Reviewed-on: https://go-review.googlesource.com/1360 Reviewed-by: Russ Cox <rsc@golang.org>
2014-12-11runtime: faster aeshash implementationKeith Randall
The aesenc instruction has high latency. For hashing large objects, hash several streams in parallel. benchmark old ns/op new ns/op delta BenchmarkHash5 7.02 7.45 +6.13% BenchmarkHash16 6.53 6.94 +6.28% BenchmarkHash32 8.38 8.26 -1.43% BenchmarkHash64 12.6 12.0 -4.76% BenchmarkHash1024 247 62.9 -74.53% BenchmarkHash65536 17335 2966 -82.89% BenchmarkHashInt32Speed 14.7 14.9 +1.36% BenchmarkHashInt64Speed 14.6 14.9 +2.05% BenchmarkHashBytesSpeed 35.4 28.6 -19.21% BenchmarkHashStringSpeed 22.0 20.4 -7.27% BenchmarkHashStringArraySpeed 65.8 56.3 -14.44% Change-Id: Ia8ba03063acc64a9066b8ab2d79f2c9aaac1770f Reviewed-on: https://go-review.googlesource.com/1330 Reviewed-by: Russ Cox <rsc@golang.org>
2014-12-10runtime: clean up & go-ify the hash function seederKeith Randall
Change-Id: I0e95f8a5962c547da20e19a356ae1cf8375c9107 Reviewed-on: https://go-review.googlesource.com/1270 Reviewed-by: Russ Cox <rsc@golang.org>
2014-11-11[dev.cc] runtime: convert operating system support code from C to GoRuss Cox
The conversion was done with an automated tool and then modified only as necessary to make it compile and run. [This CL is part of the removal of C code from package runtime. See golang.org/s/dev.cc for an overview.] LGTM=r R=r CC=austin, dvyukov, golang-codereviews, iant, khr https://golang.org/cl/174830044
2014-09-08build: move package sources from src/pkg to srcRuss Cox
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.
generated by cgit v1.3 (git 2.53.0) at 2026-04-15 10:48:48 +0000