bug#63225: Compiling regexp patterns (and REGEXP_CACHE_SIZE in search.c)

[Ihor Radchenko <yantar92@posteo.net>]

Mattias Engdegård <mattiase@acm.org> writes:

>> I was able to get rid of the regex compilation-related slowdown simply
>> by increasing REGEXP_CACHE_SIZE 10x (see the attached patch).
>
> Indeed it sounds like you are suffering from regexp cache thrashing. I'm attaching two patches: one to measure the cache miss rate, and one that allows the regexp cache size to be changed at run time.

Here are the results:

Command: (benchmark-progn
           (setq regexp-cache-hit 0
                 regexp-cache-miss 0)
           (set-regexp-cache-size 42)
           (org-element-parse-buffer)
           nil)
Buffer size: 22Mb
|   Cache size |     Hit |    Miss | % miss from total | ~org-element-parse-buffer~ time   |
|--------------+---------+---------+-------------------+---------------------------------|
| 20 (default) | 3219470 | 1491165 |             31.66 | 21.035765s (1.091127s in 2 GCs) |
|           40 | 4418377 |  293805 |              6.24 | 18.294018s (1.123854s in 2 GCs) |
|           42 | 4550483 |  161820 |              3.43 | 17.946184s (1.073528s in 2 GCs) |
|           45 | 4636222 |   76582 |              1.62 | 18.410150s (1.078844s in 2 GCs) |
|           50 | 4693497 |   44174 |              0.93 | 17.896177s (1.082944s in 2 GCs) |
|           60 | 4734712 |   10807 |              0.23 | 18.011224s (1.097961s in 2 GCs) |
|           80 | 4710155 |    1386 |              0.03 | 18.047544s (1.103518s in 2 GCs) |
|          100 | 4711821 |     399 |              0.01 | 17.880491s (1.102658s in 2 GCs) |
|          160 | 4711895 |     160 |              0.00 | 17.950772s (1.068975s in 2 GCs) |
|          320 | 4737968 |     393 |              0.01 | 17.773617s (1.089100s in 2 GCs) |
|          640 | 4737388 |     320 |              0.01 | 18.225701s (1.097688s in 2 GCs) |
|         1280 | 4711353 |     160 |              0.00 | 17.847522s (1.099575s in 2 GCs) |
|         2560 | 4711898 |     160 |              0.00 | 18.168488s (1.082394s in 2 GCs) |
|         5120 | 4711835 |     160 |              0.00 | 17.797036s (1.097445s in 2 GCs) |
#+TBLFM: $4=100*$3/($3+$2);%.2f

> That should let you find the working set size for your application,
> and ideally come up with a way to reduce it. Perhaps you could give us
> an idea of what these regexps look like and how they are used?

The Org parser is basically a giant `cond' of a number of regexp
matches. See `org-element--current-element'. It is called repeatedly on
every syntax element in Org buffer (like heading, table, paragraph,
etc). Each clause in the `cond' additionally calls for more complex
series regexps to look into smaller components of the parsed syntax
elements. For example, see `org-element-keyword-parser'.

So, we are cycling across several dozens (more than regexp cache size)
of regexps repeatedly.

>> Does anyone know if there are potential side effects of this increase if
>> applied across Emacs? Or, alternatively, may Emacs provide an ability to
>> store compiled regexp patterns from Elisp (similar to what
>> `treesit-query-compile' does)?
>
> I don't think it's necessarily a good idea to increase the size to 200
> right away because of the linear cache lookup mechanism. Allowing the
> size to be changed at run time is probably less controversial (but
> arguably just as much of a crutch).

Fair point. Although overshooting within a single command does not
appear to do much as long as we really re-use these regexps - everything
gets cached.

> Introducing regexp objects that could store compiled regexps and be
> used instead of strings would be quite some work but probably
> worthwhile.

What exactly needs to be done? Assuming that regexp objects are not
going to be readable, for simplicity.

> +DEFUN ("set-regexp-cache-size", Fset_regexp_cache_size, Sset_regexp_cache_size,
> +       1, 1, 0,
> +       doc: /* Set the regexp cache size to N elements.  Internal use only.  */)

If this is something to be used in practice, it will be more convenient
to provide a macro like (with-regexp-cache-size N <body>).

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>