[systemd-devel] [PATCH 21/26] hashmap: rewrite the implementation

[Michal Schmidt]

On 10/20/2014 08:42 PM, Lennart Poettering wrote:
> On Thu, 16.10.14 09:50, Michal Schmidt (mschmidt at redhat.com) wrote:
>> +enum {
>> +        HASHMAP_TYPE_PLAIN,
>> +        HASHMAP_TYPE_LINKED,
>> +        HASHMAP_TYPE_SET,
>> +        __HASHMAP_TYPE_COUNT
>> +};
> 
> Why is this enum anonymous? Wouldn't it be nicer to give it a name? We
> only use it internally only anyway...
> 
> So far we called the final counting entry of such enums _FOOBAR_MAX,
> not __FOOBAR_COUNT, please stick to this naming scheme... (also iirc
> the C standard reserves the double "_" prefix for the language
> itself. The kernel ignores that C standard issue so far, but we should
> probably honour it.

OK, I'll improve these.
 
>> +        uint8_t type:2;             /* HASHMAP_TYPE_* */
> 
> Should probably be a named enum (see above)
> [...]
>> +        uint8_t has_indirect:1;     /* whether indirect storage is
>> used */
> 
> Should really be a "bool", no?

OK.
 
>> +static struct HashmapBase *__hashmap_new(const struct hash_ops *hash_ops, uint8_t type  HASHMAP_DEBUG_PARAMS) {
>> +        HashmapBase *h;
>> +
>> +        h = malloc0(all_hashmap_sizes[type]);
>> +        if (!h)
>> +                return NULL;
>> +
> 
> Hmm, a malloc() for each hashmap we allocate? Isn#t that prohibitively
> expensive given how slow malloc() is? We have soo many hashmaps!

Is it really that slow? A small test program that does malloc(48) ten
million times (no freeing) runs for about 0.3 seconds on my laptop.
systemd allocates about 2000 hashmaps here. So these would take about
60 microseconds to malloc. Maybe the test program has it too easy due
to having to deal with no heap fragmentation. But then I'd expect the
allocations this small to be helped by glibc's fastbins...
I guess I'll take some measurements under qemu with no KVM :-)

>> +Set *_set_new(const struct hash_ops *hash_ops  HASHMAP_DEBUG_PARAMS) {
>> +        return (Set*)           __hashmap_new(hash_ops, HASHMAP_TYPE_SET  HASHMAP_DEBUG_PASS_ARGS);
>> +}
> 
> Not liking the double underscores... I know this is kernel style, but it's still in conflict with ISO C...
> 
> Can we maybe name this internal_xyz or so?

Will do so.

Michal