tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: RFC: Constant Database Support



On Thu, Mar 04, 2010 at 01:25:45PM +0100, Joerg Sonnenberger wrote:
> Hi all,
> attached is an implement of a constant database based on a minimal
> perfect hash table. This is a very compact read-only database. Two
> special design constraint is that more than one key can exist for a
> value and that the key itself is not stored by the database. Most users
> already do that one way or the other in the data, so it is just
> redundant and with a proper content format not even cheaper.
> 
> A patch to modify services_mkdb for using the new format is attached as
> well to demonstrate the size difference. For this use case, the
> database size drops from 2.1MB (disk space, 4.2MB file size) to 320KB
> (disk space, 306KB file size). Creation time drops from 1.9s to 0.23s
> on AMD64.
> 
> I would like to integrate this into libc for the various purposes at
> hand.

thanks, joerg, this looks very useful. a few comments:

1. seems to me this could be used for many things besides /etc/services,
as a write-once, read-many, involatile database.

2. i'd been wondering what the perfect hash stuff in libc had been
added for, and was on the verge of asking for it to be removed, but
i see now the reasons for it - thanks!

3.  even for volatile ones, adding the entry, recalculating the
perfect hash, dropping the old table, and building a new one might be
a win.

4. this might be useful for things - and yet we have mostly a bdb
interface to everything.  as such, moving over to cdb - and there must
be a better name like ''perfectdb'' or something - would involve pain
as things were re-written to use the new interface.  i think you
should consider providing a drop-in bdb1 interface for it, and
accessing it on a DB_PERFECT style of thing.  index value can be
passed in the size field of the key DBT, and i can't see much speed
being lost for that.

5. in the whole scheme of things, access speed is the thing we need
to measure, i'd have thought? build speed is important, especially
at boot time on embedded platforms, but that's a one-off.

6. nice to see the size requirements dropping too.

thanks once again.

best,
al


Home | Main Index | Thread Index | Old Index