Havoc's Blog

Thinking about Morten’s comment,
one of the main goals of GtkTextView was to keep everything better
than O(n), because I’d seen so many posts to gtk-list where people
inadvertently wrote quadratic code with GtkCList and the old GtkText.
(Those widgets also had the evil freeze/thaw convention, where you
could “freeze”, do stuff, and “thaw” and it was supposed to magically
make the “do stuff” fast. Mostly it made the widgets crash by
creating strange code paths.)

The idea with GtkTextView is that for the most part you can just
use it and it’s scalable and things are fast. Lots of internal
complexity to enable that. We had a good starting point with the
TkText btree and we improved on it a fair bit.

However, there’s one exception to the scalability, and that’s long
paragraphs. GtkTextView has code that’s O(n) in
number of characters in a paragraph or number of “segments” (analagous
to XML text nodes) in a paragraph. (Note, paragraph is the same as a
newline-terminated line.) There are various bugs about
it, but it would be extremely hard to fix.
It is mitigated somewhat by the
crazy
overengineered iterators.
Pango also
works on the level of paragraphs (PangoLayout) and really can’t do
units of work below the paragraph level, so you can’t do something
like incrementally lay out only part of a paragraph.

I have no clue how you’d make the whole stack support really long
paragraphs, without using reams of memory of creating some scary(-er)
code. But it’s probably possible (I imagine word processors do
it). Not sure it’s genuinely a problem in real life, though.

(This post was originally found at http://log.ometer.com/2005-11.html#3)