Re: Need hash: uthash?

[Kristaps Dzonsons <kristaps@bsd.lv>]

>> 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.
>
> Is that still true with Joerg's suggestion?

Ingo,

No---well, not really.  As you can see, the code switches between using 
a byte-table for lookups (regular characters) and a linear search 
(escape sequences).  Cf. roff_strdup().  Again, most mdoc manuals never 
touch this code.

The topic of hashes is important and could make a big difference, but I 
don't yet have the benchmarks to substantiate this, so I'm not pushing 
it too hard.  I'm mainly bothered by the many diverse tables and methods 
that are floating around in the codebase.

The situation is as follows.

Perfect [minimal?] hashing.

   Usage: escape table, mdoc macro table, man macro table, roff macro table.

   Pros: removes a big chunk of code/space (depending on the hash 
implementation of course) and initialisation overhead (static), some 
speed-ups in lookups.

   Cons: machine-generated code, needs Yet Another Tool.  NetBSD has one 
(nmbperf), GNU has one (gperf).

   Alternatives: use a dynamic hash and eat the overhead.  Since I 
already manually "hash" these, this is an acceptable start.

Dynamic hashing.

   Usage: `de' and `ds' symbol table, `tr' symbol table.

   Pros: cleans up interfaces, significantly speeds up some areas (the 
linear lookup).  Will speed up -man documents by quite a bit.

   Cons: needs a hash mechanism.  Some space overhead for the table vs. 
the linked list.

   Alternatives: continue being slow.

What I'm going to do is implement most of these and run benchmarks to 
see what we actually get.  I'd done this before for a small part but 
have forgotten the results, so it's time to do it again.  I'm interested 
in both the single-manual improvement and the many-manual improvement.

Thanks,

Kristaps
--
 To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv