On Thu, Mar 29, 2018 at 10:47:45AM +0200, Manfred Spraul wrote: > > > > > > This can be implemented trivially with the current code > > > > > > using idr_alloc_cyclic. > > Is there a performance impact? > 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 radix tree uses a branching factor of 64 entries (6 bits) per level. 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. I have plans to make the representation more efficient and bring the specific case of one element with a high ID down to one pointer dereference and 2 cachelines, but I have not yet had time to implement those plans. >From a memory consumption point of view, 6 layers of tree will consume 6/7 of a page on a 64-bit x86 kernel. I'm aiming to bring that down to 1/7 of a page. We get 7 radix_tree_nodes per 4kB page. (The old IDR tree had 256 entries per level which would have taken only four layers to get us to 31 bits, but the cost was getting only 3 layers per 8kB order-1 page, so we'd've taken 2 + 2/3 page to accomplish the same goal).
