From: Joaquin Cuenca Abela (e98cuenc@free.fr)
Date: Mon Jan 06 2003 - 18:14:04 EST
Martin wrote:
>
> On Sat, 4 Jan 2003, Joaquin Cuenca Abela wrote:
>
> > I've find a way to get O(log(n)) as the worst case with any
> operation
> > on the piece table. I've put a description in
> > http://e98cuenc.free.fr/wordprocessor/piecetable.html
> >
> > The main affected class will be pf_Fragments. In the web
> page (still
> > not finished) I discuss all the gory details.
> >
>
> This is a extremely interesting Joaquin and is very, very cool :-)
>
> I start to see peicetable performance issues when dealling
> with documents
> of about 100 pages or larger right now. Particularly when typing or
> deleting. You new code would certainly fix those!
Before we all got too excited, I should say that I'm not sure if the
piece table is guilty of the performance penalty that you see in
documents of ~100 pages. I suspect the layout code and not the piece
table, but it's roughly the same problem, and the layout code can also
use the red-black tree modification that I suggest to get the same
Benefits.
That said, yes, it's an improvement :)
> I haven't looked through your code yet but I assume you rewritten the
> setNext()/getNext()/setPrev()/getPrev()/getPos() methods in the
> piecetable? Right?
Well, in fact I've reimplemented a whole piece table (but an extremely
simple one) to do my tests. The piece table that I've wrote can have
two "backends" to store the fragments (or pieces). I've implemented
the tree backend that I suggest in the web page, and also a
double-linked
list backend (to simulate what we have in AbiWord, but as you know,
that's
not a "perfect" simulation, see the web page for a disclaimer :)
Once I will finish the tunning of the tree backend, we can just drop
my piece table and put the backend in place of the pf_Fragments class
(I'm sure that only that is going to take a good amount of work...)
> Does the piecetable still logically look like a doubly linked
> list? Have
If you mean "can I go to the next and previous node in O(1) time", then
yes. But the worst time of a next or previous operation will be
O(log(n)),
and in average you should follow 2 pointers to get to the next or
previous
node instead of the current "follow 1 pointer operation".
As I explain in the page, that's the only operation that loses a little
bit
of speed, but it remains extremely fast whatever size the piece table
has.
> you done tests with some of the more complex structures in
> the piecetable,
> like tables?
No, my mini piece table only has text.
> In addition I just recently introduced footnote fragments
> which are actually embedded in blocks. These still don't work
> correctly yet.
> However when they do I'd like to see how hard it would be to
> merge these nto your code.
I will put it the other way around. How hard would be to merge my
code into your code? :)
I hope that most of the piece table machinery will remain intact.
Really,
I hope to just change fp_Fragments and its surrounding code.
> Can I continue to think of the piecetable as a doubly linked list
> logically?
Yes. But you should be aware that now you don't need to walk
the whole "pseudo-list" to find a given fragment (nor did you need
to deal with the big vector that mirrors the whole list, neither with
dirty frags, etc.)
> However I think the most pressing perfomance issue we
> currently have and
> would most like fixed before 2.0 is the problem of slow
> start-up on XFT
> builds on systems with lots of fonts. Is this something
> you're interested
> in fixing?
Oh, yes, that's embarrasing :)
I will take a look asap (if you see that I've done anything
more with the piece table, and I've not yet fixed that problem,
you can kick me :)
> Maybe we should look at what gtk 2.2 (with XFT built-in) does to make
> fonts avaialble and just use that. I haven't lookedat what
> gtk 2.2 does
> though.
Maybe I did something stupid when matching the fonts at startup, or
maybe it's just freetype sucking up all the startup time opening fonts
(I will bet for the first posibility).
Let's see.
Cheers,
This archive was generated by hypermail 2.1.4 : Mon Jan 06 2003 - 18:18:17 EST