C++: Vector of Objects vs. Vector of Pointers
bfilipek.com
bfilipek.com
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
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/ 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.
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.htm...
I also know of static java compilers that do mess around with this.
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
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.
(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.
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.
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.
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.
http://openjdk.java.net/jeps/169
https://blogs.oracle.com/jrose/entry/value_types_and_struct_...
http://mail.openjdk.java.net/pipermail/lambda-dev/2014-March...
Code: http://ideone.com/xIV3f9
Here is what I see with default optimization:
jao@minizack:/tmp$ gcc -std=c99 x.c
jao@minizack:/tmp$ ./a.out
INTERNAL time/scan (usec): 29608.000000 xor: 1722783152
EXTERNAL UNSORTED time/scan (usec): 26688.105263 xor: 1722783152
EXTERNAL SORTED time/scan (usec): 279771.105263 xor: 1722783152
SORTED/UNSORTED: 10.482989
jao@minizack:/tmp$ gcc -std=c99 -O3 x.c
jao@minizack:/tmp$ ./a.out
INTERNAL time/scan (usec): 3636.421053 xor: 1722783152
EXTERNAL UNSORTED time/scan (usec): 12114.263158 xor: 1722783152
EXTERNAL SORTED time/scan (usec): 242141.263158 xor: 1722783152
SORTED/UNSORTED: 19.988113
- With -O3, the difference between INTERNAL (#1) and EXTERNAL UNSORTED (#2) is close to what you are seeing.
- Loops cannot be optimized away in this version.
- The fact that -O3 speeds up EXTERNAL UNSORTED by 2x but EXTERNAL SORTED only a little makes sense if the latter is slow due to cache misses.
I assume you know of it and have your reasons, just couldn't help but point it out.
class Something {
public int foo;
public int bar;
}
new SomeThing[100];
int[] foos = new int[100];
int[] bars = new int[100];
Also, as an example, most JITs (including the JVM one) optimize through vtable lookups (so you can inline a whole series of polymorphic calls that might boil down to a constant value). That's an example of an ease of dev vs performance tradeoff (polymorphic methods) that's been alleviated in an automated way by tools.
How? Doesn't this depend on the specific kind of polymorphism/implementation of which, rather than being about polymorphism inherently? What if types are erased at compile-time and the compiler generates functions and such for all the relevant types that you need?
> but in practice understanding much of the polymorphic code ive worked on still requires a mental process of "OK, if it's THIS type then this happens; if its THAT type then something else happens."
I think this is impossible with parametric polymorphism - if you say that the input data can be any type, you can't make any assumptions about what type it might be. If the incoming type only has the constraint that it can be tested for equality on other values of the same type, they only function you can use on it is ==, and so on.
In the benchmark this requires the compiler to generate code that makes sure that the object was not changed by issuing an exclusive request for the data plus the additional pointer dereferencing.
To check what is really happening I recommend two things:
1) Look at the generated code and see what the compiler issues. 2) Compare object* vs shared_ptr<object> 3) Compare unique_ptr vs object vs object*
My assumption is that unique_ptr will be faster than shared_ptr and have the same speed as object* and that will be a bit slower than object.
However, I haven't tried it but just looked up the implementation of std::shared_ptr in GCC 4.9.0, and accessing it is exactly the same as with a raw pointer. operator-> and operator* just return the internal pointer and do nothing else.
There's some slight space overhead associated with shared_ptr, since it has to store the two counters for shared and weak references, so that might influence the runtime. unique_ptr should behave exactly like a raw pointer.
That said, I'd love to see some benchmarks about this as well and would be even happier to be proven wrong.
Another aspect I find interesting about this is that as the objects grow, it makes sense to store them in column-wise (one array/chunk of memory just for member1, one for member2, ...) instead of row-wise.
I don't know any languages besides Q that make this way of storing data easy/the default.
The design here may also benefit from a custom allocator so that objects of same type are constructed in memory in a contiguous fashion. Especially if you want more than one vector of these objects in the code. The above book also has a number of smart pointer constructs that are probably similar to these pointers but with customizable behaviors and strategies.
As someone else mentioned when code hits the real world things tend to break down but if you are not following a good memory design to begin with you don't even have the hope of getting the better performing version.
should really be:
Just by moving data around, by carefully storing it in one place, and by not doing anything else that messes up caching or consumes CPU cycles we can get huge performance speed up.
A microbenchmark like this will always show results that are unattainable in practice; the work in real code is likely to take considerably more time than the fetch.
That is, this might not be as unobtainable as you seem to be implying. There was a great presentation by someone in the gaming community about this. I can't find it right off, but at a glance this[1] article seems pretty good. And is basically this idea.
You're probably thinking of Tony Albrecht's fantastic "Pitfalls of Object-Oriented Programming" talk which is referenced by (and inspired!) the chapter:
http://research.scee.net/files/presentations/gcapaustralia09...
Vectors are awesome because of contiguous memory allocation. Vectors are also horrible because of contiguous memory allocation. Really, the rule is that you have to understand what is going on beneath the data structure abstraction. When your vector starts resizing, when you don't know beforehand how many elements will be in it - that's when you start to consider using pointers instead.
In the very first line of code, he reserves space for `count` variables - not something you're always able to do. (When you don't reserve the space beforehand, the vector is created with some initial size, and then if it exceeds it, all pre-allocated storage for the vector must be copied to a new location w/ the new size - rinse and repeat as needed.)
Obviously there are always better data structures more suited to your needs, in this case a deque might come in handy (it's quite the underrepresented STL data structure).
And even the shuffling doesn't really simulate a realistic distribution in memory, it'd be better to also allocate random memory block in between the objects.
1) Layer of indirection
2) Non-continuous memory
3) shared_ptr overhead itself as you mentioned.
All that and only 2x slower? For many applications performance of this particular operation is a rounding error of a rounding error.
This tells me not to worry about optimizing my iterations across datasets prematurely.
min 46 onward, http://channel9.msdn.com/Events/Build/2014/2-661
Though it would be interesting to see what sort of difference there is using make_shared<>(...) vs shared_ptr(new ...).
And also what difference there would be when the vector needs to be resized and the objects are noexcept movable or need to be copied.