Eureka!
Martin Budden
formatting performance", but that investigation resulted in an insight
that gives a *significant* speedup in the rendering of tables in
TiddlyWiki. (The benchmark table discussed below takes 1300ms instead
of 2800ms and the periodic table at
http://www.tiddlywiki.com/#PeriodicTable takes 130ms instead of 700ms).
Details of the investigation are below. You can skip to the end for the
details of the performance improvement. Note that the performance
improvement not only speeds up rendering tables, but it speeds up
wikification generally.
==Investigation into table formatting performance==
There have been a number of comments/complaints in this group about
native TiddlyWiki tables being slow, and how HTML tables were much
faster.
I've done some instrumentation and made some measurements. My
"benchmark" table is a 25 row by 36 column table. Each row consists of
36 cells each containing a single letter a..zA..J. The first row is a
header row.
1) Time to render using a native table within TiddlyWiki: 2800ms
2) Time to render using embedded HTML within TiddlyWiki: 80ms
So using embedded HTML is about 35 times faster than using native
tables.
So why is this? Well, a native table is rendered using the "table"
formatter. The operations performed during rendering include:
a) compilation of regular expressions
b) execution of regular expressions to search the wiki text for table
delimiters
c) parsing the matched text
d) creation and manipulation of DOM elements.
There has been some suggestion that step (d) is a bottleneck, and that
using innerHTML would speed up table rendering.
To test this assumption I created the following macro, which directly
creates the benchmark table by direct DOM manipulation (thus avoiding
steps a-c):
config.macros.tableMacro = {};
config.macros.tableMacro.handler = function(place,macroName,params)
{
var now, then = new Date();
var table = createTiddlyElement(place,"table");
var rowContainer = createTiddlyElement(table,"tbody");
for (var ri=0;ri<25;ri++)
{
var rowElement =
createTiddlyElement(rowContainer,"tr",null,(ri&1)?"oddRow":"evenRow");
for (var ci=0;ci<36;ci++)
{
var cell = createTiddlyElement(rowElement,ri==0?"th":"td");
createTiddlyText(cell,String.fromCharCode(ci+(ci<26?97:65-26)));
}
}
now = new Date();
createTiddlyText(place,"Table display in " + (now-then) + "
milliseconds");
}
This rendered the table in about 250ms. This agrees with measurements
elsewhere ( http://www.quirksmode.org/dom/innerhtml.html ) that DOM is
about 3 times slower than innerHTML.
However it also shows that the DOM manipulation is not the bottleneck
in table rendering. If table rendering was converted to using
innerHTML, this table would take at best (2800-250+80)ms, that is
2630ms. Actually I suspect it would take longer since the matching of
HTML beginning and end tags (which is done in compiled code in DOM)
would have to be done in interpreted JavaScript.
To summerise, the results are:
1) Time to render using a native table within TiddlyWiki: 2800ms.
2) Time to render using embedded HTML within TiddlyWiki: 80ms.
3) Time to render using direct DOM manipulation within TiddlyWiki:
250ms.
4) Estimated (best case) time to render using innerHTML in TiddlyWiki:
2630ms.
So converting the table formatter to use innerHTML with speed up table
rendering by about 6%.
==The performance improvement==
This got me thinking about what was the real bottleneck. I tried other
optimisations which had little effect and all indications were that the
real bottleneck was the execution of the regular expressions. And this
is where I had the Eureka moment. In the subwikify function there are
two matches performed, one to match for the terminator, and another to
match for formatters. Here's the insight: currently the format match
matches to the end of the string, but it only has to match up to the
terminator.
The code change is to match for the terminator first, and then to
perform the format match on the substring up to the terminator match.
Here's the code:
Wikifier.prototype.subWikify = function(output,terminator)
{
// Temporarily replace the output pointer
var oldOutput = this.output;
this.output = output;
// Prepare the terminator RegExp
var terminatorRegExp = terminator ? new RegExp("(" + terminator +
")","mg") : null;
do {
// Prepare the RegExp match positions
this.formatter.formatterRegExp.lastIndex = this.nextMatch;
if(terminatorRegExp)
terminatorRegExp.lastIndex = this.nextMatch;
// Get the first matches =======changes are the next two lines
var terminatorMatch = terminatorRegExp ?
terminatorRegExp.exec(this.source) : null;
var formatterMatch =
this.formatter.formatterRegExp.exec(terminatorMatch?this.source.substr(0,terminatorMatch.index):this.source);
...
Martin
PS I have some other improvements in my bag of tricks, but they are
smaller (a few percentage points improvement) and I want to do some
more work on them.
Jeremy Ruston
Cheers
Jeremy.
--
Jeremy Ruston
mailto:jer...@osmosoft.com
http://www.tiddlywiki.com
