Gabe Black has uploaded this change for review. (
https://gem5-review.googlesource.com/5242
Change subject: base: Build caching into the AddrRangeMap class.
......................................................................
base: Build caching into the AddrRangeMap class.
Rather than have each consumer of the AddrRangeMap implement caching lookups
on their own, this change adds a centralized mechanism to the AddrRangeMap
class itself.
Some benefits of this approach are that the cache handles deleted entries
correctly/automatically, the cache is maintained by adding/removing entries
from a linked list rather than moving elements in an array and checking
valid
bits, and it's easy to enable in places which might otherwise not bother
with
caching. The amount of caching is tunable to balance overhead with improved
lookup performance.
This version also fixes a bug found in the existing version and now exposed
by
the AddrRangeMap unit test.
Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
---
M src/base/addr_range_map.hh
1 file changed, 108 insertions(+), 83 deletions(-)
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 30bd624..8811487 100644
--- a/src/base/addr_range_map.hh
+++ b/src/base/addr_range_map.hh
@@ -54,7 +54,7 @@
* address decoding. The value stored is a template type and can be
* e.g. a port identifier, or a pointer.
*/
-template <typename V>
+template <typename V, int max_cache_size=0>
class AddrRangeMap
{
private:
@@ -66,88 +66,6 @@
typedef typename RangeMap::const_iterator const_iterator;
const_iterator
- find(const AddrRange &r) const
- {
- if (tree.empty())
- return tree.end();
-
- const_iterator i = tree.upper_bound(r);
-
- if (i == tree.begin()) {
- if (i->first.intersects(r)) {
- return i;
- } else {
- return tree.end();
- }
- }
-
- --i;
-
- if (i->first.intersects(r))
- return i;
-
- // if we are looking at an interleaved range, also step
- // backwards through the ranges while we are looking at ranges
- // that are part of the same contigous chunk
- if (i->first.interleaved()) {
- AddrRange orig_range = i->first;
-
- while (i != tree.begin() && i->first.mergesWith(orig_range)) {
- --i;
- if (i->first.intersects(r)) {
- return i;
- }
- }
-
- // we could leave the loop based on reaching the first
- // element, so we must still check for an intersection
- if (i->first.intersects(r))
- return i;
- }
-
- return tree.end();
- }
-
- const_iterator
- find(const Addr &r) const
- {
- return find(RangeSize(r, 1));
- }
-
- bool
- intersect(const AddrRange &r) const
- {
- return find(r) != tree.end();
- }
-
- const_iterator
- insert(const AddrRange &r, const V& d)
- {
- if (intersect(r))
- return tree.end();
-
- return tree.insert(std::make_pair(r, d)).first;
- }
-
- void
- erase(iterator p)
- {
- tree.erase(p);
- }
-
- void
- erase(iterator p, iterator q)
- {
- tree.erase(p,q);
- }
-
- void
- clear()
- {
- tree.erase(tree.begin(), tree.end());
- }
-
- const_iterator
begin() const
{
return tree.begin();
@@ -182,6 +100,113 @@
{
return tree.empty();
}
+
+ private:
+ mutable std::list<const_iterator> cache;
+
+ static bool
+ matches(const_iterator i, const AddrRange &r)
+ {
+ return i->first.intersects(r);
+ }
+
+ public:
+ const_iterator
+ find(const AddrRange &r) const
+ {
+ if (max_cache_size != 0 && cache.size() != 0) {
+
+ // If the entry is at the front of the cache, return that.
+ auto c = cache.begin();
+ if (matches(*c, r))
+ return *c;
+
+ // Next, iterate through all the other entries in the cache.
+ for (c++; c != cache.end(); c++) {
+ // If this entry matches, promote it to the front of the
+ // cache and return it.
+ if (matches(*c, r)) {
+ if (max_cache_size > 1)
+ cache.splice(cache.begin(), cache, c);
+ return *c;
+ }
+ }
+ }
+
+ const_iterator next = tree.upper_bound(r);
+ if (next != end() && matches(next, r))
+ return next;
+ if (next == begin())
+ return end();
+ next--;
+
+ const_iterator i;
+ do {
+ i = next;
+ if (matches(i, r)) {
+ if (max_cache_size != 0) {
+ // If there's a cache, add this element to it.
+ if (cache.size() > max_cache_size) {
+ // If the cache is full, move the last element to
the
+ // front and overwrite it with the new value. This
+ // avoids creating or destroying elements of the
list.
+ auto last = cache.end();
+ last--;
+ *last = i;
+ if (max_cache_size > 1)
+ cache.splice(cache.begin(), cache, last);
+ } else {
+ cache.push_front(i);
+ }
+ }
+ return i;
+ }
+ // Keep looking if the next range merges with the current one.
+ } while (next != tree.begin() &&
+ (--next)->first.mergesWith(i->first));
+
+ return tree.end();
+ }
+
+ const_iterator
+ find(const Addr &a) const
+ {
+ return find(RangeSize(a, 1));
+ }
+
+ bool
+ intersect(const AddrRange &r) const
+ {
+ return find(r) != tree.end();
+ }
+
+ const_iterator
+ insert(const AddrRange &r, const V& d)
+ {
+ if (intersect(r))
+ return tree.end();
+
+ return tree.insert(std::make_pair(r, d)).first;
+ }
+
+ void
+ erase(iterator i)
+ {
+ for (auto c = cache.begin(); c != cache.end(); c++) {
+ if (*c == i) {
+ cache.erase(c);
+ break;
+ }
+ }
+ tree.erase(i);
+ }
+
+ void
+ clear()
+ {
+ cache.clear();
+ tree.clear();
+ }
};
#endif //__BASE_ADDR_RANGE_MAP_HH__
--
To view, visit https://gem5-review.googlesource.com/5242
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 1
Gerrit-Owner: Gabe Black <[email protected]>
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
