diff options
Diffstat (limited to 'src/lib/netlist/nl_lists.h')
-rw-r--r-- | src/lib/netlist/nl_lists.h | 163 |
1 files changed, 89 insertions, 74 deletions
diff --git a/src/lib/netlist/nl_lists.h b/src/lib/netlist/nl_lists.h index 1eae38b25fb..325f8a67c72 100644 --- a/src/lib/netlist/nl_lists.h +++ b/src/lib/netlist/nl_lists.h @@ -10,32 +10,24 @@ #ifndef NLLISTS_H_ #define NLLISTS_H_ -#include "nl_config.h" -#include "netlist_types.h" -#include "plib/plists.h" #include "plib/pchrono.h" +#include "plib/plists.h" #include "plib/ptypes.h" +#include "nl_config.h" +#include "nltypes.h" + +#include <algorithm> #include <atomic> -#include <thread> #include <mutex> -#include <algorithm> +#include <thread> #include <utility> + // ---------------------------------------------------------------------------------------- // timed queue // ---------------------------------------------------------------------------------------- -/* - * Use -DUSE_HEAP=1 to use stdc++ heap functions instead of linear processing. - * - * This slows down processing by about 25% on a Kaby Lake. - */ - -#ifndef USE_HEAP -#define USE_HEAP (0) -#endif - namespace netlist { //FIXME: move to an appropriate place @@ -43,10 +35,11 @@ namespace netlist class pspin_mutex { public: - pspin_mutex() noexcept { } + pspin_mutex() noexcept = default; void lock() noexcept{ while (m_lock.test_and_set(std::memory_order_acquire)) { } } void unlock() noexcept { m_lock.clear(std::memory_order_release); } private: + PALIGNAS_CACHELINE() std::atomic_flag m_lock = ATOMIC_FLAG_INIT; }; @@ -62,10 +55,11 @@ namespace netlist struct pqentry_t final { constexpr pqentry_t() noexcept : m_exec_time(), m_object(nullptr) { } - constexpr pqentry_t(const Time &t, const Element &o) noexcept : m_exec_time(t), m_object(o) { } + constexpr pqentry_t(const Time t, const Element o) noexcept : m_exec_time(t), m_object(o) { } +#if 0 ~pqentry_t() = default; constexpr pqentry_t(const pqentry_t &e) noexcept = default; - constexpr pqentry_t(pqentry_t &&e) = default; + constexpr pqentry_t(pqentry_t &&e) noexcept = default; pqentry_t& operator=(pqentry_t && other) noexcept = default; pqentry_t& operator=(const pqentry_t &other) noexcept = default; @@ -74,91 +68,97 @@ namespace netlist std::swap(m_exec_time, other.m_exec_time); std::swap(m_object, other.m_object); } - +#endif struct QueueOp { - static constexpr bool less(const pqentry_t &lhs, const pqentry_t &rhs) noexcept + inline static constexpr bool less(const pqentry_t &lhs, const pqentry_t &rhs) noexcept { return (lhs.m_exec_time < rhs.m_exec_time); } - static constexpr bool equal(const pqentry_t &lhs, const pqentry_t &rhs) noexcept + inline static constexpr bool lessequal(const pqentry_t &lhs, const pqentry_t &rhs) noexcept + { + return (lhs.m_exec_time <= rhs.m_exec_time); + } + + inline static constexpr bool equal(const pqentry_t &lhs, const pqentry_t &rhs) noexcept { return lhs.m_object == rhs.m_object; } - static constexpr bool equal(const pqentry_t &lhs, const Element &rhs) noexcept + inline static constexpr bool equal(const pqentry_t &lhs, const Element &rhs) noexcept { return lhs.m_object == rhs; } - static constexpr pqentry_t never() noexcept { return pqentry_t(Time::never(), nullptr); } + inline static constexpr pqentry_t never() noexcept { return pqentry_t(Time::never(), nullptr); } }; Time m_exec_time; Element m_object; }; -#if !USE_HEAP /* Use TS = true for a threadsafe queue */ - template <class T, bool TS, class QueueOp = typename T::QueueOp> - class timed_queue : plib::nocopyassignmove + template <class T, bool TS, bool KEEPSTAT, class QueueOp = typename T::QueueOp> + class timed_queue_linear : plib::nocopyassignmove { public: - explicit timed_queue(const std::size_t list_size) + explicit timed_queue_linear(const std::size_t list_size) : m_list(list_size) { clear(); } - constexpr std::size_t capacity() const noexcept { return m_list.capacity() - 1; } - constexpr bool empty() const noexcept { return (m_end == &m_list[1]); } + std::size_t capacity() const noexcept { return m_list.capacity() - 1; } + bool empty() const noexcept { return (m_end == &m_list[1]); } - void push(T &&e) noexcept + void push(T && e) noexcept { /* Lock */ - tqlock lck(m_lock); - T * i(m_end); - for (; QueueOp::less(*(i - 1), e); --i) + lock_guard_type lck(m_lock); + T * i(m_end-1); + for (; QueueOp::less(*(i), e); --i) { - *(i) = std::move(*(i-1)); + *(i+1) = *(i); m_prof_sortmove.inc(); } - *i = std::move(e); + *(i+1) = std::move(e); ++m_end; m_prof_call.inc(); } - void pop() noexcept { --m_end; } + T pop() noexcept { return *(--m_end); } const T &top() const noexcept { return *(m_end-1); } template <class R> void remove(const R &elem) noexcept { /* Lock */ - tqlock lck(m_lock); + lock_guard_type lck(m_lock); + m_prof_remove.inc(); + for (T * i = m_end - 1; i > &m_list[0]; --i) { if (QueueOp::equal(*i, elem)) { - --m_end; - for (;i < m_end; ++i) - *i = std::move(*(i+1)); + std::copy(i+1, m_end--, i); return; } } } - void retime(const T &elem) noexcept + void retime(T && elem) noexcept { /* Lock */ - tqlock lck(m_lock); + lock_guard_type lck(m_lock); + m_prof_retime.inc(); + for (T * i = m_end - 1; i > &m_list[0]; --i) { if (QueueOp::equal(*i, elem)) // partial equal! { - *i = elem; + *i = std::move(elem); while (QueueOp::less(*(i-1), *i)) { std::swap(*(i-1), *i); @@ -174,9 +174,9 @@ namespace netlist } } - void clear() + void clear() noexcept { - tqlock lck(m_lock); + lock_guard_type lck(m_lock); m_end = &m_list[0]; /* put an empty element with maximum time into the queue. * the insert algo above will run into this element and doesn't @@ -188,55 +188,61 @@ namespace netlist // save state support & mame disasm - constexpr const T *listptr() const noexcept { return &m_list[1]; } - constexpr std::size_t size() const noexcept { return static_cast<std::size_t>(m_end - &m_list[1]); } - constexpr const T & operator[](const std::size_t index) const noexcept { return m_list[ 1 + index]; } + const T *listptr() const noexcept { return &m_list[1]; } + std::size_t size() const noexcept { return static_cast<std::size_t>(m_end - &m_list[1]); } + const T & operator[](const std::size_t index) const noexcept { return m_list[ 1 + index]; } private: - using tqmutex = pspin_mutex<TS>; - using tqlock = std::lock_guard<tqmutex>; + using mutex_type = pspin_mutex<TS>; + using lock_guard_type = std::lock_guard<mutex_type>; - tqmutex m_lock; - T * m_end; - std::vector<T> m_list; + mutex_type m_lock; + PALIGNAS_CACHELINE() + T * m_end; + //std::vector<T> m_list; + plib::aligned_vector<T> m_list; public: // profiling - nperfcount_t m_prof_sortmove; - nperfcount_t m_prof_call; + nperfcount_t<KEEPSTAT> m_prof_sortmove; + nperfcount_t<KEEPSTAT> m_prof_call; + nperfcount_t<KEEPSTAT> m_prof_remove; + nperfcount_t<KEEPSTAT> m_prof_retime; }; -#else - template <class T, bool TS, class QueueOp = typename T::QueueOp> - class timed_queue : plib::nocopyassignmove + + template <class T, bool TS, bool KEEPSTAT, class QueueOp = typename T::QueueOp> + class timed_queue_heap : plib::nocopyassignmove { public: struct compare { - constexpr bool operator()(const T &a, const T &b) const { return QueueOp::less(b,a); } + constexpr bool operator()(const T &a, const T &b) const { return QueueOp::lessequal(b,a); } }; - explicit timed_queue(const std::size_t list_size) + explicit timed_queue_heap(const std::size_t list_size) : m_list(list_size) { clear(); } - constexpr std::size_t capacity() const noexcept { return m_list.capacity(); } - constexpr bool empty() const noexcept { return &m_list[0] == m_end; } + std::size_t capacity() const noexcept { return m_list.capacity(); } + bool empty() const noexcept { return &m_list[0] == m_end; } void push(T &&e) noexcept { /* Lock */ - tqlock lck(m_lock); + lock_guard_type lck(m_lock); *m_end++ = e; std::push_heap(&m_list[0], m_end, compare()); m_prof_call.inc(); } - void pop() noexcept + T pop() noexcept { + T ret(m_list[0]); std::pop_heap(&m_list[0], m_end, compare()); m_end--; + return ret; } const T &top() const noexcept { return m_list[0]; } @@ -245,7 +251,7 @@ namespace netlist void remove(const R &elem) noexcept { /* Lock */ - tqlock lck(m_lock); + lock_guard_type lck(m_lock); for (T * i = m_end - 1; i >= &m_list[0]; i--) { if (QueueOp::equal(*i, elem)) @@ -262,7 +268,7 @@ namespace netlist void retime(const T &elem) noexcept { /* Lock */ - tqlock lck(m_lock); + lock_guard_type lck(m_lock); for (T * i = m_end - 1; i >= &m_list[0]; i--) { if (QueueOp::equal(*i, elem)) // partial equal! @@ -276,7 +282,7 @@ namespace netlist void clear() { - tqlock lck(m_lock); + lock_guard_type lck(m_lock); m_list.clear(); m_end = &m_list[0]; } @@ -287,19 +293,28 @@ namespace netlist constexpr std::size_t size() const noexcept { return m_list.size(); } constexpr const T & operator[](const std::size_t index) const { return m_list[ 0 + index]; } private: - using tqmutex = pspin_mutex<TS>; - using tqlock = std::lock_guard<tqmutex>; + using mutex_type = pspin_mutex<TS>; + using lock_guard_type = std::lock_guard<mutex_type>; - tqmutex m_lock; + mutex_type m_lock; std::vector<T> m_list; T *m_end; public: // profiling - nperfcount_t m_prof_sortmove; - nperfcount_t m_prof_call; + nperfcount_t<KEEPSTAT> m_prof_sortmove; + nperfcount_t<KEEPSTAT> m_prof_call; }; -#endif -} + + /* + * Use timed_queue_heap to use stdc++ heap functions instead of linear processing. + * + * This slows down processing by about 25% on a Kaby Lake. + */ + + template <class T, bool TS, bool KEEPSTAT, class QueueOp = typename T::QueueOp> + using timed_queue = timed_queue_linear<T, TS, KEEPSTAT, QueueOp>; + +} // namespace netlist #endif /* NLLISTS_H_ */ |