Comments on McEs, A Hacker Life: Avoiding extra work

Hi,I've downloaded pango to see if I understood wh...

2007-05-07T04:53:00.000-04:00

Hi,

I've downloaded pango to see if I understood what was going on. This may not be *the* big bottle neck, but a cumulative width stored in "state" definitely lends efficiency.

For what your doing there you don't really even care about individual character width (of course, I might have missed something).

Anyway, I guess if you don't care about it I'll submit a patch for this.

Pat.

Of course I meantstart_index = (int)(N * (float)li...

2007-05-05T20:43:00.000-04:00

Of course I meant

start_index = (int)(N * (float)line_width/state->log_widths[N-1]);

I guess I thought that state->log_widths[] is popu...

2007-05-05T20:41:00.000-04:00

I guess I thought that state->log_widths[] is populated with the width of each character. If it was instead populated with the cumulative width (i.e. state->log_widths[n] = state->log_widths[n-1] + char_width[n]) then you *might* be able to very quickly find a good starting point. For example:

start_index = (int)(N * (float)state->log_widths[N-1]/line_width);

If state->log_widths[start_index] < line_width ) {
/* something */
} else {
/* something else */
}

Or something.

Or maybe a straight binary search on cumulative width would be quite fast. Or maybe it's just a dumb thought...

What's the point of using binary search if you can...

2007-05-05T14:10:00.000-04:00

What's the point of using binary search if you can't get faster than linear? I have to populate the array first (commulative or not), and then find where to break. What you suggest neither makes the algorithm asymptotically faster, not any measured speedup.

I don't get it why binary search won't work with c...

2007-05-05T00:49:00.000-04:00

I don't get it why binary search won't work with commulative width. It still has to end somewhere in the middle, be it evenly spread or not. At least you reach the right neighborhood much faster. With binary search, you still need to test for breakability or not at every binary point.

Is state->log_widths[] an array of the width of ea...

2007-05-04T13:28:00.000-04:00

Is state->log_widths[] an array of the width of each character? If so, have you thought about storing the cumulative width instead of the individual width? I don't know if that makes sense but then you could do binary searches or (possibly) even faster searches based on heuristics.

Very interesting!, fixing this bug could lead to m...

2007-05-04T12:55:00.000-04:00

Very interesting!, fixing this bug could lead to me using gedit instead of gvim. Thanks.

You have to compute the commulative width of the c...

2007-05-04T08:16:00.000-04:00

You have to compute the commulative width of the characters, so bisecting doesn't help. Also not any position is suitable for a break.

What the Fxxx? Isn't it a typical bisect searching...

2007-05-04T07:54:00.000-04:00

What the Fxxx? Isn't it a typical bisect searching problem? Why do you have to search char by char? Did I miss something here?

you are a hero, as usual :)That said as you note p...

2007-05-04T06:37:00.000-04:00

you are a hero, as usual :)

That said as you note problems with long lines are not related to line wrapping (well, at least line wrapping isn't the top of the iceberg)... in fact rendering long lines is even worse when line wrapping is off.

I am pretty sure there are a couple of bugs already open about the fact that the text widgets abuses pango layouts, but another one will not hurt :)

/me adds himself to CC

Behdad, I always love reading about your performan...

2007-05-04T05:38:00.000-04:00

Behdad, I always love reading about your performance and Pango work. It makes me happy :-).

I'm always promoting Gtk+ with my fellow devs, so it's always nice to see people improving it further.

What I tried to describe is not limited to justifi...

2007-05-03T22:22:00.000-04:00

What I tried to describe is not limited to justified text, no. However, as I said, the bottleneck doesn't seem to be Pango per se, but the fact that Gtk+ voids Pango's caching by creating new Pango layouts all the time. So, in your use case, there is still work to do, and that is why I opened bug 435405.

Does this also affect text rendering that is not j...

2007-05-03T21:50:00.000-04:00

Does this also affect text rendering that is not justified? I have also been bothered by gedit's sluggishness with regards to what I thought was line-wrapping. Checking out SQL dumps in gedit always seemd to bring it down onto its kneews. Would be really sweet if those times are over now and I don't have to find alternatives to view SQL dumps with