diff options
Diffstat (limited to '')
| -rw-r--r-- | 2024/captions/emacsconf-2024-regex--emacs-regex-compilation-and-future-directions-for-expressive-pattern-matching--danny-mcclanahan--main.vtt | 1198 |
1 files changed, 1198 insertions, 0 deletions
diff --git a/2024/captions/emacsconf-2024-regex--emacs-regex-compilation-and-future-directions-for-expressive-pattern-matching--danny-mcclanahan--main.vtt b/2024/captions/emacsconf-2024-regex--emacs-regex-compilation-and-future-directions-for-expressive-pattern-matching--danny-mcclanahan--main.vtt new file mode 100644 index 00000000..bad03237 --- /dev/null +++ b/2024/captions/emacsconf-2024-regex--emacs-regex-compilation-and-future-directions-for-expressive-pattern-matching--danny-mcclanahan--main.vtt @@ -0,0 +1,1198 @@ +WEBVTT captioned by sachac + +00:00:00.000 --> 00:00:13.359 +Hello, I'm Danny McClanahan. This is EmacsConf 2024. And + +00:00:13.360 --> 00:00:17.159 +this presentation is ostensibly about Emacs Regex + +00:00:17.160 --> 00:00:22.639 +compilation. But it'll lead a lot more in future + +00:00:22.640 --> 00:00:30.879 +directions. Thanks for coming on this journey with me. + +00:00:30.880 --> 00:00:36.719 +This presentation is 50 slides, 50 footnotes, and that's + +00:00:36.720 --> 00:00:40.679 +intended for it to be a resource later on for your perusal. We + +00:00:40.680 --> 00:00:44.199 +are unfortunately not going to be able to go into all of it, + +00:00:44.200 --> 00:00:49.439 +but I will try to be within 20 minutes so we can make it + +00:00:49.440 --> 00:00:56.199 +throughout Q&A. This is the structure of the talk. + +00:00:56.200 --> 00:01:03.519 +But enough about me. Who are you? And why are you here? + +00:01:03.520 --> 00:01:09.479 +I'm Danny McClanahan. + +00:01:09.480 --> 00:01:13.439 +My experience is a lot in build tools, especially in the + +00:01:13.440 --> 00:01:19.399 +package managers. That started because I realized I was + +00:01:19.400 --> 00:01:23.319 +wasting a lot of time. Then I didn't like that. I + +00:01:23.320 --> 00:01:29.439 +started wasting a lot of time, trying to avoid wasting time. + +00:01:29.440 --> 00:01:35.479 +Then I ended up... going so far around that I ended up + +00:01:35.480 --> 00:01:40.319 +stopping other people from wasting their own time, in this + +00:01:40.320 --> 00:01:44.359 +case, regarding failing builds. But this is a kind of + +00:01:44.360 --> 00:01:47.479 +pattern that you'll see. I'm talking a lot about patterns in + +00:01:47.480 --> 00:01:52.399 +this presentation. Parsing in text is another one of + +00:01:52.400 --> 00:01:57.479 +those tendencies that I have. Why am I here? I've got a lot + +00:01:57.480 --> 00:02:00.639 +of feelings about text. For the next 20 minutes, I'm + +00:02:00.640 --> 00:02:06.079 +making it your problem. + +00:02:06.080 --> 00:02:09.639 +First off, a huge shout out to Emacs Devel and the Emacs + +00:02:09.640 --> 00:02:12.919 +community in general. I spent a lot of time learning about + +00:02:12.920 --> 00:02:15.559 +what I'm about to talk about. I was definitely super + +00:02:15.560 --> 00:02:19.439 +confused at first. Then when I became less confused and I + +00:02:19.440 --> 00:02:23.919 +decided I was going to look at the regular expressions of the + +00:02:23.920 --> 00:02:28.039 +Regex engine, I was like, oh, it's old C code. It's + +00:02:28.040 --> 00:02:33.559 +Emacs. We can just use modern techniques. Turns out that's + +00:02:33.560 --> 00:02:37.839 +wrong for kind of two reasons. One, because using modern + +00:02:37.840 --> 00:02:41.479 +techniques or other engines don't necessarily do what + +00:02:41.480 --> 00:02:44.799 +Emacs regex engine currently does. Then secondarily, + +00:02:44.800 --> 00:02:48.719 +that's not actually as interesting as the other kind of + +00:02:48.720 --> 00:02:52.359 +larger goals that emacs-devel discussed. Thank you, Eli + +00:02:52.360 --> 00:02:56.279 +Zaretskii, so, so much, especially Pip Cet and everyone else + +00:02:56.280 --> 00:02:59.319 +as well--I believe--Pip Cet, I hope I'm pronouncing that + +00:02:59.320 --> 00:03:01.799 +correctly. Thank you so much. I'll be shouting you out + +00:03:01.800 --> 00:03:04.319 +later as well. Then these larger goals ended up + +00:03:04.320 --> 00:03:07.199 +overlapping a lot with my own research interests. And + +00:03:07.200 --> 00:03:09.879 +that's very exciting. I'm hoping it's exciting for you + +00:03:09.880 --> 00:03:14.079 +too. What is a regular expression? And when and how does + +00:03:14.080 --> 00:03:16.559 +implementation match formal theory? So what does formal + +00:03:16.560 --> 00:03:24.079 +theory mean? And we'll talk about that. + +00:03:24.080 --> 00:03:27.519 +What is a regular expression? So I might ask you this + +00:03:27.520 --> 00:03:30.799 +question, and you might give an answer. Then I might ask + +00:03:30.800 --> 00:03:33.519 +someone else, and they might have an answer. Then I might + +00:03:33.520 --> 00:03:38.039 +ask myself, and I might try to think of an answer. Our + +00:03:38.040 --> 00:03:41.799 +answers would, you know, see, the thing is, they'd all be + +00:03:41.800 --> 00:03:45.359 +correct, but they'd probably be slightly different, and + +00:03:45.360 --> 00:03:50.319 +they'd be different in kind of important ways. I'm + +00:03:50.320 --> 00:03:55.039 +using formal theory to kind of describe what unifies these + +00:03:55.040 --> 00:04:00.119 +interpretations and what causes this sort of divergence, + +00:04:00.120 --> 00:04:05.439 +both over time and then across code bases. I'm kind of + +00:04:05.440 --> 00:04:09.319 +putting a flag in the ground here and saying formal theory is + +00:04:09.320 --> 00:04:12.999 +actually a really, really negative influence, I think, but + +00:04:13.000 --> 00:04:15.999 +it can be better. That's what I'm going to talk about in + +00:04:16.000 --> 00:04:19.519 +this talk, in this presentation. We might ask, how did + +00:04:19.520 --> 00:04:26.679 +this happen? and we might try to find a start state. We + +00:04:26.680 --> 00:04:30.519 +might put that place at the theories of formal languages + +00:04:30.520 --> 00:04:34.679 +that kind of arose, especially post Turing and post + +00:04:34.680 --> 00:04:37.519 +Chomsky. Especially there was this really, really + +00:04:37.520 --> 00:04:40.119 +interesting and powerful relationship with formal + +00:04:40.120 --> 00:04:43.959 +languages between representation and computation. And + +00:04:43.960 --> 00:04:48.599 +then on top of that, we have regex as this really powerful + +00:04:48.600 --> 00:04:52.159 +union of theory and practice And then, like I mentioned, + +00:04:52.160 --> 00:04:55.799 +this is kind of divergence that kind of occurs. This + +00:04:55.800 --> 00:04:58.079 +divergence happens for a good reason. This happens because + +00:04:58.080 --> 00:05:01.999 +people were adding implementations and people adding + +00:05:02.000 --> 00:05:04.639 +features to implementations. While the people adding + +00:05:04.640 --> 00:05:06.679 +these features were often academics, they were + +00:05:06.680 --> 00:05:09.199 +industries, people that were hobbyists, they were + +00:05:09.200 --> 00:05:11.999 +interested in building practical tools. This is a good + +00:05:12.000 --> 00:05:14.879 +thing. This is still a good thing, even though it moves a + +00:05:14.880 --> 00:05:18.199 +little bit away from formal theory. But we start seeing some + +00:05:18.200 --> 00:05:22.639 +cracks developing, and we'll go into that in a second. We're + +00:05:22.640 --> 00:05:27.519 +just going to kind of electric slide into the 1980s here, and + +00:05:27.520 --> 00:05:31.879 +we're going to be confronted with two occurrences very + +00:05:31.880 --> 00:05:35.639 +similarly. We might call it simultaneous discovery. In + +00:05:35.640 --> 00:05:38.559 +1983, you have Michael Jackson demonstrating the + +00:05:38.560 --> 00:05:41.999 +moonwalk. Three years later, we have backtracking + +00:05:42.000 --> 00:05:44.999 +developed to stimulate EGREP-style regular expressions. + +00:05:45.000 --> 00:05:48.599 +These would both be incredibly influential in their own + +00:05:48.600 --> 00:05:54.039 +kind of branching paths. Here's where the gloves come + +00:05:54.040 --> 00:06:00.759 +off. Formal theory, I claim, remains largely concerned + +00:06:00.760 --> 00:06:03.359 +with incremental improvements to artificial benchmarks, + +00:06:03.360 --> 00:06:07.279 +and much less with expanding models to cover actual user + +00:06:07.280 --> 00:06:11.799 +needs. This isn't just about, oh, if you listened to + +00:06:11.800 --> 00:06:15.999 +users, that you'd be a nicer person, you'd be a better + +00:06:16.000 --> 00:06:19.359 +engineer. What I'm actually saying is that they're missing + +00:06:19.360 --> 00:06:23.919 +out. When you don't listen to applications, you miss out on a + +00:06:23.920 --> 00:06:26.639 +lot of fantastic opportunities for novel theory. So + +00:06:26.640 --> 00:06:30.839 +this is, again, my complaint with formal theory as it + +00:06:30.840 --> 00:06:34.599 +stands. But we're gonna do better. Before we get better, + +00:06:34.600 --> 00:06:36.959 +we're gonna get, a little bit worse for a bit. We're going to + +00:06:36.960 --> 00:06:40.359 +actually get a little bit worse is better. What I mean by + +00:06:40.360 --> 00:06:43.239 +that is, by the 1990s, we start looking into these + +00:06:43.240 --> 00:06:46.479 +non-backtracking engines. This is a bit of a reaction to + +00:06:46.480 --> 00:06:50.399 +backtracking. The current ones include RE2, + +00:06:50.400 --> 00:06:53.919 +hyperscan, and the rust regex library. These are all + +00:06:53.920 --> 00:06:56.439 +great. I'll talk about them later as well. They make use + +00:06:56.440 --> 00:06:58.719 +of these. They kind of call back to the earlier formal + +00:06:58.720 --> 00:07:01.479 +theory. They have linear runtimes for well-specified + +00:07:01.480 --> 00:07:02.519 +search tasks. + +00:07:02.520 --> 00:07:08.079 +What happens if that doesn't fit your needs? We're going to + +00:07:08.080 --> 00:07:11.479 +talk about that. We're going to table that for a second, + +00:07:11.480 --> 00:07:15.319 +and we're going to focus more on Emacs, the subject of this + +00:07:15.320 --> 00:07:19.359 +conference. What are regex used for? And in this + +00:07:19.360 --> 00:07:22.439 +particular case, they're used for lots of things, with + +00:07:22.440 --> 00:07:25.199 +practically, and I think they should be. But more + +00:07:25.200 --> 00:07:29.559 +specifically, how do Emacs users use them? And I'm going to + +00:07:29.560 --> 00:07:32.679 +focus in on this text as input and output. I'll be kind of + +00:07:32.680 --> 00:07:38.959 +elaborating on this analogy as we continue. Why is text + +00:07:38.960 --> 00:07:43.399 +powerful? Text as I/O. The reason text programming + +00:07:43.400 --> 00:07:45.759 +languages and not just programming languages, but + +00:07:45.760 --> 00:07:49.159 +languages themselves, the reason why they're successful + +00:07:49.160 --> 00:07:52.279 +and why they propagate, I claim, is because text is both + +00:07:52.280 --> 00:07:56.439 +input readable and output writable. What this means + +00:07:56.440 --> 00:08:01.199 +is that if you receive something in text, you can read it, And + +00:08:01.200 --> 00:08:04.239 +then you can also write it, you can modify it, and you can + +00:08:04.240 --> 00:08:06.959 +produce a new version of it. You're on a kind of level + +00:08:06.960 --> 00:08:10.959 +playing field. That's not always the case, though. You + +00:08:10.960 --> 00:08:15.959 +recall that I've worked a lot with build systems and package + +00:08:15.960 --> 00:08:20.999 +managers. There's a discussion that goes by the name of + +00:08:21.000 --> 00:08:25.319 +software supply chain security. I think it's a massive + +00:08:25.320 --> 00:08:29.079 +joke. The reason why is because people largely raise it + +00:08:29.080 --> 00:08:34.279 +to explain why their for-profit company with their + +00:08:34.280 --> 00:08:38.079 +for-profit product is going to solve the problem for you, as + +00:08:38.080 --> 00:08:41.959 +opposed to the commons of open source. If you are unable to + +00:08:41.960 --> 00:08:44.999 +modify or deploy your code without employing an opaque + +00:08:45.000 --> 00:08:48.599 +external system, I think, then you have a hidden + +00:08:48.600 --> 00:08:53.879 +dependency. you don't remove a dependency, you just, by, + +00:08:53.880 --> 00:08:59.239 +for example, paying into a for-profit product or using a + +00:08:59.240 --> 00:09:01.519 +closed-off supply chain, you end up just having a hidden + +00:09:01.520 --> 00:09:04.719 +dependency, you end up just displacing that. This can + +00:09:04.720 --> 00:09:07.639 +actually exert arbitrary control over your programming + +00:09:07.640 --> 00:09:11.279 +output and potentially even your thoughts. This is really + +00:09:11.280 --> 00:09:15.839 +important. I'm going to dive in a little bit deeper and I'm + +00:09:15.840 --> 00:09:18.999 +going to overload the term locality here. I'm going to + +00:09:19.000 --> 00:09:22.239 +say, if you cannot reproduce a system locally, it becomes an + +00:09:22.240 --> 00:09:24.999 +opaque external system. I'm going to give examples + +00:09:25.000 --> 00:09:27.479 +here, and these are going to be a bit of a hot take. First + +00:09:27.480 --> 00:09:30.519 +off, GUI IDEs. I think we might, well, some of us might agree + +00:09:30.520 --> 00:09:34.519 +with that here. I say development environments that only + +00:09:34.520 --> 00:09:38.119 +allow you to use a graphical interface, do not expose + +00:09:38.120 --> 00:09:42.799 +interaction with text, are explicitly trying to kind of + +00:09:42.800 --> 00:09:46.239 +place you on a separate kind of plane where you're not an + +00:09:46.240 --> 00:09:50.439 +equal contributor to the people who make the development + +00:09:50.440 --> 00:09:53.079 +environment, make the development kind of frameworks + +00:09:53.080 --> 00:09:57.399 +here. We'll go one further. Cloud services are precisely, + +00:09:57.400 --> 00:10:00.039 +you know, they're useful for things that, you know, that + +00:10:00.040 --> 00:10:04.399 +require large domain computation, but, you know, Twitter, + +00:10:04.400 --> 00:10:08.679 +for example, didn't actually ever use any cloud services, + +00:10:08.680 --> 00:10:12.199 +external ones, because it was really important for them to + +00:10:12.200 --> 00:10:14.999 +actually own their own hardware, their own computation, + +00:10:15.000 --> 00:10:20.199 +their own thinking. Cloud services are a way to ensure + +00:10:20.200 --> 00:10:24.919 +that you're unable to reproduce a system without paying an + +00:10:24.920 --> 00:10:28.039 +amount per month, an amount per day, an amount per second, an + +00:10:28.040 --> 00:10:32.439 +amount per cycle to an external entity. I'm just going to + +00:10:32.440 --> 00:10:35.559 +conclude this with, I'd say, the argumentum ad absurdum, + +00:10:35.560 --> 00:10:39.239 +here, where large language models are all of these at once. + +00:10:39.240 --> 00:10:42.879 +They are a cloud service, specifically, and this is what + +00:10:42.880 --> 00:10:48.439 +makes them very evil, to make it so that, similar to GUI IDEs, + +00:10:48.440 --> 00:10:52.919 +so that text itself loses that ability to be both readable + +00:10:52.920 --> 00:10:56.199 +and writable. Instead, text is both unreadable, because + +00:10:56.200 --> 00:10:59.519 +it's produced by a machine, and then also unwritable, + +00:10:59.520 --> 00:11:02.999 +because you're subservient and subjugated to the machine, + +00:11:03.000 --> 00:11:05.359 +to the large language model to produce the code in the first + +00:11:05.360 --> 00:11:08.919 +place. You lose this input, output, readable, writable + +00:11:08.920 --> 00:11:13.359 +behavior that I claim text has specifically. To + +00:11:13.360 --> 00:11:19.439 +underline this, what is text? Text is local. Finally, + +00:11:19.440 --> 00:11:23.639 +we're at the subject of this conference. Emacs, I have + +00:11:23.640 --> 00:11:27.479 +double hearts with text. I start off the slide saying Emacs + +00:11:27.480 --> 00:11:31.519 +is a text editor. I think that's a good start. Which + +00:11:31.520 --> 00:11:34.319 +implements much of its own logic and user interface via + +00:11:34.320 --> 00:11:38.399 +text. What this means is that, you know, I say without + +00:11:38.400 --> 00:11:42.639 +trying, Emacs tries very hard, but without trying so hard, + +00:11:42.640 --> 00:11:47.639 +Emacs, is imbued with all of the capabilities that text has + +00:11:47.640 --> 00:11:51.319 +specifically. When you use text like Emacs does, and + +00:11:51.320 --> 00:11:55.519 +particularly you then start offering mechanisms to query, + +00:11:55.520 --> 00:11:59.999 +to transform, and to generally metaprogram text itself, + +00:12:00.000 --> 00:12:03.319 +you don't just have the ability to edit code in new ways. And + +00:12:03.320 --> 00:12:06.999 +this is something that I think is often lost, maybe not by + +00:12:07.000 --> 00:12:11.239 +participants of this conference, you particularly start + +00:12:11.240 --> 00:12:14.319 +being able to not only just edit code differently, but to + +00:12:14.320 --> 00:12:16.599 +change the way that you think about code and actually to + +00:12:16.600 --> 00:12:20.239 +expand your range of thought, the range of actions that you + +00:12:20.240 --> 00:12:22.719 +can perform. You can actually start then editing at the + +00:12:22.720 --> 00:12:25.799 +speed of thought. This is where especially Regex kind of + +00:12:25.800 --> 00:12:30.319 +comes into play. Finally, we get to the subject of the + +00:12:30.320 --> 00:12:33.599 +title of this talk. I'm about to disappoint a lot of + +00:12:33.600 --> 00:12:38.759 +people. I claim for good reason. Unfortunately, it's a + +00:12:38.760 --> 00:12:41.599 +very brief walkthrough, but I'm going to go over what the + +00:12:41.600 --> 00:12:43.799 +current Emacs Redix engine is. This is going to give us + +00:12:43.800 --> 00:12:48.119 +enough context for the next section on future directions. + +00:12:48.120 --> 00:12:51.799 +Quickly, it's a backtracking engine over a multi-byte + +00:12:51.800 --> 00:12:53.919 +code point. I'll define what that means. It's in + +00:12:53.920 --> 00:12:58.439 +regex-emacs.c. It's invoked in two ways, which you'll see + +00:12:58.440 --> 00:13:01.759 +is actually the same way, over a single contiguous string + +00:13:01.760 --> 00:13:05.359 +input. This is a Lisp string that you pass in. or over the + +00:13:05.360 --> 00:13:07.039 +two halves of the gap buffer. This is when you match + +00:13:07.040 --> 00:13:11.879 +against a buffer text. We'll go into that a little bit + +00:13:11.880 --> 00:13:13.919 +more, but this is one of the really actually interesting and + +00:13:13.920 --> 00:13:17.839 +specific things about Emacs Regex Engine as it stands. So + +00:13:17.840 --> 00:13:21.559 +very, very quickly, this is the data layout. This is just, if + +00:13:21.560 --> 00:13:24.879 +you're interested, this is where the code lies. So + +00:13:24.880 --> 00:13:30.159 +regex-emacs.h has re-pattern buffer, which is a struct + +00:13:30.160 --> 00:13:34.239 +Actually, you know, I love, by the way, I love the Emacs C + +00:13:34.240 --> 00:13:37.359 +source code. It's so nice to read. It made all this so, so + +00:13:37.360 --> 00:13:41.119 +easy. I really appreciated it. In this particular case, + +00:13:41.120 --> 00:13:44.039 +I'm just going to focus on re-pattern buffer actually has + +00:13:44.040 --> 00:13:47.999 +the compiler. It's a C struct. It has every single thing + +00:13:48.000 --> 00:13:52.559 +that is needed to execute the regular expression against a + +00:13:52.560 --> 00:13:56.319 +string input or against a buffer input. This buffer, + +00:13:56.320 --> 00:13:59.839 +It's not an Emacs buffer. It refers to just the instruction + +00:13:59.840 --> 00:14:04.039 +table and the match loop. Again, this is very, very + +00:14:04.040 --> 00:14:07.839 +brief, but I want to specifically focus on the first part. So + +00:14:07.840 --> 00:14:11.879 +this is this inner matching loop, and there's a prologue, + +00:14:11.880 --> 00:14:15.679 +and then there's a loop body, and there's an epilogue. And + +00:14:15.680 --> 00:14:18.279 +the prologue is the really, really interesting part. I say + +00:14:18.280 --> 00:14:22.839 +extract current and next char. What Emacs does here, it + +00:14:22.840 --> 00:14:27.159 +doesn't just reach for the next byte. It actually will + +00:14:27.160 --> 00:14:31.879 +perform lazily in some sense, this variable integer size + +00:14:31.880 --> 00:14:36.039 +VAR decoding for multi-byte, and it'll actually then + +00:14:36.040 --> 00:14:43.959 +decode the next one to four bytes. Up to 32 bits at once, and + +00:14:43.960 --> 00:14:46.799 +then it'll actually go into the loop. We'll talk about the + +00:14:46.800 --> 00:14:52.519 +implications of that later. Next, in the body of the loop, we + +00:14:52.520 --> 00:14:54.239 +read the instruction from the instruction pointer, which + +00:14:54.240 --> 00:14:57.319 +is, again, in that buffer field. Then we have this big + +00:14:57.320 --> 00:14:59.479 +switch statement, which is actually, love a big switch + +00:14:59.480 --> 00:15:02.079 +statement, super easy to read, super easy to understand + +00:15:02.080 --> 00:15:05.399 +kind of what's occurring. Then that's the loop body. And + +00:15:05.400 --> 00:15:08.279 +then at the end of it, we either increment the instruction + +00:15:08.280 --> 00:15:11.119 +pointer if it was matching a single character or something + +00:15:11.120 --> 00:15:14.839 +along those lines, or if it was a jump, we don't do that. A + +00:15:14.840 --> 00:15:18.199 +jump, however, it's not referring to a jump in the sense of a + +00:15:18.200 --> 00:15:22.519 +go-to, but a jump that's elsewhere within that table, that + +00:15:22.520 --> 00:15:25.839 +buffer field. If you've included a capture, we write + +00:15:25.840 --> 00:15:29.479 +that end position there. Of course, well, as you may + +00:15:29.480 --> 00:15:34.439 +recall, the zeroth capture is, of course, the entire match + +00:15:34.440 --> 00:15:36.559 +string. If the capture is zero, then we know we've + +00:15:36.560 --> 00:15:39.839 +actually completed that match. That's really great. + +00:15:39.840 --> 00:15:43.599 +I would love to receive Q&A about this as well. I've spent a + +00:15:43.600 --> 00:15:46.719 +lot of time kind of learning and understanding it. But it's + +00:15:46.720 --> 00:15:49.879 +really interesting that this can be described in a single + +00:15:49.880 --> 00:15:52.159 +slide because it's really simple. That simplicity is + +00:15:52.160 --> 00:15:54.639 +actually a really powerful thing. I'll mention that in + +00:15:54.640 --> 00:15:58.759 +the next section. I say, is that all? And I apologize for + +00:15:58.760 --> 00:16:02.239 +not doing so. But please, please ask questions in Q&A or + +00:16:02.240 --> 00:16:04.999 +message me about this, because I think it's really, really, + +00:16:05.000 --> 00:16:07.079 +again, interesting. Again, I find the code relatively + +00:16:07.080 --> 00:16:11.999 +easy to read. Now, here's, I think this is actually the + +00:16:12.000 --> 00:16:15.519 +point of the talk. The rest of it was, you know, I think just me + +00:16:15.520 --> 00:16:18.839 +posturing. This is the really, really interesting part. + +00:16:18.840 --> 00:16:22.039 +This is the ways that we can improve, well, not just we can + +00:16:22.040 --> 00:16:25.839 +improve stuff in Emacs, but why those are the right things to + +00:16:25.840 --> 00:16:30.279 +improve. Then also how that can be a model for even things + +00:16:30.280 --> 00:16:35.079 +outside of Emacs. This is gonna be a lot of text. I'm not + +00:16:35.080 --> 00:16:38.879 +gonna go through all of it. This is the one thing that I tried. + +00:16:38.880 --> 00:16:42.239 +This is the thing that I thought would be a slam dunk, easy + +00:16:42.240 --> 00:16:47.439 +solution. My initial thought process was, well, We tried + +00:16:47.440 --> 00:16:52.919 +very hard to do an LRU cache here. It works. It's actually + +00:16:52.920 --> 00:16:57.399 +very effective. However, though, we don't actually give + +00:16:57.400 --> 00:17:00.479 +the user, the list programmer, the ability to then say, I + +00:17:00.480 --> 00:17:03.079 +know that this regex is something that is going to be used + +00:17:03.080 --> 00:17:06.399 +again. I made an artificial benchmark. I made an + +00:17:06.400 --> 00:17:10.039 +artificial benchmark because I wanted to show there is one + +00:17:10.040 --> 00:17:13.639 +very specific case that it does solve, but it's the same + +00:17:13.640 --> 00:17:16.919 +issue with the artificial benchmarks. mentioned earlier. + +00:17:16.920 --> 00:17:21.559 +It's very specifically crafted in order to show that this + +00:17:21.560 --> 00:17:25.319 +particular solution would produce some speedup. What + +00:17:25.320 --> 00:17:29.599 +this means is it just creates more than 20 regexps in a row. It + +00:17:29.600 --> 00:17:31.959 +compiles them. Then, of course, because we just don't + +00:17:31.960 --> 00:17:35.159 +pay the compile costs, because we don't go through that + +00:17:35.160 --> 00:17:39.079 +cache eviction process, it ends up being faster. But this + +00:17:39.080 --> 00:17:42.079 +isn't really mean very much, particularly the goal here, + +00:17:42.080 --> 00:17:45.559 +you know, the goal would have been to show that the compile + +00:17:45.560 --> 00:17:48.359 +cache is actually causing the performance issue in + +00:17:48.360 --> 00:17:51.359 +comparison to pre-compiling it. That's not something + +00:17:51.360 --> 00:17:56.039 +I've been able to show. Match over bytes, not cars. So + +00:17:56.040 --> 00:17:59.079 +this is when I said at the beginning, oh, I came in and I think, + +00:17:59.080 --> 00:18:02.079 +oh, we can just use modern regex engine techniques. This is + +00:18:02.080 --> 00:18:05.239 +really what I meant. In particular, I mentioned in this + +00:18:05.240 --> 00:18:09.279 +match loop here that there's this, prolog that does this + +00:18:09.280 --> 00:18:13.359 +varring decoding. What this means is that every single + +00:18:13.360 --> 00:18:18.519 +iteration of that loop is going to be interspersed with this + +00:18:18.520 --> 00:18:21.919 +not being able to read a fixed number of bytes, but a variable + +00:18:21.920 --> 00:18:24.359 +number of bytes just depending upon the Unicode character + +00:18:24.360 --> 00:18:27.039 +or the Unicode code point or the multibyte code point. So + +00:18:27.040 --> 00:18:29.799 +this ends up, again, being relatively difficult to + +00:18:29.800 --> 00:18:32.919 +optimize because processors operate over bytes and not + +00:18:32.920 --> 00:18:38.479 +over code points. Yes, we might consider a multi-byte CPU at + +00:18:38.480 --> 00:18:41.039 +some point. But this is a really, really simple thing. It's + +00:18:41.040 --> 00:18:44.999 +just generating automata that operate over bytes as + +00:18:45.000 --> 00:18:48.839 +opposed to code points. This kind of goes into the much more + +00:18:48.840 --> 00:18:51.839 +abstract one. There's a lot of text here, and we're not + +00:18:51.840 --> 00:18:56.159 +going to go into it. But the really, really important point + +00:18:56.160 --> 00:18:57.999 +that I'm specifically mentioning here is this explicit + +00:18:58.000 --> 00:19:02.079 +control over linguistic complexity. That's the + +00:19:02.080 --> 00:19:06.159 +abstract kind of point. I want to introduce the inputs and + +00:19:06.160 --> 00:19:11.279 +the outputs. Basically, when you perform a search, or a + +00:19:11.280 --> 00:19:14.799 +match, or a parse, those are different tasks. They'll + +00:19:14.800 --> 00:19:17.799 +have different expected inputs and different desired + +00:19:17.800 --> 00:19:21.559 +outputs. Right now, Emacs, the API for the regular + +00:19:21.560 --> 00:19:24.919 +expression engine and for matching, It doesn't allow + +00:19:24.920 --> 00:19:27.959 +specialization on this. Or rather, if we do specialize on + +00:19:27.960 --> 00:19:30.999 +particular inputs, if we have a heuristic to check if a regex + +00:19:31.000 --> 00:19:33.519 +is actually a literal string, that's not something that the + +00:19:33.520 --> 00:19:36.959 +user actually has control over. For example, you can make + +00:19:36.960 --> 00:19:38.999 +a mistake escaping something, and then you don't have a + +00:19:39.000 --> 00:19:42.039 +literal, and then you accidentally have behavior that you + +00:19:42.040 --> 00:19:44.279 +totally didn't expect. Not just correctness issues, but + +00:19:44.280 --> 00:19:48.599 +also performance issues. I really like this one. I like + +00:19:48.600 --> 00:19:52.239 +this a lot, because I didn't think of it at all. I think it's + +00:19:52.240 --> 00:19:58.119 +better than in all of my ideas. This was proposed, at least + +00:19:58.120 --> 00:20:01.839 +to me, by Pip Cet, and I really hope that I'm pronouncing your + +00:20:01.840 --> 00:20:04.479 +name correctly. I'm sorry I didn't ask you beforehand, + +00:20:04.480 --> 00:20:08.399 +emacs-devel. In particular, this was after a couple of + +00:20:08.400 --> 00:20:11.999 +responses where I was trying to say, oh, I want to give the + +00:20:12.000 --> 00:20:15.879 +list programmer, way back in here, I want to give the list + +00:20:15.880 --> 00:20:20.559 +programmer the ability to control compilation in some + +00:20:20.560 --> 00:20:25.759 +sense. you know, he mentioned, I think he is correct, you + +00:20:25.760 --> 00:20:28.439 +know, there's no real introspection. That happens + +00:20:28.440 --> 00:20:33.119 +because it's written in C. I was thinking, oh, if I turn + +00:20:33.120 --> 00:20:35.639 +this into a list object that gives the list programmer the + +00:20:35.640 --> 00:20:40.039 +power and the ability to do more with that, but it doesn't + +00:20:40.040 --> 00:20:42.839 +actually because it's still in C. At first, I was + +00:20:42.840 --> 00:20:46.679 +thinking, oh, we can make the C part more flexible. But + +00:20:46.680 --> 00:20:50.039 +actually, especially if we want to do almost any of the + +00:20:50.040 --> 00:20:52.719 +things we previously mentioned, I think basically that + +00:20:52.720 --> 00:20:56.599 +this is... I think that if I'm not going to do it, somebody + +00:20:56.600 --> 00:20:58.879 +else really should do it, and I think we should maybe even do + +00:20:58.880 --> 00:21:01.519 +it together, because I think this is really, I think, how we + +00:21:01.520 --> 00:21:04.079 +can start experimenting, and not just experimenting, but + +00:21:04.080 --> 00:21:07.039 +because, as mentioned here, we have libgccjit, we have the + +00:21:07.040 --> 00:21:09.519 +native compiler, we have the ability to opt, like, + +00:21:09.520 --> 00:21:12.639 +specifically to generate specific code for this, so why not + +00:21:12.640 --> 00:21:15.919 +implement the or a Redix engine itself in list, And this + +00:21:15.920 --> 00:21:18.359 +gives us the ability to introspect it. That's one of the + +00:21:18.360 --> 00:21:20.759 +things I mentioned at the beginning. But it actually gives + +00:21:20.760 --> 00:21:23.879 +us the ability to then actually look at all the previous + +00:21:23.880 --> 00:21:28.159 +implementations, to explicitly compile beforehand, to + +00:21:28.160 --> 00:21:32.519 +match against bytes, to specialize and dispatch based upon + +00:21:32.520 --> 00:21:36.799 +input and output. This is something that, you know, it's + +00:21:36.800 --> 00:21:37.999 +super simple. + +00:21:38.000 --> 00:21:40.799 +It's really smart. I'm really, really glad that Pip + +00:21:40.800 --> 00:21:44.839 +mentioned this because it is, I think, the right way to solve + +00:21:44.840 --> 00:21:49.879 +the rest of it. We're at the final section. I talked a + +00:21:49.880 --> 00:21:52.679 +lot about, you know, kind of abstract, you know, thoughts. + +00:21:52.680 --> 00:21:55.679 +I talked a little about, you know, specific solutions. + +00:21:55.680 --> 00:21:59.999 +But I especially talked about, you know, what is Regex and + +00:22:00.000 --> 00:22:02.959 +Emacs? And I don't know if I had a lot of specific examples of + +00:22:02.960 --> 00:22:06.079 +it. I'm going to just describe kind of my, I guess, + +00:22:06.080 --> 00:22:09.799 +motivation, my impetus. Then I think something that's + +00:22:09.800 --> 00:22:12.639 +really something to chew on for the future. Do I have any + +00:22:12.640 --> 00:22:15.799 +concrete examples? Yes. Well, you can decide if they're + +00:22:15.800 --> 00:22:22.799 +concrete. Or am I just posturing? Also, yes. helm, rg. Helm, + +00:22:22.800 --> 00:22:27.679 +Erg, it's literally just M-x grep, it uses ripgrep, which + +00:22:27.680 --> 00:22:31.999 +is written by the same author of the Rust regex [??]. It + +00:22:32.000 --> 00:22:36.199 +happens to be very, very fast. In particular, I use this tool + +00:22:36.200 --> 00:22:39.319 +with ripgrep on the Twitter monorepo, and I was able to + +00:22:39.320 --> 00:22:42.559 +search very, very large amounts of code that was on my local + +00:22:42.560 --> 00:22:46.399 +machine using regular expressions. I think this is one + +00:22:46.400 --> 00:22:49.199 +thing that I think is really, really important, because + +00:22:49.200 --> 00:22:52.919 +when you want to scale, People say the word scaling and they + +00:22:52.920 --> 00:22:56.719 +assume there's a specific kind of answer for that. I've + +00:22:56.720 --> 00:23:01.679 +just found that text is not only flexible, it's actually + +00:23:01.680 --> 00:23:04.359 +something that can be more performant than the alternative + +00:23:04.360 --> 00:23:07.399 +and not only more performant, but more productive. It's + +00:23:07.400 --> 00:23:10.359 +again, it's just M-x grep using ripgrep. There's a tool + +00:23:10.360 --> 00:23:12.719 +deadgrep by Wilfred Hughes, which is also fantastic. I + +00:23:12.720 --> 00:23:15.759 +think it's actually better than this, but this one's mine so + +00:23:15.760 --> 00:23:19.199 +I can mess around with it. But this tool is kind of why, + +00:23:19.200 --> 00:23:21.799 +especially I started looking into Emacs and looking into + +00:23:21.800 --> 00:23:24.919 +changing the way that, or at least diving into how the + +00:23:24.920 --> 00:23:27.559 +regular expression matching actually kind of works, both + +00:23:27.560 --> 00:23:30.359 +in Emacs and then in ripgrep. We'll go to the next one. + +00:23:30.360 --> 00:23:34.119 +This is something that does exist and continues to exist. + +00:23:34.120 --> 00:23:36.799 +This is something that doesn't quite exist yet. I'm + +00:23:36.800 --> 00:23:41.359 +calling it telepathy grams. It's, you know, it's the name, + +00:23:41.360 --> 00:23:44.719 +and it's very, you know, it doesn't work, but it's a code + +00:23:44.720 --> 00:23:47.919 +search tool that, in this case, precompiles the database to + +00:23:47.920 --> 00:23:51.879 +execute NFAs against. I was thinking, how can I beat And + +00:23:51.880 --> 00:23:55.039 +the first thing I thought is, well, as I have worked on build + +00:23:55.040 --> 00:23:57.759 +tools, especially in monorepos, one of the things that the + +00:23:57.760 --> 00:24:00.799 +pants build tool from Twitter does is it uses a file watcher + +00:24:00.800 --> 00:24:04.239 +to ensure that instead of having to constantly read in the + +00:24:04.240 --> 00:24:10.079 +entire contents of a file, which may be very, very large, it + +00:24:10.080 --> 00:24:13.679 +only does so when the file has been changed. Finally, I + +00:24:13.680 --> 00:24:16.919 +want to conclude on this note, which is just that the stuff I + +00:24:16.920 --> 00:24:20.839 +didn't learn from emacs devel, I learned from Paul + +00:24:20.840 --> 00:24:25.319 +Wankadia, Jr., who is the RE2 maintainer, and he taught me + +00:24:25.320 --> 00:24:32.399 +quite a lot from 2023 to 2024. I'm thankful for the time + +00:24:32.400 --> 00:24:37.959 +that I learned from you, so thank you, Paul. With that, we're + +00:24:37.960 --> 00:24:42.759 +at point-max. Call me, beat me, if you want to reach me and or + +00:24:42.760 --> 00:24:45.839 +hire me. These are places that you can reach me at. There are + +00:24:45.840 --> 00:24:49.719 +probably others. Feel free to suggest other ways to contact + +00:24:49.720 --> 00:24:53.199 +me. But for now, this is the end. Thank you so much for your + +00:24:53.200 --> 00:24:56.080 +time. I really appreciate it. |