COMBINATORIAL_BLAS  1.6
utils.h
Go to the documentation of this file.
1 // This code is part of the Problem Based Benchmark Suite (PBBS)
2 // Copyright (c) 2010 Guy Blelloch and the PBBS team
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a
5 // copy of this software and associated documentation files (the
6 // "Software"), to deal in the Software without restriction, including
7 // without limitation the rights (to use, copy, modify, merge, publish,
8 // distribute, sublicense, and/or sell copies of the Software, and to
9 // permit persons to whom the Software is furnished to do so, subject to
10 // the following conditions:
11 //
12 // The above copyright notice and this permission notice shall be included
13 // in all copies or substantial portions of the Software.
14 //
15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
16 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
19 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
20 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
21 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 
23 #ifndef _BENCH_UTILS_INCLUDED
24 #define _BENCH_UTILS_INCLUDED
25 #include <iostream>
26 #include <algorithm>
27 #include <limits.h>
28 
29 #if defined(__APPLE__)
30 #define PTCMPXCH " cmpxchgl %2,%1\n"
31 #else
32 #define PTCMPXCH " cmpxchgq %2,%1\n"
33 
34 // Needed to make frequent large allocations efficient with standard
35 // malloc implementation. Otherwise they are allocated directly from
36 // vm.
37 #include <malloc.h>
38 static int __ii = mallopt(M_MMAP_MAX,0);
39 static int __jj = mallopt(M_TRIM_THRESHOLD,-1);
40 #endif
41 
42 #define newA(__E,__n) (__E*) malloc((__n)*sizeof(__E))
43 
44 namespace utils {
45 
46 // ADAM: added inline to remove "defined but not used" warning
47 static inline void myAssert(int cond, std::string s) {
48  if (!cond) {
49  std::cout << s << std::endl;
50  abort();
51  }
52 }
53 
54 // returns the log base 2 rounded up (works on ints or longs or unsigned versions)
55 template <class T>
56 static int log2Up(T i) {
57  int a=0;
58  T b=i-1;
59  while (b > 0) {b = b >> 1; a++;}
60  return a;
61 }
62 
63 // ADAM: added inline to remove "defined but not used" warning
64 static inline int logUp(unsigned int i) {
65  int a=0;
66  int b=i-1;
67  while (b > 0) {b = b >> 1; a++;}
68  return a;
69 }
70 
71 // ADAM: added inline to remove "defined but not used" warning
72 static inline int logUpLong(unsigned long i) {
73  int a=0;
74  long b=i-1;
75  while (b > 0) {b = b >> 1; a++;}
76  return a;
77 }
78 
79 inline unsigned int hash(unsigned int a)
80 {
81  a = (a+0x7ed55d16) + (a<<12);
82  a = (a^0xc761c23c) ^ (a>>19);
83  a = (a+0x165667b1) + (a<<5);
84  a = (a+0xd3a2646c) ^ (a<<9);
85  a = (a+0xfd7046c5) + (a<<3);
86  a = (a^0xb55a4f09) ^ (a>>16);
87  return a;
88 }
89 
90 inline int hashInt(unsigned int a) {
91  return hash(a) & (((unsigned) 1 << 31) - 1);
92 }
93 
94 inline unsigned int hash2(unsigned int a)
95 {
96  return (((unsigned int) 1103515245 * a) + (unsigned int) 12345) %
97  (unsigned int) 0xFFFFFFFF;
98 }
99 
100 // compare and swap on 8 byte quantities
101 inline bool LCAS(long *ptr, long oldv, long newv) {
102  unsigned char ret;
103  /* Note that sete sets a 'byte' not the word */
104  __asm__ __volatile__ (
105  " lock\n"
106  " cmpxchgq %2,%1\n"
107  " sete %0\n"
108  : "=q" (ret), "=m" (*ptr)
109  : "r" (newv), "m" (*ptr), "a" (oldv)
110  : "memory");
111  return ret;
112 }
113 
114 // compare and swap on 4 byte quantity
115 inline bool SCAS(int *ptr, int oldv, int newv) {
116  unsigned char ret;
117  /* Note that sete sets a 'byte' not the word */
118  __asm__ __volatile__ (
119  " lock\n"
120  " cmpxchgl %2,%1\n"
121  " sete %0\n"
122  : "=q" (ret), "=m" (*ptr)
123  : "r" (newv), "m" (*ptr), "a" (oldv)
124  : "memory");
125  return ret;
126 }
127 
128 // The conditional should be removed by the compiler
129 // this should work with pointer types, or pairs of integers
130 template <class ET>
131 inline bool CAS(ET *ptr, ET oldv, ET newv) {
132  if (sizeof(ET) == 8) {
133  return utils::LCAS((long*) ptr, *((long*) &oldv), *((long*) &newv));
134  } else if (sizeof(ET) == 4) {
135  return utils::SCAS((int *) ptr, *((int *) &oldv), *((int *) &newv));
136  } else {
137  std::cout << "CAS bad length" << std::endl;
138  abort();
139  }
140 }
141 
142 template <class ET>
143 inline bool CAS_GCC(ET *ptr, ET oldv, ET newv) {
144  return __sync_bool_compare_and_swap(ptr, oldv, newv);
145 }
146 
147 template <class ET>
148 inline ET fetchAndAdd(ET *a, ET b) {
149  volatile ET newV, oldV;
150  abort();
151  do {oldV = *a; newV = oldV + b;}
152  while (!CAS(a, oldV, newV));
153  return oldV;
154 }
155 
156 template <class ET>
157 inline void writeAdd(ET *a, ET b) {
158  volatile ET newV, oldV;
159  do {oldV = *a; newV = oldV + b;}
160  while (!CAS(a, oldV, newV));
161 }
162 
163 template <class ET>
164 inline bool writeMax(ET *a, ET b) {
165  ET c; bool r=0;
166  do c = *a;
167  while (c < b && !(r=CAS(a,c,b)));
168  return r;
169 }
170 
171 template <class ET>
172 inline bool writeMin(ET *a, ET b) {
173  ET c; bool r=0;
174  do c = *a;
175  while (c > b && !(r=CAS(a,c,b)));
176  // while (c > b && !(r=__sync_bool_compare_and_swap(a, c, b)));
177  return r;
178 }
179 
180 template <class ET>
181 inline bool writeMin(ET **a, ET *b) {
182  ET* c; bool r = 0;
183  do c = *a;
184  while (c > b && !(r=CAS(a,c,b)));
185  return r;
186 }
187 
188 template <class E>
189 struct identityF { E operator() (const E& x) {return x;}};
190 
191 template <class E>
192 struct addF { E operator() (const E& a, const E& b) const {return a+b;}};
193 
194 template <class E>
195 struct absF { E operator() (const E& a) const {return std::abs(a);}};
196 
197 template <class E>
198 struct zeroF { E operator() (const E& a) const {return 0;}};
199 
200 template <class E>
201 struct maxF { E operator() (const E& a, const E& b) const {return (a>b) ? a : b;}};
202 
203 template <class E>
204 struct minF { E operator() (const E& a, const E& b) const {return (a<b) ? a : b;}};
205 
206 template <class E1, class E2>
207  struct firstF {E1 operator() (std::pair<E1,E2> a) {return a.first;} };
208 
209 template <class E1, class E2>
210  struct secondF {E2 operator() (std::pair<E1,E2> a) {return a.second;} };
211 
212 }
213 
214 #endif // _BENCH_UTILS_INCLUDED
bool LCAS(long *ptr, long oldv, long newv)
Definition: utils.h:101
bool writeMin(ET *a, ET b)
Definition: utils.h:172
int hashInt(unsigned int a)
Definition: utils.h:90
unsigned int hash2(unsigned int a)
Definition: utils.h:94
bool SCAS(int *ptr, int oldv, int newv)
Definition: utils.h:115
bool writeMax(ET *a, ET b)
Definition: utils.h:164
bool CAS_GCC(ET *ptr, ET oldv, ET newv)
Definition: utils.h:143
void writeAdd(ET *a, ET b)
Definition: utils.h:157
bool CAS(ET *ptr, ET oldv, ET newv)
Definition: utils.h:131
Definition: utils.h:44
unsigned int hash(unsigned int a)
Definition: utils.h:79
ET fetchAndAdd(ET *a, ET b)
Definition: utils.h:148
E operator()(const E &x)
Definition: utils.h:189