Lookup caching

[Andrea Griffini]

Hello,

I implemented that crazy idea and seems working... in its
current hacked state can still pass the test suite (exluding
the tests that don't like self generated output on stdout
from python) and the stats after the quicktest are IMO
impressing:

LOAD_GLOBAL = 13666473
globals miss = 58988
builtins = 8246184
builtins miss = 32001

LOAD_GLOBAL is the total number of times the pseudocode
instruction was executed.

globals miss is the number of time the actual lookup
on globals had to be perfomed. Note that if the lookup
wasn't done because the name was known to be absent
from globals still it's considered a cache hit, not miss.

builtins is the total number of times the builtins dict
has to be searched (because the name was not in globals)

builtin miss is the number of real builtin searches
that were performed (in other cases the lookup cache for
builtins found the answer - either positive or negative).

To me seems a promising idea, i've still to clean up
the code and to make serious speed tests (the "make test"
itself seems a lot more "fluid", but it could be just
self hypnotization :-D ).

The LOAD_GLOBAL code is actually simpler because I
resorted to a regular non-inlined lookup in case of
a cache miss. There's no reason to do that however...

Also the same approach could be used for other lookups
that get the name from co->co_names.


Andrea

[Gabriel Genellina]

Re: Lookup caching

At Saturday 9/12/2006 23:04, Andrea Griffini wrote:

>I implemented that crazy idea and seems working... in its
>current hacked state can still pass the test suite (exluding

What crazy idea? And what is this supposed to do?


--
Gabriel Genellina
Softlab SRL

_______________ _______________ _______________ _____
Correo Yahoo!
Espacio para todos tus mensajes, antivirus y antispam ¡gratis!
¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar

[Andrea Griffini]

Re: Lookup caching

Gabriel Genellina wrote:

At Saturday 9/12/2006 23:04, Andrea Griffini wrote:
>

>I implemented that crazy idea and seems working... in its
>current hacked state can still pass the test suite (exluding

>
What crazy idea? And what is this supposed to do?
>

The idea is to avoid looking up constants several times
into dictionaries that didn't change (e.g. builtins).

Reading a bit about other optimization proposals I didn't
find a similar one so I decided to invest some spare time
in it. The idea is

1) Add a "timestamp" to dictionaries, so when a dictionary
is changed the timestamp gets updated

2) Store a cached lookup for constants; the cached lookup
is stored as a timestamp value and a naked pointer to
the result. The algorithm for the lookup of a given
constant is:

if ( <<cached_timest amp>== d->timestamp)
{
x = <<cached_value> >;
}
else
{
x = PyDict_GetItem( d, key);
<<cached_timest amp>= d->timestamp;
<<cached_value> = x;
}

using a naked pointer is safe because it will be used
only if the dictionary wasn't touched, hence the value
is surely still alive.

The original place I thought about where to store the
cached lookup was the bytecode, however after reading
python sources I resorted instead to a dedicated space
inside the code object. The code for LOAD_GLOBAL uses
something like

if (co->co_cachedtstam ps[oparg] == d->timestamp)
...

i.e. I used an array indexed by the index of the co_name
used for lookups.

The patched code is currently working, however I found
that while the hit/miss ratios are impressive (as I
expected) the speedup is simply absent. Moreover there
is no difference at all between paying for the timestamp
handling and NOT using the cached lookups or instead
paying AND using the cached lookups (!).
Absurdely python on my PC runs faster if I in addition
to the cached lookup code also leave in place the
hit/miss statistics (a few static ints increment and
a static atexit-ed output function).
Also it made a lot of difference about where the
timestamp was placed inside the dictobject structure...

In addition to the not impressive results (my patched
python now is just a bit *slower* than original one :-D)
there is also another complication. The LOAD_GLOBAL
actually needs TWO lookups, so I used two cached results
(one for globals, one for builtins).
The ideal solution however IMO would be in this case
to have two timestamps and one cached value instead...
(if neither dict was touched since last lookup then the
result will be the cached one).

