Cache relevant to Squeak code? (was: RE: Skip Lists?!)

Tue Oct 2 18:31:43 UTC 2001

David, VM gurus -
David gave this pointer to an interesting article about 
> Cache Conscious Indexing for Decision-Support in Main Memory 

It's a very interesting article, and it got me thinking -
Should I be bothered about making Squeak data structures I use fit
nicely in a cache?

I suspect that the VM will be doing enough memory accesses of it's own
(like method entry caching discussed the last few days) to make this
irrelevant - none of my actual Squeak objects will manage to stay in
long enough to matter. But maybe I'm wrong...

Maybe this means I can only benefit from this technique if I also write
a primitive to do the search loop, keeping out the VM machinary
altogether.

Anybody actually knows?

Daniel

"Pennell, David" <DPennell at quallaby.com> wrote:
> This message is in MIME format. Since your mail reader does not understand
> this format, some or all of this message may not be legible.
> 
> ------_=_NextPart_001_01C14A7A.38FA0720
> Content-Type: text/plain;
> 	charset="ISO-8859-1"
> 
> > Hmm, with "main" memory being so much slower than cache, btrees might
> > even start making sense for in-memory structures.  But not necessarily
> > for Squeak, where an "array of foo's" won't necessarily have 
> > all of the
> > foo's next to each other, anyway, and thus where accessing 
> > items within
> > a node still causes fetches to distant parts of memory.
> 
> You might want to take a look at:
> 
> Cache Conscious Indexing for Decision-Support in Main Memory 
> (Jun Rao and Kenneth Ross at Columbia University)
> 
> http://citeseer.nj.nec.com/rao99cache.html
> 
> If the foo's are SmallInteger's, it could be interesting, but probably
> not for the general case.  
> 
> -david
> 
> ------_=_NextPart_001_01C14A7A.38FA0720
> Content-Type: text/html;
> 	charset="ISO-8859-1"
> 
> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
> <HTML>
> <HEAD>
> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
> <META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2653.12">
> <TITLE>RE: Skip Lists?!</TITLE>
> </HEAD>
> <BODY>
> 
> <P><FONT SIZE=2>&gt; Hmm, with &quot;main&quot; memory being so much slower than cache, btrees might</FONT>
> <BR><FONT SIZE=2>&gt; even start making sense for in-memory structures.&nbsp; But not necessarily</FONT>
> <BR><FONT SIZE=2>&gt; for Squeak, where an &quot;array of foo's&quot; won't necessarily have </FONT>
> <BR><FONT SIZE=2>&gt; all of the</FONT>
> <BR><FONT SIZE=2>&gt; foo's next to each other, anyway, and thus where accessing </FONT>
> <BR><FONT SIZE=2>&gt; items within</FONT>
> <BR><FONT SIZE=2>&gt; a node still causes fetches to distant parts of memory.</FONT>
> </P>
> 
> <P><FONT SIZE=2>You might want to take a look at:</FONT>
> </P>
> 
> <P><FONT SIZE=2>Cache Conscious Indexing for Decision-Support in Main Memory </FONT>
> <BR><FONT SIZE=2>(Jun Rao and Kenneth Ross at Columbia University)</FONT>
> </P>
> 
> <P><FONT SIZE=2><A HREF="http://citeseer.nj.nec.com/rao99cache.html" TARGET="_blank">http://citeseer.nj.nec.com/rao99cache.html</A></FONT>
> </P>
> 
> <P><FONT SIZE=2>If the foo's are SmallInteger's, it could be interesting, but probably</FONT>
> <BR><FONT SIZE=2>not for the general case.&nbsp; </FONT>
> </P>
> 
> <P><FONT SIZE=2>-david</FONT>
> </P>
> 
> </BODY>
> </HTML>
> ------_=_NextPart_001_01C14A7A.38FA0720--