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. Regards, Simon
