Faster guix search using an sqlite cache

Hi,

As discussed on guix-devel at

https://lists.gnu.org/archive/html/guix-devel/2020-01/msg00310.html, I

am working on an sqlite cache to improve guix search performance. I have

attached a highly incomplete WIP patch. The patch attempts to

reimplement the package-cache-file hook in guix/channels.scm using a

sqlite database. To this end, it rewrites most of the

generate-package-cache and cache-lookup functions in gnu/packages.scm. I

am yet to hook this up to guix search.

At the moment, I am having some difficulty populating the sqlite

database. generate-package-cache populates the database correctly when

invoked from a normal guile REPL using geiser, but fails to do so when

run by the guix daemon during guix pull.

I ran guix pull using

$ ./pre-inst-env guix pull --url=$PWD --branch=search -p /tmp/test

where search is the branch I am working on.

Running

$ ls /tmp/test/lib/guix -lh

shows

total 2.1M

-r--r--r-- 2 root root 2.1M ??. 1 1970 package-cache.sqlite

-r--r--r-- 2 root root 26K ??. 1 1970 package-cache.sqlite-journal

On examining package-cache.sqlite, I find that no records have been

written. And, there is a lingering journal file that shouldn't be

there. For some reason, populating the sqlite database does not work

with guix pull. sqlite probably crashes and leaves the journal file.

If I try to populate the database with each package record being

inserted in its own transaction, at least some of the insertions

work. But the journal file still lingers. My unverified guess is that

everything except the last transaction was successful.

Any ideas what's going on?

Also, inserting each package in its own transaction is ridiculously slow

and so that is out of the question. See https://www.sqlite.org/faq.html#q19

Hi Arun,

Thank you for the patch!

Cool! :-)

I have not tested it yet. Sorry.

On Thu, 23 Jan 2020 at 20:53, Arun Isaac <arunisaac@systemreboot.net> wrote:

[...]

Hum? weird...

Is it possible that a module is loaded when Guile repl is used and not

with Guix pull?

What about "guix repl"?

You mean 'commit' the database after each insertion, right?

And this does not happen with the repl, right?

I have no idea.

Weird.

What about adding 'last-insert-row-id' from 'guix/store/database.scm'?

I mean without really understanding and just grepping

'sqlite-finalize' spots that 'last-insert-row-id' seems often around.

:-)

Agree that it is not an option. :-)

Otherwise, 'list->string' is defined twice. And the first one is not

necessary, I guess.

The docstring of 'cache-lookup' is not coherent anymore. :-)

Cheers,

simon

It could be. But I don't know how to confirm this theory.

I just tried 'guix repl'. It worked correctly, just like guile repl.

Yes, that is what I mean.

No, this does not happen with the repl.

Do you know of any way sqlite can create an error log to report what's

going on? That might really help debug this issue.

I tried this just now, but still the journal lingers.

Ah, thanks for catching this!

Yes, I haven't gotten around to fixing up all those yet. I thought I'll

get the code working first.

Hi,

On Thu, 30 Jan 2020 at 14:49, Arun Isaac <arunisaac@systemreboot.net> wrote:

[...]

Danny told me something like:

(catch (sqlite-error

I have not tried yet.

Yes, I imagine. Just to notice. :-)

All the best,

simon

Thank you, this was useful. I was able to catch and report the error. I

also found the log file for the guix-package-cache profile hook. It says

(repl-version 0 0)

Generating package cache for '/gnu/store/b6f9b5qbcn4r932whrr6m15rdimbgrhs-profile'...

(exception sqlite-error (value sqlite-open) (value 14) (value "Unable to open the database file"))

This could be a permission error, or something to do with the existence

or lack thereof of certain directories (such as /var) in the chroot of

the build daemon. I'm still figuring it out.

I'm also in half a mind to get some guile xapian bindings ready so we

can just do that instead of messing with sqlite here. But, let's

see. :-P

Hi,

On Sun, 2 Feb 2020 at 22:16, Arun Isaac <arunisaac@systemreboot.net> wrote:

Where have you reported the error?

Hum? And this should explain why it is working with the REPL and not

with the CLI, right?

Cool!

Let me know if you push something somewhere.

Cheers,

simon

I reported the error to the derivation log. For example, if the

derivation for the guix-package-cache derivation is

/gnu/store/cyf2h3frcjxm147dii5qic8d6kpm39nq-guix-package-cache.drv, the

log file will be at

/var/log/guix/drvs/cy/f2h3frcjxm147dii5qic8d6kpm39nq-guix-package-cache.drv.bz2. Notice

that the directory name under drvs is the first two letters of the hash,

and the file name under that directory is the remaining letters.

Also please find attached a dump of my code so far.

This could expalin it, but I am not sure if this is the correct

explanation.

Sure, will let you know.

Hello Arun!

Arun Isaac <arunisaac@systemreboot.net> skribis:

[...]

[...]

I would rather keep the current package cache as-is instead of inserting

sqlite in here. I don’t expect it to bring much compared

performance-wise to the current simple cache (especially if we look at

load time), and it does increase complexity quite a bit.

However, using sqlite for keyword search as you initially proposed on

guix-devel does sound like a great idea to me.

WDYT?

Thanks,

Ludo’.

Hi Ludo,

On Tue, 11 Feb 2020 at 17:29, Ludovic Courtès <ludo@gnu.org> wrote:

Complexity is about taste. ;-)

About performance, the idea was to first implement something with

sqlite and then see if it makes the difference. I mean I have

