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 p6SAWhp6016961 for ; Thu, 28 Jul 2011 06:32:44 -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 EAB8E1558A9 for ; Thu, 28 Jul 2011 12:32:37 +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 lxyLT9Zx4Eu3 for ; Thu, 28 Jul 2011 12:32:35 +0200 (CEST) X-KTH-Auth: kristaps [89.158.117.88] X-KTH-mail-from: kristaps@bsd.lv X-KTH-rcpt-to: tech@mdocml.bsd.lv Received: from macky.local (89-158-117-88.rev.dartybox.com [89.158.117.88]) by smtp-1.sys.kth.se (Postfix) with ESMTP id 65195154220 for ; Thu, 28 Jul 2011 12:32:33 +0200 (CEST) Message-ID: <4E313AC0.2010106@bsd.lv> Date: Thu, 28 Jul 2011 12:32:32 +0200 From: Kristaps Dzonsons User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.2.18) Gecko/20110616 Thunderbird/3.1.11 X-Mailinglist: mdocml-tech Reply-To: tech@mdocml.bsd.lv MIME-Version: 1.0 To: tech@mdocml.bsd.lv Subject: Need hash: uthash? Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Hi, mandoc is getting a `tr' implementation*, needed primarily for perlpod. This is expensive as it involves iterating over each character in each text string, then each element in an array of `tr' characters (or escape sequences). Expect it in the next few commits (now it's in polish phase). For the time being, this is implemented with the same linear search of the `ds' and `de' macro keys. This means O(mn) performance over the number of words/characters (!) and keys. In practise, when profiling the code, libroff spends a lot of time running through these lists. -mdoc gets away without even touching this code, but -man (especially perlpod) is smacked hard. In short, the `ds', `de', and now `tr' macros can really benefit from a hash table. I'm settling on using uthash** due to its license---I can directly include it in the code. Does anybody have any better suggestions or criticism? Interfacing with it is very easy and clean, and I've had some good performance benefits on heavy -man manuals (e.g., gcc, cvs, etc.). Thanks, Kristaps *Search for `.tr': http://developer.apple.com/library/mac/#documentation/Darwin/Reference/ManPages/man7/groff.7.html **http://uthash.sourceforge.net/ -- To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv