Data-Oriented Hash Table
reedbeta.com
reedbeta.com
This is really the main reason why your average C++ program written naively will tend to beat the same Java/C# program written naively.
In managed languages you spend much of your time chasing pointers around memory.
Do you mean primitive type array? Because in that case, a bunch of arrays of primitives does not have the same layout and cache locality as an array of structs of primitives.
Anyway, you can usefully control some aspects of how Java lays out your data, including primitive fields:
http://psy-lob-saw.blogspot.com/2013/05/know-thy-java-object...
Layout within objects is not what I'm talking about here. What I'm talking about is layout of objects within an array. There's no way to do an array of <whatever>. It's an array of <primitive> or an array of <pointer to whatever>. So much pointer-chasing!
In (e.g.) C, I can do either array-of-structs or structs-of-arrays. In Java... I don't know any way to have an array-of-structs in Java (portably, that is).
Not necessarily. There are some compelling counterexamples indicating that, in the kinds of problem spaces Java and C# are designed for, a C++ programmer will have to go to great lengths to meet or exceed the performance of a naive Java or C# program. That famous series of blog posts by Rico Mariani and Raymond Chen over at Microsoft comes to mind.
What it comes down to is this: Business applications tend to create a lot of objects[1] that have variable lifetimes. In a language like C++ this leads to memory fragmentation - lots of little gaps start to form when shorter-lived objects that were allocated between longer-lived objects get freed. New objects get put into those gaps when they fit, which means new memory allocations involve time-consuming hunts for appropriately-sized gaps. And objects that are allocated about the same time may end up going into gaps that are widely separated in memory - which can be seriously detrimental to locality of reference, since things that are allocated together are generally also accessed together.
But Java and C# have a secret weapon here: You don't get pointers[2], so the memory manager is free to move objects around without you even knowing. And that means they get to have compacting garbage collectors. Compacting improves locality of reference by, well, compacting. But it also means that performance-wise, the heap starts to behave a bit more like a stack: Finding an empty slot where you can allocate new stuff works exactly the same as in stack allocation, and is therefore very fast. All your live, up-in-the-air stuff is very close together because it's all getting allocated at the top of the heap. Etc. etc. Long story short the cost of pointer-chasing, which you'd probably be doing anyway, is mitigated quite a bit.
C++ will absolutely let you make up the difference by carefully arranging your data, micro-managing what gets allocated when and where, etc. And that does mean that you can make it scream. But in terms of the default performance you can expect out of a language, the story can be quite a bit different. Not as well-publicized, either, since the most well-known source for language benchmarks quite explicitly makes itself into a game about who can submit the most efficient implementation in their favorite language. I'd submit, though, that the vast majority of us should be more worried about the typical outcome than the best-case scenario. That's the outcome we'll actually see.
[1]In this case, by object I mean "thing that's allocated on the heap". So not necessarily just objects-as-in-OOP, though I'm obviously drawing on a C++/Java way of thinking by picking my language in such away. Excuse the sloppy.
[2]OK yes, C# does have pointers, but they're ghettoized in order to keep them mostly out of the way of the garbage collector. Further excuse the sloppy.