simile-widgets/exhibit — pull request #11 by karger (2013-07-20 18:47:26+00:00)
Title: Modified databases index to use constant-time instead of worst case linear-time insertion.

Added a demo in demo directory "big" that can be used to test performance of other loaders.

The details: exhibit was using an index data structure that lets you
look up values given an subject and property "key" pair. It was
implemented as a two level map: a hashmap matched each subject to a
hashmap on each property, so the value-set for a given subject and
property was index[subject][property]. However, the value set itself
was stored as an *array*. As a result, inserting a new value
into the value set required scanning the entire array to make sure it
was not already there, which took linear time in the number of
values.

This was generally fine for indexing the "forward" direction of
statements, because the number of values associated with a given item
and property tended to be small. But we also indexed the reverse
direction which is much worse. For example, every item is given type
"Item" by default. Which means a statement was
indexed for every x. Which is fine in the forward direction since
there is only a single value. But we also index the reverse statment,
which has "type" as the subject and a value set consisting of every
single item, which had to be scanned (fruitlessly) on each new item
insert.

So by default, data loading took quadratic time.

The use of an array might conceivably offer storage/performance
benefits, but in exhibit all access to the contents is through methods
that imediately copy the array into a set (hashmap), removing those
benefits.