TIL that trying to compile anything with
pcase matching in it may lead to an explosion of code generated during expansion. Even the most innocent looking patterns may generate hundreds of branches and thousands of lines of code. TBH I would never have noticed had it not been for a small macro I wrote yesterday. The exact code is unimportant but the gist of it is that it had a
pcase with 4 clauses doing some matching on lists and what not. That macro was the last in the project I've been working on, so naturally I attempted to
byte-compile. Upon reaching the macro the compiler would just sit there. Out of curiosity I let it - only to be disappointed with Error: Bytecode overflow some 10min later. O..K..
M-x pp-macroexpand-all-last-sexp ... 160K lines of expanded code later I was enlightened. If you ever looked at what
pcase list pattern expands into, you wouldn't be surprised. There isn't any magic there, the rewriting rule is straightforward. Problem is it doesn't scale if you perform full macro-expansion, and IIUC that is what
byte-compile does. Let's use a tiny contrived example just to get the feel for "scale":
(pcase e (`(,a ,(or (or `(0) `) 42)) a))
Full expansion of this is 70 lines of pretty-printed code but you can imagine how a bunch of nested patterns and several clauses create all possible permutations and baloon into thousands. My first thought was that it's the
(or .. ..) pattern that's not cleverly handled and replacing it with explicit clauses may help fight branching:
(pcase e (`(,a (0)) a) (`(,a ) a) (`(,a 42) a))
Well, macroexpand-all and you get the exact same 70 loc, so, yeah, they're precisely equivalent. I bet
pcase actually re-writes one into the other.
It isn't a problem at runtime i.e. if you just eval and run the interpreter, because in 99.9% of cases the match fails at the head, so all those branches never get generated by the expander when you just interpret and match. That's why I never noticed any issues say with performance.
I guess I have several questions after this long-winded diatribe:
- How do you
byte-compilecode that uses
- Maybe you don't compile, but then how do you get reasonable performance?
- Maybe you just don't use
pcaseever? Is this why so much Elisp is poisoned with
caddaarand friends? I really want my pattern matching.
- Is there anything obvious I've overlooked?
Didn't get any relevant hits searching emacs-devel archives.