1*7c219dd6Sjoerg.\" $NetBSD: nbperf.1,v 1.8 2021/01/07 16:03:08 joerg Exp $ 203c8ba1cSjoerg.\" 303c8ba1cSjoerg.\" Copyright (c) 2009 The NetBSD Foundation, Inc. 403c8ba1cSjoerg.\" All rights reserved. 503c8ba1cSjoerg.\" 603c8ba1cSjoerg.\" This code is derived from software contributed to The NetBSD Foundation 703c8ba1cSjoerg.\" by Joerg Sonnenberger. 803c8ba1cSjoerg.\" 903c8ba1cSjoerg.\" Redistribution and use in source and binary forms, with or without 1003c8ba1cSjoerg.\" modification, are permitted provided that the following conditions 1103c8ba1cSjoerg.\" are met: 1203c8ba1cSjoerg.\" 1. Redistributions of source code must retain the above copyright 1303c8ba1cSjoerg.\" notice, this list of conditions and the following disclaimer. 1403c8ba1cSjoerg.\" 2. Redistributions in binary form must reproduce the above copyright 1503c8ba1cSjoerg.\" notice, this list of conditions and the following disclaimer in the 1603c8ba1cSjoerg.\" documentation and/or other materials provided with the distribution. 1703c8ba1cSjoerg.\" 1803c8ba1cSjoerg.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 1903c8ba1cSjoerg.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 2003c8ba1cSjoerg.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 2103c8ba1cSjoerg.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 2203c8ba1cSjoerg.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2303c8ba1cSjoerg.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2403c8ba1cSjoerg.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2503c8ba1cSjoerg.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2603c8ba1cSjoerg.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2703c8ba1cSjoerg.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2803c8ba1cSjoerg.\" POSSIBILITY OF SUCH DAMAGE. 2903c8ba1cSjoerg.\" 30*7c219dd6Sjoerg.Dd January 5, 2021 3103c8ba1cSjoerg.Dt NBPERF 1 3203c8ba1cSjoerg.Os 3303c8ba1cSjoerg.Sh NAME 3403c8ba1cSjoerg.Nm nbperf 3503c8ba1cSjoerg.Nd compute a perfect hash function 3603c8ba1cSjoerg.Sh SYNOPSIS 3703c8ba1cSjoerg.Nm 38*7c219dd6Sjoerg.Op Fl fps 3903c8ba1cSjoerg.Op Fl a Ar algorithm 4003c8ba1cSjoerg.Op Fl c Ar utilisation 4103c8ba1cSjoerg.Op Fl h Ar hash 4203c8ba1cSjoerg.Op Fl i Ar iterations 4303c8ba1cSjoerg.Op Fl m Ar map-file 4403c8ba1cSjoerg.Op Fl n Ar name 4503c8ba1cSjoerg.Op Fl o Ar output 4603c8ba1cSjoerg.Op Ar input 4703c8ba1cSjoerg.Sh DESCRIPTION 4803c8ba1cSjoerg.Nm 4903c8ba1cSjoergreads a number of keys one per line from standard input or 5003c8ba1cSjoerg.Ar input . 5184d44fb8SjoergIt computes a minimal perfect hash function and writes it to stdout or 5203c8ba1cSjoerg.Ar output . 5384d44fb8SjoergThe default algorithm is 5484d44fb8Sjoerg.Qq Sy chm . 5503c8ba1cSjoerg.Pp 5603c8ba1cSjoergThe 5703c8ba1cSjoerg.Fl m 5803c8ba1cSjoergargument instructs 5903c8ba1cSjoerg.Nm 6003c8ba1cSjoergto write the resulting key mapping to 6103c8ba1cSjoerg.Ar map-file . 6203c8ba1cSjoergEach line gives the result of the hash function for the corresponding input 6303c8ba1cSjoergkey. 6403c8ba1cSjoerg.Pp 6503c8ba1cSjoergThe parameter 6603c8ba1cSjoerg.Ar utilisation 6703c8ba1cSjoergdetermines the space efficiency. 6803c8ba1cSjoerg.Pp 6903c8ba1cSjoergSupported arguments for 7003c8ba1cSjoerg.Fl a : 7103c8ba1cSjoerg.Bl -tag -width "chm" 7203c8ba1cSjoerg.It Sy chm 7303c8ba1cSjoergThis results in an order preserving minimal perfect hash function. 7403c8ba1cSjoergThe 7503c8ba1cSjoerg.Ar utilisation 7603c8ba1cSjoergmust be at least 2, the default. 7703c8ba1cSjoergThe number of iterations needed grows if the utilisation is very near to 2. 7803c8ba1cSjoerg.It Sy chm3 7903c8ba1cSjoergSimilar to 8003c8ba1cSjoerg.Ar chm . 8103c8ba1cSjoergThe resulting hash function needs three instead of two table lookups when 8203c8ba1cSjoergcompared to 8303c8ba1cSjoerg.Ar chm . 8403c8ba1cSjoergThe 8503c8ba1cSjoerg.Ar utilisation 8603c8ba1cSjoergmust be at least 1.24, the default. 8703c8ba1cSjoergThis makes the output for 8803c8ba1cSjoerg.Ar chm3 8995487f06Sabhinavnoticeably smaller than the output for 9003c8ba1cSjoerg.Ar chm . 91a81d4ca3Sjoerg.It Sy bpz 9203c8ba1cSjoergThis results in a non-order preserving minimal perfect hash function. 934edfbdbbSjoergOutput size is approximately 2.79 bit per key for the default value of 9403c8ba1cSjoerg.Ar utilisation , 9503c8ba1cSjoerg1.24. 9603c8ba1cSjoergThis is also the smallest supported value. 9703c8ba1cSjoerg.El 9803c8ba1cSjoerg.Pp 9903c8ba1cSjoergSupported arguments for 10003c8ba1cSjoerg.Fl h : 10103c8ba1cSjoerg.Bl -tag -width "mi_vector_hash" 10203c8ba1cSjoerg.It Sy mi_vector_hash 10303c8ba1cSjoergPlatform-independent version of Jenkins parallel hash. 10403c8ba1cSjoergSee 10503c8ba1cSjoerg.Xr mi_vector_hash 3 . 10603c8ba1cSjoerg.El 10703c8ba1cSjoerg.Pp 10803c8ba1cSjoergThe number of iterations can be limited with 10903c8ba1cSjoerg.Fl i . 11003c8ba1cSjoerg.Nm 11103c8ba1cSjoergoutputs a function matching 11203c8ba1cSjoerg.Ft uint32_t 11303c8ba1cSjoerg.Fn hash "const void * restrict" "size_t" 11403c8ba1cSjoergto stdout. 11503c8ba1cSjoergThe function expects the key length as second argument, for strings not 11603c8ba1cSjoergincluding the terminating NUL. 11703c8ba1cSjoergIt is the responsibility of the caller to pass in only valid keys or compare 11803c8ba1cSjoergthe resulting index to the key. 11903c8ba1cSjoergThe function name can be changed using 12003c8ba1cSjoerg.Fl n Ar name . 12103c8ba1cSjoergIf the 12203c8ba1cSjoerg.Fl s 12303c8ba1cSjoergflag is specified, it will be static. 12403c8ba1cSjoerg.Pp 12503c8ba1cSjoergAfter each failing iteration, a dot is written to stderr. 126f9c779deSjoerg.Pp 127f9c779deSjoerg.Nm 12810769988Sjoergchecks for duplicate keys on the first iteration that passed 12910769988Sjoergbasic hash distribution tests. 130f9c779deSjoergIn that case, an error message is printed and the program terminates. 13110769988Sjoerg.Pp 13210769988SjoergIf the 13310769988Sjoerg.Fl p 13410769988Sjoergflag is specified, the hash function is seeded in a stable way. 13510769988SjoergThis may take longer than the normal random seed, but ensures 13610769988Sjoergthat the output is the same for repeated invocations as long as 13710769988Sjoergthe input is constant. 13803c8ba1cSjoerg.Sh EXIT STATUS 13903c8ba1cSjoerg.Ex -std 14003c8ba1cSjoerg.Sh SEE ALSO 14103c8ba1cSjoerg.Xr mi_vector_hash 3 14203c8ba1cSjoerg.Sh AUTHORS 14303c8ba1cSjoerg.An J\(:org Sonnenberger 144