understood that.

If I understand correctly, you are proposing 2 caches, right?

Or are you proposing an inverted index (VHash/VList table) based on

trigrams to speed up the lookup?

Cheers,

simon

zimoun <zimon.toutoune@gmail.com> skribis:

It’s measurable to some extent (lines of code, cyclomatic complexity,

etc.)

Yes. But keep in mind that this package cache is used exclusively for

package lookups by name. Namely, the goal is to speed package lookup in

operations like “guix install foo” (mapping “foo” to the right <package>

in the right module without walking through all the modules) and “guix

package -A” (which is what the shell completion hooks use).

Currently “guix package -A” runs in .5s on my laptop, and I suspect it’s

going to be hard to do better just by touching the cache.

Arun started the discussion on guix-devel with the idea of an inverted

index, and I thought this would become a second index (possibly

implemented using SQLite). Perhaps I misunderstood the discussion all

along though, let me know! :-)

Thanks,

Ludo’.

I agree with Ludo here. I think it does increase the complexity, and

probably unnecessarily so.

No, you didn't misunderstand. That's where it began. But, while

implementing it, I thought I might as well replace the existing cache.

Also, I've started working on guile-xapian bindings. With that, it seems

simpler to keep the current package cache and add a xapian index only to

speed up package search.

Hi Ludo,

On Tue, 11 Feb 2020 at 19:39, Ludovic Courtès <ludo@gnu.org> wrote:

I agree that some confusion happens here. And this cache cannot be improved.

Well, your suggestion is very welcome and 2 caches are required: one

for the lookup by name, as it is already (and does a good job);

another one for "guix search" speeds up, SQLite or whatever (based on

inverted index or whatever).

Thanks,

simon

Hi Arun,

On Tue, 11 Feb 2020 at 20:07, Arun Isaac <arunisaac@systemreboot.net> wrote:

An inverted index backed by Guile as you did on guix-devel or backed

by SQLite seems a good improvement for "guix search".

Xapian would be cool!

And an SQLite based index seems easier to index locally the packages

and their history. The Guix Data Service is already doing such thing

but AFAIK using PostgreSQL and some magic. :-)

All the best,

simon

I have published the first version of guile-xapian! Feedback is

welcome. :-)

I will now move on to building a Xapian index for Guix's package search.

Hi,

I have finally got xapian working for package search. Some comments follow.

Despite search-package-index in gnu/packages.scm taking only around 1.5ms, I

see an overall speedup in `guix search` of only a factor of 2 -- from around

2s to around 1s. I wonder what else in `guix search` is taking up so much

time.

In this patchset, I have only indexed the package descriptions. In the next

version of this patchset, I will index all other terms as specified in

%package-metrics of guix/ui.scm.

gnu/packages/package-management.scm?

In this patchset, I have retained the older regexp search support. But, I

think we should drop it and only have xapian search. In cases where the search

index is not authoritative, we can build an in-memory xapian search index on

the fly and use it to search. This will slow down the search, but will ensure

our search results are consistent and do not depend on the authoritativeness

of the search index.

Except for patch 1, I am not sure what prefixes (build-self, gnu, etc.) to use

in the first line of the commit message. Some advice there would be helpful.

Regards,

Arun.

Arun Isaac (4):

gnu: Add guile-xapian.

build-self: Add guile-xapian to Guix dependencies.

gnu: Generate xapian package search index.

gnu: Use xapian index for package search.

build-aux/build-self.scm | 11 ++++++++

gnu/packages.scm | 44 ++++++++++++++++++++++++++++-

gnu/packages/guile-xyz.scm | 50 ++++++++++++++++++++++++++++++++-

guix/channels.scm | 34 ++++++++++++++++++++++-

guix/scripts/package.scm | 57 ++++++++++++++++++++++----------------

guix/self.scm | 7 ++++-

6 files changed, 175 insertions(+), 28 deletions(-)

--

2.23.0

(generate-package-search-index): New function.

(%channel-profile-hooks): Add package-search-index.

---

gnu/packages.scm | 29 ++++++++++++++++++++++++++++-

guix/channels.scm | 34 +++++++++++++++++++++++++++++++++-

2 files changed, 61 insertions(+), 2 deletions(-)

xapian package index if search patterns are literal strings. Else, search

using fold-packages.

---

gnu/packages.scm | 17 +++++++++++-

guix/scripts/package.scm | 57 +++++++++++++++++++++++-----------------

2 files changed, 49 insertions(+), 25 deletions(-)

---

gnu/packages/guile-xyz.scm | 50 +++++++++++++++++++++++++++++++++++++-

1 file changed, 49 insertions(+), 1 deletion(-)

---

build-aux/build-self.scm | 11 +++++++++++

guix/self.scm | 7 ++++++-

2 files changed, 17 insertions(+), 1 deletion(-)

Arun Isaac <arunisaac@systemreboot.net> writes:

I guess these non-functional functions (index-text!, replace-document!)

represent how Xapian works at the C++ level. Would it be possible to

make more functional bindings nonetheless?

--

Pierre Neidhardt

Arun Isaac <arunisaac@systemreboot.net> writes:

