Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

Hi Alexey,

On Sat, 8 Aug 2026 at 03:09, Alexey Charkov <[email protected]> wrote:
>
> Hi Simon,
>
> On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <[email protected]> wrote:
> >
> > Hi Alexey,
> >
> > On 2026-08-05T14:47:38, Alexey Charkov <[email protected]> wrote:
> > > pylibfdt: Grow the FdtSw buffer geometrically
> > >
> > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > growing by a fixed amount makes building a tree cost time quadratic in
> > > its size. This is especially painful when assembling larger FIT images with
> > > binman, as it assembles the image with the data inline.
> > >
> > > Grow by at least as much as the tree already holds, which is what variable
> > > sized arrays usually do specifically to avoid such excessive copying.
> > >
> > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > produced are byte-identical and the binman and dtoc test results are
> > > unaffected.
> > >
> > > Signed-off-by: Alexey Charkov <[email protected]>
> > >
> > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > >  1 file changed, 6 insertions(+), 2 deletions(-)
> >
> > This is a _shipped file from upstream dtc, so any change here will be
> > reverted on the next resync. Please can you send this to the dtc
> > project first (see https://github.com/dgibson/dtc) and reference the
> > upstream commit / PR in the U-Boot commit message, similar to how
> > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > will be lost.
> >
> > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> >
> > Logic looks correct - doubling gives amortised O(n) total copying, and
> > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > Nice measurement in the commit message too.
>
> Merged upstream: https://github.com/dgibson/dtc/pull/189

Nice, that was quick!

>
> Shall I spin a new version of this one to mention the upstream commit?

Reviewed-by: Simon Glass <[email protected]>

Regards,
SImon