Discussion:
[gem5-dev] Change in public/gem5[master]: base: Build caching into the AddrRangeMap class.
(too old to reply)
Gabe Black (Gerrit)
2017-10-19 04:23:10 UTC
Permalink
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 <***@google.com>
Gabe Black (Gerrit)
2017-10-24 04:03:50 UTC
Permalink
Gabe Black has uploaded a new patch set (#2). (
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, 116 insertions(+), 83 deletions(-)
--
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: newpatchset
Gerrit-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 2
Gerrit-Owner: Gabe Black <***@google.com>
Gerrit-Assignee: Andreas Hansson <***@arm.com>
Gerrit-Reviewer: Gabe Black <***@google.com>
Gerrit-CC: Andreas Hansson <***@arm.com>
Gerrit-CC: Nikos Nikoleris <***@arm.com>
Gabe Black (Gerrit)
2017-10-24 04:20:36 UTC
Permalink
Gabe Black has uploaded a new patch set (#3). (
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, 115 insertions(+), 83 deletions(-)
--
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: newpatchset
Gerrit-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 3
Gerrit-Owner: Gabe Black <***@google.com>
Gerrit-Assignee: Andreas Hansson <***@arm.com>
Gerrit-Reviewer: Gabe Black <***@google.com>
Gerrit-CC: Andreas Hansson <***@arm.com>
Gerrit-CC: Nikos Nikoleris <***@arm.com>
Nikos Nikoleris (Gerrit)
2018-06-13 14:50:18 UTC
Permalink
Nikos Nikoleris has uploaded a new patch set (#4) to the change originally
created by Gabe Black. ( 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.

Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
---
M src/base/addr_range_map.hh
1 file changed, 53 insertions(+), 1 deletion(-)
--
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-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 4
Gerrit-Owner: Gabe Black <***@google.com>
Gerrit-Assignee: Andreas Hansson <***@arm.com>
Gerrit-Reviewer: Gabe Black <***@google.com>
Gerrit-CC: Andreas Hansson <***@arm.com>
Gerrit-CC: Nikos Nikoleris <***@arm.com>
Gerrit-MessageType: newpatchset
Nikos Nikoleris (Gerrit)
2018-06-14 15:43:06 UTC
Permalink
Nikos Nikoleris has uploaded a new patch set (#5) to the change originally
created by Gabe Black. ( 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.

Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
---
M src/base/addr_range_map.hh
1 file changed, 52 insertions(+), 1 deletion(-)
--
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-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 5
Gerrit-Owner: Gabe Black <***@google.com>
Gerrit-Assignee: Andreas Hansson <***@arm.com>
Gerrit-Reviewer: Gabe Black <***@google.com>
Gerrit-CC: Andreas Hansson <***@arm.com>
Gerrit-CC: Nikos Nikoleris <***@arm.com>
Gerrit-MessageType: newpatchset
Nikos Nikoleris (Gerrit)
2018-06-14 16:44:02 UTC
Permalink
Nikos Nikoleris has uploaded a new patch set (#6) to the change originally
created by Gabe Black. ( 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.

Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
---
M src/base/addr_range_map.hh
1 file changed, 52 insertions(+), 1 deletion(-)
--
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-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 6
Gerrit-Owner: Gabe Black <***@google.com>
Gerrit-Assignee: Andreas Hansson <***@arm.com>
Gerrit-Reviewer: Gabe Black <***@google.com>
Gerrit-CC: Andreas Hansson <***@arm.com>
Gerrit-CC: Daniel Carvalho <***@yahoo.com.br>
Gerrit-CC: Nikos Nikoleris <***@arm.com>
Gerrit-MessageType: newpatchset
Nikos Nikoleris (Gerrit)
2018-06-19 14:24:28 UTC
Permalink
Nikos Nikoleris has submitted this change and it was merged. (
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.

Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Reviewed-on: https://gem5-review.googlesource.com/5242
Reviewed-by: Daniel Carvalho <***@yahoo.com.br>
Reviewed-by: Jason Lowe-Power <***@lowepower.com>
Maintainer: Nikos Nikoleris <***@arm.com>
---
M src/base/addr_range_map.hh
1 file changed, 52 insertions(+), 1 deletion(-)

Approvals:
Jason Lowe-Power: Looks good to me, approved
Daniel Carvalho: Looks good to me, approved
Nikos Nikoleris: Looks good to me, approved



diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 5c627be..417d663 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:
@@ -124,18 +124,23 @@
void
erase(iterator p)
{
+ cache.remove(p);
tree.erase(p);
}

void
erase(iterator p, iterator q)
{
+ for (auto it = p; it != q; it++) {
+ cache.remove(p);
+ }
tree.erase(p,q);
}

void
clear()
{
+ cache.erase(cache.begin(), cache.end());
tree.erase(tree.begin(), tree.end());
}

@@ -177,6 +182,31 @@

private:
/**
+ * Add an address range map entry to the cache.
+ *
+ * @param it Iterator to the entry in the address range map
+ */
+ void
+ addNewEntryToCache(const_iterator it) const
+ {
+ 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 = it;
+ if (max_cache_size > 1)
+ cache.splice(cache.begin(), cache, last);
+ } else {
+ cache.push_front(it);
+ }
+ }
+ }
+
+ /**
* Find entry that satisfies a condition on an address range
*
* Searches through the ranges in the address map and returns an
@@ -190,8 +220,20 @@
const_iterator
find(const AddrRange &r, std::function<bool(const AddrRange)> cond)
const
{
+ // Check the cache first
+ for (auto c = cache.begin(); c != cache.end(); c++) {
+ auto it = *c;
+ if (cond(it->first)) {
+ // If this entry matches, promote it to the front
+ // of the cache and return it.
+ cache.splice(cache.begin(), cache, c);
+ return it;
+ }
+ }
+
const_iterator next = tree.upper_bound(r);
if (next != end() && cond(next->first)) {
+ addNewEntryToCache(next);
return next;
}
if (next == begin())
@@ -202,6 +244,7 @@
do {
i = next;
if (cond(i->first)) {
+ addNewEntryToCache(i);
return i;
}
// Keep looking if the next range merges with the current one.
@@ -212,6 +255,14 @@
}

RangeMap tree;
+
+ /**
+ * A list of iterator that correspond to the max_cache_size most
+ * recently used entries in the address range map. This mainly
+ * used to optimize lookups. The elements in the list should
+ * always be valid iterators of the tree.
+ */
+ mutable std::list<const_iterator> cache;
};

#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-Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Gerrit-Change-Number: 5242
Gerrit-PatchSet: 8
Gerrit-Owner: Gabe Black <***@google.com>
Gerrit-Assignee: Andreas Hansson <***@arm.com>
Gerrit-Reviewer: Daniel Carvalho <***@yahoo.com.br>
Gerrit-Reviewer: Gabe Black <***@google.com>
Gerrit-Reviewer: Jason Lowe-Power <***@lowepower.com>
Gerrit-Reviewer: Nikos Nikoleris <***@arm.com>
Gerrit-CC: Andreas Hansson <***@arm.com>
Gerrit-MessageType: merged
Continue reading on narkive:
Loading...