Maybe `query-string'?

Need to update the docstring.

I would not put characters like ".", "$", or "+" here, lest we mistake a

Xapian pattern for a regexp.

As you said, I don't think both are compatible without ambiguity

anyways, so we should probably drop regexp (or at least toggle them with

a command line argument).

--

Pierre Neidhardt

Fantastic, thank you so much for this great feature!

I can't build your patch though:

Beside this issue, how do you test it? I guess we first need to install

a bunch of package with `pre-inst-env guix ...` then to a `pre-inst-env search`?

--

Pierre Neidhardt

Hi Arun,

Really cool! Thank you!

On Thu, 27 Feb 2020 at 21:42, Arun Isaac <arunisaac@systemreboot.net> wrote:

Interesting... maybe an hidden 'fold-packages'?

Well, I have not yet looked into your code.

Yes, it appears to me a detail that should be easy to fix. I mean, it

does not seems blocking.

IMHO, yes.

I mean, I guess. :-)

I understand why you have turned off the regexp support. It is not

necessary at the first experimentation to see if it is worth the

addition or not.

So, before investigating how some better regexp could be used with

Xapian, let start to benchmark Xapian vs plain 'fold-packages'.

I cannot help. )-:

All the best,

simon

Hi Pierre,

On Fri, 28 Feb 2020 at 09:13, Pierre Neidhardt <mail@ambrevar.xyz> wrote:

It is not searching in the installed packages but in all the packages.

So, to test it, you need to "./pre-inst-env guix pull -p" or something

like that to populate the Xapian index database. Then "./pre-inst-env

guix search" will lookup into.

I mean, it is how I understand it should work. I have not yet looked

into the code.

Cheers,

simon

zimoun <zimon.toutoune@gmail.com> writes:

What I meant with "install a bunch of packages" is "guix pull -p", is

you said. Xapian cache

is populated as a hook of guix pull if I got it correctly.

--

Pierre Neidhardt

Sorry, I forgot to mention this in my patch cover letter. The above

error is happening because of the new guile-xapian dependency. It's a

little tricky to get right at the moment. Here goes.

Drop into a guix development environment.

$ guix environment guix

Commit patch 1 (the patch that adds guile-xapian) alone, and build.

$ git am 0001-gnu-Add-guile-xapian.patch

$ make

Then, drop into an environment where guile-xapian is available.

$ ./pre-inst-env guix environment guix --ad-hoc guile-xapian

Apply the other 3 patches and build.

$ git am 0002-build-self-Add-guile-xapian-to-Guix-dependencies.patch 0003-gnu-Generate-xapian-package-search-index.patch 0004-gnu-Use-xapian-index-for-package-search.patch

$ make

Now, the build should have completed successfully. Let's do a test guix

pull to actually test the new guix search.

$ ./pre-inst-env guix pull -p /tmp/test

Then, run the guix search in /tmp/test.

$ /tmp/test/bin/guix search game

That's it! :-)

This whole process will be simpler if the guile-xapian package is pushed

to master and guile-xapian added as an input to the guix package in

gnu/packages/package-management.scm. But, for now...

One mistake. This command should be

./pre-inst-env guix pull --url=$PWD --branch=xapian -p /tmp/test

where xapian is the name of the branch you committed the patches to.

Also, I acknowledge the corrections you both suggested. I will

incorporate them in v2 of the patchset.

Shall I push patch 1 (add guile-xapian) alone to master?

Hi Arun,

On Sat, 29 Feb 2020 at 09:25, Arun Isaac <arunisaac@systemreboot.net> wrote:

Yes, it seems a good idea and it will ease the process for building

and then benchmarking the "guix search" via Xapian.

All the best,

simon

Hi Arun,

Do you have some benchmark in mind?

On Fri, 28 Feb 2020 at 17:05, Arun Isaac <arunisaac@systemreboot.net> wrote:

We need to benchmark on different machines the new "guix pull". Well,

it is nothing compared to the derivation computations. :-)

And more importantly, 'make as-derivations' to avoid a "guix pull" breakage,

Then on cold caches, the new "guix search" for a couple of query.

There is no so much inspiration in tests/. :-)

Ah do not forget to adapt some tests.

All the best,

simon

Hi,

After a quick benchmark:

a. It is faster. Between x2 and x3. Really?

b. The xapian relevance should truncated and examined in more details.

Here for example, Xapian does not return the package 'emacs' itself as

the first. And worse, it is not returned at all.

That's said, I do not know if it is really faster since:

and

Maybe I am doing a mistake.

Well, thank you Arun for the Xapian bindings which will improve the

searching experience. :-)

And now it needs some polishing.

All the best

simo

Hi Arun,

On Thu, 27 Feb 2020 at 21:42, Arun Isaac <arunisaac@systemreboot.net> wrote:

I am a bit lost with the Guile update. Now the convention should not

be the opposite: guile-xapian using 3.0 and guile2.2-xapian using 2.2

(or simply 2.2 since 2.0 seems not really used).

Otherwise, feel free to push it. :-)

(It will ease to reach a large audience of testers for "guix search" ;-))

All the best,

simon

Hi Arun,

In the commit message, I would capitalize Xapian.

On Thu, 27 Feb 2020 at 21:42, Arun Isaac <arunisaac@systemreboot.net> wrote:

Xapian with capital.

Instead, this:

(index-term! term-generator (string-append (package-synopsis package)

(package-description package)))

should index both 'synopsis' and 'description'.

Is (make-stem "en") for the locale?

package-search-index and package-cache-file could be refactored

because they share all the same code.

Hi Arun,

On Thu, 27 Feb 2020 at 21:42, Arun Isaac <arunisaac@systemreboot.net> wrote:

Why this value of 10?

This fix the number of packages returned. Hum?

I have tried to replace by 100 and I got 100 packages. :-)

I do not know what is the convention for the bindings.

But there is 'fold-packages' so I would be inclined to 'fold-msets' or

something in this flavour.

Instead of reverting this, I would let the current

'find-packages-by-description' and would add

'find-packages-by-description-indexed' doing just

'(search-package-index (current-profile) (string-join patterns " "))'.

And maybe refactoring the sort of scores. Then I would put the test

branch in 'guix/scripts/packages.scm'...

Note that I am in the process of implementing the BM25 weights as

'package-relevance'; at least really thinking about it! :-)

I have already talked about TF-IDF as relevance, for example here [1].

And reading the Xapian documentation [2], it seems affordable. Or not

;-) because of the regexp... Need some thoughts... I mean "in the

process". ;-)

And in this case, it is almost a drop-in replacement of

'fold-packages' by 'mset-fold'; well it should add some flexibility

and a more unified code.

(Aside the searching, IMHO 'package-relevance' should help too in the

linting process of bad written descriptions, another story. ;-)

[1] https://lists.gnu.org/archive/html/guix-devel/2019-07/msg00252.html

[2] https://xapian.org/docs/bm25.html

...here.

+ (define (regexp? str)

+ (string-any

+ (char-set #\. #\[ #\{ #\} #\( #\) #\\ #\* #\+ #\? #\| #\^ #\$)

+ str))

+ (if (any regexp? patterns)

+ (matches (find-packages-by-description regexps))

+ (matches (find-packages-by-description-indexed patterns))

I mean something like that.

All the best,

simon

On Tue, 3 Mar 2020 at 20:21, zimoun <zimon.toutoune@gmail.com> wrote:

I propose the value of 4294967295 for pagesize.

Hi,

On Mon, 2 Mar 2020 at 20:13, zimoun <zimon.toutoune@gmail.com> wrote:

I think this issue is fixed when changing the 'pagesize' value.

Well, with '(pagesize 4294967295)' and using the same commit

(c1febbbf94), I get:

(I modified the patches in order to pull once to generate the index at

commit c1febbbf94 and then do some stuff.)

Note that the old "guix search" does not output blender and Xapian

does even if the term 'games' is not in the description but 'game' is.

Well, I am comparing the different list, i.e., "guix search games |

recsel -C -P name | sort" to see which one is in one list and not the

other one.

But before going more ahead, let polish a bit the patches to more

easily test without the double environment etc.

And because I am using good old HDD and some SSD comparison should be welcome.

All the best,

simon

Hello Arun,

Arun Isaac <arunisaac@systemreboot.net> skribis:

Note that ‘guix search’ time is largely dominated by I/O. On my laptop,

I get (first measurement is cold cache, second one is warm cache):

It’s hard to do better on the warm cache case because at this level,

there may be other things to optimize having little to do with searching

itself.

Note that this is on an SSD; the cold-cache case must be worse on NFS or

on a spinning disk, and there we could gain a lot.

I think we should weigh the pros and cons on all these aspects: speed,

complexity and maintenance cost, search result quality, search features,

etc.

Thanks,

Ludo’.

PS: I have not yet looked at the whole series as I’m just coming back to

the keyboard. :-)

I somehow overlooked this particular email and am reading it just

now. Yes, the non-functional bindings are a bit ugly. But, I'm not able

to think of a clean way to make functional bindings without supporting

all features offered by xapian. Any suggestions you have in this regard

would be useful. Look through xapian/termgenerator.h for more

details. In particular, look at functions increase_termpos,

index_text_without_positions.

---

build-aux/build-self.scm | 11 +++++++++++

guix/self.scm | 7 ++++++-

2 files changed, 17 insertions(+), 1 deletion(-)

(generate-package-search-index): New function.

(%channel-profile-hooks): Add package-search-index.

---

gnu/packages.scm | 42 +++++++++++++++++++++++++++++++++++++++++-

guix/channels.scm | 34 +++++++++++++++++++++++++++++++++-

guix/ui.scm | 2 ++

3 files changed, 76 insertions(+), 2 deletions(-)

index if current profile is available. Else, search using regexps.

---

gnu/packages.scm | 22 +++++++++++++++++++++-

guix/scripts/package.scm | 7 +++++--

guix/ui.scm | 35 +++++++++++++++++++++++++++++++++++

3 files changed, 61 insertions(+), 3 deletions(-)

Hi,

Here is the second iteration of my Xapian Guix package search patchset. I have

found the reason the earlier patchset did not show significant speedup. It

turns out that most of the time is spent in printing and texinfo rendering of

the search results. So, in this patchset, I pre-render the search results

while building the Xapian index and stuff them into the Xapian database

itself. Therefore, during `guix search`, I just pull out the pre-rendered

search results and print it on the screen. This is much faster. See comparison

below.

If most of the speedup comes from pre-rendering the results, it might seem

that the Xapian search is not so useful. We might as well have stuffed the

pre-rendered search results into the existing package cache generated by

generate-package-cache, or so it might seem. But, there are the following

arguments in favor of Xapian.

- The package cache would grow in size, and lookup would be slowed down

because we need to load the entire cache into memory. Xapian, on the other

hand, need only look up the specific packages that match the search query.

- Xapian can provide superior search results due to it stemming and language

models.

- Xapian can provide spelling correction and query expansion -- that is,

suggest search terms to improve search results. Note that I haven't

implemented this yet and is out of scope in this patchset.

Why not use a simpler package search results format like Arch Linux or Debian

does? We could just display the package name, version and synopsis like so.

inkscape 0.92.4

Vector graphics editor

inklingreader 0.8

Wacom Inkling sketch format conversion and manipulation

Why do we need the entire recutils format? If the user is interested, they can

always use `guix package --show` to get the full recutils formatted

info. Having shorter search results will make everything even faster and much

more readable. WDYT?

To get guile-xapian, run a `guix pull`, if you haven't already. Then in your

Guix source directory, drop into an environment with guix dependencies and

guile-xapian.

$ guix environment guix --ad-hoc guile-xapian

Apply patches and build.

$ git am v2-0000-cover-letter.patch v2-0002-gnu-Generate-Xapian-package-search-index.patch v2-0001-build-self-Add-guile-xapian-to-Guix-dependencies.patch v2-0003-gnu-Use-Xapian-index-for-package-search.patch

$ make

Run a test guix pull.

$ ./pre-inst-env guix pull --url=$PWD --branch=xapian -p /tmp/test

where xapian is the name of the branch you committed the patches to.

Then, run the guix search in /tmp/test.

$ /tmp/test/bin/guix search game

Pierre Neidhardt <mail@ambrevar.xyz> writes:

Done in this patchset.

I agree.

zimoun <zimon.toutoune@gmail.com> writes:

Done in this patchset.

Done in this patchset.

I still have English hard-coded. I haven't yet figured out how to detect the

locale and stem accordingly. But, there is a larger problem. Since we cannot

anticipate what locale the user will run guix search with, should we build the

Xapian index for all locales? That is, should we index not only the English

versions of the packages but also all other translations as well?

Yes, they could be. However, I'll postpone to the next iteration of the

patchset.

Well, everywhere else in guile we have such things as vhash-fold, string-fold,

hash-fold, stream-fold, etc. That's why I went with mset-fold. Also, we are

folding over a single mset (match-set). So, mset should be in the singular.

Will do this once we have consensus about the other features of this patchset.

Done in this patchset.

In this patchset, since we're indexing the package name as well, emacs is

returned but it is still far from the beginning.

In this patchset, I pass (database-document-count db) as the #:maximum-items

keyword argument to enquire-mset. This is the upstream recommended way to get

all search results. I hadn't done this earlier since I hadn't yet wrapped

database-document-count in guile-xapian.

Done in this patchset.

Ludovic Courtès <ludo@gnu.org> writes:

Yes, `guix search` is I/O intensive. That is why I expect Xapian to do better

since it only needs to access matching packages not all packages. Also, the

Xapian index is fast at all times. It is not very dependent on a warm

filesystem cache.

My laptop is quite old with a particularly slow HDD. Hence my motivation to

improve guix search performance!

I agree.

Welcome back! :-)

Arun Isaac (3):

build-self: Add guile-xapian to Guix dependencies.

gnu: Generate Xapian package search index.

gnu: Use Xapian index for package search.

build-aux/build-self.scm | 11 +++++++

gnu/packages.scm | 62 +++++++++++++++++++++++++++++++++++++++-

guix/channels.scm | 34 +++++++++++++++++++++-

guix/scripts/package.scm | 7 +++--

guix/self.scm | 7 ++++-

guix/ui.scm | 37 ++++++++++++++++++++++++

6 files changed, 153 insertions(+), 5 deletions(-)

--

2.25.1

Hello,

Arun Isaac <arunisaac@systemreboot.net> skribis:

Nice!

In general, pre-rendering doesn’t seem practical to me: the output of

‘guix search’ is locale-dependent (it speaks the user’s language) and

adjusts to the terminal width (well, this is temporarily broken on

Guile 3.0.0, but see ‘%text-width’ in (guix ui)).

Also, if the 12K+ descriptions need to be rendered at the time the user

runs ‘guix pull’, the experience may not be great, because it could take

a bit of time.

WDYT?

What I like about the recutils format in this context is that it’s both

human- and machine-readable. The examples in the manual show how it can

be useful to select the information displayed or to refine the search

(info "(guix) Invoking guix package").

Also: I’d recommend tackling one thing at a time. :-)

Yes, indeed.

Were you able to measure the cost of rendering specifically?

Here’s what I see when I turn ‘package->recutils’ into a no-op:

To compare with:

I think we should look at a profile of ‘package->recutils’, there’s

probably room for improvement there.

Thoughts?

Ludo’.

Also, when we put all package metadata into the Xapian index, we don't

have to look up any of the package variables in (gnu packages *) during

`guix search` time. This also contributes substantially to the speedup.

Note that we already need to index package synopses and descriptions in

all languages. I still haven't implemented this, though.

This could be accomplished even with pre-rendering. Xapian provides

"slots" to store arbitrary strings with a document. Instead of storing

the pre-rendered document as a whole, we could store pre-rendered fields

in separate slots. Then, during `guix search` time, we can assemble the

result from these pre-rendered fields.

This is a problem, but I would see it as a necessary "compilation"

step. :-P In fact, this whole patchset speeds up `guix search` by doing

part of the work of `guix search` ahead of time. So, some such cost is

unavoidable.

Xapian's query language is much more natural (as in natural language)

than the regexp based techniques we need to use with recutils. I have

hardly ever used the regexp based search and I suspect many others

haven't either. Also, refining the search query should be easier to do

with Xapian. We could even use Xapian's query expansion feature to

suggest improved queries to the user.

That said, if we want the recutils format, we can still keep it in a

simplified form like so.

name: inkscape

version: 0.92.4

synopsis: Vector graphics editor

name: inklingreader

version: 0.8

synopsis: Wacom Inkling skecth format conversion and manipulation

I totally agree, but I'm tempted to say that pre-rendering would be a

lot cheaper with the simplified form of search results. :-)

generate-package-search-index takes around 50 seconds. If I modify

generate-package-search-index to not pre-render but simply store the

package description alone, it takes around 20 seconds. That gives us a

rough idea of the cost of pre-rendering.

On quick inspection, most of the time in package->recutils is spent in

texinfo rendering the description. Unless we use the simplified search

results format as discussed above, we cannot avoid it.

Hi,

Arun Isaac <arunisaac@systemreboot.net> skribis:

Yup.

Oh, right. Tricky!

I’m not sure I understand. The index wouldn’t store pre-rendered

strings for every possible terminal width, right?

Yeah. I think we need to take the whole user experience into account,

not just ‘guix search’. ‘guix pull’ already feels very slow, and it’s a

fairly common operation. Conversely, ‘guix search’ takes roughly

between 0.5 and 2 seconds and is an uncommon operation on a “slow path”

(in the sense that when you’re searching for software, you’ll probably

have to spend more than a couple of seconds to find what you’re looking

for.)

I’m not sufficiently familiar with Xapian’s query language. The

examples I had in mind were:

guix search malloc | recsel -p name,version,relevance

guix search | recsel -p name -e 'license ~ "LGPL 3"'

guix search crypto library | \

recsel -e '! (name ~ "^(ghc|perl|python|ruby)")' -p name,synopsis

It’s not so much about regexps than it is about selecting individual

fields.

To me, adding 20–50 seconds on ‘guix pull’ would be undesirable. :-/

What I meant was that we could use (statprof) to see whether/how Texinfo

rendering/parsing can be optimized.

Thanks,

Ludo’.

Hi Arun,

Thank you for that.

I will be probably far from keyboard for a couple of days for medical

reasons* and I will not be able to look into this second set patches

soon.

Cheers,

simon

*nothing to worry, even if I am currently typing that in an hospital,

just the bad consequence of sports. ;-)

No, it wouldn't. It would store a partially pre-rendered string, that is

without fill-paragraph. We run fill-paragraph at `guix search` time to

complete the rendering.

I agree we can't compromise too much on `guix pull` performance.

Maybe I'm missing something here. guix pull takes around 40 minutes on

my machine. In comparison to that, is another 20-50 seconds (roughly 1

minute) a big deal? How much time would it be acceptable to spend on

building the Xapian index?

Also, is it possible to somehow provide substitutes for the Xapian index

so that the user does not have to actually build it locally during `guix

