On Tue, Sep 16, 2014 at 11:14 AM, Marvin Humphrey <[email protected]> wrote: > On Tue, Sep 16, 2014 at 1:04 AM, Nick Wellnhofer <[email protected]> wrote: >> I'm more concerned with the waste of memory. I'd happily sacrifice some more >> cycles to find a solution that doesn't need those sparse arrays. > > I suppose there's always linear search or binary search.
I've only been skimming this thread, so perhaps I'm way off, but from afar it sounds like a little custom hash would fit your needs excellently. Memory overhead can be very low, and probably can be localized to one or a pair of cachelines. Reads of certain keys are consistently high in frequency and thus well predicted. The slowest part is hashing the key, but you could have this happen once at registration and return the result. Writes are rare, and usually happen at startup, so runtime resizes can probably be avoided. Deletions are practically never, so you don't have to worry about shrinking. Overrides are easy, and probably could be done in a way compatible with caller caching. --nate
