Re: Fwd: Re: Severe performance regression with latest CVS sources?

Paolo Amoroso <amoroso@xxxxxxxxx> writes:

> Christophe Rhodes <csr21@xxxxxxxxx> writes:
>> I think the edges-from should be in the graph node output record.  I'm
>> not entirely sure how to get at one of those, but you could start by
>> inspecting clim:*application-frame* from the slime inspector, finding
>> the listener interactor pane, finding its output history, and looking
>> at the output records in there.
>
> Here is the interactor's output history just after generating the
> graph:
>
> An object.
>  [type: CLIM:STANDARD-TREE-OUTPUT-HISTORY]
> --------------------
> Class: #<STANDARD-CLASS CLIM:STANDARD-TREE-OUTPUT-HISTORY {5837B955}>
> Slots:
> STREAM = #3=#<CLIM:INTERACTOR-PANE CLIM-LISTENER::INTERACTOR {59E3C0DD}>
> COORDINATES = #(0 0 4950 12357)
> PARENT = NIL
> X = 0
> Y = 0
> IN-MOVING-P = NIL
> CHILDREN = #<SPATIAL-TREES-IMPL::R-TREE 
> #<SPATIAL-TREES-PROTOCOL:SPATIAL-TREE-LEAF-NODE 
> (#S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(81,24679/2) - 
> (144,24709/2)> :DATUM #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {58A7222D}>) 
> #S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(81,12339) - (724,12357)> 
> :DATUM #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {59F0EA95}>) 
> #S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(0,24679/2) - 
> (81,24709/2)> :DATUM #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {59F0DCD5}>) 
> #S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(0,17) - (4950,24645/2)> 
> :DATUM #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {59D6D0D5}>) 
> #S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(81,0) - (360,15)> :DATUM 
> #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {59D6D0C5}>) 
> #S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(81,0) - (724,17)> :DATUM 
> #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {59D6D0A5}>) 
> #S(SPATIAL-TREES-IMPL::LEAF-NODE-ENTRY :RECTANGLE #<(0,0) - (81,15)> :DATUM 
> #<CLIM-INTERNALS::TREE-OUTPUT-RECORD-ENTRY {59D6D085}>))>>
> CHILDREN-HASH = #5=#<EQL hash table, 7 entries {59E3DBA5}>
> LAST-INSERTION-NR = 13
>
> Where should I look further?

Somewhere in the CHILDREN slot.  I can't be much more specific, I'm
afraid.

>      Consed |     Calls |   Secs | Sec/Call | Bytes/C. | Name:
> -----------------------------------------------------------------------
> 609,294,888 |     2,021 | 17.476 |  0.00865 |  301,482 | 
> CLIM:MAP-OVER-OUTPUT-RECORDS
>                   1,132: #<Code Object "DEFMETHOD %TREE-RECOMPUTE-EXTENT* 
> (COMPOUND-OUTPUT-RECORD)"
>                            {58EB3847}>
>                     828: #<Code Object "DEFMETHOD* (SETF 
> OUTPUT-RECORD-POSITION)"
>                            {58C0AF87}>
>                      12: #<Code Object "DEFMETHOD COMPUTE-NEW-OUTPUT-RECORDS 
> (STANDARD-UPDATING-OUTPUT-RECORD T)"
>                            {58BA4677}>
>                      12: #<Code Object "DEF-PROFILE-FWRAPPER 1" {1035F597}>
>                      11: #<Code Object "DEFMETHOD INVOKE-UPDATING-OUTPUT 
> (UPDATING-OUTPUT-STREAM-MIXIN T T T T T T)"
>                            {58BA1007}>

Hm.  On the one hand, the use of MAP-OVER-OUTPUT-RECORDS is going to
lead to O(N^2) behaviour in %TREE-RECOMPUTE-EXTENT* if one output
record at a time is added to the graph output record.  On the other
hand, I think the code for %TREE-RECOMPUTE-EXTENT is completely
unnecessary for TREE-OUTPUT-RECORDs (though not for
SEQUENCE-OUTPUT-RECORDs).  On the gripping hand, I no longer really
have much of an idea what's going on at all.  You might want to
examine the code that draws the graph, maybe trying to insert a graph
output record instead of a sequence one if that's possible.

If possible, it would also be good to find out whether
%TREE-RECOMPUTE-EXTENT* or (SETF OUTPUT-RECORD-POSITION) is
responsible for the majority of the time.

Cheers,

Christophe