benchmark silo added
[c11concurrency-benchmarks.git] / silo / small_unordered_map.h
1 #ifndef _SMALL_UNORDERED_MAP_H_
2 #define _SMALL_UNORDERED_MAP_H_
3
4 #include <algorithm>
5 #include <iterator>
6 #include <stdint.h>
7 #include <unordered_map>
8 #include <type_traits>
9
10 #include "macros.h"
11 #include "counter.h"
12 #include "log2.hh"
13 #include "ndb_type_traits.h"
14
15 namespace private_ {
16
17   template <typename T>
18   struct is_eq_expensive { static const bool value = true; };
19
20   struct cheap_eq { static const bool value = false; };
21
22   // equals is cheap for integer types
23   template <> struct is_eq_expensive<bool>     : public cheap_eq {};
24   template <> struct is_eq_expensive<uint8_t>  : public cheap_eq {};
25   template <> struct is_eq_expensive<int8_t>   : public cheap_eq {};
26   template <> struct is_eq_expensive<uint16_t> : public cheap_eq {};
27   template <> struct is_eq_expensive<int16_t>  : public cheap_eq {};
28   template <> struct is_eq_expensive<uint32_t> : public cheap_eq {};
29   template <> struct is_eq_expensive<int32_t>  : public cheap_eq {};
30   template <> struct is_eq_expensive<uint64_t> : public cheap_eq {};
31   template <> struct is_eq_expensive<int64_t>  : public cheap_eq {};
32
33   static event_avg_counter evt_avg_max_unordered_map_chain_length CACHE_ALIGNED
34     ("avg_max_unordered_map_chain_length");
35
36   template <typename T>
37   struct fast_func_param {
38     typedef typename std::conditional<std::is_scalar<T>::value, T, const T &>::type type;
39   };
40
41   template <typename T>
42   struct myhash {
43     inline ALWAYS_INLINE size_t
44     operator()(typename fast_func_param<T>::type t) const
45     {
46       return std::hash<T>()(t);
47     }
48   };
49
50   template <typename Tp>
51   struct myhash<Tp *> {
52     inline ALWAYS_INLINE size_t
53     operator()(Tp *t) const
54     {
55       // std::hash for ptrs is bad
56       // tommyhash: http://tommyds.sourceforge.net/doc/tommyhash_8h_source.html
57       size_t key = reinterpret_cast<size_t>(t) >> 3; // shift out 8-byte pointer alignment
58 #ifdef USE_TOMMY_HASH
59       key = (~key) + (key << 21); // key = (key << 21) - key - 1;
60       key = key ^ (key >> 24);
61       key = (key + (key << 3)) + (key << 8); // key * 265
62       key = key ^ (key >> 14);
63       key = (key + (key << 2)) + (key << 4); // key * 21
64       key = key ^ (key >> 28);
65       key = key + (key << 31);
66 #else
67       key = (~key) + (key << 21); // key = (key << 21) - key - 1;
68       key = key ^ (key >> 24);
69 #endif
70       return key;
71     }
72   };
73
74   static inline constexpr size_t
75   TableSize(size_t small_size)
76   {
77     return round_up_to_pow2_const(small_size);
78   }
79 }
80
81 /**
82  * For under SmallSize, uses linear probing on a fixed size array. Otherwise,
83  * delegates to a regular std::unordered_map
84  *
85  * XXX(stephentu): allow custom allocator
86  */
87 template <typename Key,
88           typename T,
89           size_t SmallSize = SMALL_SIZE_MAP,
90           typename Hash = private_::myhash<Key>>
91 class small_unordered_map {
92 public:
93   typedef Key key_type;
94   typedef T mapped_type;
95   typedef std::pair<const key_type, mapped_type> value_type;
96   typedef Hash hasher;
97   typedef T & reference;
98   typedef const T & const_reference;
99
100 private:
101   typedef std::unordered_map<Key, T, Hash> large_table_type;
102   typedef std::pair<key_type, mapped_type> bucket_value_type;
103
104   typedef typename large_table_type::iterator large_table_iterator;
105   typedef typename large_table_type::const_iterator large_table_const_iterator;
106
107   static const bool is_trivially_destructible =
108     private_::is_trivially_destructible<bucket_value_type>::value;
109
110   static const size_t TableSize = private_::TableSize(SmallSize);
111   static_assert(SmallSize >= 1, "XXX");
112   static_assert(TableSize >= 1, "XXX");
113
114   struct bucket {
115     inline ALWAYS_INLINE bucket_value_type *
116     ptr()
117     {
118       return reinterpret_cast<bucket_value_type *>(&buf[0]);
119     }
120
121     inline ALWAYS_INLINE const bucket_value_type *
122     ptr() const
123     {
124       return reinterpret_cast<const bucket_value_type *>(&buf[0]);
125     }
126
127     inline ALWAYS_INLINE bucket_value_type &
128     ref()
129     {
130       return *ptr();
131     }
132
133     inline ALWAYS_INLINE const bucket_value_type &
134     ref() const
135     {
136       return *ptr();
137     }
138
139     template <class... Args>
140     inline ALWAYS_INLINE void
141     construct(size_t hash, Args &&... args)
142     {
143       h = hash;
144       new (&ref()) bucket_value_type(std::forward<Args>(args)...);
145     }
146
147     inline ALWAYS_INLINE void
148     destroy()
149     {
150       if (!is_trivially_destructible)
151         ref().~bucket_value_type();
152     }
153
154     struct bucket *bnext;
155     size_t h;
156     char buf[sizeof(value_type)];
157   };
158
159   // iterators are not stable across mutation
160   template <typename SmallIterType,
161             typename LargeIterType,
162             typename ValueType>
163   class iterator_ : public std::iterator<std::forward_iterator_tag, ValueType> {
164     friend class small_unordered_map;
165   public:
166     inline iterator_() : large(false), b(0) {}
167
168     template <typename S, typename L, typename V>
169     inline iterator_(const iterator_<S, L, V> &other)
170       : large(other.large), b(other.b)
171     {}
172
173     inline ValueType &
174     operator*() const
175     {
176       if (unlikely(large))
177         return *large_it;
178       return reinterpret_cast<ValueType &>(b->ref());
179     }
180
181     inline ValueType *
182     operator->() const
183     {
184       if (unlikely(large))
185         return &(*large_it);
186       return reinterpret_cast<ValueType *>(b->ptr());
187     }
188
189     inline bool
190     operator==(const iterator_ &o) const
191     {
192       INVARIANT(large == o.large);
193       if (likely(!large))
194         return b == o.b;
195       return large_it == o.large_it;
196     }
197
198     inline bool
199     operator!=(const iterator_ &o) const
200     {
201       return !operator==(o);
202     }
203
204     inline iterator_ &
205     operator++()
206     {
207       if (unlikely(large)) {
208         ++large_it;
209         return *this;
210       }
211       b++;
212       return *this;
213     }
214
215     inline iterator_
216     operator++(int)
217     {
218       iterator_ cur = *this;
219       ++(*this);
220       return cur;
221     }
222
223   protected:
224     inline iterator_(SmallIterType *b)
225       : large(false), b(b)
226     {
227     }
228     inline iterator_(LargeIterType large_it)
229       : large(true), large_it(large_it) {}
230
231   private:
232     bool large;
233     SmallIterType *b;
234     LargeIterType large_it;
235   };
236
237   static size_t
238   chain_length(bucket *b)
239   {
240     size_t ret = 0;
241     while (b) {
242       ret++;
243       b = b->bnext;
244     }
245     return ret;
246   }
247
248 public:
249
250   typedef
251     iterator_<
252       bucket,
253       large_table_iterator,
254       value_type>
255     iterator;
256
257   typedef
258     iterator_<
259       const bucket,
260       large_table_const_iterator,
261       const value_type>
262     const_iterator;
263
264   small_unordered_map()
265     : n(0), large_elems(0)
266   {
267     NDB_MEMSET(&table[0], 0, sizeof(table));
268   }
269
270   ~small_unordered_map()
271   {
272     if (unlikely(large_elems)) {
273       delete large_elems;
274       return;
275     }
276     for (size_t i = 0; i < n; i++)
277       small_elems[i].destroy();
278   }
279
280   small_unordered_map(const small_unordered_map &other)
281     : n(0), large_elems(0)
282   {
283     NDB_MEMSET(&table[0], 0, sizeof(table));
284     assignFrom(other);
285   }
286
287   small_unordered_map &
288   operator=(const small_unordered_map &other)
289   {
290     // self assignment
291     if (unlikely(this == &other))
292       return *this;
293     assignFrom(other);
294     return *this;
295   }
296
297 private:
298   bucket *
299   find_bucket(const key_type &k, size_t *hash_value)
300   {
301     INVARIANT(!large_elems);
302     const size_t h = Hash()(k);
303     if (hash_value)
304       *hash_value = h;
305     const size_t i = h % TableSize;
306     bucket *b = table[i];
307     while (b) {
308       const bool check_hash = private_::is_eq_expensive<key_type>::value;
309       if ((!check_hash || b->h == h) && b->ref().first == k)
310         return b;
311       b = b->bnext;
312     }
313     return 0;
314   }
315
316   inline ALWAYS_INLINE const bucket *
317   find_bucket(const key_type &k, size_t *hash_value) const
318   {
319     return const_cast<small_unordered_map *>(this)->find_bucket(k, hash_value);
320   }
321
322 public:
323
324   // XXX(stephentu): template away this stuff
325
326   mapped_type &
327   operator[](const key_type &k)
328   {
329     if (unlikely(large_elems))
330       return large_elems->operator[](k);
331     size_t h;
332     bucket *b = find_bucket(k, &h);
333     if (b)
334       return b->ref().second;
335     if (unlikely(n == SmallSize)) {
336       large_elems = new large_table_type;
337       for (size_t n = 0; n < SmallSize; n++) {
338         bucket &b = small_elems[n];
339 #if GCC_AT_LEAST_47
340         large_elems->emplace(std::move(b.ref()));
341 #else
342         large_elems->operator[](std::move(b.ref().first)) = std::move(b.ref().second);
343 #endif
344         b.destroy();
345       }
346       n = 0;
347       return large_elems->operator[](k);
348     }
349     INVARIANT(n < SmallSize);
350     b = &small_elems[n++];
351     b->construct(h, k, mapped_type());
352     const size_t i = h % TableSize;
353     b->bnext = table[i];
354     table[i] = b;
355     return b->ref().second;
356   }
357
358   mapped_type &
359   operator[](key_type &&k)
360   {
361     if (unlikely(large_elems))
362       return large_elems->operator[](std::move(k));
363     size_t h;
364     bucket *b = find_bucket(k, &h);
365     if (b)
366       return b->ref().second;
367     if (unlikely(n == SmallSize)) {
368       large_elems = new large_table_type;
369       for (size_t n = 0; n < SmallSize; n++) {
370         bucket &b = small_elems[n];
371 #if GCC_AT_LEAST_47
372         large_elems->emplace(std::move(b.ref()));
373 #else
374         large_elems->operator[](std::move(b.ref().first)) = std::move(b.ref().second);
375 #endif
376         b.destroy();
377       }
378       n = 0;
379       return large_elems->operator[](std::move(k));
380     }
381     INVARIANT(n < SmallSize);
382     b = &small_elems[n++];
383     b->construct(h, std::move(k), mapped_type());
384     const size_t i = h % TableSize;
385     b->bnext = table[i];
386     table[i] = b;
387     return b->ref().second;
388   }
389
390   inline size_t
391   size() const
392   {
393     if (unlikely(large_elems))
394       return large_elems->size();
395     return n;
396   }
397
398   inline bool
399   empty() const
400   {
401     return size() == 0;
402   }
403
404   iterator
405   begin()
406   {
407     if (unlikely(large_elems))
408       return iterator(large_elems->begin());
409     return iterator(&small_elems[0]);
410   }
411
412   const_iterator
413   begin() const
414   {
415     if (unlikely(large_elems))
416       return const_iterator(large_elems->begin());
417     return const_iterator(&small_elems[0]);
418   }
419
420   inline iterator
421   end()
422   {
423     if (unlikely(large_elems))
424       return iterator(large_elems->end());
425     return iterator(&small_elems[n]);
426   }
427
428   inline const_iterator
429   end() const
430   {
431     if (unlikely(large_elems))
432       return const_iterator(large_elems->end());
433     return const_iterator(&small_elems[n]);
434   }
435
436   iterator
437   find(const key_type &k)
438   {
439     if (unlikely(large_elems))
440       return iterator(large_elems->find(k));
441     bucket * const b = find_bucket(k, 0);
442     if (b)
443       return iterator(b);
444     return end();
445   }
446
447   const_iterator
448   find(const key_type &k) const
449   {
450     if (unlikely(large_elems))
451       return const_iterator(large_elems->find(k));
452     const bucket * const b = find_bucket(k, 0);
453     if (b)
454       return const_iterator(b);
455     return end();
456   }
457
458   void
459   clear()
460   {
461     if (unlikely(large_elems)) {
462       INVARIANT(!n);
463       delete large_elems;
464       large_elems = NULL;
465       return;
466     }
467     if (!n)
468       return;
469     NDB_MEMSET(&table[0], 0, sizeof(table));
470     for (size_t i = 0; i < n; i++)
471       small_elems[i].destroy();
472     n = 0;
473   }
474
475 public:
476   // non-standard API
477   inline bool is_small_type() const { return !large_elems; }
478
479 private:
480
481   // doesn't check for self assignment
482   inline void
483   assignFrom(const small_unordered_map &that)
484   {
485     clear();
486     if (that.large_elems) {
487       INVARIANT(!that.n);
488       INVARIANT(!n);
489       large_elems = new large_table_type(*that.large_elems);
490       return;
491     }
492     INVARIANT(!large_elems);
493     for (size_t i = 0; i < that.n; i++) {
494       bucket * const b = &small_elems[n++];
495       const bucket * const that_b = &that.small_elems[i];
496       b->construct(that_b->h, that_b->ref().first, that_b->ref().second);
497       const size_t idx = b->h % TableSize;
498       b->bnext = table[idx];
499       table[idx] = b;
500     }
501   }
502
503   size_t n;
504
505   bucket small_elems[SmallSize];
506   bucket *table[TableSize];
507
508   large_table_type *large_elems;
509 };
510
511 #endif /* _SMALL_UNORDERED_MAP_H_ */