Subject: Re: patch -- cache last searched frag
From: Martin Sevior (msevior@mccubbin.ph.unimelb.edu.au)
Date: Fri Jul 06 2001 - 09:39:14 CDT
On Fri, 6 Jul 2001, [ISO-8859-1] Joaquín Cuenca Abela wrote:
> 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).
This is a great idea. Just to let you know, before I implemented the
binary search about 1 month ago, we did a LINEAR search from the start of
the document for the Frag.
>
> 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.
>
Not necessarily. If you delete a whole lot of text before the cached Frag
you might have an incorrect doc position in the cached frag.
To be safe you should check the areFragsDirty() method.
If it does return true, do the binary search (which will clean the Frags
first) and cache the returned Frag. This is guarenteed to give you a valid
Fragment.
> 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 :-)
Sounds very nice. Try it with areFragDirty() check :-)
Cheers
Martin
This archive was generated by hypermail 2b25 : Fri Jul 06 2001 - 09:39:21 CDT