Re: Need hash: uthash?

[Ingo Schwarze <schwarze@usta.de>]

Hi Kristaps,

Kristaps Dzonsons wrote on Thu, Jul 28, 2011 at 12:32:32PM +0200:

> mandoc is getting a `tr' implementation*, needed primarily for
> perlpod.

It's astounding how fast this happened.
I can't even keep up with reading the code right now,
however, i'm sure it's good to have it.

> This is expensive as it involves iterating over each character in
> each text string, then each element in an array of `tr' characters
[...]

Good that Joerg's suggestions mitigated this problem.

> 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?

> 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.

All the required tools for developing mandoc ought to be in
OpenBSD base.  So, *if* we settle on uthash, we should first
discuss that with the other developers, and even if people
agree, we will likely have to maintain it in tree ourselves.

The first things we will be asked is:  Why not use the existing
tools?  If i understand correctly, uthash is a dynamic hasher
(as opposed to a perfect static hasher).  What about hash(3) in
/usr/src/lib/libc/db/hash/ ?  Is that useable?

But even if we use tools from base, i think in the current
phase of development, we should only do optimizations that
require additional libraries if they really cause HUGE
performance gain in practice.  All of the places where this
might be used are still covered in dust that is hardly starting
to settle down, so simplicity and flexibility are still top
priorities, and will stay for some time.

Yours,
  Ingo
--
 To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv