lazamar

Why not search the FM-indexes directly? It is faster than the n-gram search and you can use the exact full text of the needle.

At Meta they are using FM indexes to power text search through the entire commit history of their monorepo.

Lol. Loved it.

This was a lovely passage from Dyson’s Web of Stories interview, and it struck a chord with me, like it clearly did with the authors too.

It happened when Dyson took the preliminary results of his work on the Pseudoscalar theory of Pions to Fermi and Fermi very quickly dismissed the whole thing. It was a shock to Dyson but freed him from wasting more time on it.

Fermi: When one does a theoretical calculation, either you have a clear physical module in mind or a rigorous mathematical basis. You have neither. How many free parameters did you use for your fitting?

Dyson: 4

Fermi: You know, Johnny Von Neumann always used to say ‘with four parameters I can fit an elephant; and with five I can make him wiggle his trunk’.

Indeed, but worth noting that LZ is a modelling scheme, whilst Huffman is a coding technique.

That is, LZ determines, dynamically as it goes, what are all the elements we want to encode and their probabilities. Then you need a coder, like Huffman, to actually encode it.

In the post I used a semi-static zero-order byte-based model. Which means I counted the byte occurrences first and just used that count for the probabilities throughout all of the encoding. Then I used Huffman codes to translate those probabilities into bits.

But I'm considering writing a follow-up changing this static model for an LZ77 one as I think that would be fun.

The goal of this implementation is not to be fast, but to be clear.

I am doing some inefficient things (like two pass encoding) on purpose to keep things simple and clear. So using this particular piece of code to judge a language's performance potential is not really the way to go here.

Haskell's speed can be competitive with systems languages but keep in mind that its killer feature is ease of abstraction.

The idea is that it is simple to assemble multiple parts into a coherent, well organised program. Which is important for the entirety of the program, no just the tight loop.

So, with the nice FFI Haskell has, you can always drop down to languages without a GC for inherently imperative optimisations. Then you wrap that into a library with nice types and you can now leverage that raw power anywhere in your Haskell code where the types will match.

I worked at Meta in a high performance Haskell application and that's what we did. Wrote beautiful, large, fast Haskell programs which in some specialised parts had C++ building blocks. 99% of the time was spent on Haskell land composing things into more and more useful applications.

Fixed it. Well spotted!

I’d say unbeatable!

The goal was simplicity of implementation and code clarity. For this kind of thing I say Haskell performs the best.

That’s interesting. I guess this is not usually used because you may have a long string of bits that is ambiguous till you get to a disambiguating bit.

Something like

`100000000000000001`

In this case, where to know whether the first code was an `a` or a `c` you have to read all the way to where the zeroes end.

There is one way in which Huffman codes are better: they are easier to explain and simpler to implement.

I went for simplicity of exposition in the post, but arithmetic coders can indeed get arbitrarily close to the entropy, which is not quite the case with Huffman.

Thanks for the link. I was motivated to write the post after reading Moffat’s book ‘Managing Gigabytes’. A pearl from the 90’s.

The authors mention this technique in the second edition.

The most effective solution I found was keeping my phone in my backpack instead of my pocket. When working I keep it somewhere I’d need to get up to get it.

Together with taming notifications this provides enough friction to discourage me from reaching for it at every spare second.

Once the phone reaches my hands the tricks in the post are not enough to remove the need for conscious effort to let go of the thing and put it back in its inconveniently positioned place.

Do you mean whether nodes could be rearranged without recreating them? This would require identifying them with IDs, like React can do. That's definitely possible, but not something covered in the article or supported in the associated library. Although the article does mention it.

Julia’s explanations are clear and fun, I hope she keeps doing that for a very long time.

Thanks. I’ve just wasted 2 hours.

Loved the game.

To make it generate winnable games just start from a solution and keep expanding it until you get to the initial game state.

Glean is focused on storing and querying data about the code. The idea is that you have your own program to collect that data, then you use Glean to store that compactly and to have snappy queries.

You would create entries like "this is a declaration of X", "this is a use of X". Then you can query things like "give me all uses of X" in sub-millisecond time. You hook that up to an LSP server then you get almost zero-cost find-references, jump-to-definition, etc. The snappy queries also mean it becomes possible to perform whole codebase (and cross-language) analysis. That is, answering questions like "what code is not referenced from this root?", "does this Haskell function use anything that calls malloc?" (analysis through the ffi barrier).

One can also attach all kinds of information from different sources to code entities, not only things derived from the source itself. You add things like run-time costs, frequency of use, common errors, etc, and an LSP server could make all of it available right in your editor.

For very large or complex codebases, where it is just too expensive or too complicated to calculate this information locally a system like this becomes very useful.

I followed that curriculum and it sorted me out with regards to algorithms and networking. I recommend it very highly.

The idea is that once you have read these books you have the knowledge needed to identify what kind of problem you have in front of you, what tools are known to solve it, what are their disadvantages, and most importantly what should you search for to find out more about the problem.