Re: test-tool: bloom: generate_filter for multiple string?

From: Đoàn Trần Công Danh <congdanhqx@gmail.com>
Date: Jan 13, 2021, 12:13 UTC
Message-ID: <X/7j4w22s3gEbm2R@danh.dev>
In-Reply-To: <31aec25c-07ef-b3b7-2759-494ad47bcfb1@gmail.com>

On 2021-01-13 07:06:59-0500, Derrick Stolee <stolee@gmail.com> wrote:

Show 21 quoted lines

> On 1/13/2021 6:59 AM, Đoàn Trần Công Danh wrote:
> > On 2021-01-12 14:53:32-0500, Taylor Blau <me@ttaylorr.com> wrote:
> >> On Thu, Dec 31, 2020 at 10:54:38AM +0700, Đoàn Trần Công Danh wrote:
> >>> I'm reading the code for Bloom Filter to see if arXiv:2012.00472
> >>> could be an improvement.
> >>
> >> I'm late to the party, but I'm curious to hear which part of this
> >> article you think would help out the Bloom filter implementation.
> > 
> > Uhm, no. The article doesn't help the Bloom filter implementation.
> > The article was suggesting using Bloom filter to speed-up the
> > negotiation in fetch-pack and upload-pack. Which, in my own quick
> > experience, doesn't help much. Maybe it's me not understand the
> > article idea or I have made a naive implementation. However, I'm not
> > convinced to pursued further.
> 
> I saw that idea, and was immediately skeptical. Bloom filters still
> have size linear to the size of the set. By using a Bloom filter to
> describe "these are ALL the objects I have" instead of "these are
> the TIPS I have" the size will explode to be much larger than our
> current negotiation algorithm.

Yes, I saw that problem, too.

My implementation was trying to use it from the second round, downstream will say: these are ALL the objects I have from our common objects.

The result is not much different, though.

Thanks,

-- 
Danh