On Mon, Mar 04, 2013 at 12:22:31PM +0100, Michael Schroeder wrote:
> For 2000 packages we have about... ugh, that's actually hard
> to tell as the avg and the median differ that much. Let's
> use the average: 2000 * 130 = 260000 files.
>
> I would hash them using just a 32-bit number for each hash entry,
> the number would be a combination of the hash value and a header
> number. Thus:
>
> 260000 -> 2^19 = 524288 hash entries (49% fill size)
> hash(basename) = xxxx...xxxx yyyy....yyyy
> --13 bits-- -- 19 bits--
>
> Thus we store 13 bits of the hash value together with the header
> number (we may need a header number -> header db idx array to keep
> the header number small, but that just needs 2000 * 4 bytes).
>
> I would not store the real string on disk, in most cases we
> need to retrieve the real header anyway, our db function
> can simply fetch the header and make sure that it's not a false
> positive. Chances for that are pretty slim anyway, as we have the
> extra 13 bits in the entry.
Hmm, turns out that it works only well if we have a really good
hash function. The simple hashing I do in libsolv can't be used
as too many files map to the same hash value. I tried the
popular "MurMurHash", it seems to do a good job. Disadvantages
of the scheme are the excess header fetches and there's also no
fast way to get all the keys from the hash (needed for rpm's new
IndexIterator).
If we don't want to access excess headers, we need to put the
strings into the hash. Here's the data for my machine:
filelist entries: 238032
-> hash entries: 524288
-> hash memory used: 4 * 524288 = 2 Mbyte
unique basenames: 207686
basename stringspace needed: 3355117 bytes = 3.2 MByte
This assumes that we can somehow address the string from the
32bit hash value. I have 2099 package installed, this needs
12 bits. That leaves us with 20 bits for the string offset, which
is not enough (2^20 = 1048576). We might put the strings at
a somewhat aligned offsets, thus we would need max 3 excess bytes
for aligning, making the needed space 3355117 + 3 * 207686 =
3.8 MBytes, which is smalled than 1048576 * 4.
It's probably easier to just use 2 * 32bit for the hashing, i.e.
the needed size is 2 * 2 MByte hash + 3.2 MByte strings.
Cheers,
Michael.
--
Michael Schroeder m...@suse.de
SUSE LINUX Products GmbH, GF Jeff Hawn, HRB 16746 AG Nuernberg
main(_){while(_=~getchar())putchar(~_-1/(~(_|32)/13*2-11)*13);}
_______________________________________________
Rpm-maint mailing list
Rpm-maint@lists.rpm.org
http://lists.rpm.org/mailman/listinfo/rpm-maint
