From mboxrd@z Thu Jan 1 00:00:00 1970 From: Ricardo Wurmus Subject: Re: Inverted index to accelerate guix package search Date: Wed, 15 Jan 2020 22:03:24 +0100 Message-ID: <87sgkgxwir.fsf@elephly.net> References: <87a76r68u6.fsf@ambrevar.xyz> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Return-path: Received: from eggs.gnu.org ([2001:470:142:3::10]:49756) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1irppG-0004NQ-M7 for guix-devel@gnu.org; Wed, 15 Jan 2020 16:03:46 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1irppC-0006AI-RE for guix-devel@gnu.org; Wed, 15 Jan 2020 16:03:42 -0500 Received: from sender4-of-o51.zoho.com ([136.143.188.51]:21198) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1irppC-00068j-GE for guix-devel@gnu.org; Wed, 15 Jan 2020 16:03:38 -0500 In-reply-to: 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: Arun Isaac Cc: guix-devel@gnu.org Arun Isaac writes: > Indeed, I found the bug and fixed it. Please find attached the updated > code. Also, the inverted index hash table stores package objects instead > of package names and all comparisons are now done with eq?. This gets us > an even higher speedup of around 300x. > > Built index in 8.556596040725708 seconds > Brute force search took 0.4107058048248291 seconds > Inverted index search took 0.0012979507446289062 seconds Neat! We could build and install the index when Guix is built and installed and then use it for the search. I can=E2=80=99t think of a downside to ado= pting an index compared to what we have now. --=20 Ricardo