1 /* Compare times for firstbitnz instructions */
2 /* Usage: lztest K N
3 - measures the time for 1000*N popcount operations on words
4 with K one bits, comparing with the macro FIRSTBITNZ.
5 Compile with values for WORDSIZE and FBNZ with FBNZ values:
6 1 = __builtin_clz* */
7
8 #define MAXN WORDSIZE
9
10 #ifndef WORDSIZE
11 #define WORDSIZE 32
12 #endif
13
14 #ifndef FBNZ
15 #error Need a value for FBNZ
16 #endif
17
18 #if FBNZ==1
19 #define NEWFBNZ(x,c) {c = FIRSTBITNZ(x);}
20 #endif
21
22 #include "gtools.h"
23 #ifdef __INTEL_COMPILER
24 #include <nmmintrin.h>
25 #endif
26
27 #if WORDSIZE==64
28 #define FIRSTBITMAC(x) ((x) & MSK3232 ? \
29 (x) & MSK1648 ? \
30 (x) & MSK0856 ? \
31 0+leftbit[((x)>>56) & MSK8] : \
32 8+leftbit[(x)>>48] \
33 : (x) & MSK0840 ? \
34 16+leftbit[(x)>>40] : \
35 24+leftbit[(x)>>32] \
36 : (x) & MSK1616 ? \
37 (x) & MSK0824 ? \
38 32+leftbit[(x)>>24] : \
39 40+leftbit[(x)>>16] \
40 : (x) & MSK0808 ? \
41 48+leftbit[(x)>>8] : \
42 56+leftbit[x])
43 #elif WORDSIZE==32
44 #define FIRSTBITMAC(x) ((x) & MSK1616 ? ((x) & MSK0824 ? \
45 leftbit[((x)>>24) & MSK8] : 8+leftbit[(x)>>16]) \
46 : ((x) & MSK0808 ? 16+leftbit[(x)>>8] : 24+leftbit[x]))
47 #else
48 #define FIRSTBITMAC(x) ((x) & MSK0808 ? leftbit[((x)>>8) & MSK8] : 8+leftbit[x])
49 #endif
50
51 #if FBNZ==1
52 #define NEWFBNZ(x,c) {c = FIRSTBITNZ(x);}
53 #endif
54
55 static setword
ransetword(int k)56 ransetword(int k) /* setword with k random bits */
57 {
58 register setword w,rb;
59 register int j;
60
61 j = 0;
62 w = 0;
63 for (;;)
64 {
65 if (j == k) return w;
66
67 rb = bit[random() % WORDSIZE];
68 if ((rb & w) == 0)
69 {
70 w |= rb;
71 ++j;
72 }
73 }
74 }
75
76 static double
timemac(setword * x,int n,int iters,int * sump)77 timemac(setword *x, int n, int iters, int *sump)
78 {
79 register int c,i,j,sum;
80 register setword w;
81 int it;
82 double t;
83
84 sum = 0;
85 for (i = 0; i < n; ++i)
86 {
87 w = x[i];
88 sum += FIRSTBITMAC(w);
89 }
90
91 t = CPUTIME;
92
93 for (it = 0; it < iters; ++it)
94 {
95 for (i = 0; i < n; ++i)
96 {
97 w = x[i];
98 sum += FIRSTBITMAC(w);
99 }
100 sum ^= it;
101 }
102
103 t = CPUTIME - t;
104 *sump = sum;
105
106 return t;
107 }
108
109 static double
timeold(setword * x,int n,int iters,int * sump)110 timeold(setword *x, int n, int iters, int *sump)
111 {
112 register int c,i,j,sum;
113 register setword w;
114 int it;
115 double t;
116
117 sum = 0;
118 for (i = 0; i < n; ++i)
119 {
120 w = x[i];
121 sum += FIRSTBITNZ(w);
122 }
123
124 t = CPUTIME;
125
126 for (it = 0; it < iters; ++it)
127 {
128 for (i = 0; i < n; ++i)
129 {
130 w = x[i];
131 sum += FIRSTBITNZ(w);
132 }
133 sum ^= it;
134 }
135
136 t = CPUTIME - t;
137 *sump = sum;
138
139 return t;
140 }
141
142 static double
timenew(setword * x,int n,int iters,int * sump)143 timenew(setword *x, int n, int iters, int *sump)
144 {
145 register int c,i,j,sum;
146 register setword w;
147 int it;
148 double t;
149
150 sum = 0;
151 for (i = 0; i < n; ++i)
152 {
153 w = x[i];
154 NEWFBNZ(w,c);
155 sum += c;
156 }
157
158 t = CPUTIME;
159
160 for (it = 0; it < iters; ++it)
161 {
162 for (i = 0; i < n; ++i)
163 {
164 w = x[i];
165 NEWFBNZ(w,c);
166 sum += c;
167 }
168 sum ^= it;
169 }
170
171 t = CPUTIME - t;
172 *sump = sum;
173
174 return t;
175 }
176
177 static double
timenull(setword * x,int n,int iters,int * sump)178 timenull(setword *x, int n, int iters, int *sump)
179 {
180 register int c,i,j,sum;
181 register setword w;
182 int it;
183 double t;
184
185 sum = 0;
186 for (i = 0; i < n; ++i)
187 {
188 w = x[i];
189 NEWFBNZ(w,c);
190 sum += c;
191 }
192
193 t = CPUTIME;
194
195 for (it = 0; it < iters; ++it)
196 {
197 for (i = 0; i < n; ++i)
198 {
199 w = x[i];
200 c = w;
201 sum += c;
202 }
203 sum ^= it;
204 }
205
206 t = CPUTIME - t;
207 *sump = sum;
208
209 return t;
210 }
211
212 int
main(int argc,char * argv[])213 main(int argc, char *argv[])
214 {
215 int i,k,iters;
216 setword x[1000];
217 double tnull,told,tnew,tmac;
218 int summac,sumold,sumnew,sumnull;
219
220 printf("WORDSIZE=%d FBNZ=%s ",WORDSIZE,
221 FBNZ==1 ? "intrinsic" : "undefined");
222 #ifdef SETWORD_SHORT
223 printf(" setword=unsigned short ");
224 #endif
225 #ifdef SETWORD_INT
226 printf(" setword=unsigned int ");
227 #endif
228 #ifdef SETWORD_LONG
229 printf(" setword=unsigned long ");
230 #endif
231 #ifdef SETWORD_LONGLONG
232 printf(" setword=unsigned long long ");
233 #endif
234 #ifdef __SSE4_2__
235 printf("__SSE4_2__ ");
236 #endif
237 #ifdef __INTEL_COMPILER
238 printf("__INTEL_COMPILER ");
239 #endif
240 printf("\n");
241
242 if (argc != 3)
243 {
244 fprintf(stderr,"Usage: lztest num1bits numiters\n");
245 exit(1);
246 }
247
248 k = atoi(argv[1]);
249 if (k > WORDSIZE) k = WORDSIZE;
250 iters = atoi(argv[2]);
251
252 for (i = 0; i < 1000; ++i)
253 x[i] = ransetword(k);
254
255 tnull = timenull(x,1000,iters,&sumnull);
256 tmac = timemac(x,1000,iters,&summac);
257 tnew = timenew(x,1000,iters,&sumnew);
258
259 if (summac != sumnew) printf("*** sum mismatch (mac/old)\n");
260
261 printf("macro=%3.2f new=%3.2f\n",
262 tmac-tnull,tnew-tnull);
263
264 return 0;
265 }
266