systemc: use list instead of map in scheduler
authorEarl Ou <shunhsingou@google.com>
Tue, 15 Sep 2020 05:07:25 +0000 (13:07 +0800)
committerEarl Ou <shunhsingou@google.com>
Thu, 17 Sep 2020 02:26:05 +0000 (02:26 +0000)
commit1bca30c95b4c6413203fd54642ccddcff119c0c6
treeabd8bf4a2c0eda98badb659ebc7b8c36b48624cf
parent9a39ac876e376bcb91ed8d4a44f7e81cd15d315a
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 <gabeblack@google.com>
Maintainer: Gabe Black <gabeblack@google.com>
Tested-by: kokoro <noreply+kokoro@google.com>
src/systemc/core/scheduler.cc
src/systemc/core/scheduler.hh