Re: [boost] [multi_index] benchmarking

From: Maxim Yegorushkin (maxim.yegorushkin_at_[hidden])
Date: 2006-05-31 03:16:16

JOAQUIN LOPEZ MU?Z wrote:
> ----- Mensaje original -----
> De: Maxim Yegorushkin <maxim.yegorushkin_at_[hidden]>
> Fecha: Martes, Mayo 30, 2006 10:25 pm
> Asunto: Re: [boost] [multi_index] benchmarking
> 
>> Darren Cook wrote:
>>>> Here are results for cvs head version with your modification, 
>> which show that 
>>>> your analysis was correct:
>>> It would be interesting to see how your results compare to Google's
>>> (open source) hash map:
>>>   http://goog-sparsehash.sourceforge.net/
>>>   http://goog-sparsehash.sourceforge.net/doc/performance.html
>>>
>>> I've not used them but they seem to give some good improvements 
>> (memory> or speed, but not both) over std_hash and std_map.
>>
>> Surprisingly google::dense_hash_set often outperforms all other 
>> containers in both speed and memory usage.
> [...]
>> 99997 elements; 10 iterations
> [...]
>> memory test (lower is better)
>> gs_hash   [ 21.64%] OOOOOOOO 432760 bytes
>> gd_hash   [ 52.43%] OOOOOOOOOOOOOOOOOOOO 1048576 bytes
>> std_hash  [ 61.58%] OOOOOOOOOOOOOOOOOOOOOOOO 1231568 bytes
>> ext_hash  [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586428 bytes
>> mi_hash   [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586440 bytes
>> mi_set    [ 80.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1599968 bytes
>> std_set   [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 
>> 1999940 bytes
> 
> Hello Maxim, gd_hash is expected to be faster than other hash
> containers, but in general it occupies more memory --only that
> your test is particularly favorable to gd_hash, let me explain:

[]

> That is, R(n) grows as n*(C+sizeof(element)) with C a
> constant, while D(n) has the form K*n*sizeof(element)
> with K always >=2. Hence, when sizeof(element) is
> sufficiently large gd_hash takes nearly twice the space
> as a regular hash container.

Thank you for the illuminating explanation.