pull` time?

I have totally not tested this, but I imagine that equivalent Xapian

queries might look something like:

guix search license:LGPL3

guix search crypto library AND (NOT ghc) AND (NOT perl) AND (NOT python)

AND (NOT ruby)

Oh, ok. I'll try this if we decide not to pre-render.

zimoun <zimon.toutoune@gmail.com> writes:

No problem, take care! :-)

Arun Isaac <arunisaac@systemreboot.net> writes:

Indeed, if you look at the notmuch-search-terms man page, you'll see

that you can select fields.

In my opinion, the recsel format is fully superseded by Xapian.

--

Pierre Neidhardt

Ludovic Courtès <ludo@gnu.org> writes:

I think I disagree with "guix search" being an uncommon operation and a

slow path.

- The slowness of `guix search' (and the awkwardness of recutils) is

maybe what makes it uncommon: users refrain from using it because it's

too impractical.

- Searches are typically refined, i.e. you run a search multiple times

by precising the terms, so in that sense I believe `guix search` is a

very common operation. Or should be.

Anyways, one of the key issues here is the inherent limitation of the

shell interface that does not allow us to directly and contextually

process the output of a command (at least not without rerunning it).

This issue can only be tackled with a GUI: there the user would be able

to interactively act with the result of the search, without having to

