6 ms·

I was wondering about this very issue the other day, and wrote a little C program to try something similar. I tried three things: 1. Create an array of random

I was wondering about this very issue the other day, and wrote a little C program to try something similar. I tried three things: 1. Create an array of random ints, (sort them, not that it matters), and then time how long it takes to compute the sum. 2. Create an array of ints (data) and an array of int* (ptr). Set ptr[i] to point to data[i]. Scan the data through the ptr array and compute the sum. Obviously there is very good locality of access to both arrays. 3. Same as #2, but first sort the ptr array so that * ptr[i] <= * ptr[i+1]. There will be good locality on ptr, not so much on data. For arrays of size 10M, #1 and #2 cost about the same, and #3 was 5x slower. (This was on my MacBook Pro, using XCode.) But my main point here is about Java, which has been my main language for many years. I don't care (much) about its verbosity, its lack of closures, etc. I can get my work done. But working with large heaps has proven very problematic, both in avoiding GC overheard, and in the effects of non-locality. While you can have both true int arrays and Integer arrays, the same is not true of non-primitive types. There is no way to have anything like an array of structs, with the same compact representation, as you can have in C. There are benchmarks showing that Java and C are competitive in performance. But C/C++ can be used to preserve locality for arrays of structs and objects in ways that Java cannot. Java has to be slower in these situations. There are well-known tricks to address this problem. E.g. use two arrays of ints instead of an array of Objects which encapsulate two ints. For these reasons, I would be very happy to see an idea like Value Types added to Java: http://cr.openjdk.java.net/~jrose/values/values-0.html http://cr.openjdk.java.net/~jrose/values/values-0.html

Guvante 12y ago
C# has value types and is Java like. I assume you know of it and have your reasons, just couldn't help but point it out.
- pkolaczk 12y ago
  Even without value types, Java/C# can do probably much better on the pointer vector case than C++, thanks to allocation from contiguous region and automatic memory defragmentation. It is very likely all the objects referenced from the vector would be placed in a contiguous memory region which is easy to prefetch for the CPU (sure, still not as fast as inlining them into array). This is completely different than in C++ where subsequent dynamic allocations return pointers scattered around the whole heap, especially after long run.
bradleyjg 12y ago
I think Oracle is working on adding value types. Hopefully for java 9, more likely java 10. http://openjdk.java.net/jeps/169 http://openjdk.java.net/jeps/169 https://blogs.oracle.com/jrose/entry/value_types_and_struct_tearing https://blogs.oracle.com/jrose/entry/value_types_and_struct_... http://mail.openjdk.java.net/pipermail/lambda-dev/2014-March/011938.html http://mail.openjdk.java.net/pipermail/lambda-dev/2014-March...
anonymoushn 12y ago
You can hack together an "array of structs" object using unsafe, but the amount of code involved when using Java is unreasonable. It was manageable in Scala, but this is no reason to introduce Scala to a non-Scala codebase.
stonemetal 12y ago
Why couldn't java do #2? It sees you allocate the array it could preallocate or reserve a block of memory for the objects that are about to fill it.
- Rusky 12y ago
  In the general case, you need to be able to put arbitrary objects into the array, regardless of how they were allocated. You also need to be able to keep track of null elements.
detrino 12y ago
I'm not sure how you measured your programs, if you measured them as a whole, then the random generation and sorting probably dominated the run-time. On my machine #1 is 3x faster than #2 for just the summing part of 10M 32-bit integers. Code: http://ideone.com/xIV3f9 http://ideone.com/xIV3f9
- geophile 12y ago
  Sorry I wasn't clear, I just measured the scan time, after loading and sorting the arrays.
  - detrino 12y ago
    Then my results disagree with yours. Do you have the source code to your benchmark ?
    - geophile 12y ago
      http://pastebin.com/DtsYEsYL http://pastebin.com/DtsYEsYL
      - detrino 12y ago
        The compiler is entirely eliminating your loop because you never do anything with the sum variable. Also, signed integer overflow is UB so you should use unsigned integers or compile with the non-standard -fwrapv option.
        geophile 12y ago
        I'm not convinced of this. I modified the code to do something with the sums. #2 is now slightly slower than #1, but the absolute times and the ratios are otherwise about the same. http://pastebin.com/vbUSdKGc http://pastebin.com/vbUSdKGc
        detrino 12y ago
