i#2006 generalize drcachesim: add the reuse-distance tool

Commit log for first patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: 78851 total accesses
Cache Reuse Distance: 2254 unique cache lines accessed
Cache Reuse Distance: reuse distance threshold = 256 cache lines
Cache Reuse Distance: top interested 10 cache lines
        cache line:       #accesses      #accesses 
                        (< threshold)  (>= threshold)
    0x7f1a055c0780:          250,            6
    0x7f1a055d11c0:          373,            5
    0x7f1a055d1180:          332,            5
    0x7f1a04798480:           21,            5
    0x7f1a057e3a40:           43,            4
    0x7f1a04798940:           43,            4
    0x7f1a057e4a40:           42,            4
    0x7f1a055c07c0:           40,            4
    0x7f1a057e2e80:           37,            4
    0x7f1a057e4580:           27,            4


---------------

[zhaoqin, 2016-10-18 02:37:43]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Result example:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78851
Cache Reuse Distance: last level cache = 131072 cache lines
Cache Reuse Distance: last level cache = 2253 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7fcc58a16400:        11933,            1
    0x7fcc58a23c00:        10548,            1
    0x7fcc58a14880:         6639,            1
    0x7fcc58a14840:         4721,            1
    0x7fcc58a163c0:         3613,            1
    0x7fcc58a13fc0:         2743,            1
    0x7fcc58a13f80:         2417,            1
    0x7fcc58a24940:         2204,            1
    0x7ffe6b349180:         2030,            1
    0x7fcc58a14780:         1813,            1

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-10-18 02:38:47]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78851
Cache Reuse Distance: last level cache = 131072 cache lines
Cache Reuse Distance: last level cache = 2253 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7fcc58a16400:        11933,            1
    0x7fcc58a23c00:        10548,            1
    0x7fcc58a14880:         6639,            1
    0x7fcc58a14840:         4721,            1
    0x7fcc58a163c0:         3613,            1
    0x7fcc58a13fc0:         2743,            1
    0x7fcc58a13f80:         2417,            1
    0x7fcc58a24940:         2204,            1
    0x7ffe6b349180:         2030,            1
    0x7fcc58a14780:         1813,            1

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-10-18 02:44:26]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78880
Cache Reuse Distance: last level cache = 256 cache lines
Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7f79e5d3d780:          250,            7
    0x7f79e5d4e1c0:          373,            6
    0x7f79e5d4e180:          332,            6
    0x7f79e4f15480:           21,            6
    0x7f79e5f60a40:           43,            5
    0x7f79e4f15940:           43,            5
    0x7f79e5f61a40:           42,            5
    0x7f79e5d3d7c0:           40,            5
    0x7f79e5f5fe80:           37,            5
    0x7f79e5f61580:           27,            5

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-10-18 15:13:15]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78880
Cache Reuse Distance: last level cache = 256 cache lines
Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7f79e5d3d780:          250,            7
    0x7f79e5d4e1c0:          373,            6
    0x7f79e5d4e180:          332,            6
    0x7f79e4f15480:           21,            6
    0x7f79e5f60a40:           43,            5
    0x7f79e4f15940:           43,            5
    0x7f79e5f61a40:           42,            5
    0x7f79e5d3d7c0:           40,            5
    0x7f79e5f5fe80:           37,            5
    0x7f79e5f61580:           27,            5

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-10-18 15:17:01]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78880
Cache Reuse Distance: last level cache = 256 cache lines
Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7f79e5d3d780:          250,            7
    0x7f79e5d4e1c0:          373,            6
    0x7f79e5d4e180:          332,            6
    0x7f79e4f15480:           21,            6
    0x7f79e5f60a40:           43,            5
    0x7f79e4f15940:           43,            5
    0x7f79e5f61a40:           42,            5
    0x7f79e5d3d7c0:           40,            5
    0x7f79e5f5fe80:           37,            5
    0x7f79e5f61580:           27,            5

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-10-18 15:45:48]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78880
Cache Reuse Distance: last level cache = 256 cache lines
Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7f79e5d3d780:          250,            7
    0x7f79e5d4e1c0:          373,            6
    0x7f79e5d4e180:          332,            6
    0x7f79e4f15480:           21,            6
    0x7f79e5f60a40:           43,            5
    0x7f79e4f15940:           43,            5
    0x7f79e5f61a40:           42,            5
    0x7f79e5d3d7c0:           40,            5
    0x7f79e5f5fe80:           37,            5
    0x7f79e5f61580:           27,            5

