-2

Prelude

Recently, I helped a friend of mine in coding him a problem for his university Algorithms course, where problems are submitted in Java. I sent him code with good O notation complexity, sequential memory accesses (as I thought) and etc, all the common in C++ world good practices, and kept hitting Time Limit Exceeded message. This is not an attempt to start a war about programming languages.

Known issues

However, sequential memory accesses when iterating over an ArrayList<SomeClass> (which I thought is as simple as going over std::vector<SomeStruct> in C++) turned out to be not as fast as I wanted it to be, due to reasons we all know:

  1. Each separate element of the ArrayList is stored in some arbitrary place of the heap (potentially not sequential at all?)
  2. Some of the allocations (not all, but some of them) require an actual system call to get memory from OS to create an instance of SomeClass (well, it's partially solved with memory pools, and might be solved in some way with Project Valhalla JEP-401)
  3. And even after all that generics in Java work in a way that ArrayList actually stores pointers to Objects, so on each call of SomeClass's method, CPU has to go to v-table, check type (potentially branch-predicted?), and only after all that call correct method.
  4. Bound-checks in array (probably branch-predicted or JIT optimized?)
  5. Also, sometimes daemon-thread like garbage collector kicks in, and spends some of the time resources of the program

After thinking on it for a while, I have no idea how developers in banks, some HFT companies (!!!), stock markets and other businesses that require high performance, manage to write fast (not "fast enough", but really fast, competing) code in Java.

Question

I can understand how anything can be optimized by out-of-order execution on CPU, smart allocator, and JIT, except for the memory-access patern: How does Java, and other managed languages, get any performance, if everything is at random places of a heap [or they aren't random?], everything is non-sequential [is it?] and therefore each memory access, even in "sequential" ArrayList is a cache miss?

19
  • 2
    Welp, then I assume professor has forgot to implement warmup stage of tests. Happens to the best of us. The course is probably new.
    – Basilevs
    Jan 30 at 16:47
  • 1
    @blonded04 Iterating over an array is not filling an array. Are you including the time to create and populate the array in the timing? That's fine, but you should be clear about what you are measuring.
    – JimmyJames
    Jan 30 at 17:18
  • 2
    Realistically: most people don't care about cache locality in any language. Those that do use different data structures. May I present the LMAX Disruptor: lmax-exchange.github.io/disruptor/user-guide/index.html
    – pjc50
    Jan 31 at 14:27
  • 4
    (also, if you're helping someone else cheat on their homework, there is no way Java students would be expected to care about cache locality, and there is something else performance-wise wrong that you've not spotted)
    – pjc50
    Jan 31 at 14:29
  • 3
    @blonded04 anyway, a key insight you need is that very few Java users are bound by raw CPU use as an important consideration. Most Java - in fact I suspect most server-side code - is of the form "retrieve a small number of records from DB or another API and process them lightly". Cache locality works because the code is working with the objects it just created, and most of the request-based unit of work fits in cache.
    – pjc50
    Jan 31 at 15:07

2 Answers 2

4

After thinking on it for a while, I have no idea how developers in banks, some HFT companies (!!!), stock markets and other businesses that require high performance, manage to write fast (not "fast enough", but really fast, competing) code in Java.

Fast enough is fast enough. These are businesses. You don't blindly reach for speed if you want to stay in business. A little thing called the law of diminishing returns will bankrupt you faster than any competitor if you ignore practicality. Focus on the speed you need. Measure. Profile. Decide if you really care.

You seem really averse to indirection. Understand that indirection can speed you up if the alternative is moving copies around. Don't assume you know which is faster without evidence. Yes, indirection comes at a cost. Making things sequential comes at a cost as well.

Recently, I helped a friend of mine in coding him a problem for his university Algorithms course, where problems are submitted in Java. I sent him code with good O notation complexity, sequential memory accesses (as I thought) and etc, all the common in C++ world good practices, and kept hitting Time Limit Exceeded message. This is not an attempt to start a war about programming languages.

Java isn't C++. Not all the C++ tricks work in Java.

If you were hoping for a list of Java tricks you should know that we regularly close list questions.

performance, if everything is at random places of a heap [or they aren't random?] , everything is non-sequential [is it?] and therefore each memory access, even in "sequential" ArrayList is a cache miss?

I can’t predict everything but I think there are some fundamental misunderstandings here.

What prevents a cache miss isn’t being sequential (or even contiguous). It’s having a footprint that fits in a cache page (and the luck to get that footprint placed on only one page).

A random ordering wouldn’t change the size of the footprint. What might is interleaving different object types together. There’s no predicting this behavior under the Java spec. This is up to the flavor of JVM you ran this on.

The most reliable way to cause a cache miss is to allocate and access more than a cache page of memory.

3
  • You can answer closed questions? Interesting, but is that how things are supposed to be done?
    – JimmyJames
    Jan 30 at 18:43
  • @JimmyJames there's a race condition where if you start writing an answer before the question is closed there is a window in which you can still post the answer. It's not considered important enough to fix (which I agree with as a decision, not that anyone cares what I think) Jan 30 at 19:12
  • @PhilipKendall I got a pop-up in the browser when I was writing my answer. Does that mean if I had submitted it would be posted anyway?
    – JimmyJames
    Jan 30 at 19:15
2

Once profiling isolates a bottleneck following optimizations can be done:

  • increase available memory
  • vary garbage collection settings
  • parallelize
  • eliminate garbage collection by reusing objects
  • use primitives and arrays instead of objects
  • delegate computations to other languages

Example:

ArrayList<Point> points = new ArrayList<>();

becomes

double[] x = new double[1000], y = new double[1000];;

Not the answer you're looking for? Browse other questions tagged or ask your own question.