🚀 go-pugleaf

Dirk Hohndel wrote:
> 
> 3. Sometimes emacs locks up completely, consuming all CPU he can get
>    but displayin nothing (so it doesn't redisplay parts that were hidden)
>    This happens for example often when pressing 'n' to see the next mail.

I'll bet the reason for this is the new regex.c that FSF19 is using; VM uses
some regexps that will perform pessimally in FSF19.  Lucid Emacs still uses
the same regex.c that was in v18 because the new one's time requirements have
gone ballistic.  We're talking going from 0 seconds to 27 seconds when
matching a pattern against a buffer that only contains 70 characters!

The reason for this is that Posix compliance has forced a change in the
semantics of regexp matching: a regexp is supposed to match the largest
possible substring, whereas in v18, it matched the longest possible substring
of the *first* match it found.

It seems clear to me that having a regexp matcher that never takes more than a
few seconds to do any match no matter how big the buffer is is more important
than Posix compliance, especially given the enormous amount of code that gets
broken, so Lucid Emacs will continue to use the v18 regex code until/unless
someone figures out another way around this problem.

Here's a message from jimb that explains things in a little more detail.

	-- Jamie

------- Start of forwarded message -------
X-Windows: The cutting edge of obsolescence.
Date: Fri, 30 Apr 93 21:23:54 -0400
From: jimb@totoro.cs.oberlin.edu (Jim Blandy)
To: jwz@lucid.com, karl@cs.umb.edu
Subject: regexp slowness


I think I have bad news, but I'm not positive.

You very kindly reported to me that regexp matches akin to

  (string-match "[^0-9]*\\(\\([-, \t]*\\([0-9]+\\)\\)\\)+.*"
    ";; Copyright (C) 1985, 1986, 1987, 1992 Free Software Foundation, Inc.\n")

take a long time (27 seconds or so on my machine) using the latest
release of the regexp package.  Although I agree that the performance
is terrible, after looking into it, I'm not sure there's much I can do
about it without breaking the semantics, and I'm skeptical that Tom
Lord's matcher will do any better.

Here's why I'm pessimistic.

What is the result of evaluating the following expression?

    (list
     (string-match "\\(ab\\|a\\|bc\\)*"
		   "abc")
     (match-data))

If you use the Emacs 18 regexp package, you'll get (0 (0 2 0 2)),
indicating that string-match believes that the given regexp matches
only the first two characters of that string.  This is an incorrect
result; In fact, that regexp clearly can match the entire string.
Since the matching routines are supposed to return the longest match
possible, this is a bug.

Version 0.12 of the regexp package will give the correct result,
(0 (0 3 ...)), because it doesn't accept the first pass through the
regexp as final; instead, it goes back and tries every failure point
on the stack, just in case taking back a previous decision could
extend the length of the match.  I'm pretty sure it is this
re-evaluation which makes 0.12 so slow.  For example, evaluating the
following expression:

 (string-match "a*a*a*a*a*"
   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.")

takes it almost six minutes.  Basically, it tries every possible
extent for each "a*" pattern, to see if any combination of them is
longer than the first it discovers.  There are C73,4 such
combinations, a few more than 1 million.

Basically, regex needs to get a lot smarter about how it retries its
patterns.  I'm not sure how to go about it.

------- End of forwarded message -------