Bug 7832

Created attachment 6510 [details] [review]
Optimization for typical cases

I've written a patch that reduces excution time when the pattern contains
"*-*-*-..."" character sequence.

Created attachment 6511 [details] [review]
Different algorithm

This patch uses a different algorithm that lacks the problem for pattern
matching.

Could anyone verify/apply/comment on the proposed patch?
I really need this bug to be fixed.

Sorry about the phenomenal bug spam, guys.  Adding xorg-team@ to the QA contact so bugs don't get lost in future.

I've not tried the patch, but I agree that this is an increasingly annoying problem.  Most Linux distributions are switching to using UTF-8 as the default locale and that exposes this bug.  If I use the xmessage command in Mandriva 2007, I get a five second delay, with xfs running at 90% load on a 2GHz CPU, before it finally works.  According to bug #2475 and bug #4939, this also causes huge delays in a whole bunch of apps like xcalc, xfontsel, XEmacs,and xman.  Workarounds are to switch to a non-UTF-8 locale, or to install a whole bunch of extraneous Asian fonts.

What is the difference between the two patches - which should we take into
libXfont?    (We've been getting complaints about this on OpenSolaris as well,
so I'm willing to do some work here, but am not that familiar with this bit of
code.)

(In reply to comment #6)
> What is the difference between the two patches - which should we take into
> libXfont?    (We've been getting complaints about this on OpenSolaris as well,
> so I'm willing to do some work here, but am not that familiar with this bit of
> code.)
> 

I'm sorry for the late reply.

I think the original code has 2 problems.

1. It gets slow on certain conditions. In the worst case, it takes exponential time with respect to the number of asterisks in the patern. As a typical case, the slowdown happens in practice when the following conditions are met.
  * '*' and '-' appear alternately in the beginning of the pattern.
  * The number of '*' is around 7.
  * The match ultimately fails.
2. It always reports no match when the pattern contains a "**" or "*?" sequence. If I understand correctly, this does not conform to the X11 specification.

The first patch tries to remove the slowdown for the 'typical cases' above, while keeping other behaviors unchanged. There are still many patterns that would cause slowdown, but I'm not sure they will happen in practice.

The second patch replaces the matching algorithm altogether, removing slowdown on all cases. However, it also "fixes" the problem 2 above, so it changes the behavior of the code.

I would suggest using the second patch because it's cleaner and always fast, but I haven't done enough tests to ensure that it breaks nothing.

Sent the patch to the mailing list.

Matt, where did this go?

I sent it, http://lists.x.org/archives/xorg-devel/2010-December/016544.html and ajax commented on it http://lists.x.org/archives/xorg-devel/2010-December/017113.html

Responding to ajax's review, it does look like the existing code will not let a * eat up a - ... I think that can be address by just re-adding this:

if (stringdashes < patdashes)
 	return 0;

Does that sound right?  Would you mind sending an updated version to xorg-devel for review.  After adding in the above, consider it Reviewed-by: Jeremy Huddleston <jeremyhu@apple.com>


On a slightly related note (and maybe for a followup patch)...  After looking at this for about a minute, I'm a tad confused.  We have uses like:

res = PatternMatch(...);
if(res > 0) {
...
} else if (res < 0) {
...
}

but it looks like PatternMatch is a boolean return.  What's with the < 0 cases?

*** Bug 4939 has been marked as a duplicate of this bug. ***

-- GitLab Migration Automatic Message --

This bug has been migrated to freedesktop.org's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.freedesktop.org/xorg/lib/libxfont/issues/1.