In the time I used this patch, a few things came up:

* I made the map-over-* methods the default. * 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.

Here's the patch fixing both these issues:

Cheers,

Andreas Fuchs asf@boinkor.net writes:

On 2006-02-21, Andreas Fuchs asf@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