CODEWITHSUNDEEP
linuxdata-structureslinux-kernelramvirtual-memory
user855
user855

Reputation: 19948

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

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?

Upvotes: 10

Views: 781

Answers (3)

Jason
Jason

Reputation: 3917

The first thing you need to do is figure out the data you need to represent in graphical format. The memory layout in Poul-Henning Kamp's figures are both the pointer structure, and contiguous virtual memory pages. The former can easily be displayed using a debugging tool like ddd. The latter takes a bit more effort, and there are more ways to accomplish it.

A few ideas...

  • Write a function to traverse the data structure and print values, compile as scaffold code and run
  • Add function and call it from a debugger, such as gdb
  • Write a script to be called from a debugger

Another possibility nobody mentioned yet, would be reading through the specification for the language you're writing the code in. This should generally let you determine the memory layout of the structures in the actual compiled code (C/C++, etc...), neglecting compiler optimization. This can be altered by telling the compiler to lay out the data structures in non-default ways though (alignas, __attribute__(aligned), etc...). You would still need to consider how the memory is allocated from the heap and the operating system.

However, once you have the relevant values, you should be able to use any software you like to convert the data into a graphical format (graphviz, etc...).

Upvotes: 1

moorray
moorray

Reputation: 222

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

Upvotes: 3

user3666197
user3666197

Reputation: 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 )

Upvotes: 3

Related Questions