One easy way to implement exact LRU in software.... (doubly) linked list.
Each item points to its node in the linked list. On each access to an item move its node to the head of the list. When you need to evict, kick out the tail element. Alot of software cache simulators use this for exact LRU
This way you can maintain LRU by only changing a few pointers in a nice generic manner.
Also, since this would be fully associative with ALOT of associativity, the things that get evicted are the files that you nearly NEVER use.
Right now im doing data-cache research that requires reference traces that are post-processed for various statistics (aka. every load & store is written to a file and then examined by other apps).
These files are HUGE. Some of the benchmarks we're running have well over a billion memory references. For each reference you have 4 to 8 bytes for the address and various additional bytes for additional statistics.
...and for people who know its ALOT quicker to implement something in HDL's. Try doing something with a few hundred thousand gates in schematics & you'll see what I mean...
Just try doing this with 2 or 3 people in a month or two without HDL's: http://www.eecs.umich.edu/courses/eecs470/ term_pro j.pdf
(Super-scalar (2-wide issue) Alpha ISA (64bit data path) processor, L1 caches, etc etc....)
Bugs are one of the few drawbacks ive seen with the STL. Even where they exist, its not that hard to avoid them due to the number of member functions which overlap...
the linked list class is an example of this (bare with me, Someone i worked with found this problem and its been a few months since ive looked at it).. Depending on how you use erase, if you keep calling the function untill the entire list is empty, invalid pointers seem to exist within the container. IF you then add a few elements (i believe it was two push backs in this specific case) the entire list gets hosed. Ive only tried/seen this on the SUN implementation.
Though this is annoying, its easy to avoid this with all of the member functions you're given to play with... Just knowing its there becomes sorta screwy.
>To track down the signal, units must >be processed. If we process signals >faster it'll either let them eventually >process more signals
They are already processing the signals at nearly twice the speed they can collect them.
By speeding up the client a small percent you hope for what? processing at 3 times the speed its collected? The client is good enough and nothing is gained by spending countless hours gaining a small speed increase, the time could be better spent somewhere else.
(this is like spending months of your spare time speeding up lilo or some other command. might learn something doing it but it is just a waste of time)
If this were a typical user program then id say open source it. The fact is this is a scientific experiment. The validity of the data collected is all that matters. If you open source the code then you will have a number of people who screwed up their version of the client because they didnt know how to do it right or because they just want higher stats and dont care about the data.
The benifit of an open source client is lost in a case such as this.
Slashdot Mirror
One easy way to implement exact LRU in software.... (doubly) linked list.
Each item points to its node in the linked list. On each access to an item move its node to the head of the list. When you need to evict, kick out the tail element. Alot of software cache simulators use this for exact LRU
This way you can maintain LRU by only changing a few pointers in a nice generic manner.
Also, since this would be fully associative with ALOT of associativity, the things that get evicted are the files that you nearly NEVER use.
One not-so-everyday reason....
:(
Research.
Right now im doing data-cache research that requires reference traces that are post-processed for various statistics (aka. every load & store is written to a file and then examined by other apps).
These files are HUGE. Some of the benchmarks we're running have well over a billion memory references. For each reference you have 4 to 8 bytes for the address and various additional bytes for additional statistics.
On the low side these files are ~ 4GB
That harddrive (assuming its the 5400rpm) is $67.95 on pricewatch INCLUDING shipping.
$183 is alot to pay for free software that's been imaged onto the disk
I still like the basic idea though.
none of the less-than & greater-than signs made it through the filter :)
Look at the for loops
If anyone is wondering, this is what he is the comic he is talking about.
I dunno where you go to school but all the college girls around here look alot oder than that one. try this or this or this etc.. etc..
... of _legal_ age.
That girl looks like she's 12. 13 at the most.
"VHDL code is for wimps ;)"
/ term_pro j.pdf
...and for people who know its ALOT quicker to implement something in HDL's. Try doing something with a few hundred thousand gates in schematics & you'll see what I mean...
Just try doing this with 2 or 3 people in a month or two without HDL's:
http://www.eecs.umich.edu/courses/eecs470
(Super-scalar (2-wide issue) Alpha ISA (64bit data path) processor, L1 caches, etc etc....)
Bugs are one of the few drawbacks ive seen with the STL. Even where they exist, its not that hard to avoid them due to the number of member functions which overlap...
the linked list class is an example of this (bare with me, Someone i worked with found this problem and its been a few months since ive looked at it)..
Depending on how you use erase, if you keep calling the function untill the entire list is empty, invalid pointers seem to exist within the container. IF you then add a few elements (i believe it was two push backs in this specific case) the entire list gets hosed.
Ive only tried/seen this on the SUN implementation.
Though this is annoying, its easy to avoid this with all of the member functions you're given to play with... Just knowing its there becomes sorta screwy.
>To track down the signal, units must
>be processed. If we process signals
>faster it'll either let them eventually
>process more signals
They are already processing the signals at nearly twice the speed they can collect them.
By speeding up the client a small percent you hope for what? processing at 3 times the speed its collected? The client is good enough and nothing is gained by spending countless hours gaining a small speed increase, the time could be better spent somewhere else.
(this is like spending months of your spare time speeding up lilo or some other command. might learn something doing it but it is just a waste of time)
If this were a typical user program then id say open source it. The fact is this is a scientific experiment. The validity of the data collected is all that matters. If you open source the code then you will have a number of people who screwed up their version of the client because they didnt know how to do it right or because they just want higher stats and dont care about the data.
The benifit of an open source client is lost in a case such as this.