3 ms·

"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 stru

"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.
  - robryk 12y ago
    More importantly, even if a compiler does optimize that, you can't rely on that: next version of the compiler could have slightly different conditions that trigger the optimization and your code could run 5x slower for no obvious reason.
    - DannyBee 12y ago
      Compiler bugs and regressions are a fact of life, it's why we have regression tests :)
  - epistasis 12y ago
    >correctly perform the operations specified therein Not sure how you're reading the JVM docs to the contrary, as the actual JVM instruction set differs quite a bit from a normal CPU. The JVM has limited operations for calculating memory addresses for arrays. Typically, this is a great thing, as it means that all memory accesses are bounds checked and an entire class of memory errors are eliminated. However, if you're trying to do what geophile is trying do with memory layout, you want a calculation like i * (sizeof(struct) + base_pointer But with Java the sizeof(struct) can only be one of the base types. And then you have to pop memory addresses and treat them as different things, etc. And even if you store things as byte arrays and perform an extra multiplication and add on your own, you then have to collate bytes and cast, which involves lots and lots of jvm operations. With special JVM support, it may be possible, but it's not something that is the least bit natural. And you'd want some sort of standardized support so that you could ensure that your JVM would support the special translation of 10 instructions into a single machine instruction every time, basically the Value Types proposal, I guess.
    - DannyBee 12y ago
      I think you may be confused. At the point at which you compile this, you are no longer dealing with JVM bytecode, but your own IR (translated from JVM bytecode), and can do whatever you want. Thus, you are not limited by what the JVM has in terms of instructions. (and in general, you never are. You are only limited by correctness of program execution) If you want to support it at the bytecode level, yes, what you are suggesting is correct, but it doesn't have to be done this way at all, and rarely is in any language. In general, having to muck up source-code to get optimal data-layouts is a non-starter. Second, the actual optimal data layouts are rarely what programmers think they are due to cache/other complications (it's usually some very complicated nested struct layout with explicit packing and unions in various places) In any case, i believe my base point stands: There is nothing that stops java from being fast in these cases, because you don't need any support from bytecode to do it.
srean 12y ago
I was not aware of PLUTO, thanks for the pointer (no pun intended). If you have used it could you share more. I am particularly interested in how different is the speedup compared to accessin polyhedral loop optimization from inside gcc (or g++). GCC has interface to Cloog and graphite, that seem to target the same features. With that out of the way, "can be" is a very weak statement. Almost anything "can be", what matters more is "does it now". @DannyBee Reply appreciated.
- DannyBee 12y ago
  Pluto's basic algorithm was implemented in ISL, and can be used by graphite. There are patches to do it. The optimizer i last remember in graphite was very basic. So you'd see much much larger speedups if you used pluto Graphite in GCC is, AFAIK, semi-abandoned. The research and future work was moved to Polly and LLVM (at least, most of the developers were hired and put to work on it). I don't know who still develops graphite for GCC, if anyone. In Polly, Polly supports both the ISL version of the algorithm and actually, linking to Pluto, but i don't have any performance numbers handy. "With that out of the way, "can be" is a very weak statement. Almost anything "can be", what matters more is "does it now". " IMHO, not really. Sure, in the sense that it's not useful if nobody ever does it. But if this was the performance problem a lot of people were having, it'd be fixed. So in that sense, it matters a lot more what can be.
gsg 12y ago
> For arrays of whatever, it may be internally transformed into the same contiguous representation you see in C. This is a bit tricky because Java and C semantics are not the same, and an optimizer is obliged to prove that the difference does not matter before allowing the transformation. (It could also be given license by some kind of annotation.) Sharing of mutated fields and Java's == are the major obstacles to doing this transparently, as far as I know. They turn out not to matter if there are no other references to the objects which you want to embed in the array, but proving that (in all the cases in which you would want it to apply) is a bit tough.

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.
- robryk 12y ago
  More importantly, even if a compiler does optimize that, you can't rely on that: next version of the compiler could have slightly different conditions that trigger the optimization and your code could run 5x slower for no obvious reason.
  - DannyBee 12y ago
    Compiler bugs and regressions are a fact of life, it's why we have regression tests :)
- epistasis 12y ago
  >correctly perform the operations specified therein Not sure how you're reading the JVM docs to the contrary, as the actual JVM instruction set differs quite a bit from a normal CPU. The JVM has limited operations for calculating memory addresses for arrays. Typically, this is a great thing, as it means that all memory accesses are bounds checked and an entire class of memory errors are eliminated. However, if you're trying to do what geophile is trying do with memory layout, you want a calculation like i * (sizeof(struct) + base_pointer But with Java the sizeof(struct) can only be one of the base types. And then you have to pop memory addresses and treat them as different things, etc. And even if you store things as byte arrays and perform an extra multiplication and add on your own, you then have to collate bytes and cast, which involves lots and lots of jvm operations. With special JVM support, it may be possible, but it's not something that is the least bit natural. And you'd want some sort of standardized support so that you could ensure that your JVM would support the special translation of 10 instructions into a single machine instruction every time, basically the Value Types proposal, I guess.
  - DannyBee 12y ago
    I think you may be confused. At the point at which you compile this, you are no longer dealing with JVM bytecode, but your own IR (translated from JVM bytecode), and can do whatever you want. Thus, you are not limited by what the JVM has in terms of instructions. (and in general, you never are. You are only limited by correctness of program execution) If you want to support it at the bytecode level, yes, what you are suggesting is correct, but it doesn't have to be done this way at all, and rarely is in any language. In general, having to muck up source-code to get optimal data-layouts is a non-starter. Second, the actual optimal data layouts are rarely what programmers think they are due to cache/other complications (it's usually some very complicated nested struct layout with explicit packing and unions in various places) In any case, i believe my base point stands: There is nothing that stops java from being fast in these cases, because you don't need any support from bytecode to do it.

srean 12y ago

I was not aware of PLUTO, thanks for the pointer (no pun intended). If you have used it could you share more. I am particularly interested in how different is the speedup compared to accessin polyhedral loop optimization from inside gcc (or g++). GCC has interface to Cloog and graphite, that seem to target the same features. With that out of the way, "can be" is a very weak statement. Almost anything "can be", what matters more is "does it now". @DannyBee Reply appreciated.

DannyBee 12y ago
Pluto's basic algorithm was implemented in ISL, and can be used by graphite. There are patches to do it. The optimizer i last remember in graphite was very basic. So you'd see much much larger speedups if you used pluto Graphite in GCC is, AFAIK, semi-abandoned. The research and future work was moved to Polly and LLVM (at least, most of the developers were hired and put to work on it). I don't know who still develops graphite for GCC, if anyone. In Polly, Polly supports both the ISL version of the algorithm and actually, linking to Pluto, but i don't have any performance numbers handy. "With that out of the way, "can be" is a very weak statement. Almost anything "can be", what matters more is "does it now". " IMHO, not really. Sure, in the sense that it's not useful if nobody ever does it. But if this was the performance problem a lot of people were having, it'd be fixed. So in that sense, it matters a lot more what can be.

gsg 12y ago

> For arrays of whatever, it may be internally transformed into the same contiguous representation you see in C. This is a bit tricky because Java and C semantics are not the same, and an optimizer is obliged to prove that the difference does not matter before allowing the transformation. (It could also be given license by some kind of annotation.) Sharing of mutated fields and Java's == are the major obstacles to doing this transparently, as far as I know. They turn out not to matter if there are no other references to the objects which you want to embed in the array, but proving that (in all the cases in which you would want it to apply) is a bit tough.