[Libreoffice] Calc - a better design ...

Hi Kevin,

On Wed, 2011-07-27 at 06:56 -0400, Kevin Hunter wrote:
> At 6:07am -0400 Wed, 27 Jul 2011, Michael Meeks wrote:
> > but IMHO -the- fundamental design problem with calc, is something
> > quite banal - the concept that a spreadsheet is built from cells:
> > without breaking that basic misconception I don't think we can do
> > any of the really interesting space / time optimisations we need to
> > do.
>
> Can you elaborate a little on this fundamental design flaw ?

        Hah - so, yes - and not easily - I'd really need a whiteboard.

>  As a naive and unfortunately focused elsewhere personality, I don't
> immediately know of a better model for creating a spreadsheet.

        So - of course, the first thing to say is that (at a first pass), I'd
want the UI to continue to look the same - all that would change would
be the underlying model.

>   Is it "just" a problem of sparsity?  Or is there a much more
> sophisticated method for memory sharing of various similar cell
> attributes, perhaps analogous to CSS?

        Here is the thing - since we work on a per-cell basis, all of our type
checking, and formula adaptation, and storage, and dependencies etc. are
all ultimately per-cell based. This (crudely) means that we have an O(n)
where n is the number of cells in vast numbers of operations where we do
not want it. It also tends to explode storage and computation time
around dependencies - which is a substantial cost.

        NB. much of this is quite normal for a spreadsheet FWIW, I believe
Excel is not completely dis-similar; however I think we can do better
with much improved (much more complex / slow) data structure design that
will ultimately be far faster to execute.

        Take a banal example; when we do a SUM() of a million rows containing
plain doubles, we would want to (at root) have a function that [ in the
ideal case ] does:

        double sum (double *array, sal_Int64 nItems);

        Which we can shove onto a gpu, multi-thread if nItems is big, etc. etc.
unfortunately approaching this limit is basically impossible in calc.
Instead for this case we would do a very slow, pointer-chasing iteration
over a million scattered ScCell's - we would do type checking - to
ensure that each one was a double, and only then would we add /
accumulate them.

        Of course none of that can be pushed to a GPU, none of it can be SIMD
accelerated, and threading it is rather hard.

        Now ... if we stored contiguous spans of identically typed items [ ie.
a column of doubles ], as value runs in our data structures; currently
we (amazingly) have arrays of (row/cell*) pairs incidentally. Then we
could push a lot of branch-heavy, expensive type checking, and lots of
pointer chasing outside the main-loop, we'd also use rather less memory.

        That's fine for doubles of course; but the really huge wins come from
an entirely new model of dependencies and areas containing formulae - I
propose only storing a base formula, and an iterator to describe how
that formula changes down a row: to compress an entire column of
formulae to a single formula. Futhermore on top of that substantially
discarding the existing dependency mechanism such that a single-cell
change in a contiguous range of doubles would have a shared broadcast on
that whole range (with the specific detail of what cell changed), such
that that could be turned into a specific row (or row range) to
re-compute in any dependent by comparing the base formula, plus it's
iterator with the range that changed ;-) 

        So - in a nutshell, compressing and making explicit the vast amount of
duplication and uniformity present in all big spreadsheets.

        IMNSHO if we can get to this world, we can kick Excel's backside in the
performance and scalability arena, storage-wise we can become as tiny as
we should be :-) and thus ideally we can also start to address far
larger and more interesting data-sets.

        Anyhow - as text, this is not terribly convincing; drawing on a
whiteboard would be more so, and with lots of working code - even more
so ;-) I keep hoping to have time to play with ixion with Kohei in this
regard.

        ATB,

                Michael.

-- 
 michael.meeks@novell.com  <><, Pseudo Engineer, itinerant idiot