Re: log(n) PT works!!!

Very impressive work is all I can say. You all rock.

  Marc

On Thu, 2009-08-20 at 22:26 +1000, Martin Sevior wrote:
> HI Everyone,
> Here are the results of inserting large tables in
> trunk vs the lognpt branch.
> lognpt trunk
> cols, rows, millisecs cols, rows, millisecs
> 20, 50, 148 20, 50, 202
> 20, 100, 304 20 , 100, 556
> 20, 200, 683 20, 200, 2069
> 20, 300, 1232 20, 300, 7602
> 20, 400, 1772 20, 400, 23051
> 20, 500, 2482 20, 500, 46021
> 20, 600, 3318
> 20, 800, 5405
> 20, 1000,8284
>
> I ran out of patience for tables greater the 20x500 for trunk.
>
> Anyway you can see that lognpt is quite usable up to 20x1000 and is
> over an order of magnitude faster at 20*400 and larger.
>
> Cheers
>
> Martin
>
> On Wed, Aug 19, 2009 at 12:52 PM, Martin Sevior<msevior@gmail.com> wrote:
> > Hi everyone,
> > With this commit abiword works with the log(N)
> > PieceTable designed by Joaquin Cuenca Abela and mostly implemented by
> > our Google Summer of Code student Aditya Manthramurthy. I've provided
> > many bug fixes.
> >
> > We've simply re-implented the low level src/text/ptbl/xp/pf_Frag, and
> > pf_Fragments methods with equivalents from Joaquin's Red/Black tree.
> >
> > Our pf_Frag's used to be in a doubly linked list with an ordered
> > vector. This allowed searches in log(n) times but inserts and deletes
> > happen in linear time.
> > Operations like insert table and large pastes required time
> > proportional to N^2 where N is the size of the document.
> >
> > Now they reside in Joaquin's red/black tree. This allows
> > searches/inserts/deletes in logorithmic time.
> >
> > This all works very nicely from my tests so far. More tests and
> > timings to follow.
> >
> > To see more about why this is very exciting have a read of these two links.
> >
> > http://www.abisource.com/wiki/AbiWordDevelopment#PieceTable_speedups.
> >
> > http://e98cuenc.free.fr/wordprocessor/piecetable.html
> >
> > With this in place we have the capability to scale to tables of many
> > thouasands of rows of tables and document sizes ten times bigger than
> > we can comfortably handle today.
> >
> > Cheers!
> >
> > Martin
> >
> >
> > Author: msevior
> > Date: 2009-08-19 04:28:36 +0200 (Wed, 19 Aug 2009)
> > New Revision: 27746
> >
> > Modified:
> > abiword/branches/lognpt/src/text/ptbl/xp/pf_Frag.cpp
> > abiword/branches/lognpt/src/text/ptbl/xp/pf_Frag.h
> > abiword/branches/lognpt/src/text/ptbl/xp/pf_Frag_Text.cpp
> > abiword/branches/lognpt/src/text/ptbl/xp/pf_Fragments.cpp
> > Log:
> >
> > Allow the Text Fragments to change in size and adjust the tree when then do.
> >
> > ABiWord works with log(n) PT now!!!!!!!!
> > Woot! Woot!
> >
Received on Thu Aug 20 14:37:52 2009