Re: FYI: GtkText design progress

[leon udmnet ru]

Derek Simkowiak wrote:

Well, seems you got to get a working text widget fast. So changing
underlying logic isn't good in the middle of the work. Though I 
will express some ideas as to what a text widget might be. It 
will not be implemented now, but, who knows, maybe some time in
the future :) These are just thoughts. Fore the bright future :)

> 
>         If your single C code file is 10,000 lines long (which is
> relatively large for a well-written, modular program) then that could be
> 40,000 list elements for your file.  Incidentally, I'm making these
> numbers up in my head.
> 
>         Doing a single pointer reference, plus an integer addition, is
> fairly fast, even for 40,000 elements.
> 

For one insertion it is fast. But the trouble comes when you append
a number of items. Then time consumption becames quadratic. Simply
pasting a sizeable piece at the end of such file can be a nightmare.
Why I am so dreaded by performance is my experience with CList
widget. It cannot handle lists of some 20000 items. When I filled
CList by appending items one by one, it took minutes to fill 50000
items. I worked around this trouble by prepending to list, not
appending, because my program's logic allows that. But this is not
a general solution. A general solution guarantees something about
approximated times of operations, namely, that they grow not
faster than some (small) order of size. The cost of O(n) for a 
single append to the list isn't acceptable, because that means
quadratic times for batch appends. The cost of O(log(n)) is much 
better, effectiely it is O(C), so batch appends are O(m*log(n)),
effectively O(m).

>         I plan to reduce the number of references and additions with the
> following algorithm.  Imagine moving from the end of the file, to
> someplace near the middle (or from the beginning of the file to someplace
> near the beginning)--you wouldn't want to iterate from the tail backwards
> to the beginning of the file, or vice versa.  So:
> 
> 1) Assume the number of TextProperties are distributed (more or less)
> evenly throughout the buffer.
> 
> 2) Calculate, as a percentage of the total buffer size, which of the
> following is smallest:
> 
>         a) The distance from the last known location to the new location
>         b) The distance from the beginning of the file to the new location
>         c) The distance from the end of the file to the new location
> 
>         ...then, iterate through the TextPropery linked list to the new
> location from (a) the current location, (b) the head of the list, or (c)
> the tail of the list.  This will greatly optimize a jump from, say, the
> end of a 10Megabyte file to the very beginning.
> 

Hm, a clever trick. But is nevertheless a (dirty) hack, which 
Real Programmers should disdain :) BTW, gapped buffer itself is
a hack. IMHO. 

My experience suggests that no hack can replace a piece of real 
thought, i.e. a good algorithm. You can invent a hack to patch
a hole here, hole there, but you never know where your patches
will fail tomorrow. They may not fail, and they may. You never know.

> 
>         Yes, we do have a balanced tree in Glib, but what will be the
> nodes of your tree? A single character?  Or a word?
>

This can be an evenly styled piece of text. Or, if it is longer
than, say, 4k, it is split in two. 
 
>         Also, I can't imagine (at 1:30am) how to make an easy to read line
> drawing algorithm if we use a tree.  With the gapped text buffer,
> optimizing drawing a line of text to an X window is a fairly
> straightforward problem.  Nedit is a prime example of a fast, usable, and
> easy-to-understand editor application.  Walking a tree, tracking nodes,
> using custom structures at the nodes... it all sounds like a fast headache

All you need is wrappers around tree which hide intrinsics of the
tree from other parts. Object oriented design, you know :) The 
functions can be: GiveChunkOfTextByOffsetAndLength, 
InsertChunkOfTextAtPosition, etc. Not so dreadful :)

Leon.