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

List:       koffice-devel
Subject:    Re: KSpread bug (was Re: KOffice-1.2 release schedule)
From:       Philipp =?iso-8859-1?q?M=FCller?= <philipp.mueller () gmx ! de>
Date:       2002-03-25 18:18:32
[Download RAW message or body]

Am Montag, 25. März 2002 15:33 schrieb John Dailey:
> > No, not the perfect place. The cluster is some kind of a fixed map of
> > pointers (always x times y), regardless if filled or not. It doesn't help
> > you cycling through _filled_ cells. In comparison to KSpreadCell we would
> > even loose more memory, if we optimize for performance at this place.
>
> Isn't that exactly what we need?  It's a reference to any cell stored in
> arrays for fast, efficient access -- grouped in blocks so that we can skip
> past large areas of unused cells.
>
> Absolute worst case scenario is if the first and last cell in a column are
> used.  There's 127 cells left in the level2 cluster, 254 unused level1
> clusters, and then 127 empty level2 cluster cells before the last cell.  So
> we basically loop 508 times testing if cluster[blah][blah] == NULL.  Fast!
> How much more efficiency would we need?  I don't think it's worth it to put
> in up/down/left/right pointers and then maintain them.
>
> I'll go ahead and implement this -- there's lots of places where it would
> be useful.  Right now, there are lots of places in the cell layout code
> that loop through every cell in the spreadsheet and then test if it's in a
> particular column.
>
> -John

You are right John, the overhead of cycling through emtpy fields of a single 
cluster is not that performance relevant, especially if we can optimize them 
a bit.

And when you are at enhancing the cluster, maybe you can change it in a 
different way too.

Currently we have 2 fixed clusters (cluster1 with a size of 256^2 and cluster2 
with a size of 128^2. 
As I really want to have more than 2^15 rows (columns not that relevant), we 
should enhance it by another cluster, as growing the existing size of 
clusters are not preferable to get more rows (we should even reduce the 
size).

RFC (3 cluster level):
CLUSTER0: 
Default size: 16 x 16, can be reallocated up to 256 (or whatever we like) 
times 16 (so columns keeps the same).
Here I think we can afford reallocation. 

CLUSTER1:
fixed size of 64 x 64

CLUSTER2:
fixed size of 64 x 64

I think 64 x 64 is reasonable, it reduces memory overhead while still not 
necessary to allocate memory on each keytype.

Result:
- This will then lead to 2^16 columns and enough rows.
- Cycling through columns/rows will be faster too (with the new search 
function)
- Memory footprint is reduced heavily

- It will cost another calculation on each cell access.


Philipp

_______________________________________________
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]