On Thu, Mar 29, 2018 at 10:47:45AM +0200, Manfred Spraul wrote:I'm concerned about the up to 6 branches.
The radix tree uses a branching factor of 64 entries (6 bits) per level.Is there a performance impact?This can be implemented trivially with the current code
using idr_alloc_cyclic.
Right now, the idr tree is only large if there are lots of objects.
What happens if we have only 1 object, with id=INT_MAX-1?
The maximum ID is 31 bits (positive signed 32-bit integer). So the
worst case for a single object is 6 pointer dereferences to find the
object anywhere in the range (INT_MAX/2 - INT_MAX]. That will read 12
cachelines. If we were to constrain ourselves to a maximum of INT_MAX/2
(30 bits), we'd reduce that to 5 pointer dereferences and 10 cachelines.