>From c1c9bcae16096c5346d9d82fa74b13e7d12c5d06 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Sun, 27 Sep 2026 15:31:18 +0000 Subject: [PATCH 20/25] regex: avoid tag dups use merge_nodup in tre_set_union to avoid duplicate tags in case of iterated nullable patterns like (a*){0,n} (|(|(|a))){0,n} these have many tags repeated ~n times per transition in their tnfa causing exec time slow down and memory use. explicit repetition like (a*)(a*)(a*)(a*).. is not addressed as there the tags are different. note: a merge_nodup is O(n^2) while just doing a copy is O(n), but getting long merges requires large nullable subtrees so the overall amortized cost is not clear. i did not measure slow down, but even if i did, we are trading regcomp time for regexec time. --- src/regex/regcomp.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index ed35ac72..52119a38 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -2105,11 +2105,8 @@ tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2, * (i + num_tags + 1))); if (new_tags == NULL) return NULL; - for (j = 0; j < i; j++) - new_tags[j] = set1[s1].tags[j]; - for (i = 0; i < num_tags; i++) - new_tags[j + i] = tags[i]; - new_tags[j + i] = -1; + j = merge_nodup(new_tags, set1[s1].tags, i, tags, num_tags); + new_tags[j] = -1; new_set[s1].tags = new_tags; } } -- 2.52.0