]> Cypherpunks repositories - gostls13.git/commit
[dev.garbage] runtime: logic that uses count trailing zero (ctz)
authorRick Hudson <rlh@golang.org>
Wed, 17 Feb 2016 16:27:52 +0000 (11:27 -0500)
committerRick Hudson <rlh@golang.org>
Wed, 27 Apr 2016 21:54:52 +0000 (21:54 +0000)
commit44fe90d0b393c961e3fb1b4c37e93ce268da46bc
tree735386d60a503ae4b876df365dfae3d344e7d5d4
parente4ac2d4acc8cb44df2107e3fa1067755feaaa005
[dev.garbage] runtime: logic that uses count trailing zero (ctz)

Most (all?) processors that Go supports supply a hardware
instruction that takes a byte and returns the number
of zeros trailing the first 1 encountered, or 8
if no ones are found. This is the index within the
byte of the first 1 encountered. CTZ should improve the
performance of the nextFreeIndex function.

Since nextFreeIndex wants the next unmarked (0) bit
a bit-wise complement is needed before calling ctz.
Furthermore unmarked bits associated with previously
allocated objects need to be ignored. Instead of writing
a 1 as we allocate the code masks all bits less than the
freeindex after loading the byte.

While this CL does not actual execute a CTZ instruction
it supplies a ctz function with the appropiate signature
along with the logic to execute it.

Change-Id: I5c55ce0ed48ca22c21c4dd9f969b0819b4eadaa7
Reviewed-on: https://go-review.googlesource.com/20169
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
src/runtime/mbitmap.go