pfritz

February 25, 2009

Mythbusting

Filed under: ecore,eina — pfritz @ 18:51

Today I was talking with Vincent about the memory usage of the Ecore and Eina datatypes. And he stated that Eina’s datatypes are using less memory then the counter-parts of Ecore. That wasn’t the first time that I heard about that myth, and I don’t know how it ever came off, if it was because of ignorance or if it is just a lie to promote Eina as the best stuff ever. In dubio pro reo! So let me show you that it is simply not true.

For the lists the calculation is pretty simple. The container base of Ecore_List and Ecore_DList has 4 pointers and 2 integers. That are on a 32-bit architecture, 24 bytes. The nodes of Ecore_List has 2 pointers the double linked version has 3. On 32-bit that are 8 and 12 bytes. The countainer base of Eina_List takes one integer and one pointer the nodes are taking 4 pointers. That are on 32-bit systems that are 8 and 16 bytes. If you now want to calculate the memory usage you get the formulas for Ecore_List 32 + 8n, for Ecore_DList 32 + 12n, for Eina_List 8 + 16n. And there is the special case that Eina_List is using 0 bytes if the list is empty. Indeed, Eina_List is using less memory then Ecore_Dlist, but only for lists that are shorter then 4 nodes! For large lists where the container base size is negliable it is using 33% more space.

For hashes the calculations are a bit more difficult. Ecore doesn’t use a static bucket size and Eina has a nested tree structure for collisions protection. If I understood it right, it has a tree for every hash value, those nodes are called heads, and every head has a tree for futher collisions. Since the formulars are here more complexe, I don’t want to discuss them in detail. I put them into a little c app, to actually calculate them. Since the memory usage of Eina_Hash differs depending of the quality of the hash function, I’ve calculated the best case (no collisions) and the worst case (only one hash value for every key). The real world case is some where between those two values. For bit fields I used the size of an integer, which should be at least on 32-bit architectures correct. You can find the source code here: http://mowem.de/ecore/hash.c

The results can be found here: http://mowem.de/ecore/plot1000.png http://mowem.de/ecore/plot10000.png

The red line is for Ecore, the blue for the worst case of Eina and the green line is for the best case scenario. Note: with best/worst case senario I’m talking about hash collisions and not about memory usage! So what we see is that Eina_Hash eats between 100% and 275% more memory then Ecore_Hash.

I know that there is a trade-off between memory usage and performance, but please stop pretending that Eina datatypes are using less memory then the Ecore counterparts. It’s simply not true.

Advertisements

Create a free website or blog at WordPress.com.