From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp-1.sys.kth.se (smtp-1.sys.kth.se [130.237.32.175]) by krisdoz.my.domain (8.14.3/8.14.3) with ESMTP id p5JDOW0F016940 for ; Sun, 19 Jun 2011 09:24:33 -0400 (EDT) Received: from mailscan-1.sys.kth.se (mailscan-1.sys.kth.se [130.237.32.91]) by smtp-1.sys.kth.se (Postfix) with ESMTP id 538F71557D7 for ; Sun, 19 Jun 2011 15:24:26 +0200 (CEST) X-Virus-Scanned: by amavisd-new at kth.se Received: from smtp-1.sys.kth.se ([130.237.32.175]) by mailscan-1.sys.kth.se (mailscan-1.sys.kth.se [130.237.32.91]) (amavisd-new, port 10024) with LMTP id hJg27GMkgwfg for ; Sun, 19 Jun 2011 15:24:24 +0200 (CEST) X-KTH-Auth: kristaps [193.10.49.5] X-KTH-mail-from: kristaps@bsd.lv X-KTH-rcpt-to: tech@mdocml.bsd.lv Received: from [172.16.18.84] (unknown [193.10.49.5]) by smtp-1.sys.kth.se (Postfix) with ESMTP id D784A1549F5 for ; Sun, 19 Jun 2011 15:24:22 +0200 (CEST) Message-ID: <4DFDF886.9050306@bsd.lv> Date: Sun, 19 Jun 2011 15:24:22 +0200 From: Kristaps Dzonsons User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.16) Gecko/20110303 Icedove/3.0.11 X-Mailinglist: mdocml-tech Reply-To: tech@mdocml.bsd.lv MIME-Version: 1.0 To: tech@mdocml.bsd.lv Subject: Re: Perfect hashes. References: <4DDD69EF.3050008@bsd.lv> In-Reply-To: <4DDD69EF.3050008@bsd.lv> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit 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