From mboxrd@z Thu Jan  1 00:00:00 1970
From: =?utf-8?Q?Ludovic_Court=C3=A8s?= <ludo@gnu.org>
Subject: Re: Inverted index to accelerate guix package search
Date: Thu, 16 Jan 2020 15:44:31 +0100
Message-ID: <87a76ncvg0.fsf@gnu.org>
References: <cu7h810emy0.fsf@systemreboot.net> <87a76r68u6.fsf@ambrevar.xyz>
 <cu7a76re6nj.fsf@systemreboot.net>
 <CAJ3okZ23f4kuygoj_HS0+uKYGCad2ZV=u7DWuZ=-3vQXM_QYtQ@mail.gmail.com>
 <cu74kwxe0jv.fsf@systemreboot.net> <87sgkgxwir.fsf@elephly.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Return-path: <guix-devel-bounces+gcggd-guix-devel=m.gmane-mx.org@gnu.org>
Received: from eggs.gnu.org ([2001:470:142:3::10]:54632)
 by lists.gnu.org with esmtp (Exim 4.90_1)
 (envelope-from <ludo@gnu.org>) id 1is6OS-0001EW-7Z
 for guix-devel@gnu.org; Thu, 16 Jan 2020 09:45:09 -0500
In-Reply-To: <87sgkgxwir.fsf@elephly.net> (Ricardo Wurmus's message of "Wed,
 15 Jan 2020 22:03:24 +0100")
List-Id: "Development of GNU Guix and the GNU System distribution."
 <guix-devel.gnu.org>
List-Unsubscribe: <https://lists.gnu.org/mailman/options/guix-devel>,
 <mailto:guix-devel-request@gnu.org?subject=unsubscribe>
List-Archive: <https://lists.gnu.org/archive/html/guix-devel>
List-Post: <mailto:guix-devel@gnu.org>
List-Help: <mailto:guix-devel-request@gnu.org?subject=help>
List-Subscribe: <https://lists.gnu.org/mailman/listinfo/guix-devel>,
 <mailto:guix-devel-request@gnu.org?subject=subscribe>
Errors-To: guix-devel-bounces+gcggd-guix-devel=m.gmane-mx.org@gnu.org
Sender: "Guix-devel"
 <guix-devel-bounces+gcggd-guix-devel=m.gmane-mx.org@gnu.org>
To: Ricardo Wurmus <rekado@elephly.net>
Cc: guix-devel@gnu.org

Hello,

Ricardo Wurmus <rekado@elephly.net> skribis:

> Arun Isaac <arunisaac@systemreboot.net> 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 a=
dopting
> an index compared to what we have now.

The possible downsides are (1) =E2=80=98guix pull=E2=80=99 will take an add=
itional 8
seconds, (2) there=E2=80=99ll be some extra complexity because the current
implementation needs to be kept anyway for when the pre-built index is
not authoritative=E2=80=94i.e., when =E2=80=98GUIX_PACKAGE_PATH=E2=80=99 is=
 set or when =E2=80=98-L=E2=80=99 is
used; see =E2=80=98cache-is-authoritative?=E2=80=99 in (gnu packages).

I don=E2=80=99t find =E2=80=98guix search=E2=80=99 to be excessively slow c=
urrently (on an SSD
at least), but I agree that the speedup would be welcome!

Thanks,
Ludo=E2=80=99.