On 2022-05-31 23:10, Tony Battersby wrote:
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.
No, n represents the size of the set that the algorithm is inserting
into (or removing from, searching within, etc.). Hence why constant time
is represented by O(1), i.e. not involving the variable at all.
Robin.