Review-URL: https://codereview.appspot.com/312880043
---------------

[bruening, 2016-10-18 15:46:53]

Woah, are you sure this is ready for review?  I see 7 patchsets (!) already.

[zhaoqin, 2016-10-18 16:01:21]

On 2016/10/18 15:46:53, bruening wrote:
> Woah, are you sure this is ready for review?  I see 7 patchsets (!) already.

most are minor update like comment or commit message updates.
There are one or two that I changed my mind on how to do it.
And one is bug fixing.

Just cannot stop thinking it, and keep having different thought about code.

[bruening, 2016-10-19 21:38:50]

On 2016/10/18 15:45:48, zhaoqin wrote:
> Example result:
> Hello, world!
> ---- <application exited with code 0> ----
> Cache Reuse Distance result:
> Cache Reuse Distance: total accesses: 78880
> Cache Reuse Distance: last level cache = 256 cache lines
> Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
> Cache Reuse Distance: last level cache top 10
>         cache line:         hits,       misses
>     0x7f79e5d3d780:          250,            7
>     0x7f79e5d4e1c0:          373,            6
>     0x7f79e5d4e180:          332,            6
>     0x7f79e4f15480:           21,            6
>     0x7f79e5f60a40:           43,            5
>     0x7f79e4f15940:           43,            5
>     0x7f79e5f61a40:           42,            5
>     0x7f79e5d3d7c0:           40,            5
>     0x7f79e5f5fe80:           37,            5
>     0x7f79e5f61580:           27,            5

I'm confused: where is the reuse distance?  I see hits and misses.

[zhaoqin, 2016-10-20 01:04:50]

On 2016/10/19 21:38:50, bruening wrote:
> On 2016/10/18 15:45:48, zhaoqin wrote:
> > Example result:
> > Hello, world!
> > ---- <application exited with code 0> ----
> > Cache Reuse Distance result:
> > Cache Reuse Distance: total accesses: 78880
> > Cache Reuse Distance: last level cache = 256 cache lines
> > Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
> > Cache Reuse Distance: last level cache top 10
> >         cache line:         hits,       misses
> >     0x7f79e5d3d780:          250,            7
> >     0x7f79e5d4e1c0:          373,            6
> >     0x7f79e5d4e180:          332,            6
> >     0x7f79e4f15480:           21,            6
> >     0x7f79e5f60a40:           43,            5
> >     0x7f79e4f15940:           43,            5
> >     0x7f79e5f61a40:           42,            5
> >     0x7f79e5d3d7c0:           40,            5
> >     0x7f79e5f5fe80:           37,            5
> >     0x7f79e5f61580:           27,            5
> 
> I'm confused: where is the reuse distance?  I see hits and misses.

it just report hit if the reuse distance is smaller than a threshold (which is
set by LL_size).
The reuse distance info is maintained, but it require extra traverse the double
linked list to report.
but checking the threshold is cheaper. So I report how many times the reuse
distance exceed the threshold (miss) or below the threshold (hit)

[bruening, 2016-10-20 02:41:44]

