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?

GhostCat
  • 137,827
  • 25
  • 176
  • 248
AccCreate
  • 373
  • 3
  • 6
  • 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. – Michael Aug 08 '17 at 14:45
  • Just so you know: `int` in Java aren't "initialised", they're not objects. `int`s up to 127 (IIRC) are actually initialized only once, you only get pointers to these values. – Turtle Aug 08 '17 at 14:46
  • So I can assume if I were to be making a code to be as memory efficient as possible, utilizing array pointing for primitives is far better than passing int? Also would the first code by memory standards still be considered O(1) or is it O(n^2) since it theoretically would make new memory values for each pass? Sorry, I'm just genuinely curious on this issue. – AccCreate Aug 08 '17 at 14:47
  • 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.. – harold Aug 08 '17 at 14:51
  • 14
    @Nathan that is only true for the `Integer` wrapper class, not a primitive `int`. –  Aug 08 '17 at 15:25
  • 1
    @Michael passing an int[] is not highly efficient, so that's not the reason. Passing an int as a parameter does not "create another integer". Passing an int as a parameter has the same characteristics as passing an int[] as a parameter - it will temporarily mark a number of bytes off on the JVM internal call/local variable stack, and when the method returns, the stack is popped and the memory is released. – Erwin Bolwidt Aug 08 '17 at 15:27
  • 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`. – Erwin Bolwidt Aug 08 '17 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) – Thomas Kläger Aug 08 '17 at 15:34
  • 3
    If you **have** to wonder about memory efficiency in the order of a couple of bytes, Java is not a good language to do it in (as opposed to, say, C). While there may be documentation that talks about stack allocations etc., you can't really know what's going on at runtime in programs such as yours. It all depends on what the compiler and the JIT do with your code. For all you know, the compiler might optimize away your entire "program" since it has no side effects and a zero exit status. – MarioDS Aug 08 '17 at 17:21
  • Your add up function in your example code is the same as a simple `return 0;` statement. Surely that's not what you meant? The compiler may be smart enough to see this and shorten it to `return i>-1?0:while(1);`. – tuskiomi Aug 08 '17 at 17:30
  • @tuskiomi Ya I know. But I was just wondering upon how Java itself thinks of these kind of recursive calls through methods in a general sense. Since ints don't get pointers since they are primitives, I questioned whether these kind of ideas would be better implemented making an array first then pointing to it. It's more for intellectual pursuit I guess. After all, we use StringBuilders for passing Strings to change them in methods but for int, for some reason, we don't. :D – AccCreate Aug 08 '17 at 19:15
  • The primary reason why people don't do this is because it doesn't work. Your example does not compile. If it did compile, it would always return `0` regardless of the value passed-in (even if the value was negative). – Christopher Schultz Aug 09 '17 at 12:09
  • I appreciate the accept :-) – GhostCat Aug 16 '17 at 16:29

7 Answers7

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).

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • 1
    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? – AccCreate Aug 08 '17 at 14:59
  • 1
    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. – GhostCat Aug 08 '17 at 15:03
  • 5
    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. – Daniel Pryden Aug 08 '17 at 16:53
  • @DanielPryden Thanks for that update. One can learn a new thing here each day. – GhostCat Aug 08 '17 at 17:06
  • Also, pointers have to be stored and duplicated somewhere too. And since they have the same size as ints in java, the second example is in fact **not** more mempry conserving than the first. – WorldSEnder Aug 08 '17 at 23:17
  • @AccCreate I would not want to have to identify stack space utilization using big-O notation in Java. Its performance depends too much on the specifics of how the optimizer handles it. At its worst, space usage could actually be O(n) for both approaches (don't forget that you had to pass a reference to an array in your array based approach). However, it is possible for a decently clever optimizer to do tail-call-recursion optimization, which makes both O(1) – Cort Ammon Aug 09 '17 at 04:09
  • 2
    @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 https://softwareengineering.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization#comment555950_157685). 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. – ninjalj Aug 09 '17 at 09:08
  • 1
    @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. – Holger Aug 09 '17 at 12:57
  • 1
    @AccCreate: formally, both have `O(n)` stack space complexity, as the needed space grows linearly. Practically, the needed stack space per method [can differ by factor six, depending on the JIT state](https://stackoverflow.com/q/27043922/2711488) and even more important, HotSpot uses a preallocated stack memory per thread, which doesn’t change whatever you do. You may get a `StackOverflowError` when it is exhausted, but in regard to memory allocated from the operating system, it is constant, in other words, recursion itself never causes memory allocations in the HotSpot JVM. – Holger Aug 09 '17 at 13:04
  • @WorldSEnder Ints are always 4 byte in Java. References are not. – Voo Aug 09 '17 at 14:36
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.

pfranza
  • 3,292
  • 2
  • 21
  • 34
  • 1
    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). – Daniel Pryden Aug 08 '17 at 16:50
  • 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. – pfranza Aug 08 '17 at 17:04
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.

harold
  • 61,398
  • 6
  • 86
  • 164
  • arguments passed to functions necessarily consume memory. This is how processors work. Am I missing something? – Jack Aug 09 '17 at 16:06
  • 1
    @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. – harold Aug 09 '17 at 17:54
  • 1
    @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. – BeeOnRope Aug 10 '17 at 21:46
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.

Theodore Norvell
  • 15,366
  • 6
  • 31
  • 45
  • 2
    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. – Theodore Norvell Aug 08 '17 at 16:01
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.

Oleksandr Pyrohov
  • 14,685
  • 6
  • 61
  • 90
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.

Andres
  • 10,561
  • 4
  • 45
  • 63
  • 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? – AccCreate Aug 08 '17 at 14:42
  • 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. – JakeRobb Aug 08 '17 at 15:42
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.

Juan C Nuno
  • 476
  • 1
  • 3
  • 8