usr.bin/nbperf/nbperf.1

   1 .\"     $NetBSD: nbperf.1,v 1.6 2013/01/31 16:32:02 joerg Exp $
   2 .\"
   3 .\" Copyright (c) 2009 The NetBSD Foundation, Inc.
   4 .\" All rights reserved.
   5 .\"
   6 .\" This code is derived from software contributed to The NetBSD Foundation
   7 .\" by Joerg Sonnenberger.
   8 .\"
   9 .\" Redistribution and use in source and binary forms, with or without
  10 .\" modification, are permitted provided that the following conditions
  11 .\" are met:
  12 .\" 1. Redistributions of source code must retain the above copyright
  13 .\"    notice, this list of conditions and the following disclaimer.
  14 .\" 2. Redistributions in binary form must reproduce the above copyright
  15 .\"    notice, this list of conditions and the following disclaimer in the
  16 .\"    documentation and/or other materials provided with the distribution.
  17 .\"
  18 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  19 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  20 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21 .\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  22 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28 .\" POSSIBILITY OF SUCH DAMAGE.
  29 .\"
  30 .Dd September 25, 2012
  31 .Dt NBPERF 1
  32 .Os
  33 .Sh NAME
  34 .Nm nbperf
  35 .Nd compute a perfect hash function
  36 .Sh SYNOPSIS
  37 .Nm
  38 .Op Fl ps
  39 .Op Fl a Ar algorithm
  40 .Op Fl c Ar utilisation
  41 .Op Fl h Ar hash
  42 .Op Fl i Ar iterations
  43 .Op Fl m Ar map-file
  44 .Op Fl n Ar name
  45 .Op Fl o Ar output
  46 .Op Ar input
  47 .Sh DESCRIPTION
  48 .Nm
  49 reads a number of keys one per line from standard input or
  50 .Ar input .
  51 It computes a minimal perfect hash function and writes it to stdout or
  52 .Ar output .
  53 The default algorithm is
  54 .Qq Sy chm .
  55 .Pp
  56 The
  57 .Fl m
  58 argument instructs
  59 .Nm
  60 to write the resulting key mapping to
  61 .Ar map-file .
  62 Each line gives the result of the hash function for the corresponding input
  63 key.
  64 .Pp
  65 The parameter
  66 .Ar utilisation
  67 determines the space efficiency.
  68 .Pp
  69 Supported arguments for
  70 .Fl a :
  71 .Bl -tag -width "chm"
  72 .It Sy chm
  73 This results in an order preserving minimal perfect hash function.
  74 The
  75 .Ar utilisation
  76 must be at least 2, the default.
  77 The number of iterations needed grows if the utilisation is very near to 2.
  78 .It Sy chm3
  79 Similar to
  80 .Ar chm .
  81 The resulting hash function needs three instead of two table lookups when
  82 compared to
  83 .Ar chm .
  84 The
  85 .Ar utilisation
  86 must be at least 1.24, the default.
  87 This makes the output for
  88 .Ar chm3
  89 noticable smaller than the output for
  90 .Ar chm .
  91 .It Sy bpz
  92 This results in a non-order preserving minimal perfect hash function.
  93 Output size is approximately 2.79 bit per key for the default value of
  94 .Ar utilisation ,
  95 1.24.
  96 This is also the smallest supported value.
  97 .El
  98 .Pp
  99 Supported arguments for
 100 .Fl h :
 101 .Bl -tag -width "mi_vector_hash"
 102 .It Sy mi_vector_hash
 103 Platform-independent version of Jenkins parallel hash.
 104 See
 105 .Xr mi_vector_hash 3 .
 106 .El
 107 .Pp
 108 The number of iterations can be limited with
 109 .Fl i .
 110 .Nm
 111 outputs a function matching
 112 .Ft uint32_t
 113 .Fn hash "const void * restrict" "size_t"
 114 to stdout.
 115 The function expects the key length as second argument, for strings not
 116 including the terminating NUL.
 117 It is the responsibility of the caller to pass in only valid keys or compare
 118 the resulting index to the key.
 119 The function name can be changed using
 120 .Fl n Ar name .
 121 If the
 122 .Fl s
 123 flag is specified, it will be static.
 124 .Pp
 125 After each failing iteration, a dot is written to stderr.
 126 .Pp
 127 .Nm
 128 checks for duplicate keys on the first iteration that passed
 129 basic hash distribution tests.
 130 In that case, an error message is printed and the program terminates.
 131 .Pp
 132 If the
 133 .Fl p
 134 flag is specified, the hash function is seeded in a stable way.
 135 This may take longer than the normal random seed, but ensures
 136 that the output is the same for repeated invocations as long as
 137 the input is constant.
 138 .Sh EXIT STATUS
 139 .Ex -std
 140 .Sh SEE ALSO
 141 .Xr mi_vector_hash 3
 142 .Sh AUTHORS
 143 .An J\(:org Sonnenberger