Re: log(n) PT works!!!

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:26:39 2009