On 2016/10/20 01:04:50, zhaoqin wrote:
> On 2016/10/19 21:38:50, bruening wrote:
> > On 2016/10/18 15:45:48, zhaoqin wrote:
> > > Example result:
> > > Hello, world!
> > > ---- <application exited with code 0> ----
> > > Cache Reuse Distance result:
> > > Cache Reuse Distance: total accesses: 78880
> > > Cache Reuse Distance: last level cache = 256 cache lines
> > > Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
> > > Cache Reuse Distance: last level cache top 10
> > >         cache line:         hits,       misses
> > >     0x7f79e5d3d780:          250,            7
> > >     0x7f79e5d4e1c0:          373,            6
> > >     0x7f79e5d4e180:          332,            6
> > >     0x7f79e4f15480:           21,            6
> > >     0x7f79e5f60a40:           43,            5
> > >     0x7f79e4f15940:           43,            5
> > >     0x7f79e5f61a40:           42,            5
> > >     0x7f79e5d3d7c0:           40,            5
> > >     0x7f79e5f5fe80:           37,            5
> > >     0x7f79e5f61580:           27,            5
> > 
> > I'm confused: where is the reuse distance?  I see hits and misses.
> 
> it just report hit if the reuse distance is smaller than a threshold (which is
> set by LL_size).
> The reuse distance info is maintained, but it require extra traverse the
double
> linked list to report.
> but checking the threshold is cheaper. So I report how many times the reuse
> distance exceed the threshold (miss) or below the threshold (hit)

The output needs to explain that.  I don't see how someone could figure out what
this current output is showing.  There is no mention of a threshold.

[zhaoqin, 2016-10-20 20:56:58]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: total accesses: 78880
Cache Reuse Distance: last level cache = 256 cache lines
Cache Reuse Distance: last level cache = 2257 unique cache lines accessed
Cache Reuse Distance: last level cache top 10
        cache line:         hits,       misses
    0x7f79e5d3d780:          250,            7
    0x7f79e5d4e1c0:          373,            6
    0x7f79e5d4e180:          332,            6
    0x7f79e4f15480:           21,            6
    0x7f79e5f60a40:           43,            5
    0x7f79e4f15940:           43,            5
    0x7f79e5f61a40:           42,            5
    0x7f79e5d3d7c0:           40,            5
    0x7f79e5f5fe80:           37,            5
    0x7f79e5f61580:           27,            5

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-10-20 20:58:59]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
Cache Reuse Distance: 78851 total accesses
Cache Reuse Distance: 2254 unique cache lines accessed
Cache Reuse Distance: reuse distance threshold = 256 cache lines
Cache Reuse Distance: top interested 10 cache lines
        cache line:       #accesses      #accesses
                        (< threshold)  (>= threshold)
    0x7f1a055c0780:          250,            6
    0x7f1a055d11c0:          373,            5
    0x7f1a055d1180:          332,            5
    0x7f1a04798480:           21,            5
    0x7f1a057e3a40:           43,            4
    0x7f1a04798940:           43,            4
    0x7f1a057e4a40:           42,            4
    0x7f1a055c07c0:           40,            4
    0x7f1a057e2e80:           37,            4
    0x7f1a057e4580:           27,            4

Review-URL: https://codereview.appspot.com/312880043
---------------

[bruening, 2016-10-27 04:25:27]

