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 Shall I spin a new version of this one to mention the upstream commit? Best regards, Alexey
