Subject: patch -- cache last searched frag
From: Joaquín Cuenca Abela (cuenca@pacaterie.u-psud.fr)
Date: Fri Jul 06 2001 - 07:49:44 CDT
I've been taking a look at our pf_Fragments, and after some UT_DEBUGMSG
I've seen that the searches for pf_Frag's are very (*very*) local. So
I've added a little cache (of only 1 element) to this class.
Before this patch, the algorithm was something as:
{
if (position in last frag)
return last frag
else
return binary searched frag
}
and now it's something as:
{
if (position in lastfrag)
return lastfrag
else
if (position in cached frag)
return cached frag
else
put binary searched frag in cache and return it
}
of course, the slower step is the binary search. In my test (write
several lines of text, with some typos, changing a bit of formatting,
comming back for fix typos, and writting some text in the middle of the
document), the value cached was the right one 99.5% of times. That's
due mainly to:
1) we request several times the same frag when inserting text
2) when the user is typing a word (very usual operation), all the
searches should return the same frag.
When the cached value is not the right one, we don't lost many time (it
*seems* to be *absolutely* ridiculous compared to all the stuff that we
do in the binary search).
The only thing that can invalidate the cached value is if we unlink the
Frag from the Frags list, and in this case I change the cached value to
the previous frag.
Anyway, I will ask to *not* yet commit this patch. I've only tested it
slightly, and I've not yet been able to run a profiler in both,
precached-abiword and cached-abiword. So please, hold your breath until
I run a profiler and some more tests. And feel free to help with the
tests! :-)
(I've not so experienced as Jesper or Martin doing hards and weirds
tests... ;-)
P.S.: I've just run a little run, and I'm impressed :) ok, it's not a
very rich one, but I've just written two lines of text, copied them, and
start copying them at the end of the doc (just press C-v and wait a
minute :). Abi tries to scroll to keep up with mouvement cursor, and...
well, not cached abi *tries* to scroll and cached abi scrolls :-)
Cheers,
-- Joaquín Cuenca Abela cuenca@celium.net
This archive was generated by hypermail 2b25 : Fri Jul 06 2001 - 07:49:16 CDT