Need hash: uthash?

Need hash: uthash?

[Kristaps Dzonsons]

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

Re: Need hash: uthash?

[Joerg Sonnenberger]

On Thu, Jul 28, 2011 at 12:32:32PM +0200, Kristaps Dzonsons wrote:
> 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).

Shouldn't this use a simple byte lookup table for the hot path?
Most of the tr processing applies to non-special sequences and unicode
or other \-literals are rare.

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

Re: Need hash: uthash?

[Kristaps Dzonsons]

On 28/07/2011 17:04, Joerg Sonnenberger wrote:
> On Thu, Jul 28, 2011 at 12:32:32PM +0200, Kristaps Dzonsons wrote:
>> 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).
>
> Shouldn't this use a simple byte lookup table for the hot path?
> Most of the tr processing applies to non-special sequences and unicode
> or other \-literals are rare.

Joerg,

On the contrary.  perlpod (followed by GNU) is the main offender and 
makes significant use of escape-translation.  Yes, I could special-case 
\(*W, but really would rather not.

 From OpenBSD:

gnu/gcc/gcc/doc/gcjh.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/fsf-funding.7:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gfortran.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gcj.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gij.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/jv-convert.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gfdl.7:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gcc.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/jcf-dump.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/jv-scan.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gpl.7:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/cpp.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gcov.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/grmiregistry.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/grmic.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gjnih.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/g++.1:.tr \(*W-|\(bv\*(Tr
gnu/gcc/gcc/doc/gcj-dbtool.1:.tr \(*W-|\(bv\*(Tr
gnu/egcs/gcc/cp/g++.1:.tr !"
gnu/usr.bin/binutils/binutils/doc/windres.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/ar.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/addr2line.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/nlmconv.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/size.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/readelf.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/strings.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/nm.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/ranlib.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/strip.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/objcopy.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/objdump.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/binutils/doc/dlltool.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils/gprof/gprof.1:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils-2.17/binutils/doc/windres.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/ar.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/addr2line.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/nlmconv.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/size.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/readelf.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/strings.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/nm.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/ranlib.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/strip.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/objcopy.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/objdump.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/binutils/doc/dlltool.1:.tr \(*W-
gnu/usr.bin/binutils-2.17/gprof/gprof.1:.tr \(*W-
gnu/usr.bin/binutils/binutils/doc/cxxfilt.man:.tr \(*W-|\(bv\*(Tr
gnu/usr.bin/binutils-2.17/binutils/doc/cxxfilt.man:.tr \(*W-
gnu/usr.bin/cxxfilt/cxxfilt.man:.tr \(*W-|\(bv\*(Tr

 From NetBSD:
external/gpl3/binutils/dist/binutils/doc/windres.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/ar.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/addr2line.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/nlmconv.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/windmc.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/size.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/readelf.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/strings.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/nm.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/ranlib.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/strip.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/objcopy.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/objdump.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/binutils/doc/dlltool.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/ld/ld.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/gas/doc/as.1:.tr \(*W-|\(bv\*(Tr
external/gpl3/binutils/dist/gprof/gprof.1:.tr \(*W-|\(bv\*(Tr
external/gpl2/lvm2/dist/scripts/lvm2create_initrd/lvm2create_initrd.8:.tr \(*W-|\(bv\*(Tr
crypto/external/bsd/openssl/lib/libcrypto/man/ERR_load_strings.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_genpkey.1:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/DSA_SIG_new.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_md5.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/X509_STORE_set_verify_cb_func.3:.tr 
\(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/BN_mod_mul_montgomery.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_connect.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/DSA_do_sign.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/ASN1_STRING_new.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/BN_swap.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_CTX_use_psk_identity_hint.3:.tr 
\(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/RSA_padding_add_PKCS1_type_1.3:.tr 
\(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/ERR_load_crypto_strings.3:.tr 
\(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/CMS_final.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/EVP_PKEY_encrypt.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_err.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/EVP_PKEY_CTX_ctrl.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/X509_STORE_CTX_get_error.3:.tr 
\(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_pkeyutl.1:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_CTX_new.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/EVP_PKEY_derive.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/ERR_get_error.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_clear.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_ecdsa.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_CTX_set_options.3:.tr 
\(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/BN_generate_prime.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_x509.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_errstr.1:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_pending.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/d2i_X509_REQ.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/DH_size.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/SSL_want.3:.tr \(*W-
crypto/external/bsd/openssl/lib/libcrypto/man/openssl_s_time.1:.tr \(*W-

(this goes on and on)
--
 To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv

Re: Need hash: uthash?

[Joerg Sonnenberger]

On Thu, Jul 28, 2011 at 05:12:27PM +0200, Kristaps Dzonsons wrote:
> On 28/07/2011 17:04, Joerg Sonnenberger wrote:
> >On Thu, Jul 28, 2011 at 12:32:32PM +0200, Kristaps Dzonsons wrote:
> >>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).
> >
> >Shouldn't this use a simple byte lookup table for the hot path?
> >Most of the tr processing applies to non-special sequences and unicode
> >or other \-literals are rare.
> 
> Joerg,
> 
> On the contrary.  perlpod (followed by GNU) is the main offender and
> makes significant use of escape-translation.  Yes, I could
> special-case \(*W, but really would rather not.

i think you misunderstand me. My point is that the really critical path
for .tr processing is handling non-backslashed sequences. E.g. normal
text. For that, building a byte lookup table drops the performance
penalty to a few percent at most. The rest is relative expensive anyway,
but it should be only a very small part of the input. So the O(nm) drops
down to O(normal text + m * backslash-literals).

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

Re: Need hash: uthash?

[Kristaps Dzonsons]

On 28/07/2011 17:18, Joerg Sonnenberger wrote:
> On Thu, Jul 28, 2011 at 05:12:27PM +0200, Kristaps Dzonsons wrote:
>> On 28/07/2011 17:04, Joerg Sonnenberger wrote:
>>> On Thu, Jul 28, 2011 at 12:32:32PM +0200, Kristaps Dzonsons wrote:
>>>> 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).
>>>
>>> Shouldn't this use a simple byte lookup table for the hot path?
>>> Most of the tr processing applies to non-special sequences and unicode
>>> or other \-literals are rare.
>>
>> Joerg,
>>
>> On the contrary.  perlpod (followed by GNU) is the main offender and
>> makes significant use of escape-translation.  Yes, I could
>> special-case \(*W, but really would rather not.
>
> i think you misunderstand me. My point is that the really critical path
> for .tr processing is handling non-backslashed sequences. E.g. normal
> text. For that, building a byte lookup table drops the performance
> penalty to a few percent at most. The rest is relative expensive anyway,
> but it should be only a very small part of the input. So the O(nm) drops
> down to O(normal text + m * backslash-literals).

Joerg, yes, I see what you mean---I'll put something in to that effect. 
  In fact, I can use the same interface for the character substitution 
macros.  However, the requirement of a good hashtable for the other 
elements is still very relevant.  Any suggestions beyond uthash?

Thanks,

Kristaps

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

Re: Need hash: uthash?

[Ingo Schwarze]

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

Re: Need hash: uthash?

[Joerg Sonnenberger]

On Sun, Jul 31, 2011 at 12:42:23PM +0200, Ingo Schwarze wrote:
> 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?

The db(3) interface is crap. It's easier to just write a small hash
table from scratch, especially with a good hash function.

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

Re: Need hash: uthash?

[Kristaps Dzonsons]

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