The claim here wasn't just "first implementation of derivatives." It was a far more precise "first industrial implementation of derivatives for standard regexes in an imperative language."
Compression, synchronization and backup systems often use rolling hash to implement "content-defined chunking", an effective form of deduplication.
In optimized implementations, Rabin-Karp is likely to be the bottleneck. See for instance https://github.com/facebook/zstd/pull/2483 which replaces a Rabin-Karp variant by a >2x faster Gear-Hashing.
> I would love to hear of other low(er) barrier-to-entry ways to use LaTeX, because it’s a pretty steep commitment for someone who isn’t a professional writer.
I have been working on and off on a fork of LaTeX with real-time feedback: you can see the document and error messages rendered and updated live. It also supports SyncTeX (going from a source line to the corresponding output and vice-versa).
I added vim support recently, you can see it in action there: https://github.com/let-def/texpresso.vim
There is also emacs support in the main repo (https://github.com/let-def/texpresso). That's all quite experimental, but I hope to do a first release next year. It should work on most unix, I test with Linux and macOS.
I don't think you should be worried about Unicode in particular. Although the derivation formula on paper is parameterized by a character, you don't have to compute the derivative for every character separately.
It's actually easy to compute classes of characters that have the same derivative (it's done in the linked "Regular-expression derivative re-examined" paper, although their particular implementation favors simplicity over efficiency), and it's not even necessary when using Antimirov's partial derivatives.
Actually, the complexity of the derivation is independent of the size of the alphabet. You could even define derivation on an arbitrary semi-lattice, not necessarily a set of characters. (Or a boolean algebra if you care about negation/complementation).
The difficulty in handling unicode has more to do with the efficiency of the automaton representation and manipulation rather than in turning the RE in an NFA or DFA.
Does there exist a regex engine I can try that uses derivatives and supports large Unicode classes and purports to be usable for others? :-)
It has been a long time since I read the "Regular-expression derivative re-examined" derivative paper. Mostly the only thing I remember at this point is that I came away thinking that it would be difficult to adapt in practice for large Unicode classes. But I don't remember the details.
It is honestly very difficult for me to translate your comment here into an actionable implementation strategy. But that's probably just my inexperience with derivatives talking.
> Does there exist a regex engine I can try that uses derivatives and supports large Unicode classes and purports to be usable for others? :-)
I don't know any besides ocaml-re that Drup already linked, sorry :).
And sorry that my comment is hard to decipher. I think the core point is that the "character set" can be an abstract type from the point of view of the derivation algorithm.
So it doesn't matter how they are represented, nor "how big" a character set is.
With Antimirov's derivative (which produces an NFA), there is no constraint on this type.
With Brzozowski's derivative, you need at least the ability to intersect two character sets. So the type should implement a trait with an intersection function (in Rust syntax, `trait Intersect fn intersect(self, Self) -> Self`). That's necessary for any implementation generating a DFA anyway.
And if you also want to deal with complementation, then a second method `fn negate(self) -> Self` is necessary.
Thanks! You might be right. I'm probably at a point where I'd have to actually go out and try it to understand it better.
I do wonder if there is some room for derivatives in a meta regex engine (like RE2 or the regex crate). For example, if it let you build a DFA more quickly (in practice, not necessarily in theory), then you might be able to use it for a big subset of cases. It's tricky to make that case over the lazy DFA, however, a full DFA has more optimization opportunities. For example, identifying states with very few outgoing transitions and "accelerating" them by running memchr (or memchr2 or memchr3) on those outgoing transitions instead of continuing to walk the automaton. It's really hard to do that with a lazy DFA because you don't really compute entire states up front.
I think what you suggest is possible, derivation might even be well suited for this application, however I can't tell if it would be better than existing approaches.
There are some chances that it might be interesting in practice, since it seems that this application of derivatives has not been much studied, but that's highly speculative.
I wrote a similar sorting algorithm around 14 years ago (fast, inplace, adaptive merge sort algorithm using rotation/swap, and I think, stable). This is all I remember from the time...
I was able to prove (on paper) that the whole algorithm was actually O(n log n). The moves seems to have a bad recursion pattern, but assuming my proof was right, it is possible to have a well behaved implementation in practice.
However, the recursion pattern didn't fit the master theorem, I remember having to do a taylor expansion of some formula giving an upper bound on the number of computation steps to prove the O(n log n) bound.
And runtime measurements graph were showing the expected O(n log n) curve, as in your cases. So maybe they are not O(n log n ^ 2) as you feared...
I did not keep much information from that time :P.
Of course, this is nitpicking :). For all practical purpose, this O(log n) is O(1).
If you are interested, I can try to recover the proof that the rotation step can be done in O(n), thus allowing to apply the master theorem on the main recursion and getting the O(n log n) result.
Both the synchronous and asynchronous frontends preserve as much state as possible (all untouched modules are kept). They differ in the control flow they permit (the asynchronous one being more expressive).
I will try to make a parallel with a simple Makefile-driven project.
In the initial build, all files are built, following a topological ordering of the dependencies.
For the Makefile it means invoking some unix command for each intermediate artefact.
For Hotcaml, it means parsing, typing, compiling and loading each module.
After that, build is incremental: when a file is modified, only this file and its reverse dependencies need to be rebuilt.
Make will keep the existing artifacts that are not out of date.
Hotcaml will keep the existing modules that are not out of date. And their state is preserved.
Now, the synchronous frontend is quite like a regular Makefile: a build step is considered done when the build command finishes.
The asynchronous frontend allows command to run in the background, like a Makefile that would spawn processes/daemon using the shell & control operator.
In Hotcaml, these threads continue executing concurrently with the reloading process. They can be notified that their "host" module has been reloaded by registering with some runtime service (via a module named Hotlink).
There is actually some notion of persisting state in it. Reloading is done at the granularity of a module. The reverse dependencies of a module that changed are also reloaded, but the dependencies are not. The runtime state of all modules that are not reloaded is persisted.
The dependency graph is roughly: system layer -> renderer -> slideshow
The system layer initializes the window (with SDL) and an OpenGL context.
The renderer allocates resources (buffers, fonts, ...).
The slideshow only defines the content to be drawn.
In the live code, only the slideshow is modified, so the system and renderer states are not affected.
Doing reloading at the module granularity meshes well with ML semantics: it is a straightforward extension of the "hyperstatic environment" and it preserves type safety and modular abstraction.
A static language that is designed with hot reloading in mind could do better, the generative nature of ML type definitions is not ideal.
I guess that structural type systems permit a finer grained notion of reloading. Actually, a finer-grained notion of persistence and state migration could be built as a library (with some macros) on top of Hotcaml. The important step is to be able to reify type definitions and then to define some notion of "type compatibility" (between old and new modules) by induction on the structure of types.
This is a lot of work, but could be built on top of Hotcaml foundations.
> Reloading is done at the granularity of a module. The reverse dependencies of a module that changed are also reloaded, but the dependencies are not. The runtime state of all modules that are not reloaded is persisted.
Ah that makes sense to me, and explains to me why in your linked demo the rotation resets after every color change, but the other stuff doesn't. That does mean though that having the circle not reset after every color change is probably not feasible unless the module order is fairly convoluted right? (because most straightforward ways I can think of organizing the code would have the circle motion as a reverse dependency of the color of the circle).
> having the circle not reset after every color change is probably not feasible unless the module order is fairly convoluted right?
Not necessarily no. The thing is that you could have an early module that implements a framework to manage state.
For the circle rotation, it is quite easy, it is a single number.
You could do something like:
"The rotation of the circle is represented by a float initialized to 0".
Then even when your module is reloaded, the hypothetical framework takes care of preserving this piece of state.
The output is a bit underwhelming. You might be interested in https://codinuum.github.io/gallery-cca/
It is not based on tree sitter , the parsers they use are quite impressive. Yet a difficult part is computing large tree diff (it is O(n^3) if I remember well), the authors devise heuristics that are efficient in practice and should be adaptable to tree sitter.
Indeed. GADTs provide type equalities and existentials. This example involves neither, only sub-typing (which is quite strong and interesting in Typescript)
Something pretty similar to the AST example in another thread can be implemented in Typescript using sub typing (as it happens, trying to do something like that is how I first found out about GADTs). Looking into existential types, I see that one of the things they can be used for is OOP style subtype polymorphism [1]. Are there things you can do with existential types that can't be done with subtyping?
An ADT is a "closed" type like an enum, which then enables other features that you can't implement for OO-style "open" subtyping (e.g. pattern matching). You can encode that in a traditional-OO language with the visitor pattern, but it's very cumbersome to work with in practice.
The other subtle thing with GADTs is that the type information must flow back from the matched case to the type parameter: if you match an Ast<R> and get Mul, you know that R=Int. And that part is impossible to do fully in a language that doesn't have higher-kinded types, because you not only need to be able to know that you can pass an Int where an R was expected, but also that you can pass an Ast<Int> where an Ast<R> is expected, or return a List<Int> where a List<R> is expected, or....
That might seem counter-intuitive, but tracing GC is the fastest way to manage memory in general (arbitrary life time, graph shapes and allocation patterns).
It permits really fast allocation, defragmentation and is sometime the only way to manage memory (cyclic datastructures for which reachability cannot be known directly from program text).
Reference-counted GC on the other hand is notoriously slow, incomplete, and exhibit lots of bad performance patterns (that can be somehow managed by taking some elements of tracing GCs).
The drawback is that tracing GCs are very hard to implement, to tune, and sometimes not all of the benefits are available at the same time. And because they are so counter intuitive, programmers in general have a hard time understanding their runtime behavior... Even GC experts struggle (the skills required range from low-level hardware to control theory, otherwise performance at scale is unpredictable).
In C/C++ we have the possibility to avoid dynamic allocation altogether and to use system features like memory mapping. If we use C++ the same way as Java (everything dynamically) it's not too surprising the result is not (much) faster than Java.
Their original implementation was in common lisp. Common Lisp also lets you use mmap (in fact it's not that uncommon to do so if you have a large amount of mostly static data) to manage your memory manually.
They clearly wanted automatic memory management, so the C++ implementation is reasonable. A fairer comparison might have used MPS or boehm instead of refcounting, but I suspect the results would have been similar.
Fig. 4 shows that deallocation, presumably of objects allocated during the first phase, takes half as long as the first phase itself. Unless the nature of the problem solved by the program requires you to have a ton of objects with shared mutability (the use case for shared_ptr), and requires you to make a lot of allocations up-front without knowing if you will need them, the memory thrashing occurring does not seem reasonable.
> But not without allocating dynamic memory and copying data.
Sure it does. In SBCL you can force a stack allocation (though rarely does it improve performance), and very short-lived values do not leave registers in any case.
> > They clearly wanted automatic memory management
> Most likely because of some misconceptions.
There are both good and bad reasons to want automatic memory management. At least one good reason it it would decrease the porting effort by keeping the code similar.
> > so the C++ implementation is reasonable.
> How so?
Using reference counting is a reasonable way to get automatic memory management in C++
> > but I suspect the results would have been similar
> Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB.
Which is going to be rough on any automatic memory management system, which makes using a language with a better ecosystem of automatic memory management more performant.
> > Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB.
> Which is going to be rough on any automatic memory management system
You could equally say that it makes the case for actually designing memory allocation strategy (which only C++ really supports) that much more important.
You always see this in Java programs for large data analysis. They pick java because of memory management and the tooling. But it's just SO slow and after optimisation the only thing that stubbornly remains up there in the profiler data is memory and GC. And what do they do?
A global object of the following form:
class DataStore {
float theFloatsWeNeed[constHowMany];
int theIntsWeNeed[anotherConst];
}
You get the idea. Because this avoids memory allocation in java. And you use the flyweight pattern to pass data around. Or you fake pointer arithmetic in java. You create your own pointers by specifying indexes and you oh the horror use math on those indexes. Even then just checking those indexes actually becomes a significant time sink (and then you disable that, which of course kills memory safety in java, but you won't care).
The truth is you don't want memory management for large amounts of data. You don't want to allocate it, track it or deallocate it at all. You leave it in it's on-disk data format and never serialize/deserialize it at all. You want to mmap it into your program, operate on it and then just close the mmap when you're done. C++ definitely has the best tools for this way of working.
Yeah, right. The people who know this can apparently be counted on one hand when I look at the advertised publication and the discussion in this forum.
C++: It is permissible for an implementation to allocate every local variable on the heap.
Going back to my original point, you are suggesting a complete rearchitecture of their allocation system. That does not require switching languages to C++. If we are talking about working with 100s of GB of data, that's probably even the correct approach!
TFA does not, however, claim that they have a working set of 100s of GB of data. The data is 100s of GB at rest, but can be processed in chunks with a single pass. That, by itself, does not scream "mmap" to me. On top of that, the data is compressed at rest, so copying is inevitable.
So we are glad that we can use the data of the memory mapped file directly and do not have to allocate or copy anything. But of course you may solve the problem badly if you prefer so; after all, there are even "scientific" publications that do it that way, as the example shows.
