| H A D | nvlist.c | 89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
89d5cbb8 Fri Jun 11 15:35:36 GMT 2021 Mariusz Zaborski <oshogbo@FreeBSD.org> 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
|