Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.


#5 uthash performance is choppy with item number

Niall Douglas

I recently did a scaling performance analysis comparing my bitwise tries implementation with red black trees and uthash. If you look at the graphs on you'll see how each algorithm scales according to N.

uthash shows very distinct choppiness in scaling - if you test std::unordered_set<> from C++ in an identical framework you get a smooth, flat O(1) line for all operations as one ought to.

In particular you shouldn't be seeing O(1/log N) insert scaling nor O(log N) remove scaling between the bucket expansions as uthash is apparently demonstrating. This suggests that your bucket indexation routine has a bug in it which is introducing the partial log N behaviour, perhaps it isn't making full use of all the buckets for a given hash key?



  • Troy Hanson
    Troy Hanson

    Interesting, my first question is whether the key domain on which this particular graph is based is a good match for the default hash function. If its not, ideal% would tend low and your operations get worse and worse than constant time. In that kind of scenario the solution might be as simple as switching to a different hash function. Or maybe there is something deeper. I would need to have the code you used to generate the data to analyze the ideal% (or you could use hashscan or keystats as described in the documentation).

    Incidentally I don't routinely use SourceForge so email is preferable to opening tickets. Thanks.