21 ms·
Not to be mean to the author, but this is an example of why it's generally useless to try to resort to assembly to beat a compiler unless you're an expert at as
by jcranmer 9y ago
Not to be mean to the author, but this is an example of why it's generally useless to try to resort to assembly to beat a compiler unless you're an expert at assembly. The sort of case that's being optimized here--a straight-line piece of assembly--is the case where compilers are going to do better than hand-coded except in specific cases.
The first critical failure is using the source code to guide assembly optimization, rather than the original generated assembly. It means that you're going to miss what optimizations the compiler is doing to improve this, and missing those optimizations is going to turn out worse than the original.
There are two main optimizations that come to mind. The first is instruction scheduling. On newer CPUs (Haswell or later), you have two separate instruction ports for vector ALU instructions, so you can execute two instructions in parallel if there are no conflicts. If you interleave the instructions for computing the denominator and the numerator, you can take advantage of the twin execution ports and execute two instructions at once instead of two (you use more registers though). This is the main optimization that I'm sure the Go library is getting.
The other possible optimization is SLP vectorization: the numerators and denominators are both polynomial interpolation, so they're doing the same operations on data vectors. This means that you can stick both of them in the vector and use one instruction to compute the operation for numerator and denominator simultaneously. On the other hand, it's not immediately clear if the extra cost in vector formation is going to be worth the win in speed, particularly given that you can already simultaneously schedule the two instructions in the first operation. I don't know if Go is applying this optimization.
So if you're wondering why it's slower, it's almost certainly that the hand-written assembly is actually poorly scheduled.
- dvt 9y ago> So if you're wondering why it's slower, it's almost certainly that the hand-written assembly is actually poorly scheduled. The assembly is slower because Go doesn't inline it. The overhead is obvious when calling one-op assembly blocks[1]. The proposal to inline assembly was rejected last year[2] by Russ Cox. [1] https://lemire.me/blog/2016/12/21/performance-overhead-when-calling-assembly-from-go/ https://lemire.me/blog/2016/12/21/performance-overhead-when-... [2] https://github.com/golang/go/issues/17373 https://github.com/golang/go/issues/17373
- wolfgang42 9y agoThanks for the link to the issue. I was wondering why the post was talking about function call overhead instead of being able to inline it.
- agnivade 9y ago> but this is an example of why it's generally useless to try to resort to assembly to beat a compiler unless you're an expert at assembly. Yes I realized ! Expert ? Not even close. I barely know a thing or two in assembly. The fact that I even managed to make it run amazes me. This was my first time venturing into the assembly land. It was just something which I wanted to give a shot and hopefully learn something at the end of the day, which I did. The 2 optimizations that you are talking about - I am totally clueless about them :) It's totally possible that if whatever you are saying is done, we may see better gains. Hopefully, some good samaritan who is better at this than me will be willing to give this a shot and see where it gets us.