summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/netlist/nl_lists.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/netlist/nl_lists.h')
-rw-r--r--src/lib/netlist/nl_lists.h163
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_ */