[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Proof of concept: kwset running 3 times smaller
From: |
Nick Cleaton |
Subject: |
Proof of concept: kwset running 3 times smaller |
Date: |
Sat, 02 Oct 2010 06:55:15 +0100 |
Hi,
I've been playing around with src/kwset.c, and I've found a way to
reduce the memory footprint when matching by a factor of 3 and to
improve locality of reference: collect and sort all of the reversed
keywords before starting on the trie build, allowing the trie layout to
be planned in advance and reducing the number of pointers required.
This gives a speedup on some benchmarks with large numbers of keywords,
for example matching 32-byte random hex keywords against random hex
input is just over twice as fast in my tests, which use keyword counts
between 100k and 1M. The setup time is also reduced by about a factor
of 2.
I've yet to find a benchmark in which the modified code is measurably
slower than the original at match time. I have found one case where it
takes about twice as long at prep time: 8M short keywords such that each
adds a single trie node, arranged in an order that gives good locality
of reference to the original trie building code but does not include any
pre-sorted runs of reversed keywords.
Proof of concept patches follow. All feedback welcome, particularly
test/benchmark results on hardware other than i386.
If some variant of this idea is judged suitable to go into gnu grep,
then I expect the first step would be to add more tests for kwset.
Nick
- Proof of concept: kwset running 3 times smaller,
Nick Cleaton <=
- [PATCH 01/15] Merge trie and tree into a single struct, Nick Cleaton, 2010/10/02
- [PATCH 02/15] Sort the keywords before building the trie, Nick Cleaton, 2010/10/02
- [PATCH 03/15] Lay out the trie more systematically, Nick Cleaton, 2010/10/02
- [PATCH 04/15] Lay out the trees more systematically, Nick Cleaton, 2010/10/02
- [PATCH 05/15] Avoid using llink and rlink during prep, Nick Cleaton, 2010/10/02
- [PATCH 06/15] Defer llink/rlink plumbing to the end of prep, Nick Cleaton, 2010/10/02
- [PATCH 07/15] Share storage between llink and fail, Nick Cleaton, 2010/10/02
- [PATCH 08/15] Avoid using trie->depth during matching, Nick Cleaton, 2010/10/02
- [PATCH 09/15] Share storage between rlink and depth, Nick Cleaton, 2010/10/02
- [PATCH 10/15] Eliminate the trie->parent field, Nick Cleaton, 2010/10/02