1. C++ / Говнокод #12555

    +27

    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
    inline double poly(double x, const double *c, int k) const {
        double y = c[k];
        switch (k) {
            case 15: y = y * x + c[14];
            case 14: y = y * x + c[13];
            case 13: y = y * x + c[12];
            case 12: y = y * x + c[11];
            case 11: y = y * x + c[10];
            case 10: y = y * x + c[ 9];
            case  9: y = y * x + c[ 8];
            case  8: y = y * x + c[ 7];
            case  7: y = y * x + c[ 6];
            case  6: y = y * x + c[ 5];
            case  5: y = y * x + c[ 4];
            case  4: y = y * x + c[ 3];
            case  3: y = y * x + c[ 2];
            case  2: y = y * x + c[ 1];
            case  1: y = y * x + c[ 0];
            case  0: break;
        }
        return y;
    }

    Схема Горнера для вычисления значения многочлена в точке

    Запостил: uranix, 08 Февраля 2013

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

    • ava bormand 08.02.2013 05:17 # 0

      В чем говно, uranix?
      Видимо в отсутствии проверки на k > 15 и в бесполезном break?

      В общем случае, конечно, так делать не стоит. Но, видимо, автор убедился, что это вычисление является узким местом в его расчете, и сделал вот такую вот микрооптимизацию. Этот код должен работать эффективнее цикла.
      Ответить

      • ava bormand 08.02.2013 05:28 # +1

        P.S. Маленький бенчмарк показал чуть более чем двукратное превосходство кода из поста - 14.2с у цикла против 6.2с у данного кода при k=15, 3.8с у цикла против 2.2с при k=5.
        Ответить

        • ava defecate-plusplus 08.02.2013 09:49 # +1

          > показал чуть более чем двукратное превосходство кода
          хм, при -funroll-loops выхлоп инлайна функции с циклом вполне приличен
          Ответить

          • ava defecate-plusplus 08.02.2013 10:04 # +2

            причем на гцц 4.8.0 он вообще крайне похож на функцию со свичом
            на 4.7.2 немного хуже, но терпимо

            желающие могут поэкспериментировать с выхлопом вот тут:
            http://liveworkspace.org/code/1FESYP$4
            Ответить

            • ava absolut 08.02.2013 10:12 # 0

              4.8? это unstable что ли?
              Ответить

            • ava bormand 08.02.2013 10:12 # 0

              Ну да, старый дурак я, забыл что на -O2 анролл выключен. С анроллом даже на 4.6.3 работает не хуже чем код ОП'а (раскрутило на блоки по 12 итераций).
              Ответить

            • ava bormand 08.02.2013 10:16 # 0

              Забавно, но жаба неплохо показала себя на этой задачке (тестил реализацию через цикл). С опцией -client работала чуть-чуть медленнее чем сишный код без анролла. С -server - процентов на 10 медленнее чем сишный с анроллом.
              Ответить

            • ava uranix 08.02.2013 11:38 # +1

              За ссылку на liveworkspace спасибо.
              Добавил SSE вариант - делает по скорости исходный код при k > 6
              http://liveworkspace.org/code/3QcmgC$5
              Ответить

      • ava uranix 08.02.2013 05:28 # 0

        Собственно, как автор, согласен по всем пунктам (работает примерно на 50% шустрее цикла). Говно в том, что не знаю как это же оформить без хака со switch'ем.
        Ответить

        • ava bormand 08.02.2013 06:17 # +3

          Ну можно попробовать как-то так:
          template <int k> inline double poly3(double x, const double *c) {
    return c[0] + x*poly3<k-1>(x, c+1);
}

template <> inline double poly3<0>(double x, const double *c) {
    return c[0];
}

double res = poly<15>(x, c);
          gcc компилит это в отличный асм:
          ...
        fmul    %st(1), %st
        faddl   32(%eax)
        fmul    %st(1), %st
        faddl   24(%eax)
        fmul    %st(1), %st
        faddl   16(%eax)
...
          Работает чуть-чуть быстрее кода со свичом, но, к сожалению, при фиксированных k.
          Ответить

          • ava TarasB 08.02.2013 10:08 # +1

            switch(k)
            {
            case 0 : return poly<0>(x,c);
            case 1 : return poly<1>(x,c);
            ...

            Помнится, кто-то спрашивал в №11479, зачем такое может быть нужно.
            Ответить

            • ava bormand 08.02.2013 10:24 # 0

              Ну профита в этом уже не будет. Производительность будет точно такая же, как в коде ОП'а, и чуть-чуть быстрее, чем в коде с тупым циклом и -funroll-loops.

              Профит от подобного шаблона проявится только если k фиксированное.

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

          • ava tirinox 08.02.2013 18:48 # 0

            После такого пора задуматься.
            Ответить

        • ava Dummy00001 09.02.2013 01:16 # +2

          > Говно в том, что не знаю как это же оформить без хака со switch'ем.

          это не хак - это фича. и говна соответственно в коде я лично не вижу.

          я еще пару аналогичных свичей встречал.

          теория (как сверху объясняется) в том что компилеры должны это сами делать уметь. на практике, без coverage прохода, компилеры не могут знать что именно будет узким местом, поэтому почти всегда идут на компромис когда применяют оптимизации которые могут значительно увеличить размер кода. (излишне много кода == кэш CPU для кода становится узким местом.) поэтому много циклов и не разворачивается.

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

    • ava igumnovf 10.02.2013 22:38 # 0

      Duff's device успешно детектирован. Не могу понять только одного, зачем там const после скобок оно же не член класса?
      Ответить

      • ava bormand 10.02.2013 22:46 # 0

        > Duff's device успешно детектирован.
        Кусок дафф девайса, ибо в даффе еще цикл не помешает.

        > оно же не член класса
        Ну видимо член, раз написали. Хотя если член, то какого хрена он не static - не понятно.
        Ответить

        • ava igumnovf 10.02.2013 22:51 # 0

          И правда нет цикла, детектор барахлит ночью. force inline еще надо впаять.
          Ответить

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