commit b90acb87add41527b7d76849f4f0f293b5e64bbb
parent f59f4c66c337cb9eee7ba2a3db9c664cad325270
Author: Walther Chen <walther.chen@gmail.com>
Date: Fri, 1 Nov 2024 14:28:29 -0400
Free temp inside neighbors
bioinformatics on main [$] > poop "./ba1i-before ba1i-input.txt" "./ba1i ba1i-input.txt"
Benchmark 1 (151 runs): ./ba1i-before ba1i-input.txt
measurement mean ± σ min … max outliers delta
wall_time 33.0ms ± 2.47ms 29.9ms … 40.4ms 2 ( 1%) 0%
peak_rss 19.1MB ± 53.7KB 19.0MB … 19.2MB 0 ( 0%) 0%
cpu_cycles 67.1M ± 1.77M 64.5M … 75.3M 1 ( 1%) 0%
instructions 128M ± 2.42 128M … 128M 4 ( 3%) 0%
cache_references 1.06M ± 8.00K 1.04M … 1.10M 2 ( 1%) 0%
cache_misses 337K ± 35.5K 286K … 472K 2 ( 1%) 0%
branch_misses 132K ± 1.55K 130K … 139K 6 ( 4%) 0%
Benchmark 2 (200 runs): ./ba1i ba1i-input.txt
measurement mean ± σ min … max outliers delta
wall_time 25.0ms ± 2.26ms 22.3ms … 35.7ms 1 ( 1%) ⚡- 24.2% ± 1.5%
peak_rss 7.49MB ± 49.8KB 7.42MB … 7.58MB 0 ( 0%) ⚡- 60.8% ± 0.1%
cpu_cycles 58.0M ± 3.27M 55.0M … 89.2M 8 ( 4%) ⚡- 13.6% ± 0.9%
instructions 118M ± 3.05 118M … 118M 2 ( 1%) ⚡- 8.3% ± 0.0%
cache_references 768K ± 23.8K 665K … 979K 7 ( 4%) ⚡- 27.4% ± 0.4%
cache_misses 156K ± 58.1K 93.5K … 360K 13 ( 7%) ⚡- 53.8% ± 3.1%
branch_misses 121K ± 1.49K 118K … 129K 9 ( 5%) ⚡- 8.5% ± 0.2%
Diffstat:
| M | util-frequency.c3 | | | 114 | ++++++++++++++++++++++++++++++++++++++++--------------------------------------- |
1 file changed, 58 insertions(+), 56 deletions(-)
diff --git a/util-frequency.c3 b/util-frequency.c3
@@ -256,68 +256,70 @@ fn String[] neighbors(String pattern, int d, Allocator alloc = allocator::heap()
{
if (d == 0) return {pattern};
if (pattern.len == 0) return {};
- DynamicArenaAllocator neighborhood_arena;
- DynamicArenaAllocator suffix_neighborhood_arena;
- neighborhood_arena.init(1024, allocator::temp());
- suffix_neighborhood_arena.init(1024, allocator::temp());
- List(<String>) neighborhood;
- List(<String>) suffix_neighborhood;
- neighborhood.new_init_with_array({"A", "C", "G", "T"}, &neighborhood_arena);
- suffix_neighborhood.new_init(16, &suffix_neighborhood_arena);
- for (int i = 1; i < pattern.len; i += 1) {
- // swap suffix_neighborhood and neighborhood. The previous
- // neighborhood becomes the new suffix_neighborhood to iterate
- // over. Now we need a place to collect the next neighborhood into,
- // so we reuse the memory from the old suffix_neighborhood, which is
- // no longer useful for future calculation, as its results have already
- // been moved into the old neighborhood/new suffix_neighborhood as
- // calculated during the last iteration. (otherwise we have to keep
- // allocating new memory to collect the next neighborhood into).
- //
- // The memory itself is cleared for reuse by the arena holding the
- // List (see next swap)
- List(<String>) swap_var;
- swap_var = suffix_neighborhood;
- suffix_neighborhood = neighborhood;
- neighborhood = swap_var;
+ @pool(alloc) {
+ DynamicArenaAllocator neighborhood_arena;
+ DynamicArenaAllocator suffix_neighborhood_arena;
+ neighborhood_arena.init(1024, allocator::temp());
+ suffix_neighborhood_arena.init(1024, allocator::temp());
+ List(<String>) neighborhood;
+ List(<String>) suffix_neighborhood;
+ neighborhood.new_init_with_array({"A", "C", "G", "T"}, &neighborhood_arena);
+ suffix_neighborhood.new_init(16, &suffix_neighborhood_arena);
+ for (int i = 1; i < pattern.len; i += 1) {
+ // swap suffix_neighborhood and neighborhood. The previous
+ // neighborhood becomes the new suffix_neighborhood to iterate
+ // over. Now we need a place to collect the next neighborhood into,
+ // so we reuse the memory from the old suffix_neighborhood, which is
+ // no longer useful for future calculation, as its results have already
+ // been moved into the old neighborhood/new suffix_neighborhood as
+ // calculated during the last iteration. (otherwise we have to keep
+ // allocating new memory to collect the next neighborhood into).
+ //
+ // The memory itself is cleared for reuse by the arena holding the
+ // List (see next swap)
+ List(<String>) swap_var;
+ swap_var = suffix_neighborhood;
+ suffix_neighborhood = neighborhood;
+ neighborhood = swap_var;
- // Same swap with the arenas
- // Old strings and the List holding them all get cleared
- DynamicArenaAllocator swap_arena;
- swap_arena = suffix_neighborhood_arena;
- suffix_neighborhood_arena = neighborhood_arena;
- neighborhood_arena = swap_arena;
+ // Same swap with the arenas
+ // Old strings and the List holding them all get cleared
+ DynamicArenaAllocator swap_arena;
+ swap_arena = suffix_neighborhood_arena;
+ suffix_neighborhood_arena = neighborhood_arena;
+ neighborhood_arena = swap_arena;
- // clear out the old neighborhood for use in next iteration
- neighborhood_arena.free();
- neighborhood.new_init(suffix_neighborhood.len(), &neighborhood_arena);
+ // clear out the old neighborhood for use in next iteration
+ neighborhood_arena.free();
+ neighborhood.new_init(suffix_neighborhood.len(), &neighborhood_arena);
- int suffix_idx = pattern.len - i;
- String suffix = pattern[suffix_idx..];
- //io::printfn("%s, suffix_neighborhood = %s, neighborhood = %s", suffix, suffix_neighborhood, neighborhood);
- foreach (suffix_neighbor : suffix_neighborhood) {
- //io::printfn("%s, %s, %s, %s", suffix, suffix_neighbor, suffix_neighborhood, neighborhood);
- if (hamming_distance(suffix, suffix_neighbor) < d) {
- // adding the additional base will be at most hamming dist == d,
- neighborhood.push("A".concat(suffix_neighbor, &suffix_neighborhood_arena));
- neighborhood.push("C".concat(suffix_neighbor, &suffix_neighborhood_arena));
- neighborhood.push("G".concat(suffix_neighbor, &suffix_neighborhood_arena));
- neighborhood.push("T".concat(suffix_neighbor, &suffix_neighborhood_arena));
- } else {
- // hamming distance == d. It can't be more, because the neighbors are
- // generated up to hamming distance d. Adding the first symbol from the
- // original pattern cannot increase the hamming distance.
- neighborhood.push(pattern[suffix_idx - 1:1].concat(suffix_neighbor, &suffix_neighborhood_arena));
+ int suffix_idx = pattern.len - i;
+ String suffix = pattern[suffix_idx..];
+ //io::printfn("%s, suffix_neighborhood = %s, neighborhood = %s", suffix, suffix_neighborhood, neighborhood);
+ foreach (suffix_neighbor : suffix_neighborhood) {
+ //io::printfn("%s, %s, %s, %s", suffix, suffix_neighbor, suffix_neighborhood, neighborhood);
+ if (hamming_distance(suffix, suffix_neighbor) < d) {
+ // adding the additional base will be at most hamming dist == d,
+ neighborhood.push("A".concat(suffix_neighbor, &suffix_neighborhood_arena));
+ neighborhood.push("C".concat(suffix_neighbor, &suffix_neighborhood_arena));
+ neighborhood.push("G".concat(suffix_neighbor, &suffix_neighborhood_arena));
+ neighborhood.push("T".concat(suffix_neighbor, &suffix_neighborhood_arena));
+ } else {
+ // hamming distance == d. It can't be more, because the neighbors are
+ // generated up to hamming distance d. Adding the first symbol from the
+ // original pattern cannot increase the hamming distance.
+ neighborhood.push(pattern[suffix_idx - 1:1].concat(suffix_neighbor, &suffix_neighborhood_arena));
+ }
}
}
- }
- // Copy strings out to final result's allocator
- String[] res = allocator::new_array(alloc, String, neighborhood.len());
- foreach (i, neighbor : neighborhood) {
- res[i] = neighbor.copy(alloc);
- }
- return res;
+ // Copy strings out to final result's allocator
+ String[] res = allocator::new_array(alloc, String, neighborhood.len());
+ foreach (i, neighbor : neighborhood) {
+ res[i] = neighbor.copy(alloc);
+ }
+ return res;
+ };
}
struct NeighborsTest {
