Regular expression performance in emacs, number of cached regexps

Regular expression performance in emacs, number of cached regexps

[Gregory S. Stark]

In profiling an elisp program I was working on I found that an inordinate
quantity of string memory was being allocated in a function I thought I had
optimized extensively. Using the source, I eventually found that the memory
was allocated by the regular expression searching functions to cache a small
constant number of compiled regular expressions.

Unfortunately in my code, which was fairly short and simple, the behaviour was
pathological. If I recall correctly, Emacs cached the five most recently used
compiled regular expressions, and I was looping through about six or seven. So
Emacs was repeatedly recompiling the same six or seven regular expressions and
allocating memory only to be thrown away as garbage shortly later, causing
excessive regular expression compilations and garbage collections.

I've since optimized my package to use less than five regular expressions, but
my concern is that several other large packages including W3 and Gnus use
re-search-forward and looking-at liberally in code that is otherwise quite
carefully optimized (more or less). Reducing the number of regular expressions
these packages use in loops is likely to be quite hard. I suspect increasing
the compile-time configuration constant governing the size of this cache will
be a big speed and memory boost for these packages.

greg

In case people are curious, here is the code I use to profile memory usage in
my packages. I've suggested something like this be integrated in elp.el, which
I don't think would really be all that hard, but I don't think elp.el is under
active development, which is a shame, it's a great tool.

(defadvice the-function-to-profile (around profile-memory)
  (let (before after delta)
    (setq before (memory-use-counts))
    ad-do-it
    (setq after (memory-use-counts))
    (while before
    (push (- (pop after) (pop before)) delta))
    (apply 'message
           "MEMORY USE cons:%d fl:%d vec:%d sym:%d str:%d misc:%d int:%d"
           (nreverse delta))))

Re: Regular expression performance in emacs, number of cached regexps

[Kai Grossjohann]

>>>>> gsstark@mit.edu (Gregory S. Stark) writes:

  > [...] If I recall correctly, Emacs cached the five most recently
  > used compiled regular expressions, and I was looping through about
  > six or seven. So Emacs was repeatedly recompiling the same six or
  > seven regular expressions and allocating memory only to be thrown
  > away as garbage shortly later, causing excessive regular
  > expression compilations and garbage collections. [...]

I think I read that the limit has been increased to maybe 20 or so in
a more recent Emacs (the yet to be released 20.3?).

But I'm sure RMS knows best :-)

kai
-- 
A large number of young women don't trust men with beards.
(BFBS Radio)

Re: Regular expression performance in emacs, number of cached regexps

[Hrvoje Niksic]

Kai Grossjohann <grossjohann@charly.cs.uni-dortmund.de> writes:

> >>>>> gsstark@mit.edu (Gregory S. Stark) writes:
> 
>   > [...] If I recall correctly, Emacs cached the five most recently
>   > used compiled regular expressions, and I was looping through about
>   > six or seven. So Emacs was repeatedly recompiling the same six or
>   > seven regular expressions and allocating memory only to be thrown
>   > away as garbage shortly later, causing excessive regular
>   > expression compilations and garbage collections. [...]
> 
> I think I read that the limit has been increased to maybe 20 or so in
> a more recent Emacs (the yet to be released 20.3?).

Yes.  So did XEmacs, a few releases ago.

