IntegerBenchmark.java revision 5a7833b406bb2716b057d3ed923f22f1f86b2a20 
1/*
2 * Copyright (C) 2011 Google Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package benchmarks.regression;
18
19import com.google.caliper.Param;
20import com.google.caliper.SimpleBenchmark;
21
22public class IntegerBenchmark extends SimpleBenchmark {
23    public int timeLongSignumBranch(int reps) {
24        int t = 0;
25        for (int i = 0; i < reps; ++i) {
26            t += signum1(-i);
27            t += signum1(0);
28            t += signum1(i);
29        }
30        return t;
31    }
32
33    public int timeLongSignumBranchFree(int reps) {
34        int t = 0;
35        for (int i = 0; i < reps; ++i) {
36            t += signum2(-i);
37            t += signum2(0);
38            t += signum2(i);
39        }
40        return t;
41    }
42
43    private static int signum1(long v) {
44        return v < 0 ? -1 : (v == 0 ? 0 : 1);
45    }
46
47    private static int signum2(long v) {
48        return ((int)(v >> 63)) | (int) (-v >>> 63); // Hacker's delight 2-7
49    }
50
51    public int timeLongBitCount_BitSet(int reps) {
52        int t = 0;
53        for (int i = 0; i < reps; ++i) {
54            t += pop((long) i);
55        }
56        return t;
57    }
58
59    private static int pop(long l) {
60        int count = popX(l & 0xffffffffL);
61        count += popX(l >>> 32);
62        return count;
63    }
64
65    private static int popX(long x) {
66        // BEGIN android-note
67        // delegate to Integer.bitCount(i); consider using native code
68        // END android-note
69        x = x - ((x >>> 1) & 0x55555555);
70        x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
71        x = (x + (x >>> 4)) & 0x0f0f0f0f;
72        x = x + (x >>> 8);
73        x = x + (x >>> 16);
74        return (int) x & 0x0000003f;
75    }
76
77    public int timeLongBitCount_2Int(int reps) {
78        int t = 0;
79        for (int i = 0; i < reps; ++i) {
80            t += pop2((long) i);
81        }
82        return t;
83    }
84
85    private static int pop2(long l) {
86        int count = Integer.bitCount((int) (l & 0xffffffffL));
87        count += Integer.bitCount((int) (l >>> 32));
88        return count;
89    }
90
91    public int timeLongBitCount_Long(int reps) {
92        int t = 0;
93        for (int i = 0; i < reps; ++i) {
94            t += Long.bitCount((long) i);
95        }
96        return t;
97    }
98
99    /**
100     * Table for Seal's algorithm for Number of Trailing Zeros. Hacker's Delight
101     * online, Figure 5-18 (http://www.hackersdelight.org/revisions.pdf)
102     * The entries whose value is -1 are never referenced.
103     */
104    private static final byte[] NTZ_TABLE = {
105        32,  0,  1, 12,  2,  6, -1, 13,   3, -1,  7, -1, -1, -1, -1, 14,
106        10,  4, -1, -1,  8, -1, -1, 25,  -1, -1, -1, -1, -1, 21, 27, 15,
107        31, 11,  5, -1, -1, -1, -1, -1,   9, -1, -1, 24, -1, -1, 20, 26,
108        30, -1, -1, -1, -1, 23, -1, 19,  29, -1, 22, 18, 28, 17, 16, -1
109    };
110
111    private static int numberOfTrailingZerosHD(int i) {
112        // Seal's algorithm - Hacker's Delight 5-18
113        i &= -i;
114        i = (i <<  4) + i;    // x *= 17
115        i = (i <<  6) + i;    // x *= 65
116        i = (i << 16) - i;    // x *= 65535
117        return NTZ_TABLE[i >>> 26];
118    }
119
120    private static int numberOfTrailingZerosOL(int i) {
121        return NTZ_TABLE[((i & -i) * 0x0450FBAF) >>> 26];
122    }
123
124    public int timeNumberOfTrailingZerosHD(int reps) {
125        int t = 0;
126        for (int i = 0; i < reps; ++i) {
127            t += numberOfTrailingZerosHD(i);
128        }
129        return t;
130    }
131
132    public int timeNumberOfTrailingZerosOL(int reps) {
133        int t = 0;
134        for (int i = 0; i < reps; ++i) {
135            t += numberOfTrailingZerosOL(i);
136        }
137        return t;
138    }
139}
140