[prev in list] [next in list] [prev in thread] [next in thread] 

List:       koffice-devel
Subject:    KSpread: Style Storage
From:       Stefan Nikolaus <stefan.nikolaus () kdemail ! net>
Date:       2006-06-21 14:20:32
Message-ID: 200606211620.36957.stefan.nikolaus () kdemail ! net
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


Hello everybody,

the decoupling of the Cell and Format classes, I made some time ago, was a 
small step towards a new style storage and I want to finish this stuff. But I 
need some input from you before.

The plan is to use a tree to store the Styles - either an R+-Tree, with 
which's implementation I started, or a Quad-Tree or an oak ;-). I think, that 
we could exchange the backend (tree) later, if needed.

Now to the discussable thing: The Development Notes 
(http://websvn.kde.org/*checkout*/trunk/koffice/kspread/DESIGN.html) propose 
a splitting of the Style into smaller style pieces. As the current Styles are 
ref counted, I see no advantage in doing so. It would result in several 
lookups and slows things down. Therefore, I want to stay with the Style class 
in its current form.

Insertion and deletion of regions in the R+-Tree are no problem. The 
algorithms are described in the corresponding paper. Insertion will be used 
for the case, in which the user applies named styles (KSpread's CustomStyle 
or ODF's common styles) to a region; deletion to go back to the default cell 
style.
The common case, the direct altering of attributes, e.g. setting a border 
around a cell, would be a bit trickier, if we want to avoid to go the 
expensive 'lookup - delete - reinsert' way. But I think, that a specialised 
method for changing a region in the tree would be possible. The visitor 
pattern (which I only know by name ;-) would be helpful for this case.

The performance of my R+-Tree so far (it's not finished yet) on my Athlon64 
3000+:
Insertion of 100.000 rectangles is performant enough. It takes less than 2000 
ms. This could become worse. Looking at the ~6.000 ms the KoRTree needs.
Lookup is still a bit expensive: 100.000 points in 11.000 ms. But the same 
test with the KoRTree gives me times about 1.100 ms. So, there's room for 
optimization. I asssume, it's mainly due to the usage of QVector<QRectF> 
instead of a (basically) QVector<QRect*>. -> adjacent mem posititions -> 
higher chance for cache hits.
Column and row insertions/deletions are cheap IMHO: They consume about 50 ms 
with 100.000 leaves processed.

So, my actual question is before I waste my time: Do I oversee any benefit of 
the style splitting or anything else?

Bye,
Stefan

[Attachment #5 (application/pgp-signature)]

_______________________________________________
koffice-devel mailing list
koffice-devel@kde.org
https://mail.kde.org/mailman/listinfo/koffice-devel


[prev in list] [next in list] [prev in thread] [next in thread]