From: Stefan Sperling <stsp@stsp.name>
Subject: Re: use a bloom filter to avoid pointless pack index searches
To: gameoftrees@openbsd.org
Date: Wed, 13 Oct 2021 13:13:35 +0200

On Sun, Oct 10, 2021 at 10:15:22PM +0200, Stefan Sperling wrote:
> And as for 'got histedit -l' which started this investigation:
> 
> With got 0.60:
> $ time /usr/local/bin/got he -l >/dev/null
>     2m42.96s real     0m51.16s user     1m44.11s system
> 
> With this patch:
> $ time got he -l >/dev/null
>     0m32.94s real     0m27.31s user     0m04.82s system
> $

I have committed this patch.

And afterwards I tried using a red-black tree instead of the simple
tail queue to manage bloom filters, and that makes it even faster.
This change has already been committed as well.

The command 'got he -l' now usually completes within 2 seconds in
my test case. These changes also speed up operations like 'got blame'
when many pack files exist.