Earl Ou has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/34515 )
Change subject: systemc: use list instead of map in scheduler
......................................................................
systemc: use list instead of map in scheduler
The queue in systemC scheduler is implemented as a std::map. This provides
the best big-O solution. However, most of simulation usecases has very
small number of pending events. This is expected as we usually only trigger
a
few new events after some events are processed. In such scenario, we
should optimize for insert/erase instead of search. This change use
std::list instead of std::map.
As a proof, we can find that gem5's original event_queue is also
implemented as a list instead of tree.
We see 5% speed improvement with the example provided by Matthias Jung:
https://gist.github.com/myzinsky/557200aa04556de44a317e0a10f51840
Change-Id: I75c30df9134e94df42fd778115cf923488ff5886
---
M src/systemc/core/scheduler.hh
1 file changed, 14 insertions(+), 8 deletions(-)
diff --git a/src/systemc/core/scheduler.hh b/src/systemc/core/scheduler.hh
index c9ca161..c129a35 100644
--- a/src/systemc/core/scheduler.hh
+++ b/src/systemc/core/scheduler.hh
@@ -29,6 +29,7 @@
#define __SYSTEMC_CORE_SCHEDULER_HH__
#include <functional>
+#include <list>
#include <map>
#include <mutex>
#include <set>
@@ -157,7 +158,7 @@
void process();
};
- typedef std::map<Tick, TimeSlot *> TimeSlots;
+ typedef std::list<std::pair<Tick, TimeSlot *>> TimeSlots;
Scheduler();
~Scheduler();
@@ -250,12 +251,14 @@
}
// Timed notification/timeout.
- TimeSlot *&ts = timeSlots[tick];
- if (!ts) {
- ts = new TimeSlot;
- schedule(ts, tick);
+ auto it = timeSlots.begin();
+ while (it != timeSlots.end() && it->first < tick)
+ it++;
+ if (it == timeSlots.end() || it->first != tick) {
+ it = timeSlots.emplace(it, tick, new TimeSlot);
+ schedule(it->second, tick);
}
- event->schedule(ts->events, tick);
+ event->schedule(it->second->events, tick);
}
// For descheduling delayed/timed notifications/timeouts.
@@ -270,8 +273,11 @@
}
// Timed notification/timeout.
- auto tsit = timeSlots.find(event->when());
- panic_if(tsit == timeSlots.end(),
+ auto tsit = timeSlots.begin();
+ while (tsit != timeSlots.end() && tsit->first < event->when())
+ tsit++;
+
+ panic_if(tsit == timeSlots.end() || tsit->first != event->when(),
"Descheduling event at time with no events.");
TimeSlot *ts = tsit->second;
ScEvents &events = ts->events;
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/34515
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: I75c30df9134e94df42fd778115cf923488ff5886
Gerrit-Change-Number: 34515
Gerrit-PatchSet: 1
Gerrit-Owner: Earl Ou <shunhsin...@google.com>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- gem5-dev@gem5.org
To unsubscribe send an email to gem5-dev-le...@gem5.org
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
