4 ms·
You can run an agent in a loop, but for something this small you can already use a SAT solver or superoptimizer if you want to get out of the business of thinki
by astrange 1y ago
You can run an agent in a loop, but for something this small you can already use a SAT solver or superoptimizer if you want to get out of the business of thinking about things yourself.
I've never seen anyone actually do it, mostly because modeling the problem is more work than just doing it.
- ksclk 1y ago> you can already use a SAT solver Could you elaborate please? How would you approach this problem, using a SAT solver? All I know is that a SAT solver tells you whether a certain formula of ANDs and ORs is true. I don't know how it could be useful in this case.
- dragontamer 1y agoPretty much all instructions at the assembly level are sequences of AND/OR/XOR operations. SAT solvers can prove that some (shorter) sequences are equivalent to other (longer) sequences. But it takes a brute force search. IIRC, these super optimizing SAT solvers can see patterns and pick 'Multiply' instructions as part of their search. So it's more than traditional SAT. But it's still... At the end of the day.... A SAT equivalence problem.
- peaboff 1y agoWhat you're saying is true. Yes you can grind away at generating sequences of instructions, SAT solve equivalence and benchmark, but of course, you would sooner see all black holes in the observable universe evaporate before you find an instruction sequence that is both correct AND 100x faster.
- agent327 1y agoA short look at any compiled code on godbolt will very quickly inform you that pretty much all instructions at the assembly level are, in fact, NOT sequences of AND/OR/XOR operations.
- valkon 1y ago[dead]
- dragontamer 1y agoAll instructions are implemented with logic gates. In fact. All instructions today are likely NAND gates. Have you ever seen a WallaceTree multiplier? A good sequence that shows how XOR and AND gates can implement multiply. Now, if multiply + XOR gets the new function you want, it's likely better than whatever the original compiler output.
- saagarjha 1y agoComputers are not programmed on the level of logic gates. If you want to do that, design an FPGA.
- dragontamer 1y agoSuperoptimizers take this stuff into consideration. Which is what the parent post was talking about, the rare superoptimizer.
- agent327 1y agoThat was not the claim. The claim was that assembler was made up out of sequences of OR/AND/XOR, and that claim is demonstrably false.
- astrange 1y ago"Made up of" isn't helpful. All assembly languages are equivalent to a sequence of bit operations. (…if you ignore side effects and memory operations.) In fact there's several different single operations you can build them all out of: https://en.wikipedia.org/wiki/One-instruction_set_computer#Instruction_types https://en.wikipedia.org/wiki/One-instruction_set_computer#I... So you take your assembly instructions, write a sufficiently good model of assembly instructions<>bit operations, write a cost model (byte size of the assembly works as a cheap one), and then search for assembly instructions that perform the equivalent operation and minimize the cost model. Like here: https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...
- dataangel 1y agoYou're a bit naive about the complexity. Commonly longer sequences are actually faster, not just because instructions vary in their speed, but also because the presence of earlier instructions that don't feed results into later instructions still affect their performance. Different instructions consume different CPU resources and can contend for them (e.g. the CPU can stall even though all the inputs needed for a calculation are ready just because you've done too many of that operation recently). And then keep in mind when I say "earlier instructions" I don't mean earlier in the textual list, I mean in the history of instructions actually executed; you can reach the same instruction arriving from many different paths!
- astrange 1y agoHmm, this usually doesn't come up simply because you're usually targeting multiple different CPU generations at once, and then the details cancel each other out. The most ffmpeg has had to do in this area is that some CPUs had very slow unaligned memory loads and some didn't.
- LtWorf 1y agoI see a guy who has never seen assembly explain assembly to people who have written assembly and written compilers and optimisations…