Re: [PATCH v5 0/3] iommu/iova: convert from rbtree to maple tree

[Jörg Rödel]

Hi Ankit,

On Fri, Oct 09, 2026 at 08:45:29AM +0000, Ankit Soni wrote:
> Summary:
> 
> alloc_iova() is O(log n) in practice, on two CPUs and by two independent
> tools. The series costs about 2x on a near-empty tree and wins by orders
> of magnitude on a deep one, which is the trade you describe. Memory is
> the same within noise below 786k live IOVAs and a third less at 12.58M. 
> The costs are confined to microbenchmarks on near-empty trees, No regression
> in any real workload.

Thanks for providing these numbers, this is very helpful.

-Joerg