Making the obvious code fast (2016)

https://jackmott.github.io/programming/2016/07/22/making-obvious-fast.html

by GordonS • 7 years ago

109 39 7 years ago

jackmott.github.io

twic• 7 years ago

Java 8 includes a very nice library called stream which provides higher order functions over collections in a lazy evaluated manner, similar to the F# Nessos streams library and Rust. Given that this is a lazy evaluated system, it is odd that there is such a performance difference between map then sum and a single reduction. The reduce function is compiling down to the equivalent of SSE vectorized C, but the map then sum is not even close. It turns out that the sum() method on DoubleStream "may be implemented using compensated summation or other technique to reduce the error bound in the numerical sum compared to a simple summation of double values." A nice feature, but not clearly communicated by the method name!

As i said recently [1], the Java way is to sacrifice a little performance to allow users to do silly things and still get the right answer.

[1] https://news.ycombinator.com/item?id=19644366

gameswithgo4• 7 years ago

Since I wrote this, Rust did stabilize SIMD intrinsics, and using crates like https://github.com/AdamNiederer/faster or https://github.com/jackmott/simdeez you can write pretty idiomatic code to leverage them too.

Also I believe the browsers have sped up some of the Javascript cases shown there substantially.

sambe• 7 years ago

Does a more modern Rust/LLVM not auto-vectorize this?

timerol• 7 years ago

Yes. Rust 1.34.0 (and presumably earlier as well) generates an unrolled SIMD-loop for the iterator option: https://rust.godbolt.org/z/c6uZCv

apfel912• 7 years ago

Would be interesting to see how later versions of Node perform compared to v6 in the tests.

Node 8 especially, with turbofan.

tomohawk• 7 years ago

GC overhead almost always becomes an issue in performance or latency sensitive code. Raw timing benchmarks such as these do not capture that. It's mentioned in the article, but its worth emphasizing that the times on some of the higher order approaches may greatly understate the actual overhead of the approach.

GordonS• 7 years ago

That depends on whether any actual allocations take place - looking at the C# code samples in the article, the only ones that would cause allocations would be the ones that used Linq. And Linq is kind of verboten in performance sensitive code; I assume the author used Linq in a few samples precisely because they would cause allocations to demonstrate the perf disadvantage.

With the advent of Span, stackalloc and the like, there has been something of a "war on allocations" in .NET recently - it's great to see some extra focus on performance!

barrkel4• 7 years ago

What I would like to see is more of an attitude change among high level language designers and their communities.

The reason a language like C makes obvious code fast is because C has very little expressive power. The lack of power strongly encourages the programmer to think imperatively and code at a very low level. Apply this to an extremely trivial problem (mere addition - does it get any simpler?), and of course you end up with fast code.

The lesson doesn't generalize. The lack of expressive power means higher level abstractions are clumsy to write, refactoring is more expensive, and recomposing your program with e.g. a caching layer is much harder.

See https://blog.codinghorror.com/on-managed-code-performance-ag... for example (alas, it appears some of the original source blogs are gone) - Raymond Chen wrote a dictionary in C++, Rico Mariani implemented it in C# and and got great performance with the obvious solution.

tedunangst• 7 years ago

But isn't the point that sufficiently smart compilers are supposed to compile to faster than C?

barrkel4• 7 years ago

Are you being facetious? :) "Sufficiently smart compiler" - http://wiki.c2.com/?SufficientlySmartCompiler

Don't get me wrong, I like C - especially on small problems. I don't get the feeling that I'm creating something flexible with C, though, it's very much bespoke and tailored. I get involved in micromanagement of fine details. This is OK for a small problem, but extremely aggravating for a big problem. As soon as I want higher level abstractions, and start building structs of function pointers and whatnot, I just shake my head - I'd rather write a parser and corresponding text generator than manually compile that into C.

C++ has been hobbled by the concept of a sufficiently smart compiler. It's so afraid of introducing abstractions that aren't cost-free, it tries to make them all optional, and the resulting explosion in feature combination means some combinations don't work well together, and then every big C++ project has to decide which set of features they'll adopt, and which ones they won't.

Give me the freedom to think closer to the problem, and even if the abstractions have some costs, and even if the compilers aren't quite sufficiently smart, the chances are I'll come up with algorithm improvements that meet speed and space requirements and let me move on to the next problem much sooner. Agility trumps hyper-optimization.

maxxxxx2• 7 years ago

That has been the dream for a long time. When Java introduced JIT (Hotspot?) a lot of people claimed that Java was faster than C. Lately people are telling me that JavaScript "can" run faster than C. Usually they present some well written code in their favorite language and then compare it to horribly written C. Usually I tell them that most likely the runtime of their language is written in C so you can always do as well in C.

kingaillas• 7 years ago

See https://blog.codinghorror.com/on-managed-code-performance-ag.... for example (alas, it appears some of the original source blogs are gone)

They are there... it's just the recent migration at MSDN blogs broke a lot of links. Basically it looks like Rico doesn't blog anymore (no longer at Microsoft) so his blog is archived and links to it work, but Raymond Chen's blog is active and was moved en masse to new links.

The links from Rico Mariani's blog (https://blogs.msdn.microsoft.com/ricom/2005/05/10/performanc...) are here:

Raymond Chen's posts:

https://devblogs.microsoft.com/oldnewthing/20050509-30/?p=35...

https://devblogs.microsoft.com/oldnewthing/20050510-55/?p=35...

https://devblogs.microsoft.com/oldnewthing/20050511-46/?p=35...

https://devblogs.microsoft.com/oldnewthing/20050513-26/?p=35...

https://devblogs.microsoft.com/oldnewthing/20050516-30/?p=35...

https://devblogs.microsoft.com/oldnewthing/20050518-42/?p=35...

