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

List:       koffice-devel
Subject:    Re: KSpread - algorithm for fast and memory-saving storage of
From:       "Pascal A. Niklaus" <Pascal.Niklaus () unibas ! ch>
Date:       2003-04-25 7:16:31
[Download RAW message or body]

Norbert Andres wrote:

>On Thursday 24 April 2003 18:01, Alexander Neundorf wrote:
>  
>
>>I don't know how much your proposed algorithm would improve performance or
>>memory consumption compared with the current situation.
>>
>>But I think if you implement it it will be a quite big change to the
>>formatting code in kspread. In this sense I don't see an obvious advantage
>>of the now used hierarchical structure.
>>    
>>
>There would be one visible advantage: we can have something like "Select All". 
>Right now we would create about 65000*65000 cells right away. Creating 30000 
>cells take about 5-8 minutes. "Select All" is an often requested feature and 
>we found that layout areas would be one way to do it (Gnumeric does it this 
>way, too).
>
>If you think about performance: there won't be an advantage. Right now the 
>layout of a cell is represented by one pointer (and some obsolete flags). 
>Our performance problems are some place else - not in the way the layout is 
>stored.
>
>About memory: the style work is not completely finished if you compare with 
>OpenCalc. I plan to do that sometime.
>
>The memory consumption of the style solution and the area solution is similar. 
>If it were fully implemented the style solution would even use less memory if 
>every second cell has the same layout:
>A B A B A B
>This is hard to do with areas, you will end up with 6 different one, while 
>there were 2 with the OpenCalc style solution. 
>
Maybe I didn't get your point properly, but if you have 1 pointer per cell,

65'000 x 65'000 cells x 32bits/pointer = 16 Gigabytes just for the 
pointers !!!

Even for smaller sheets, having a pointer in each cell seems to be a 
waste of memory.
The "regions" and the tree wouldn't have to be saved - it's really just 
a way to represent the data in memory so that you don't need any pointer 
to formatting information in the cell. The tree itself can easily be 
rebuilt on loading and allows very fast access to the style because 
height scales with log(size) and most branches are shorter.

I'm using Excel all the time, and based on my experience, you can easily 
have millions of cells, but even then, usually a few hundred or thousand 
of regions would be enough to specify the formatting. So the memory 
advantage should be obvious.

Re "Select All": The obvious solution would be to select only a 
rectangular area as large as the part that really contains data... and 
as long as you don't put a single number in the bottom right corner... ;-)

Again, you guys that are familiar with KSpread's internas are in the 
position to decide... I just posted this idea because I read this 
comment in the source code and thought this idea may be useful.

Pascal

_______________________________________________
koffice-devel mailing list
koffice-devel@mail.kde.org
http://mail.kde.org/mailman/listinfo/koffice-devel
[prev in list] [next in list] [prev in thread] [next in thread]