Re: log(n) PT works!!!

HI Joaquin,
                 Thanks! Awesome work with your original
implementation too. It didn't take too much manipulation to make it
fit.

To answer your question each consists of 4 Frags. The cell trux,
,block strux a fmt frag and an endcell strux. So a 20000 cell table
has 80,000 fragments. However abiword is doing a lot more than simply
inserting data into a PieceTable on each cell creation. It is also
creating an populating a cell layout and cell container and linking it
into a table.

However there is clearly some more performance improvement to be had.
The time from 20x50 to 20x100 increases almost linearly, The step
from 20x100 to 20x200 shows the beginning of trend which by 20x1000
shows a quadratic increase in time.

We will need to do some profiling to find out what is causing the N^2
dependence.

We should be able to get this NLog(N) time eventually.. Scaling from
the speed for inserting 20x100 that would imply a 20x1000 insert of
around 3 seconds as opposed to 8 seconds.

Cheers

Martin

it you look
On Fri, Aug 21, 2009 at 12:37 AM, Joaquin Cuenca
Abela<e98cuenc@gmail.com> wrote:
> Awesome work!
>
> Martin, do you how many pieces are there with a a table of 1000 rows
> and 20 cols? I remember the times were in the single digit nanoseconds
> (10^-6), so to get up to 8s we're talking here at around 8M pieces. As
> I suspect there are less pieces than that there is maybe some
> inefficiency that can be fixed to further improve the speed.
>
> Cheers,
>
> On Thu, Aug 20, 2009 at 2:37 PM, J.M. Maurer<uwog@uwog.net> wrote:
>> 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!
>>> >
>>
>>
>
>
>
> --
> Joaquin Cuenca Abela
>
Received on Fri Aug 21 16:48:28 2009