Messages in this thread | | | Date | Tue, 31 May 2022 15:54:23 -0600 | From | Keith Busch <> | Subject | Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free |
| |
On Tue, May 31, 2022 at 02:23:44PM -0400, Tony Battersby wrote: > dma_pool_free() scales poorly when the pool contains many pages because > pool_find_page() does a linear scan of all allocated pages. Improve its > scalability by replacing the linear scan with a red-black tree lookup. > In big O notation, this improves the algorithm from O(n^2) to O(n * log n).
The improvement should say O(n) to O(log n), right?
| |