[RESEND PATCH] flattree: Optimize stringtable_insert()

[RESEND PATCH] flattree: Optimize stringtable_insert()

[Yao Zi]

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 optimizes the function in two ways,

- Replace brute-force deduplication with libc-provided memmem(), which
  is guaranteed to be in linear complexity on both glibc on musl libc.
  This brings roughly 24.6% reduction in execution time.

- An open-addressing hashtable is maintained to track strings already
  inserted. As property names are likely to be duplicated, this could
  filter out many existing strings, avoiding traversing the string
  block. This reduces another 1.2% of execution time.

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

Signed-off-by: Yao Zi <ziyao@disroot.org>
---

This patch was originally created as GitHub PR[1] and closed by myself
later as I found more opportunities to optimize (mostly about
get_property_by_*). Failing to do so with some trial, I decide to send
it as is now.

[1]: https://github.com/dgibson/dtc/pull/164

 flattree.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 129 insertions(+), 14 deletions(-)

diff --git a/flattree.c b/flattree.c
index 30e6de2..afca1f2 100644
--- a/flattree.c
+++ b/flattree.c
@@ -218,23 +218,134 @@ static struct emitter asm_emitter = {
 	.property = asm_emit_property,
 };
 
-static int stringtable_insert(struct data *d, const char *str)
+struct stringtable {
+	unsigned int len, cap;
+	struct data data;
+	int *slots;
+};
+
+/*
+ * Must be 2^n to ensure stringtable.cap - 1 correctly masks hash into the
+ * index of slots
+ */
+#define stringtable_initcap		256
+
+static unsigned int stringtable_hash(const char *str, size_t len)
+{
+	unsigned int hash = (unsigned int)len;
+
+	for (; len > 0; len--)
+		hash ^= (hash << 5) + (hash >> 2) + str[len - 1];
+
+	return hash;
+}
+
+static void stringtable_init(struct stringtable *strtab)
 {
 	unsigned int i;
 
-	/* FIXME: do this more efficiently? */
+	*strtab = (struct stringtable) {
+			.len	= 0,
+			.cap	= stringtable_initcap,
+			.data	= empty_data,
+			.slots	= xmalloc(sizeof(int) * stringtable_initcap),
+		  };
 
-	for (i = 0; i < d->len; i++) {
-		if (streq(str, d->val + i))
-			return i;
-	}
+	for (i = 0; i < strtab->cap; i++)
+		strtab->slots[i] = -1;
+}
+
+/*
+ * Return the internal data and let the caller owns it.
+ */
+static struct data stringtable_data(struct stringtable *strtab)
+{
+	free(strtab->slots);
+	strtab->slots = NULL;
+
+	return strtab->data;
+}
+
+static void stringtable_free(struct stringtable *strtab)
+{
+	free(strtab->slots);
+	strtab->slots = NULL;
+
+	data_free(strtab->data);
+}
+
+static unsigned int stringtable_findslot(int *slots, unsigned int cap,
+					 unsigned int hash)
+{
+	unsigned int i, mask;
+
+	mask = cap - 1;
+
+	for (i = hash & mask; slots[i] != -1; i = (i + 1) & mask) ;
 
-	*d = data_append_data(*d, str, strlen(str)+1);
 	return i;
 }
 
