How to find out memory layout of your data structure implementation on Linux 64bit machine

Question

In this article, http://cacm.acm.org/magazines/2010/7/95061-youre-doing-it-wrong/fulltext

The author talks about the memory layouts of 2 data structures - The Binary Heap and the B-Heap and compares how one has better memory layout than the other (figures 5 and 6).

I want to get hands on experience on this. I have an implementation of a N-Ary Tree and I want to find out the memory layout of my data structure. What is the best way to come up with a memory layout like the one in the article?

Secondly, I think it is easier to identify the memory layout if it is an array based implementation. If the implementation of a Tree uses pointers then what Tools do we have or what kind of approach is required to map it's memory layout?

Answer 1

Design a code for a data-structure to test

Pre-fill the data-structure under test with significant-values ( 0x00000000, 0x01111111, ... ) highlighting the layout borders & data belonging to data-structure elements

Use debugging tools to view actual live-memory content & layout that the coded data-structure element-under-test uses in-vivo

( be systematic & patient )

Answer 2

Perhaps just traversing the data structure to print element addresses (and sizes if they vary) would give you enough information to feed to for instance graphviz? I'm not sure why did you include the linux-kernel tag. Basic virtual memory mapping happens at page granularity (ignoring huge pages here) so physical vs virtual address don't matter. You can easily do your tests in user space.

I would proceed as follows:

1. place calls to dump your N-ary trees in the code OR use a GDB script to do it
2. write a script in your favourite scripting language to group objects into pages (masking lower 12 bits of addresses out gives page id), calculate statistics, see if objects span multiple pages, do whatever you want; output graphviz description file
3. run graphviz to enjoy the vizualisation