re-run the search.

Concretely, the GUI search would only return the package name, version

and synopses. No need for the Texinfo / recutils juggling.

Then the user would select the packages of interest to display more

details. This allows us to query the full details just-in-time.

Back to the topic: I believe that Xapian is a huge win both for the

shell and the future GUI :)

--

Pierre Neidhardt

Hello,

Pierre Neidhardt <mail@ambrevar.xyz> skribis:

(Not “and” but “on” a slow path.)

I think “slowness” and “awkwardness” are overstatements. I’m not saying

this is perfect, but to me it’s not bad. (Of course I’m biased :-), but

I’ve used other similar tools and this one looks rather good compared to

what I’ve used.)

I agree, but ‘guix search’ is a shell command, so we have to adapt to

that context.

Note that Emacs-Guix does that, although it doesn’t use the search

facility of (guix ui) with relevance metrics.

It could be, but we need to consider all the aspects of the story,

including the maintenance cost and overhead moved to ‘guix pull’. So

it’s not so much about “beliefs” at this point, but rather about

demonstrating what can be done, and I’m glad Arun is exploring that

space!

Ludo’.

Hello!

Arun Isaac <arunisaac@systemreboot.net> skribis:

Note that Texinfo rendering doesn’t use (@ (guix ui) fill-paragraph).

