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

[David Gibson <david@gibson.dropbear.id.au>]

[-- 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 --]