https://devblogs.microsoft.com/oldnewthing/20050519-00/?p=35...

gameswithgo4• 7 years ago

Rust managed to make some of these high level abstractions compile to fast machine code almost every time. Its quite refreshing to go from Linq/Streams etc to Rust iterators.

So does C++ iterators for that matter but they are not so pleasant to actually write.

barrkel4• 7 years ago

It's true. Rust's approach to passing lambdas to iterators usually gives the compiler good info to inline. Some of my exercise programs when learning Rust exceeded fairly straightforward C implementation too, possibly due to stronger guarantees around aliasing.

stygiansonic• 7 years ago

As for the section on Java, Java can indeed auto-vectorize certain loops, but the loops have to be "simple". Something like this would work:

    for (int i = 0; i < x.length; i++) {
        z[i] = x[i] * y[i];
    }

(Above code copied from: http://prestodb.rocks/code/simd/ )

But the reason it doesn't work for the article's code is because of the accumulator variable. That is not supported yet. See: https://bugs.java.com/bugdatabase/view_bug.do?bug_id=7192383

However, the difference between using sum() and reduce() are interesting. Will eventually have to JMH to verify if this is still the case and if it matters in our codebase.

jerf• 7 years ago

You can get to SIMD in Go via assembly support: https://goroutines.com/asm I would give a pretty decent guess it'd also score 17 ms since it'll be the same inner loop as everything else.

How you score that in terms of "support" I freely leave up to the reader. Go assembly does integrate into Go more than simply raw assembler would, as it handles some of the runtime concerns, so the "support" is more than just "yeah, we can write some stuff in assembler and link it in, I can do that anywhere", but on the other hand, it is a form of assembler, not something that looks like a function call in the native language or something.

chrchang523• 7 years ago

Yes, it's clumsier than intrinsics, but ever since Go 1.10 added mnemonic support up to AVX2, I've found it usable enough. (And it's easier to efficiently exploit multiple processor cores in Go than most other languages...)

hyperpape• 7 years ago

It would be a nice update to redo the Java examples with both Hotspot and Graal, as many (but not all) of the cases where Graal outperforms Hotspot are in how it optimizes higher order functions. I don't have an intuition whether it would matter for these particular examples, but I'd like to see.

emsy2• 7 years ago

Tangential to Jon Blow mentioned in the post is the Handmade Network, which advocates for better programming by sticking closer to the hardware. While I think this is a worthwhile and noble effort, I think what this post really shows is that we need better tools to help developers to do the right thing more effortlessly.

jstimpfle3• 7 years ago

What is "the right thing", though? When requirements get more and more complex, "better tools" stop working. Their built-in mechanisms are not the answer to anything and everything. Beyond some complexity treshold, you can't do with generic solutions, but need to tailor solutions to the problem.

emsy2• 7 years ago

There is no hidden depth in "the right thing": perform the intended action with as little time/memory complexity as possible. I disagree completely with what you're saying. If anything, the examples in the post show we still have a lot of opportunities to build better tools at the micro level. We didn't even try To build better tools for complex systems yet.

bufferoverflow• 7 years ago

I tried JS in chrome, and the best I got was 78ms on i7-8750H

    <script>
    let arr = new Float64Array(32000000);
    let sum = new Float64Array(1);
    sum[0] = 0;
    let l = arr.length, i, el;
    // Initialize with radom values
    for (i=0; i<l; i++) arr[i] = Math.random();

    // Sum
    let st = performance.now();
    for (i=0; i<l; i++) sum[0] += arr[i] * arr[i];
    let en = performance.now();
    console.log(en - st, sum[0]);
    </script>

Using a temporary value for arr[i] is definitely slower.

wilgertvelinga• 7 years ago

I created a jsbench of the JavaScript tests: https://jsbench.me/80jule61z5/1

Gajurgensen• 7 years ago

Rust achieves impressive numbers with the most obvious approach. This is super cool. I feel that this behavior should be the goal for any language offering these kinds of higher order functions as part of the language or core library.

Certainly it should be a goal, but I don't think it should be the goal. Higher levels of abstraction aren't typically motivated by performance. The priority is ease of expression and reasoning about code. Of course both are desirable, but when the two are in conflict and a trade off is necessary, designers will lean toward expressive abstractions, not performant abstractions. After all, performance is already available without the abstractions.

But I do agree it is super cool how Rust finds a sweet spot between performance and expressibility. It is one of my favorite languages for that reason. I just don't think it should be a universal goal.

apocalypses• 7 years ago

Swift can also auto vectorise these simple loops, but only with the right combination of compiler flags.

https://swift.godbolt.org/z/JmtOMx

carapace• 7 years ago

FWIW, working in the Joy language you could write this:

    [dup *] map sum

And given the definition of sum (the Joy combinator step is like fold),

    sum == 0 swap [+] step

There could be a (pre-)compilation transform that generated:

    0 swap [dup * +] step

From which the proverbial "sufficiently smart compiler" would generate SIMD instructions. (I'm working on that now, in Prolog. At this point the type-inferencer can already tell that this function expects a list of numbers and returns a single number (it's a "Catamorphism"[1].) But I'm nowhere near specializing the output code to SIMD. My target architecture is Prof. Wirth RISC machine for Project Oberon. However, there's a body of research on Prolog compilation that includes work on retargeting machine code generator generators, so there's that.)

[1] http://joypy.osdn.io/notebooks/Recursion_Combinators.html

pjmlp2• 7 years ago

Intel has contributed SIMD support to Hotspot and it is available since Java 10, including AVX.

Likewise Google, Azul and IBM have SIMD support on their JIT/AOT compilers.

Making the obvious code fast (2016)

Related Stories