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

    +134

    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
    static U32 Round_up_to_next_2_power( U32 value )
{
  if ( value > 16 )
    if ( value > 64 )
      if ( value > 128 )
        if ( value > 256 )
          if ( value > 512 )
            return( 1024 );
          else
            return( 512 );
        else
          return( 256 );
      else
        return( 128 );
    else
      if ( value > 32 )
        return( 64 );
      else
        return( 32 );
  else
    if ( value > 4 )
      if ( value > 8 )
        return( 16 );
      else
        return( 8 );
    else
      if ( value > 2 )
        return( 4 );
  return( value );
}

    Simple function to round up to the next power of 2.

    Запостил: Wicked, 23 Мая 2014

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

    • ava myaut 23.05.2014 09:33 # 0

      Этому коду не хватает байтоебства.
      Ответить

    • ava wvxvw 23.05.2014 10:18 # 0

      Очень быстро сдался как-то. А вообще, если продолжить идею и переписать нормально, то вполне можно выиграть у байтоебских вариантов, зависит от распределения значений, к которым будет применятся функция.
      Ответить

      • ava bormand 23.05.2014 10:23 # +4

        > байтоебских вариантов
        Ну вот первый попавшийся байтоёбский вариант для 32 бит:
        n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;
        > переписать нормально
        > выиграть
        5 непредсказуемых условных переходов никак не могут быть быстрее 10 логических операций. Без шансов.
        Ответить

        • ava wvxvw 23.05.2014 10:32 # 0

          Если распределение равномерное, то половина попадет в if (value > 2^31), и вполне имеет шанс выиграть.
          Ответить

          • ava bormand 23.05.2014 10:36 # +3

            С точки зрения статистики - да, согласен, матожидание будет в районе 2 переходов.

            Но два непредсказанных перехода могут оказаться дороже этого десятка операций т.к. сбивают пайплайн...
            Ответить

            • ava wvxvw 23.05.2014 10:40 # 0

              Это уже детали архитектуры процессора. Может оказаться, а может и не оказаться. Кроме того, распределение не должно быть равномерным, может там Гаусс с сильным bias в сторону 2^31 и с большой peakedness (хз. опять же, как по-русски). Или вообще экспонентное распределение, типа power law / Zipf law сильно предпочитающее большие числа.
              Ответить

            • ava roman-kashitsyn 23.05.2014 10:48 # +1

              Имхо авторам подобных функций не желательно подразумевать какое-то распределение значений входных параметров.
              Ответить

            • ava 3.14159265 23.05.2014 17:58 # +1

              >Но два непредсказанных перехода могут оказаться дороже этого десятка операций т.к. сбивают пайплайн...
              Даже один! Ибо конвееры у большинства современных ЦП длиной 15-20 инструкций.
              Ответить

          • ava 3.14159265 23.05.2014 17:42 # 0

            Хе-хе-хе. 3 дня назад
            http://govnokod.ru/16008#comment232774
            if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n +=  8; i <<=  8; }
if (i >>> 28 == 0) { n +=  4; i <<=  4; }
if (i >>> 30 == 0) { n +=  2; i <<=  2; }
n -= i >>> 31;
n = 32-n;

            Ответить

        • ava guest 23.05.2014 11:40 # 0

          тем временем 10 логических операций никак не могут быть быстрее аппаратной поддержки http://en.wikipedia.org/wiki/Find_first_set#Hardware_support
          Ответить

          • ava bormand 23.05.2014 11:46 # +1

            Интринсик кстати есть на эти операции? Или только асмом херачить?

            P.S. Ну и в любом случае кроссплатформенного способа для нестандартных операций нету и походу не будет. Так что если делать через эти фичи - придется трахаться с вариантами для разных компиляторов и осей ;(

            Так что код, который я кидал - более-менее разумный компромисс между скоростью и ёблей.
            Ответить

            • ava guest 23.05.2014 11:52 # 0

              можно посчитать через log2 - если поддержка есть, компилятор его аппаратно за одну инструкцию сделает, если нету то скорее всего использует байтоебский вариант.

              интристики описаны там же в википедии следующим разделом http://en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support
              Ответить

            • ava 3.14159265 23.05.2014 17:37 # 0

              >Интринсик кстати есть на эти операции?
              unsigned __int64 _tzcnt_u64(unsigned __int64 src);

              Как-то все забыли про старый-добрый BSF.
              Ответить

            • ava 3.14159265 23.05.2014 17:55 # +1

              >Ну и в любом случае кроссплатформенного способа для нестандартных операций нету и походу не будет.
              Та умные компилеры превращают такие "станадартные" байтоебские коды в одну инструкцию. А самописную срань с ветками они откажутся оптимизировать.
              Ответить

            • ava Dummy00001 24.05.2014 01:14 # 0

              find first set - man ffs
              некоторые системы еще умеют и find last set - man fls

              ffs попал в позикс. fls не думаю что до туда когда попадет.

              PS в gcc - __builtin_ffs*(). в добавок __builtin_clz и __builtin_ctz - http://gcc.gnu.org/onlinedocs/gcc-4.8.1/gcc/Other-Builtins.html
              Ответить

        • ava 3.14159265 23.05.2014 17:45 # 0

          >5 непредсказуемых условных переходов никак не могут быть быстрее 10 логических операций. Без шансов.
          Ну да. С этим утверждением трудно поспорить что бы не говорил wvxvw.
          Ответить

      • ava 3.14159265 23.05.2014 17:51 # 0

        > то вполне можно выиграть у байтоебских вариантов, зависит от распределения значений
        Я бы выделил частный случай: if (i&(i-1)==0) return i;
        в остальном вариант борманда практически оптимален.
        Ответить

    • ava 1024-- 23.05.2014 10:57 # 0

      Напомнило старое доброе http://govnokod.ru/14217
      Ответить

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