Earl Ou has submitted this change. (
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
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/34515
Reviewed-by: Gabe Black
Maintainer: Gabe Black
Tested-by: kokoro
---
M src/systemc/core/scheduler.cc
M src/systemc/core/scheduler.hh
2 files changed, 28 insertions(+), 16 deletions(-)
Approvals:
Gabe Black: Looks good to me, approved; Looks good to me, approved
kokoro: Regressions pass
diff --git a/src/systemc/core/scheduler.cc b/src/systemc/core/scheduler.cc
index 179bd55..50a1e6b 100644
--- a/src/systemc/core/scheduler.cc
+++ b/src/systemc/core/scheduler.cc
@@ -71,8 +71,7 @@
deltas.front()->deschedule();
// Timed notifications.
-for (auto : timeSlots) {
-TimeSlot * = tsp.second;
+for (auto : timeSlots) {
while (!ts->events.empty())
ts->events.front()->deschedule();
deschedule(ts);
diff --git a/src/systemc/core/scheduler.hh b/src/systemc/core/scheduler.hh
index c9ca161..693cb3a 100644
--- a/src/systemc/core/scheduler.hh
+++ b/src/systemc/core/scheduler.hh
@@ -29,6 +29,7 @@
#define __SYSTEMC_CORE_SCHEDULER_HH__
#include
+#include
#include
#include
#include
@@ -151,13 +152,17 @@
class TimeSlot : public ::Event
{
public:
-TimeSlot() : ::Event(Default_Pri, AutoDelete) {}
-
+TimeSlot(const Tick& targeted_when) : ::Event(Default_Pri,
AutoDelete),
+ targeted_when(targeted_when)
{}
+// Event::when() is only set after it's scheduled to an event
queue.
+// However, TimeSlot won't be scheduled before init is done. We
need
+// to keep the real 'targeted_when' information before scheduled.
+Tick targeted_when;
ScEvents events;
void process();
};
-typedef std::map TimeSlots;
+typedef std::list TimeSlots;
Scheduler();
~Scheduler();
@@ -250,12 +255,14 @@
}
// Timed notification/timeout.
-TimeSlot * = timeSlots[tick];
-if (!ts) {
-ts = new TimeSlot;
-schedule(ts, tick);
+auto it = timeSlots.begin();
+while (it != timeSlots.end() && (*it)->targeted_when < tick)
+it++;
+if (it == timeSlots.end() || (*it)->targeted_when != tick) {
+it = timeSlots.emplace(it, new TimeSlot(tick));
+schedule(*it, tick);
}
-event->schedule(ts->events, tick);
+event->schedule((*it)->events, tick);
}
// For descheduling delayed/timed notifications/timeouts.
@@ -270,10 +277,15 @@
}
// Timed notification/timeout.
-auto tsit = timeSlots.find(event->when());
-panic_if(tsit == timeSlots.end(),
+auto tsit = timeSlots.begin();
+while (tsit != timeSlots.end() &&
+ (*tsit)->targeted_when < event->when())
+tsit++;
+
+panic_if(tsit == timeSlots.end() ||
+ (*tsit)->targeted_when != event->when(),
"Descheduling event at time with no events.");
-TimeSlot *ts = tsit->second;
+TimeSlot *ts = *tsit;
ScEvents = ts->events;
assert(on == );
event->deschedule();
@@ -288,7 +300,7 @@
void
completeTimeSlot(TimeSlot *ts)
{
-assert(ts == timeSlots.begin()->second);
+assert(ts == timeSlots.front());
timeSlots.erase(timeSlots.begin());
if (!runToTime && starved())
scheduleStarvationEvent();
@@ -324,7 +336,7 @@
if (pendingCurr())
return 0;
if (pendingFuture())
-return timeSlots.begin()->first - getCurTick();
+return timeSlots.front()->targeted_when - getCurTick();
return MaxTick - getCurTick();
}
@@ -434,7 +446,8 @@
{
return (readyListMethods.empty() && readyListThreads.empty() &&
updateList.empty() && deltas.empty() &&
-(timeSlots.empty() || timeSlots.begin()->first > maxTick)
&&
+(timeSlots.empty()
