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 <gabebl...@google.com>
Maintainer: Gabe Black <gabebl...@google.com>
Tested-by: kokoro <noreply+kok...@google.com>
---
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 &tsp: timeSlots) {
- TimeSlot *&ts = tsp.second;
+ for (auto &ts: 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 <functional>
+#include <list>
#include <map>
#include <mutex>
#include <set>
@@ -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<Tick, TimeSlot *> TimeSlots;
+ typedef std::list<TimeSlot *> TimeSlots;
Scheduler();
~Scheduler();
@@ -250,12 +255,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)->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 &events = ts->events;
assert(on == &events);
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() ||
+ timeSlots.front()->targeted_when > maxTick) &&
initList.empty());
}
EventWrapper<Scheduler, &Scheduler::pause> starvationEvent;
--
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: 8
Gerrit-Owner: Earl Ou <shunhsin...@google.com>
Gerrit-Reviewer: Earl Ou <shunhsin...@google.com>
Gerrit-Reviewer: Gabe Black <gabebl...@google.com>
Gerrit-Reviewer: Yu-hsin Wang <yuhsi...@google.com>
Gerrit-Reviewer: kokoro <noreply+kok...@google.com>
Gerrit-CC: Jui-min Lee <f...@google.com>
Gerrit-MessageType: merged
_______________________________________________
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
