3

I try to find what is difference between primitive java 'array' and 'List' data structure (like ArrayList), and find articles or Q&A like this (Difference between List and Array). Many articles including that link point that java primitive 'array' is 'sequential memory'. In this point, what is sequential exactly? is this really sequential in physical memory? or sequential in virtual memory? My guess is sequential in virtual memory, because OS assigns physical memory in general and application(JVM) doesn't care about specific memory allocation. But I do not know exact answer.

Community
  • 1
  • 1
Stephen Choi
  • 70
  • 1
  • 8

4 Answers4

4

A Java array is sequential in virtual memory not necessarily in physical memory.

A user-space application (such as a JVM) has no say over whether the physical pages that make up its virtual address space are contiguous in memory. And in fact, it has no way of even knowing this in typical modern operating systems. This is all hidden from a user-space application by the machine's virtual memory hardware and (user-space) instruction set architecture.

Looking at the JVM spec is not going to be instructive on the physical memory issue. It is simply not relevant / out of scope.

The JVM spec doesn't mandate that arrays are contiguous in virtual memory. However, (hypothetical) array implementations that involved non-contiguous virtual memory would lead to expensive array operations, so you are unlikely to find a mainstream JVM that does this.

References:

  • JVM Spec 2.7 says:

    "The Java Virtual Machine does not mandate any particular internal structure for objects."

    Other parts of the spec imply that "objects" refers here to BOTH instances of classes AND arrays.

  • JVM Spec 2.4 talks about arrays, but it doesn't mention how they are represented in memory.

The difference between arrays and ArrayLists are at a higher level. Arrays have a fixed size. ArrayLists have a variable size. But under the hood, an ArrayList is implemented using a (single) array ... which can be reallocated (i.e. replaced) if the list grows too big.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • Thanks for answer. In conclusion, when system access memory, order is physically sequential memory > virtually sequential memory > others. right? – Stephen Choi Jul 17 '14 at 10:01
  • I don't understand what you are asking. – Stephen C Jul 17 '14 at 10:04
  • It's question about access time. I think required time to access to physically sequential items is faster than virtually sequential items. – Stephen Choi Jul 17 '14 at 10:15
  • Not necessarily. The problem is that you tyoically can't turn off the virtual memory support. So even if the memory pages are physically contiguous, you still have the same (potential) overhead of page table lookup when you address across a page boundary. – Stephen C Jul 17 '14 at 10:43
2

You would have to look at the JVM specs to see whether any such requirement is made (whether arrays need to be sequential memory or not), but for efficiency purposes it makes sense that an array would be allocated in a malloc type way.

As for virtual vs. physical, everything (above the OS) works with virtual memory. The JVM isn't low level enough to have access to something the kernel does at Ring-0.

And lastly, why are you interested, are you writing your own JVM?

Kayaman
  • 72,141
  • 5
  • 83
  • 121
  • Thanks for answer. and you mentioned malloc, but vmalloc and kmalloc is different.. you mean vmalloc? – Stephen Choi Jul 17 '14 at 09:56
  • Yes, vmalloc. It would be quite unnecessary (not to mention dangerous) for the JVM to have access to physical memory. – Kayaman Jul 17 '14 at 09:58
1

JVM gets virtual sequential memory from OS. Only at OS level it is possible to assign physical memory sequentially.

Also it's important to not confuse between sequential memory allocation and sequential access - sequential access means that a group of elements is accessed in a predetermined, ordered sequence. A data structure is said to have sequential access if one can only visit the values it contains in one particular order. The canonical example is the linked list. Whereas sequential memory meaning assigning of sequential memory (not necessarily physically sequential, but virtually sequential).

Besides the link you posted some major differences between Array and ArrayList are:

  • Array is fixed in size, ArrayList is dynamic in size
  • Array can store primitives, ArrayList can only store Objects (Wrapper types for primitives)
  • You can use generics with ArrayList
  • You can use add() method to insert element into ArrayList and you can simply use assignment operator to store element into Array

References: Java67 article, Wikipedia

Alexander Rühl
  • 6,769
  • 9
  • 53
  • 96
Mustafa sabir
  • 4,130
  • 1
  • 19
  • 28
0

this might be an interesting article explaining your question.

  • Arrays are also objects in Java, so how an object looks like in memory applies to an array.

To summarise: 

class A {
int x;
int y;
}



public void m1() {
int i = 0;
m2();
}

public void m2() {
A a = new A();
}

When m1 is invoked, a new frame (Frame-1) is pushed into the stack, and local variable i is also created in Frame-1. Then m2 is invoked inside of m1, another new frame (Frame-2) is pushed into the stack. In m2, an object of class A is created in the heap and reference variable is put in Frame-2.

Physical memory locations are out of your hands and will be assigned by the OS

http://www.programcreek.com/2013/04/what-does-a-java-array-look-like-in-memory/

Arno_Geismar
  • 2,296
  • 1
  • 15
  • 29