It has its own paragraph-filling code. We cannot use ‘fill-paragraph’

after Texinfo rendering anyway, since Texinfo knows where things can be

filled and where they cannot—e.g., @example.

On my laptop, in the best case, when all the substitutes are available

(not uncommon), it takes 2 minutes. Sometimes, when some substitutes

are missing, it takes 15 minutes.

So of course, the 20–50 seconds matter only in the best case. But they

matter primarily because that index build may not be substitutable: it’s

possibly unique to each profile (see below). That means we know we’re

often going to pay for it.

We could provide a substitute for users who use only the official 'guix

channel. However, as soon as users combine multiple channels, they’ll

have to build the index locally.

Nice.

This one is not quite equivalent I guess, but yeah. :-)

It’d be beneficial anyways.

Thank you!

Ludo’.

Hi,

On Sat, 7 Mar 2020 at 14:31, Arun Isaac <arunisaac@systemreboot.net> wrote:

IMHO, it is interesting to compare the list of results and the order

of the both query; as i did with Emacs.

Speed is one thing, the initial motivation. But accuracy is maybe more

important.

I agree that 'fold-packages' could become soon a bottleneck.

IMHO, 'mset-fold' should be a drop-in replacement of 'fold-package' in

the search function.

I agree too that Xapian should improve the user experience when searching.

