(sorry if you see this twice but i think my last posting failed...)
i want to build a method cache for an object system i am designing and
i need some advice.
the Smalltalk-80 books tell me that that 32% of an OO system's runtime
behaviour is method look-up. with a method cache, we can reduce that to
5%. they recommend a cache of 512-1024 items.
but the cache needs one trick: the method cache has to contain only the
most recently accessed items. so i have to build a cache that can
compute "recently-used" real quick. design problem: how to manage this
recently-used test without slowing down the processing of the methods
that are recently used.
here's what I've come up with. its a method inspired by skip lists and
generation garbage collectors. to me, it seems too simple to (a) be the
best approach; (b) be the best method and (c) be an original idea.
suggestions/improvements anyone?
--------------------------------------------------------------
a "small memo" is a hash table that remembers the last N items computed
by some GENERATOR. when a value is needed, we check for it in the memo
space. if its there, we return it. else we ask GENERATOR to create it,
then we store it.
associated with the GENERATOR is a set of "G" GENERATION-SPACES
numbered 1 to G. Generation space G[i] is ALPHA times as small as space
G[i+1]. Generation space G[1] stores the most used items and is the
smallest space. for example, if N is 1300 then G[1] holds 100 items,
G[2] holds 300 items, and G[3] holds 900 items.
each generation space is a linked list. a SPACE-MANAGER stores pointers
to the FIRST and LAST item in the linked list. each linked list item
stores pointers to NEXT, PREV, KEY, and its associated space manager.
several operations can be performed very fast on such a space. an item
can HOP forward 1 space, SKIP to in front of the FIRST item, or JUMP
forward to space G[j] (j < i where i is the current generation). if an
item is JUMPED to space j, then the it becomes the FIRST item in j and
the LAST item in j is "demoted".
demotion from space g means being moved back to being the FIRST item of
space g+1. if there is no next largest space (i.e. when j=G), then the
item is dumped and its corresponding entry in the hash table is
removed.
2 special cases: if the first item is HOPed or SKIPped, it merely stays
where it is. if an item is JUMPed from G[1] it merely SKIPs.
hash table items are a pair: KEY VALUE. VALUEs have a RAW-VALUE field
as well as a GENERATION-PTR pointer into a generation space. when
accessing an item that is already in the cache, the processing follows
the GENERATION-PTR to the its associated generation space. it then
consults a probability distribution to see whether it should HOP, SKIP,
or JUMP. JUMPS are less likely than SKIPs which are less likely than
HOPs. the slowest operation is a jump since this requires reseting the
FIRST and LAST pointers of all spaces G[j] where j > i (i being the
current space). consider a jump in G[1]. an item is pushed demoted to
G[2]. this implies another demotion of the LAST of G[2] into G[3]. and
so on.
the smaller the space number g, the less likely are the HOPs (so things
in the smaller spaces which we access a lot are less likely to be moved
around than things in the larger spaces). "less likely" is some factor
controlled by a variable BETA.
note that the probability distribution could be compiled into a
circular list of instructions and cached with each GENERATION-SPACE.
so, a BETA = 3, generation G[i] have a circular list 130 items long
storing 90 hop symbols, 30 skip symbols and 10 jump symbols spread
randomly around the list. generation G[i+1] would have 3 jumps, 10
skips. and 117 hops. at runtime, when a space is accessed, it moves a
NEXT-OP pointer to the next thing in the list then consults a case
statement about how to perform the action.
note the more often an item is called, the more likely it is that it is
moved up a generation. however, the higher the generation (i.e the
smaller g) then its less likely that it will move onwards. so
something has to be called a lot to make it into the top of G[1].
also, we will be doing less and less with the things that are used most
frequently (i.e. those things in G[1]).
--
,-_|\ Tim Menzies (····@cse.unsw.edu.au) | "Fortunately, I say,
/ \ AI Lab, Computer Science, Uni. NSW | fortunately, I keep my
\_,-._* <- P.O. Box 1, Kensington, Australia, 2033 | feathers numbered for
v +61-2-663-4576 (fax) +61-2-697-3980 (w) | just such an emergency."
-- Foghorn Leghorn
"We have many sayings,
but no doings."
-- Anon.
In article <·····················@usage.csd.unsw.OZ.AU>, ····@cse.unsw.edu.au (Tim Menzies) writes:
> the Smalltalk-80 books tell me that that 32% of an OO system's runtime
> behaviour is method look-up. with a method cache, we can reduce that to
> 5%. they recommend a cache of 512-1024 items.
>
> but the cache needs one trick: the method cache has to contain only the
> most recently accessed items. so i have to build a cache that can
> compute "recently-used" real quick. design problem: how to manage this
> recently-used test without slowing down the processing of the methods
> that are recently used.
You can't. Overhead sucks. :)
> --------------------------------------------------------------
>
> a "small memo" is a hash table that remembers the last N items computed
> by some GENERATOR. when a value is needed, we check for it in the memo
> space. if its there, we return it. else we ask GENERATOR to create it,
> then we store it.
>
> associated with the GENERATOR is a set of "G" GENERATION-SPACES
> numbered 1 to G. Generation space G[i] is ALPHA times as small as space
> G[i+1]. Generation space G[1] stores the most used items and is the
> smallest space. for example, if N is 1300 then G[1] holds 100 items,
> G[2] holds 300 items, and G[3] holds 900 items.
>
> each generation space is a linked list. a SPACE-MANAGER stores pointers
> to the FIRST and LAST item in the linked list. each linked list item
> stores pointers to NEXT, PREV, KEY, and its associated space manager.
>
> several operations can be performed very fast on such a space. an item
> can HOP forward 1 space, SKIP to in front of the FIRST item, or JUMP
> forward to space G[j] (j < i where i is the current generation). if an
> item is JUMPED to space j, then the it becomes the FIRST item in j and
> the LAST item in j is "demoted".
>
> demotion from space g means being moved back to being the FIRST item of
> space g+1. if there is no next largest space (i.e. when j=G), then the
> item is dumped and its corresponding entry in the hash table is
> removed.
>
> 2 special cases: if the first item is HOPed or SKIPped, it merely stays
> where it is. if an item is JUMPed from G[1] it merely SKIPs.
>
> hash table items are a pair: KEY VALUE. VALUEs have a RAW-VALUE field
> as well as a GENERATION-PTR pointer into a generation space. when
> accessing an item that is already in the cache, the processing follows
> the GENERATION-PTR to the its associated generation space. it then
> consults a probability distribution to see whether it should HOP, SKIP,
^^^^^^^^^^^^^^^^^^^^^^^^ There go some more cycles...
> or JUMP. JUMPS are less likely than SKIPs which are less likely than
> HOPs. the slowest operation is a jump since this requires reseting the
> FIRST and LAST pointers of all spaces G[j] where j > i (i being the
> current space). consider a jump in G[1]. an item is pushed demoted to
> G[2]. this implies another demotion of the LAST of G[2] into G[3]. and
> so on.
>
> the smaller the space number g, the less likely are the HOPs (so things
> in the smaller spaces which we access a lot are less likely to be moved
> around than things in the larger spaces). "less likely" is some factor
> controlled by a variable BETA.
>
> note that the probability distribution could be compiled into a
> circular list of instructions and cached with each GENERATION-SPACE.
> so, a BETA = 3, generation G[i] have a circular list 130 items long
> storing 90 hop symbols, 30 skip symbols and 10 jump symbols spread
> randomly around the list. generation G[i+1] would have 3 jumps, 10
> skips. and 117 hops. at runtime, when a space is accessed, it moves a
> NEXT-OP pointer to the next thing in the list then consults a case
> statement about how to perform the action.
>
> note the more often an item is called, the more likely it is that it is
> moved up a generation. however, the higher the generation (i.e the
> smaller g) then its less likely that it will move onwards. so
> something has to be called a lot to make it into the top of G[1].
> also, we will be doing less and less with the things that are used most
> frequently (i.e. those things in G[1]).
>
Interesting stuff. Code it up an see! This is a priority queue, not original,
but good work anyway.
--
** ····@merlin.cobb.ziff.com // (502) 491-1900 x401
** All opinions my own **
>>> Luck is the residue of good design <<<
From: Karel Driesen
Subject: Re: ADVICE PLEASE: how to build a method cache?
Date:
Message-ID: <2hgph6$ar8@rc1.vub.ac.be>
In article <·····················@usage.csd.unsw.OZ.AU> Tim Menzies,
····@cse.unsw.edu.au writes:
>i want to build a method cache for an object system i am designing and
(stuff deleted)
You might want to look at descriptions of method caches in the following
articles:
[AND!92] P. Andr!, J. C. Royer.
Optimizing Method Search with Lookup Caches and Incremental Coloring
OOPSLA'92 Proceedings p.110-126
[CON!82] T.J.Conroy, E.Pelegri-Llopart
An Assessment of Method-Lookup Caches for Smalltalk-80 Implementations
1982, in [KRA 83], p.239-247
[DIX 89] T. Dixon, M. Vaughan, P. Sweizer.
A fast Method Dispatcher for Compiled Languages with Multiple Inheritance
OOPSLA'89 Proceedings p.221-214
[DRI 93] K. Driesen.
Selector Table Indexing & Sparse Arrays
OOPSLA'93 Proceedings p.259-270
[DEU 84] P. Deutch, A. Schiffman.
Efficient Implementation of the Smalltalk-80 System
POPL Proceedings 1984 p. 297-302
[HOL!91] U. H!lzle, C. Chambers, D. Ungar
Optimizing Dynamically-Typed Object-Oriented Programs using Polymorphic
Inline Caches
ECOOP'91 Proceedings p. 21-38
[KRA 83] G. Krasner
Smalltalk-80: Bits of History, Words of Advice
Addison-Wesley 1983
[ROS!88] J. R. Rose
Fast Dispatch Mechanisms for Stock Hardware
OOPSLA'88 Proceedings
[UNG 87] D. M. Ungar
The Design and Evaluation of a High Performance Smalltalk System
An ACM Distinguished Dissertation 1986, MIT Press 1987
I wrote a dissertation on the subject (readable, so people tell me), in
which most of the currently used alternatives are treated in a more or
less uniform way. I can make it FTP-able for you if you send me a note.
+-----------------------------------------------------------------------+
| Karel Driesen E-mail: ········@vnet3.vub.ac.be |
| PROG (WE) Phone: (+32) 2-6413306 |
| Vrije Universiteit Brussel Fax: (+32) 2-6413495 |
| Pleinlaan 2 1050 Brussels |
| Belgium |
+-----------------------------------------------------------------------+
From: Karel Driesen
Subject: Re: ADVICE PLEASE: how to build a method cache?
Date:
Message-ID: <2hj4rr$1km@rc1.vub.ac.be>
There were a lot of people interested, so I post this information instead
of replying to each one separately:
temporary ftp-site for anon ftp (I will keep it open for a week):
134.184.43.111
You will find 3 postscript files:
Mthesis93.ps : Master thesis: Overview of method caching strategies,
with detailed description of selector table indexing with sparse array
implementation
oopsla93.ps : "Selector Table Indexing & Sparse Arrays", as in OOPSLA
proceedings
gronics94.ps : "Compressing a Sparse Table using a Genetic Algorithm",
experiment with GA's as a combinatorial optimisation strategy for sparse
tables. (ok but very slow)
Please email if there are any problems in ftp-ing or otherwise,
Karel
PS: You might also want to contact Jan Vitek (······@cui.unige.ch), who
has very recently implemented a technique based on static caching, but
with very little overhead.
+-----------------------------------------------------------------------+
| Karel Driesen E-mail: ········@vnet3.vub.ac.be |
| PROG (WE) Phone: (+32) 2-6413306 |
| Vrije Universiteit Brussel Fax: (+32) 2-6413495 |
| Pleinlaan 2 1050 Brussels |
| Belgium |
+-----------------------------------------------------------------------+
You might also want to check the following in which we show how a VERY
simple hash function, used with selector specific tables, can get very
hit rates ands very good table utilization.
@inproceedings{KiczalesLFP90,
Title="Efficient Method Dispatch in {PCL}",
Author="Gregor J. Kiczales and Luis H. {Rodriguez Jr.}",
booktitle="Proceedings of the 1990 ACM Conference on Lisp and Functional Programming",
year="1990",
pages="99--105"}
From: ···············@cup.portal.com
Subject: Re: ADVICE PLEASE: how to build a method cache?
Date:
Message-ID: <101722@cup.portal.com>
A very good way to speed up method lookup in an object system is
to avoid doing it at all. Assuming a system along the lines of
Smalltalk (dispatch to a method based on the class of the
receiver), a technique due to Peter Deutsch goes like this:
1. At each message sending location, remember what method was
resolved to last time. (Start things up by storing the
message dispatcher as the remembered 'method'.)
2. At each message sending location, invoke the method used the
last time that a message was sent from the location.
3. In front of every method, make a check to see if the class of
the receiver is correct for the method. If it is, enter the
method. If it's not, invoke the message dispatcher. Have
the dispatcher store the location of the method resolved to
at the message sending location.
Of course, you can conjure up message sending patterns where this
scheme doesn't help, but the technique works in practice because:
- The check in step 3 can be done in a *very* small number of
instructions.
- Real object systems are 'not that polymorphic'; there is a
strong tendency for the class of the receiver to remain
nearly constant at most sending locations.
I have used this technique in a large (700 classes, 10000 method)
commercial OO implementation. The result is a message dispatch
overhead in this system of less than 5% of total processor time.
The scheme or a near cousin can be seen to be in use in the
current ParcPlace implementation. To see this, make some test
message sends, vary the tendency of the class of the receiver
to remain constant and plot the message execution time as a
function of the tendency to remain constant.
...Tom M
The Brooklyn Union Gas Company
From: ···············@cup.portal.com
Subject: Re: ADVICE PLEASE: how to build a method cache?
Date:
Message-ID: <101882@cup.portal.com>
The previous posting by me about a scheme to make method
resolution faster left out some important stuff. Here's a corrected
statement. This is simple and fast, but does consume memory
at the sending locations.
1. At each message sending location, remember what the receiver
class was and what the method was resolved to last time. (Start
things up by storing the message dispatcher as the remembered
'method'.)
2. At each message sending location, invoke the method used the
last time that a message was sent from the location.
3. In front of every method, make a check to see if the class of
the receiver is correct for the method, by seeing that the class
this time is the same as last. If it is, enter the
method. If it's not, invoke the message dispatcher. Have
the dispatcher store the location of the method resolved
and the current receiver class at the message sending location.
...Tom M