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 
17 package benchmarks.regression;
18 
19 public class IntegerBenchmark {
timeLongSignumBranch(int reps)20     public int timeLongSignumBranch(int reps) {
21         int t = 0;
22         for (int i = 0; i < reps; ++i) {
23             t += signum1(-i);
24             t += signum1(0);
25             t += signum1(i);
26         }
27         return t;
28     }
29 
timeLongSignumBranchFree(int reps)30     public int timeLongSignumBranchFree(int reps) {
31         int t = 0;
32         for (int i = 0; i < reps; ++i) {
33             t += signum2(-i);
34             t += signum2(0);
35             t += signum2(i);
36         }
37         return t;
38     }
39 
signum1(long v)40     private static int signum1(long v) {
41         return v < 0 ? -1 : (v == 0 ? 0 : 1);
42     }
43 
signum2(long v)44     private static int signum2(long v) {
45         return ((int)(v >> 63)) | (int) (-v >>> 63); // Hacker's delight 2-7
46     }
47 
timeLongBitCount_BitSet(int reps)48     public int timeLongBitCount_BitSet(int reps) {
49         int t = 0;
50         for (int i = 0; i < reps; ++i) {
51             t += pop((long) i);
52         }
53         return t;
54     }
55 
pop(long l)56     private static int pop(long l) {
57         int count = popX(l & 0xffffffffL);
58         count += popX(l >>> 32);
59         return count;
60     }
61 
popX(long x)62     private static int popX(long x) {
63         // BEGIN android-note
64         // delegate to Integer.bitCount(i); consider using native code
65         // END android-note
66         x = x - ((x >>> 1) & 0x55555555);
67         x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
68         x = (x + (x >>> 4)) & 0x0f0f0f0f;
69         x = x + (x >>> 8);
70         x = x + (x >>> 16);
71         return (int) x & 0x0000003f;
72     }
73 
timeLongBitCount_2Int(int reps)74     public int timeLongBitCount_2Int(int reps) {
75         int t = 0;
76         for (int i = 0; i < reps; ++i) {
77             t += pop2((long) i);
78         }
79         return t;
80     }
81 
pop2(long l)82     private static int pop2(long l) {
83         int count = Integer.bitCount((int) (l & 0xffffffffL));
84         count += Integer.bitCount((int) (l >>> 32));
85         return count;
86     }
87 
timeLongBitCount_Long(int reps)88     public int timeLongBitCount_Long(int reps) {
89         int t = 0;
90         for (int i = 0; i < reps; ++i) {
91             t += Long.bitCount((long) i);
92         }
93         return t;
94     }
95 
96     /**
97      * Table for Seal's algorithm for Number of Trailing Zeros. Hacker's Delight
98      * online, Figure 5-18 (http://www.hackersdelight.org/revisions.pdf)
99      * The entries whose value is -1 are never referenced.
100      */
101     private static final byte[] NTZ_TABLE = {
102         32,  0,  1, 12,  2,  6, -1, 13,   3, -1,  7, -1, -1, -1, -1, 14,
103         10,  4, -1, -1,  8, -1, -1, 25,  -1, -1, -1, -1, -1, 21, 27, 15,
104         31, 11,  5, -1, -1, -1, -1, -1,   9, -1, -1, 24, -1, -1, 20, 26,
105         30, -1, -1, -1, -1, 23, -1, 19,  29, -1, 22, 18, 28, 17, 16, -1
106     };
107 
numberOfTrailingZerosHD(int i)108     private static int numberOfTrailingZerosHD(int i) {
109         // Seal's algorithm - Hacker's Delight 5-18
110         i &= -i;
111         i = (i <<  4) + i;    // x *= 17
112         i = (i <<  6) + i;    // x *= 65
113         i = (i << 16) - i;    // x *= 65535
114         return NTZ_TABLE[i >>> 26];
115     }
116 
numberOfTrailingZerosOL(int i)117     private static int numberOfTrailingZerosOL(int i) {
118         return NTZ_TABLE[((i & -i) * 0x0450FBAF) >>> 26];
119     }
120 
timeNumberOfTrailingZerosHD(int reps)121     public int timeNumberOfTrailingZerosHD(int reps) {
122         int t = 0;
123         for (int i = 0; i < reps; ++i) {
124             t += numberOfTrailingZerosHD(i);
125         }
126         return t;
127     }
128 
timeNumberOfTrailingZerosOL(int reps)129     public int timeNumberOfTrailingZerosOL(int reps) {
130         int t = 0;
131         for (int i = 0; i < reps; ++i) {
132             t += numberOfTrailingZerosOL(i);
133         }
134         return t;
135     }
136 
timeIntegerValueOf(int reps)137     public int timeIntegerValueOf(int reps) throws Exception {
138         String[] intStrings = new String[]{"0", "1", "12", "123", "1234", "12345",
139                                            "123456", "1234567", "12345678"};
140         int t = 0;
141         for (int i = 0; i < reps; ++i) {
142             for (int j = 0; j < intStrings.length; ++j) {
143                 t += Integer.valueOf(intStrings[j]);
144             }
145         }
146         return t;
147     }
148 }
149