Messages in this thread | | | From | (Eric W. Biederman) | Date | Thu, 29 Mar 2018 13:52:25 -0500 | Subject | Re: [RFC][PATCH] ipc: Remove IPCMNI |
| |
Manfred Spraul <manfred@colorfullife.com> writes:
> Hello Mathew, > > On 03/29/2018 12:56 PM, Matthew Wilcox wrote: >> 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'm concerned about the up to 6 branches. > But this is just guessing, we need a test with a realistic workload.
Yes.
My primary purpose with the patch was to show that the issues with the current limits could be resolved in a straght forward manner. I really don't know if idrs are the appropriate data structure. It is possible rbtrees are a better fit.
I think my algorithm I proposed for generating identifiers is as likely as any to be a good one. It does need testing on a wide variety of applications to see what applications actually care about and for that I think my proposed patch is more than sufficient.
By not keeping a generation counters in the slots themselves linux already differs substantially from traditional implementations.
Doing something to free us from using a fixed number of bits for the counter and a fixed number of bits to encode the slot we can support much larger use of this API.
Eric
| |