Occupied memory on a recursive call

Question

I've started to learn about data structures at school and I have an homework where I have to implement an Binary Search Tree and tell the memory occupied by the data structures.

I've created my BST and I believe all is working as expected but I don't have a clue how to calculate the memory used.

This is the code I've created for the data structure and the code for inserting:

class Node {

    int key, totalValue;
    public Node left;
    public Node right;

    public Node (int key, int totalValue) {
        this.key= key;
        this.totalValue = totalValue;
        this.left = null;
        this.right = null;
    }

    public int getkey() {
        return key;
    }

    public int getTotalValue() {
        return totalValue;
    }
}

class Tree {

    private Node root;

    public Tree() {
        this.root = null;
    }

    public Node getRoot() {
        return this.root;
    }

    public void setRoot(Node node) {
        this.root = node;
    }
}

And this is the code for inserting:

private static void addNode(Node node, Node tempNode) {

    if (tempNode.getkey() < node.getkey()) {
        if (node.left == null) {
            node.left = tempNode;
        } else {
            addNode(node.left, tempNode);
        }
    } else if (tempNode.getkey() > node.getkey()){
        if (node.right == null) {
            node.right = tempNode;
        } else {
            addNode(node.right, tempNode);
        }
    }else{
        node.totalValue += tempNode.getTotalValue();
    }
}

I know that for each node I need 8 bytes for the 2 int, but I don't know how much each pointer occupies.

Second question. Imagine I insert 25000 entries from 10000 keys. Each insertion will be used recursively until the new node finds it's "position". How can I calculate the memory occupied?

Do you want to know the amount of memory occupied by the data structure solely (heap usage) or do you also need to know the amount of memory used to do the insertion (stack usage)? — Mike Samuel, Apr 11 '13 at 18:34
[What is the memory consumption of an object in java?](http://stackoverflow.com/questions/258120/what-is-the-memory-consumption-of-an-object-in-java) — Mike Samuel, Apr 11 '13 at 18:35
@MikeSamuel Both. I've followed the link you provided but unfortunately I didn't understand how much each pointer will occupy (8 bytes????) so I can do the amount for each node — Favolas, Apr 11 '13 at 18:40
@Favolas - Despite the really annoying downvote from Sam I am, I'd definitely encourage you to look at the links I gave below to see exactly what memory your code is actually allocating. IMHO... PS: I believe the size will vary from platform to platform: 32 bit vs 64-bit vs ["compressed OOPs"](http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-enhancements-7.html) — paulsm4, Apr 11 '13 at 18:44
@Favolas, the memory overhead of a reference depends on the architecture since Java references are typically implemented as pointers and pointers vary in size depending on the architecture. Often pointers are 32b or 64b on ["32-bit architectures"](http://en.wikipedia.org/wiki/32-bit#Architecture) and "64-bit architectures" respectively, but many other memory models use different pointer sizes and some instruction sets distinguish between near and far pointers. — Mike Samuel, Apr 11 '13 at 18:51

score 1 · Accepted Answer · answered Apr 11 '13 at 18:36

The basic concept behind the recursive method would be

GetMemoryUsed(node)
{

    if(node is leaf)
        return (node.localMemory)

    return(GetMemoryUsed(node.left) + GetMemoryUsed(node.right) + node.localMemory);
}

where node.localMemory is just the amount of memory that the specific node uses (not counting the child nodes)

score 0 · Answer 2 · answered Apr 11 '13 at 18:37

0

As far as getting precise numbers, here are a couple of tools you might be interested in:

Java Instrumentation

JMap Memory Map

answered Apr 11 '13 at 18:37

paulsm4

114,292
17
138
190

you can at least describe what the tools do – Sam I am says Reinstate Monica Apr 11 '13 at 18:38
@paulsm4 Thanks. Will take a look into that but I would like to know using some kind of mathematical formula – Favolas Apr 11 '13 at 18:47
2

The mathematically precise answer is "it depends". One would think you could get a nice, deterministic answer from simple arithmetic. And, in your case, maybe you *can*. Then again, other variables might affect your results. In addition to *computing* the answer, you should also empirically *look* at your actual allocation. IMHO... – paulsm4 Apr 11 '13 at 18:49
@paulsm4 Thanks. Will see the tools – Favolas Apr 11 '13 at 19:54
I don't know why this got downvoted. Even if you know how fields tend to be laid out on a particular JVM and compute it mathematically, alignment is tricky so you'd be wise to empirically check your calculations. – Mike Samuel Apr 11 '13 at 22:03

Occupied memory on a recursive call

2 Answers2