- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
typedef unsigned int uint;
uint inc(uint i) {
return i+1;
}
uint dec(uint i) {
return i-1;
}
uint add(uint a, uint b) {
return 0==b ? a : add(inc(a),dec(b));
}
inline uint _mul(uint a, uint b, uint r) {
return 0==b ? r : _mul(a,b-1,r+a);
}
uint mul(uint a, uint b) {
return _mul(a,b,0);
}
uint dec_mul(uint a, uint b, uint r) {
return 0==b ? r : dec_mul(a,dec(b),r+a);
}
//gcc 7 здесь сходит с ума на O3, шланг невозмутимо ставит imul edi, esi
uint crazy_mul(uint a, uint b, uint r) {
return 0==b ? r : crazy_mul(a,dec(b),add(r,a));
}
//арифметическая прогрессия.
inline uint _sum(uint a,uint s) {
return a==0 ? s :_sum(a-1,s+a);
}
//gcc: сложна нипанятна
uint sum(uint a) {
return _sum(a,0);
}
//шланг:
// imul rcx, rax
// shr rcx
uint sum1(uint a) {
uint s=0;
for (int i=0;i<a;++i){
s+=i;
}
return s;
}
1. Транслируем bf в сишку
2. Компилим сишку шлангом или скармливаем bf напрямую в llvm.
3. Получаем оптимизированный и человекочитаемый asm-выхлоп.
...
PROFIT
Есть кстати пара декомпиляторов на основе LLVM: snowman и retdec
узнал я про эту хрень из https://yurichev.com/writings/SAT_SMT_draft-RU.pdf
но все это работает далеко неидеально
Оптимизируем сложение. O(log(N))
Эвристики в clang 5/gcc7 не обучены булевой алгебре 🙁
Единственное - непонятно, зачем вообще распознавать, скажем, арифметическую прогрессию. Или это часть какого-то более общего метода оптимизации?
В теории разница должна быть примерно в 1 такт в пользу второго варианта. На практике по отдельности второй вариант в полтора раза быстрее, а внутри тех самых фунций - второй вариант медленнее на несколько порядков. С чем связано?
movddup - double precision
Вообще не въеду: какой смысл делать xorps над плавающей точкой.
movddup - грузит 64 бита в обе части xmm
Второй код попахивает безумием: грузим в xmm каких-то плавающих питухов, делаем на них xor, а потом складываем.
Причём что в xmm2 вообще непонятно!
Шикарный трюк.
Похожие симптомы:
http://web.archive.org/web/20120415131601/http://x264dev.multimedia.cx:80/archives/201
With data caches, despite what I said in the previous article, you still have a good bit of control. You can prefetch data to them explicitly using the prefetch instructions. You control memory allocation and can make all sorts of changes to potentially improve access patterns. Every single memory access is explicit by you in your code.
But it isn’t the same with the L1 code cache (L1I). You can’t prefetch to them at all; the prefetch instructions go to the L1 data cache, not the L1 code cache. Unless you write everything directly in assembly, you can’t control the allocation and layout of the code. And you don’t control access to the code at all; it is accessed implicitly when it is run.
Many readers may have heard stories of programs running faster with gcc’s -Os (optimize for size) than -O2 or -O3 (optimize for speed); this is why. Larger code size causes more L1I cache misses, more load on the L2->L1 memory load unit, and uses up L2 cache as well. While the naive programmer may see great advantage to lots of loop unrolling or inlining, even timing the code may not be sufficient to prove that such code-size-increasing optimizations are worthwhile, since other parts of the program called afterwards could suffer due to evictions from the L1 instruction cache.
https://godbolt.org/g/CmVFeB
Немного оптимизируем, учитывая что не только 0²=0, но и 1²=1;
Извиняйте, паралелльных сумматоров не подвезли.
К сожалению
https://gcc.godbolt.org/z/Tv88c4G93
Исправил:
Быстрее чем рекурсивный вызов inc/dec.
Там O(N), а здесь O(log₂N)