+static void stringtable_grow(struct stringtable *strtab)
+{
+	unsigned int newcap = strtab->cap * 2;
+	int *newslots = xmalloc(newcap * sizeof(int));
+	unsigned int i;
+
+	for (i = 0; i < newcap; i++)
+		newslots[i] = -1;
+
+	for (i = 0; i < strtab->cap; i++) {
+		int off = strtab->slots[i];
+		const char *str = strtab->data.val + off;
+		unsigned int hash = stringtable_hash(str, strlen(str));
+		int newslot = stringtable_findslot(newslots, newcap, hash);
+
+		newslots[newslot] = off;
+	}
+
+	strtab->cap	= newcap;
+	strtab->slots	= newslots;
+}
+
+static int stringtable_insert(struct stringtable *strtab, const char *str)
+{
+	unsigned int hash, i, mask;
+	int *slots, *slot;
+	const char *dup;
+	size_t len;
+
+	if (strtab->cap < strtab->len * 2)
+		stringtable_grow(strtab);
+
+	len	= strlen(str);
+	mask	= strtab->cap - 1;
+	hash	= stringtable_hash(str, len);
+	slots	= strtab->slots;
+
+	for (i = hash & mask; *(slot = &slots[i]) != -1; i = (i + 1) & mask) {
+		const char *oldstr = strtab->data.val + *slot;
+
+		if (streq(str, oldstr))
+			return *slot;
+	}
+
+	/* Try to match a subsequence */
+	dup = memmem(strtab->data.val, strtab->data.len, str, len + 1);
+	if (dup) {
+		*slot = dup - strtab->data.val;
+	} else {
+		*slot = strtab->data.len;
+		strtab->data = data_append_data(strtab->data, str, len + 1);
+	}
+
+	strtab->len++;
+
+	return *slot;
+}
+
 static void flatten_tree(struct node *tree, struct emitter *emit,
-			 void *etarget, struct data *strbuf,
+			 void *etarget, struct stringtable *strbuf,
 			 struct version_info *vi)
 {
 	struct property *prop;
@@ -350,10 +461,12 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
 	struct data blob       = empty_data;
 	struct data reservebuf = empty_data;
 	struct data dtbuf      = empty_data;
-	struct data strbuf     = empty_data;
+	struct stringtable strbuf;
 	struct fdt_header fdt;
 	int padlen = 0;
 
+	stringtable_init(&strbuf);
+
 	for (i = 0; i < ARRAY_SIZE(version_table); i++) {
 		if (version_table[i].version == version)
 			vi = &version_table[i];
@@ -367,7 +480,7 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
 	reservebuf = flatten_reserve_list(dti->reservelist, vi);
 
 	/* Make header */
-	make_fdt_header(&fdt, vi, reservebuf.len, dtbuf.len, strbuf.len,
+	make_fdt_header(&fdt, vi, reservebuf.len, dtbuf.len, strbuf.data.len,
 			dti->boot_cpuid_phys);
 
 	/*
@@ -407,7 +520,7 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
 	blob = data_merge(blob, reservebuf);
 	blob = data_append_zeroes(blob, sizeof(struct fdt_reserve_entry));
 	blob = data_merge(blob, dtbuf);
-	blob = data_merge(blob, strbuf);
+	blob = data_merge(blob, stringtable_data(&strbuf));
 
 	/*
 	 * If the user asked for more space than is used, pad out the blob.
@@ -448,10 +561,12 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
 {
 	struct version_info *vi = NULL;
 	unsigned int i;
-	struct data strbuf = empty_data;
+	struct stringtable strbuf;
 	struct reserve_info *re;
 	const char *symprefix = "dt";
 
+	stringtable_init(&strbuf);
+
 	for (i = 0; i < ARRAY_SIZE(version_table); i++) {
 		if (version_table[i].version == version)
 			vi = &version_table[i];
@@ -541,7 +656,7 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
 	emit_label(f, symprefix, "struct_end");
 
 	emit_label(f, symprefix, "strings_start");
-	dump_stringtable_asm(f, strbuf);
+	dump_stringtable_asm(f, strbuf.data);
 	emit_label(f, symprefix, "strings_end");
 
 	emit_label(f, symprefix, "blob_end");
@@ -560,7 +675,7 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
 		asm_emit_align(f, alignsize);
 	emit_label(f, symprefix, "blob_abs_end");
 
-	data_free(strbuf);
+	stringtable_free(&strbuf);
 }
 
 struct inbuf {
-- 
2.49.0

Re: [RESEND PATCH] flattree: Optimize stringtable_insert()

[Simon Glass]

Hi Yao,

On Sat, 12 Apr 2025 at 04:05, Yao Zi <ziyao@disroot.org> wrote:
>
> 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 optimizes the function in two ways,
>
> - Replace brute-force deduplication with libc-provided memmem(), which
>   is guaranteed to be in linear complexity on both glibc on musl libc.
>   This brings roughly 24.6% reduction in execution time.

This is a really good improvement!

>
> - An open-addressing hashtable is maintained to track strings already
>   inserted. As property names are likely to be duplicated, this could
>   filter out many existing strings, avoiding traversing the string
>   block. This reduces another 1.2% of execution time.
>
> On an i7-7200U Linux system with musl-libc, building the "dtbs" target
> in Linux 6.11's arm64 port takes 19.8s less in average, achieving 25.8%
> speed up.
>
> Signed-off-by: Yao Zi <ziyao@disroot.org>
> ---
>
> This patch was originally created as GitHub PR[1] and closed by myself
> later as I found more opportunities to optimize (mostly about
> get_property_by_*). Failing to do so with some trial, I decide to send
> it as is now.
>
> [1]: https://github.com/dgibson/dtc/pull/164
>
>  flattree.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 129 insertions(+), 14 deletions(-)
>
> diff --git a/flattree.c b/flattree.c
> index 30e6de2..afca1f2 100644
> --- a/flattree.c
> +++ b/flattree.c
> @@ -218,23 +218,134 @@ static struct emitter asm_emitter = {
>         .property = asm_emit_property,
>  };
>
> -static int stringtable_insert(struct data *d, const char *str)
> +struct stringtable {
> +       unsigned int len, cap;
> +       struct data data;
> +       int *slots;
> +};

Could you comment these items, including that a slot of -1 means it is free?

> +
> +/*
> + * Must be 2^n to ensure stringtable.cap - 1 correctly masks hash into the
> + * index of slots
> + */
> +#define stringtable_initcap            256

When building the kernel, does stringtable_grow() get called
regularly? If so, and if it affects execution table, perhaps this
value could be larger?

> +
> +static unsigned int stringtable_hash(const char *str, size_t len)
> +{
> +       unsigned int hash = (unsigned int)len;
> +
> +       for (; len > 0; len--)
> +               hash ^= (hash << 5) + (hash >> 2) + str[len - 1];
> +
> +       return hash;
> +}
> +
> +static void stringtable_init(struct stringtable *strtab)
>  {
>         unsigned int i;
>
> -       /* FIXME: do this more efficiently? */
> +       *strtab = (struct stringtable) {
> +                       .len    = 0,
> +                       .cap    = stringtable_initcap,
> +                       .data   = empty_data,
> +                       .slots  = xmalloc(sizeof(int) * stringtable_initcap),
> +                 };
>
> -       for (i = 0; i < d->len; i++) {
> -               if (streq(str, d->val + i))
> -                       return i;
> -       }
> +       for (i = 0; i < strtab->cap; i++)
> +               strtab->slots[i] = -1;
> +}
> +
> +/*
> + * Return the internal data and let the caller owns it.
> + */
> +static struct data stringtable_data(struct stringtable *strtab)
> +{
> +       free(strtab->slots);
> +       strtab->slots = NULL;
> +
> +       return strtab->data;
> +}
> +
> +static void stringtable_free(struct stringtable *strtab)
> +{
> +       free(strtab->slots);
> +       strtab->slots = NULL;
> +
> +       data_free(strtab->data);
> +}
> +
> +static unsigned int stringtable_findslot(int *slots, unsigned int cap,
> +                                        unsigned int hash)
> +{
> +       unsigned int i, mask;
> +
> +       mask = cap - 1;
> +
> +       for (i = hash & mask; slots[i] != -1; i = (i + 1) & mask) ;
>
> -       *d = data_append_data(*d, str, strlen(str)+1);
>         return i;
>  }
>
> +static void stringtable_grow(struct stringtable *strtab)
> +{
> +       unsigned int newcap = strtab->cap * 2;
> +       int *newslots = xmalloc(newcap * sizeof(int));
> +       unsigned int i;
> +
> +       for (i = 0; i < newcap; i++)
> +               newslots[i] = -1;
> +
> +       for (i = 0; i < strtab->cap; i++) {
> +               int off = strtab->slots[i];
> +               const char *str = strtab->data.val + off;
> +               unsigned int hash = stringtable_hash(str, strlen(str));
> +               int newslot = stringtable_findslot(newslots, newcap, hash);
> +
> +               newslots[newslot] = off;
> +       }
> +
> +       strtab->cap     = newcap;
> +       strtab->slots   = newslots;

Does strtab->slots get freed here?

> +}
> +
> +static int stringtable_insert(struct stringtable *strtab, const char *str)
> +{
> +       unsigned int hash, i, mask;
> +       int *slots, *slot;
> +       const char *dup;
> +       size_t len;
> +
> +       if (strtab->cap < strtab->len * 2)
> +               stringtable_grow(strtab);
> +
> +       len     = strlen(str);
> +       mask    = strtab->cap - 1;
> +       hash    = stringtable_hash(str, len);
> +       slots   = strtab->slots;
> +
> +       for (i = hash & mask; *(slot = &slots[i]) != -1; i = (i + 1) & mask) {
> +               const char *oldstr = strtab->data.val + *slot;
> +
> +               if (streq(str, oldstr))
> +                       return *slot;
> +       }
> +
> +       /* Try to match a subsequence */
> +       dup = memmem(strtab->data.val, strtab->data.len, str, len + 1);

Is there a case early on where strtab->data.len < len + 1 ?

> +       if (dup) {
> +               *slot = dup - strtab->data.val;
> +       } else {
> +               *slot = strtab->data.len;
> +               strtab->data = data_append_data(strtab->data, str, len + 1);
> +       }

What case is this subsequence-code handling? If you add "frederick"
and then "fred", won't this end up using "frederick" for both, in the
flattened tree? I suppose not since the tests pass, but I think a
better comment would help.

> +
> +       strtab->len++;
> +
> +       return *slot;
> +}
> +
>  static void flatten_tree(struct node *tree, struct emitter *emit,
> -                        void *etarget, struct data *strbuf,
> +                        void *etarget, struct stringtable *strbuf,
>                          struct version_info *vi)
>  {
>         struct property *prop;
> @@ -350,10 +461,12 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
>         struct data blob       = empty_data;
>         struct data reservebuf = empty_data;
>         struct data dtbuf      = empty_data;
> -       struct data strbuf     = empty_data;
> +       struct stringtable strbuf;
>         struct fdt_header fdt;
>         int padlen = 0;
>
> +       stringtable_init(&strbuf);
> +
>         for (i = 0; i < ARRAY_SIZE(version_table); i++) {
>                 if (version_table[i].version == version)
>                         vi = &version_table[i];
> @@ -367,7 +480,7 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
>         reservebuf = flatten_reserve_list(dti->reservelist, vi);
>
>         /* Make header */
> -       make_fdt_header(&fdt, vi, reservebuf.len, dtbuf.len, strbuf.len,
> +       make_fdt_header(&fdt, vi, reservebuf.len, dtbuf.len, strbuf.data.len,
>                         dti->boot_cpuid_phys);
>
>         /*
> @@ -407,7 +520,7 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
>         blob = data_merge(blob, reservebuf);
>         blob = data_append_zeroes(blob, sizeof(struct fdt_reserve_entry));
>         blob = data_merge(blob, dtbuf);
> -       blob = data_merge(blob, strbuf);
> +       blob = data_merge(blob, stringtable_data(&strbuf));
>
>         /*
>          * If the user asked for more space than is used, pad out the blob.
> @@ -448,10 +561,12 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
>  {
>         struct version_info *vi = NULL;
>         unsigned int i;
> -       struct data strbuf = empty_data;
> +       struct stringtable strbuf;
>         struct reserve_info *re;
>         const char *symprefix = "dt";
>
> +       stringtable_init(&strbuf);
> +
>         for (i = 0; i < ARRAY_SIZE(version_table); i++) {
>                 if (version_table[i].version == version)
>                         vi = &version_table[i];
> @@ -541,7 +656,7 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
>         emit_label(f, symprefix, "struct_end");
>
>         emit_label(f, symprefix, "strings_start");
> -       dump_stringtable_asm(f, strbuf);
> +       dump_stringtable_asm(f, strbuf.data);
>         emit_label(f, symprefix, "strings_end");
>
>         emit_label(f, symprefix, "blob_end");
> @@ -560,7 +675,7 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
>                 asm_emit_align(f, alignsize);
>         emit_label(f, symprefix, "blob_abs_end");
>
> -       data_free(strbuf);
> +       stringtable_free(&strbuf);
>  }
>
>  struct inbuf {
> --
> 2.49.0
>
>

Regards,
Simon

Re: [RESEND PATCH] flattree: Optimize stringtable_insert()

[Yao Zi]

On Sat, Apr 12, 2025 at 06:45:07AM -0600, Simon Glass wrote:
> Hi Yao,
> 
> On Sat, 12 Apr 2025 at 04:05, Yao Zi <ziyao@disroot.org> wrote:

...

> > diff --git a/flattree.c b/flattree.c
> > index 30e6de2..afca1f2 100644
> > --- a/flattree.c
> > +++ b/flattree.c
> > @@ -218,23 +218,134 @@ static struct emitter asm_emitter = {
> >         .property = asm_emit_property,
> >  };
> >
> > -static int stringtable_insert(struct data *d, const char *str)
> > +struct stringtable {
> > +       unsigned int len, cap;
> > +       struct data data;
> > +       int *slots;
> > +};
> 
> Could you comment these items, including that a slot of -1 means it is free?

Sure, I'll do it in v2.

> > +
> > +/*
> > + * Must be 2^n to ensure stringtable.cap - 1 correctly masks hash into the
> > + * index of slots
> > + */
> > +#define stringtable_initcap            256
> 
> When building the kernel, does stringtable_grow() get called
> regularly? If so, and if it affects execution table, perhaps this
> value could be larger?

Among the 1161 devicetrees in Linux 6.11 (counted by
find arch/arm64/boot/dts/ -name '*.dtb' | wc -l), 821 of them trigger
stringtable_grow() for at least one time. But increasing the initial
capability doesn't help much for the overall performance since it's not
a hot function actually. Thus I'd like to keep the macro as is.

> > +
> > +static unsigned int stringtable_hash(const char *str, size_t len)
> > +{
> > +       unsigned int hash = (unsigned int)len;
> > +
> > +       for (; len > 0; len--)
> > +               hash ^= (hash << 5) + (hash >> 2) + str[len - 1];
> > +
> > +       return hash;
> > +}

...

> > +static void stringtable_grow(struct stringtable *strtab)
> > +{
> > +       unsigned int newcap = strtab->cap * 2;
> > +       int *newslots = xmalloc(newcap * sizeof(int));
> > +       unsigned int i;
> > +
> > +       for (i = 0; i < newcap; i++)
> > +               newslots[i] = -1;
> > +
> > +       for (i = 0; i < strtab->cap; i++) {
> > +               int off = strtab->slots[i];
> > +               const char *str = strtab->data.val + off;
> > +               unsigned int hash = stringtable_hash(str, strlen(str));
> > +               int newslot = stringtable_findslot(newslots, newcap, hash);
> > +
> > +               newslots[newslot] = off;
> > +       }
> > +
> > +       strtab->cap     = newcap;
> > +       strtab->slots   = newslots;
> 
> Does strtab->slots get freed here?

Thanks for catching this! It's lost here, causing some leaking, I'll fix
it in v2.

> > +}
> > +
> > +static int stringtable_insert(struct stringtable *strtab, const char *str)
> > +{
> > +       unsigned int hash, i, mask;
> > +       int *slots, *slot;
> > +       const char *dup;
> > +       size_t len;
> > +
> > +       if (strtab->cap < strtab->len * 2)
> > +               stringtable_grow(strtab);
> > +
> > +       len     = strlen(str);
> > +       mask    = strtab->cap - 1;
> > +       hash    = stringtable_hash(str, len);
> > +       slots   = strtab->slots;
> > +
> > +       for (i = hash & mask; *(slot = &slots[i]) != -1; i = (i + 1) & mask) {
> > +               const char *oldstr = strtab->data.val + *slot;
> > +
> > +               if (streq(str, oldstr))
> > +                       return *slot;
> > +       }
> > +
> > +       /* Try to match a subsequence */
> > +       dup = memmem(strtab->data.val, strtab->data.len, str, len + 1);
> 
> Is there a case early on where strtab->data.len < len + 1 ?

Yes, but I don't think it's worth a special branch, as it's very rare.
AFAIK the memmem implementation of musl libc is even able to handle such
cases,

        /* Return immediately when needle is longer than haystack */
        if (k<l) return 0;


> > +       if (dup) {
> > +               *slot = dup - strtab->data.val;
> > +       } else {
> > +               *slot = strtab->data.len;
> > +               strtab->data = data_append_data(strtab->data, str, len + 1);
> > +       }
> 
> What case is this subsequence-code handling?

String block contains C-style strings (terminated by zero). If A is
a suffix of B, we could reuse the data of B by pointing to the middle of
B when emitting A. For example, we could reuse "enable-method" when
emitting "method", which is common in a DTS of ARM SoC.

> If you add "frederick"
> and then "fred", won't this end up using "frederick" for both, in the
> flattened tree? I suppose not since the tests pass, but I think a
> better comment would help.

This won't happen since we take the terminating '\0' into account when
searching for a subsequence, the two strings are actually "frederick\0"
and "fred\0", where the latter is obviously not a subsequence of the
former one.

At first I didn't add such sebsequence deduplication and then noted
small increasing of size of compiled devicetree blobs. Then I realized
the original code may reuse sebsequences as well -- sure I'll add a
comment to explain to avoid confusion in the future.

> > +
> > +       strtab->len++;
> > +
> > +       return *slot;
> > +}
> > +

...

> Regards,
> Simon

Regards,
Yao Zi

Re: [RESEND PATCH] flattree: Optimize stringtable_insert()

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 8410 bytes --]

On Sat, Apr 12, 2025 at 10:03:52AM +0000, Yao Zi wrote:
> 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.

Right.  The optimization strategy of dtc and libfdt is pretty much "if
it's slow enough that it bothers someone, then we'll think about it".
Little effort has gone into optimization, in general, because device
trees are generally so small that runtime hasn't really been a
problem, even with very inefficient coding.

> This patch optimizes the function in two ways,
> 
> - Replace brute-force deduplication with libc-provided memmem(), which
>   is guaranteed to be in linear complexity on both glibc on musl libc.
>   This brings roughly 24.6% reduction in execution time.

That said, this is a substantial improvement for a very simple change.
I'd be happy to apply this change, separated into its own patch.

> - An open-addressing hashtable is maintained to track strings already
>   inserted. As property names are likely to be duplicated, this could
>   filter out many existing strings, avoiding traversing the string
>   block. This reduces another 1.2% of execution time.

Honestly the substantial complexity this adds doesn't seem worth it
for a mere 1.2% improvement.

> On an i7-7200U Linux system with musl-libc, building the "dtbs" target
> in Linux 6.11's arm64 port takes 19.8s less in average, achieving 25.8%
> speed up.
> 
> Signed-off-by: Yao Zi <ziyao@disroot.org>
> ---
> 
> This patch was originally created as GitHub PR[1] and closed by myself
> later as I found more opportunities to optimize (mostly about
> get_property_by_*). Failing to do so with some trial, I decide to send
> it as is now.
> 
> [1]: https://github.com/dgibson/dtc/pull/164
> 
>  flattree.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 129 insertions(+), 14 deletions(-)
> 
> diff --git a/flattree.c b/flattree.c
> index 30e6de2..afca1f2 100644
> --- a/flattree.c
> +++ b/flattree.c
> @@ -218,23 +218,134 @@ static struct emitter asm_emitter = {
>  	.property = asm_emit_property,
>  };
>  
> -static int stringtable_insert(struct data *d, const char *str)
> +struct stringtable {
> +	unsigned int len, cap;
> +	struct data data;
> +	int *slots;
> +};
> +
> +/*
> + * Must be 2^n to ensure stringtable.cap - 1 correctly masks hash into the
> + * index of slots
> + */
> +#define stringtable_initcap		256
> +
> +static unsigned int stringtable_hash(const char *str, size_t len)
> +{
> +	unsigned int hash = (unsigned int)len;
> +
> +	for (; len > 0; len--)
> +		hash ^= (hash << 5) + (hash >> 2) + str[len - 1];
> +
> +	return hash;
> +}
> +
> +static void stringtable_init(struct stringtable *strtab)
>  {
>  	unsigned int i;
>  
> -	/* FIXME: do this more efficiently? */
> +	*strtab = (struct stringtable) {
> +			.len	= 0,
> +			.cap	= stringtable_initcap,
> +			.data	= empty_data,
> +			.slots	= xmalloc(sizeof(int) * stringtable_initcap),
> +		  };
>  
> -	for (i = 0; i < d->len; i++) {
> -		if (streq(str, d->val + i))
> -			return i;
> -	}
> +	for (i = 0; i < strtab->cap; i++)
> +		strtab->slots[i] = -1;
> +}
> +
> +/*
> + * Return the internal data and let the caller owns it.
> + */
> +static struct data stringtable_data(struct stringtable *strtab)
> +{
> +	free(strtab->slots);
> +	strtab->slots = NULL;
> +
> +	return strtab->data;
> +}
> +
> +static void stringtable_free(struct stringtable *strtab)
> +{
> +	free(strtab->slots);
> +	strtab->slots = NULL;
> +
> +	data_free(strtab->data);
> +}
> +
> +static unsigned int stringtable_findslot(int *slots, unsigned int cap,
> +					 unsigned int hash)
> +{
> +	unsigned int i, mask;
> +
> +	mask = cap - 1;
> +
> +	for (i = hash & mask; slots[i] != -1; i = (i + 1) & mask) ;
>  
> -	*d = data_append_data(*d, str, strlen(str)+1);
>  	return i;
>  }
>  
> +static void stringtable_grow(struct stringtable *strtab)
> +{
> +	unsigned int newcap = strtab->cap * 2;
> +	int *newslots = xmalloc(newcap * sizeof(int));
> +	unsigned int i;
> +
> +	for (i = 0; i < newcap; i++)
> +		newslots[i] = -1;
> +
> +	for (i = 0; i < strtab->cap; i++) {
> +		int off = strtab->slots[i];
> +		const char *str = strtab->data.val + off;
> +		unsigned int hash = stringtable_hash(str, strlen(str));
> +		int newslot = stringtable_findslot(newslots, newcap, hash);
> +
> +		newslots[newslot] = off;
> +	}
> +
> +	strtab->cap	= newcap;
> +	strtab->slots	= newslots;
> +}
> +
> +static int stringtable_insert(struct stringtable *strtab, const char *str)
> +{
> +	unsigned int hash, i, mask;
> +	int *slots, *slot;
> +	const char *dup;
> +	size_t len;
> +
> +	if (strtab->cap < strtab->len * 2)
> +		stringtable_grow(strtab);
> +
> +	len	= strlen(str);
> +	mask	= strtab->cap - 1;
> +	hash	= stringtable_hash(str, len);
> +	slots	= strtab->slots;
> +
> +	for (i = hash & mask; *(slot = &slots[i]) != -1; i = (i + 1) & mask) {
> +		const char *oldstr = strtab->data.val + *slot;
> +
> +		if (streq(str, oldstr))
> +			return *slot;
> +	}
> +
> +	/* Try to match a subsequence */
> +	dup = memmem(strtab->data.val, strtab->data.len, str, len + 1);
> +	if (dup) {
> +		*slot = dup - strtab->data.val;
> +	} else {
> +		*slot = strtab->data.len;
> +		strtab->data = data_append_data(strtab->data, str, len + 1);
> +	}
> +
> +	strtab->len++;
> +
> +	return *slot;
> +}
> +
>  static void flatten_tree(struct node *tree, struct emitter *emit,
> -			 void *etarget, struct data *strbuf,
> +			 void *etarget, struct stringtable *strbuf,
>  			 struct version_info *vi)
>  {
>  	struct property *prop;
> @@ -350,10 +461,12 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
>  	struct data blob       = empty_data;
>  	struct data reservebuf = empty_data;
>  	struct data dtbuf      = empty_data;
> -	struct data strbuf     = empty_data;
> +	struct stringtable strbuf;
>  	struct fdt_header fdt;
>  	int padlen = 0;
>  
> +	stringtable_init(&strbuf);
> +
>  	for (i = 0; i < ARRAY_SIZE(version_table); i++) {
>  		if (version_table[i].version == version)
>  			vi = &version_table[i];
> @@ -367,7 +480,7 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
>  	reservebuf = flatten_reserve_list(dti->reservelist, vi);
>  
>  	/* Make header */
> -	make_fdt_header(&fdt, vi, reservebuf.len, dtbuf.len, strbuf.len,
> +	make_fdt_header(&fdt, vi, reservebuf.len, dtbuf.len, strbuf.data.len,
>  			dti->boot_cpuid_phys);
>  
>  	/*
> @@ -407,7 +520,7 @@ void dt_to_blob(FILE *f, struct dt_info *dti, int version)
>  	blob = data_merge(blob, reservebuf);
>  	blob = data_append_zeroes(blob, sizeof(struct fdt_reserve_entry));
>  	blob = data_merge(blob, dtbuf);
> -	blob = data_merge(blob, strbuf);
> +	blob = data_merge(blob, stringtable_data(&strbuf));
>  
>  	/*
>  	 * If the user asked for more space than is used, pad out the blob.
> @@ -448,10 +561,12 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
>  {
>  	struct version_info *vi = NULL;
>  	unsigned int i;
> -	struct data strbuf = empty_data;
> +	struct stringtable strbuf;
>  	struct reserve_info *re;
>  	const char *symprefix = "dt";
>  
> +	stringtable_init(&strbuf);
> +
>  	for (i = 0; i < ARRAY_SIZE(version_table); i++) {
>  		if (version_table[i].version == version)
>  			vi = &version_table[i];
> @@ -541,7 +656,7 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
>  	emit_label(f, symprefix, "struct_end");
>  
>  	emit_label(f, symprefix, "strings_start");
> -	dump_stringtable_asm(f, strbuf);
> +	dump_stringtable_asm(f, strbuf.data);
>  	emit_label(f, symprefix, "strings_end");
>  
>  	emit_label(f, symprefix, "blob_end");
> @@ -560,7 +675,7 @@ void dt_to_asm(FILE *f, struct dt_info *dti, int version)
>  		asm_emit_align(f, alignsize);
>  	emit_label(f, symprefix, "blob_abs_end");
>  
> -	data_free(strbuf);
> +	stringtable_free(&strbuf);
>  }
>  
>  struct inbuf {

-- 
David Gibson (he or they)	| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you, not the other way
				| around.
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [RESEND PATCH] flattree: Optimize stringtable_insert()

[Yao Zi]

On Mon, Apr 14, 2025 at 04:24:23PM +1000, David Gibson wrote:
> On Sat, Apr 12, 2025 at 10:03:52AM +0000, Yao Zi wrote:
> > 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.
> 
> Right.  The optimization strategy of dtc and libfdt is pretty much "if
> it's slow enough that it bothers someone, then we'll think about it".
> Little effort has gone into optimization, in general, because device
> trees are generally so small that runtime hasn't really been a
> problem, even with very inefficient coding.
> 
> > This patch optimizes the function in two ways,
> > 
> > - Replace brute-force deduplication with libc-provided memmem(), which
> >   is guaranteed to be in linear complexity on both glibc on musl libc.
> >   This brings roughly 24.6% reduction in execution time.
> 
> That said, this is a substantial improvement for a very simple change.
> I'd be happy to apply this change, separated into its own patch.
> 
> > - An open-addressing hashtable is maintained to track strings already
> >   inserted. As property names are likely to be duplicated, this could
> >   filter out many existing strings, avoiding traversing the string
> >   block. This reduces another 1.2% of execution time.
> 
> Honestly the substantial complexity this adds doesn't seem worth it
> for a mere 1.2% improvement.

Thanks for the feedback. At first I'm only interested in improving the
deduplication with a hashtable -- but later it's found that reusing
subsequences is also necessary and memmem() itself surprisingly brings a
huge improvement.

I'm preparing for v2 where the hashtable is split out and also used for
optimizing get_node_by_label(). Although the changes are not ready for
reviewing now, the new optimization reduces executation by another
6.4%. Do you think it's a reason strong enough to keep the the code?
Here's a summary of the changes,

	Makefile.dtc |   1 +
	checks.c     |   4 --
	dtc-parser.y |   4 +-
	dtc.c        |   4 ++
	dtc.h        |  19 +++++++
	flattree.c   |  68 +++++++++++++++++++------
	hashtable.c  | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++
	livetree.c   |  35 +++++++++++--
	8 files changed, 251 insertions(+), 25 deletions(-)

...

> -- 
> David Gibson (he or they)	| I'll have my music baroque, and my code
> david AT gibson.dropbear.id.au	| minimalist, thank you, not the other way
> 				| around.
> http://www.ozlabs.org/~dgibson

Best regards,
Yao Zi

Re: [RESEND PATCH] flattree: Optimize stringtable_insert()

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 2949 bytes --]

On Mon, Apr 14, 2025 at 12:10:09PM +0000, Yao Zi wrote:
> On Mon, Apr 14, 2025 at 04:24:23PM +1000, David Gibson wrote:
> > On Sat, Apr 12, 2025 at 10:03:52AM +0000, Yao Zi wrote:
> > > 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.
> > 
> > Right.  The optimization strategy of dtc and libfdt is pretty much "if
> > it's slow enough that it bothers someone, then we'll think about it".
> > Little effort has gone into optimization, in general, because device
> > trees are generally so small that runtime hasn't really been a
> > problem, even with very inefficient coding.
> > 
> > > This patch optimizes the function in two ways,
> > > 
> > > - Replace brute-force deduplication with libc-provided memmem(), which
> > >   is guaranteed to be in linear complexity on both glibc on musl libc.
> > >   This brings roughly 24.6% reduction in execution time.
> > 
> > That said, this is a substantial improvement for a very simple change.
> > I'd be happy to apply this change, separated into its own patch.
> > 
> > > - An open-addressing hashtable is maintained to track strings already
> > >   inserted. As property names are likely to be duplicated, this could
> > >   filter out many existing strings, avoiding traversing the string
> > >   block. This reduces another 1.2% of execution time.
> > 
> > Honestly the substantial complexity this adds doesn't seem worth it
> > for a mere 1.2% improvement.
> 
> Thanks for the feedback. At first I'm only interested in improving the
> deduplication with a hashtable -- but later it's found that reusing
> subsequences is also necessary and memmem() itself surprisingly brings a
> huge improvement.
> 
> I'm preparing for v2 where the hashtable is split out and also used for
> optimizing get_node_by_label(). Although the changes are not ready for
> reviewing now, the new optimization reduces executation by another
> 6.4%. Do you think it's a reason strong enough to keep the the code?

Probably not, unless you can convince me there's a use case where the
performance is a pressing practical problem.

> Here's a summary of the changes,
> 
> 	Makefile.dtc |   1 +
> 	checks.c     |   4 --
> 	dtc-parser.y |   4 +-
> 	dtc.c        |   4 ++
> 	dtc.h        |  19 +++++++
> 	flattree.c   |  68 +++++++++++++++++++------
> 	hashtable.c  | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++
> 	livetree.c   |  35 +++++++++++--
> 	8 files changed, 251 insertions(+), 25 deletions(-)
> 
> ...
> 
> 
> Best regards,
> Yao Zi
> 

-- 
David Gibson (he or they)	| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you, not the other way
				| around.
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [RESEND PATCH] flattree: Optimize stringtable_insert()

[Yao Zi]

On Tue, Apr 15, 2025 at 11:39:03AM +1000, David Gibson wrote:
> On Mon, Apr 14, 2025 at 12:10:09PM +0000, Yao Zi wrote:
> > On Mon, Apr 14, 2025 at 04:24:23PM +1000, David Gibson wrote:
> > > On Sat, Apr 12, 2025 at 10:03:52AM +0000, Yao Zi wrote:
> > > > 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.
> > > 
> > > Right.  The optimization strategy of dtc and libfdt is pretty much "if
> > > it's slow enough that it bothers someone, then we'll think about it".
> > > Little effort has gone into optimization, in general, because device
> > > trees are generally so small that runtime hasn't really been a
> > > problem, even with very inefficient coding.
> > > 
> > > > This patch optimizes the function in two ways,
> > > > 
> > > > - Replace brute-force deduplication with libc-provided memmem(), which
> > > >   is guaranteed to be in linear complexity on both glibc on musl libc.
> > > >   This brings roughly 24.6% reduction in execution time.
> > > 
> > > That said, this is a substantial improvement for a very simple change.
> > > I'd be happy to apply this change, separated into its own patch.
> > > 
> > > > - An open-addressing hashtable is maintained to track strings already
> > > >   inserted. As property names are likely to be duplicated, this could
> > > >   filter out many existing strings, avoiding traversing the string
> > > >   block. This reduces another 1.2% of execution time.
> > > 
> > > Honestly the substantial complexity this adds doesn't seem worth it
> > > for a mere 1.2% improvement.
> > 
> > Thanks for the feedback. At first I'm only interested in improving the
> > deduplication with a hashtable -- but later it's found that reusing
> > subsequences is also necessary and memmem() itself surprisingly brings a
> > huge improvement.
> > 
> > I'm preparing for v2 where the hashtable is split out and also used for
> > optimizing get_node_by_label(). Although the changes are not ready for
> > reviewing now, the new optimization reduces executation by another
> > 6.4%. Do you think it's a reason strong enough to keep the the code?
> 
> Probably not, unless you can convince me there's a use case where the
> performance is a pressing practical problem.

Okay, I'll keep only the memmem() change in v2.

> > Here's a summary of the changes,
> > 
> > 	Makefile.dtc |   1 +
> > 	checks.c     |   4 --
> > 	dtc-parser.y |   4 +-
> > 	dtc.c        |   4 ++
> > 	dtc.h        |  19 +++++++
> > 	flattree.c   |  68 +++++++++++++++++++------
> > 	hashtable.c  | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++
> > 	livetree.c   |  35 +++++++++++--
> > 	8 files changed, 251 insertions(+), 25 deletions(-)
> > 
> > ...
> > 
> > 
> > Best regards,
> > Yao Zi
> > 
> 
> -- 
> David Gibson (he or they)	| I'll have my music baroque, and my code
> david AT gibson.dropbear.id.au	| minimalist, thank you, not the other way
> 				| around.
> http://www.ozlabs.org/~dgibson

Thanks,
Yao Zi