flattree: Optimize stringtable_insert()
PATCH RESEND 1/1 flattree: Optimize stringtable_insert()
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.
---
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(-)
flattree.c +129 -14
@@ -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 {
Signature · 1 line
2.49.0
Hi Yao,
Quoted 11 lines · 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.
This is a really good improvement!
Quoted 28 lines
- 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(-)flattree.c +0
-0
flattree.c static struct emitter asm_emitter = { · line 225
Quoted 9 lines
flattree.c +5
-1@@ -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?
flattree.c static struct emitter asm_emitter = { · line 231
Quoted 6 lines
flattree.c +6
-0+ +/* +* 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?
Quoted 73 lines
flattree.c +59
-6+ +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++) {
flattree.c static struct emitter asm_emitter = { · line 308
Quoted 10 lines
flattree.c +10
-0+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?
Quoted 16 lines
flattree.c +16
-0+} + +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;
flattree.c static struct emitter asm_emitter = { · line 334
Quoted 10 lines
flattree.c +10
-0+ +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 ?
flattree.c static struct emitter asm_emitter = { · line 340
Quoted 6 lines
flattree.c +6
-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? 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.
Quoted 77 lines
flattree.c +17
-8+ + 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 { --
Quoted 3 lines
2.49.0
Regards,
Simon
Quoted 3 lines · Simon Glass
Hi Yao,
On Sat, 12 Apr 2025 at 04:05, Yao Zi <[email protected]> wrote:
...
Quoted 8 lines
Quoted 8 lines
flattree.c +0
-0@@ -218,23 +218,134 @@ static struct emitter asm_emitter = { .property = asm_emit_property, };
Quoted 8 lines
flattree.c static struct emitter asm_emitter = { · line 225
Quoted 6 lines
flattree.c +5
-1-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.
Quoted 10 lines
flattree.c static struct emitter asm_emitter = { · line 231
Quoted 6 lines
flattree.c +6
-0+ +/* +* Must be 2^n to ensure stringtable.cap - 1 correctly masks hash into the +* index of slots +*/ +#define stringtable_initcap 256When 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.
Quoted 10 lines
Quoted 10 lines
flattree.c +10
-0+ +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; +}
...
Quoted 14 lines
Quoted 14 lines
flattree.c +14
-0+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);
Quoted 8 lines
flattree.c static struct emitter asm_emitter = { · line 308
Quoted 6 lines
flattree.c +6
-0+ + newslots[newslot] = off; + } + + strtab->cap = newcap; + strtab->slots = newslots;Does
strtab->slotsget freed here?
Thanks for catching this! It's lost here, causing some leaking, I'll fix it in v2.
Quoted 20 lines
Quoted 20 lines
flattree.c +20
-0+} + +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; +
Quoted 8 lines
flattree.c static struct emitter asm_emitter = { · line 334
Quoted 6 lines
flattree.c +6
-0+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;Quoted 8 lines
flattree.c static struct emitter asm_emitter = { · line 340
Quoted 6 lines
flattree.c +6
-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.
Quoted 4 lines
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.
Quoted 6 lines
Quoted 6 lines
flattree.c +6
-0+ + strtab->len++; + +return *slot; +} +
...
Quoted 2 lines
Regards,
Simon
Regards,
Yao Zi
Quoted 4 lines · 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.
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.
Quoted 5 lines
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.
Quoted 4 lines
- 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.
Quoted 228 lines
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(-)flattree.c +129
-14@@ -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 {
Signature · 4 lines
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
Quoted 21 lines · David Gibson
Quoted 4 lines · 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.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.
Quoted 5 lines
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.
Quoted 7 lines
Quoted 4 lines
- 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(-)
...
Quoted 5 lines
Signature · 4 lines
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
Quoted 35 lines · Yao Zi
Quoted 21 lines · David Gibson
Quoted 4 lines · 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.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.
Quoted 5 lines
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.
Quoted 7 lines
Quoted 4 lines
- 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.
Quoted 4 lines
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.
Quoted 18 lines
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
Signature · 4 lines
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
Quoted 36 lines · David Gibson
Quoted 35 lines · Yao Zi
Quoted 21 lines · David Gibson
Quoted 4 lines · 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.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.
Quoted 5 lines
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.
Quoted 7 lines
Quoted 4 lines
- 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.
Quoted 7 lines
Quoted 4 lines
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.
Quoted 12 lines
Quoted 12 lines
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(-)
Quoted 12 lines
Quoted 6 lines
...
Best regards,
Yao ZiSignature · 4 lines
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