Search

Monday, June 3, 2013

Java - Pass by Reference Value!

Location: Salt Lake City, UT, USA
To maintain a little bit of the geeky theme I have had going this last week, I wanted to talk a little about something I think is often misunderstood by those beginning in programming, and can be especially confusing to those moving to Java from other languages: the subject of reference vs value.

The primary place where I see this confused is in method parameter passing, but a better understanding of this can pay off in other areas as well.  Also, one point of note, the terms function and method are interchangeable in the topic of computer science. Function is the traditional term, borrowed from mathematics, and used in languages like C.  Method is simply an alternate term, and is favored in Java.  The terms are interchangeable in this context.

Before we start to discuss the differences between them, we should ensure we understand the terms:

Value is what we would call an immediate.  It is a section in memory where an actual value sits.  It could be any data type, an int, double, char[], or even a struct.  On the inside this is just a set amount of memory, contiguous bytes, the number of which depends on the size (or width) of the datatype being stored there.

Reference is simply a memory address which points to a 'value'.  References are held in variables, in C/C++ they are called pointers, which is an ideal name for them, as they literally point to somewhere else in memory.  I will continue to call them pointers here.  The size of a pointer is simply the size (or again, width) of the memory addresses on your hardware (either 4 or 8 bytes typically), and will never be any different because it simply stores a memory address that points to some value.

Values are fairly straightforward to understand, but references are more difficult, mainly because references are also values, but special values, memory values.  This means that references can point to other references, forming a chain which hopefully ends at a real object that has been allocated in memory.  A reference which does not point to a valid allocated object in memory is considered a 'null pointer', it should not be used other than to write a valid address to.



The most succinct way I can think of these relationships is that a value is an actual value that is stored in memory.  A reference is the address to a memory location where a value is stored.  And a pointer is a special type of value, it only holds references (memory addresses), it's the manifestation of a reference.



One of the useful reasons for having references is to facilitate parameter passing, and that is primarily what I intend to address today.

Say you have a exponent or power function, it takes int A and B and returns a long, A to the power of B (A^B).  On our imaginary system an int is 32 bits and a long is 64, so we have a total of 64 bits of input to our function, or 8 bytes of data, in computer speak this is basically nothing.  To run this function we allocate 8 bytes, copy over the values that the method caller provided, and crunch the numbers.  When it's time to return our long (which we had to allocate within our function) we again have a small amount of data and we simply copy it over to a location where the calling function knows to find it.  This method of passing parameters to a function is called pass by value.  We are literally passing the value of the variable provided to the function (or more precisely, an identical copy of that value).

Now say you have a sort function, it takes a linked list, and has no return value (void return type), it sorts the list provided in-place.  When sort function is called what happens?  Given the scenario in the previous paragraph we would assume that enough memory would be allocated to hold the linked list, the values held in the original list would be copied over to this new list, and we would sort the values within this new list.  But this has a few issues.  For one, we couldn't have a return type of void because without returning, we have no way of getting our copy of the list back to the caller.  But even if we return our new list, what if our list is big?  I mean really big?  What if our list was more than half our available memory and we couldn't copy the whole thing to pass to the function?

Do we really require twice as much space as our list requires to call a sort method?  Of course not!  This is where references come in.  Instead of copying our list over to our function, we can copy the address of our list which is what we mean by a reference, and then the method can access it without having to copy or move it at all.  Remember, a reference is typically 32 to 64 bits, basically nothing compared to even a small linked list.  This is referred to as passing by reference since we don't copy the actual value we want to operate on, we pass its memory address so that the function can work directly on the object.

So you can probably see why we need pass by reference, but why then do we bother with pass by value?  The main reason that I am aware of is that references do not allow a caller to protect their data from a function.  When a function is passed a reference there is a risk that the function will modify the input data which the calling function is still using, and this could cause the calling function to violate its assumptions about the state of its own data.  When you pass by value you guarantee that none of your parameters are modified without your knowledge, as the called function is only operating on copies.  There is also a question of optimization.  If you have a function that takes a byte as input, passing by reference might use four times as much memory to pass parameters as passing by value, on a 64 bit system it might be 8 times.  Just as we might want to optimize functions that handle very large inputs, we also should be able to optimize functions with small inputs.

Java does away with the question of reference vs value by making all primitive data types (char, short, int, long, float, double, etc...) pass by value, and all non-primitives pass by reference-value.  Java has no pointers because every reference to a non-primitive type is always a pointer.  There is no special syntax involved because this is simply how all non-primitive variables work, they are all pointers to the object.  So what is passed to a method in java is a copy of that reference, or in other words a totally new variable (which under the hood is a pointer), with a copy of the address to the variable passed to the function.  This distinction can be a little tricky to sort out at first, and difficult to describe in text, so you might want to read that a few times...

Some of the more insidious 'bugs' I have seen in beginning students Java code is related to not understanding how method parameters are passed under the hood.  How modifying the contents of an object itself will be reflected in the calling methods copy of the input, but something like reassigning the variable to a new object entirely will result in no change to the object passed in by the caller.  In other words there is a big difference between:

public static void copyList(LinkedList a, LinkedList b) {
    a.clear();
    a.addAll(b);
}

and

public static void copyList(LinkedList a, LinkedList b) {
    a = b;
}

The first example above will result in the calling function having two lists that contain the same nodes in the same order, as we have simply performed operations on the original lists provided by the caller.  In the second example we have assigned the address for object b to the variable named a.  the variable a now points to the same object that the variable b points to.  In fact, within the second method we no longer even have a reference to the list originally passed in as parameter 'a' at all!  Our second method has not changed the original inputs as expected, it simply changed how the method references those lists, duplicating the reference to the list passed in as 'b' and losing the reference to the list passed in as 'a'.

This is a subtle but important distinction to understand if you hope to write functional Java code.  If you are struggling, leave a comment and I might be able to help make it more clear!

I had intended to write a little about the stack and the heap (dynamic vs static memory) and why this distinction of value vs reference exists in the first place, but this post has already grown larger than I would like, so I will save that discussion for another day!

No comments:

Post a Comment