33

While I was thinking over the memory usage of various types, I started to become a bit confused of how Java utilizes memory for integers when passed to a method.

Say, I had the following code:

public static void main (String[] args){
     int i = 4;
     addUp(i);
}

public static int addUp(int i){
     if(i == 0) return 0;
     else return addUp(i - 1);         
}

In this following example, I am wondering if my following logic was correct:

  • I have made a memory initially for integer i = 4. Then I pass it to a method. However, since primitives are not pointed in Java, in the addUp(i == 4), I create another integer i = 4. Then afterwards, there is another addUp(i == 3), addUp(i == 2), addUp(i == 1), addUp(i == 0) in which each time, since the value is not pointed, a new i value is allocated in the memory.
  • Then for a single "int i" value, I have used 6 integer value memories.

However, if I were to always pass it through an array:

public static void main (String[] args){
     int[] i = {4};
     // int tempI = i[0];
     addUp(i);
}

public static int addUp(int[] i){
     if(i[0] == 0) return 0;
     else return addUp(i[0] = i[0] - 1);         
}

- Since I create an integer array of size 1 and then pass that to addUp which will again be passed for addUp(i[0] == 3), addUp(i[0] == 2), addUp(i[0] == 1), addUp(i[0] == 0), I have only had to use 1 integer array memory space and hence far more cost efficient. In addition, if I were to make a int value beforehand to store the initial value of i[0], I still have my "original" value.

Then this leads me to the question, why do people pass primitives like int in Java methods? Isn't it far more memory efficient to just pass the array values of those primitives? Or is the first example somehow still just O(1) memory?

And on top of this question, I just wonder the memory differences of using int[] and int especially for a size of 1. Thank you in advance. I was simply wondering being more memory efficient with Java and this came to my head.

Thanks for all the answers! I'm just now quickly wondering if I were to "analyze" big-oh memory of each code, would they both be considered O(1) or would that be wrong to assume?

Improve this question
13
  • 16
    "why do people pass primitives like int in Java methods?" Because Java is a language which places readable, maintainable code over highly efficient gibberish. Commented Aug 8, 2017 at 14:45
  • 5
    As an aside, of course when analyzing recursive functions you should count the size of the implicit stack in the asymptotic memory usage. Whether you assume tail calls or not is an interesting consideration there.. Commented Aug 8, 2017 at 14:51
  • 14
    @Nathan that is only true for the Integer wrapper class, not a primitive int. Commented Aug 8, 2017 at 15:25
  • 3
    @Nathan all ints from value -2^31 to +2^31-1 are behaving exactly the same way. Nothing special about values up to 127. You must be thinking about Integer rather than int. Commented Aug 8, 2017 at 15:29
  • 7
    Both approaches use O(n) stack memory because both approaches use a parameter (for the Big-O-notation it doesn't matter whether the parameter is an int that needs 4 bytes or a reference to the int array that is either 4 bytes or 8 bytes) Commented Aug 8, 2017 at 15:34

7 Answers 7

Reset to default
56

What you are missing here: the int values in your example go on the stack, not on the heap.

And it is much less overhead to deal with fixed size primitive values existing on the stack - compared to objects on the heap!

In other words: using a "pointer" means that you have to create a new object on the heap. All objects live on the heap; there is no stack for arrays! And objects becomes subject to garbage collection immediately after you stopped using them. Stacks on the other hand come and go as you invoke methods!

Beyond that: keep in mind that the abstractions that programming languages provide to us are created to help us writing code that is easy to read, understand and maintain. Your approach is basically to do some sort of fine tuning that leads to more complicated code. And that is not how Java solves such problems.

Meaning: with Java, the real "performance magic" happens at runtime, when the just-in-time compiler kicks in! You see, the JIT can inline calls to small methods when the method is invoked "often enough". And then it becomes even more important to keep data "close" together. As in: when data lives on the heap, you might have to access memory to get a value. Whereas items living on the stack - might still be "close" (as in: in the processor cache). So your little idea to optimize memory usage could actually slow down program execution by orders of magnitude. Because even today, there are orders of magnitude between accessing the processor cache and reading main memory.

Long story short: avoid getting into such "micro-tuning" for either performance or memory usage: the JVM is optimized for the "normal, typical" use cases. Your attempts to introduce clever work-arounds can therefore easily result in "less good" results.

So - when you worry about performance: do what everybody else is doing. And if you one really care - then learn how the JVM works. As it turns out that even my knowledge is slightly outdated - as the comments imply that a JIT can inline objects on the stack. In that sense: focus on writing clean, elegant code that solves the problem in straight forward way!

Finally: this is subject to change at some point. There are ideas to introduce true value value objects to java. Which basically live on the stack, not the heap. But don't expect that to happen before Java10. Or 11. Or ... (I think this would be relevant here).

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

Thanks. Btw, I know this sounds dumb and elementary but if someone was to ask for the big oh memory space of both, would both be considered O(1) at end of day?
There are no dump questions. Only dumb people ;-) ... honestly; I am out of my wits regarding that question - simply because it is too long ago since I had to compute BigO for memory whilst distinguishing between stack and heap. In other words: I do not recall the exact rules ... and thus I respectfully leave that aspect for somebody else to answer on.
It muddies the water a bit, but a modern JIT can actually do escape analysis and allocate objects on the stack (rather than on the heap) if it can prove that the object's lifetime will never extend beyond the stack frame. So even the example code in the question, if it were identified as a hotspot, would likely be JIT-compiled into machine code that kept the values on the stack regardless.
@CortAmmon: "decently clever" compilers seem to be harder to do in Java. AFAIK, Sun's JVM (and OpenJDK's) still doesn't do TCO (apparently IBM's JVM does softwareengineering.stackexchange.com/questions/157684/…). Java security model involves checking whether a given caller has permissions to call a given callee. Also, altering stack traces is a potential problem for TCO.
@Daniel Pryden: there’s more to it than just allocating an object on the stack. A purely local object may get decomposed into its variables, which are then treated like like other local variables, i.e. redundant fields may get collapsed or unused fields get removed, up to the point that an actually obsolete local object gets removed entirely.
|
18