I disagree.

What I proposed some time ago was to have different flavour of the

ouput of search; as e.g., 'git log --pretty=oneline' etc..

For example by default, it should be what you suggest. Then "guix

search --format=full" should output the current. And we could imagine

mimick the Git log strategy: "guix search --format="%name

%version\n%license" etc.

WDYT?

I understand. Let consider that for the next round.

Ok.

I understand.

And we should test that on different machines and states.

This is an issue.

IMHO, it is because of the BM25 score. It is too rough and some weight

should be applied. But that another story.

The fix is:

a- provide a scoring function to Xapian as the doc explains

b- adapt 'fold-package' to 'mset-fold' in

'find-packages-by-description' and implement our version of BM25 then

use it in 'relevance'

Cool!

I agree.

But performance is not all. Accuracy counts more! :-)

I agree too.

We should write a benchmark. For example, using Emacs as query or more

complex we could think of.

All the best,

simon

Hi,

On Sat, 7 Mar 2020 at 21:33, Ludovic Courtès <ludo@gnu.org> wrote:

I agree with Ludo.

And IMHO, we should add "guix search --format=<options>" mimicking how

"git log" works.

By default, displays as Arun proposes. Using '--format=full" as it is

done now by default.

And we could imagine "--format=%name \t %version \n %description" etc.

Interesting. Note that speed was the initial motivation but accuracy

is another important one. As we discussed earlier when I showed an

example with TF-IDF. And Xapian implemets the state-of-art (BM25) for

scoring.

All the best,

simon

On Sun, 8 Mar 2020 at 10:02, Arun Isaac <arunisaac@systemreboot.net> wrote:

Yes, magic power of inverted index. ;-)

Currently "guix pull" is rather long on my machine. I would accept a

couple of seconds more (even minutes).

So this compilation step could be done at the "guix pull" time.

Or even we could imagine something indexing in the background.

IMHO, we "just" need to propose different outputs mimicking "git log

--format". Soemthing like "guix search --format=".

What do you think?

All the best,

simon

On Sun, 8 Mar 2020 at 12:33, Ludovic Courtès <ludo@gnu.org> wrote:

We could imagine something doing the job of indexing in the

background; using the daemon or whatever.

I think these examples are good ones to benchmark the different approaches.

Because the speed is one thing, the accuracy is another one.

Let cut the "slow path" by providing a better experience when searching. ;-)

The regexp should be provided directly to "guix search" actually and

'recsel' is only a "filter" allowing to deal differently with the

fields.

Ok, at least it is clear. :-)

And computing in the background?

All the best,

simon

On Mon, 9 Mar 2020 at 08:42, Pierre Neidhardt <mail@ambrevar.xyz> wrote:

No!

Because implementing the "fields" using Xapian is not done and it is

not as straightforward as it seems.

For sure, Xapian could do a lot of thing. But we should move one step

after one step.

Let first focus on speed and accuracy. For example, the fact that

"guix search emacs" does not returns first the package 'emacs' using

Xapian is really an issue.

Cheers,

simon

On Mon, 9 Mar 2020 at 08:50, Pierre Neidhardt <mail@ambrevar.xyz> wrote:

I agree.

The big win is to test the strategy of the inverted index strategy and

in the same time the state-of-art of scoring (relevance).

On Mon, 9 Mar 2020 at 11:29, Ludovic Courtès <ludo@gnu.org> wrote:

I agree.

What is currently tested with Xapian is:

1- speeding up (or not) using an inverted index

2- the accuracy using the state-of-art of information retrieval (BM25)

About 1- I do not have a strong opinion; even if I find "guix search"

terribly slow as I mentioned earlier (one year ago ;-)).

About 2- as I mentioned earlier, the 'relevance' function could be

improved. Currently, the score is computed only considering the

package itself and not the other packages (the words they use, their

number etc.). BM25 is the state-of-art using what I tried to explained

some time ago when I showed for example TF-IDF. The question is so

what the best move to improve the accuracy. And the improvement

necessarily uses a global index (of terms, at least). But on the other

hand, the improvement should not pay off because it would add

complexity and burden, more than the improvement itself.

Without testing, we cannot say. Thank you Arun for pushing forward.

All the best,

simon

On Sat, 7 Mar 2020 at 14:31, Arun Isaac <arunisaac@systemreboot.net> wrote:

Why 'fake-xapian-hash' and not simply 'fake-xapian'?

On Sat, 7 Mar 2020 at 14:31, Arun Isaac <arunisaac@systemreboot.net> wrote:

[...]

