Date: Wed, 19 Feb 2020 10:47:52 +0200
From: Timo Teras <timo.teras@iki.fi>
To: "Ariadne Conill" <ariadne@dereferenced.org>
Cc: "Carl Chave" <online@chave.us>, ~alpine/apk-tools@lists.alpinelinux.org
Subject: Re: APK Package Name Issue on armel port
Message-ID: <20200219104752.01d68e90@vostro.wlan>
In-Reply-To: <340209c209104e20dd01b7b6aa71251c@dereferenced.org>
References: <20200217123334.031047d1@vostro.wlan>
	<CAGP1gyMH+GoXnGd3YQjg4piFYpMpNiHkC7PDO7BoHTSbYsP1Ug@mail.gmail.com>
	<20200214105215.6873e402@vostro.wlan>
	<CAGP1gyOakdw54WaRNVrJFWwr4vcv410c-hUr_k4J4su6CnRBBg@mail.gmail.com>
	<62f21c96-ff43-83e4-5b7f-2e65e6d72729@adelielinux.org>
	<CAGP1gyMVCGirBd8MgNUOpiUDMsbLSSdmri3qwMLS+trh0=NWng@mail.gmail.com>
	<CAGP1gyOL_CEYcT_cEeJ=+GMccDuUi5Fv-d3q=nq70Y8HxK1bxQ@mail.gmail.com>
	<20200217111200.08405b9c@vostro.wlan>
	<340209c209104e20dd01b7b6aa71251c@dereferenced.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit

On Wed, 19 Feb 2020 00:58:31 +0000
"Ariadne Conill" <ariadne@dereferenced.org> wrote:

> February 17, 2020 4:33 AM, "Timo Teras" <timo.teras@iki.fi> wrote:
> 
> > On Mon, 17 Feb 2020 11:12:00 +0200
> > Timo Teras <timo.teras@iki.fi> wrote:
> >   
> >> Reviewing the code in apk, it seems that the murmur hashing code is
> >> not properly accounting for alignment. So the symptoms do match.
> >> The hash lookup does not work (well, works randomly based on few
> >> things), but when enumerating all packages (by using the wildcard
> >> in lookups) it'll show everything.  
> > 
> > Seems this is a common complaint about original murmur3 and there's
> > been other projects affected with this too.  
> 
> I wonder if we may be better off adopting a simpler hash function
> for our hashtables, such as FNV-1?  I have had much success over
> the years using FNV hashes in various projects in a similar role
> as what apk uses murmur3 for.

It used to be DJB hash. And later switched to murmur for better speed
and hash qualities. FNV-1 seems to be slightly better quality and speed
than DJB, but below Murmur3. Though, that probably greatly depends on
input length.

See also:
https://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/

In the current code base that needs to intern large amounts of even
long strings, I'd prefer to keep Murmur3 or go even something better
like xxHash.

Though, perhaps this is becoming less important. That is, the
interning of most package data is not needed as we mmap the files in
future. If the result is that hashing is needed for short strings only,
such as the package name, it might be worth looking at simplifying
things by going to FNV-1.

Timo