[mcclim-devel] standard-tree-output-records using spatial-trees

[Christophe Rhodes]

Andreas Fuchs <asf at boinkor.net> writes:

> On 2006-02-21, Andreas Fuchs <asf at boinkor.net> wrote:
>> * map-over-* didn't check if the child truly intersects the region /
>> contains the point; this is enough only for ORs and regions that
>> are equal to their bounding rectangle.
>
> Thanks to Robert's tests with gsharp yesterday, we found out that this
> code wrongly assumes that output records are regions. ORs are just
> bounding rectangles, which means the code shouldn't call
> bounding-rectangle on any OR; also, we shouldn't use the ORs in region
> comparisons directly.

So the spatial trees code is now in CVS.

I'm mailing here so that we don't lose sight of various observations.

Firstly, Robert Strandh has observed that the new code makes gsharp
slower, and indeed I can confirm this: loading
Scores/rapsoden-sjunger.gsh on my workstation and hitting C-f and C-b
has noticeable lag, where it didn't before.  (It has always had
noticeable lag on my laptop, I should say; I would imagine that it's
now unbearable :-).

Secondly, Andy Hefner did some simple benchmarking of constructing the
output record; the code and some results are at
<http://paste.lisp.org/display/17633>.  I believe that this benchmark
measures the construction of the output record (and not any subsequent
interactions).  

In fact, both Robert's and Andy's observations are largely to do with
constructing the output record, rather than subsequent use; I believe
that gsharp redraws everything after each command, and so does not
reuse an output record that has been constructed.  Note that one might
expect a slowdown in this case, because constructing a tree is
probably O(N logN) as opposed to O(N) for a sequence; however, looking
for bottlenecks in constructing the spatial trees reveals some
low-hanging fruit.

Firstly, there is some error checking in spatial-trees:make-rectangle
which should be elided for McCLIM's use of it; it verifies that the
bounds are in numerical order.  Eliding that error check appears to
reduce the spatial tree overhead by about 30% (again, looking at
Andy's benchmark results) and makes MAKE-RECTANGLE no longer be the
bottleneck.

The top three entries in the profile are then

  seconds  |    consed   |    calls   |  sec/call  |  name  
--------------------------------------------------------------
     0.591 |           0 |  3,788,832 |  0.0000002 | SPATIAL-TREES-IMPL::MBR
     0.414 | 226,208,568 |  1,347,295 |  0.0000003 | RECTANGLES:MINIMUM-BOUND
     0.394 |           0 |  2,313,343 |  0.0000002 | RECTANGLES:AREA

MBR is quite hard to optimize, I think, in that it is basically slot
lookups.  It's possible that the CLOS dispatch is the bottleneck;
something to be tried is to despecialize the second argument in both
of the methods, from
  (defmethod mbr ((n spatial-tree-node) (tree spatial-tree))
  (defmethod mbr ((o leaf-node-entry) (tree spatial-tree))
to
  (defmethod mbr ((n spatial-tree-node) tree)
  (defmethod mbr ((o leaf-node-entry) tree)
as at least SBCL's clos can then further optimize the dispatch, as it
no longer needs to compute the class of the second argument.  I don't
know if this is actually the bottleneck, though.

RECTANGLES:MINIMUM-BOUND and RECTANGLES:AREA could be further
optimized, however, given that in McCLIM we know that we are dealing
with two-dimensional rectangles (while the spatial-trees library is
for general dimensionality).  I don't yet have a clear idea of how to
allow this specialization for particular uses while maintaining a
general-purpose fallback (without introducing more dispatch code which
will likely clobber any gains we make from the specialization).
Ideas?

(There are a couple of other minor problems: the spatial-trees asd can
in some circumstances cause ordinary users to trip after root has
installed it, as spatial-tree-viz is conditionally compiled; also,
delete-output-record on tree-output-records does not remove the entry
from the children cache hash table, which then grows without bound...)

Cheers,

Christophe