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

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