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

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