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

[Havoc Pennington <hp redhat com>]

Derek Simkowiak <dereks@kd-dev.com> writes: 
> 	I had no idea the toggle segments would use so much ram.  It's the
> largest non-character memory hog, by an order of magnitude.  But at 8
> bytes per on or off toggle:
> 
> typedef struct TkTextToggle {
>     struct TkTextTag *tagPtr;           /* Tag that starts or ends here. */
>     int inNodeCounts;                   /* 1 means this toggle has been
>                                          * accounted for in node toggle  
>                                          * counts; 0 means it hasn't, yet. */
> } TkTextToggle;
>  
> 	...I can see how it would add it up.
> 

It isn't 8 bytes, 8 bytes would be small. You are just looking at the
toggle-specific part of the segment. The entire toggle segment is 40
bytes:

struct _FrooTkxtSegment {
  FrooTkxtSegType *type;		/* Pointer to record describing
					 * segment's type. */
  FrooTkxtSegment *next;	        /* Next in list of segments for this
					 * line, or NULL for end of list. */

  int char_count;                       /* # of chars of index space occupied */
  
  int byte_count;               	/* Size of this segment (# of bytes
					 * of index space it occupies). */
  union {
    char chars[4];			/* Characters that make up character
					 * info.  Actual length varies to
					 * hold as many characters as needed.*/
    FrooTkxtToggle toggle;		/* Information about tag toggle. */
    FrooTkxtMark mark;	        	/* Information about mark. */
    FrooTkxtPixmap pixmap;              /* Child pixmap */
#if 0
    FrooTkxtChild child;                /* child widget */
#endif
  } body;
};

You are only looking at the size of the union at the end. 

"type" and "next" are impossible to eliminate. char_count and
byte_count can only be eliminated by taking a performance hit.

> 	I'm designing my tag system to be slightly different from the
> TkText design.  To begin with, I'm dropping the 'priority' system for
> tags.  I find it confusing, and I don't see the point.  Rather, I'm going
> to have simple on/off toggles.
>

The point of the priority system is to resolve conflicts. If two tags
both set the foreground color, you either a) have a priority system or
b) basically choose one randomly or c) do something like "use the
first one that got applied" which will increase the complexity of
certain btree/skiplist code by a lot.

It's not like the priority system costs anything in terms of memory or
speed, and users can totally ignore it if they want (most recently
created tags become higher priority).
 
> 	Next, I'm not going to track particular off tags for TkTextTags.
> Instead, I'm going to have generic "close" tags, which will always apply
> to the nearest unclosed on tag.  I.e., my tags will render exactly the
> same way Netscape would render
> 

This means that you save 4 of the 80 bytes per toggle pair and
significantly increase the pain-in-the-ass factor of writing your
btree/skiplist code. Plus it won't work, see below...

> This <font color="ff0000">is my <font color="00ff00">line</font> of
> text</font>.
> 
> 	Notice that there is only a generic </font> tag.  I think people
> are more used to a system like this than they are a priority-based system.  
> My widget's "Tags" will simply have more than just the color attribute.
>

Um, if you have:

<green>blah blah <blue> blah blah blah </end> blah blah blah </end>

Which </end> ends green and which ends blue?

The only sane policy is that the </end> ends the most-recent tag,
which removes a useful feature of the widget, namely overlapping tags.

Note that with FrooTkxt if you have:

<big>blah blah blah<blue>blah blah</big>blah blah</blue>

Then you have big, regular-color text, then big blue text, then 
regular-size blue text. Kind of what users expect if you're writing a
simple word processor with the widget, for example.
  
> 	...where a tagPtr == NULL means this is a close tag.  That would
> immediately cut the toggle memory usage in half.
>

Or by 1/16, depending on how accurate you are. ;-)
 
> 	Another option is to have a hardcoded maximum of 255 different
> "styles" in a particular text buffer.  Then, I could use an int from
> 0..255 as a key to the Tag.  That would mean:
> 
> typedef struct TextToggle {
>     guint8 tagIndex;           /* Tag key that starts or ends here. */
> } TextToggle;
> 
> 	...where tagIndex == 0 means a close tag.  That would reduce the
> toggle memory usage by 7/8, at the expense of flexibility.  Comments on

It wouldn't, the struct would end up being 4 bytes anyway with 3 bytes
of padding. Plus it would be a sucky limitation to only have 255 tags.
 
> 	Another idea I'm playing with is to make every line have only one
> text buffer--perhaps even a gapped text buffer.  That would mean only one
> char data pointer per line, as though it were unmarked text.  I could
> then use some sort of GtkText-like indexing system for the Tags.  I
> haven't thought this through yet.
>

That could reduce the number of character segments, worth
experimenting.
 
> > 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.
> 
> 	Would using GAllocator for that be appropriate?
> 

mem chunks reduce the malloc() overhead, but have the unfortunate
property that they are never freed again (or if they are freed, they
are slow). So, I don't know if we want to use them.

Havoc