3 ms·
I've recently been trying to write some very fast x64 assembly, and have been thinking about this quite a bit. I think one could get substantial improvement ev
by nkurz 14y ago
I've recently been trying to write some very fast x64 assembly, and have been thinking about this quite a bit. I think one could get substantial improvement even with the simpler approach of just reordering the code. With modern processors, small changes in number of instructions have much less impact than how well they interact with the superscalar nature of the CPU. And while out-of-order processing helps diminish this, the order of instructions still matters a lot.
Instead of trying lots of random orders and seeing if they work produce the right result, my thought is to generate a data dependency graph of the instructions, and then enumerate all possible topological sorts of this DAG. There's a classic 1974 Knuth typewritten Knuth paper on generating all the sortings efficiently: http://www.cs.ncl.ac.uk/publications/trs/papers/61.pdf http://www.cs.ncl.ac.uk/publications/trs/papers/61.pdf
Generating the dependency graph is difficult in the general case, but should be simple enough if we presume branch-agnostic and alias-free code. As long as the dependency graph is correct, all the orderings should work. Thus if one of them doesn't, I'll know immediately that the graph is wrong. Since I only need to generate the graph once, this step doesn't need to be particularly fast.
Then I'll directly generate assembly for each of these orderings. For speed, and since I already have the machine code, I'm planning to write the bytes directly memory. Then instead of analyzing the code and estimating the processors front-end scheduler, I'll just call each function and time it using RDTSC or a a comparable on-die performance counter. As the timer is cycle-accurate, I shouldn't need many if any iterations.
This should be straightforward in C, and apparently possible in the standard scripting languages using libffi: http://stackoverflow.com/questions/6143042/how-can-i-call-inlined-machine-code-in-python-on-linux http://stackoverflow.com/questions/6143042/how-can-i-call-in.... Then I'll save and write out the fastest one.
To keep it simple, it would be nice to outsource the heavy lifting to existing libraries and programs. Their availability might dictate my choice of language. I'm most comfortable with Python, Perl or C, but something else might be fun if all the tools are available. Here's my current list of potential tools:
For disassembly, DiStorm from Python or C. Haven't found anything great for Perl. Maybe X86::Udis86? Maybe just parse 'objdump -d'? My needs are very simple since I'll already have machine code.
For calling assembly, wrappers for libffi if using Perl or Python; nothing needed for C. I guess this could be trickier if I want to consider different alignments, but I think I'll start without.
For timing, I don't think it's usually possible to call RDTSC from Python or Perl, but since I'm planning to be able to execute arbitrary assembly, this shouldn't be any harder to add. A much more travelled path in C, though
For generating all the possible topological sortings, I'll just write something following Knuth's approach. It would be nice if I could generate and call the functions from the sorting algorithm so I can monitor progress and start getting results sooner.
I think my weakest part is generating the dependency graph. I'm willing to cut corners on this by making lots of assumptions about the code, but it needs to be right. I can parse the output from Intel's IACA if necessary, but would be nice to have something more easily available. Are there libraries that do this?
Suggestions and alternative approaches greatly appreciate. My thought is that once it works, it shouldn't be that hard to add some of the "substitute different code" approaches. I like the idea of having a database of approaches one could try out. Of course, what I really hope is that something exactly like this already exists, and I'm just searching by the wrong terms.