On 5/31/22 17:54, Keith Busch wrote: > 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? That would be the improvement for a single call to dma_pool_alloc or dma_pool_free, but I was going with the improvement for "n" calls instead, which is consistent with the improvement for the example in the cover letter for mpt3sas. I would have to look up the convention to be sure of the proper notation in a situation like this, but I usually think "inserting N items takes N^2 time"; to me it makes less sense to say "inserting 1 item takes N time", because the N seems to come out of nowhere. Tony
