[PATCH v2] flattree: Optimize stringtable_insert() with memmem()

According to perf result, stringtable_insert() is one of the five hotest
functions, which is obvious since it depends on a brute-force,
quadratic-complexity method to deduplicate the string block and is
called at creation of every property.

This patch replaces the brute-force deduplication with libc-provided
memmem(), which is guaranteed to be in linear complexity on both glibc
and musl libc.

On an i7-7200U Linux system with musl-libc, building the "dtbs" target
in Linux 6.11's arm64 port takes 19.1s less in average, achieving 25.1%
speed up.

Signed-off-by: Yao Zi <[email protected]>
---

Changed from v1
- Drop the hashtable for simplicity and update the commit message
- Add a comment to explain restrictions on deduplication
- Link to v1: https://lore.kernel.org/devicetree-compiler/[email protected]/

 flattree.c | 23 +++++++++++++++--------
 1 file changed, 15 insertions(+), 8 deletions(-)

diff --git a/flattree.c b/flattree.c
index 30e6de2044b2..d7328690e008 100644
--- a/flattree.c
+++ b/flattree.c
@@ -220,17 +220,24 @@ static struct emitter asm_emitter = {
 
 static int stringtable_insert(struct data *d, const char *str)
 {
-	unsigned int i;
+	const char *dup;
+	size_t size;
 
-	/* FIXME: do this more efficiently? */
+	/*
+	 * Reuse (subsequence of) existing string if possible. E.g.
+	 * "enable-method" could be reused when inserting "method".
+	 *
+	 * The terminating '\0' must be taken into account, or "foo\0" may be
+	 * wrongly recognized as subsequence of "foobar\0".
+	 */
+	size = strlen(str) + 1;
+	dup = memmem(d->val, d->len, str, size);
+	if (dup)
+		return dup - d->val;
 
-	for (i = 0; i < d->len; i++) {
-		if (streq(str, d->val + i))
-			return i;
-	}
+	*d = data_append_data(*d, str, size);
 
-	*d = data_append_data(*d, str, strlen(str)+1);
-	return i;
+	return d->len - size;
 }
 
 static void flatten_tree(struct node *tree, struct emitter *emit,
-- 
2.49.0