- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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;
}
Смотрим как компиляторы решают разные упоротые рекурентные задачки.
https://godbolt.org/g/4JZuPr
3.14159265 28.02.2018 00:00 # +3
1. Транслируем bf в сишку
2. Компилим сишку шлангом или скармливаем bf напрямую в llvm.
3. Получаем оптимизированный и человекочитаемый asm-выхлоп.
...
PROFIT
j123123 28.02.2018 06:43 # +2
Есть кстати пара декомпиляторов на основе LLVM: snowman и retdec
j123123 28.02.2018 06:47 # +1
узнал я про эту хрень из https://yurichev.com/writings/SAT_SMT_draft-RU.pdf
3.14159265 28.02.2018 16:47 # 0
j123123 28.02.2018 17:08 # 0
но все это работает далеко неидеально
Antervis 02.03.2018 12:15 # 0
3.14159265 28.02.2018 00:08 # +4
Оптимизируем сложение. O(log(N))
Эвристики в clang 5/gcc7 не обучены булевой алгебре :(
Steve_Brown 28.02.2018 10:55 # 0
Единственное - непонятно, зачем вообще распознавать, скажем, арифметическую прогрессию. Или это часть какого-то более общего метода оптимизации?
Antervis 28.02.2018 16:43 # 0
В теории разница должна быть примерно в 1 такт в пользу второго варианта. На практике по отдельности второй вариант в полтора раза быстрее, а внутри тех самых фунций - второй вариант медленнее на несколько порядков. С чем связано?
3.14159265 28.02.2018 16:49 # 0
movddup - double precision
Вообще не въеду: какой смысл делать xorps над плавающей точкой.
Antervis 28.02.2018 16:54 # 0
movddup - грузит 64 бита в обе части xmm
3.14159265 28.02.2018 17:03 # +1
Второй код попахивает безумием: грузим в xmm каких-то плавающих питухов, делаем на них xor, а потом складываем.
Причём что в xmm2 вообще непонятно!
g0_1494089135835 28.02.2018 17:07 # 0
Antervis 28.02.2018 17:55 # +3
3.14159265 28.02.2018 18:23 # +1
Шикарный трюк.
HoBorogHuu_nemyx 16.01.2020 15:57 # 0
3.14159265 28.02.2018 18:30 # +2
Похожие симптомы:
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.
3.14159265 28.02.2018 18:37 # 0
Antervis 28.02.2018 18:37 # 0
Antervis 02.03.2018 12:19 # +2
3.14159265 28.02.2018 19:59 # +2
https://godbolt.org/g/CmVFeB
Немного оптимизируем, учитывая что не только 0²=0, но и 1²=1;
3.14159265 21.07.2022 01:26 # 0
Извиняйте, паралелльных сумматоров не подвезли.
К сожалению
https://gcc.godbolt.org/z/Tv88c4G93
3.14159265 21.07.2022 02:29 # 0
3.14159265 21.07.2022 02:36 # 0
Исправил:
3.14159265 21.07.2022 01:53 # 0
Быстрее чем рекурсивный вызов inc/dec.
Там O(N), а здесь O(log₂N)
3.14159265 21.07.2022 02:18 # 0
guest6 21.07.2022 02:29 # 0