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

Hi Yao,

On Sat, 12 Apr 2025 at 04:05, Yao Zi <[email protected]> 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 <[email protected]>
> ---
>
> 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