From: Jeff Preshing Date: Thu, 18 Feb 2016 14:01:51 +0000 (-0500) Subject: Rename SimpleRelaxed to Crude X-Git-Url: http://plrg.eecs.uci.edu/git/?p=junction.git;a=commitdiff_plain;h=624f46ff6ace5dfca5dcfe2606585b3aa68ae28c Rename SimpleRelaxed to Crude --- diff --git a/README.md b/README.md index 5fd67b0..195a747 100644 --- a/README.md +++ b/README.md @@ -1,5 +1,6 @@ -Junction is a library of concurrent data structures in C++. It contains three hash map implementations: +Junction is a library of concurrent data structures in C++. It contains several hash map implementations: + junction::ConcurrentMap_Crude junction::ConcurrentMap_Linear junction::ConcurrentMap_LeapFrog junction::ConcurrentMap_Grampa @@ -98,13 +99,11 @@ The `JUNCTION_USERCONFIG` variable works in a similar way. As an example, take a ## Rules and Behavior -A Junction map is a lot like a big array of `std::atomic<>` variables, where the key is an index into the array, stores use `memory_order_release`, and loads use `memory_order_consume`. +A Junction map is a lot like a big array of `std::atomic<>` variables, where the key is an index into the array. More precisely: -More precisely, the following rules apply to Junction's Linear, LeapFrog and Grampa maps: - -* All of their member functions, together with their `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion. +* All of a Junction map's member functions, together with its `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion. * If an `insert` [happens before](http://preshing.com/20130702/the-happens-before-relation/) a `get` with the same key, the `get` will return the value it inserted, except if another operation changes the value in between. Any [synchronizing operation](http://preshing.com/20130823/the-synchronizes-with-relation/) will establish this relationship. -* `insert` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. +* For Linear, LeapFrog and Grampa maps, `insert` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed. * In the current version, you must not insert while concurrently using an `Iterator`. ## Feedback diff --git a/junction/ConcurrentMap_Crude.h b/junction/ConcurrentMap_Crude.h new file mode 100644 index 0000000..c78e4cf --- /dev/null +++ b/junction/ConcurrentMap_Crude.h @@ -0,0 +1,108 @@ +/*------------------------------------------------------------------------ + Junction: Concurrent data structures in C++ + Copyright (c) 2016 Jeff Preshing + + Distributed under the Simplified BSD License. + Original location: https://github.com/preshing/junction + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the LICENSE file for more information. +------------------------------------------------------------------------*/ + +#ifndef JUNCTION_CONCURRENTMAP_CRUDE_H +#define JUNCTION_CONCURRENTMAP_CRUDE_H + +#include +#include + +namespace junction { + +template , class VT = DefaultValueTraits > +class ConcurrentMap_Crude { +public: + typedef K Key; + typedef V Value; + typedef KT KeyTraits; + typedef VT ValueTraits; + + static const ureg DefaultCapacity = 256; + +private: + struct Cell { + turf::Atomic key; + turf::Atomic value; + }; + + Cell* m_cells; + ureg m_sizeMask; + +public: + ConcurrentMap_Crude(ureg capacity = DefaultCapacity) { + TURF_ASSERT(turf::util::isPowerOf2(capacity)); + m_sizeMask = capacity - 1; + m_cells = new Cell[capacity]; + clear(); + } + + ~ConcurrentMap_Crude() { + delete[] m_cells; + } + + void insert(Key key, Value value) { + TURF_ASSERT(key != KeyTraits::NullKey); + TURF_ASSERT(value != Value(ValueTraits::NullValue)); + + for (ureg idx = KeyTraits::hash(key);; idx++) { + idx &= m_sizeMask; + Cell* cell = m_cells + idx; + + // Load the key that was there. + Key probedKey = cell->key.load(turf::Relaxed); + if (probedKey != key) { + // The cell was either free, or contains another key. + if (probedKey != KeyTraits::NullKey) + continue; // Usually, it contains another key. Keep probing. + + // The cell was free. Now let's try to take it using a CAS. + Key prevKey = cell->key.compareExchange(probedKey, key, turf::Relaxed); + if ((prevKey != KeyTraits::NullKey) && (prevKey != key)) + continue; // Another thread just stole it from underneath us. + + // Either we just added the key, or another thread did. + } + + // Store the value in this cell. + cell->value.store(value, turf::Relaxed); + return; + } + } + + Value get(Key key) { + TURF_ASSERT(key != KeyTraits::NullKey); + + for (ureg idx = KeyTraits::hash(key);; idx++) { + idx &= m_sizeMask; + Cell* cell = m_cells + idx; + + Key probedKey = cell->key.load(turf::Relaxed); + if (probedKey == key) + return cell->value.load(turf::Relaxed); + if (probedKey == KeyTraits::NullKey) + return Value(ValueTraits::NullValue); + } + } + + void clear() { + // Must be called when there are no concurrent readers or writers + for (ureg idx = 0; idx <= m_sizeMask; idx++) { + Cell* cell = m_cells + idx; + cell->key.storeNonatomic(KeyTraits::NullKey); + cell->value.storeNonatomic(Value(ValueTraits::NullValue)); + } + } +}; + +} // namespace junction + +#endif // JUNCTION_CONCURRENTMAP_CRUDE_H diff --git a/junction/ConcurrentMap_SimpleRelaxed.h b/junction/ConcurrentMap_SimpleRelaxed.h deleted file mode 100644 index 269db9a..0000000 --- a/junction/ConcurrentMap_SimpleRelaxed.h +++ /dev/null @@ -1,108 +0,0 @@ -/*------------------------------------------------------------------------ - Junction: Concurrent data structures in C++ - Copyright (c) 2016 Jeff Preshing - - Distributed under the Simplified BSD License. - Original location: https://github.com/preshing/junction - - This software is distributed WITHOUT ANY WARRANTY; without even the - implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. - See the LICENSE file for more information. -------------------------------------------------------------------------*/ - -#ifndef JUNCTION_CONCURRENTMAP_SIMPLERELAXED_H -#define JUNCTION_CONCURRENTMAP_SIMPLERELAXED_H - -#include -#include - -namespace junction { - -template , class VT = DefaultValueTraits > -class ConcurrentMap_SimpleRelaxed { -public: - typedef K Key; - typedef V Value; - typedef KT KeyTraits; - typedef VT ValueTraits; - - static const ureg DefaultCapacity = 256; - -private: - struct Cell { - turf::Atomic key; - turf::Atomic value; - }; - - Cell* m_cells; - ureg m_sizeMask; - -public: - ConcurrentMap_SimpleRelaxed(ureg capacity = DefaultCapacity) { - TURF_ASSERT(turf::util::isPowerOf2(capacity)); - m_sizeMask = capacity - 1; - m_cells = new Cell[capacity]; - clear(); - } - - ~ConcurrentMap_SimpleRelaxed() { - delete[] m_cells; - } - - void insert(Key key, Value value) { - TURF_ASSERT(key != KeyTraits::NullKey); - TURF_ASSERT(value != Value(ValueTraits::NullValue)); - - for (ureg idx = KeyTraits::hash(key);; idx++) { - idx &= m_sizeMask; - Cell* cell = m_cells + idx; - - // Load the key that was there. - Key probedKey = cell->key.load(turf::Relaxed); - if (probedKey != key) { - // The cell was either free, or contains another key. - if (probedKey != KeyTraits::NullKey) - continue; // Usually, it contains another key. Keep probing. - - // The cell was free. Now let's try to take it using a CAS. - Key prevKey = cell->key.compareExchange(probedKey, key, turf::Relaxed); - if ((prevKey != KeyTraits::NullKey) && (prevKey != key)) - continue; // Another thread just stole it from underneath us. - - // Either we just added the key, or another thread did. - } - - // Store the value in this cell. - cell->value.store(value, turf::Relaxed); - return; - } - } - - Value get(Key key) { - TURF_ASSERT(key != KeyTraits::NullKey); - - for (ureg idx = KeyTraits::hash(key);; idx++) { - idx &= m_sizeMask; - Cell* cell = m_cells + idx; - - Key probedKey = cell->key.load(turf::Relaxed); - if (probedKey == key) - return cell->value.load(turf::Relaxed); - if (probedKey == KeyTraits::NullKey) - return Value(ValueTraits::NullValue); - } - } - - void clear() { - // Must be called when there are no concurrent readers or writers - for (ureg idx = 0; idx <= m_sizeMask; idx++) { - Cell* cell = m_cells + idx; - cell->key.storeNonatomic(KeyTraits::NullKey); - cell->value.storeNonatomic(Value(ValueTraits::NullValue)); - } - } -}; - -} // namespace junction - -#endif // JUNCTION_CONCURRENTMAP_SIMPLERELAXED_H diff --git a/junction/extra/impl/MapAdapter_Crude.h b/junction/extra/impl/MapAdapter_Crude.h new file mode 100644 index 0000000..1548ff6 --- /dev/null +++ b/junction/extra/impl/MapAdapter_Crude.h @@ -0,0 +1,55 @@ +/*------------------------------------------------------------------------ + Junction: Concurrent data structures in C++ + Copyright (c) 2016 Jeff Preshing + + Distributed under the Simplified BSD License. + Original location: https://github.com/preshing/junction + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the LICENSE file for more information. +------------------------------------------------------------------------*/ + +#ifndef JUNCTION_EXTRA_IMPL_MAPADAPTER_CRUDE_H +#define JUNCTION_EXTRA_IMPL_MAPADAPTER_CRUDE_H + +#include +#include +#include + +namespace junction { +namespace extra { + +class MapAdapter { +public: + static TURF_CONSTEXPR const char* MapName = "Junction Crude map"; + + MapAdapter(ureg) { + } + + class ThreadContext { + public: + ThreadContext(MapAdapter&, ureg) { + } + + void registerThread() { + } + + void unregisterThread() { + } + + void update() { + } + }; + + typedef ConcurrentMap_Crude Map; + + static ureg getInitialCapacity(ureg maxPopulation) { + return turf::util::roundUpPowerOf2(ureg(maxPopulation * 1.25f)); + } +}; + +} // namespace extra +} // namespace junction + +#endif // JUNCTION_EXTRA_IMPL_MAPADAPTER_CRUDE_H diff --git a/junction/extra/impl/MapAdapter_SimpleRelaxed.h b/junction/extra/impl/MapAdapter_SimpleRelaxed.h deleted file mode 100644 index 88a2e81..0000000 --- a/junction/extra/impl/MapAdapter_SimpleRelaxed.h +++ /dev/null @@ -1,55 +0,0 @@ -/*------------------------------------------------------------------------ - Junction: Concurrent data structures in C++ - Copyright (c) 2016 Jeff Preshing - - Distributed under the Simplified BSD License. - Original location: https://github.com/preshing/junction - - This software is distributed WITHOUT ANY WARRANTY; without even the - implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. - See the LICENSE file for more information. -------------------------------------------------------------------------*/ - -#ifndef JUNCTION_EXTRA_IMPL_MAPADAPTER_SIMPLERELAXED_H -#define JUNCTION_EXTRA_IMPL_MAPADAPTER_SIMPLERELAXED_H - -#include -#include -#include - -namespace junction { -namespace extra { - -class MapAdapter { -public: - static TURF_CONSTEXPR const char* MapName = "Junction SimpleRelaxed map"; - - MapAdapter(ureg) { - } - - class ThreadContext { - public: - ThreadContext(MapAdapter&, ureg) { - } - - void registerThread() { - } - - void unregisterThread() { - } - - void update() { - } - }; - - typedef ConcurrentMap_SimpleRelaxed Map; - - static ureg getInitialCapacity(ureg maxPopulation) { - return turf::util::roundUpPowerOf2(ureg(maxPopulation * 1.25f)); - } -}; - -} // namespace extra -} // namespace junction - -#endif // JUNCTION_EXTRA_IMPL_MAPADAPTER_SIMPLERELAXED_H diff --git a/samples/MapLinearizabilityTest/junction_userconfig.h.in b/samples/MapLinearizabilityTest/junction_userconfig.h.in index 5c9739d..7380013 100644 --- a/samples/MapLinearizabilityTest/junction_userconfig.h.in +++ b/samples/MapLinearizabilityTest/junction_userconfig.h.in @@ -1 +1 @@ -#define JUNCTION_IMPL_MAPADAPTER_PATH "junction/extra/impl/MapAdapter_SimpleRelaxed.h" +#define JUNCTION_IMPL_MAPADAPTER_PATH "junction/extra/impl/MapAdapter_Crude.h"