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

List:       koffice-devel
Subject:    PointStorage performance (was: Re: koffice/kspread)
From:       Stefan Nikolaus <stefan.nikolaus () kdemail ! net>
Date:       2007-01-10 17:14:52
Message-ID: 200701101814.55959.stefan.nikolaus () kdemail ! net
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


On Wednesday, January 10, 2007 05:14:06 PM Tomas Mecir wrote:
> Looks good, as far as I can tell. Didn't look through the PointStorage
> thing too much, so I hope you have that one tested well.

The basic functionality, insertion and lookup, is tested well enough. For the 
specialties, like column insertions, some more tests are necessary, but it's 
not used by the ValueArray either.

> Is your PointStorage efficient enough for all of the following cases?
> - sparse matrix with lots of empty rows/columns
> - sparse matrix, where most/all columns/rows contain at least one value
> - matrix which contains a lot of values, all concentrated to upper left end
> - almost completely filled matrix
>
> Because any of these can happen quite frequently (especially with
> selections that span entire rows/columns).

It's a compressed row sparse matrix. Hence matrices with lots of empty columns 
are no problem at all. Empty rows are represented by repeated values in the 
m_rows vector.
I've added two scenarios to the benchmark, that covers the lookups in 
column/row selections. The needed time per operation is of the order of 100 
ns. Good enough, I think. The Cluster benchmark, which can be seen as dense 
matrix (ignoring the two levelled array), produces times of the order of 10 
ns. So, we have to pay one order of time for the reduced memory storage. This 
is for the case where we have iterate over each column and row explicitly. 
Not many functions will do this anyway. Maybe it's even completely avoidable 
as you have access to the row and column also for the index-based iteration 
over the non-empty entries.

The more common case, where we just iterate over the non-empty entries should 
beat the dense matrix behavior easily - benchmark's still to be written 
though.

Regards,
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]