1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
package scala.collection
import org.openjdk.jmh.annotations._
import org.openjdk.jmh.infra._
import org.openjdk.jmh.runner.IterationType
import benchmark._
import java.util.concurrent.TimeUnit
@BenchmarkMode(Array(Mode.AverageTime))
@Fork(2)
@Threads(1)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
class BitManipulationBenchmark {
val powersOfTwo = Array(1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824)
//////////////////////////////////////////////
@Benchmark def withIntegerBitCount(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = withIntegerBitCount(v)
// assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)")
bh.consume(leadingZeros)
}
}
private def withIntegerBitCount(v: Int) = Integer.SIZE - Integer.bitCount(v - 1)
//////////////////////////////////////////////
@Benchmark def withIntegerNumberOfLeadingZeros(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = withIntegerNumberOfLeadingZeros(v)
// assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)")
bh.consume(leadingZeros)
}
}
private def withIntegerNumberOfLeadingZeros(v: Int) = Integer.numberOfLeadingZeros(v - 1)
//////////////////////////////////////////////
@Benchmark def withLoop(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = withLoop(v)
bh.consume(leadingZeros)
}
}
private def withLoop(v: Int): Int = {
var r = Integer.SIZE
var copy = v >> 1
while (copy != 0) {
r -= 1
copy = copy >> 1
}
r
}
//////////////////////////////////////////////
@Benchmark def withMatch(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = withMatch(v)
// assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)")
bh.consume(leadingZeros)
}
}
private def withMatch(i: Int) = i match {
case 1 => 32
case 2 => 31
case 4 => 30
case 8 => 29
case 16 => 28
case 32 => 27
case 64 => 26
case 128 => 25
case 256 => 24
case 512 => 23
case 1024 => 22
case 2048 => 21
case 4096 => 20
case 8192 => 19
case 16384 => 18
case 32768 => 17
case 65536 => 16
case 131072 => 15
case 262144 => 14
case 524288 => 13
case 1048576 => 12
case 2097152 => 11
case 4194304 => 10
case 8388608 => 9
case 16777216 => 8
case 33554432 => 7
case 67108864 => 6
case 134217728 => 5
case 268435456 => 4
case 536870912 => 3
case 1073741824 => 2
}
//////////////////////////////////////////////
@Benchmark def with2DeBruijn(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = with2DeBruijn(v)
// assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)")
bh.consume(leadingZeros)
}
}
// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
private val multiplyDeBruijnBitPosition2 = Array(32, 31, 4, 30, 3, 18, 8, 29, 2, 10, 12, 17, 7, 15, 28, 24, 1, 5, 19, 9, 11, 13, 16, 25, 6, 20, 14, 26, 21, 27, 22, 23)
private def with2DeBruijn(v: Int) = multiplyDeBruijnBitPosition2((v * 0x077CB531) >>> 27)
//////////////////////////////////////////////
@Benchmark def withBinSearch(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = withBinSearch(v)
// assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)")
bh.consume(leadingZeros)
}
}
private def withBinSearch(v: Int) =
if (v < 65536) if (v < 256) if (v < 16) if (v < 4) if (v == 1) 32 else 31
else if (v == 4) 30 else 29
else if (v < 64) if (v == 16) 28 else 27
else if (v == 64) 26 else 25
else if (v < 4096) if (v < 1024) if (v == 256) 24 else 23
else if (v == 1024) 22 else 21
else if (v < 16384) if (v == 4096) 20 else 19
else if (v == 16384) 18 else 17
else if (v < 16777216) if (v < 1048576) if (v < 262144) if (v == 65536) 16 else 15
else if (v == 262144) 14 else 13
else if (v < 4194304) if (v == 1048576) 12 else 11
else if (v == 4194304) 10 else 9
else if (v < 268435456) if (v < 67108864) if (v == 16777216) 8 else 7
else if (v == 67108864) 6 else 5
else if (v < 1073741824) if (v == 268435456) 4 else 3
else if (v == 1073741824) 2 else 1
//////////////////////////////////////////////
@Benchmark def withSumBinSearch(bh: Blackhole) {
for (v <- powersOfTwo) {
val leadingZeros = withSumBinSearch(v)
// assert(leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)")
bh.consume(leadingZeros)
}
}
private def withSumBinSearch(v: Int): Int = {
var exponent = Integer.SIZE
var remaining = v
if (remaining >= 65536) { remaining >>>= 16; exponent = 16 }
if (remaining >= 256) { remaining >>>= 8; exponent -= 8 }
if (remaining >= 16) { remaining >>>= 4; exponent -= 4 }
if (remaining >= 4) { remaining >>>= 2; exponent -= 2 }
if (remaining >= 2) exponent - 1 else exponent
}
}
|
