Date: Mon, 14 Jun 2021 14:09:57 +0200 From: "Kristof Provost" <kristof@sigsegv.be> To: "Mariusz Zaborski" <oshogbo@FreeBSD.org> Cc: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: Re: git: 89d5cbb82294 - main - libnv: optimize nvlist size calculation Message-ID: <4EF64072-D94B-46FB-9AE9-321936DEEA7C@sigsegv.be> In-Reply-To: <202106111551.15BFpp8j055403@gitrepo.freebsd.org> References: <202106111551.15BFpp8j055403@gitrepo.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 11 Jun 2021, at 17:51, Mariusz Zaborski wrote: > The branch main has been updated by oshogbo: > > URL: = > https://cgit.FreeBSD.org/src/commit/?id=3D89d5cbb82294c8624e66f920d5035= 3057ccab14b > > commit 89d5cbb82294c8624e66f920d50353057ccab14b > Author: Mariusz Zaborski <oshogbo@FreeBSD.org> > AuthorDate: 2021-06-11 15:35:36 +0000 > Commit: Mariusz Zaborski <oshogbo@FreeBSD.org> > CommitDate: 2021-06-11 15:51:29 +0000 > > libnv: optimize nvlist size calculation > > If we had a multiple nvlist, during nvlist_pack, we calculated the = > size > of every nvlist separately. For example, if we had a nvlist with = > three > nodes each containing another (A contains B, and B contains C), we = > first > calculated the size of nvlist A (which contains B, C), then we = > calculate > the size of B (which contains C, notice that we already did the > calculation of B, when we calculate A), and finally C. This means = > that > this calculation was O(N!). This was done because each time we = > pack > nvlist, we have to put its size in the header > (the separate header for A, B, and C). > > To not break the ABI and to reduce the complexity of nvlist_size, > instead of calculating the nvlist size when requested, > we track the size of each nvlist. > > Reported by: pjd, kp > Tested by: kp Thanks for this! Do you object to this being MFCd in a few days? Thanks, Kristof
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4EF64072-D94B-46FB-9AE9-321936DEEA7C>