Ncurses/Panel: Cost of update_panels ()

[Leon Winter]

Hi,

when studying the source code of the update_panel () function of the
"panel" library of ncurses I was surprised of its simplicity. However
the man page indicated that the extension only made use of "high-level
curses calls" which seems to be the case.
So the function update_panel () iterates all the layers from
bottom to top invalidating all the intersecting areas in the layer
above. The cost in terms of runtime therefore is O(n) which is also the
cost of drawing operations. At the same time the push/pop operations of
the layer stack are O(1). As we can see the performance steadily
decreases with a growing number of layers. It is also very sad that the
optimization information of all the layers except the bottom layer are
dropped (or at least of the intersecting areas).
I am currently developing an application making use of many layers and
came accross this bottleneck. Thus I implemented a rather trivial
optimization where every layer is assigned a visbility mask. When
adding/removing layers, the masks will be computed in a semantics
similar to the current update_panels () which will increase the cost of
push/pop from O(1) to O(n). However in order to redraw one does not have
to update all the layers like before, but can request an update of any
layer on the stack. The refresh operation (based on wrefresh) will
additionally check whether the dirty position of the window is actually
visible on the screen (using the visibility mask) and will only then
copy the character to newscr. All the optimization (dirty areas) will
stay intact, yet the visibility of the layers is strictly enforced. The
cost of drawing therefore is O(1). In practise the effect of not
dropping the dirty flags is probably even yielding a bigger positive
performance impact.
Long story short, by increasing the cost (in terms of computing and
memory) of push/pop from O(1) to O(n) one can reduce the cost of drawing
from O(n) to O(1). Assuming drawing takes place way more often than
pushing/poping layers on the stack this can yield significantly
increased performance.
So while this optimization made sense for my particular use case I was
wondering whether it would also make sense to be incorperated into
ncurses/panel. Obviously we cannot rely on high-level functions for this
but make use of the low-level functions and internal data structures,
which could be undesirable. Secondly while checking for the actual usage
of panel library, I found that it is rarely used. Of the 657 packages
using ncurses in Debian [0], only about 6 or 7 actually uses the panel
library. Of those none seems to make use of it excessively in the sense
that an optimization would make an impact.
Based on this observation it makes little sense to optimize the panel
extension in such a way. However I would like to hear other opinions on
that.

Regards,
Leon

p.s. How are the considerations for dynamic field alignment coming
along?

[0] aptitude search '?depends(ncurses)' | wc -l