1. Си / Говнокод #23832

    +2

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 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, 27 Февраля 2018

    Комментарии (27) RSS

    • Кстати так же можно деобфусцировать брейнфак-программы.
      1. Транслируем bf в сишку
      2. Компилим сишку шлангом или скармливаем bf напрямую в llvm.
      3. Получаем оптимизированный и человекочитаемый asm-выхлоп.
      ...
      PROFIT
      Ответить
      • Нихрена не выйдет т.к. шланг тоже говно, и для продвинутых символьных вычислений не предназначен. Тут надо по-хорошему придумывать какую-то систему символьных вычислений с SMT решателями и эвристиками, встроенным ИИ.
        Есть кстати пара декомпиляторов на основе LLVM: snowman и retdec
        Ответить
        • А да, есть еще такая вот поебень https://klee.github.io/
          узнал я про эту хрень из https://yurichev.com/writings/SAT_SMT_draft-RU.pdf
          Ответить
          • Годно. А это smt z3 умеет в высокие степеня, тригонометрию, экспоненты или ограниченно только линейными задачками?
            Ответить
            • Ну как... Возведение в степень есть, синусы-косинусы-экспонетны тоже есть. Есть nonlinear real arithmetic (NLSat) в этом z3:
              https://github.com/Z3Prover/z3/blob/master/src/nlsat/nlsat_solver.cpp
              https://www.microsoft.com/en-us/research/publication/solving-non-linear-arithmetic/

              но все это работает далеко неидеально
              Ответить
      • кстати, а реально ли готовый бинарь дизассемблировать, преобразовать в код на си, а потом скомпилить так, чтобы новый бинарь был оптимальнее старого?
        Ответить
    • Продолжаем упарываться.
      Оптимизируем сложение. O(log(N))
      uint add2(uint a,uint b){
         return 0==a ? b : add2((a&b)<<1,a^b);
      }

      Эвристики в clang 5/gcc7 не обучены булевой алгебре :(
      add2:                                   # @add2
              test    edi, edi
              je      .LBB0_2
      .LBB0_1:                                # =>This Inner Loop Header: Depth=1
              mov     eax, esi
              and     eax, edi
              add     eax, eax
              xor     esi, edi
              test    eax, eax
              mov     edi, eax
              jne     .LBB0_1
      .LBB0_2:
              mov     eax, esi
              ret
      Ответить
    • Ничего себе.

      Единственное - непонятно, зачем вообще распознавать, скажем, арифметическую прогрессию. Или это часть какого-то более общего метода оптимизации?
      Ответить
    • о, как раз в тему тред. У меня буквально сегодня было: две версии функции, в бинарнике отличаются минимальным куском кода:
      // 1
      movlps xmm0, QWORD PTR [rdi+r8*8]
      add r8, rdx
      movlps xmm1, QWORD PTR [rdi+r8*8]
      movaps xmm2, xmm0
      addps xmm0, xmm1
      subps xmm2, xmm1
      movlhps xmm0, xmm2
      movaps XMMWORD PTR [rsi+rax*8], xmm0
      
      // 2
      lea r9, [r8+rdx]
      movddup xmm0, QWORD PTR [rdi+r8*8]
      movddup xmm1, QWORD PTR [rdi+r9*8]
      xorps xmm1, xmm2
      addps xmm1, xmm0
      movaps XMMWORD PTR [rsi+rax*8], xmm1

      В теории разница должна быть примерно в 1 такт в пользу второго варианта. На практике по отдельности второй вариант в полтора раза быстрее, а внутри тех самых фунций - второй вариант медленнее на несколько порядков. С чем связано?
      Ответить
      • movlps - single precision питух
        movddup - double precision

        Вообще не въеду: какой смысл делать xorps над плавающей точкой.
        Ответить
        • movlps - грузит 64 бита в младшую часть xmm
          movddup - грузит 64 бита в обе части xmm
          Ответить
          • С первым все понятно. Сложили, вычли, записали в память две суммы (нижняя часть xmm0) и две разности (верхняя часть xmm0).

            Второй код попахивает безумием: грузим в xmm каких-то плавающих питухов, делаем на них xor, а потом складываем.
            Причём что в xmm2 вообще непонятно!
            Ответить
            • 3агрузил плавающих питухов тебе за щеку, проверь.
              Ответить
            • Данные - флоаты
              movddup xmm0, QWORD PTR [rdi+r8*8] // xmm0 = {f0, f1, f0, f1}
              movddup xmm1, QWORD PTR [rdi+r9*8] // xmm1 = {f2, f3, f2, f3}
              xorps xmm1, xmm2 // xmm2 = {0.f, 0.f, -0.f, -0.f} => xmm1 = {f2, f3, -f2, -f3}
              addps xmm1, xmm0 // xmm1 = {f0+f2, f1+f3, f0-f2, f1-f3}
              Ответить
      • >На практике по отдельности второй вариант в полтора раза быстрее, а внутри тех самых фунций - второй вариант медленнее на несколько порядков. С чем связано?

        Похожие симптомы:
        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.
        Ответить
        • Хотя не. Второй же кейс меньше по размеру.
          Ответить
        • вряд ли размер пары инструкций повлияет на общий объем кода так, чтобы получить стабильный кеш мисс в коде от запуска к запуску на разных компах.
          Ответить
      • короче в чем была трабла: замена movlhps на что угодно из loadups/loaddup/movsd/... пр. влекло к тому, что подавлялся loop dependency на xmm регистре. Из-за этого GCC пытался оптимизнуть код лучше, а получалось как всегда - пережевывалась другая часть функции. Решилось в итоге явным указыванием в каких регистрах хранить опред. переменные
        Ответить
    • Упарываюсь дальше.

      https://godbolt.org/g/CmVFeB
      uint sqr(uint i){    return (i<1) ? i : (2*i-1)+sqr(i-1);  }

      sqr:                                    # @sqr
              test    edi, edi
              je      .LBB0_1
              lea     eax, [rdi - 1]
              lea     ecx, [rdi + rdi - 3]
              imul    ecx, eax
              mov     edx, edi
              add     edx, -2
              imul    edx, eax
              and     edx, -2
              lea     eax, [rcx + 2*rdi - 1]
              sub     eax, edx
              ret
      .LBB0_1:
              xor     eax, eax
              ret


      Немного оптимизируем, учитывая что не только 0²=0, но и 1²=1;
      uint sqr(uint i){    return (i<2) ? i : (2*i-1)+sqr(i-1);  }

      sqr:                                    # @sqr
              push    rbx
              mov     ebx, edi
              cmp     ebx, 2
              jae     .LBB0_1
              mov     eax, ebx
              pop     rbx
              ret
      .LBB0_1:
              lea     edi, [rbx - 1]
              call    sqr
              lea     eax, [rax + 2*rbx - 1]
              pop     rbx
              ret
      Ответить
    • Реализация инкремента.
      Извиняйте, паралелльных сумматоров не подвезли.
      typedef unsigned int uint;
      
      uint halfsum(uint a, uint carry)
      {
          return 0==(carry & a) ? (a | carry) : halfsum(a^carry, carry<<1);
      }
      
      uint inc(uint i) 
      {
          return halfsum(i, 1);
      }


      К сожалению
      https://gcc.godbolt.org/z/Tv88c4G93
      Ответить
      • //в carry должен быть установлен ровно один бит
        function halfsum(a, carry)
        {
            return 0==(carry & a) ? (a | carry) : halfsum(a^carry, carry<<1);
        }
        
        //прибавляет единичные биты, вычлененные (b&-b)
        // b & (b-1); стирает младший единичный разряд 
        function add3( a, b)
        {
            return 0==b ? a : add3( halfsum(a, b&-b) , b & (b-1) );
        }
        Ответить
        • Непорядок. В ральзации сложения использовался декремент (b-1)
          Исправил:
          function add3( a, b)
          {
              low = b&-b;
              return 0==b ? a : add3( halfsum(a, low) , b ^ low );
          }
          Ответить
    • Ещё Сложение
      uint add2(uint a,uint b)
      {
         return 0==a ? b : add2((a&b)<<1, a^b);
      }

      Быстрее чем рекурсивный вызов inc/dec.
      Там O(N), а здесь O(log₂N)
      Ответить
    • https://www.doxdesk.com/img/updates/20091116-so-large.gif
      Ответить
    • vStart building cross-platform apps with .NET Multi-platform App UI (.NET MAUI).
      Ответить

    Добавить комментарий