Bug#881692: command-not-found: I re-wrote command-not-found

[Julian Andres Klode]

On Tue, Nov 14, 2017 at 03:35:02PM +0000, John Lenton wrote:
> On 14 November 2017 at 12:34, Julian Andres Klode <jak at debian.org> wrote:
> > On Tue, Nov 14, 2017 at 01:00:54PM +0100, Zygmunt Krynicki wrote:
> >> I would love if we have a compact representation of mapping from name
> >> to list of bits of information where each bit can be a small structure
> >> with some data. Apart from components for ubuntu archive it could be
> >> used to store facts about snap packages, flatpaks, etc. I would try to
> >> avoid a simplistic command -> package mapping as that will force us to
> >> encode things into strings in an ad-hoc way.
> >
> > That makes sense to me. But then we're back on a db, I guess. I sort
> > like this minimal approach.
> 
> I was thinking in the other direction, was going to see how it behaved
> with sqlite as the store. Would that be objectionable?

Using a relational database for a simple key -> structure mapping seems
overkill and a mismatch for the problem, and the SQL does not make it
more readable.

I'd play with lmdb and kyotocabinet, these are two high-performance
key-value file databases and then encode a structure as mentioned
before.

For the text file approach, we can even go human, readable, like git:

git just encodes a number in a fixed-length decimal number, we can do
the same, and then just encode (length, key), (length, data) pairs after
each other (or as mentioned, just use the "index" as the field id, and
store field ids in the progrma). Uses a bit more space, but encodes
everything in a format you could read with a text editor, and should
not be terribly less efficient.

The thing is: This needs to be as efficient as possible: it should
be below 100ms (or better 50ms), regardless of whether caches are dropped
or not.

		Python code	|	Shawn's code

SSD, cache		50ms			5ms
SSD, " dropped	       256ms		       15ms
HDD, cache		50ms		        5ms
HDD, " dropped         530ms                   15ms

I guess Shawn's code could even be improved in performance by
avoiding the subprocess execution, avoiding various ld cache
lookups and library loads.

That said, space requirements might matter too.
-- 
Debian Developer - deb.li/jak | jak-linux.org - free software dev
Ubuntu Core Developer                              de, en speaker