6 ms·
Branchless code sequences
- wsxcde 11y agoScanning http://www.hackersdelight.org/aha/aha.pdf http://www.hackersdelight.org/aha/aha.pdf, it looks like Aha performs some form of exhaustive search over all programs? An SMT solver is probably a better way of doing this search; there's been some work in this direction. Jha, Gulwani and colleagues have a very nice paper on oracle-guided synthesis. They show how you can generate loop-free bitvector programs using SMT: http://www.eecs.berkeley.edu/~sseshia/pubdir/synth-icse10.pdf http://www.eecs.berkeley.edu/~sseshia/pubdir/synth-icse10.pd.... John Regehr has also written about this on his blog: http://blog.regehr.org/archives/1146 http://blog.regehr.org/archives/1146. Part of the complexity here in an SMT solution might be encoding all the bizarre instructions that you could possibly take advantage of in x86-like instruction sets.
- TheLoneWolfling 11y agoNever underestimate the utility of brute force & ignorance.
- murbard2 11y agoThe advantage of brute force generation is that you can eliminate a lot of solutions extremely fast by trying random inputs.
- beeworker 11y agoAha reminds me of STOKE: https://github.com/StanfordPL/stoke-release https://github.com/StanfordPL/stoke-release
- caf 11y agoJohn Regehr's most recent post is also on an example superoptimisation - in this case one where the generated answer isn't obviously correct. http://blog.regehr.org/archives/1219 http://blog.regehr.org/archives/1219
- haberman 11y agoInteresting, I'd never heard of the technique of searching all possible instruction sequences to find one with desired characteristics. It's the Infinite Monkey Theorem for code.
- molyss 11y agoHere's the original paper on super optimization by Alexia Massalin : http://courses.cs.washington.edu/courses/cse501/15sp/papers/massalin.pdf http://courses.cs.washington.edu/courses/cse501/15sp/papers/... I ran into it a couple years ago, after hearing from other research from her. Her papers are really impressive. I would have loved that the author of the article had mentioned her. On a side note, I wouldn't be surprised if the JIT compilers were doing some use of this, allowing some interpreted language to have better performances than compiled C on some benchmarks EDIT : formatting and JIT addition
- kevinnk 11y agoJIT compilers are time constrained so super optimization isn't a very good match.
- chrisseaton 11y agoWhy are JIT compilers time constrained? If you have a banking system that runs all day every day, why does it matter if it takes 5 minutes to compile the hot spots at the top tier of optimisation?
- oso2k 11y agoImagine you happen to walk up to your ATM when it's Mother Banking System is in the middle hotspot compile followed by a GC pause. What would you do if your ATM took 5 minutes+ to respond to your Withdrawal Request? You'd probably freak out and worry about getting ATM card back.
- chrisseaton 11y ago
- darkmighty 11y agoAnyone know why compilers don't already do this for small branches? Not worth the effort?
- lysium 11y agoI'd say probably too much effort? First, it does an exhaustive search on all possible instruction combinations. Second, it does not _prove_ that the resulting instructions do the same as the original code. It shows it only for some random numbers and border cases.
- TheLoneWolfling 11y agoIt's fairly easy to extend this to either an exhaustive search afterwards, or to run into a SMT solver to prove that it's correct / incorrect. Though that's probably too much machinery to add on to a compiler.
- Guvante 11y agoThere has been talk of using superoptimizers in larger compilers however it is usually not worth the effort unless you know a problem case in particular. Especially since these kinds of transformations could slow down your code if the branch predictor is working well for your code set.
- adwf 11y agoHalting problem perhaps? Even if you put in safeguards, an exhaustive search could still be unacceptably slow. You can never tell when a pathological case might arise.
- rdc12 11y agoBoth GCC and Clang can compile to branchless solutions for some conditional statements. The FizzBuzz problem for example both GCC and Clang can turn that into a small lookup table
- AReallyGoodName 11y agoYou miss out on branch prediction. There's a bit of a myth that branches are always bad because a branch misprediction is slower than a correctly predicted branch and therefore no branches are better. A bit of code that eliminates branches but has dependant variables (A must be computed before B can be computed) will have pipeline stalls while the computation for A is completed. Yes it might be faster than a branch misprediction but it will never be as fast as a correctly predicted branch (which takes effectively 0 cycles). Notice the one thing missing in this post? Benchmarks!
- wehadfun 11y agowhat kind of a bump does this produce
- chipaca 11y agoGoosebumps.
- jamesrom 11y agoIs there any other reason to use a tool like this other than eliminating branch misprediction?
- rdc12 11y agoSuperoptimisers can be used on any sequance of instructions, to find a more optimial sequance. Since they approach the problem in a very different way to a compiler, it can do a better job in some cases. And it can work on hand written assembler too. They tend to be good at finding obscure solutions.
- andrewchambers 11y agoThis sort of thing was automated to entire binaries in this paper. http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf http://theory.stanford.edu/~aiken/publications/papers/asplos... They managed to beat gcc -O3 - "we show speedups from 1.7 to a factor of 10 on some compute intensive kernels"
- andrewchambers 11y agoO2* , here is a cached version http://webcache.googleusercontent.com/search?q=cache:http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf http://webcache.googleusercontent.com/search?q=cache:http://...