It doesn't add up
Jun. 15th, 2019 12:18 pmIn 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
The concurrency stuff that I didn't know turns out to be easy enough. I had
The big winner is letting streams do the concurrency. Instead of 40 or 50 lines, you can just do this:
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
So the conclusions are nothing to get excited about.
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 Callable
s and give me some Future
s 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!