Several things:

First thing will be splitting hairs, but when you pass an int in java you are allocating 4 bytes onto the stack, and when you pass an array (because it is a reference) you are actually allocating 8 bytes (assuming an x64 architecture) onto the stack, plus the additional 4 bytes that store the int into the heap.

More importantly, the data that lives in the array is allocated into the heap, whereas the reference to the array itself is allocated onto the stack, when passing an integer there is no heap allocation required the primitive is only allocated into the stack. Over time reducing the heap allocations will mean that the garbage collector will have fewer things to clean up. Whereas the cleanup of stack-frames is trivial and doesn't require additional processing.

However, this is all moot (imho) because in practice when you have complicated collections of variables and objects you are likely going to end up grouping them together into a class. In general, you should be writing to promote readability and maintainability rather than trying to squeeze every last drop of performance out of the JVM. The JVM is pretty quick as it is, and there is always Moore's Law as a backstop.

It would be difficult to analyze the the Big-O for each because in order to get a true picture you would have to factor in the behavior of the garbage collector and that behavior is highly dependent on both the JVM itself and any runtime (JIT) optimizations that the JVM has made to your code.

Please remember Donald Knuth's wise words that "premature optimization is the root of all evil"

Write code that avoids micro-tuning, code that promotes readability and maintainability will fare better over the long run.

Improve this answer

2 Comments

A couple of hair-splitting points on your hair-splitting: 1. with compressed OOPs (which is now the default AFAIK) a pointer to an array may only occupy 4 bytes, even on a 64-bit system; 2. young generation allocations (of objects that don't have finalizers) are collected en masse and can actually be about as cheap as stack allocations. The overhead of GC really only kicks in if an object needs to be copied (especially if it is copied enough times to move out of a scavenger space and into the tenured generation).
Agree, but all of that is to reinforce the point that we shouldn't be worrying about it, and should just let the JVM/JIT work it out (since all of those points are valid, but heavily JVM implementation dependent) Instead should just focus on writing clear and maintainable code and let the JVM do what it does best.
10

If your assumption is that arguments passed to functions necessarily consume memory (which is false by the way), then in your second example that passes an array, a copy of the reference to the array is made. That reference may actually be larger than an int, it's unlikely to be smaller.

Improve this answer

3 Comments

arguments passed to functions necessarily consume memory. This is how processors work. Am I missing something?
@Jack arguments may be passed in registers, which is not the norm for x86 code but it is for x64 and ARM. Of course only up to some limit.
@Jack - furthermore, any important Java code is going to be compiled, perhaps several times, and the final results will be heavily inlined and there may be "zero" memory use for many arguments, because they are passed in registers, or simply because the function call itself has totally disappeared and there is no passing at all. In that way, it isn't really meaningful to talk about the memory use of arguments, in a general way. You can usually talk about the memory use of objects on the heap (but even that is subject to various optimizations), but the stack not so much.
7

Whether these methods take O(1) or O(N) depends on the compiler. (Here N is the value of i or i[0], depending.) If the compiler uses tail-recursion optimization then the stack space for the parameters, local variables, and return address can be reused and the implementation will then be O(1) for space. Absent tail-recursion optimization the space complexity is the same as the time complexity, O(N).

Basically tail-recursion optimization amounts (in this case) to the compiler rewriting your code as

public static int addUp(int i){
     while(i != 0) i = i-1 ;
     return 0;        
}

or

public static int addUp(int[] i){
     while(i[0] != 0) i[0] = i[0] - 1 ;
     return 0 ;
}

A good optimizer might further optimize away the loops.

As far as I know, no Java compilers implement tail-recursion optimization at present, but there is no technical reason that it can't be done in many cases.

Improve this answer

1 Comment

Strictly speaking I should be using big-Theta instead of big-Oh since we are discussing the exact complexity, not an upper-bound on complexity.
5

Actually, when you pass an array as a parameter to a method - a reference to this array is passed under the hood. The array itself is stored on the heap. And the reference can be 4 or 8 bytes in size (depending on CPU architecture, JVM implementation, etc.; even more, JLS doesn't say anything about how big a reference is in memory).

On the other hand, primitive int value always consumes only 4 bytes and resides on the stack.

Improve this answer

Comments

4

When you pass an array, the content of the array may be modified by the method that receives the array. When you pass int primitives, those primitives may not be modified by the method that receives them. That's why sometimes you may use primitives and sometimes arrays.

Also in general, in Java programming you tend to favor readability and let this kind of memory optimizations be done by the JIT compiler.

Improve this answer

2 Comments

But if I were to save the value of the original int[0] value through: int tempI = i[0];, then is it better to just use arrays or is the memory usage similar at end of day?
That's a very difficult question to answer. Your sample code doesn't really do anything, and so it's impossible for us to understand the context in which you are operating to a point where we could recommend one approach over the other.
4

The int array reference actually takes up more space in the stack frames than an int primitive (8 bytes vs 4). You're actually using more space.

But I think the primary reason people prefer the first way is because it's clearer and more legible.

People actually do do things a lot closer to the second when more ints are involved.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.