Re: [PATCH] add compiled regexp primitive lisp object

[Ihor Radchenko <yantar92@posteo.net>]

Eli Zaretskii <eliz@gnu.org> writes:

>> 1. They could be inspected from Elisp, and hopefully optimized
>>    better. For now, there is simply no way to detect which parts of
>>    regexps are slow and which are not.
>
> If we can optimize them from Lisp, we should be able to do the same in
> C.  If you explain what kind of optimization opportunities you had in
> mind, we could discuss how to implement that.  In any case, adding
> APIs for regexp optimizations doesn't require to have compiled regexp
> objects.

What I had in mind is some kind of profiler for regexps.  I cannot
imagine such a profiler without having access to the state machine
instructions emitted by regexp compiler - there will be no easy mapping
between regexp itself and the resulting compiled instructions (that
mapping will depend on the specifics of Emacs compiler)

>> 2. They could maybe even be constructed from Elisp, opening
>>    opportunities for custom regexp compilers that can be tailored to
>>    specific application needs rather than having to stick to hard-coded
>>    generic tradeoffs Emacs has to do without knowing the purpose of a
>>    regexp.
>
> How will this help making matching faster, and why does this have to
> be via compiled regexp objects?

My motivation is
https://burntsushi.net/regex-internals/#literal-extraction that explains
how regexp compilation depends on certain heuristics.

For example, when searching for "\\(foo\\|bar\\)[a-z]+", heuristics
invoking simple string literal search for "foo" and "bar" first before
using heavy regexp automata is justified. Not so much when the prefix is
simply " " that usually occurs very frequently in text.

However, for specially structures texts (e.g. in parsers), additional
knowledge about structure is available and can be utilized to fine-tune
the regexp compilation.

Ultimately, an ability to construct instructions from scratch can be
useful - this may allow going beyond what Emacs regexp syntax provides;
and faster.

-- 
Ihor Radchenko // yantar92,
Org mode maintainer,
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>