[ovs-dev] [hmap 0/7] Reduce memory requirements, simplify code

Ben Pfaff blp at nicira.com
Mon Jul 19 14:05:32 PDT 2010

It has occurred to me recently that the "port_array" data structure
has a significant memory cost compared to "hmap".  If a port_array
has only one element in use, then it consumes this amount of memory:

	32 pointers for level 1
	32 pointers for a single level 2
	64 pointers for a single level 3

or (32 + 32 + 64) * 4 == 512 bytes of memory on a 32-bit system.
Even a completely empty port_array takes up 32 * 4 == 128 bytes
of memory.

On the other hand, an empty hmap, or one with 1 or 2 elements in
it, takes up only 16 bytes of memory.

So I conclude that it's better to use an hmap unless we know that
we need the advantage of a "port_array" (primarily, iteration in
numerical order).  This series of commits makes a number of such
conversions.  It leaves in place the single use where in-order
iteration makes some sense, in pinsched.c.  Even there, it would
probably make more sense to use a different data structure, but
conversion is slightly harder than for the other cases.

The final two patches in this series are a little different.
They make users of CONTAINER_OF, such as HMAP_FOR_EACH and
LIST_FOR_EACH, simpler by allowing them to drop the argument that
specifies the encapsulating structure type; instead, the type is
inferred from the type of the variable used for iteration.
Somehow, I had never until now realized that this was possible.

More information about the dev mailing list