Re: Latest guile-daemon changes and bewilderment

[Mark H Weaver <mhw@netris.org>]

Caleb Ristvedt <caleb.ristvedt@cune.org> writes:

> This includes reference-scanning, which I think pretty much works, but
> which I regret to say I spent too much time thinking about. Premature
> optimization and all that. It takes a rather different approach to the
> way the C++ code does it - it uses a trie to recognize references out of
> a list of possibilities (namely, anything thrown in the build
> environment's store). The idea is that additional pre-calculation can be
> performed on each node and it can become a sort of branching skip table
> of the sort used in that one string-matching algorithm whose name I
> can't remember.

Maybe you're thinking of the Boyer-Moore string search algorithm:

  https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

You might also want to take a look at the simple algorithm I cooked up
to make grafting faster, in (guix build graft).  In theory it might be
improved by building some kind of lookup table based on the set of
expected hashes, as you suggest, but I wasn't sure if it would be a net
win, given the added code complexity and larger lookup tables.  We can
skip quite a lot simply based on the fact that Nix hashes include only
1/8 of the possible byte values, and exclude the most common letters
from English text.  More investigation is needed!

    Regards,
      Mark