CLIM mail archive
[Prev][Next][Index][Thread]

Performance analysis of Clim incremental redisplay

I have lately been analyzing the performance of a CLIM application
under Lucid CLIM 1.0-Beta on a Sparc 1+, and I thought members of this
list might be interested in the results.

The application I am developing (actually, porting from the Symbolics
environment) is a very general graph display system that allows full
interactive editing of graphs.  Therefore, fast incremental redisplay
of an edited portion of a graph (such as a node whose shape is
altered) is important, and I began using CLIM's incremental redisplay
facilities.  Since graphs can contain hundreds of nodes, the initial
display of the entire graph must also be fast.  When I began testing
the application on graphs containing hundreds of nodes I found both
initial display and incremental redisplay to be very slow, so I began
to look at their performance in detail.

The spirit of this message is to help people better understand the
performance characteristics of CLIM 1.0-Beta.  I should note that in
general my conclusions reinforce some of the statements that Scott
McKay has made concerning CLIM the performance of incremental
redisplay, and so in a sense these conclusions might be considered old
news.  However, I was greatly surprised by the quantitative aspects of
some of the experiments I performed, and I expect you will be also.
Let me note the possibility that some of these characteristics may
change due to performance enhancements in CLIM 1.0 over the beta
release.

I will begin with my general conclusions, and then include the
supporting data.  These conclusions pertain to the relative
performance of incremental and nonincremental display on graphic
display of varying sizes.  My data refers to "graph size".  A graph
size of 200 means 200 nodes plus 200 edges, where each node consists
of a label string enclosed in a rectangle, and each edge consists of a
line plus an arrowhead (polygon) -- therefore a graph size of 200
contains about 800 "graphic elements."  I should note that my
application allows no obvious hierarchical structuring of the output
records, so I used the simple approach of having a different
:unique-value for every node and every edge in the display -- if nodes
and edges were grouped into some hierarchy I may well have obtained
different results.

My conclusions concern three types of display operations:

1. Full display of the entire graph when the application employs
CLIM's incremental redisplay facilities using clim:updating-output
("updating-output full display")

2. Full display of the entire graph when the application does not
employ incremental redisplay facilities -- all calls to
clim:updating-output were commented out ("simple full display")

3. Incremental redisplay of the entire graph using clim:redisplay when
a single node in the entire graph has been changed (i.e., all other
nodes and edges have the same :cache-value as when first displayed)
("incremental redisplay")

My overall conclusion is that for moderate to large numbers of graphic
elements, incremental display with no hierarchical structure does not
provide any performance advantage over simple full display of the
entire graphic.  More specifically:

First, for the case of under 500 graphic elements, performance of
incremental redisplay is reasonable, and pictures are small enough
that the cost is not really noticable:

o Updating-output full display takes approximately 1.5 times as long
as simple full display.

o Incremental redisplay is approximately 2 times faster than simple
full display.

Second, for the case of 1000-2000 graphic elements (200-400 nodes and edges):

o Updating-output full display takes approximately twice as long as
simple full display, i.e., when using CLIM's incremental redisplay
facilities it takes about twice as long to bring up the graph the
first time.

o Incremental redisplay takes approximately the same time as simple
full display.  In other words, it takes approximately the same amount
of time for clim:redisplay to redisplay a single changed node as to
simply redraw the entire graph in its entirety with incremental
redisplay facilities disabled.

Third, for the case of 2500 graphic elements (800 nodes and edges) or
more:

o The shape of the curve I plotted for display time as a function of
number of graphic elements suggests that CLIM is using a polynomial
(at best) algorithm for both full and incremental redisplay.  With
this many graphic elements, incremental redisplay was taking 50%
longer than simple full display, and updating-output full display took
three times longer than simple full display.


Below is the actual data.  I used Kantrowitz' Metering System to
measure the execution time of my graph-pane display function.  I
measured display times for four different graph sizes, each consisting
of the same number of nodes and edges: 100, 200, 400, and 800 nodes
and edges.  I measured the execution time for each graph two
consecutive times and took the smaller of the two numbers, to minimize
the influence of paging and garbage collection.  The timings are
quite reproducible within 5%.

The first row of the table shows times required for CLIM to
incrementally update the display when I had modified a single node in
the graph.  Thus, the number 26 in the table below indicates that 26
seconds were required to incrementally update the display for a graph
of 200 nodes and edges.  Note that in rows 1 and 3 there is a
cross-over point between 200 and 400 nodes where incremental redisplay
becomes slower than simple full display.

Graph size:			100	200	400	800
-----------------------------------------------------------
Incremental redisplay:		8	26	97	351
Updating-output full display:	21	57	180	595
Simple full display:		15	32	86	234

I will note in closing that I have been able to speed up the simple
full display by a factor of 3-4 by optimizing my code by hand and in
conjunction with Lucid's optimizing compiler.  Presumably these
optimizations will not affect the incremental redisplay since my code
is only being executed for the single changed node during incremental
redisplay; the majority of the computation must be internal to CLIM.

Peter Karp


0,,
Follow-Ups:
Main Index | Thread Index