The complication is that a lot of lookups are done by
the LOAD_ATTR instead and thinking to the ideal solution
for new classes made my brain explode (mro, descriptor
and stuff...). It would be simple to do something for
classic classes, but would that be worth (i mean...
aren't those going to disappear ?).

Probably something can be done for using caches for
LOAD_ATTR for modules (to speed up a bit things like
math.sin or mod1.mod2.mod3. func).

Any suggestion is welcome...

Andrea

[MRAB]

Re: Lookup caching


Andrea Griffini wrote:

Gabriel Genellina wrote:

At Saturday 9/12/2006 23:04, Andrea Griffini wrote:

I implemented that crazy idea and seems working... in its
current hacked state can still pass the test suite (exluding

What crazy idea? And what is this supposed to do?

The idea is to avoid looking up constants several times
into dictionaries that didn't change (e.g. builtins).
>
Reading a bit about other optimization proposals I didn't
find a similar one so I decided to invest some spare time
in it. The idea is
>
1) Add a "timestamp" to dictionaries, so when a dictionary
is changed the timestamp gets updated
>
2) Store a cached lookup for constants; the cached lookup
is stored as a timestamp value and a naked pointer to
the result. The algorithm for the lookup of a given
constant is:
>
if ( <<cached_timest amp>== d->timestamp)
{
x = <<cached_value> >;
}
else
{
x = PyDict_GetItem( d, key);
<<cached_timest amp>= d->timestamp;
<<cached_value> = x;
}
>
using a naked pointer is safe because it will be used
only if the dictionary wasn't touched, hence the value
is surely still alive.
>
The original place I thought about where to store the
cached lookup was the bytecode, however after reading
python sources I resorted instead to a dedicated space
inside the code object. The code for LOAD_GLOBAL uses
something like
>
if (co->co_cachedtstam ps[oparg] == d->timestamp)
...
>
i.e. I used an array indexed by the index of the co_name
used for lookups.
>
The patched code is currently working, however I found
that while the hit/miss ratios are impressive (as I
expected) the speedup is simply absent. Moreover there
is no difference at all between paying for the timestamp
handling and NOT using the cached lookups or instead
paying AND using the cached lookups (!).
Absurdely python on my PC runs faster if I in addition
to the cached lookup code also leave in place the
hit/miss statistics (a few static ints increment and
a static atexit-ed output function).
Also it made a lot of difference about where the
timestamp was placed inside the dictobject structure...
>
In addition to the not impressive results (my patched
python now is just a bit *slower* than original one :-D)
there is also another complication. The LOAD_GLOBAL
actually needs TWO lookups, so I used two cached results
(one for globals, one for builtins).
The ideal solution however IMO would be in this case
to have two timestamps and one cached value instead...
(if neither dict was touched since last lookup then the
result will be the cached one).
>

[snip]
What are you using for the timestamp? Are you calling a function to
read a timer?

If so, you could try something that's 'cheaper' like a modification
counter instead, ie a counter that's incremented each time the dict is
modified.

[Andrea Griffini]

Re: Lookup caching

MRAB wrote:

....

What are you using for the timestamp? Are you calling a function to
read a timer?

For timestamp I used a static variable; to update the timestamp for
a dictionary I used

d->timestamp = ++global_dict_t imestamp;

I'm using a single counter for all dicts so that when doing the check
for cached value validity I'm checking at the same time that the dict
is the same dict was used and that it wasn't touched since when the
lookup result was stored.

Using this approach and tweaking the LOAD_GLOBAL double lookup for
using a "two timestamps one value" cache I got an 8%-10% speedup
(depending on the compiler options when building python) in a real
application of mines and about 5% in a small test.

I've yet to try more complex applications (the biggest real
application I have however requires a lot of external modules
so testing the speed gain with that will require a lot more work
or just downgrading the python version to 2.4).

Also I'm using an 32 bit int for timestamp... I wonder if I should
listen to the paranoid in my head that is crying for 64 instead.


Andrea