Re: Text Widget issues (forked from: Possible Glib BTree substitute)

[Havoc Pennington <hp redhat com>]

Derek Simkowiak <dereks@kd-dev.com> writes:
> 
> 	However, every single Line (FrooTkxtLine) also has a BTree node
> associated with it (or rather, every node with level zero has a line
> associated with it).   I believe you have only counted "parent" nodes
> above, and have discounted the nodes that have a level of zero.  So, in
> addition to your 300K, you have another 36 bytes of memory for every
> single line, in addition to the FrooTkxtLine struct for each line.
>

No, I've counted all nodes (I just put a counter in node_new(), so I
know I got them all).

The lines themselves are the tree leaves, all nodes have between 6 and
12 children. The immediate parents of the lines ("level 0 nodes") 
have lines as children, all higher-up nodes have nodes as children.

The Line structure found on the leaves is deliberately smaller than
the Node structure, lines are only 16 bytes.

See below for some memory use numbers.

> 	I think it's fair to say that many (if not most) lines of C code
> (as an example text file) have fewer than 36 characters, so using a
> structure other than something like a gapped text buffer is very
> expensive.  I used to think Nedit was expensive because it uses a second,
> parallel "style buffer" that basically doubles the amount of RAM needed to
> hold the text.  But a 100% increase is nuthin' :).
>

Indeed, any node-based structure will use more RAM. IMO the advantages
are very much worth it, but opinions will vary.
 
> 	I'll have the same problem with my skip list--except that the
> nodes at level zero won't have "num_lines".  

No savings here. :-)

> Also, with the skip list I
> won't need "num_children", which amounts to another 4 bytes per line
> savings. 

Indeed, you can nuke this, since you won't need to balance the skip
list. Good point.

> 	I plan on also adding another 4 bytes for "gint pixel_height", the
> calculated total height of all the DLines for a given line.  Then, I'll
> propagate that sum up the tree, just like num_chars or num_lines, and
> I'll always know my total height at the cost of one int per line.
> 

You also need gint max_width, and you need this width/height thing for
each "view" of your tree, so if you support multiple views as my
widget does that is a linked list of structs containing at minimum a
view ID, a width, and a height, with one struct per view stored at
each node/line.

But your main users of RAM are the segments in the lines, and the
lines themselves, not the nodes, so again I wouldn't spend a bunch of
time trying to trim fat off the nodes...

memprof results for the version of testfrootkxt in CVS (5000-line
buffer) are something like:

 - 640K of char data
 - 240K of tag toggle segments
 - 100K of wrapped line structs (widht/height of line, plus pointer 
   to list of wrapped lines)
 - 47K of tag summary information stored at nodes
 - 28K of nodes
 - 24K of pixmap segments
 - 12K of per-view width/height data stored at nodes

For a 50,000-line buffer, same lines just repeated more, things scale
exactly linearly (which sort of surprised me, but then I guess I never
had a clear idea how many nodes were required for a given number of
leaves):

 - 6.5 megs of char data
 - 2.4 megs of toggle segments
 - 1 meg of wrapped line structs
 - .47 megs of tag summary information
 - .28 megs of nodes
 - .24 megs of pixmap segments
 - .12 megs of node data

Anyone who gets worried about these numbers may want to read the
README first, they go down quite a bit for untagged text because the
char data usage goes up when you start breaking char segments in half
to insert tag toggle segments. i.e. untagged text uses much less for
char data, and eliminates both the toggle segements and the tag
summary information.

Also remember that memprof is showing the allocated memory, but not
the overhead from malloc() itself, which can be reduced by using fewer
allocations for the same data.

> >  - The only user-visible speed problem with the BTree, with a 
> >    50,000-line buffer, is re-wrapping a lot of lines. gprof
> >    reveals most time spent in gdk_char_width(), with the second 
> >    largest amount of time spent retrieving a list of tags 
> >    applied to a given point in the buffer.
> 
> 	How often does this get calculated?  Do you store the calculated
> result anywhere?
> 

The only time you have to rewrap everything is when you find out a new
width for your window. (Or if the user changes all the buffer
contents, but that is expected.)

Otherwise I mark at each tree node whether the child nodes need to be
recalculated, so you can rapidly traverse the tree and find exactly
which lines to rewrap.

> >    Pango will increase the gdk_char_width() time. This is really 
> >    the huge bottleneck.
> 
> 	The way I picture it now is to do the total_height calculation
> once, when the file is loaded (or after syntax highlighting is done) and
> then just maintain that number, like num_chars or anything else.
> 

Of course. The speed problem I'm talking about only occurs when you
have to recalc a a large portion of the buffer, for example when you
first load the file. There is no problem for small portions.

Havoc