ref: 8a92415ad8220c1f651b0ed6338efb072e848d5c
parent: 2b1c13ce2d20ce2b4e68e1daf08a1679d94fe397
author: Ori Bernstein <ori@eigenstate.org>
date: Mon Jan 9 20:53:58 EST 2017
Use debruijn multiplication to find bit position. Should be faster than loopy branchy testing.
--- a/lib/std/bytealloc.myr
+++ b/lib/std/bytealloc.myr
@@ -292,17 +292,22 @@
Finds the correct bucket index to allocate from
for allocations of size 'sz'
*/
+const bitpos : byte[32] = [
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
+]
const bktnum = {sz- var bktsz
+ var n, v
- bktsz = Align
- for var i = 0; bktsz <= Bktmax; i++
- if bktsz >= sz
- -> i
- ;;
- bktsz *= 2
- ;;
- die("Size does not match any buckets")+ v = (sz >> 3 : uint32)
+ v |= v >> 1
+ v |= v >> 2
+ v |= v >> 4
+ v |= v >> 8
+ v |= v >> 16
+
+ n = bitpos[((v * 0x07c4acdd) & 0xffff_ffffui) >> 27]
+ -> (n : size)
}
/*