From mboxrd@z Thu Jan 1 00:00:00 1970 From: Arun Isaac Subject: Inverted index to accelerate guix package search Date: Sun, 12 Jan 2020 20:33:51 +0530 Message-ID: Mime-Version: 1.0 Content-Type: multipart/signed; boundary="==-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" Return-path: Received: from eggs.gnu.org ([2001:470:142:3::10]:53243) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iqemm-0007u3-RI for guix-devel@gnu.org; Sun, 12 Jan 2020 10:04:19 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iqemk-0006ou-IL for guix-devel@gnu.org; Sun, 12 Jan 2020 10:04:15 -0500 Received: from mugam.systemreboot.net ([139.59.75.54]:60904) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iqemj-0006O3-8y for guix-devel@gnu.org; Sun, 12 Jan 2020 10:04:14 -0500 Received: from [192.168.2.1] (helo=steel) by systemreboot.net with esmtpsa (TLSv1.3:TLS_AES_256_GCM_SHA384:256) (Exim 4.92.3) (envelope-from ) id 1iqemd-002HAk-Ef for guix-devel@gnu.org; Sun, 12 Jan 2020 20:34:07 +0530 List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-devel-bounces+gcggd-guix-devel=m.gmane-mx.org@gnu.org Sender: "Guix-devel" To: guix-devel@gnu.org --==-=-= Content-Type: multipart/mixed; boundary="=-=-=" --=-=-= Content-Type: text/plain 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 --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=inverted-index-poc.scm (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) --=-=-=-- --==-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQEzBAEBCAAdFiEEf3MDQ/Lwnzx3v3nTLiXui2GAK7MFAl4bNVcACgkQLiXui2GA K7NWMwgAinGefcmmiwNXI8yaWoLzI1TBu1X+KOT2tGOBzJdba+tSy3KeY9d4pTJL QHhJuydEZXuhd8iklFJx+RUWRW4Ecq1hLb4bhWOHbC+2K4fRqyNgkeFEXrYup6zt EzWAwZylV8mvpLAeh+eNPQHoThSa/0q3QnAmGxzyDYro1aO6OlJwNENc1PBe+D7c pI0GWtGKdkMUGy2wofa7RxeErj7Ag41xHxOYOAoRQdfNukLz+m2s5++m40Sg0T41 gReYj9sXdB0EOz2eeJLTvKda6ufJB4HkqWdx0QpT7BQHvQ/zKgFUH6DRtASWz5/u udBqETgg0+AzmQqTewGqVq7EOyrx5Q== =SIgm -----END PGP SIGNATURE----- --==-=-=--