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

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

[-- Attachment #1: Type: text/plain, Size: 2949 bytes --]

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.

> 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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]