There are a surprising number of code style violations so maybe another look is
best.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tests...
File clients/drcachesim/tests/reuse_distance.templatex (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tests...
clients/drcachesim/tests/reuse_distance.templatex:4: Cache Reuse Distance:
[0-9]+ total accesses
If the idea is to distinguish from app output would something with the pid in it
work better, like the typical Valgrind or Dr. Memory prefixes?  We may not need
a refix on every line, if this is *after* the app exited and thus will not
interleave with app output?

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tests...
clients/drcachesim/tests/reuse_distance.templatex:7: Cache Reuse Distance: top
interested 10 cache lines
"interested" is ungrammatical here.  "interesting" maybe -- but this is
quantitative, not qualitative, so don't you mean the 10 cache lines that crossed
the threshold the most often?  Maybe "top 10 cache lines sorted by count of
threshold crossings" -- hmm not sure how to make it concise.

Also in the commit msg

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.cpp (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.cpp:110: std::cerr << TOOL_NAME << ":
reuse distance threshold = "
Should the threshold just be called a threshold and not a cache size, in the
runtime options?  It seems confusing to conflate the two.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.h (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:44: /* A double linked list for cache
line reference info */
How about using std::list since this is C++ code?

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:44: /* A double linked list for cache
line reference info */
"doubly linked list"

Also multiple places below

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:47: struct line_ref_t* prev;
style: DR style has the * on the var name, not the type name.

Also in a lot of places below.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:57: // The top N nodes are cache lines
in the cache.
You mean the *first* N in the list

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:59: // a reference reuse distance is
within the top N or not in constant time.
This N is unrelated to the N above so maybe use different names

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:71: cache_lines = lines;
Why not in the constructor list

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:74: virtual ~line_ref_list_t()
style: type on own line

Also 3 times below

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:75: {
I guess we have no style for how big of an impl should be in a header file (b/c
our style guide is for C) but for the most part all our implementations are in
.cpp files, right?  Only droption is in a header and it has to be.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:88: if (victim == NULL ||
ref->time_stamp > victim->time_stamp)
OK, I had to read the code below to figure out what is going on: victim is
pointing at the next LRU line to go, which is M lines from the from of the list,
and its time stamp is guaranteed to be the lowest of those M.  A few well-placed
comments up above and again here would make this clearer and avoid the reader
having to read through all the code and infer the invariants.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:102: // move victim forward if
necessary
An explanation of the algorithm here would help -- this is sthg like the classic
"stack distance" it seems.  Here you're maintaining the victim M lines away
where M is the cache capacity.  Right?

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:102: // move victim forward if
necessary
Or is it backward -- depends on how you think about it

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:103: if (total_lines > cache_lines)
So you're implementing your own LRU cache sim here.

Per offline discussion: we may want to explore a different definition of reuse
distance that is tied to cache misses (per cache set) and thus be able to
leverage the existing cache simulator.  By decoupling from the simulator, we can
easily swap different replacement policies and cache sizes without having to
duplicate all that code and those options here.  But it would not be measuring
classic reuse distance.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:151: /* FIXME i#2020: use unsorted_map
(C++11) for faster lookup */
XXX, not FIXME, b/c this is not a correctness issue

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:153: line_ref_list_t *ref_list;
This one matches the style guide but not the others

https://codereview.appspot.com/312880043/diff/150001/suite/tests/CMakeLists.txt
File suite/tests/CMakeLists.txt (right):

https://codereview.appspot.com/312880043/diff/150001/suite/tests/CMakeLists.t...
suite/tests/CMakeLists.txt:2453: "-ipc_name drtestpipe6 -simulator_type
reuse-distance -LL_size 16384" "" "")
Maybe _instead of - b/c everything else is _

[zhaoqin, 2016-10-28 18:26:28]

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.h (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:44: /* A double linked list for cache
line reference info */
On 2016/10/27 04:25:26, bruening wrote:
> How about using std::list since this is C++ code?

I guess I could.
I just feel that it is complex/less efficient to use std::list and std::map
together.
For example, for move_to_front. How do I find the node to be moved without a
lookup in the list? store the iterator in std::map?
I guess I am just not familiar with cpp, and confuse about the object life time.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:47: struct line_ref_t* prev;
On 2016/10/27 04:25:26, bruening wrote:
> style: DR style has the * on the var name, not the type name.
> 
> Also in a lot of places below.

Done

I am influnced by a Googler code reviewer, who insist * on the type side.

[bruening, 2016-10-29 17:59:04]

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.h (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:47: struct line_ref_t* prev;
On 2016/10/28 18:26:28, zhaoqin wrote:
> On 2016/10/27 04:25:26, bruening wrote:
> > style: DR style has the * on the var name, not the type name.
> > 
> > Also in a lot of places below.
> 
> Done
> 
> I am influnced by a Googler code reviewer, who insist * on the type side.

?  But that's for Google code which has a completely different style guide.

[zhaoqin, 2016-11-04 15:15:30]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace.

Adds reuse-distance test.

Adds -simulator_type reuse_distance and -reuse_distance_threshold.

Implements a doubly linked list based reuse distance checking algorithm.

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
78802 total accesses
2257 unique cache lines accessed
reuse distance threshold = 256 cache lines
top 10 frequently referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fd5400:        11934,            1
    0x7f1833fe2c00:        10549,            3
    0x7f1833fd3880:         6640,            0
    0x7f1833fd3840:         4722,            0
    0x7f1833fd53c0:         3614,            1
    0x7f1833fd2fc0:         2744,            1
    0x7f1833fd2f80:         2418,            0
    0x7f1833fe3940:         2205,            3
    0x7fff8b07da80:         2031,            2
    0x7f1833fd3780:         1814,            1
top 10 distant repeatedly referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fc9780:          257,            6
    0x7f1833fda1c0:          379,            5
    0x7f1833fda180:          338,            5
    0x7f18331a1480:           28,            5
    0x7f18341eca40:           48,            4
    0x7f18331a1940:           48,            4
    0x7f18341eda40:           47,            4
    0x7f1833fc97c0:           45,            4
    0x7f18341ebe80:           42,            4
    0x7f18341ed580:           32,            4

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-11-04 15:15:42]

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tests...
File clients/drcachesim/tests/reuse_distance.templatex (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tests...
clients/drcachesim/tests/reuse_distance.templatex:4: Cache Reuse Distance:
[0-9]+ total accesses
On 2016/10/27 04:25:26, bruening wrote:
> If the idea is to distinguish from app output would something with the pid in
it
> work better, like the typical Valgrind or Dr. Memory prefixes?  We may not
need
> a refix on every line, if this is *after* the app exited and thus will not
> interleave with app output?

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tests...
clients/drcachesim/tests/reuse_distance.templatex:7: Cache Reuse Distance: top
interested 10 cache lines
On 2016/10/27 04:25:26, bruening wrote:
> "interested" is ungrammatical here.  "interesting" maybe -- but this is
> quantitative, not qualitative, so don't you mean the 10 cache lines that
crossed
> the threshold the most often?  Maybe "top 10 cache lines sorted by count of
> threshold crossings" -- hmm not sure how to make it concise.
> 
> Also in the commit msg

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.cpp (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.cpp:110: std::cerr << TOOL_NAME << ":
reuse distance threshold = "
On 2016/10/27 04:25:26, bruening wrote:
> Should the threshold just be called a threshold and not a cache size, in the
> runtime options?  It seems confusing to conflate the two.

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.h (right):

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:44: /* A double linked list for cache
line reference info */
On 2016/10/27 04:25:26, bruening wrote:
> "doubly linked list"
> 
> Also multiple places below

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:57: // The top N nodes are cache lines
in the cache.
On 2016/10/27 04:25:26, bruening wrote:
> You mean the *first* N in the list

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:59: // a reference reuse distance is
within the top N or not in constant time.
On 2016/10/27 04:25:26, bruening wrote:
> This N is unrelated to the N above so maybe use different names

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:71: cache_lines = lines;
On 2016/10/27 04:25:26, bruening wrote:
> Why not in the constructor list

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:74: virtual ~line_ref_list_t()
On 2016/10/27 04:25:26, bruening wrote:
> style: type on own line
> 
> Also 3 times below

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:75: {
On 2016/10/27 04:25:26, bruening wrote:
> I guess we have no style for how big of an impl should be in a header file
(b/c
> our style guide is for C) but for the most part all our implementations are in
> .cpp files, right?  Only droption is in a header and it has to be.

I thought this would be better for code reading as it is not very long.
I will move it to separate file if we add other way of reuse distance
implementation, e.g., time based, miss based as we discussed offline.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:88: if (victim == NULL ||
ref->time_stamp > victim->time_stamp)
On 2016/10/27 04:25:26, bruening wrote:
> OK, I had to read the code below to figure out what is going on: victim is
> pointing at the next LRU line to go, which is M lines from the from of the
list,
> and its time stamp is guaranteed to be the lowest of those M.  A few
well-placed
> comments up above and again here would make this clearer and avoid the reader
> having to read through all the code and infer the invariants.

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:102: // move victim forward if
necessary
On 2016/10/27 04:25:26, bruening wrote:
> An explanation of the algorithm here would help -- this is sthg like the
classic
> "stack distance" it seems.  Here you're maintaining the victim M lines away
> where M is the cache capacity.  Right?

yes. clearly I am not familiar with that term.
Add the description on top of the struct.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:102: // move victim forward if
necessary
On 2016/10/27 04:25:26, bruening wrote:
> Or is it backward -- depends on how you think about it

Acknowledged.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:103: if (total_lines > cache_lines)
On 2016/10/27 04:25:26, bruening wrote:
> So you're implementing your own LRU cache sim here.
> 
> Per offline discussion: we may want to explore a different definition of reuse
> distance that is tied to cache misses (per cache set) and thus be able to
> leverage the existing cache simulator.  By decoupling from the simulator, we
can
> easily swap different replacement policies and cache sizes without having to
> duplicate all that code and those options here.  But it would not be measuring
> classic reuse distance.

This could be used for each (fully associated) cache line set. In that case, the
threshold is usually 3-8. So may not worth the doubly linked list
implementation, which can handle any threshold. An array implementation might be
more suitable.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:151: /* FIXME i#2020: use unsorted_map
(C++11) for faster lookup */
On 2016/10/27 04:25:26, bruening wrote:
> XXX, not FIXME, b/c this is not a correctness issue

Done.

https://codereview.appspot.com/312880043/diff/150001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:153: line_ref_list_t *ref_list;
On 2016/10/27 04:25:26, bruening wrote:
> This one matches the style guide but not the others

Acknowledged.

https://codereview.appspot.com/312880043/diff/150001/suite/tests/CMakeLists.txt
File suite/tests/CMakeLists.txt (right):

https://codereview.appspot.com/312880043/diff/150001/suite/tests/CMakeLists.t...
suite/tests/CMakeLists.txt:2453: "-ipc_name drtestpipe6 -simulator_type
reuse-distance -LL_size 16384" "" "")
On 2016/10/27 04:25:26, bruening wrote:
> Maybe _instead of - b/c everything else is _

Done.

[zhaoqin, 2016-11-04 15:21:43]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace.

Adds reuse-distance test.

Adds -simulator_type reuse_distance and -reuse_distance_threshold.

Implements a doubly linked list based reuse distance checking algorithm.

Example result:
Hello, world!
---- <application exited with code 0> ----
Cache Reuse Distance result:
78802 total accesses
2257 unique cache lines accessed
reuse distance threshold = 256 cache lines
top 10 frequently referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fd5400:        11934,            1
    0x7f1833fe2c00:        10549,            3
    0x7f1833fd3880:         6640,            0
    0x7f1833fd3840:         4722,            0
    0x7f1833fd53c0:         3614,            1
    0x7f1833fd2fc0:         2744,            1
    0x7f1833fd2f80:         2418,            0
    0x7f1833fe3940:         2205,            3
    0x7fff8b07da80:         2031,            2
    0x7f1833fd3780:         1814,            1
top 10 distant repeatedly referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fc9780:          257,            6
    0x7f1833fda1c0:          379,            5
    0x7f1833fda180:          338,            5
    0x7f18331a1480:           28,            5
    0x7f18341eca40:           48,            4
    0x7f18331a1940:           48,            4
    0x7f18341eda40:           47,            4
    0x7f1833fc97c0:           45,            4
    0x7f18341ebe80:           42,            4
    0x7f18341ed580:           32,            4

Review-URL: https://codereview.appspot.com/312880043
---------------

[bruening, 2016-11-07 17:17:42]

On 2016/11/04 15:21:43, zhaoqin wrote:
> Cache Reuse Distance result:
> 78802 total accesses
> 2257 unique cache lines accessed
> reuse distance threshold = 256 cache lines
> top 10 frequently referenced cache lines

nit: the capitalization seems a little odd: internal caps in "Cache Reuse
Distance" but starting with lowercase on lines like "top 10...".

There are grammar errors, but otherwise the description and field names are much
clearer, making it much easier to understand.  LGTM w/ comments.

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.h (right):

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:51: uint64_t distant_refs;    // the
total number of distant references on this line
This is much better than the prior names, which conflated cache simulation with
reuse distance, resulting in confusion.

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:66: // We also keeps a pointer (gate)
pointing to the the earliest cache
grammar error: keep

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:105: // We may need move gate forward
if there are more cache lines
need to

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:126: // We need move the gate pointer
forward if the referenced cache
need to

[zhaoqin, 2016-11-07 19:58:31]

Commit log for latest patchset:
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace.

Adds reuse-distance test.

Adds -simulator_type reuse_distance and -reuse_distance_threshold.

Implements a doubly linked list based reuse distance checking algorithm.

Example result:
Hello, world!
---- <application exited with code 0> ----
cache reuse distance result:
78802 total accesses
2257 unique cache lines accessed
reuse distance threshold = 256 cache lines
top 10 frequently referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fd5400:        11934,            1
    0x7f1833fe2c00:        10549,            3
    0x7f1833fd3880:         6640,            0
    0x7f1833fd3840:         4722,            0
    0x7f1833fd53c0:         3614,            1
    0x7f1833fd2fc0:         2744,            1
    0x7f1833fd2f80:         2418,            0
    0x7f1833fe3940:         2205,            3
    0x7fff8b07da80:         2031,            2
    0x7f1833fd3780:         1814,            1
top 10 distant repeatedly referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fc9780:          257,            6
    0x7f1833fda1c0:          379,            5
    0x7f1833fda180:          338,            5
    0x7f18331a1480:           28,            5
    0x7f18341eca40:           48,            4
    0x7f18331a1940:           48,            4
    0x7f18341eda40:           47,            4
    0x7f1833fc97c0:           45,            4
    0x7f18341ebe80:           42,            4
    0x7f18341ed580:           32,            4

Review-URL: https://codereview.appspot.com/312880043
---------------

[zhaoqin, 2016-11-07 20:00:03]

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
File clients/drcachesim/tools/reuse_distance.h (right):

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:51: uint64_t distant_refs;    // the
total number of distant references on this line
On 2016/11/07 17:17:42, bruening wrote:
> This is much better than the prior names, which conflated cache simulation
with
> reuse distance, resulting in confusion.

Acknowledged.

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:66: // We also keeps a pointer (gate)
pointing to the the earliest cache
On 2016/11/07 17:17:42, bruening wrote:
> grammar error: keep

Done.

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:105: // We may need move gate forward
if there are more cache lines
On 2016/11/07 17:17:42, bruening wrote:
> need to

Done.

https://codereview.appspot.com/312880043/diff/190001/clients/drcachesim/tools...
clients/drcachesim/tools/reuse_distance.h:126: // We need move the gate pointer
forward if the referenced cache
On 2016/11/07 17:17:42, bruening wrote:
> need to

Done.

[zhaoqin, 2016-11-07 20:25:31]

Committed as
https://github.com/DynamoRIO/dynamorio/commit/018a5f73a2a4eb90c0df774dc96eec9...

Final commit log: 
---------------
i#2006 generalize drcachesim: add the reuse-distance tool

Adds the reuse-distance tool to track each cacheline usage by the trace.

Adds reuse-distance test.

Adds -simulator_type reuse_distance and -reuse_distance_threshold.

Implements a doubly linked list based reuse distance checking algorithm.

Example result:
Hello, world!
---- <application exited with code 0> ----
cache reuse distance result:
78802 total accesses
2257 unique cache lines accessed
reuse distance threshold = 256 cache lines
top 10 frequently referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fd5400:        11934,            1
    0x7f1833fe2c00:        10549,            3
    0x7f1833fd3880:         6640,            0
    0x7f1833fd3840:         4722,            0
    0x7f1833fd53c0:         3614,            1
    0x7f1833fd2fc0:         2744,            1
    0x7f1833fd2f80:         2418,            0
    0x7f1833fe3940:         2205,            3
    0x7fff8b07da80:         2031,            2
    0x7f1833fd3780:         1814,            1
top 10 distant repeatedly referenced cache lines
        cache line:     #references   #distant refs
    0x7f1833fc9780:          257,            6
    0x7f1833fda1c0:          379,            5
    0x7f1833fda180:          338,            5
    0x7f18331a1480:           28,            5
    0x7f18341eca40:           48,            4
    0x7f18331a1940:           48,            4
    0x7f18341eda40:           47,            4
    0x7f1833fc97c0:           45,            4
    0x7f18341ebe80:           42,            4
    0x7f18341ed580:           32,            4

Review-URL: https://codereview.appspot.com/312880043
---------------