<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
Hi,
<div class=""><br class="">
</div>
<div class="">
<blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"></span>Sounds like an interesting book =) It's a shame we had a<br class="">
LibreOffice conference in Denmark a couple of years back and would have<br class="">
been interesting to meet up and compare spreadsheet design notes. Perhaps<br class="">
you could join one of our Hamburg hackfests at some stage.</blockquote>
<div class=""><br class="">
</div>
It’s a good read with lots of different design considerations. There’s also a bunch of <a href="https://www.itu.dk/people/sestoft/itu/bachelorprojekter.html" class="">bachelor</a> and <a href="https://www.itu.dk/people/sestoft/itu/specialer.html" class="">master</a> thesis
projects that investigate some of the suggestions from the book.</div>
<div class=""><br class="">
</div>
<div class="">I would be delighted to join one of the hackfests if time allows. Is there a schedule available somewhere?</div>
<div class="">
<div class=""><br class="webkit-block-placeholder">
</div>
<div class="">
<blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"></span>Easy - just reply to the mail - and be aware it's permanently public.</blockquote>
<br class="">
</div>
<div class="">I see. Easy indeed.</div>
<div class=""><br class="">
</div>
<div class="">
<blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"></span>You might think so - but I couldn't possibly comment =) It would<br class="">
be interesting too do some measurements and benchmarking here I think - we<br class="">
have our own numbers, but some 3rd party looking at this might find some<br class="">
good things.<br class="">
</blockquote>
<div class=""><br class="">
</div>
<div class="">It is definitely worth a try at some point :)</div>
<br class="">
<blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"></span>Ultimately I'd be really interested in how your compiled & jitted<br class="">
C# stuff works too, you can emit IL rather than C-strings (as we do for CL)<br class="">
so perhaps it is also rather fast.</blockquote>
</div>
<div class=""><br class="webkit-block-placeholder">
</div>
<div class="">The book provides all the details but there are <a href="https://www.itu.dk/people/sestoft/publications.html" class="">a few papers</a> on it as well (search for sheet-defined function).</div>
<div class=""><br class="">
</div>
<div class="">In essence, a dependency graph is constructed from the single output cell of the SDF and analysed. There are code generators available for each kind of expression in the language which are called as needed to generate the code as specified by
the cells in the dependency graph. Extra optimisations are used to decrease packing/unpacking of internal structures and to generate local variables for things that are used more than once. The code is emitted via the <a href="https://docs.microsoft.com/en-us/dotnet/api/system.reflection.emit.ilgenerator?redirectedfrom=MSDN&view=netframework-4.7.2" class="">ILGenerator</a> class.</div>
<div class=""><br class="">
</div>
<div class="">SDF compilation performance has not been an issue for me thus far.</div>
<div class=""><br class="webkit-block-placeholder">
</div>
<div class="">
<blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"></span>Interesting. Anyhow I'd suggest that LibreOffice is a great code-base<br class="">
to read through to update Peter's book - we're wrestling mightily with the<br class="">
data structures to make it cleaner, faster and more sensible while staying<br class="">
fully compatible with Excel.</blockquote>
<br class="">
</div>
<div class="">I will relay that to my supervisor :) I did skim through your dependency graph code at some point.</div>
<div class=""><br class="">
</div>
<div class="">
<blockquote type="cite" class=""><span class="Apple-tab-span" style="white-space: pre;"></span>I'm also curious if there are good spreadsheet conferences out there,<br class="">
I attended EUSPRIG in the past which was interesting - any recommendations ?</blockquote>
<br class="">
</div>
<div class="">I know of EUSPRIG as well and their <a href="http://eusprig.org/horror-stories.htm" class="">horror stories</a> although I have not attended. Personally, I have mainly attended conferences on parallelism and concurrency as well as (declarative)
programming language implementation, which are the two main parts of my PhD.</div>
<div class=""><br class="">
</div>
<div class="">Actually, I did go through a list of about 100 references in a survey paper I wrote on spreadsheet technology, picking out the venues for papers on the subject. They should be good venues for literature searches on spreadsheets or for publication.</div>
<div class=""><br class="">
</div>
<div class="">
<ul class="MailOutline">
<li class=""><i class="">International Conference on Software Engineering</i> (ICSE) - lots of spreadsheet papers published here.</li><li class=""><i class="">Principles and Practice of Declarative Programming</i> (PPDP)</li><li class=""><i class="">International Conference on Functional Programming</i> (ICFP) - mainly due to the functional nature of spreadsheets and SDFs.</li><li class=""><i class="">Journal of Functional Programming</i> (JFP) - ditto.</li><li class=""><i class="">Commercial Users of Functional Programming</i> (CUFP) - ditto.</li><li class=""><i class="">European Symposium on Programming</i> (ESOP)</li><li class=""><i class="">Automated Software Engineering</i> (ASE)</li><li class=""><i class="">Journal on Systems and Software</i></li><li class=""><i class="">Human Centric Computing Languages and Environments</i></li><li class=""><i class="">Journal of Visual Languages and Computing</i></li><li class=""><i class="">Foundations on Software Engineering</i> (FSE)</li><li class=""><i class="">Visual Languages and Human-Centric Computing</i> (VL/HCC) - lots of spreadsheet papers published here as well.</li><li class=""><i class="">Transactions on Software Engineering</i> (TSE)</li><li class=""><i class="">ACM Transactions on Software Engineering Methodology</i></li><li class=""><i class="">International Symposium on End-User Development</i> (IS-EUD)</li></ul>
</div>
<div class=""><br class="webkit-block-placeholder">
</div>
<div class="">Note that some of these journals/conferences may not be active anymore.</div>
<div class=""><br class="webkit-block-placeholder">
</div>
<div class="">Do you run any of the generated OpenCL kernels in parallel or do you run a normal sequential recalculation and call the kernel code as necessary? I would suspect the latter given the information you have provided so far :)</div>
<div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div style="color: rgb(0, 0, 0); font-variant-caps: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<br class="Apple-interchange-newline">
Mvh/Best regards,</div>
<div style="color: rgb(0, 0, 0); font-variant-caps: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<font face="Consolas" class=""><br class="Apple-interchange-newline">
<b class="">Alexander Asp Bock</b>, PhD student</font></div>
<div style="color: rgb(0, 0, 0); font-variant-caps: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<a href="https://computerscience.wikit.itu.dk/" class=""><font face="Consolas" class="">Computer Science Department</font></a></div>
<div style="color: rgb(0, 0, 0); font-variant-caps: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">
<a href="http://en.itu.dk/" class=""><font face="Consolas" class="">IT University of Copenhagen</font></a></div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div><br class="">
<blockquote type="cite" class="">
<div class="">On 7 Sep 2018, at 11.33, Michael Meeks <<a href="mailto:michael.meeks@collabora.com" class="">michael.meeks@collabora.com</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div class="">Hi there,<br class="">
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>So - opening this to a wider audience with minor edits - and<br class="">
more comments in-line:<br class="">
<br class="">
On 03/09/18 16:21, Alexander Bock wrote:<br class="">
<blockquote type="cite" class="">Sorry for the delay in getting back to you.<br class="">
<br class="">
Michael wrote:<br class="">
<blockquote type="cite" class="">First - great to meet you; and good to find another team interested in<br class="">
spreadsheets. The LibreOffice Calc team has been working hard to really<br class="">
improve the state of the art wrt. spreadsheet representations - at least<br class="">
in the form of things that we can feasibly re-architect towards while<br class="">
continuing to ship a working product =) - not trivial.<br class="">
</blockquote>
<br class="">
Likewise :) we are still a relatively small crowd. I was very pleased to<br class="">
read about all the improvements from the slide materials to get a better<br class="">
idea of all the improvements that have been made.<br class="">
<br class="">
<blockquote type="cite" class="">Isn't that implementation decision such 'fun' =) we work quite hard to<br class="">
kill implicit intersection in our internal compiled form of formulae -<br class="">
that helps have precise dependencies: so =SIN(A:A) doesn't end up with<br class="">
some massive heap there.<br class="">
</blockquote>
<br class="">
Ugh…I’m very glad Funcalc does not support it. I would be very<br class="">
interested to know more about the internal compiled formulae if you have<br class="">
any resources on that. Funcalc is interpreted except for the<br class="">
sheet-defined functions (SDFs) which are compiled on-the-fly to .NET<br class="">
bytecode and executed by the JIT compiler.<br class="">
<br class="">
Here’s a picture of an SDF for rolling an n-sided die to get a better<br class="">
idea of how it works. Cell A1 defines the function. The green cells are<br class="">
zero or more input cells, the light blue cells (not shown) are<br class="">
intermediate calculations and the blue cell is the single output cell of<br class="">
the function. The pink border stems from the fact that SDFs can only be<br class="">
defined on special “function sheets”.<br class="">
<br class="">
<blockquote type="cite" class="">Having said that - reading funcalc - it seems your dependency<br class="">
structures are a cell <-> cell(s) mapping - not special casing range<br class="">
references - which is unusual. I personally think that one of the big<br class="">
errors of spreadsheet design is separating dependencies from formulae<br class="">
but ... ;-) These days we do group dependency tracking which makes life<br class="">
hugely more efficient.<br class="">
</blockquote>
<br class="">
To be more precise, it is indeed a cell-to-cell mapping although the<br class="">
graph is implicitly defined, i.e. there is no omniscient, global data<br class="">
structure. We do special case areas/ranges for supported cells (i.e. the<br class="">
inverse direction of the dependency graph) which does a lot of caching<br class="">
and cleverness to remain efficient. For each cell, we can still query<br class="">
its dependencies and supported cells. For the full details, it is<br class="">
probably better to refer you to my supervisor’s book “Spreadsheet<br class="">
Implementation Technology”<br class="">
<<a href="https://www.amazon.com/Spreadsheet-Implementation-Technology-Basics-Extensions/dp/0262526646" class="">https://www.amazon.com/Spreadsheet-Implementation-Technology-Basics-Extensions/dp/0262526646</a>>.<br class="">
There may be an older version available somewhere on his site<br class="">
<<a href="https://www.itu.dk/people/sestoft/" class="">https://www.itu.dk/people/sestoft/</a>>.<br class="">
</blockquote>
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>Sounds like an interesting book =) It's a shame we had a<br class="">
LibreOffice conference in Denmark a couple of years back and would have<br class="">
been interesting to meet up and compare spreadsheet design notes. Perhaps<br class="">
you could join one of our Hamburg hackfests at some stage.<br class="">
<br class="">
<blockquote type="cite" class="">I was actually considering that we should track cell arrays/groups<br class="">
explicitly especially for dependency management, instead of finding them<br class="">
when necessary which is what I do in my tool currently. However, I am<br class="">
unsure how well it will fit with the current infrastructure.<br class="">
<br class="">
<blockquote type="cite" class="">Hmm - so do you handle =RAND() for example - it's trivial using<br class="">
=INDIRECT(ADDRESS(RAND()...)) to build dependency graph mutating horrors<br class="">
- or just some vlookup on a semi-random cell range.<br class="">
</blockquote>
<br class="">
Good point. Simply by not having similar “problematic” functions<br class="">
available. I guess that is one benefit of working with a research<br class="">
prototype…I believe my supervisor did not want to deal with those<br class="">
issues, as important as they may be, since the primary proof-of-concept<br class="">
for Funcalc was sheet-defined functions.<br class="">
<br class="">
<blockquote type="cite" class="">This is all really interesting. I'd prefer we move this mail to the<br class="">
public LibreOffice developer list if that's ok (?) may I re-post this<br class="">
mail there ? No doubt that would get more input - and we can CC more<br class="">
people outside Collabora that would be curious.<br class="">
</blockquote>
<br class="">
That is perfectly fine. Do I need to respond there then? It’s been a<br class="">
quite a while since I’ve dealt with mailing lists :)<br class="">
</blockquote>
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>Easy - just reply to the mail - and be aware it's permanently public.<br class="">
<br class="">
<blockquote type="cite" class="">
<blockquote type="cite" class="">In addition - you should really check out Kohie's MDDS library - the<br class="">
Multi-Dimensional-Data-Structures, which is the C++ template magic of<br class="">
our core, and Kohei has his own new-gen spreadsheet prototype called<br class="">
'Orcus' that we re-use pieces of in LibreOffice.<br class="">
</blockquote>
<br class="">
Ah yes, I saw it in one of the slides. Very interesting stuff and cool<br class="">
use case! I’ll make sure to look into it.<br class="">
</blockquote>
...<br class="">
<blockquote type="cite" class="">
<blockquote type="cite" class="">Oh - and, another thing - in many of the cases that we can parallelize<br class="">
LibreOffice 6.1 has some great performance characteristics vs. Excel by<br class="">
wall-clock time measurements.<br class="">
<br class="">
I'm wondering if you've measured any of that ?<br class="">
</blockquote>
<br class="">
Is this parallelisation via OpenCL or threads or both?<br class="">
</blockquote>
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>Both - but I think the representation wins and CPU parallelism<br class="">
should be particularly interesting in 6.1.<br class="">
<br class="">
<blockquote type="cite" class="">We haven’t measured our tools against Excel. In part because felt the<br class="">
comparison would be hard to attribute to specific optimisations without<br class="">
taking into account all the internals of both pieces of software<br class="">
(Funcalc is written in C#, not C/C++). Additionally, we are not trying<br class="">
to beat Excel’s speed but use Funcalc as a research platform for<br class="">
experimentation (we might have used LibreOffice Calc instead).<br class="">
<br class="">
My initial guess would be that Excel will easily beat at least the<br class="">
sequential execution since it has enjoyed ~25 years of optimisations<br class="">
(barring issues related to a 25 year old codebase). It would definitely<br class="">
be interesting to compare wall-clock time measurements anyway,<br class="">
especially if Excel already has a feature for getting those numbers.<br class="">
</blockquote>
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>You might think so - but I couldn't possibly comment =) It would<br class="">
be interesting too do some measurements and benchmarking here I think - we<br class="">
have our own numbers, but some 3rd party looking at this might find some<br class="">
good things.<br class="">
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>Ultimately I'd be really interested in how your compiled & jitted<br class="">
C# stuff works too, you can emit IL rather than C-strings (as we do for CL)<br class="">
so perhaps it is also rather fast.<br class="">
<br class="">
<blockquote type="cite" class="">So far, we have modified the LibreOffice Calc benchmark spreadsheets<br class="">
<<a href="https://gerrit.libreoffice.org/gitweb?p=benchmark.git;a=tree" class="">https://gerrit.libreoffice.org/gitweb?p=benchmark.git;a=tree</a>> to run in<br class="">
Funcalc (by converting functions like PEARSON and SLOPE to sheet-defined<br class="">
functions) and have only compared speed-ups between sequential and<br class="">
parallel versions of Funcalc.<br class="">
</blockquote>
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>Interesting. Anyhow I'd suggest that LibreOffice is a great code-base<br class="">
to read through to update Peter's book - we're wrestling mightily with the<br class="">
data structures to make it cleaner, faster and more sensible while staying<br class="">
fully compatible with Excel.<br class="">
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>I'm also curious if there are good spreadsheet conferences out there,<br class="">
I attended EUSPRIG in the past which was interesting - any recommendations ?<br class="">
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span>All the best,<br class="">
<br class="">
<span class="Apple-tab-span" style="white-space:pre"></span><span class="Apple-tab-span" style="white-space:pre"></span>Michael.<br class="">
<br class="">
<blockquote type="cite" class="">*Alexander Asp Bock*, PhD student<br class="">
Computer Science Department <<a href="https://computerscience.wikit.itu.dk/" class="">https://computerscience.wikit.itu.dk/</a>><br class="">
IT University of Copenhagen <<a href="http://en.itu.dk/" class="">http://en.itu.dk/</a>><br class="">
</blockquote>
-- <br class="">
<a href="mailto:michael.meeks@collabora.com" class="">michael.meeks@collabora.com</a> <><, GM Collabora Productivity<br class="">
Hangout: <a href="mailto:mejmeeks@gmail.com" class="">mejmeeks@gmail.com</a>, Skype: mmeeks<br class="">
(M) +44 7795 666 147 - timezone usually UK / Europe<br class="">
<span id="cid:4CD93E78-A783-44FB-9729-CC93DA3C9229@webspeed.dk"><Attached Message Part.png></span></div>
</div>
</blockquote>
</div>
<br class="">
</div>
</body>
</html>