If I understand correctly, the index is stored with a weight coming

from '%package-metrics', right? Well, I am not convinced it is the

correct way but I have not tried by myself yet. :-)

On 07.03.20 14:31, Arun Isaac wrote:

Could you please trigger a release (e.g. 0.0.1) for guile-xapian? This

would make it more easy for distributions like openSUSE to package it.

Jonathan Brielmaier <jonathan.brielmaier@web.de> writes:

Done! :-) See

But I must warn you that guile-xapian is terribly incomplete and

terribly unstable. The API may change at any time without notice.

True, I did not think of this.

We could build a separate Xapian database for each channel. Xapian does

support searching across multiple databases at once and will handle

merging the results together appropriately. If I understand correctly,

this means we can provide substitutes for at least the official guix

channel and let the user build the index locally for other channels. Is

that correct?

Also, could someone please build the patchset v2 on their machine and

measure the time taken by generate-package-search-index? My laptop,

particularly my HDD is slow even as far as HDDs go. So, my figure of

20-50 seconds may not be representative.

Thanks,

Arun.

Hi Arun,

On Tue, 10 Mar 2020 at 15:18, Arun Isaac <arunisaac@systemreboot.net> wrote:

To complement your words, you could also imagine index all the history

as any other channels. It needs some thoughts but it seems a path that

I would to go.

I will do when I will be fully back. :-)

All the best,

simon

Hello!

Arun Isaac <arunisaac@systemreboot.net> skribis:

Nice!

I’m afraid not, or at least not trivially.

Currently, profile hooks such as ‘%channel-profile-hooks’, receive a

complete profile—in this case, the composition of all the channels the

user chose.

So if we want to achieve what you propose, we’d need to find another way

to hook database generation.

BTW, there’s also the problem of modules added dynamically with

$GUIX_PACKAGE_PATH or ‘-L’. With the proposed scheme, it seems that

they could no longer be searched. Is that correct?

(Conversely the package cache is optional: it’s only used when it’s

considered authoritative, see (gnu packages). The API and behavior are

exactly the same whether or not the package cache is used.)

Thanks,

Ludo’.

Hmmm. Tough luck, I suppose. Do you have suggestions for anywhere else

to hook database generation?

Unfortunately, that is correct. To address this, we discussed retaining

the current search implementation along with the new xapian

implementation. But, that changes the search query behaviour and

adds a lot of complexity. I'll think of some other way out.

Thanks,

Arun

Hi Arun,

Arun Isaac <arunisaac@systemreboot.net> skribis:

For the core database (packages that come with Guix), (guix self) could

take care of it.

Yeah, I think we’d want to have roughly a single implementation.

I wonder if the relevant metrics that Xapian implements, like zimoun

mentioned, could be available directly in Scheme in a way that allows us

to compute them at run time when the pre-built cache is unavailable. Or

would that be necessarily too slow?

If so, perhaps a slightly less fancy metric could work with better

performance?

Thanks,

Ludo’.

Hi everyone,

This is v3 of my attempt to make guix search faster. In this version, I have

abandoned use of xapian. Instead I build a cache of the metadata of all

packages in a profile hook. Then, I use that cache to search and display

search results. This way, package guile modules are not loaded during guix

search.

Speedup is around 2x. Both measurements below are with a warm cache.

This patchset does not affect the search API nor does it improve the relevance

of search results. If there is interest in this approach, I'll complete this

patchset properly. But, in the long run, I do think we should aim to get

xapian or the like for guix search. WDYT?

Unfortunately, generate-package-metadata-cache takes 43 seconds to build the

cache on my relatively slow computer. Performance should be better on other

people's machines.

Meanwhile, it would still be useful if someone built patchset v2 on their

machine and reported the time it took to build the xapian index.

Apply patches and build as usual. Do a guix pull into a temporary profile.

$ ./pre-inst-env guix pull --url=$PWD --branch=the-name-of-the-branch-you-applied-patches-to -p /tmp/test

Then, run guix search from the built profile

$ /tmp/test/bin/guix search inkscape

Thanks!

Arun Isaac (3):

guix: Generate package metadata cache.

guix: Search package metadata cache.

guix: Use package metadata cache for package search.

gnu/packages.scm | 88 +++++++++++++++++++++++++-

guix/channels.scm | 34 +++++++++-

guix/packages.scm | 32 ++++++++++

guix/scripts/package.scm | 5 +-

guix/ui.scm | 132 ++++++++++++++++++++++++++++++++++++---

5 files changed, 277 insertions(+), 14 deletions(-)

--

2.25.1

---

gnu/packages.scm | 38 ++++++++++++++++++++++++++++++++++++++

guix/packages.scm | 32 ++++++++++++++++++++++++++++++++

2 files changed, 70 insertions(+)

(generate-package-metadata-cache): New function.

(%channel-profile-hooks): Add package-metadata-cache-file.

---

gnu/packages.scm | 50 ++++++++++++++++++++++++++++++++++++++++++++++-

guix/channels.scm | 34 +++++++++++++++++++++++++++++++-

2 files changed, 82 insertions(+), 2 deletions(-)

display-package-search-results instead of find-packages-by-description and

display-search-results respectively.

(%package-metrics): Use package-metadata record field accessors.

(package-relevance): Rename argument package to package-metadata.

(display-package-search-results): New function.

---

guix/scripts/package.scm | 5 +-

guix/ui.scm | 132 ++++++++++++++++++++++++++++++++++++---

2 files changed, 125 insertions(+), 12 deletions(-)