It doesn't add up

In a job interview, I was asked about summing a list of numbers. It's a simple task, but we went through things that could go wrong and how to mitigate those issues. I didn't do so well on improving performance with concurrency (and I didn't get the job) so afterwards I had a play with that. I wrote various list summing methods and summed some huge lists. Here's what I learned.

It's a truism that premature optimisation is the root of all evil. But I've always used LinkedList instead of ArrayList because "it's faster" - you never have to copy the elements into a new array as it grows. It turns out that it's ArrayList that's faster. You can sum elements two or three times as fast. I was expecting random access on LinkedList to be awful - O(n^2) - and it was spectacularly bad for large lists, so I avoided that. But for iteration as well, it was much slower. Maybe it's because LinkedList has more indirection - there's a wrapper around an element. The counter argument is that for small lists, the difference isn't worth bothering about.

The concurrency stuff that I didn't know turns out to be easy enough. I had ExecutorService process a bunch of Callables and give me some Futures with partial sums. It's annoying to think that I might have had a job offer if I'd said the previous sentence in the interview. I was disappointed that it's almost as much code to write as the old-skool method that I did know - creating some threads and wait for them to complete.

The big winner is letting streams do the concurrency. Instead of 40 or 50 lines, you can just do this:

private static long addListStreamParallel(List<Integer>list){
   return list
      .stream()
      .parallel()
      .mapToLong(a->a)
      .sum();
}

Simple!

None of the methods of making it concurrent was necessarily faster. I assume that's because the amount of computation per list element is small (add a number to a total) so the overhead of making it parallel is large. Curiously, it seemed to get slightly quicker for ArrayList but quite a bit slower for LinkedList but, er, doesn't that contradict the assumption that I just made?

So the conclusions are nothing to get excited about.

• Write correct code first and optimise only when you know it's too slow.
• Everything you thought you knew about performance is supposition.
• You only know if it's too slow by instrumenting the relevant bit of code and running lots of tests.
• Less code is better, even if it's not the fastest. Use that streams thing!