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 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.
> 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.
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.
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.
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.
> 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.
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.
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)
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).
I did a part of the incremental parsing in Menhir and the whole recovery aspect. I can try to explain a bit.
My goal was Merlin (https://github.com/ocaml/merlin/), not research so there is no paper covering the work I am about to describe. Also as of today only incrementality and error message generation are part of upstream version of Menhir, but the rest should come soon.
# Incrementality, part I
The notion of incrementality that comes builtin with Menhir is slightly weaker than what you are looking for.
With Menhir, the parser state is reified and control of the parsing is given back to the user. The important point here is the departure from a Bison-like interface. The user of the parser is handled a (pure) abstract object that represents the state of the parsing.
In regular parsing, this means we can store a snapshot of the parsing for each token, and resume from the first token that has changed (effectively sharing the prefix).
But on the side, we can also run arbitrary analysis on a parser (for error message generation, recovery, syntactic completion, or more incrementality...).
# Incrementality, part II
Sharing prefix was good enough for our use case (parsing is not a bottleneck in the pipeline). But it turns out that a trivial extension to the parser can also solve your case.
Using the token stream and the LR automaton, you can structure the tokens as a tree:
- starts with a root node annotated by the state of the automaton
- store each token consumed as a leaf in that tree
- whenever you push on the automaton's stack, enter a sub-level of the tree (annotated by the new state), whenever you pop, return to the parent node
This gives you the knowledge that "when the parser is in state $x and $y is a prefix of the token stream, it is valid to directly reduce the subtree $z".
In a later parse, whenever you identify a known (state number, prefix) pair, you can short-circuit the parser and directly reuse the subtree of the previous parse.
If you were to write the parser by hand, this is simply memoization done on the parsing function (which is defunctionalized to a state number by the parser generator) and the prefix of token stream that is consumed by a call.
In your handwritten parser, reusing the objects from the previous parsetree amounts to memoizing a single run (and forgetting older parses).
Here you are free to choose the strategy: you can memoize every run since the beginning, devise some caching policy, etc (think about a user (un)commenting blocks of code, or switching preprocessor definitions: you can get sharing of all known subtrees, if this is of any use :)).
So with part I and II, you get sharing of subtrees for free. Indeed, absolutely no work from the grammar writer has been required so far: this can all be derived by the parser generator (with the correctness guarantees that you can expect from it, as opposed to handwritten code).
A last kind of sharing you might want is sharing the spine of the tree by mutating older objects. It is surely possible but tricky and I haven't investigated that at all.
I might be biased but contrary to popular opinions I think that LR grammars are well suited to error message generation.
The prefix propery guarantees that the token pointed out by the parser is relevant to the error. The property means that there exist valid parses beginning with the prefix before this token. This is a property that doesn't hold for most backtracking parsers afaik, e.g PEG.
Knowledge of the automaton and grammar at compile time allow a precise work on error messages and separation of concerns: the tooling ensures exhaustivity of error coverage, assists in migration of error messages when the grammar is refactored, or can give an explicit description of the information available around a given error.
This is not completely free however, sometimes the grammar needs to be reengineered to carry the relevant information. But you would have to do that anyway with a handwritten parser and here the parser generator can help you....
If you have such a parser generator of course :). Menhir is the most advanced solution I know for that, and the UX is not very polished (still better than Bison). It is however a very officient workflow once you are used to it.
So LR is not the problem, but existing tools do a rather poor job at solving that kind of (real) problems.
# Recovery
In Merlin's, recovery is split in two parts.
The first is completion of the parsetree: for any prefix of a parse, it is possible to fill holes in the tree (and thus get a complete AST).
This is done by a mix of static analysis on the automaton and user guidance: for major constructions of the AST, the grammar writer provide "dummy" constructors (the node to use for erroneous expressions, incomplete statement, etc).
The parser generator then checks that is has enough information to recover from any situation, or point out the cases it cannot handle.
It is not 100% free for the grammar writer, but for a grammar such as OCaml one it took less than an hour of initial work (I remember only a few minutes, but I wasn't measuring properly :)). It is also a very intuitive step as it follows the shape of the AST quite closely.
The second part is resuming the parse after an error (we don't fill the whole AST every time there is an error; before filling holes we try to look at later tokens to resume the parse).
There is no big magic for that part yet, but the heuristic of indentation works quite well: constructions that have the same indentation in source code are likely to appear at the same depth in the AST, and this is used to decide when to resume consuming tokens rather than filling the AST.
I have a few lead for more disciplined approaches, but the heuristic works so well that it isn't an urgency.
# Conclusion
I would say that if I had to write a parser for a language for which a reasonable LR grammar exists, I will use a (good) parser generator without hesitation.
For the grammars of most programming languages, LR is the sweet spot between parsing expressivity and amenability to static analysis.
Do you mean making Merlin works in a Js_of_ocaml environment?
I am not familiar with JS programming model, but I think it should be possible to turn Merlin into a worker and have synchronous loading of "cmi" files via some service
(I don't want to do control inversion on the whole typechecker :)).
$ ./a.out 1000 1002 100001
google hash 0.0343956 49967527 8.34091e+09, different bins 207
bob jenkins hash 0.0039651 50033275 8.34095e+09, different bins 99794
google is 0.115279x faster
bob is 8.67458x faster
google moved 0.206998x% objects
bob moved 99.793x% objects
optimal distribution required 200 movements (0.199998%)
bob is performing extremely bad.
edit: updated the gist to include the integer version
Also, the google algorithm does O(log(bins)) iterations in the loop, which explains the speed advantage of bob one. Given the task accomplished, it's really efficient and near optimal.
