[PATCH] scripts/dtc/flattree.c: stringtable_insert optimization

[PATCH] scripts/dtc/flattree.c: stringtable_insert optimization

[Alex Tran]

Increment string by string instead of character by character.

Signed-off-by: Alex Tran <alex.t.tran@gmail.com>
---
 scripts/dtc/flattree.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/scripts/dtc/flattree.c b/scripts/dtc/flattree.c
index 1bcd8089c5b9..156ca5da89b2 100644
--- a/scripts/dtc/flattree.c
+++ b/scripts/dtc/flattree.c
@@ -222,9 +222,7 @@ static int stringtable_insert(struct data *d, const char *str)
 {
 	unsigned int i;
 
-	/* FIXME: do this more efficiently? */
-
-	for (i = 0; i < d->len; i++) {
+	for (i = 0; i < d->len; i += strlen(d->val + i) + 1) {
 		if (streq(str, d->val + i))
 			return i;
 	}
-- 
2.50.1

Re: [PATCH] scripts/dtc/flattree.c: stringtable_insert optimization

[Rob Herring]

On Fri, Aug 22, 2025 at 1:04 AM Alex Tran <alex.t.tran@gmail.com> wrote:
>
> Increment string by string instead of character by character.

Why? Are you doing something where this provides measurable improvement?

>
> Signed-off-by: Alex Tran <alex.t.tran@gmail.com>
> ---
>  scripts/dtc/flattree.c | 4 +---
>  1 file changed, 1 insertion(+), 3 deletions(-)

This is a copy of upstream dtc. If you want to make changes to dtc,
you have to submit them upstream.

>
> diff --git a/scripts/dtc/flattree.c b/scripts/dtc/flattree.c
> index 1bcd8089c5b9..156ca5da89b2 100644
> --- a/scripts/dtc/flattree.c
> +++ b/scripts/dtc/flattree.c
> @@ -222,9 +222,7 @@ static int stringtable_insert(struct data *d, const char *str)
>  {
>         unsigned int i;
>
> -       /* FIXME: do this more efficiently? */
> -
> -       for (i = 0; i < d->len; i++) {
> +       for (i = 0; i < d->len; i += strlen(d->val + i) + 1) {

This isn't equivalent. If 'd' was 'foobar' and 'str' was 'bar', then
before we'd match. Now you don't.

>                 if (streq(str, d->val + i))
>                         return i;
>         }
> --
> 2.50.1
>

Re: [PATCH] scripts/dtc/flattree.c: stringtable_insert optimization

[Alex Tran]

I didn't take into account the substring cases. Originally I thought
that incrementing by each string in the table would be more efficient
than by each character to reduce iterations but now with checking for
substrings it is more difficult. I could use strstr(haystack, needle)
to detect substrings and get the position on top of the changes I made
but the performance boost would be negligible. I'll drop this patch.

Thanks for the review.

On Fri, Aug 22, 2025 at 6:34 AM Rob Herring <robh@kernel.org> wrote:
>
> On Fri, Aug 22, 2025 at 1:04 AM Alex Tran <alex.t.tran@gmail.com> wrote:
> >
> > Increment string by string instead of character by character.
>
> Why? Are you doing something where this provides measurable improvement?
>
> >
> > Signed-off-by: Alex Tran <alex.t.tran@gmail.com>
> > ---
> >  scripts/dtc/flattree.c | 4 +---
> >  1 file changed, 1 insertion(+), 3 deletions(-)
>
> This is a copy of upstream dtc. If you want to make changes to dtc,
> you have to submit them upstream.
>
> >
> > diff --git a/scripts/dtc/flattree.c b/scripts/dtc/flattree.c
> > index 1bcd8089c5b9..156ca5da89b2 100644
> > --- a/scripts/dtc/flattree.c
> > +++ b/scripts/dtc/flattree.c
> > @@ -222,9 +222,7 @@ static int stringtable_insert(struct data *d, const char *str)
> >  {
> >         unsigned int i;
> >
> > -       /* FIXME: do this more efficiently? */
> > -
> > -       for (i = 0; i < d->len; i++) {
> > +       for (i = 0; i < d->len; i += strlen(d->val + i) + 1) {
>
> This isn't equivalent. If 'd' was 'foobar' and 'str' was 'bar', then
> before we'd match. Now you don't.
>
> >                 if (streq(str, d->val + i))
> >                         return i;
> >         }
> > --
> > 2.50.1
> >



-- 
Alex Tran
alex.t.tran@gmail.com | 408-406-2417