| History log of /src/usr.bin/nbperf |
| Revision | Date | Author | Comments |
| 1.2 | 18-Sep-2025 |
mrg | introduce a couple of new turn-off-gcc-warning variables and use them.
GCC 14 has a new annoying calloc() checker that we turn off in a bunch
of places, and there are a few more dangling-pointer issuse that come up,
but seem bogus.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.6 | 28-Jan-2021 |
joerg | Fix sanity check to match the fixed off-by-one logic in the sizing
logic.
|
| 1.5 | 07-Jan-2021 |
joerg | 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
|
| 1.4 | 21-Oct-2011 |
joerg | Add support for build as part of the toolchain. Add option for
deterministic output (-p), which replaces the random seed with a
incremental counter.
|
| 1.3 | 03-Mar-2010 |
joerg | Add a check for duplicate keys. The check is run once and quadratic in
the hash collision chain length, which is expected to be fairly low.
|
| 1.2 | 22-Aug-2009 |
joerg | GCC's propolice complains about dynamic stack arrays to bite the bullet
and introduce a compile constant that limits the number of hash results.
Verify that the choosen hash function is not beyond that limit and just
the upper limit as static size in the graph tree functions.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.2 | 07-Jan-2021 |
joerg | 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
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.6 | 31-Jul-2023 |
andvar | fix RCSID.
|
| 1.5 | 07-Jan-2021 |
joerg | 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
|
| 1.4 | 21-Oct-2011 |
joerg | Add support for build as part of the toolchain. Add option for
deterministic output (-p), which replaces the random seed with a
incremental counter.
|
| 1.3 | 03-Mar-2010 |
joerg | Add a check for duplicate keys. The check is run once and quadratic in
the hash collision chain length, which is expected to be fairly low.
|
| 1.2 | 22-Aug-2009 |
joerg | GCC's propolice complains about dynamic stack arrays to bite the bullet
and introduce a compile constant that limits the number of hash results.
Verify that the choosen hash function is not beyond that limit and just
the upper limit as static size in the graph tree functions.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.2 | 07-Jan-2021 |
joerg | 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
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.12 | 31-Jul-2023 |
andvar | s/proceeedings/proceedings/ in comment.
|
| 1.11 | 26-Jan-2021 |
joerg | Fix potential off-by-one error when using hash fudging. It needs to
round up to 2/4 and not one less to guarantee that the adjusted hash
fits into array.
|
| 1.10 | 07-Jan-2021 |
joerg | 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
|
| 1.9 | 30-Apr-2014 |
joerg | Most CPUs implement shifts modulo the width, but ARM doesn't. Don't
depend on this UB.
|
| 1.8 | 01-Mar-2013 |
joerg | branches: 1.8.6;
Retire OSI network stack. OK core@
|
| 1.7 | 31-Jan-2013 |
joerg | bdz -> bpz to match the initials of the authors.
|
| 1.6 | 23-Nov-2012 |
joerg | Adding missing new lines in output.
|
| 1.5 | 25-Sep-2012 |
joerg | Simplify the BDZ compression function, making it smaller at the same
time. Fixes a bug where non-minimal hash functions could be created.
Add regression tests for BDZ, including the map output functionality.
|
| 1.4 | 21-Oct-2011 |
joerg | branches: 1.4.2; 1.4.4; 1.4.8;
Add support for build as part of the toolchain. Add option for
deterministic output (-p), which replaces the random seed with a
incremental counter.
|
| 1.3 | 01-Mar-2010 |
joerg | Fix a comment.
|
| 1.2 | 17-Aug-2009 |
joerg | GCC doesn't trace switch (foo & 7) completely, so add a default: abort()
to avoid warnings about unused variables.
Consistently use \t for the output function.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.4.8.4 | 20-Aug-2014 |
tls | Rebase to HEAD as of a few days ago.
|
| 1.4.8.3 | 23-Jun-2013 |
tls | resync from head
|
| 1.4.8.2 | 25-Feb-2013 |
tls | resync with head
|
| 1.4.8.1 | 20-Nov-2012 |
tls | Resync to 2012-11-19 00:00:00 UTC
|
| 1.4.4.3 | 21-May-2014 |
bouyer | Pull up following revision(s) (requested by joerg in ticket #1059):
usr.bin/nbperf/nbperf-bdz.c: revision 1.9 via patch
Most CPUs implement shifts modulo the width, but ARM doesn't. Don't
depend on this UB.
|
| 1.4.4.2 | 14-Feb-2013 |
jdc | Pull up revisions:
src/usr.bin/nbperf/nbperf-bdz.c revision 1.7
src/usr.bin/nbperf/nbperf.1 revision 1.6
src/usr.bin/nbperf/nbperf.c revision 1.5
src/usr.bin/nbperf/nbperf.h revision 1.4
(requested by joerg in ticket #819).
bdz -> bpz to match the initials of the authors.
|
| 1.4.4.1 | 17-Oct-2012 |
riz | Pull up following revision(s) (requested by joerg in ticket #574):
tests/usr.bin/nbperf/hash_driver.c: revision 1.2
tests/usr.bin/nbperf/h_nbperf.sh: revision 1.2
tests/usr.bin/nbperf/t_nbperf.sh: revision 1.2
usr.bin/nbperf/nbperf.1: revision 1.5
usr.bin/nbperf/nbperf-bdz.c: revision 1.5
Simplify the BDZ compression function, making it smaller at the same
time. Fixes a bug where non-minimal hash functions could be created.
Add regression tests for BDZ, including the map output functionality.
|
| 1.4.2.3 | 22-May-2014 |
yamt | sync with head.
for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.
this commit was splitted into small chunks to avoid
a limitation of cvs. ("Protocol error: too many arguments")
|
| 1.4.2.2 | 16-Jan-2013 |
yamt | sync with (a bit old) head
|
| 1.4.2.1 | 30-Oct-2012 |
yamt | sync with head
|
| 1.8.6.1 | 10-Aug-2014 |
tls | Rebase.
|
| 1.5 | 26-Jan-2021 |
joerg | Fix potential off-by-one error when using hash fudging. It needs to
round up to 2/4 and not one less to guarantee that the adjusted hash
fits into array.
|
| 1.4 | 07-Jan-2021 |
joerg | 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
|
| 1.3 | 21-Oct-2011 |
joerg | Add support for build as part of the toolchain. Add option for
deterministic output (-p), which replaces the random seed with a
incremental counter.
|
| 1.2 | 24-Aug-2009 |
joerg | Use a more compact presentation for g if the size is small enough.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.2 | 07-Jan-2021 |
joerg | 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
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.8 | 07-Jan-2021 |
joerg | 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
|
| 1.7 | 20-Jun-2017 |
abhinav | Fix typo
|
| 1.6 | 31-Jan-2013 |
joerg | bdz -> bpz to match the initials of the authors.
|
| 1.5 | 25-Sep-2012 |
joerg | Simplify the BDZ compression function, making it smaller at the same
time. Fixes a bug where non-minimal hash functions could be created.
Add regression tests for BDZ, including the map output functionality.
|
| 1.4 | 31-May-2012 |
joerg | branches: 1.4.2;
The output function is only order preserving for chm and chm3, so
correct that part of the documentation and also mention what the default
algorithm is.
|
| 1.3 | 21-Oct-2011 |
joerg | branches: 1.3.2; 1.3.4;
Add support for build as part of the toolchain. Add option for
deterministic output (-p), which replaces the random seed with a
incremental counter.
|
| 1.2 | 03-Mar-2010 |
joerg | Add a check for duplicate keys. The check is run once and quadratic in
the hash collision chain length, which is expected to be fairly low.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.3.4.3 | 14-Feb-2013 |
jdc | Pull up revisions:
src/usr.bin/nbperf/nbperf-bdz.c revision 1.7
src/usr.bin/nbperf/nbperf.1 revision 1.6
src/usr.bin/nbperf/nbperf.c revision 1.5
src/usr.bin/nbperf/nbperf.h revision 1.4
(requested by joerg in ticket #819).
bdz -> bpz to match the initials of the authors.
|
| 1.3.4.2 | 17-Oct-2012 |
riz | Pull up following revision(s) (requested by joerg in ticket #574):
tests/usr.bin/nbperf/hash_driver.c: revision 1.2
tests/usr.bin/nbperf/h_nbperf.sh: revision 1.2
tests/usr.bin/nbperf/t_nbperf.sh: revision 1.2
usr.bin/nbperf/nbperf.1: revision 1.5
usr.bin/nbperf/nbperf-bdz.c: revision 1.5
Simplify the BDZ compression function, making it smaller at the same
time. Fixes a bug where non-minimal hash functions could be created.
Add regression tests for BDZ, including the map output functionality.
|
| 1.3.4.1 | 11-Jun-2012 |
riz | Pull up following revision(s) (requested by joerg in ticket #295):
usr.bin/nbperf/nbperf.1: revision 1.4
The output function is only order preserving for chm and chm3, so
correct that part of the documentation and also mention what the default
algorithm is.
|
| 1.3.2.2 | 22-May-2014 |
yamt | sync with head.
for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.
this commit was splitted into small chunks to avoid
a limitation of cvs. ("Protocol error: too many arguments")
|
| 1.3.2.1 | 30-Oct-2012 |
yamt | sync with head
|
| 1.4.2.2 | 25-Feb-2013 |
tls | resync with head
|
| 1.4.2.1 | 20-Nov-2012 |
tls | Resync to 2012-11-19 00:00:00 UTC
|
| 1.9 | 22-Sep-2024 |
christos | Set the default to "infinity" and use ~0 so we don't need to count f's.
(Brad Harder)
|
| 1.8 | 02-Feb-2024 |
andvar | branches: 1.8.2;
fix typos, mainly s/unsupport/unsupported/ in log messages.
|
| 1.7 | 12-Jan-2021 |
joerg | Don't use arc4random for the tools build on NetBSD either.
compat_defs.h explicitly forces _POSIX_SOURCE and this hides the
prototype in stdlib.h.
|
| 1.6 | 07-Jan-2021 |
joerg | 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
|
| 1.5 | 31-Jan-2013 |
joerg | branches: 1.5.32;
bdz -> bpz to match the initials of the authors.
|
| 1.4 | 21-Oct-2011 |
joerg | branches: 1.4.2; 1.4.4; 1.4.8;
Add support for build as part of the toolchain. Add option for
deterministic output (-p), which replaces the random seed with a
incremental counter.
|
| 1.3 | 03-Mar-2010 |
joerg | Add a check for duplicate keys. The check is run once and quadratic in
the hash collision chain length, which is expected to be fairly low.
|
| 1.2 | 22-Aug-2009 |
joerg | GCC's propolice complains about dynamic stack arrays to bite the bullet
and introduce a compile constant that limits the number of hash results.
Verify that the choosen hash function is not beyond that limit and just
the upper limit as static size in the graph tree functions.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.4.8.1 | 25-Feb-2013 |
tls | resync with head
|
| 1.4.4.1 | 14-Feb-2013 |
jdc | Pull up revisions:
src/usr.bin/nbperf/nbperf-bdz.c revision 1.7
src/usr.bin/nbperf/nbperf.1 revision 1.6
src/usr.bin/nbperf/nbperf.c revision 1.5
src/usr.bin/nbperf/nbperf.h revision 1.4
(requested by joerg in ticket #819).
bdz -> bpz to match the initials of the authors.
|
| 1.4.2.1 | 22-May-2014 |
yamt | sync with head.
for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.
this commit was splitted into small chunks to avoid
a limitation of cvs. ("Protocol error: too many arguments")
|
| 1.5.32.1 | 19-Oct-2025 |
martin | Pull up following revision(s) (requested by mrg in ticket #1973):
tools/compat/configure.ac: revision 1.111
tools/compat/compat_defs.h: revision 1.126
tools/compat/compat_defs.h: revision 1.127
usr.bin/nbperf/nbperf.c: revision 1.7
bin/pax/options.c: revision 1.120
tools/compat/nbtool_config.h.in: revision 1.59 (patch)
tools/compat/Makefile: revision 1.95 (patch)
tools/compat/configure.ac: revision 1.110 (patch)
tools/compat/configure (patch for regen from above)
Don't use arc4random for the tools build on NetBSD either.
compat_defs.h explicitly forces _POSIX_SOURCE and this hides the
prototype in stdlib.h.
pax: need <strings.h> for ffs()
Fixes warning as host tool on NetBSD 9.99
Add more functions needed by mandoc
add vsyslog decl check
|
| 1.8.2.1 | 02-Aug-2025 |
perseant | Sync with HEAD
|
| 1.5 | 07-Jan-2021 |
joerg | 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
|
| 1.4 | 31-Jan-2013 |
joerg | bdz -> bpz to match the initials of the authors.
|
| 1.3 | 03-Mar-2010 |
joerg | branches: 1.3.6; 1.3.8; 1.3.12;
Add a check for duplicate keys. The check is run once and quadratic in
the hash collision chain length, which is expected to be fairly low.
|
| 1.2 | 22-Aug-2009 |
joerg | GCC's propolice complains about dynamic stack arrays to bite the bullet
and introduce a compile constant that limits the number of hash results.
Verify that the choosen hash function is not beyond that limit and just
the upper limit as static size in the graph tree functions.
|
| 1.1 | 15-Aug-2009 |
joerg | Add nbperf(1), a minimal perfect hash function generator.
Implemented are the 3-graph BDZ algorithm as well as the
2-graph and 3-graph CHM algorithms. All algorithms have expected
linear run time and the smallest functions need around 2.85 bit/key.
|
| 1.3.12.1 | 25-Feb-2013 |
tls | resync with head
|
| 1.3.8.1 | 14-Feb-2013 |
jdc | Pull up revisions:
src/usr.bin/nbperf/nbperf-bdz.c revision 1.7
src/usr.bin/nbperf/nbperf.1 revision 1.6
src/usr.bin/nbperf/nbperf.c revision 1.5
src/usr.bin/nbperf/nbperf.h revision 1.4
(requested by joerg in ticket #819).
bdz -> bpz to match the initials of the authors.
|
| 1.3.6.1 | 22-May-2014 |
yamt | sync with head.
for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.
this commit was splitted into small chunks to avoid
a limitation of cvs. ("Protocol error: too many arguments")
|
