summaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
author couriersud <couriersud@gmx.org>2017-02-22 21:58:07 +0100
committer couriersud <couriersud@gmx.org>2017-02-24 14:49:12 +0100
commitacd0382d902de85397278ee5aa4c753abaf48d3d (patch)
tree97a43a31f632bd5e5f450e2e58e3cea351132ee4
parent1d5539207158cfa3f5449b480b4002e487ee761a (diff)
Added a heap priority queue to the netlist source.
This is currently not used since performance drops by about 40%. The typical use case would be circuits a lot more complex than those we currently emulate where the 2*log(n) advantage really applies. (nw)
-rw-r--r--src/lib/netlist/nl_lists.h126
-rw-r--r--src/lib/netlist/plib/plists.h8
2 files changed, 127 insertions, 7 deletions
diff --git a/src/lib/netlist/nl_lists.h b/src/lib/netlist/nl_lists.h
index a13f14c0da3..618b1b68d92 100644
--- a/src/lib/netlist/nl_lists.h
+++ b/src/lib/netlist/nl_lists.h
@@ -19,11 +19,13 @@
#include <atomic>
#include <thread>
#include <mutex>
+#include <algorithm>
// ----------------------------------------------------------------------------------------
// timed queue
// ----------------------------------------------------------------------------------------
+#define USE_HEAP (0)
namespace netlist
{
@@ -47,6 +49,7 @@ namespace netlist
void unlock() const noexcept { }
};
+#if !USE_HEAP
template <class Element, class Time>
class timed_queue : plib::nocopyassignmove
{
@@ -89,14 +92,13 @@ namespace netlist
clear();
}
- constexpr std::size_t capacity() const noexcept { return m_list.size(); }
+ constexpr std::size_t capacity() const noexcept { return m_list.capacity() - 1; }
constexpr bool empty() const noexcept { return (m_end == &m_list[1]); }
void push(entry_t &&e) noexcept
{
/* Lock */
tqlock lck(m_lock);
-
entry_t * i = m_end;
for (; e.m_exec_time > (i - 1)->m_exec_time; --i)
{
@@ -150,7 +152,6 @@ namespace netlist
constexpr const entry_t *listptr() const { return &m_list[1]; }
constexpr std::size_t size() const noexcept { return static_cast<std::size_t>(m_end - &m_list[1]); }
constexpr const entry_t & operator[](const std::size_t index) const { return m_list[ 1 + index]; }
-
private:
#if HAS_OPENMP && USE_OPENMP
using tqmutex = pspin_mutex<true>;
@@ -167,8 +168,125 @@ namespace netlist
// profiling
nperfcount_t m_prof_sortmove;
nperfcount_t m_prof_call;
-};
+ };
+#else
+ template <class Element, class Time>
+ class timed_queue : plib::nocopyassignmove
+ {
+ public:
+
+ struct entry_t final
+ {
+ constexpr entry_t() noexcept : m_exec_time(), m_object(nullptr) { }
+ constexpr entry_t(const Time &t, const Element &o) noexcept : m_exec_time(t), m_object(o) { }
+ constexpr entry_t(const entry_t &e) noexcept : m_exec_time(e.m_exec_time), m_object(e.m_object) { }
+ entry_t(entry_t &&e) noexcept { swap(e); }
+ ~entry_t() = default;
+
+ entry_t& operator=(entry_t && other) noexcept
+ {
+ swap(other);
+ return *this;
+ }
+
+ entry_t& operator=(const entry_t &other) noexcept
+ {
+ entry_t t(other);
+ swap(t);
+ return *this;
+ }
+
+ void swap(entry_t &other) noexcept
+ {
+ std::swap(m_exec_time, other.m_exec_time);
+ std::swap(m_object, other.m_object);
+ }
+
+ Time m_exec_time;
+ Element m_object;
+ };
+
+ struct compare
+ {
+ bool operator()(const entry_t &a, const entry_t &b) { return a.m_exec_time > b.m_exec_time; }
+ };
+
+ timed_queue(const std::size_t list_size)
+ {
+ m_list.reserve(list_size);
+ clear();
+ }
+
+ constexpr std::size_t capacity() const noexcept { return m_list.capacity(); }
+ constexpr bool empty() const noexcept { return m_list.empty(); }
+
+ void push(entry_t &&e) noexcept
+ {
+ /* Lock */
+ tqlock lck(m_lock);
+ m_list.push_back(e);
+ std::push_heap(m_list.begin(), m_list.end(), compare());
+ m_prof_call.inc();
+ }
+ entry_t pop() noexcept
+ {
+ entry_t t(m_list[0]);
+ std::pop_heap(m_list.begin(), m_list.end(), compare());
+ m_list.pop_back();
+ return t;
+ }
+
+ const entry_t &top() const noexcept { return m_list[0]; }
+
+ void remove(const Element &elem) noexcept
+ {
+ /* Lock */
+ tqlock lck(m_lock);
+ for (entry_t * i = &m_list[m_list.size() - 1]; i >= &m_list[0]; i--)
+ {
+ if (i->m_object == elem)
+ {
+ m_list.erase(m_list.begin() + (i - &m_list[0]));
+ std::make_heap(m_list.begin(), m_list.end(), compare());
+ }
+ }
+ }
+
+ void retime(const Element &elem, const Time t) noexcept
+ {
+ remove(elem);
+ push(entry_t(t, elem));
+ }
+
+ void clear()
+ {
+ tqlock lck(m_lock);
+ m_list.clear();
+ }
+
+ // save state support & mame disasm
+
+ constexpr const entry_t *listptr() const { return &m_list[0]; }
+ constexpr std::size_t size() const noexcept { return m_list.size(); }
+ constexpr const entry_t & operator[](const std::size_t index) const { return m_list[ 0 + index]; }
+ private:
+ #if HAS_OPENMP && USE_OPENMP
+ using tqmutex = pspin_mutex<true>;
+ #else
+ using tqmutex = pspin_mutex<false>;
+ #endif
+ using tqlock = std::lock_guard<tqmutex>;
+
+ tqmutex m_lock;
+ std::vector<entry_t> m_list;
+
+ public:
+ // profiling
+ nperfcount_t m_prof_sortmove;
+ nperfcount_t m_prof_call;
+ };
+#endif
}
#endif /* NLLISTS_H_ */
diff --git a/src/lib/netlist/plib/plists.h b/src/lib/netlist/plib/plists.h
index 72e17b75424..5fefa658b83 100644
--- a/src/lib/netlist/plib/plists.h
+++ b/src/lib/netlist/plib/plists.h
@@ -111,9 +111,11 @@ public:
private:
LC* p;
public:
- explicit constexpr iter_t(LC* x) noexcept : p(x) {}
- explicit constexpr iter_t(const iter_t &rhs) noexcept = default;
- constexpr iter_t(iter_t &&rhs) noexcept = default;
+ explicit constexpr iter_t(LC* x) noexcept : p(x) { }
+ explicit constexpr iter_t(const iter_t &rhs) noexcept : p(rhs.p) { }
+ iter_t(iter_t &&rhs) noexcept { std::swap(*this, rhs); }
+ iter_t& operator=(const iter_t &rhs) { iter_t t(rhs); std::swap(*this, t); return *this; }
+ iter_t& operator=(iter_t &&rhs) { std::swap(*this, rhs); return *this; }
iter_t& operator++() noexcept {p = p->next();return *this;}
iter_t operator++(int) noexcept {iter_t tmp(*this); operator++(); return tmp;}
constexpr bool operator==(const iter_t& rhs) const noexcept {return p == rhs.p;}