Re: iterator resolution

[Havoc Pennington <hp redhat com>]

Karl Nelson <kenelson@ece.ucdavis.edu> writes:
> 
> True, but since going back in the buffer is expensive it might 
> be better just to leave it there and give an offset which can be
> used to move the iterator to the end.  (Other than the expensive
> back traversing, I like right as well.)  
> 

Well, for a single insert neither traversal will be especially
expensive, though the back traversal is probably a few times more
expensive we aren't talking about large numbers. 

If you're inserting in a loop and need speed, I would recommend trying
to insert large chunks at a time to minimize loop iterations. Anyway,
basically if you are concerned about speed you won't be doing a
million small insertions, you'll be doing a few larger insertions.

Also, back traversal is only more expensive for the
character-by-character scan; for any large movement, we just do this:

 gint current_pos = iter_to_char_index();
 gint new_pos = current_pos + step; /* step can be negative */
 iter_set_char_index(new_pos);

Where iter_set_char_index() is going to do a tree lookup to find the
new_pos, rather than a linear scan. Some profiling will be required to
decide exactly when to bail out and do the tree lookup, I'm sure the
linear scan is faster for small movements, but clearly at some point
the tree becomes faster. Right now I just have a MAX_LINEAR_SCAN
constant.

So, I don't think the speed is a huge issue, since we do have the hard
maximum of an O(log n) tree lookup, we won't ever get hosed too badly.

Havoc