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

List:       koffice-devel
Subject:    Re: KSpread: Style Storage
From:       "Robert Knight" <robertknight () gmail ! com>
Date:       2006-06-21 18:46:51
Message-ID: 13ed09c00606211146i5695541dpa95fe42a7037371b () mail ! gmail ! com
[Download RAW message or body]

Hi Stefan,

I think splitting the style up is essential because style regions will overlap.

Example scenario:  I have several tables in a spreadsheet, one above
the other.  Each table has a different background colour.
After creating the tables, I decide that I want to change the font
used by all of them.  I then select the whole region (including all of
the tables) and select a new font.

With the Style class as it is, it would be necessary to iterate over
all of the styles in the region and modify each of them.  Additional
complications would be introduced if a style region intersected the
boundary between the selected and unselected areas of the sheet.  This
is at least an O(n) operation.

If we split the style up so that a style can specify only a subset of
the available properties, then it would only be necessary to insert a
single new Style instance covering the whole area which just specifies
the new font.  This gives us a low memory cost which is a big reason
for replacing the Style handling system.  Obviously this would require
a way of handling the priority of  multiple styles which cover the
same cell and specify the same property - but a simple counter which
is incremented for each new style would probably be suitable.  In
order to lookup a property for a cell, it will be necessary to look at
each style which covers a particular region and select the 'newest'
style instance which specifies that property.  However, it would be
possible to cache a merged style for a particular cell (which is what
Gnumeric does).

Regarding the data structure used to store the data, my quad-tree
implementation seems to give better performance time-wise (650ms for
100,000 insertions , 1100ms for 100,000 lookups on a 1.7Ghz P4 and
insertion / lookup is O(log(n)).  Insertion / removal of rows and
columns is O(n) - but this is a much less common operation).  Memory
usage for just the quad-tree (ignoring the size of Style instances) is
5.6MB for the above example and there is room for reduction.  The
gains in memory usage over just storing a pointer for each cell depend
hugely on how effectively the application makes use of the new style
system - ie. the application should strive to use the smallest number
of individual regions as possible.  Of course, all this relies on me
finishing the implementation soon.

I agree about a generic interface to the style storage system though -
this is hugely important.

Mine looks something like this in pseudo-code:

class RegionMap<T>
{
  RegionMap(int width, int height)
  insertRegion(QRect region, T* value)
  QList< RegionValuePair > regionsContaining(QPoint point)

  insertRows( int insertBefore , int count )
  insertColumns( int insertBefore , int count)
  QList< T* > deleteRows( int start , int count )  // returns elements
no longer in tree
  QList< T* > deleteColumns( int start , int count ) // returns
elements no longer in tree
}

... and some other methods to facilitate garbage collection would
probably be a good idea as well.

Regards,
Robert.

On 21/06/06, Stefan Nikolaus <stefan.nikolaus@kdemail.net> wrote:
> 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
>
>
> _______________________________________________
> koffice-devel mailing list
> koffice-devel@kde.org
> https://mail.kde.org/mailman/listinfo/koffice-devel
>
>
>
>
_______________________________________________
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]