JOAQUIN LOPEZ MU?Z wrote:
----- Mensaje original ----- De: Maxim Yegorushkin <maxim.yegorushkin@gmail.com> 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.