Re: Perfect hashes.

[Kristaps Dzonsons <kristaps@bsd.lv>]

On 05/25/2011 10:43 PM, Kristaps Dzonsons wrote:
> Hi,
>
> A while ago, Joerg brought up the idea of using perfect hashes for some
> of the keywords in mandoc. I'm reviving this conversation because I'd
> like a uniform interface for the roff, mdoc, man, chars, and mdoc-args
> tables. For the time being, each of these has its own method, which is
> error-prone, ugly, and bloated.
>
> Perfect hashes make sense because the above data is fixed. Furthermore,
> they have no cost of allocation and have little overhead in terms of
> unused table-space.
>
> Enclosed is a patch that implements this just for the mdoc macro names.
> I used gperf as I don't have a new NetBSD box handy for nbperf. (It
> doesn't matter which is used---I messed around with the generated code
> as it is.)
>
> The speed-up is a bit more than 1% when repeatedly running mandoc over a
> set of manuals. When running it with a large number of manuals on the
> command-line, the results are more or less the same. Either way, the
> generated binary is slightly smaller.
>
> I'm leaning toward implementing similar steps for all existing hash
> files. Does anybody have any objections? My intent in this isn't so much
> performance as uniform interfacing, code readability, correctness, and
> bloat. All of these are covered by perfect hashes, at the cost of
> needing an external utility whenever the symbols change.
>
> (I had to remove mdoc_macronames[] because there wasn't an immediate way
> to map back... I'll figure this out later, if nobody objects to the
> notion in the first place.)
>
> Thoughts?

Anybody?  I'm going to check in nbperf/gperf-constructed hashes for 
chars.c and the others if nobody speaks up...
--
 To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv