• Rick Hudson's avatar
    [dev.garbage] runtime: logic that uses count trailing zero (ctz) · 44fe90d0
    Rick Hudson authored
    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/20169Reviewed-by: 's avatarKeith Randall <khr@golang.org>
    Reviewed-by: 's avatarAustin Clements <austin@google.com>
    44fe90d0
mbitmap.go 64.7 KB