HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
unordered_map_concurrent.h
Go to the documentation of this file.
1 /*
2 Copyright 2012 Larry Gritz and the other authors and contributors.
3 All Rights Reserved.
4 
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
8 * Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 * Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 * Neither the name of the software's owners nor the names of its
14  contributors may be used to endorse or promote products derived from
15  this software without specific prior written permission.
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 (This is the Modified BSD License)
29 */
30 
31 
32 #pragma once
33 
34 #include <OpenImageIO/dassert.h>
35 #include <OpenImageIO/hash.h>
36 #include <OpenImageIO/thread.h>
37 
39 
40 
41 /// unordered_map_concurrent provides an unordered_map replacement that
42 /// is optimized for concurrent access. Its principle of operation is
43 /// similar to Java's ConcurrentHashMap.
44 ///
45 /// With naive use of an unordered_map, multiple threads would have to
46 /// lock a mutex of some kind to control access to the map, either with
47 /// a unique full lock, or with a reader/writer lock. But as the number
48 /// of threads contending for this shared resource rises, they end up
49 /// locking each other out and the map becomes a thread bottleneck.
50 ///
51 /// unordered_map_concurrent solves this problem by internally splitting
52 /// the hash map into several disjoint bins, each of which is a standard
53 /// unordered_map. For any given map item, the hash of its key
54 /// determines both the bin as well as its hashing within the bin (i.e.,
55 /// we break a big hash map into lots of little hash maps,
56 /// deterministically determined by the key). Thus, we should expect
57 /// map entries to be spread more or less evenly among the bins. There
58 /// is no mutex that locks the map as a whole; instead, each bin is
59 /// locked individually. If the number of bins is larger than the
60 /// typical number of threads, most of the time two (or more) threads
61 /// accessing the map simultaneously will not be accessing the same bin,
62 /// and therefore will not be contending for the same lock.
63 ///
64 /// unordered_map_concurrent provides an iterator which points to an
65 /// entry in the map and also knows which bin it is in and implicitly
66 /// holds a lock on the bin. When the iterator is destroyed, the lock
67 /// on that bin is released. When the iterator is incremented in such a
68 /// way that it transitions from the last entry of its current bin to
69 /// the first entry of the next bin, it will also release its current
70 /// lock and obtain a lock on the next bin.
71 ///
72 
73 template<class KEY, class VALUE, class HASH = std::hash<KEY>,
74  class PRED = std::equal_to<KEY>, size_t BINS = 16,
75  class BINMAP = unordered_map<KEY, VALUE, HASH, PRED>>
77 public:
78  typedef BINMAP BinMap_t;
79  typedef typename BINMAP::iterator BinMap_iterator_t;
80 
81 public:
82  unordered_map_concurrent() { m_size = 0; }
83 
85  {
86  // for (size_t i = 0; i < BINS; ++i)
87  // std::cout << "Bin " << i << ": " << m_bins[i].map.size() << "\n";
88  }
89 
90  /// An unordered_map_concurrent::iterator points to a specific entry
91  /// in the umc, and holds a lock to the bin the entry is in.
92  class iterator {
93  public:
94  friend class unordered_map_concurrent<KEY, VALUE, HASH, PRED, BINS,
95  BINMAP>;
96 
97  public:
98  /// Construct an unordered_map_concurrent iterator that points
99  /// to nothing.
101  : m_umc(umc)
102  , m_bin(-1)
103  , m_locked(false)
104  {
105  }
106 
107  /// Copy constructor of an unordered_map_concurrent iterator
108  /// transfers the lock (if held) to this. Caveat: the copied
109  /// iterator no longer holds the lock!
111  {
112  m_umc = src.m_umc;
113  m_bin = src.m_bin;
114  m_biniterator = src.m_biniterator;
115  m_locked = src.m_locked;
116  // assignment transfers lock ownership
117  *(const_cast<bool*>(&src.m_locked)) = false;
118  }
119 
120  /// Destroying an unordered_map_concurrent iterator releases any
121  /// bin locks it held.
122  ~iterator() { clear(); }
123 
124  /// Totally invalidate this iterator -- point it to nothing
125  /// (releasing any locks it may have had).
126  void clear()
127  {
128  if (m_umc) {
129  unbin();
130  m_umc = NULL;
131  }
132  }
133 
134  // Dereferencing returns a reference to the hash table entry the
135  // iterator refers to.
136  const typename BinMap_t::value_type& operator*() const
137  {
138  return *m_biniterator;
139  }
140 
141  /// Dereferencing returns a reference to the hash table entry the
142  /// iterator refers to.
143  const typename BinMap_t::value_type* operator->() const
144  {
145  return &(*m_biniterator);
146  }
147 
148  /// Treating an iterator as a bool yields true if it points to a
149  /// valid element of one of the bins of the map, false if it's
150  /// equivalent to the end() iterator.
151  operator bool()
152  {
153  return m_umc && m_bin >= 0
154  && m_biniterator != m_umc->m_bins[m_bin].map.end();
155  }
156 
157  /// Iterator assignment transfers ownership of any bin locks
158  /// held by the operand.
160  {
161  unbin();
162  m_umc = src.m_umc;
163  m_bin = src.m_bin;
164  m_biniterator = src.m_biniterator;
165  m_locked = src.m_locked;
166  // assignment transfers lock ownership
167  *(const_cast<bool*>(&src.m_locked)) = false;
168  return *this;
169  }
170 
171  bool operator==(const iterator& other) const
172  {
173  if (m_umc != other.m_umc)
174  return false;
175  if (m_bin == -1 && other.m_bin == -1)
176  return true;
177  return m_bin == other.m_bin && m_biniterator == other.m_biniterator;
178  }
179  bool operator!=(const iterator& other) { return !(*this == other); }
180 
181  /// Increment to the next entry in the map. If we finish the
182  /// bin we're in, move on to the next bin (releasing our lock on
183  /// the old bin and acquiring a lock on the new bin). If we
184  /// finish the last bin of the map, return the end() iterator.
185  void operator++()
186  {
187  DASSERT(m_umc);
188  DASSERT(m_bin >= 0);
189  ++m_biniterator;
190  while (m_biniterator == m_umc->m_bins[m_bin].map.end()) {
191  if (m_bin == BINS - 1) {
192  // ran off the end
193  unbin();
194  return;
195  }
196  rebin(m_bin + 1);
197  }
198  }
199  void operator++(int) { ++(*this); }
200 
201  /// Lock the bin we point to, if not already locked.
202  void lock()
203  {
204  if (m_bin >= 0 && !m_locked) {
205  m_umc->m_bins[m_bin].lock();
206  m_locked = true;
207  }
208  }
209  /// Unlock the bin we point to, if locked.
210  void unlock()
211  {
212  if (m_bin >= 0 && m_locked) {
213  m_umc->m_bins[m_bin].unlock();
214  m_locked = false;
215  }
216  }
217 
218  /// Without changing the lock status (i.e., the caller already
219  /// holds the lock on the iterator's bin), increment to the next
220  /// element within the bin. Return true if it's pointing to a
221  /// valid element afterwards, false if it ran off the end of the
222  /// bin contents.
224  {
225  ++m_biniterator;
226  return (m_biniterator != m_umc->m_bins[m_bin].map.end());
227  }
228 
229  private:
230  // No longer refer to a particular bin, release lock on the bin
231  // it had (if any).
232  void unbin()
233  {
234  if (m_bin >= 0) {
235  if (m_locked)
236  unlock();
237  m_bin = -1;
238  }
239  }
240 
241  // Point this iterator to a different bin, releasing locks on
242  // the bin it previously referred to.
243  void rebin(int newbin)
244  {
245  DASSERT(m_umc);
246  unbin();
247  m_bin = newbin;
248  lock();
249  m_biniterator = m_umc->m_bins[m_bin].map.begin();
250  }
251 
252  unordered_map_concurrent* m_umc; // which umc this iterator refers to
253  int m_bin; // which bin within the umc
254  BinMap_iterator_t m_biniterator; // which entry within the bin
255  bool m_locked; // do we own the lock on the bin?
256  };
257 
258 
259  /// Return an interator pointing to the first entry in the map.
261  {
262  iterator i(this);
263  i.rebin(0);
264  while (i.m_biniterator == m_bins[i.m_bin].map.end()) {
265  if (i.m_bin == BINS - 1) {
266  // ran off the end
267  i.unbin();
268  return i;
269  }
270  i.rebin(i.m_bin + 1);
271  }
272  return i;
273  }
274 
275  /// Return an iterator signifying the end of the map (no valid
276  /// entry pointed to).
278  {
279  iterator i(this);
280  return i;
281  }
282 
283  /// Search for key. If found, return an iterator referring to the
284  /// element, otherwise, return an iterator that is equivalent to
285  /// this->end(). If do_lock is true, lock the bin that we're
286  /// searching and return the iterator in a locked state, and unlock
287  /// the bin again if not found; however, if do_lock is false, assume
288  /// that the caller already has the bin locked, so do no locking or
289  /// unlocking and return an iterator that is unaware that it holds a
290  /// lock.
291  iterator find(const KEY& key, bool do_lock = true)
292  {
293  size_t b = whichbin(key);
294  Bin& bin(m_bins[b]);
295  if (do_lock)
296  bin.lock();
297  typename BinMap_t::iterator it = bin.map.find(key);
298  if (it == bin.map.end()) {
299  // not found -- return the 'end' iterator
300  if (do_lock)
301  bin.unlock();
302  return end();
303  }
304  // Found
305  iterator i(this);
306  i.m_bin = (unsigned)b;
307  i.m_biniterator = it;
308  i.m_locked = do_lock;
309  return i;
310  }
311 
312  /// Search for key. If found, return true and store the value. If not
313  /// found, return false and do not alter value. If do_lock is true,
314  /// read-lock the bin while we're searching, and release it before
315  /// returning; however, if do_lock is false, assume that the caller
316  /// already has the bin locked, so do no locking or unlocking.
317  bool retrieve(const KEY& key, VALUE& value, bool do_lock = true)
318  {
319  size_t b = whichbin(key);
320  Bin& bin(m_bins[b]);
321  if (do_lock)
322  bin.lock();
323  typename BinMap_t::iterator it = bin.map.find(key);
324  bool found = (it != bin.map.end());
325  if (found)
326  value = it->second;
327  if (do_lock)
328  bin.unlock();
329  return found;
330  }
331 
332  /// Insert <key,value> into the hash map if it's not already there.
333  /// Return true if added, false if it was already present.
334  /// If do_lock is true, lock the bin containing key while doing this
335  /// operation; if do_lock is false, assume that the caller already
336  /// has the bin locked, so do no locking or unlocking.
337  bool insert(const KEY& key, const VALUE& value, bool do_lock = true)
338  {
339  size_t b = whichbin(key);
340  Bin& bin(m_bins[b]);
341  if (do_lock)
342  bin.lock();
343  auto result = bin.map.emplace(key, value);
344  if (result.second) {
345  // the insert was succesful!
346  ++m_size;
347  }
348  if (do_lock)
349  bin.unlock();
350  return result.second;
351  }
352 
353  /// If the key is in the map, safely erase it.
354  /// If do_lock is true, lock the bin containing key while doing this
355  /// operation; if do_lock is false, assume that the caller already
356  /// has the bin locked, so do no locking or unlocking.
357  void erase(const KEY& key, bool do_lock = true)
358  {
359  size_t b = whichbin(key);
360  Bin& bin(m_bins[b]);
361  if (do_lock)
362  bin.lock();
363  bin.map.erase(key);
364  if (do_lock)
365  bin.unlock();
366  }
367 
368  /// Return true if the entire map is empty.
369  bool empty() { return m_size == 0; }
370 
371  /// Return the total number of entries in the map.
372  size_t size() { return size_t(m_size); }
373 
374  /// Expliticly lock the bin that will contain the key (regardless of
375  /// whether there is such an entry in the map), and return its bin
376  /// number.
377  size_t lock_bin(const KEY& key)
378  {
379  size_t b = whichbin(key);
380  m_bins[b].lock();
381  return b;
382  }
383 
384  /// Explicitly unlock the specified bin (this assumes that the caller
385  /// holds the lock).
386  void unlock_bin(size_t bin) { m_bins[bin].unlock(); }
387 
388 private:
389  struct Bin {
390  OIIO_CACHE_ALIGN // align bin to cache line
391  mutable spin_mutex mutex; // mutex for this bin
392  BinMap_t map; // hash map for this bin
393 #ifndef NDEBUG
394  mutable atomic_int m_nlocks; // for debugging
395 #endif
396 
397  Bin()
398  {
399 #ifndef NDEBUG
400  m_nlocks = 0;
401 #endif
402  }
403  ~Bin()
404  {
405 #ifndef NDEBUG
406  DASSERT(m_nlocks == 0);
407 #endif
408  }
409  void lock() const
410  {
411  mutex.lock();
412 #ifndef NDEBUG
413  ++m_nlocks;
414  DASSERT_MSG(m_nlocks == 1, "oops, m_nlocks = %d", (int)m_nlocks);
415 #endif
416  }
417  void unlock() const
418  {
419 #ifndef NDEBUG
420  DASSERT_MSG(m_nlocks == 1, "oops, m_nlocks = %d", (int)m_nlocks);
421  --m_nlocks;
422 #endif
423  mutex.unlock();
424  }
425  };
426 
427  HASH m_hash; // hashing function
428  atomic_int m_size; // total entries in all bins
429  Bin m_bins[BINS]; // the bins
430 
431  static constexpr int log2(unsigned n)
432  {
433  return n < 2 ? 0 : 1 + log2(n / 2);
434  }
435 
436  // Which bin will this key always appear in?
437  size_t whichbin(const KEY& key)
438  {
439  constexpr int LOG2_BINS = log2(BINS);
440  constexpr int BIN_SHIFT = 32 - LOG2_BINS;
441 
442  static_assert(1 << LOG2_BINS == BINS,
443  "Number of bins must be a power of two");
444  static_assert(~uint32_t(0) >> BIN_SHIFT == (BINS - 1), "Hash overflow");
445 
446  // Use the high order bits of the hash to index the bin. We assume that the
447  // low-order bits of the hash will directly be used to index the hash table,
448  // so using those would lead to collisions.
449  // To avoid mixups between size_t among platforms, we always cast to a 32-bit
450  // integer first. Its quite possible the hash function only gave us a uint32_t
451  // even though the API technically wants a size_t.
452  size_t hash = m_hash(key);
453  unsigned bin = uint32_t(hash) >> BIN_SHIFT;
454  DASSERT(bin < BINS);
455  return bin;
456  }
457 };
458 
459 
void erase(const KEY &key, bool do_lock=true)
iterator & operator=(const iterator &src)
iterator(unordered_map_concurrent *umc=NULL)
GLenum src
Definition: glew.h:2410
bool retrieve(const KEY &key, VALUE &value, bool do_lock=true)
bool empty()
Return true if the entire map is empty.
size_t size()
Return the total number of entries in the map.
uint64 value_type
Definition: GA_PrimCompat.h:29
atomic< int > atomic_int
Definition: atomic.h:51
void unlock()
Unlock the bin we point to, if locked.
Wrappers and utilities for multithreading.
#define DASSERT(x)
Definition: dassert.h:99
bool insert(const KEY &key, const VALUE &value, bool do_lock=true)
iterator begin()
Return an interator pointing to the first entry in the map.
size_t lock_bin(const KEY &key)
GLsizei n
Definition: glew.h:4040
const BinMap_t::value_type * operator->() const
void lock()
Lock the bin we point to, if not already locked.
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
#define DASSERT_MSG
Definition: dassert.h:109
#define OIIO_CACHE_ALIGN
Definition: platform.h:215
const BinMap_t::value_type & operator*() const
iterator find(const KEY &key, bool do_lock=true)
GLuint64EXT * result
Definition: glew.h:14007
bool operator==(const iterator &other) const
#define OIIO_NAMESPACE_END
Definition: oiioversion.h:66
GLsizei const GLfloat * value
Definition: glew.h:1849
#define OIIO_NAMESPACE_BEGIN
Definition: oiioversion.h:65