DannyBee 12y ago
"While you can have both true int arrays and Integer arrays, the same is not true of non-primitive types. There is no way to have anything like an array of structs, with the same compact representation, as you can have in C. There are benchmarks showing that Java and C are competitive in performance. But C/C++ can be used to preserve locality for arrays of structs and objects in ways that Java cannot. Java has to be slower in these situations. " Java does not have to be slower in these situations. The fact that something does not exist in the source language is irrelevant. You can rearrange, restructure, and generally do whatever you want in a compiler as long as you preserve the original semantics or can prove they don't matter to the program. For things like you are talking about, for non-primitive accesses, often the non-primitive types are locally split up in a function, each piece treated like a separate part, and then put back together where necessary (if necessary, in fact). Given large parts of the program, you can also do this interprocedurally as well (it's trickier though, to know when it is safe). For arrays of whatever, it may be internally transformed into the same contiguous representation you see in C. (ie struct of arrays transformed into array of structs, which has been done for a very long time. It became famous because it sped up SPECcpu's 179.art by a very very large factor). Besides that, data layout optimizations are pretty common in compilers (as is loop rearrangement of various sorts. For heavy locality optimization, algorithms like http://pluto-compiler.sourceforge.net/ http://pluto-compiler.sourceforge.net/ exist) So in short, it does not have to be slower. It often is for other reasons, but it does not have to be. It all depends on how much time you are willing to trade optimizing code vs running it.
- epistasis 12y ago
  Implicit with the term "Java" is also the JVM, and the JVM has significant restrictions with regard to memory layout of arrays. I'm not sure any compiler can get around that.
  - DannyBee 12y ago
    Like what? I'm honestly curious, the only docs i see say the opposite: "To implement the Java Virtual Machine correctly, you need only be able to read the class file format and correctly perform the operations specified therein. Implementation details that are not part of the Java Virtual Machine's specification would unnecessarily constrain the creativity of implementors. For example, the memory layout of run-time data areas, the garbage-collection algorithm used, and any internal optimization of the Java Virtual Machine instructions (for example, translating them into machine code) are left to the discretion of the implementor." From the JVM spec: http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.htm... I also know of static java compilers that do mess around with this.
sreque 12y ago
It is bad for performance that Java doesn't have structs, but, you can work around this somewhat using byte buffers: http://www.kdgregory.com/?page=java.byteBuffer http://www.kdgregory.com/?page=java.byteBuffer
- danieldk 12y ago
  In the case of arrays, you can also have parallel arrays. E.g.: class Something { public int foo; public int bar; } new SomeThing[100]; becomes: int[] foos = new int[100]; int[] bars = new int[100]; And write appropriate getters/setters.

Guvante 12y ago

C# has value types and is Java like. I assume you know of it and have your reasons, just couldn't help but point it out.

pkolaczk 12y ago
Even without value types, Java/C# can do probably much better on the pointer vector case than C++, thanks to allocation from contiguous region and automatic memory defragmentation. It is very likely all the objects referenced from the vector would be placed in a contiguous memory region which is easy to prefetch for the CPU (sure, still not as fast as inlining them into array). This is completely different than in C++ where subsequent dynamic allocations return pointers scattered around the whole heap, especially after long run.

bradleyjg 12y ago

I think Oracle is working on adding value types. Hopefully for java 9, more likely java 10. http://openjdk.java.net/jeps/169 http://openjdk.java.net/jeps/169 https://blogs.oracle.com/jrose/entry/value_types_and_struct_tearing https://blogs.oracle.com/jrose/entry/value_types_and_struct_... http://mail.openjdk.java.net/pipermail/lambda-dev/2014-March/011938.html http://mail.openjdk.java.net/pipermail/lambda-dev/2014-March...

anonymoushn 12y ago

You can hack together an "array of structs" object using unsafe, but the amount of code involved when using Java is unreasonable. It was manageable in Scala, but this is no reason to introduce Scala to a non-Scala codebase.

stonemetal 12y ago

Why couldn't java do #2? It sees you allocate the array it could preallocate or reserve a block of memory for the objects that are about to fill it.

Rusky 12y ago
In the general case, you need to be able to put arbitrary objects into the array, regardless of how they were allocated. You also need to be able to keep track of null elements.

detrino 12y ago

I'm not sure how you measured your programs, if you measured them as a whole, then the random generation and sorting probably dominated the run-time. On my machine #1 is 3x faster than #2 for just the summing part of 10M 32-bit integers. Code: http://ideone.com/xIV3f9 http://ideone.com/xIV3f9

geophile 12y ago
Sorry I wasn't clear, I just measured the scan time, after loading and sorting the arrays.
- detrino 12y ago
  Then my results disagree with yours. Do you have the source code to your benchmark ?
  - geophile 12y ago
    http://pastebin.com/DtsYEsYL http://pastebin.com/DtsYEsYL
    - detrino 12y ago
      The compiler is entirely eliminating your loop because you never do anything with the sum variable. Also, signed integer overflow is UB so you should use unsigned integers or compile with the non-standard -fwrapv option.
      - geophile 12y ago
        I'm not convinced of this. I modified the code to do something with the sums. #2 is now slightly slower than #1, but the absolute times and the ratios are otherwise about the same. http://pastebin.com/vbUSdKGc http://pastebin.com/vbUSdKGc
        detrino 12y ago

DannyBee 12y ago

"While you can have both true int arrays and Integer arrays, the same is not true of non-primitive types. There is no way to have anything like an array of structs, with the same compact representation, as you can have in C. There are benchmarks showing that Java and C are competitive in performance. But C/C++ can be used to preserve locality for arrays of structs and objects in ways that Java cannot. Java has to be slower in these situations. " Java does not have to be slower in these situations. The fact that something does not exist in the source language is irrelevant. You can rearrange, restructure, and generally do whatever you want in a compiler as long as you preserve the original semantics or can prove they don't matter to the program. For things like you are talking about, for non-primitive accesses, often the non-primitive types are locally split up in a function, each piece treated like a separate part, and then put back together where necessary (if necessary, in fact). Given large parts of the program, you can also do this interprocedurally as well (it's trickier though, to know when it is safe). For arrays of whatever, it may be internally transformed into the same contiguous representation you see in C. (ie struct of arrays transformed into array of structs, which has been done for a very long time. It became famous because it sped up SPECcpu's 179.art by a very very large factor). Besides that, data layout optimizations are pretty common in compilers (as is loop rearrangement of various sorts. For heavy locality optimization, algorithms like http://pluto-compiler.sourceforge.net/ http://pluto-compiler.sourceforge.net/ exist) So in short, it does not have to be slower. It often is for other reasons, but it does not have to be. It all depends on how much time you are willing to trade optimizing code vs running it.

epistasis 12y ago
Implicit with the term "Java" is also the JVM, and the JVM has significant restrictions with regard to memory layout of arrays. I'm not sure any compiler can get around that.
- DannyBee 12y ago
  Like what? I'm honestly curious, the only docs i see say the opposite: "To implement the Java Virtual Machine correctly, you need only be able to read the class file format and correctly perform the operations specified therein. Implementation details that are not part of the Java Virtual Machine's specification would unnecessarily constrain the creativity of implementors. For example, the memory layout of run-time data areas, the garbage-collection algorithm used, and any internal optimization of the Java Virtual Machine instructions (for example, translating them into machine code) are left to the discretion of the implementor." From the JVM spec: http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.htm... I also know of static java compilers that do mess around with this.

sreque 12y ago

It is bad for performance that Java doesn't have structs, but, you can work around this somewhat using byte buffers: http://www.kdgregory.com/?page=java.byteBuffer http://www.kdgregory.com/?page=java.byteBuffer

danieldk 12y ago
In the case of arrays, you can also have parallel arrays. E.g.: class Something { public int foo; public int bar; } new SomeThing[100]; becomes: int[] foos = new int[100]; int[] bars = new int[100]; And write appropriate getters/setters.