2
$\begingroup$

In terms of references and their implementation on the heap and the stack, how is equality testing for arrays different from that for integers?

This is to do with Java programming, if you have a stack and a heap, would equality testing for example j == i be the same for arrays and for integers? I understand that arrays, are stored in the heap and the stack, as it holds bulks of data, but integers are only stored in the stack and referenced in the heap.

this is a picture on how integer variables are stored on the heap and referenced on the heap

I understand for equality testing j==i (variables) the stack pointer will point to the same location.

I'm confused on how j==i would be different for array and integers.

Could someone explain?

$\endgroup$
  • 1
    $\begingroup$ What is your context? Are you talking about heap and stack as in program execution? I don't understand "In terms of references and their implementation on the heap and the stack", either. $\endgroup$ – Raphael May 19 '12 at 10:42
  • $\begingroup$ Yes, i meant in terms of program execution. $\endgroup$ – Xabi May 19 '12 at 13:24
  • 1
    $\begingroup$ This question is not clear, please provide more context. Are you looking at compilation or at runtime? Which of the several possible meanings of “reference” are you using? Are the integers machine integers or bignums? You mention heap and stack, what kind of languages are you considering? Is concurrency in play? I am closing your question because there is really too little information. Feel free to reply to Raphael's comment or to mine, or to flag your question, after you've improved it, so that we can reopen it. $\endgroup$ – Gilles May 19 '12 at 14:21
  • $\begingroup$ @Gilles, sorry for unclear question, i have edited $\endgroup$ – Xabi May 19 '12 at 15:59
  • $\begingroup$ Primitive, local values are stored on the stack, not the heap. In other words, there are no (direct) references from the stack to integers on the heap. $\endgroup$ – Raphael May 19 '12 at 19:15
3
$\begingroup$

Integers are stored in one word of memory and there is a primitive machine code instruction for testing their equality. Most programming languages lift this instruction to the syntax, as with i == j in Java (where i and j are of type int).

Arrays are stored in multiple contiguous words in memory. In order to test the equality of two arrays, the program needs to iterate through each pair of memory locations and test the equality of the elements stored in them.

Some programming languages hide the distinction between these to operations by allowing the syntax == to be used for testing the equality of two arrays (one can do this in C++, for instance, or Ruby). Other programming languages, such as Java, do not.

$\endgroup$
  • $\begingroup$ Regarding the last paragraph: in C/C++, comparing two arrays A and B with the equality operator does not result in comparing the arrays element-by-element. Instead the comparison is made between the starting address of A and the starting address of B. $\endgroup$ – Juho Jul 26 '12 at 12:05
  • $\begingroup$ @Juho: Dave may have been referring to the fact that std::vector does do an element-wise comparison with its overload of ==. $\endgroup$ – Jon Purdy Jul 26 '12 at 23:24
  • $\begingroup$ @JonPurdy Right, that would be a correct statement. It's important to specify that to avoid confusion since the language has both static C-style arrays and dynamic vector arrays. $\endgroup$ – Juho Jul 27 '12 at 8:57
3
$\begingroup$

The idea of "stack" and "heap" is incoherent in my view. It is best not to think in those terms.

The real difference is between

  • locations that are named by (variable) symbols in the program (call them named locations) and

  • locations (or groups of locations) whose references are stored in other locations (call them referenced locations).

If you want, you can think of named locations sitting in a "stack" and referenced locations sitting in a "heap". But that would be mere terminology. It does not reflect what an implementation might actually do.

In Java, when you declare an integer variable:

int i;

you are creating a named location. An integer such as 23, say, will be stored in that location. Note that only one location is created!

On the other hand, when you declare an integer array:

int a[10];

you are creating a named location a and, in addition, a block of 10 referenced locations for the elements of the array. The named location a stores a reference to the block of the 10 locations. (Note that 11 locations are now created. In addition to the 10 locations for the array elements, an extra location for the reference to the array!) This corresponds to the picture that you have drawn in the question. For integer variables, there is no reference stored anywhere. So, your picture is wrong for integer variables.

I think of Java as an extremely confusing language from this point of view. The declarations int i; and int a[10]; look so similar, but what they mean is entirely different!

Coming back to the question, when you compare two integer variables using i == j", you are asking "are the integers stored in the two named locations the same?". When you compare two array variables using a == b, you are asking the question "are the references stored in the two named locations a and b the same?" If a and b store references to two different blocks of locations both of which might contain the same integers, the comparison a == b would still come out false. Why? The comparison a == b doesn't look at the actual blocks of locations at all. It just checks to see whether they are the same block. This kind of thing is often called reference equality or shallow equality.

It is not really your fault if you are totally confused. When hackers design programming languages, this is the kind of mess they create!

$\endgroup$
  • $\begingroup$ Compared to C++, Java made some substantial simplifications to the object model which greatly benefited the design of the runtime environment. Unfortunately, the Java language erases any distinction between a storage location which is used to identify an entity, and one which is used to encapsulate the contents of the object it identifies. Two storage locations whose purpose is to identify mutable objects should only be considered equal if they identify the same objects; two locations whose purpose is to encapsulate the contents of objects should be considered equal... $\endgroup$ – supercat Mar 25 '14 at 23:40
  • $\begingroup$ ...if they identify objects with equal content. If there were separate compiler types for "object identity" and "object content", even if the runtime considered them mostly the same, then tasks like equality checking and "cloning" could be largely automated. Unfortunately, neither Java nor .NET includes any such distinctions. $\endgroup$ – supercat Mar 25 '14 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.