Module Name: src
Committed By: joerg
Date: Thu Jan 7 16:03:08 UTC 2021
Modified Files:
src/tests/usr.bin/nbperf: t_nbperf.sh
src/usr.bin/nbperf: graph2.c graph2.h graph3.c nbperf-bdz.c
nbperf-chm.c nbperf-chm3.c nbperf.1 nbperf.c nbperf.h
Removed Files:
src/usr.bin/nbperf: graph3.h
Log Message:
Optimize nbperf
- add fudge mode which gives a slightly slower hash function, but works
almost always in the first iteration by avoiding degenerate edges
- avoid keeping incidence lists around reducing the memory foot print by
30%
- split edge processing from hashing as in the non-fudge case it is a
reasonable costly part that often gets thrown away
- merge graph2 and graph3 routines now that they are mostly the same
To generate a diff of this commit:
cvs rdiff -u -r1.3 -r1.4 src/tests/usr.bin/nbperf/t_nbperf.sh
cvs rdiff -u -r1.4 -r1.5 src/usr.bin/nbperf/graph2.c \
src/usr.bin/nbperf/graph3.c src/usr.bin/nbperf/nbperf.h
cvs rdiff -u -r1.1 -r1.2 src/usr.bin/nbperf/graph2.h \
src/usr.bin/nbperf/nbperf-chm3.c
cvs rdiff -u -r1.1 -r0 src/usr.bin/nbperf/graph3.h
cvs rdiff -u -r1.9 -r1.10 src/usr.bin/nbperf/nbperf-bdz.c
cvs rdiff -u -r1.3 -r1.4 src/usr.bin/nbperf/nbperf-chm.c
cvs rdiff -u -r1.7 -r1.8 src/usr.bin/nbperf/nbperf.1
cvs rdiff -u -r1.5 -r1.6 src/usr.bin/nbperf/nbperf.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/tests/usr.bin/nbperf/t_nbperf.sh
diff -u src/tests/usr.bin/nbperf/t_nbperf.sh:1.3 src/tests/usr.bin/nbperf/t_nbperf.sh:1.4
--- src/tests/usr.bin/nbperf/t_nbperf.sh:1.3 Wed Apr 30 21:04:21 2014
+++ src/tests/usr.bin/nbperf/t_nbperf.sh Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-# $NetBSD: t_nbperf.sh,v 1.3 2014/04/30 21:04:21 joerg Exp $
+# $NetBSD: t_nbperf.sh,v 1.4 2021/01/07 16:03:08 joerg Exp $
#
# Copyright (c) 2012 The NetBSD Foundation, Inc.
# All rights reserved.
@@ -27,7 +27,7 @@
cleanup()
{
- rm -f reference.txt hash.c hash.map testprog
+ rm -f reference.txt input.txt hash.c hash.map testprog
}
atf_test_case chm
@@ -38,7 +38,7 @@ chm_head()
atf_set "require.progs" "cc"
}
chm_body()
-{
+{
for n in 4 32 128 1024 65536; do
seq 0 $(($n - 1)) > reference.txt
atf_check -o file:reference.txt \
@@ -54,6 +54,32 @@ chm_clean()
cleanup
}
+atf_test_case chm_fudged
+chm_fudged_head()
+{
+ atf_set "descr" "Checks chm algorithm with fudged hash"
+ atf_set "require.progs" "cc"
+}
+chm_fudged_body()
+{
+ seq 0 9 > reference.txt
+ seq 1 10 > input.txt
+
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf input.txt "chm -p" cat \
+ 10 $(atf_get_srcdir)/hash_driver.c
+ atf_check -s exit:1 fgrep -q '^=' hash.c
+
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf input.txt "chm -f -p" cat \
+ 10 $(atf_get_srcdir)/hash_driver.c
+ atf_check -s exit:0 fgrep -q '^=' hash.c
+}
+chm_fudged_clean()
+{
+ cleanup
+}
+
atf_test_case chm3
chm3_head()
{
@@ -78,26 +104,102 @@ chm3_clean()
cleanup
}
-atf_test_case bdz
-bdz_head()
+atf_test_case chm3_fudged
+chm3_fudged_head()
+{
+ atf_set "descr" "Checks chm3 algorithm with fudged hash"
+ atf_set "require.progs" "cc"
+}
+chm3_fudged_body()
+{
+ seq 0 9 > reference.txt
+ seq 1 10 > input.txt
+
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf input.txt "chm3 -p" cat \
+ 10 $(atf_get_srcdir)/hash_driver.c
+ atf_check -s exit:1 fgrep -q '^=' hash.c
+
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf input.txt "chm3 -f -p" cat \
+ 10 $(atf_get_srcdir)/hash_driver.c
+ atf_check -s exit:0 fgrep -q '^= (' hash.c
+ atf_check -s exit:0 fgrep -q '^= 2' hash.c
+}
+chm3_fudged_clean()
+{
+ cleanup
+}
+
+atf_test_case bpz
+bpz_head()
{
- atf_set "descr" "Checks bdz algorithm"
+ atf_set "descr" "Checks bpz algorithm"
atf_set "require.files" "/usr/share/dict/web2"
atf_set "require.progs" "cc"
}
-bdz_body()
-{
+bpz_body()
+{
for n in 4 32 128 1024 65536 131072; do
seq 0 $(($n - 1)) > reference.txt
atf_check -o file:reference.txt \
- $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 bdz "sort -n" \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 bpz "sort -n" \
$n $(atf_get_srcdir)/hash_driver.c
atf_check -o file:hash.map \
- $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 bdz cat \
+ $(atf_get_srcdir)/h_nbperf /usr/share/dict/web2 bpz cat \
$n $(atf_get_srcdir)/hash_driver.c
done
}
-bdz_clean()
+bpz_clean()
+{
+ cleanup
+}
+
+atf_test_case bpz_fudged
+bpz_fudged_head()
+{
+ atf_set "descr" "Checks bpz algorithm with fudged hash"
+ atf_set "require.progs" "cc"
+}
+bpz_fudged_body()
+{
+ seq 0 9 > reference.txt
+ seq 1 10 > input.txt
+
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf input.txt "bpz -p" "sort -n" \
+ 10 $(atf_get_srcdir)/hash_driver.c
+ atf_check -s exit:1 fgrep -q '^=' hash.c
+
+ atf_check -o file:reference.txt \
+ $(atf_get_srcdir)/h_nbperf input.txt "bpz -f -p" "sort -n" \
+ 10 $(atf_get_srcdir)/hash_driver.c
+ atf_check -s exit:0 fgrep -q '^= (' hash.c
+ atf_check -s exit:0 fgrep -q '^= 2' hash.c
+}
+bpz_fudged_clean()
+{
+ cleanup
+}
+
+atf_test_case handle_dup
+handle_dup_head()
+{
+ atf_set "descr" "Checks different algorithms deal with duplicates"
+ atf_set "require.progs" "cc"
+}
+handle_dup_body()
+{
+ seq 0 9 > reference.txt
+ echo 0 >> reference.txt
+ atf_check -s exit:1 -e match:"nbperf: Duplicate keys detected" \
+ nbperf -a chm < reference.txt
+ atf_check -s exit:1 -e match:"nbperf: Duplicate keys detected" \
+ nbperf -a chm3 < reference.txt
+ atf_check -s exit:1 -e match:"nbperf: Duplicate keys detected" \
+ nbperf -a bpz < reference.txt
+}
+handle_dup_clean()
{
cleanup
}
@@ -105,6 +207,10 @@ bdz_clean()
atf_init_test_cases()
{
atf_add_test_case chm
+ atf_add_test_case chm_fudged
atf_add_test_case chm3
- atf_add_test_case bdz
+ atf_add_test_case chm3_fudged
+ atf_add_test_case bpz
+ atf_add_test_case bpz_fudged
+ atf_add_test_case handle_dup
}
Index: src/usr.bin/nbperf/graph2.c
diff -u src/usr.bin/nbperf/graph2.c:1.4 src/usr.bin/nbperf/graph2.c:1.5
--- src/usr.bin/nbperf/graph2.c:1.4 Fri Oct 21 23:47:11 2011
+++ src/usr.bin/nbperf/graph2.c Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: graph2.c,v 1.4 2011/10/21 23:47:11 joerg Exp $ */
+/* $NetBSD: graph2.c,v 1.5 2021/01/07 16:03:08 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -36,7 +36,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: graph2.c,v 1.4 2011/10/21 23:47:11 joerg Exp $");
+__RCSID("$NetBSD: graph2.c,v 1.5 2021/01/07 16:03:08 joerg Exp $");
#include <err.h>
#include <inttypes.h>
@@ -47,16 +47,14 @@ __RCSID("$NetBSD: graph2.c,v 1.4 2011/10
#include "nbperf.h"
#include "graph2.h"
-static const uint32_t unused = 0xffffffffU;
-
void
-graph2_setup(struct graph2 *graph, uint32_t v, uint32_t e)
+SIZED2(_setup)(struct SIZED(graph) *graph, uint32_t v, uint32_t e)
{
graph->v = v;
graph->e = e;
- graph->verts = calloc(sizeof(struct vertex2), v);
- graph->edges = calloc(sizeof(struct edge2), e);
+ graph->verts = calloc(sizeof(*graph->verts), v);
+ graph->edges = calloc(sizeof(*graph->edges), e);
graph->output_order = calloc(sizeof(uint32_t), e);
if (graph->verts == NULL || graph->edges == NULL ||
@@ -65,7 +63,7 @@ graph2_setup(struct graph2 *graph, uint3
}
void
-graph2_free(struct graph2 *graph)
+SIZED2(_free)(struct SIZED(graph) *graph)
{
free(graph->verts);
free(graph->edges);
@@ -76,136 +74,180 @@ graph2_free(struct graph2 *graph)
graph->output_order = NULL;
}
+static struct nbperf *sorting_nbperf;
+static struct SIZED(graph) *sorting_graph;
+static int sorting_found;
+
+static int sorting_cmp(const void *a_, const void *b_)
+{
+ const uint32_t *a = a_, *b = b_;
+ int i;
+ const struct SIZED(edge) *ea = &sorting_graph->edges[*a],
+ *eb = &sorting_graph->edges[*b];
+ for (i = 0; i < GRAPH_SIZE; ++i) {
+ if (ea->vertices[i] < eb->vertices[i])
+ return -1;
+ if (ea->vertices[i] > eb->vertices[i])
+ return 1;
+ }
+ if (sorting_nbperf->keylens[*a] < sorting_nbperf->keylens[*b])
+ return -1;
+ if (sorting_nbperf->keylens[*a] > sorting_nbperf->keylens[*b])
+ return 1;
+ i = memcmp(sorting_nbperf->keys[*a], sorting_nbperf->keys[*b],
+ sorting_nbperf->keylens[*a]);
+ if (i == 0)
+ sorting_found = 1;
+ return i;
+}
+
static int
-graph2_check_duplicates(struct nbperf *nbperf, struct graph2 *graph)
+SIZED2(_check_duplicates)(struct nbperf *nbperf, struct SIZED(graph) *graph)
{
- struct vertex2 *v;
- struct edge2 *e, *e2;
- uint32_t i, j;
+ size_t i;
+ uint32_t *key_index = calloc(sizeof(*key_index), graph->e);
- for (i = 0; i < graph->e; ++i) {
- e = &graph->edges[i];
- v = &graph->verts[e->left];
- j = v->l_edge;
- e2 = &graph->edges[j];
- for (;;) {
- if (i < j && e->right == e2->right &&
- nbperf->keylens[i] == nbperf->keylens[j] &&
- memcmp(nbperf->keys[i], nbperf->keys[j],
- nbperf->keylens[i]) == 0) {
- nbperf->has_duplicates = 1;
- return -1;
- }
- if (e2->l_next == unused)
- break;
- j = e2->l_next;
- e2 = &graph->edges[j];
- }
- }
+ if (key_index == NULL)
+ err(1, "malloc failed");
+ for (i = 0; i < graph->e; ++i)
+ key_index[i] = i;
+
+ sorting_nbperf = nbperf;
+ sorting_graph = graph;
+ sorting_found = 0;
+ qsort(key_index, graph->e, sizeof(*key_index), sorting_cmp);
+ if (sorting_found)
+ goto found_dups;
+ /*
+ * Any duplicate must have been found as part of the qsort,
+ * as it can't sort consecutive elements in the output without
+ * comparing them at least once.
+ */
+
+ free(key_index);
return 0;
+ found_dups:
+ nbperf->has_duplicates = 1;
+ return -1;
}
-int
-graph2_hash(struct nbperf *nbperf, struct graph2 *graph)
+static inline void
+SIZED2(_add_edge)(struct SIZED(graph) *graph, uint32_t edge)
{
- struct vertex2 *v;
- uint32_t hashes[NBPERF_MAX_HASH_SIZE];
+ struct SIZED(edge) *e = graph->edges + edge;
+ struct SIZED(vertex) *v;
size_t i;
- for (i = 0; i < graph->e; ++i) {
- (*nbperf->compute_hash)(nbperf,
- nbperf->keys[i], nbperf->keylens[i], hashes);
- graph->edges[i].left = hashes[0] % graph->v;
- graph->edges[i].right = hashes[1] % graph->v;
- if (graph->edges[i].left == graph->edges[i].right)
- return -1;
+ for (i = 0; i < GRAPH_SIZE; ++i) {
+ v = graph->verts + e->vertices[i];
+ v->edges ^= edge;
+ ++v->degree;
}
+}
- for (i = 0; i < graph->v; ++i) {
- graph->verts[i].l_edge = unused;
- graph->verts[i].r_edge = unused;
- }
+static inline void
+SIZED2(_remove_edge)(struct SIZED(graph) *graph, uint32_t edge)
+{
+ struct SIZED(edge) *e = graph->edges + edge;
+ struct SIZED(vertex) *v;
+ size_t i;
- for (i = 0; i < graph->e; ++i) {
- v = &graph->verts[graph->edges[i].left];
- if (v->l_edge != unused)
- graph->edges[v->l_edge].l_prev = i;
- graph->edges[i].l_next = v->l_edge;
- graph->edges[i].l_prev = unused;
- v->l_edge = i;
-
- v = &graph->verts[graph->edges[i].right];
- if (v->r_edge != unused)
- graph->edges[v->r_edge].r_prev = i;
- graph->edges[i].r_next = v->r_edge;
- graph->edges[i].r_prev = unused;
- v->r_edge = i;
- }
-
- if (nbperf->first_round) {
- nbperf->first_round = 0;
- return graph2_check_duplicates(nbperf, graph);
+ for (i = 0; i < GRAPH_SIZE; ++i) {
+ v = graph->verts + e->vertices[i];
+ v->edges ^= edge;
+ --v->degree;
}
+}
- return 0;
+static inline void
+SIZED2(_remove_vertex)(struct SIZED(graph) *graph, uint32_t vertex)
+{
+ struct SIZED(vertex) *v = graph->verts + vertex;
+ uint32_t e;
+
+ if (v->degree == 1) {
+ e = v->edges;
+ graph->output_order[--graph->output_index] = e;
+ SIZED2(_remove_edge)(graph, e);
+ }
}
-static void
-graph2_remove_vertex(struct graph2 *graph, struct vertex2 *v)
+int
+SIZED2(_hash)(struct nbperf *nbperf, struct SIZED(graph) *graph)
{
- struct edge2 *e;
- struct vertex2 *v2;
+ struct SIZED(edge) *e;
+ uint32_t hashes[NBPERF_MAX_HASH_SIZE];
+ size_t i, j;
- for (;;) {
- if (v->l_edge != unused && v->r_edge != unused)
- break;
- if (v->l_edge == unused && v->r_edge == unused)
- break;
-
- if (v->l_edge != unused) {
- e = &graph->edges[v->l_edge];
- if (e->l_next != unused)
- break;
- v->l_edge = unused; /* No other elements possible! */
- v2 = &graph->verts[e->right];
- if (e->r_prev == unused)
- v2->r_edge = e->r_next;
- else
- graph->edges[e->r_prev].r_next = e->r_next;
- if (e->r_next != unused)
- graph->edges[e->r_next].r_prev = e->r_prev;
- v = v2;
- } else {
- e = &graph->edges[v->r_edge];
- if (e->r_next != unused)
- break;
- v->r_edge = unused; /* No other elements possible! */
- v2 = &graph->verts[e->left];
- if (e->l_prev == unused)
- v2->l_edge = e->l_next;
- else
- graph->edges[e->l_prev].l_next = e->l_next;
- if (e->l_next != unused)
- graph->edges[e->l_next].l_prev = e->l_prev;
- v = v2;
+#if GRAPH_SIZE == 2
+ if (nbperf->allow_hash_fudging && (graph->v & 1) != 1)
+ errx(1, "vertex count must have lowest bit set");
+#else
+ if (nbperf->allow_hash_fudging && (graph->v & 3) != 3)
+ errx(1, "vertex count must have lowest 2 bits set");
+#endif
+
+
+ memset(graph->verts, 0, sizeof(*graph->verts) * graph->v);
+ graph->hash_fudge = 0;
+
+ for (i = 0; i < graph->e; ++i) {
+ (*nbperf->compute_hash)(nbperf,
+ nbperf->keys[i], nbperf->keylens[i], hashes);
+ e = graph->edges + i;
+ for (j = 0; j < GRAPH_SIZE; ++j) {
+ e->vertices[j] = hashes[j] % graph->v;
+ if (j == 1 && e->vertices[0] == e->vertices[1]) {
+ if (!nbperf->allow_hash_fudging)
+ return -1;
+ e->vertices[1] ^= 1; /* toogle bit to differ */
+ graph->hash_fudge |= 1;
+ }
+#if GRAPH_SIZE == 3
+ if (j == 2 && (e->vertices[0] == e->vertices[2] ||
+ e->vertices[1] == e->vertices[2])) {
+ if (!nbperf->allow_hash_fudging)
+ return -1;
+ graph->hash_fudge |= 2;
+ e->vertices[2] ^= 1;
+ e->vertices[2] ^= 2 * (e->vertices[0] == e->vertices[2] ||
+ e->vertices[1] == e->vertices[2]);
+ }
+#endif
}
+ }
+
+ for (i = 0; i < graph->e; ++i)
+ SIZED2(_add_edge)(graph, i);
- graph->output_order[--graph->output_index] = e - graph->edges;
+ if (nbperf->check_duplicates) {
+ nbperf->check_duplicates = 0;
+ return SIZED2(_check_duplicates)(nbperf, graph);
}
+
+ return 0;
}
int
-graph2_output_order(struct graph2 *graph)
+SIZED2(_output_order)(struct SIZED(graph) *graph)
{
- size_t i;
+ size_t i, j;
+ struct SIZED(edge) *e2;
graph->output_index = graph->e;
for (i = 0; i < graph->v; ++i)
- graph2_remove_vertex(graph, &graph->verts[i]);
+ SIZED2(_remove_vertex)(graph, i);
- if (graph->output_index != 0)
+ for (i = graph->e; graph->output_index > 0 && i > graph->output_index;) {
+ e2 = graph->edges + graph->output_order[--i];
+ for (j = 0; j < GRAPH_SIZE; ++j)
+ SIZED2(_remove_vertex)(graph, e2->vertices[j]);
+ }
+
+ if (graph->output_index != 0) {
return -1;
+ }
return 0;
}
Index: src/usr.bin/nbperf/graph3.c
diff -u src/usr.bin/nbperf/graph3.c:1.4 src/usr.bin/nbperf/graph3.c:1.5
--- src/usr.bin/nbperf/graph3.c:1.4 Fri Oct 21 23:47:11 2011
+++ src/usr.bin/nbperf/graph3.c Thu Jan 7 16:03:08 2021
@@ -1,250 +1,4 @@
-/* $NetBSD: graph3.c,v 1.4 2011/10/21 23:47:11 joerg Exp $ */
-/*-
- * Copyright (c) 2009 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Joerg Sonnenberger.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
- * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
- * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
- * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
+/* $NetBSD*/
-#if HAVE_NBTOOL_CONFIG_H
-#include "nbtool_config.h"
-#endif
-
-#include <sys/cdefs.h>
-__RCSID("$NetBSD: graph3.c,v 1.4 2011/10/21 23:47:11 joerg Exp $");
-
-#include <err.h>
-#include <inttypes.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "nbperf.h"
-#include "graph3.h"
-
-static const uint32_t unused = 0xffffffffU;
-
-void
-graph3_setup(struct graph3 *graph, uint32_t v, uint32_t e)
-{
- graph->v = v;
- graph->e = e;
-
- graph->verts = calloc(sizeof(struct vertex3), v);
- graph->edges = calloc(sizeof(struct edge3), e);
- graph->output_order = calloc(sizeof(uint32_t), e);
-
- if (graph->verts == NULL || graph->edges == NULL ||
- graph->output_order == NULL)
- err(1, "malloc failed");
-}
-
-void
-graph3_free(struct graph3 *graph)
-{
- free(graph->verts);
- free(graph->edges);
- free(graph->output_order);
-
- graph->verts = NULL;
- graph->edges = NULL;
- graph->output_order = NULL;
-}
-
-static int
-graph3_check_duplicates(struct nbperf *nbperf, struct graph3 *graph)
-{
- struct vertex3 *v;
- struct edge3 *e, *e2;
- uint32_t i, j;
-
- for (i = 0; i < graph->e; ++i) {
- e = &graph->edges[i];
- v = &graph->verts[e->left];
- j = v->l_edge;
- e2 = &graph->edges[j];
- for (;;) {
- if (i < j && e->middle == e2->middle &&
- e->right == e2->right &&
- nbperf->keylens[i] == nbperf->keylens[j] &&
- memcmp(nbperf->keys[i], nbperf->keys[j],
- nbperf->keylens[i]) == 0) {
- nbperf->has_duplicates = 1;
- return -1;
- }
- if (e2->l_next == unused)
- break;
- j = e2->l_next;
- e2 = &graph->edges[j];
- }
- }
- return 0;
-}
-
-int
-graph3_hash(struct nbperf *nbperf, struct graph3 *graph)
-{
- struct vertex3 *v;
- uint32_t hashes[NBPERF_MAX_HASH_SIZE];
- size_t i;
-
- for (i = 0; i < graph->e; ++i) {
- (*nbperf->compute_hash)(nbperf,
- nbperf->keys[i], nbperf->keylens[i], hashes);
- graph->edges[i].left = hashes[0] % graph->v;
- graph->edges[i].middle = hashes[1] % graph->v;
- graph->edges[i].right = hashes[2] % graph->v;
- if (graph->edges[i].left == graph->edges[i].middle)
- return -1;
- if (graph->edges[i].left == graph->edges[i].right)
- return -1;
- if (graph->edges[i].middle == graph->edges[i].right)
- return -1;
- }
-
- for (i = 0; i < graph->v; ++i) {
- graph->verts[i].l_edge = unused;
- graph->verts[i].m_edge = unused;
- graph->verts[i].r_edge = unused;
- }
-
- for (i = 0; i < graph->e; ++i) {
- v = &graph->verts[graph->edges[i].left];
- if (v->l_edge != unused)
- graph->edges[v->l_edge].l_prev = i;
- graph->edges[i].l_next = v->l_edge;
- graph->edges[i].l_prev = unused;
- v->l_edge = i;
-
- v = &graph->verts[graph->edges[i].middle];
- if (v->m_edge != unused)
- graph->edges[v->m_edge].m_prev = i;
- graph->edges[i].m_next = v->m_edge;
- graph->edges[i].m_prev = unused;
- v->m_edge = i;
-
- v = &graph->verts[graph->edges[i].right];
- if (v->r_edge != unused)
- graph->edges[v->r_edge].r_prev = i;
- graph->edges[i].r_next = v->r_edge;
- graph->edges[i].r_prev = unused;
- v->r_edge = i;
- }
-
- if (nbperf->first_round) {
- nbperf->first_round = 0;
- return graph3_check_duplicates(nbperf, graph);
- }
-
- return 0;
-}
-
-static void
-graph3_remove_vertex(struct graph3 *graph, struct vertex3 *v)
-{
- struct edge3 *e;
- struct vertex3 *vl, *vm, *vr;
-
- if (v->l_edge != unused && v->m_edge != unused)
- return;
- if (v->l_edge != unused && v->r_edge != unused)
- return;
- if (v->m_edge != unused && v->r_edge != unused)
- return;
- if (v->l_edge == unused && v->m_edge == unused && v->r_edge == unused)
- return;
-
- if (v->l_edge != unused) {
- e = &graph->edges[v->l_edge];
- if (e->l_next != unused)
- return;
- } else if (v->m_edge != unused) {
- e = &graph->edges[v->m_edge];
- if (e->m_next != unused)
- return;
- } else {
- if (v->r_edge == unused)
- abort();
- e = &graph->edges[v->r_edge];
- if (e->r_next != unused)
- return;
- }
-
- graph->output_order[--graph->output_index] = e - graph->edges;
-
- vl = &graph->verts[e->left];
- vm = &graph->verts[e->middle];
- vr = &graph->verts[e->right];
-
- if (e->l_prev == unused)
- vl->l_edge = e->l_next;
- else
- graph->edges[e->l_prev].l_next = e->l_next;
- if (e->l_next != unused)
- graph->edges[e->l_next].l_prev = e->l_prev;
-
- if (e->m_prev == unused)
- vm->m_edge = e->m_next;
- else
- graph->edges[e->m_prev].m_next = e->m_next;
- if (e->m_next != unused)
- graph->edges[e->m_next].m_prev = e->m_prev;
-
- if (e->r_prev == unused)
- vr->r_edge = e->r_next;
- else
- graph->edges[e->r_prev].r_next = e->r_next;
- if (e->r_next != unused)
- graph->edges[e->r_next].r_prev = e->r_prev;
-}
-
-int
-graph3_output_order(struct graph3 *graph)
-{
- struct edge3 *e;
- size_t i;
-
- graph->output_index = graph->e;
-
- for (i = 0; i < graph->v; ++i)
- graph3_remove_vertex(graph, &graph->verts[i]);
-
- for (i = graph->e; i > 0 && i > graph->output_index;) {
- --i;
- e = &graph->edges[graph->output_order[i]];
-
- graph3_remove_vertex(graph, &graph->verts[e->left]);
- graph3_remove_vertex(graph, &graph->verts[e->middle]);
- graph3_remove_vertex(graph, &graph->verts[e->right]);
- }
-
- if (graph->output_index != 0)
- return -1;
-
- return 0;
-}
+#define GRAPH_SIZE 3
+#include "graph2.c"
Index: src/usr.bin/nbperf/nbperf.h
diff -u src/usr.bin/nbperf/nbperf.h:1.4 src/usr.bin/nbperf/nbperf.h:1.5
--- src/usr.bin/nbperf/nbperf.h:1.4 Thu Jan 31 16:32:02 2013
+++ src/usr.bin/nbperf/nbperf.h Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: nbperf.h,v 1.4 2013/01/31 16:32:02 joerg Exp $ */
+/* $NetBSD: nbperf.h,v 1.5 2021/01/07 16:03:08 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -38,10 +38,11 @@ struct nbperf {
FILE *map_output;
const char *hash_name;
int static_hash;
+ int allow_hash_fudging;
size_t n;
const void * __restrict * keys;
const size_t *keylens;
- int first_round, has_duplicates;
+ int check_duplicates, has_duplicates;
double c;
Index: src/usr.bin/nbperf/graph2.h
diff -u src/usr.bin/nbperf/graph2.h:1.1 src/usr.bin/nbperf/graph2.h:1.2
--- src/usr.bin/nbperf/graph2.h:1.1 Sat Aug 15 16:21:05 2009
+++ src/usr.bin/nbperf/graph2.h Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: graph2.h,v 1.1 2009/08/15 16:21:05 joerg Exp $ */
+/* $NetBSD: graph2.h,v 1.2 2021/01/07 16:03:08 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -32,32 +32,57 @@
*/
/*
- * Implementation of common 2-graph routines:
- * - build a 2-graph with hash-pairs as edges
- * - check a 2-graph for acyclicness and compute an output order
+ * Implementation of common 2/3-graph routines:
+ * - build a 2/3-graph with hash-pairs as edges
+ * - check a 2/3-graph for acyclicness and compute an output order
+*
+ * For each vertex in the 2/3-graph, the incidence lists need to kept.
+ * Avoid storing the full list by just XORing the indices of the still
+ * incident edges and the number of such edges as that's all the peeling
+ * computation needs. This is inspired by:
+ * Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui,
+ * Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano
+ * Vigna. https://arxiv.org/abs/1312.0526
+ *
+ * Unlike in the paper, we don't care about external storage and have
+ * the edge list at hand all the time. As such, no ordering is necessary
+ * and the vertices of the edge don't have to be copied.
+ *
+ * The core observation of the paper above is that for a degree of one,
+ * the incident edge can be obtained directly.
*/
-struct vertex2 {
- uint32_t l_edge, r_edge;
+#ifndef GRAPH_SIZE
+#define GRAPH_SIZE 2
+#endif
+
+#define SIZED__(n, i) n ## i
+#define SIZED_(n, i) SIZED__(n, i)
+#define SIZED(n) SIZED_(n, GRAPH_SIZE)
+#define SIZED2__(n, i, m) n ## i ## m
+#define SIZED2_(n, i, m) SIZED2__(n, i, m)
+#define SIZED2(n) SIZED2_(graph, GRAPH_SIZE, n)
+
+struct SIZED(vertex) {
+ uint32_t degree, edges;
};
-struct edge2 {
- uint32_t left, right;
- uint32_t l_prev, l_next;
- uint32_t r_prev, r_next;
+struct SIZED(edge) {
+ uint32_t vertices[GRAPH_SIZE];
};
-struct graph2 {
- struct vertex2 *verts;
- struct edge2 *edges;
+struct SIZED(graph) {
+ struct SIZED(vertex) *verts;
+ struct SIZED(edge) *edges;
uint32_t output_index;
uint32_t *output_order;
uint8_t *visited;
uint32_t e, v;
+ int hash_fudge;
};
-void graph2_setup(struct graph2 *, uint32_t, uint32_t);
-void graph2_free(struct graph2 *);
+void SIZED2(_setup)(struct SIZED(graph) *, uint32_t, uint32_t);
+void SIZED2(_free)(struct SIZED(graph) *);
-int graph2_hash(struct nbperf *, struct graph2 *);
-int graph2_output_order(struct graph2 *graph);
+int SIZED2(_hash)(struct nbperf *, struct SIZED(graph) *);
+int SIZED2(_output_order)(struct SIZED(graph) *graph);
Index: src/usr.bin/nbperf/nbperf-chm3.c
diff -u src/usr.bin/nbperf/nbperf-chm3.c:1.1 src/usr.bin/nbperf/nbperf-chm3.c:1.2
--- src/usr.bin/nbperf/nbperf-chm3.c:1.1 Sat Aug 15 16:21:05 2009
+++ src/usr.bin/nbperf/nbperf-chm3.c Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: nbperf-chm3.c,v 1.1 2009/08/15 16:21:05 joerg Exp $ */
+/* $NetBSD: nbperf-chm3.c,v 1.2 2021/01/07 16:03:08 joerg Exp $ */
-#define BUILD_CHM3
+#define GRAPH_SIZE 3
#include "nbperf-chm.c"
Index: src/usr.bin/nbperf/nbperf-bdz.c
diff -u src/usr.bin/nbperf/nbperf-bdz.c:1.9 src/usr.bin/nbperf/nbperf-bdz.c:1.10
--- src/usr.bin/nbperf/nbperf-bdz.c:1.9 Wed Apr 30 21:04:58 2014
+++ src/usr.bin/nbperf/nbperf-bdz.c Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: nbperf-bdz.c,v 1.9 2014/04/30 21:04:58 joerg Exp $ */
+/* $NetBSD: nbperf-bdz.c,v 1.10 2021/01/07 16:03:08 joerg Exp $ */
/*-
* Copyright (c) 2009, 2012 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -36,7 +36,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: nbperf-bdz.c,v 1.9 2014/04/30 21:04:58 joerg Exp $");
+__RCSID("$NetBSD: nbperf-bdz.c,v 1.10 2021/01/07 16:03:08 joerg Exp $");
#include <err.h>
#include <inttypes.h>
@@ -66,10 +66,11 @@ __RCSID("$NetBSD: nbperf-bdz.c,v 1.9 201
* the index of the authoritive vertex.
*/
-#include "graph3.h"
+#define GRAPH_SIZE 3
+#include "graph2.h"
struct state {
- struct graph3 graph;
+ struct SIZED(graph) graph;
uint32_t *visited;
uint32_t *holes64k;
uint16_t *holes64;
@@ -80,7 +81,7 @@ struct state {
static void
assign_nodes(struct state *state)
{
- struct edge3 *e;
+ struct SIZED(edge) *e;
size_t i, j;
uint32_t t, r, holes;
@@ -90,29 +91,29 @@ assign_nodes(struct state *state)
for (i = 0; i < state->graph.e; ++i) {
j = state->graph.output_order[i];
e = &state->graph.edges[j];
- if (!state->visited[e->left]) {
+ if (!state->visited[e->vertices[0]]) {
r = 0;
- t = e->left;
- } else if (!state->visited[e->middle]) {
+ t = e->vertices[0];
+ } else if (!state->visited[e->vertices[1]]) {
r = 1;
- t = e->middle;
+ t = e->vertices[1];
} else {
- if (state->visited[e->right])
+ if (state->visited[e->vertices[2]])
abort();
r = 2;
- t = e->right;
+ t = e->vertices[2];
}
state->visited[t] = 2 + j;
- if (state->visited[e->left] == 0)
- state->visited[e->left] = 1;
- if (state->visited[e->middle] == 0)
- state->visited[e->middle] = 1;
- if (state->visited[e->right] == 0)
- state->visited[e->right] = 1;
+ if (state->visited[e->vertices[0]] == 0)
+ state->visited[e->vertices[0]] = 1;
+ if (state->visited[e->vertices[1]] == 0)
+ state->visited[e->vertices[1]] = 1;
+ if (state->visited[e->vertices[2]] == 0)
+ state->visited[e->vertices[2]] = 1;
- state->g[t] = (9 + r - state->g[e->left] - state->g[e->middle]
- - state->g[e->right]) % 3;
+ state->g[t] = (9 + r - state->g[e->vertices[0]] - state->g[e->vertices[1]]
+ - state->g[e->vertices[2]]) % 3;
}
holes = 0;
@@ -226,6 +227,16 @@ print_hash(struct nbperf *nbperf, struct
fprintf(nbperf->output, "\th[2] = h[2] %% %" PRIu32 ";\n",
state->graph.v);
+ if (state->graph.hash_fudge & 1)
+ fprintf(nbperf->output, "\th[1] ^= (h[0] == h[1]);\n");
+
+ if (state->graph.hash_fudge & 2) {
+ fprintf(nbperf->output,
+ "\th[2] ^= (h[0] == h[2] || h[1] == h[2]);\n");
+ fprintf(nbperf->output,
+ "\th[2] ^= 2 * (h[0] == h[2] || h[1] == h[2]);\n");
+ }
+
fprintf(nbperf->output,
"\tidx = 9 + ((g1[h[0] >> 6] >> (h[0] & 63)) &1)\n"
"\t + ((g1[h[1] >> 6] >> (h[1] & 63)) & 1)\n"
@@ -273,6 +284,8 @@ bpz_compute(struct nbperf *nbperf)
++v;
if (v < 10)
v = 10;
+ if (nbperf->allow_hash_fudging)
+ v |= 3;
graph3_setup(&state.graph, v, e);
@@ -287,9 +300,9 @@ bpz_compute(struct nbperf *nbperf)
state.result_map == NULL)
err(1, "malloc failed");
- if (graph3_hash(nbperf, &state.graph))
+ if (SIZED2(_hash)(nbperf, &state.graph))
goto failed;
- if (graph3_output_order(&state.graph))
+ if (SIZED2(_output_order)(&state.graph))
goto failed;
assign_nodes(&state);
print_hash(nbperf, &state);
@@ -297,7 +310,7 @@ bpz_compute(struct nbperf *nbperf)
retval = 0;
failed:
- graph3_free(&state.graph);
+ SIZED2(_free)(&state.graph);
free(state.visited);
free(state.g);
free(state.holes64k);
Index: src/usr.bin/nbperf/nbperf-chm.c
diff -u src/usr.bin/nbperf/nbperf-chm.c:1.3 src/usr.bin/nbperf/nbperf-chm.c:1.4
--- src/usr.bin/nbperf/nbperf-chm.c:1.3 Fri Oct 21 23:47:11 2011
+++ src/usr.bin/nbperf/nbperf-chm.c Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: nbperf-chm.c,v 1.3 2011/10/21 23:47:11 joerg Exp $ */
+/* $NetBSD: nbperf-chm.c,v 1.4 2021/01/07 16:03:08 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -35,7 +35,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: nbperf-chm.c,v 1.3 2011/10/21 23:47:11 joerg Exp $");
+__RCSID("$NetBSD: nbperf-chm.c,v 1.4 2021/01/07 16:03:08 joerg Exp $");
#include <err.h>
#include <inttypes.h>
@@ -45,11 +45,7 @@ __RCSID("$NetBSD: nbperf-chm.c,v 1.3 201
#include "nbperf.h"
-#ifdef BUILD_CHM3
-#include "graph3.h"
-#else
#include "graph2.h"
-#endif
/*
* A full description of the algorithm can be found in:
@@ -78,60 +74,74 @@ __RCSID("$NetBSD: nbperf-chm.c,v 1.3 201
*/
struct state {
-#ifdef BUILD_CHM3
- struct graph3 graph;
-#else
- struct graph2 graph;
-#endif
+ struct SIZED(graph) graph;
uint32_t *g;
uint8_t *visited;
};
+#if GRAPH_SIZE == 3
static void
assign_nodes(struct state *state)
{
-#ifdef BUILD_CHM3
- struct edge3 *e;
-#else
- struct edge2 *e;
-#endif
+ struct SIZED(edge) *e;
size_t i;
- uint32_t e_idx;
+ uint32_t e_idx, v0, v1, v2, g;
for (i = 0; i < state->graph.e; ++i) {
e_idx = state->graph.output_order[i];
e = &state->graph.edges[e_idx];
-
-#ifdef BUILD_CHM3
- if (!state->visited[e->left]) {
- state->g[e->left] = (2 * state->graph.e + e_idx
- - state->g[e->middle] - state->g[e->right])
- % state->graph.e;
- } else if (!state->visited[e->middle]) {
- state->g[e->middle] = (2 * state->graph.e + e_idx
- - state->g[e->left] - state->g[e->right])
- % state->graph.e;
+ if (!state->visited[e->vertices[0]]) {
+ v0 = e->vertices[0];
+ v1 = e->vertices[1];
+ v2 = e->vertices[2];
+ } else if (!state->visited[e->vertices[1]]) {
+ v0 = e->vertices[1];
+ v1 = e->vertices[0];
+ v2 = e->vertices[2];
} else {
- state->g[e->right] = (2 * state->graph.e + e_idx
- - state->g[e->left] - state->g[e->middle])
- % state->graph.e;
+ v0 = e->vertices[2];
+ v1 = e->vertices[0];
+ v2 = e->vertices[1];
+ }
+ g = e_idx - state->g[v1] - state->g[v2];
+ if (g >= state->graph.e) {
+ g += state->graph.e;
+ if (g >= state->graph.e)
+ g += state->graph.e;
}
- state->visited[e->left] = 1;
- state->visited[e->middle] = 1;
- state->visited[e->right] = 1;
+ state->g[v0] = g;
+ state->visited[v0] = 1;
+ state->visited[v1] = 1;
+ state->visited[v2] = 1;
+ }
+}
#else
- if (!state->visited[e->left]) {
- state->g[e->left] = (state->graph.e + e_idx
- - state->g[e->right]) % state->graph.e;
+static void
+assign_nodes(struct state *state)
+{
+ struct SIZED(edge) *e;
+ size_t i;
+ uint32_t e_idx, v0, v1, g;
+
+ for (i = 0; i < state->graph.e; ++i) {
+ e_idx = state->graph.output_order[i];
+ e = &state->graph.edges[e_idx];
+ if (!state->visited[e->vertices[0]]) {
+ v0 = e->vertices[0];
+ v1 = e->vertices[1];
} else {
- state->g[e->right] = (state->graph.e + e_idx
- - state->g[e->left]) % state->graph.e;
+ v0 = e->vertices[1];
+ v1 = e->vertices[0];
}
- state->visited[e->left] = 1;
- state->visited[e->right] = 1;
-#endif
+ g = e_idx - state->g[v1];
+ if (g >= state->graph.e)
+ g += state->graph.e;
+ state->g[v0] = g;
+ state->visited[v0] = 1;
+ state->visited[v1] = 1;
}
}
+#endif
static void
print_hash(struct nbperf *nbperf, struct state *state)
@@ -175,15 +185,34 @@ print_hash(struct nbperf *nbperf, struct
fprintf(nbperf->output, "\t};\n");
fprintf(nbperf->output, "\tuint32_t h[%zu];\n\n", nbperf->hash_size);
(*nbperf->print_hash)(nbperf, "\t", "key", "keylen", "h");
-#ifdef BUILD_CHM3
- fprintf(nbperf->output, "\treturn (g[h[0] %% %" PRIu32 "] + "
- "g[h[1] %% %" PRIu32 "] + "
- "g[h[2] %% %" PRIu32"]) %% %" PRIu32 ";\n",
- state->graph.v, state->graph.v, state->graph.v, state->graph.e);
+
+ fprintf(nbperf->output, "\n\th[0] = h[0] %% %" PRIu32 ";\n",
+ state->graph.v);
+ fprintf(nbperf->output, "\th[1] = h[1] %% %" PRIu32 ";\n",
+ state->graph.v);
+#if GRAPH_SIZE == 3
+ fprintf(nbperf->output, "\th[2] = h[2] %% %" PRIu32 ";\n",
+ state->graph.v);
+#endif
+
+ if (state->graph.hash_fudge & 1)
+ fprintf(nbperf->output, "\th[1] ^= (h[0] == h[1]);\n");
+
+#if GRAPH_SIZE == 3
+ if (state->graph.hash_fudge & 2) {
+ fprintf(nbperf->output,
+ "\th[2] ^= (h[0] == h[2] || h[1] == h[2]);\n");
+ fprintf(nbperf->output,
+ "\th[2] ^= 2 * (h[0] == h[2] || h[1] == h[2]);\n");
+ }
+#endif
+
+#if GRAPH_SIZE == 3
+ fprintf(nbperf->output, "\treturn (g[h[0]] + g[h[1]] + g[h[2]]) %% "
+ "%" PRIu32 ";\n", state->graph.e);
#else
- fprintf(nbperf->output, "\treturn (g[h[0] %% %" PRIu32 "] + "
- "g[h[1] %% %" PRIu32"]) %% %" PRIu32 ";\n",
- state->graph.v, state->graph.v, state->graph.e);
+ fprintf(nbperf->output, "\treturn (g[h[0]] + g[h[1]]) %% "
+ "%" PRIu32 ";\n", state->graph.e);
#endif
fprintf(nbperf->output, "}\n");
@@ -194,7 +223,7 @@ print_hash(struct nbperf *nbperf, struct
}
int
-#ifdef BUILD_CHM3
+#if GRAPH_SIZE == 3
chm3_compute(struct nbperf *nbperf)
#else
chm_compute(struct nbperf *nbperf)
@@ -204,7 +233,7 @@ chm_compute(struct nbperf *nbperf)
int retval = -1;
uint32_t v, e;
-#ifdef BUILD_CHM3
+#if GRAPH_SIZE == 3
if (nbperf->c == 0)
nbperf-> c = 1.24;
@@ -227,14 +256,18 @@ chm_compute(struct nbperf *nbperf)
(*nbperf->seed_hash)(nbperf);
e = nbperf->n;
v = nbperf->c * nbperf->n;
-#ifdef BUILD_CHM3
+#if GRAPH_SIZE == 3
if (v == 1.24 * nbperf->n)
++v;
if (v < 10)
v = 10;
+ if (nbperf->allow_hash_fudging)
+ v |= 3;
#else
if (v == 2 * nbperf->n)
++v;
+ if (nbperf->allow_hash_fudging)
+ v |= 1;
#endif
state.g = calloc(sizeof(uint32_t), v);
@@ -242,30 +275,18 @@ chm_compute(struct nbperf *nbperf)
if (state.g == NULL || state.visited == NULL)
err(1, "malloc failed");
-#ifdef BUILD_CHM3
- graph3_setup(&state.graph, v, e);
- if (graph3_hash(nbperf, &state.graph))
- goto failed;
- if (graph3_output_order(&state.graph))
- goto failed;
-#else
- graph2_setup(&state.graph, v, e);
- if (graph2_hash(nbperf, &state.graph))
+ SIZED2(_setup)(&state.graph, v, e);
+ if (SIZED2(_hash)(nbperf, &state.graph))
goto failed;
- if (graph2_output_order(&state.graph))
+ if (SIZED2(_output_order)(&state.graph))
goto failed;
-#endif
assign_nodes(&state);
print_hash(nbperf, &state);
retval = 0;
failed:
-#ifdef BUILD_CHM3
- graph3_free(&state.graph);
-#else
- graph2_free(&state.graph);
-#endif
+ SIZED2(_free)(&state.graph);
free(state.g);
free(state.visited);
return retval;
Index: src/usr.bin/nbperf/nbperf.1
diff -u src/usr.bin/nbperf/nbperf.1:1.7 src/usr.bin/nbperf/nbperf.1:1.8
--- src/usr.bin/nbperf/nbperf.1:1.7 Tue Jun 20 15:50:04 2017
+++ src/usr.bin/nbperf/nbperf.1 Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-.\" $NetBSD: nbperf.1,v 1.7 2017/06/20 15:50:04 abhinav Exp $
+.\" $NetBSD: nbperf.1,v 1.8 2021/01/07 16:03:08 joerg Exp $
.\"
.\" Copyright (c) 2009 The NetBSD Foundation, Inc.
.\" All rights reserved.
@@ -27,7 +27,7 @@
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
-.Dd September 25, 2012
+.Dd January 5, 2021
.Dt NBPERF 1
.Os
.Sh NAME
@@ -35,7 +35,7 @@
.Nd compute a perfect hash function
.Sh SYNOPSIS
.Nm
-.Op Fl ps
+.Op Fl fps
.Op Fl a Ar algorithm
.Op Fl c Ar utilisation
.Op Fl h Ar hash
Index: src/usr.bin/nbperf/nbperf.c
diff -u src/usr.bin/nbperf/nbperf.c:1.5 src/usr.bin/nbperf/nbperf.c:1.6
--- src/usr.bin/nbperf/nbperf.c:1.5 Thu Jan 31 16:32:02 2013
+++ src/usr.bin/nbperf/nbperf.c Thu Jan 7 16:03:08 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: nbperf.c,v 1.5 2013/01/31 16:32:02 joerg Exp $ */
+/* $NetBSD: nbperf.c,v 1.6 2021/01/07 16:03:08 joerg Exp $ */
/*-
* Copyright (c) 2009 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -36,7 +36,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: nbperf.c,v 1.5 2013/01/31 16:32:02 joerg Exp $");
+__RCSID("$NetBSD: nbperf.c,v 1.6 2021/01/07 16:03:08 joerg Exp $");
#include <sys/endian.h>
#include <err.h>
@@ -45,6 +45,7 @@ __RCSID("$NetBSD: nbperf.c,v 1.5 2013/01
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
+#include <time.h>
#include <unistd.h>
#include "nbperf.h"
@@ -115,8 +116,9 @@ main(int argc, char **argv)
.map_output = NULL,
.output = NULL,
.static_hash = 0,
- .first_round = 1,
+ .check_duplicates = 0,
.has_duplicates = 0,
+ .allow_hash_fudging = 0,
};
FILE *input;
size_t curlen = 0, curalloc = 0;
@@ -132,7 +134,7 @@ main(int argc, char **argv)
set_hash(&nbperf, "mi_vector_hash");
- while ((ch = getopt(argc, argv, "a:c:h:i:m:n:o:ps")) != -1) {
+ while ((ch = getopt(argc, argv, "a:c:fh:i:m:n:o:ps")) != -1) {
switch (ch) {
case 'a':
/* Accept bdz as alias for netbsd-6 compat. */
@@ -152,6 +154,9 @@ main(int argc, char **argv)
if (errno || eos[0] || !nbperf.c)
errx(2, "Invalid argument for -c");
break;
+ case 'f':
+ nbperf.allow_hash_fudging = 1;
+ break;
case 'h':
set_hash(&nbperf, optarg);
break;
@@ -241,10 +246,18 @@ main(int argc, char **argv)
nbperf.keylens = keylens;
looped = 0;
- while ((*build_hash)(&nbperf)) {
- if (nbperf.has_duplicates)
+ int rv;
+ for (;;) {
+ rv = (*build_hash)(&nbperf);
+ if (!rv)
+ break;
+ if (nbperf.has_duplicates) {
+ fputc('\n', stderr);
errx(1, "Duplicate keys detected");
+ }
fputc('.', stderr);
+ if (!looped)
+ nbperf.check_duplicates = 1;
looped = 1;
if (max_iterations == 0xffffffffU)
continue;