(see definition of REGEXP_CACHE_SIZE in `src/search.c'.)

> But I'm sure RMS knows best :-)

Ha ha ha.

-- 
Hrvoje Niksic <hniksic@srce.hr> | Student at FER Zagreb, Croatia
--------------------------------+--------------------------------
Be nice to your kids.
They'll choose your nursing home.

Re: Regular expression performance in emacs, number of cached regexps

[Richard Stallman]

I can easily increase this cache size--the question is,
how far should I increase it?

It was already increased to 20 in Emacs 20.  So I don't
think I need to increase it now.  How about switching to Emacs 20?

Re: Regular expression performance in emacs, number of cached regexps

[William M. Perry]

Richard Stallman <rms@santafe.edu> writes:

> I can easily increase this cache size--the question is, how far should I
> increase it?
> 
> It was already increased to 20 in Emacs 20.  So I don't think I need to
> increase it now.  How about switching to Emacs 20?

  Well, as people are wont to say nowadays - memory is cheap, and so is
disk.  If I'm reading the code right, the regexp cache only takes 398 bytes
(worst case on a 64bit machine)... so 20 cache entries are only 7960 (~
7.75k).

  I would propose bumping this up to about 64k total (164 entries).  This
would help _alot_ with gnus and Emacs/W3.

-Bill P.

Re: Regular expression performance in emacs, number of cached regexps

[Richard Stallman]

      Well, as people are wont to say nowadays - memory is cheap, and so is
    disk.  If I'm reading the code right, the regexp cache only takes 398 bytes
    (worst case on a 64bit machine)... so 20 cache entries are only 7960 (~
    7.75k).

There must be a misunderstanding, because the data in a cache
entry has variable size.  Perhaps you're looking only at the
cache structure itself and not its contents.

Re: Regular expression performance in emacs, number of cached regexps

[Jan Vroonhof]

Richard Stallman <rms@santafe.edu> writes:

> I can easily increase this cache size--the question is,
> how far should I increase it?

Make it settible from lisp? A quick glance at the code [1] gives the
impression that it is accessed by pointer chasing anyway so you would
use not (much) speed by the compiler not able to make static array
optimisations. 

Jan

[1] of XEmacs, which is all I have availible here at the moment,
sorry.

Re: Regular expression performance in emacs, number of cached regexps

[William M. Perry]

Richard Stallman <rms@santafe.edu> writes:

>     Well, as people are wont to say nowadays - memory is cheap, and so is
>     disk.  If I'm reading the code right, the regexp cache only takes 398
>     bytes (worst case on a 64bit machine)... so 20 cache entries are only
>     7960 (~ 7.75k).
> 
> There must be a misunderstanding, because the data in a cache entry has
> variable size.  Perhaps you're looking only at the cache structure itself
> and not its contents.

  I was assuming this was fairly small - how bad could a pathological posix 
regexp get? :)  Another 64k total?  Megabytes?  I've never delved too much
into the internals of regexp matching - it scares me.

-Bill P.

Re: Regular expression performance in emacs, number of cached regexps

[Richard Stallman]

If the cache had 64 items, I could easily imagine it might occupy 64k,
counting the contents.  I don't consider 64k insignificant.

Re: Regular expression performance in emacs, number of cached regexps

[Dale Hagglund]

Maybe adding a new function along the lines of

	(re-compile REGEXP)

that returns a compiled form of REGEXP would be a useful approach.
Along with this, all the various regexp search functions could check
if they're given a compiled or an uncompiled regexp, and either check
the cache and compile if necessary, or just use the given compiled
form.

This would let authors of regexp-heavy code pre-compile their own
regexps, avoiding the entire issue of cache size.  The down-side of
this is that over-zealous use of this could chew quite a bit of space
in compiled regexps.

Is there some reason why this sort of approach is a bad idea?  I've
used emacs extensively for many years, and written a fair amount of
lisp code, but I'm only looked at the C internals a few times.

Dale.

Re: Regular expression performance in emacs, number of cached regexps

[William M. Perry]

Dale Hagglund <rdh@best.com> writes:

> Maybe adding a new function along the lines of
> 
> 	(re-compile REGEXP)
> 
> that returns a compiled form of REGEXP would be a useful approach.  Along
> with this, all the various regexp search functions could check if they're
> given a compiled or an uncompiled regexp, and either check the cache and
> compile if necessary, or just use the given compiled form.
> 
> This would let authors of regexp-heavy code pre-compile their own
> regexps, avoiding the entire issue of cache size.  The down-side of this
> is that over-zealous use of this could chew quite a bit of space in
> compiled regexps.
> 
> Is there some reason why this sort of approach is a bad idea?  I've used
> emacs extensively for many years, and written a fair amount of lisp code,
> but I'm only looked at the C internals a few times.

  This is actually something that is on my todo list, but I have zero free
time right now due to my mother's illness, so its been on the back burner
for a while.

-bill p.

Re: Regular expression performance in emacs, number of cached regexps

[Richard Stallman]

I've thought about this idea before.  I am not sure it is a bad idea,
but I'm not sure it is worth its weight, so to speak.