unofficial mirror of guix-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Inverted index to accelerate guix package search
@ 2020-01-12 15:03 Arun Isaac
  2020-01-13  8:48 ` Pierre Neidhardt
  0 siblings, 1 reply; 35+ messages in thread
From: Arun Isaac @ 2020-01-12 15:03 UTC (permalink / raw)
  To: guix-devel


[-- Attachment #1.1: Type: text/plain, Size: 1910 bytes --]


Hi,

I have a proof of concept inverted index based accelerator for guix
package search. The attached proof of concept script searches for
packages whose description contains a certain query string, and achieves
at least a 10x speedup (maybe more!) over brute force search.

Example proof of concept script run below:

Building index
clock utime stime cutime cstime gctime
 9.15 11.62  0.16   0.00   0.00   5.63

Brute force search
clock utime stime cutime cstime gctime
 0.12  0.12  0.00   0.00   0.00   0.00

Inverted index search
clock utime stime cutime cstime gctime
 0.00  0.00  0.00   0.00   0.00   0.00

* Method

We iterate over all package descriptions, decompose them into trigrams
(substrings of length 3), and build an "inverted index" -- a hash table
mapping trigrams to package names. Building this index needs to be done
only once, say during 'guix pull'. When the user provides a search
string, we decompose the search string into trigrams and use the
inverted index to look up packages whose descriptions contain those
trigrams. For typical search strings, this only has an average
complexity of O(1) whereas brute force search over all package
descriptions scales as O(n).

* Extension to regexp search

The attached proof of concept script only works for exact string
search. However, I can extend this to work for arbitrary regular
expressions (see references) if there is sufficient interest to have
this in Guix.

I think performance of guix package search will become even more
important as the number of packages in Guix grows. And, even as it is,
guix package search is relatively slow. Having blazing fast package
search could do wonders for user experience and user perception of
Guix's speed! :-)

WDYT?

* References

- https://en.wikipedia.org/wiki/Inverted_index
- http://wonconsulting.com/~cho/papers/cho-regex.pdf
- https://swtch.com/~rsc/regexp/regexp4.html

Regards,
Arun


[-- Attachment #1.2: inverted-index-poc.scm --]
[-- Type: text/plain, Size: 2600 bytes --]

(use-modules (gnu packages)
             (guix packages)
             (ice-9 match)
             (ice-9 time)
             (srfi srfi-1)
             (srfi srfi-26))

;;; Implementation of sets using hash tables

(define make-set make-hash-table)
(define set-element-of? hash-ref)
(define set-add! (cut hash-set! <> <> #t))
(define set->list (cut hash-map->list (lambda (element _) element) <>))

(define (set-intersection set1 set2)
  "Return the intersection of SET1 with SET2"
  (let ((result (make-set)))
    (hash-for-each (lambda (element _)
                     (when (set-element-of? set2 element)
                       (set-add! result element)))
                   set1)
    result))

(define (trigrams str)
  "Return all trigrams in STR."
  (if (< (string-length str) 3)
      (list)
      (map (lambda (start)
             (substring str start (+ start 3)))
           (iota (- (string-length str) 2)))))

;; Inverted index
(define index (make-hash-table))

(define (build-index!)
  "Return an inverted index of all trigrams in the descriptions of all
packages."
  (fold-packages (lambda (package _)
                   (for-each (lambda (trigram)
                               (let ((set (hash-ref index trigram (make-set))))
                                 (set-add! set (package-name package))
                                 (hash-set! index trigram set)))
                             (trigrams (package-description package))))
                 #f)
  index)

(define (brute-force-retrieve query)
  "Return names of all packages whose descriptions contain the string QUERY.
Search brute force by folding over all packages."
  (fold-packages (lambda (package result)
                   (if (string-contains (package-description package) query)
                       (cons (package-name package) result)
                       result))
                 (list)))

(define (inverted-index-retrieve query)
  "Return names of all packages whose descriptions contain the string QUERY.
Search using the pre-built inverted index."
  (match (trigrams query)
    ((first-trigram . remaining-trigrams)
     (set->list
      (fold (lambda (trigram result)
              (set-intersection result (hash-ref index trigram)))
            (hash-ref index first-trigram)
            remaining-trigrams)))
    (() (brute-force-retrieve query))))

(display "Building index")
(newline)
(time (build-index!))
(newline)

(display "Brute force search")
(newline)
(time (brute-force-retrieve "game"))
(newline)

(display "Inverted index search")
(newline)
(time (inverted-index-retrieve "game"))
(newline)

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

^ permalink raw reply	[flat|nested] 35+ messages in thread

end of thread, other threads:[~2020-01-23 20:49 UTC | newest]

Thread overview: 35+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2020-01-12 15:03 Inverted index to accelerate guix package search Arun Isaac
2020-01-13  8:48 ` Pierre Neidhardt
2020-01-13 15:08   ` Arun Isaac
2020-01-13 17:54     ` zimoun
2020-01-14  3:53       ` Bengt Richter
2020-01-14 14:21       ` Pierre Neidhardt
2020-01-14 15:27         ` Giovanni Biscuolo
2020-01-14 20:55           ` zimoun
2020-01-14 21:41             ` Pierre Neidhardt
2020-01-14 21:59               ` zimoun
2020-01-15  9:12                 ` Pierre Neidhardt
2020-01-15 14:25                   ` zimoun
2020-01-15 11:53             ` Giovanni Biscuolo
2020-01-15 14:49               ` zimoun
2020-01-16 19:06         ` Arun Isaac
2020-01-16 20:08           ` zimoun
2020-01-17 17:13           ` Pierre Neidhardt
2020-01-17 19:11             ` Pierre Neidhardt
2020-01-18 20:31               ` Arun Isaac
2020-01-15  5:44       ` Arun Isaac
2020-01-15  9:06         ` Pierre Neidhardt
2020-01-15 12:00           ` zimoun
2020-01-15 13:41             ` Pierre Neidhardt
2020-01-15 11:54         ` zimoun
2020-01-15 21:03         ` Ricardo Wurmus
2020-01-15 21:19           ` zimoun
2020-01-16 14:44           ` Ludovic Courtès
2020-01-16 15:04             ` zimoun
2020-01-16 19:11               ` Arun Isaac
2020-01-16 19:53                 ` zimoun
2020-01-17 19:29                   ` Arun Isaac
2020-01-20 19:14                     ` zimoun
2020-01-20 20:42                       ` Arun Isaac
2020-01-21 10:46                     ` Ludovic Courtès
2020-01-23 20:49                       ` Arun Isaac

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/guix.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).