Этот ваш хаскель (не) только для факториалов и годен

    Когда речь заходит о любимых языках, я обычно говорю, что при прочих равных предпочитаю C++ для числодробилок и хаскель для всего остального. Полезно периодически проверять, насколько такое деление обосновано, а тут ещё недавно возник один праздный и очень простой вопрос: как себя будет вести сумма всех делителей числа с ростом этого самого числа, скажем, для первого миллиарда чисел. Эту задачу просто запрогать (аж стыдно называть получившееся числодробилкой), так что она выглядит как отличный вариант для такой проверки.


    Кроме того, я всё ещё не владею навыком точного предсказания производительности хаскель-кода, так что полезно пробовать заведомо плохие подходы, чтобы посмотреть, как будет деградировать производительность.


    Ну и вдобавок можно легонько выпендриться более эффективным алгоритмом, чем лобовой поиск делителей для каждого числа от $1$ до $n$.


    Алгоритм


    Итак, начнём с алгоритма.


    Как найти сумму всех делителей числа $n$? Можно пройтись по всем $k_1 \in \{ 1 \dots \lfloor \sqrt n \rfloor \}$ и для каждого такого $k_1$ проверить остаток от деления $n$ на $k_1$. Если остаток — $0$, то добавляем к аккумулятору $k_1 + k_2$, где $k_2 = \frac{n}{k_1}$, если $k_1 \neq k_2$, и просто $k_1$ иначе.


    Можно ли применять этот алгоритм $n$ раз, для каждого числа от $1$ до $n$? Можно, конечно. Какова будет сложность? Легко видеть, что порядка $O(n^\frac{3}{2})$ делений — для каждого числа мы делаем ровно корень-из-него делений, а чисел у нас $n$. Можем ли мы лучше? Оказывается, что да.


    Одна из проблем этого метода — мы тратим слишком много сил впустую. Слишком много делений не приводят нас к успеху, давая ненулевой остаток. Естественно попытаться быть чуть более ленивыми и подойти к задаче с другой стороны: давайте просто будем генерировать всевозможные кандидаты на делители и смотреть, каким числам они удовлетворяют?


    Итак, пусть теперь нам нужно одним махом для каждого числа от $1$ до $n$ посчитать сумму всех его делителей. Для этого пройдёмся по всем $k_1 \in \{ 1 \dots \lfloor \sqrt n \rfloor \}$, и для каждого такого $k_1$ пройдёмся по всем $k_2 \in \{ k_1 \dots \lfloor \frac{n}{k} \rfloor \}$. Для каждой пары $(k_1, k_2)$ добавим в ячейку с индексом $k_1 \cdot k_2$ значение $k_1 + k_2$, если $k_1 \neq k_2$, и $k_1$ иначе.


    Этот алгоритм делает ровно $n^\frac{1}{2}$ делений, и каждое умножение (которое дешевле деления) приводит нас к успеху: на каждой итерации мы что-нибудь увеличиваем. Это сильно эффективнее, чем лобовой подход.


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


    Первая реализация


    И, кстати, это прямо почти псевдокод начальной реализации на хаскеле:


    module Divisors.Multi(divisorSums) where
    
    import Data.IntMap.Strict as IM
    
    divisorSums :: Int -> Int
    divisorSums n = IM.fromListWith (+) premap IM.! n
      where premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1)
                     | k1 <- [ 1 .. floor $ sqrt $ fromIntegral n ]
                     , k2 <- [ k1 .. n `quot` k1 ]
                     ]

    Main-модуль простой, и я его не привожу.


    Кроме того, здесь мы показываем сумму только для самого $n$ для простоты сравнения с другими реализациями. Несмотря на то, что хаскель — ленивый язык, в этом случае будут вычислены все суммы (хотя полное обоснование этого выходит за рамки этой заметки), так что тут не получится, что мы ненароком что-нибудь не посчитаем.


    Как быстро это работает? На моём i7 3930k в один поток 100'000 элементов отрабатывается за 0.4 с. При этом 0.15 с тратится на вычисления и 0.25 с — на GC. И занимаем мы примерно 8 мегабайт памяти, хотя, так как размер инта — 8 байт, в идеале нам должно хватить 800 килобайт.


    Хорошо (на самом деле нет). Как эти числа будут расти с увеличением, гм, числа́? Для 1'000'000 элементов оно работает уже примерно 7.5 секунд, три секунды тратя на вычисления и 4.5 секунды тратя на GC, а также занимая 80 мегабайт (в 10 раз больше, чем нужно). И даже если мы на секунду прикинемся Senior Java Software Developer'ами и начнём тюнить GC, существенно картину мы не поменяем. Плохо. Похоже, миллиарда чисел мы не дождёмся никогда, да и по памяти не влезем: на моей машине всего 64 гигабайта оперативной памяти, а нужно будет примерно 80, если тенденция сохранится.


    Кажется, время сделать


    Вариант на C++


    Попробуем получить некоторое представление о том, к чему вообще имеет смысл стремиться, а для этого напишем код на плюсах.


    Ну, раз у нас уже есть отлаженный алгоритм, то тут всё просто:


    #include <vector>
    #include <string>
    #include <cmath>
    #include <iostream>
    
    int main(int argc, char **argv)
    {
        if (argc != 2)
        {
            std::cerr << "Usage: " << argv[0] << " maxN" << std::endl;
            return 1;
        }
        int64_t n = std::stoi(argv[1]);
    
        std::vector<int64_t> arr;
        arr.resize(n + 1);
    
        for (int64_t k1 = 1; k1 <= static_cast<int64_t>(std::sqrt(n)); ++k1)
        {
            for (int64_t k2 = k1; k2 <= n / k1; ++k2)
            {
                auto val = k1 != k2 ? k1 + k2 : k1;
                arr[k1 * k2] += val;
            }
        }
    
        std::cout << arr.back() << std::endl;
    }

    Если вдруг кое-что хочется написать про этот код

    Компилятор отлично делает loop-invariant code motion в этом случае, вычисляя корень один раз за всю жизнь программы, и вычисляя n / k1 один раз на одну итерацию внешнего цикла.


    И спойлер про простоту

    Этот код у меня заработал не с первого раза, несмотря на то, что я копировал уже имеющийся алгоритм. Я сделал пару очень тупых ошибок, которые вроде бы и не относятся напрямую к типам, но всё же они были сделаны. Но это так, мысли вслух.


    -O3 -march=native, clang 8, миллион элементов обрабатывается за 0.024 с, занимая положенные 8 мегабайт памяти. Миллиард — 155 секунд, 8 гигабайт памяти, как и ожидалось. Ой. Хаскель никуда не годится. Хаскель надо выкидывать. Только факториалы и препроморфизмы на нём и писать! Или нет?


    Второй вариант


    Очевидно, что прогонять все сгенерированные данные через IntMap, то есть, по факту, относительно обычную мапу — мягко скажем, не самое мудрое решение (да, это тот самый заведомо паршивый вариант, о котором говорилось вначале). Почему бы нам не использовать массив, как и в коде на C++?


    Попробуем:


    module Divisors.Multi(divisorSums) where
    
    import qualified Data.Array.IArray as A
    import qualified Data.Array.Unboxed as A
    
    divisorSums :: Int -> Int
    divisorSums n = arr A.! n
      where arr = A.accumArray (+) 0 (1, n) premap :: A.UArray Int Int
            premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1)
                     | k1 <- [ 1 .. floor bound ]
                     , k2 <- [ k1 .. n `quot` k1 ]
                     ]
            bound = sqrt $ fromIntegral n :: Double

    Здесь мы сразу используем unboxed-версию массива, так как Int достаточно простой, и ленивость в нём нам не нужна. Boxed-версия отличалась бы только типом arr, так что в идиоматичности мы тоже не теряем. Кроме того, здесь отдельно вынесен байндинг для bound, но не потому, что компилятор глупый и не делает LICM, а потому, что тогда можно явно указать его тип и избежать предупреждения от компилятора о defaulting'е аргумента floor.


    0.045 с для миллиона элементов (всего в два раза хуже плюсов!). 8 мегабайт памяти, ноль миллисекунд в GC (!). На размерах побольше тенденция сохраняется — примерно в два раза медленнее, чем C++, и столько же памяти. Отличный результат! Но можем ли мы лучше?


    Оказывается, что да. accumArray проверяет индексы, чего нам в этом случае делать не надо — индексы корректны по построению. Попробуем заменить вызов accumArray на unsafeAccumArray:


    module Divisors.Multi(divisorSums) where
    
    import qualified Data.Array.Base as A
    import qualified Data.Array.IArray as A
    import qualified Data.Array.Unboxed as A
    
    divisorSums :: Int -> Int
    divisorSums n = arr A.! (n - 1)
      where arr = A.unsafeAccumArray (+) 0 (0, n - 1) premap :: A.UArray Int Int
            premap = [ (k1 * k2 - 1, if k1 /= k2 then k1 + k2 else k1)
                     | k1 <- [ 1 .. floor bound ]
                     , k2 <- [ k1 .. n `quot` k1 ]
                     ]
            bound = sqrt $ fromIntegral n :: Double

    Как видим, изменения минимальны, кроме необходимости индексироваться с нуля (что, на мой взгляд, является багом в API библиотеки, но это другой вопрос). Какова производительность?


    Миллион элементов — 0.021 с (уау, в рамках погрешности, но быстрее, чем плюсы!). Естественно, те же 8 мегабайт памяти, тот же 0 мс в GC.


    Миллиард элементов — 152 с (похоже, оно действительно быстрее плюсов!). Чуть меньше 8 гигабайт. 0 мс в GC. Код по-прежнему идиоматичен. Думаю, можно сказать, что это победа.


    В заключение


    Во-первых, я был удивлён, что замена accumArray на unsafe-версию даст такой прирост. Разумнее было бы ожидать процентов 10-20 (в конце концов, в плюсах замена operator[] на at() не даёт существенного снижения производительности), но никак не половину!


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


    В-третьих, конечно, возможны дальнейшие оптимизации, причём на всех уровнях. Я уверен, например, что из кода на плюсах можно выжать ещё чуточку больше. Однако, на мой взгляд, во всяких таких бенчмарках важен баланс между затраченными усилиями (и объёмом кода) и полученным выхлопом. Иначе всё в конце концов в пределе сойдётся к вызову LLVM JIT или чего подобного. Кроме того, наверняка есть более эффективные алгоритмы решения этой задачи, но представленный результат непродолжительных раздумий тоже сойдёт для этого небольшого воскресного приключения.


    В-четвёртых, моё любимое: надо развивать системы типов. unsafe здесь не нужен, я как программист могу доказать, что k_1 * k_2 <= n для всех k_1, k_2, встречающихся в цикле. В идеальном мире зависимо типизированных языков я бы конструировал это доказательство статически и передавал бы его в соответствующую функцию, что убирало бы необходимость проверок в рантайме. Но, увы, в хаскеле нет полноценных завтипов, а в языках, где завтипы есть (и которые я знаю), нет array и аналогов.


    Ну и в-пятых: я не знаю других языков программирования достаточно, чтобы претендовать на околобенчмарки на этих языках, но один мой приятель написал аналог на питоне. Практически ровно в сто раз медленнее, и похуже по памяти. А сам алгоритм предельно простой, поэтому если кто-то знающий напишет в комментариях аналог на Go, Rust, Julia, D, Java, Malbolge или чём ещё и поделится сравнением, например, с C++-кодом на их машине — будет, наверное, здорово.


    P.S.: Сорри за немного кликбейтный заголовок. У меня не получилось придумать ничего лучше.

    Share post

    Similar posts

    Comments 144

      +1
      Ммм. n^2 — x^2, где x от 1 до n дает ряд чисел, которые раскладываются на множители с суммой 2n. Что то мне кажется это можно было бы сюда прикрутить.

      P.S. так множители то не простые! Тогда одно и то же число может давать разные суммы множителей, зависит от того как разложить.
        0
        Да, мы сумму всех (что определяет сумму, кстати) множителей считаем. Но если нам дано разложение на простые, то посчитать сумму всех множителей тоже довольно просто.
          +2
          А, то есть сумма множителей ВСЕХ возможных разложений. Ок, перечитаю статью со свежей головой.
            0
            Хех, делал когда-то такое:
            def factor(x):
                def f(y, q):
                    while not y % q:
                        y //= q
                        r[q] = r.get(q, 0) + 1
                    return y
            
                r, p = {}, 7
                x = f(f(f(x, 2), 3), 5)
                while x >= p * p:
                    for s in 4, 2, 4, 2, 4, 6, 2, 6:
                        if not x % p:
                            x = f(x, p)
                        p += s
                if x > 1:
                    f(x, x)
                return r
            
            def divisors(x):
                r = [1]
                for p, n in factor(x).items():
                    t = -len(r)
                    for _ in range(n):
                        for _ in range(t, 0):
                            r.append(r[t] * p)
                return r
            
            # посмотрим, как оно
            
            @timer
            def main(x):
                print(sum(divisors(x)))
            
            main(10 ** 9)
            main(999983 * 1000003)  # два больших простых
            

            Выхлоп
            2497558338
            main , sec: 0.000041
            999987999936
            main , sec: 0.032282
          0
              for (int64_t k1 = 1; k1 <= static_cast<int64_t>(std::sqrt(n)); ++k1)
              {
                  arr[k1 * k1] += k1;
                  
                  for (int64_t k2 = k1 + 1; k2 <= n / k1; ++k2)
                  {
                      auto val = k1 + k2;
                      arr[k1 * k2] += val;
                  }
              }


          Чуть лучше, чем изначальный вариант везде, где удалось проверить, по идее должно примерно сравняться с хаскелем.
            0

            Ещё можно попробовать во внешнем цикле инициализировать индекс как k1 * k1, а во внутреннем цикле прибавлять к нему k1 вместо умножения. Может тоже получиться чуть эффективнее.

              +1
              Это компилятор и сам сделал, а вот первую итерацию из цикла не вынес. Наверное, не готов гарантировать, что ( n / k1 ) всегда больше k1 при заданных условиях, то есть, цикл выполнится минимум раз.
            +1
            Вариант на питоне нужно показать, слишком тормозно на первый взгляд, в питоне тоже есть всякие полезные для вычисления типы, использовались ли они?
              0
              #!/usr/bin/env python3
              import array
              import itertools
              import math
              import sys
              
              if __name__ == "__main__":
                  try:
                      n = int(sys.argv[1])
                      assert n > 0
                  except (IndexError, ValueError, AssertionError):
                      print("Invalid argument.", file=sys.stderr)
                      sys.exit(1)
              
                  arr = array.array("q", itertools.repeat(0, n + 1))
              
                  for k1 in range(1, math.floor(math.sqrt(n)) + 1):
                      for k2 in range(k1, (n // k1) + 1):
                          arr[k1 * k2] += k1 + k2 if k1 != k2 else k1 
              
                  print(arr[-1])

              Товарищ довольно долго её мучал, пробуя разные подходы, вплоть до использования массивов из numpy. Как я понял, это оказалось лучшим вариантом.

                0
                Далеко не лучшим. Numpy шикарен своими векторными операциями и при их использовании (на моем процессоре) обгоняет данный код в 6 раз.
                Реализация:
                arr_v = np.zeros(shape=(n + 1), dtype=np.int64)
                for k1 in range(1, math.floor(np.sqrt(n)) + 1):
                    x = np.arange(k1, (n // k1) + 1, dtype=np.int64)
                    indices_true = np.select([x != k1], [x]) * k1
                    indices_false = np.select([x == k1], [x]) * k1
                    
                    arr_v[indices_true] += k1 + x
                    arr_v[indices_false] += k1
                    
                arr_v[0] = 0

                Пользуемся тем, что нулевой элемент массива будет == 0 и используем его как «отстойник» для лишней информации. Причем уверен, что данный код можно переписать еще оптимальнее.
                timeit для обоих вариантов:
                2.9 s ± 173 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) — первоначальный
                469 ms ± 35.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) — Numpy

                P.S. Кто нибудь может сравнить numpy с c++ на одном и том же оборудовании?

                ноутбук: colab.research.google.com/drive/1e2A7OMm853gVN84mEIex7BLW7szyapLI
                  +1

                  Но ведь, если я правильно понимаю, реализация numpy по большому счёту сделана на С, так что этот код в каком-то смысле бенчмаркает FFI в C, разве нет?

                    +1
                    Модуль array тоже, как и вообще основная реализация интерпретатора — CPython, так что тут вообще сложно говорить о том, что что-то можно написать на Python. :D

                    Еще немного более оптимизированных и исправленных реализаций:
                    Numpy
                    arr_v = np.zeros(shape=(n + 1), dtype=np.int64)
                    
                    for k1 in range(1, int(math.floor(np.sqrt(n)) + 1)):
                      x = np.arange(k1 + 1, (n // k1) + 1, dtype=np.int64)
                      arr_v[x * k1] += k1 + x
                      arr_v[k1 * k1] += k1
                    
                    arr_v[0] = 0
                    


                    Numpy + Numba (для тех, кто почему то на Python борется за миллисекунды)
                    @jit(int64[:](int64[:], int64[:], int64), nopython=True)
                    def internal(x_, arr_v_, k1_):
                      arr_v_[x_ * k1_] += k1_ + x_
                      return arr_v_
                    
                    arr_v = np.zeros(shape=(n + 1), dtype=np.int64)
                    
                    for k1 in range(1, int(math.floor(np.sqrt(n)) + 1)):
                      x = np.arange(k1 + 1, (n // k1) + 1, dtype=np.int64)
                      arr_v = internal(x, arr_v, k1)
                      arr_v[k1 * k1] += k1
                    
                    arr_v[0] = 0
                    


                    Ноутбук с сравнением из предыдущего комментария обновил.
                      0
                      У питона совсем другая ниша, числодробилки это не для него, смысла в сравнении с ним особого нет, тут питон проигрывает даже например го, хотя есть питонные вебфрейморки которые в соответствующих задачах имеют производительность близкую к го и ноде.
                +3
                Вот реализация на Прологе:
                sumdel(K,Sum):- R is round(sqrt(K)), sumdel(K,R,Sum).
                
                sumdel(_,1,0).
                sumdel(X,K1,S):-
                  K1_next is K1 - 1, divmod(X,K1,K2,Rest),
                  ( Rest =:= 0 
                     -> sumdel(X,K1_next,Akk), (K1 =:= K2 -> S is Akk + K1; S is Akk + (K1 + K2));
                     sumdel(X,K1_next,S)
                  ).
                

                Результаты — процессор i7-4771 CPU @ 3.50GHz, для K = 100000 время 0.000 сек, K = 1000000 время 0.001 сек, для K = 1000000000 время 0.017 сек.
                Алгоритм, надеюсь, перевел слово в слово из начала статьи…
                  0
                  Хм, интересно. А оно точно суммы делителей для всех чисел от 1 до K считает?

                  В начале статьи первый алгоритм же только для одного числа, и производительность больше похожа на вычисление одной суммы.
                    +4
                    Ага, вот оно — действительно, только для одного числа! Добавление тупого кода
                    sd(1,0).
                    sd(K,Sum):- sumdel(K,Akk), N is K - 1,!, sd(N,S), Sum is S + Akk.
                    

                    дало более понятный результат для K = 100000 время 28.129 секунд.
                    Правда, я думаю, что вполне можно изменить на динамическое вычисление и тогда… но лень писать :)
                      0
                      Жалко. Логическое программирование красивое, но реализации не всесильны.
                        +2
                        вот прямо сейчас я пишу именно на прологе о-о-очень серьезную систему, так там буквально 50 строк пролога порождают множественные рекурсии рекурсии (в общем, работа начинается с того, что часа два пытаюсь понять, что же это :). Что интересно, написать то же на С (или Яве или..) я бы смог, наверно, месяцев за 5-7… Пока по скорости работы она превосходит аналоги (написанные на обычных языках, думаю, что С++ Ява и т.д.) просто на 2-3 порядка!
                          +4
                          Прямо заинтриговали, что же такое пишете… :)
                        0

                        Как вариант, можно вывести все совершенные числа до N, чтобы гарантировать, что алгоритм честно считает сумму делителей для всех* чисел.


                        *: Компилятор может пропустить некоторые числа, если докажет, что они не могут быть совершенными.

                          0

                          Или считать хэш.

                        0
                        Вот, кстати, еще одно замечание — в прологе же работа с числами не просто так устроена, а именно как с арифметикой бесконечной точности! Отсюда и торможение…
                        Я просто вспомнил «дело о факториале» — как-то раз давно посоревновались в написании факториала (ну ясно, что на прологе это всегда рекурсия), и вот момент истины — сравниваем результаты ф(10) — пролог медленнее… ф(10000) — пролог считает! а на других языках нет (точности-то не хватает), а так как условие соревнования было учесть суммарное время разработки и выполнения, то пришлось другим участникам дописывать использование библиотеки работы с модулярной арифметикой. Так что в соревновании… выиграл пролог.
                        Был еще один случай — на олимпиаде была задача — написать программу, которая печатает свой исходный текст (не используя хитростей), причем победитель оценивался как самый короткий текст программы… Ну победил бейсик, конечно… :) (8 байт), но на втором месте был пролог ( :- display. ) :) а для текста на С удалось ужаться в 125 байт вроде бы…
                      0
                      Автор хотел GOLANG?
                      на моём проце
                      1) голанг считал 2 минуты 3 секунды
                      2) с++ считал 3 минут 20 секунд (компилил прогу так g++ -O2 -o m m.cpp)
                      3) хаскель проверить не смог, ибо тут не весь код, а я не шарю

                      Пусть автор проверит голанг.
                      Могу сказать, что похоже с гошкой есть чит — проц 4 ядра, на виртуальных ядер 8. Голанг как-то захапал оба виртуальных ядра на 100%, в отличии от с++

                      package main
                      
                      import (
                      	"fmt"
                      	"math"
                      )
                      
                      func main() {
                      	n := 1000 * 1000 * 1000 //2497558338
                      	//n = 1000000             //2480437
                      
                      	arr := make([]int, n+1)
                      	sqrtn := int(math.Sqrt(float64(n)))
                      	for k1 := 1; k1 <= sqrtn; k1++ {
                      		nk1 := n / k1
                      		for k2 := k1; k2 <= nk1; k2++ {
                      			if k1 != k2 {
                      				arr[k1*k2] += k1 + k2
                      			} else {
                      				arr[k1*k2] += k1
                      			}
                      		}
                      	}
                      	fmt.Printf("%d\n", arr[n])
                      
                      }

                        +1
                        Спасибо за вариант! Часов через шесть смогу проверить на той же машине, отпишусь о результатах.

                        Параллелизовать этот код автоматически — не самая тривиальная задача. Я бы ставил на параллельный GC, если он в Go есть. Хотя GC тут и не особо нужен. Но я в Go не шарю совсем.
                          0
                          Не упомянул, что запускал на линуксе. Проц Intel Core i5 8250U 1600 МГц
                          Не уверен, что выставил правильную оптимизацию в с++ компиляторе.
                          Выложите код на хаскеле одним файлом, чтоб я тоже запустил. Интересно.
                            0

                            Попробуйте


                            import qualified Data.Array.Base as A
                            import qualified Data.Array.IArray as A
                            import qualified Data.Array.Unboxed as A
                            import System.Environment
                            
                            divisorSums :: Int -> Int
                            divisorSums n = arr A.! (n - 1)
                              where arr = A.unsafeAccumArray (+) 0 (0, n - 1) premap :: A.UArray Int Int
                                    premap = [ (k1 * k2 - 1, if k1 /= k2 then k1 + k2 else k1)
                                             | k1 <- [ 1 .. floor bound ]
                                             , k2 <- [ k1 .. n `quot` k1 ]
                                             ]
                                    bound = sqrt $ fromIntegral n :: Double
                            
                            main :: IO ()
                            main = do
                              [nStr] <- getArgs
                              print $ divisorSums $ read nStr

                            Я использовал ghc 8.6.4, собирал с -O2, запуск с передачей одного аргумента — максимального числа.


                            Писал с мобильника, прошу прощенья, если не соберётся.

                              0
                              ghc -O2 Main.hs
                              за 8 минут прога не выдала ответа для миллиарда и мне стало лень ждать (миллион посчитался корректно и быстро)
                                0
                                А памяти сколько у вас, и какой размер инта в Go на вашей системе?
                                  0
                                  16гб, 64бит.
                                  Памяти хватает, свап файл не используется
                                  ghc 8.0.2
                                  go 1.11
                            0

                            Параллельный GC в golang есть.

                            0

                            Ура, смог через мобильник зайти на ту же машину.


                            В общем, производительность для go чуть хуже, чем для C++/clang, но несущественно — 160 секунд для миллиарда.

                              0
                              всегда подозрительно, когда у хаскелиста не так, как у гофера или любого другого императивщика))
                                0
                                Да, что-то у нас как-то в противофазе всё, у меня Go медленнее, а у вас хаскель.
                            0

                            Вариант на Golang:


                            package main
                            
                            import (
                                "math"
                                "testing"
                            )
                            
                            func BenchmarkMaxN_1_000_000(b *testing.B) {
                                for i := 0; i < b.N; i++ {
                                    calc(1000000)
                                }
                            }
                            
                            func BenchmarkMaxN_10_000_000(b *testing.B) {
                                for i := 0; i < b.N; i++ {
                                    calc(10000000)
                                }
                            }
                            
                            func BenchmarkMaxN_100_000_000(b *testing.B) {
                                for i := 0; i < b.N; i++ {
                                    calc(100000000)
                                }
                            }
                            
                            func BenchmarkMaxN_1_000_000_000(b *testing.B) {
                                for i := 0; i < b.N; i++ {
                                    calc(1000000000)
                                }
                            }
                            
                            func calc(n int64) int64 {
                                arr := make([]int64, n+1)
                            
                                for k1 := int64(1); k1 <= int64(math.Sqrt(float64(n))); k1++ {
                                    for k2 := k1; k2 <= n/k1; k2++ {
                                        var val int64
                            
                                        if k1 != k2 {
                                            val = k1 + k2
                                        } else {
                                            val = k1
                                        }
                            
                                        arr[k1*k2] += val
                                    }
                                }
                            
                                return arr[n]
                            }

                            И результат на моем древнем ноутбуке с Intel® Core(TM) i7-2860QM CPU @ 2.50GHz и 16 Gb оперативки:


                            $ go test -bench=. -benchmem
                            goos: linux
                            goarch: amd64
                            BenchmarkMaxN_1_000_000-8                 20      97029314 ns/op     8003696 B/op          1 allocs/op  // 0.097 sec
                            BenchmarkMaxN_10_000_000-8                 1    2065155756 ns/op    80003072 B/op          1 allocs/op  // 2.06 sec
                            BenchmarkMaxN_100_000_000-8                1    27831236382 ns/op   800006144 B/op         1 allocs/op  // 27.83 sec
                            BenchmarkMaxN_1_000_000_000-8              1    386078665273 ns/op  8000004096 B/op        1 allocs/op  // 386.07 sec
                            PASS
                            ok      _/home/ilya/Projects/habr-test-1    418.363s

                            При этом С++ вариант у меня выполняется:


                            • Для 1 000 000 за 0.044 sec
                            • Для 1 000 000 000 за 158.79 sec

                            Т.е. на моем ноуте Golang медленнее С++ чуть более чем в 2 раза. Потребление памяти одинаковое.


                            Кстати, еще примечательно, что C++ код выполнялся в абсолютной тишине, а от Golang кулеры завизжали как сумасшедшие. Хотя возможно, это как-то связанно со спецификой работы Benchmark в Golang.


                            PS Слишком долго форматировал сообщение, опередили :D

                              0
                              Golang медленнее С++ чуть более чем в 2 раза

                              У меня получилось с точностью наоборот…
                                0

                                А вы уровень оптимизации указывали как -o2, как в вашем комментарии, или -O2?

                                  0
                                  о маленькое. Попробовал Большое — стало 3:20. Лучше, но гоу всё-равно обычгрывает
                                    0

                                    Я компилировал ваш код с теми же аргументами: clang++ -O3 -march=native -o habr-test-cpp ./habr-test-1.cpp. Правда, судя по всему, у меня clang 6

                                  +1
                                  Спасибо за результат!

                                  Моему настольному 3930k на 4 гигагерцах должно быть стыдно.
                                    0
                                    возникает вопрос, а это точно будет выполняться один раз, а не каждый раз цикла?
                                    int64(math.Sqrt(float64(n)))
                                      0

                                      Я думаю Golang достаточно умный чтобы выполнить это один раз. Попробовал вынести это в переменную, но не заметил разницы.

                                      +1

                                      Заменил int64 на uint64 и результат получился значительно лучше:


                                      goos: linux
                                      goarch: amd64
                                      BenchmarkMaxN_1_000_000-8                 20      86956243 ns/op     8003608 B/op          1 allocs/op
                                      BenchmarkMaxN_10_000_000-8                 1    1594835918 ns/op    80003168 B/op          2 allocs/op
                                      BenchmarkMaxN_100_000_000-8                1    21094544631 ns/op   800006144 B/op         1 allocs/op
                                      BenchmarkMaxN_1_000_000_000-8              1    299162328158 ns/op  8000004096 B/op        1 allocs/op
                                      PASS
                                      ok      _/home/ilya/Projects/habr-test-1    324.019s
                                        0
                                        а если замерить секундомером, а не встроенным тестированием?
                                      +2
                                      Java 8 -Xms9000M
                                      i5 7300HQ 16 Гб
                                      112,7 сек.
                                      public static void main(final String[] args) {
                                              long time1 = System.nanoTime();
                                              int n = 1000000000;
                                             int arr [] = new int[n+1];
                                              int sqrtN = (int) Math.sqrt(n);
                                             for (int k1 = 1; k1 <= sqrtN ;k1++){
                                                 for (int k2 = k1;k2 <=n/k1;k2++ ){
                                                     int val;
                                                      if (k1!=k2){
                                                         val  = k1+k2;
                                                      } else {
                                                          val = k1;
                                                      }
                                                      arr[k1*k2]+=val;
                                                 }
                                             }
                                             long time2 = System.nanoTime();
                                              out.println((time2-time1)/1000000);
                                          }

                                        0
                                        На мой взгляд некорректно сравнивать код оперирующий int64 с кодом оперирующим int32. Если в C++ варианте заменить int64_t на int32_t, то скорость выполнения у меня возрастает почти в два раза. Так что в данном случае надо везде long использовать.
                                          0

                                          Отличное замечание! И очень интересное, даёт пищу для дальнейших размышлений.


                                          Я поигрался с заменой int64_t на int32_t — ничего не поменялось. Вероятно, оно упирается в латентность памяти на моей системе, уж больно не дружественный к кешу алгоритм. Но, увы, я не знаю, как это оценить.


                                          Если брать оценку снизу по количеству данных, которые нужно перегнать:


                                          -- Для каждого k1 во вложенном цикле мы делаем столько итераций:
                                          Prelude> itersK1 n k1 = n `div` k1 - k1 + 1
                                          
                                          -- Значит, суммарно для n мы делаем столько итераций:
                                          Prelude> iters n = sum $ itersK1 n <$> [1 .. floor $ sqrt n]
                                          
                                          -- На каждой итерации мы прогоняем минимум 8 байт из памяти и 8 байт обратно:
                                          Prelude> fromIntegral (iters 1000000000) / 1024 / 1024 / 1024 * 8 * 2
                                          155.55120450258255

                                          155 гигабайт — ну, 15-30 секунд. Это адская оценка снизу.


                                          Оценка сверху — по времени доступа. Латентность памяти — пусть порядка 100 наносекунд на операцию, что даёт оценку сверху без учёта кеширования записей и кеширования чтений (когда предиктор может) порядка


                                          Prelude> fromIntegral (iters 1000000000) * 1e-7
                                          1043.8864628

                                          Точнее я не знаю, как.

                                            0
                                            Я попробовал заменить на long, оно теперь ругается, ждет int. Видать не везде менять надо, изменил только тип массива и теперь оно не запускается с ошибкой «Exception in thread „main“ java.lang.OutOfMemoryError: Java heap space», я хз где чего надо подкрутить.

                                            На c# у меня на Int64 выполнилось за 103 сек, поменял на Int32 и выполнилось за 83 сек, т.е. ускорение есть, но не 2 раза. Вот памяти, логично, использовало в 2 раза меньше. И результат в случае Int32 неправильный.
                                              0
                                              Индекс массива должен быть int, остальное можно заменить на long.
                                              Ошибка, потому что JVM не хватает памяти по-умолчанию. Параметрами -Xms и -Xmx в VM options можно задавать минимальную и максимальную выделяемую для JVM память.
                                                0
                                                Я там и пробовал вставлять, но сейчас все таки добился чтобы начало выполняться. Оно оказывается начинает работать при -Xmx начиная от 12Гб. В общем на моем компе если заменить на long там где это возможно, то начинает выполняться за 120 сек вместо 105 сек при использовании int.
                                            0
                                            Это горячий код в JMH?
                                              +1

                                              scala:
                                              i7 — 6500U


                                              object Main extends App {
                                                val start = System.currentTimeMillis()
                                                val n = 100000000
                                                val arr = new Array[Int](n + 1)
                                              
                                                for (k1 <- 1 to math.sqrt(n).toInt) {
                                                  for (k2 <- k1 to (n / k1)) {
                                                    arr(k1 * k2) += (if (k1 != k2) k1 + k2 else k1)
                                                  }
                                                }
                                              
                                                val finish = System.currentTimeMillis()
                                                println((finish - start) * 0.001)
                                              }

                                              Код такой же, читабельность чуть получше. Время около 10 секунд для 10^8. Замена массива Int на массив Long производительность вроде бы не снижает.

                                              0
                                              shell> systeminfo
                                              
                                              Название ОС:                      Microsoft Windows 7 Максимальная
                                              Процессор(ы):                     Число процессоров - 1.
                                                                                [01]: Intel64 Family 6 Model 58 Stepping 9 GenuineIntel ~2601 МГц
                                              Полный объем физической памяти:   8 010 МБ
                                              Доступная физическая память:      3 173 МБ

                                              Вариант на Julia


                                              function divisorsum(n::Int64)
                                              
                                                  arr = zeros(Int64, n)
                                              
                                                  for k1 = 1:Int(round(sqrt(n))), k2 = k1:n÷k1
                                              
                                                      val = k1 != k2 ? k1 + k2 : k1
                                                      arr[k1 * k2] += val
                                                  end
                                              end

                                              using BenchmarkTools
                                              @benchmark divisorsum(1_000_000)
                                              
                                              BenchmarkTools.Trial: 
                                                memory estimate:  7.63 MiB
                                                allocs estimate:  2
                                                --------------
                                                minimum time:     56.909 ms (0.00% GC)
                                                median time:      59.520 ms (0.00% GC)
                                                mean time:        60.466 ms (2.21% GC)
                                                maximum time:     107.803 ms (45.13% GC)
                                                --------------
                                                samples:          83
                                                evals/sample:     1
                                              
                                              @benchmark divisorsum(10_000_000)
                                              
                                              BenchmarkTools.Trial: 
                                                memory estimate:  76.29 MiB
                                                allocs estimate:  2
                                                --------------
                                                minimum time:     856.228 ms (0.61% GC)
                                                median time:      891.972 ms (0.95% GC)
                                                mean time:        897.030 ms (2.68% GC)
                                                maximum time:     941.900 ms (5.56% GC)
                                                --------------
                                                samples:          6
                                                evals/sample:     1
                                                0

                                                Если отменить слежку за индексами массива, чуть ускорится


                                                function divisorsum(n::Int64)
                                                
                                                    arr = zeros(Int64, n)
                                                
                                                    @inbounds for k1 = 1:Int(round(sqrt(n))), k2 = k1:n÷k1
                                                
                                                        val = k1 != k2 ? k1 + k2 : k1
                                                        arr[k1 * k2] += val
                                                    end
                                                end
                                                
                                                BenchmarkTools.Trial: 
                                                  memory estimate:  7.63 MiB
                                                  allocs estimate:  2
                                                  --------------
                                                  minimum time:     45.428 ms (0.00% GC)
                                                  median time:      47.001 ms (0.00% GC)
                                                  mean time:        48.004 ms (2.55% GC)
                                                  maximum time:     97.231 ms (49.98% GC)
                                                  --------------
                                                  samples:          105
                                                  evals/sample:     1
                                                  0
                                                  А вариант на C++ сколько у вас выполняется?
                                                    0

                                                    n = 1000000
                                                    Process returned 0 (0x0) execution time: 0.216 s
                                                    Сдуру попробовал для миллиарда, а когда проигрыватель поперхнувшись замолчал, и окна перестали отвечать, вспомнил что оператива не потянет

                                                      0

                                                      Оказывается в Julia есть корень и для целых, но на производительность это не особо влияет, зато код чертовски нагляден


                                                      julia> isqrt(64)
                                                      8
                                                      julia> isqrt(66)
                                                      8
                                                      
                                                      julia> function divisorsum(n::Int64)
                                                                     arr = zeros(Int64, n)
                                                                     @inbounds for k1 = 1:isqrt(n), k2 = k1:n?k1
                                                                         val = k1 != k2 ? k1 + k2 : k1
                                                                         arr[k1 * k2] += val
                                                                     end
                                                             end
                                                      
                                                      julia> using BenchmarkTools
                                                      
                                                      julia> @benchmark divisorsum(1_000_000)
                                                      BenchmarkTools.Trial:
                                                        memory estimate:  7.63 MiB
                                                        allocs estimate:  2
                                                        --------------
                                                        minimum time:     45.840 ms (0.00% GC)
                                                        median time:      48.228 ms (0.00% GC)
                                                        mean time:        49.407 ms (2.19% GC)
                                                        maximum time:     89.813 ms (47.11% GC)
                                                        --------------
                                                        samples:          102
                                                        evals/sample:     1
                                                      
                                                      julia> @benchmark divisorsum(100_000_000)
                                                      BenchmarkTools.Trial:
                                                        memory estimate:  762.94 MiB
                                                        allocs estimate:  2
                                                        --------------
                                                        minimum time:     10.212 s (0.09% GC)
                                                        median time:      10.212 s (0.09% GC)
                                                        mean time:        10.212 s (0.09% GC)
                                                        maximum time:     10.212 s (0.09% GC)
                                                        --------------
                                                        samples:          1
                                                        evals/sample:     1
                                                        0
                                                        Хм, а вы точно с оптимизациями плюсовый вариант собрали?
                                                          0
                                                          На счет плюсов, все эти команды компилятору для меня непаханное поле — у меня пятилетний кодеблокс. Ничего не менял, кинул код, не трогая все эти оптимизации
                                                            0

                                                            Выставил оптимизацию О3, но уже на другой машине
                                                            i7-2600K 3.4GHz 16Gb mem


                                                            c++ and Julia

                                                            С++
                                                            n = 1000000
                                                            Process returned 0 (0x0) execution time: 0.062 s
                                                            n = 100 000 000
                                                            Process returned 0 (0x0) execution time: 14.803 s


                                                            julia> @benchmark divisorsum(1_000_000)
                                                            BenchmarkTools.Trial:
                                                              memory estimate:  7.63 MiB
                                                              allocs estimate:  2
                                                              --------------
                                                              minimum time:     25.045 ms (0.00% GC)
                                                              median time:      26.728 ms (0.00% GC)
                                                              mean time:        27.676 ms (3.77% GC)
                                                              maximum time:     69.359 ms (60.17% GC)
                                                              --------------
                                                              samples:          181
                                                              evals/sample:     1
                                                            
                                                            julia> @benchmark divisorsum(100_000_000)
                                                            BenchmarkTools.Trial:
                                                              memory estimate:  762.94 MiB
                                                              allocs estimate:  2
                                                              --------------
                                                              minimum time:     12.202 s (0.07% GC)
                                                              median time:      12.202 s (0.07% GC)
                                                              mean time:        12.202 s (0.07% GC)
                                                              maximum time:     12.202 s (0.07% GC)
                                                              --------------
                                                              samples:          1
                                                              evals/sample:     1

                                                            Шах и мат аметисты

                                                              +1
                                                              Да, очень неплохо. Julia интересная.
                                                    0

                                                    Попытался распараллелить "в лоб" на Golang. Правда я не уверен, что не накосячил с синхронизацией, но по идеи если массив не меняется, то получать ссылку на значение можно и без лока. Во всяком случае результирующее значение для миллиарда он считает правильное:


                                                    package main
                                                    
                                                    import (
                                                        "flag"
                                                        "math"
                                                        "sync"
                                                        "sync/atomic"
                                                    )
                                                    
                                                    var wg sync.WaitGroup
                                                    func calc(n uint64) uint64 {
                                                        arr := make([]uint64, n+1)
                                                    
                                                        for k1 := uint64(1); k1 <= uint64(math.Sqrt(float64(n))); k1++ {
                                                            wg.Add(1)
                                                            go func(t1 uint64) {
                                                                for k2 := t1; k2 <= n/t1; k2++ {
                                                                    var val uint64
                                                    
                                                                    if t1 != k2 {
                                                                        val = t1 + k2
                                                                    } else {
                                                                        val = t1
                                                                    }
                                                    
                                                                    atomic.AddUint64(&arr[t1*k2], val)
                                                                }
                                                                wg.Done()
                                                            }(k1)
                                                        }
                                                    
                                                        wg.Wait()
                                                        return arr[n]
                                                    }
                                                    
                                                    var maxN = flag.Uint64("max", 1000000, "max N")
                                                    
                                                    func main() {
                                                        flag.Parse()
                                                        println(calc(*maxN))
                                                    }

                                                    В итоге для миллиарда получилось 111.69 sec, т.е. примерно на 40 sec быстрее, чем на C++. 0xd34df00d если будет возможность, попробуйте протестировать у себя. Интересно какой будет результат.

                                                      0
                                                      На плюсах я бы делал так же в общем, но да, без лока вокруг массива и с атомиками. Если я правильно понимаю, как работают атомики и кеши, то оверхед от них на этой задаче будет не очень большой.

                                                      На хаскеле я бы просто несколько кусков массива параллельно обрабатывал, а потом сливал вместе. Атомики не очень хорошо сочетаются с чистотой и equational reasoning, поэтому там пришлось бы вылезать в монаду IO.

                                                      Через пару часов погоняю у себя.
                                                        0

                                                        можно еще GC отключить, GOGC=off, должно быть чуть быстрее

                                                          +1
                                                          Добрался до машины. Что-то как-то ну так. Миллиард считается ровно минуту, при этом счастливо кушая все 12 ядер процессора.
                                                            0

                                                            Раз уж пошла такая пьянка с распараллеливанием на других языках, то решил немного доработать этот код. Сделал обычный пул на нативных каналах, на моем ноуте получилось примерно на 20-30% эффективнее, чем в варианте с 30 000 горутин.


                                                            package main
                                                            
                                                            import (
                                                                "flag"
                                                                "math"
                                                                "runtime"
                                                                "sync"
                                                                "sync/atomic"
                                                            )
                                                            
                                                            var n uint64
                                                            var workers int
                                                            var wg sync.WaitGroup
                                                            
                                                            func worker(arr []uint64, inners <- chan uint64) {
                                                                for k1 := range inners {
                                                                    for k2 := k1; k2 <= n/k1; k2++ {
                                                                        var val uint64
                                                            
                                                                        if k1 != k2 {
                                                                            val = k1 + k2
                                                                        } else {
                                                                            val = k1
                                                                        }
                                                            
                                                                        atomic.AddUint64(&arr[k1*k2], val)
                                                                    }
                                                                }
                                                                wg.Done()
                                                            }
                                                            
                                                            func main() {
                                                                flag.Uint64Var(&n,"max", 1000000, "max N")
                                                                flag.IntVar(&workers, "workers", runtime.NumCPU() / 2, "num of workers")
                                                                flag.Parse()
                                                            
                                                                sqrtN := uint64(math.Sqrt(float64(n)))
                                                                arr := make([]uint64, n+1)
                                                                pool := make(chan uint64, sqrtN)
                                                            
                                                                for k1 := uint64(1); k1 <= sqrtN; k1++ {
                                                                    pool <- k1
                                                                }
                                                                close(pool)
                                                            
                                                                for i := 0; i < workers; i++ {
                                                                    wg.Add(1)
                                                                    go worker(arr, pool)
                                                                }
                                                            
                                                                wg.Wait()
                                                                println(arr[n])
                                                            }
                                                              0
                                                              У меня все три вариации кода на го выдают примерно одинаковое время.
                                                                0

                                                                А какая у вас версия Golang? Такое впечатление, что у вас GOMAXPROCS устанавливается в 1, а не равное количеству ядер.


                                                                И как вы его запускали? Через go run или go build?

                                                                  0
                                                                  Такое впечатление, что у вас GOMAXPROCS устанавливается в 1, а не равное количеству ядер.

                                                                  Нет, я бы это увидел. Ваша пилит на половине ядер, другая на всех, а ещё одна на ядре + гипетред(как и говорил автор).

                                                                  А какая у вас версия Golang?

                                                                  go version go1.12.1 linux/amd64

                                                                  И как вы его запускали? Через go run или go build?

                                                                  go run, но я не думаю, что это на что-то влияет. Там гцц собирает С++-код (миллионы строк) за 0.4sec.

                                                                0
                                                                А сколько у вас там ядер?

                                                                Если распараллеливать правильно (без всяких атомиков, просто в непересекающиеся части массива писать), то там кратный прирост производительности, по идее.
                                                                  0

                                                                  4 физических / 8 логических https://pastebin.com/xfVW6g3h. Странно, что результат так сильно от процессора зависит. Надо будет на нормальном железе потестить.


                                                                  Попробую без атомиков реализовать позже.

                                                                    0
                                                                    Странно, что результат так сильно от процессора зависит.

                                                                    Там дело не совсем в процессоре.Я уже писал про transparent huge pages.

                                                                    У вас «многопоточность» не код ускорят, а tlb-промахи. Т.е. если отображения нету в кэше(tlb) — процессор идёт искать отображение в памяти. В случае с одним потоком — ядро(процессор) почти всё время(половину) занимается поиском. В многопотоке этот поиск размазывается по ядрам.

                                                                    75,197948177 seconds time elapsed// - ваш
                                                                    124,388672662 seconds time elapsed// - который "однопоточный"
                                                                    66,385085639 seconds time elapsed// ваш на всех потоках.
                                                                    58,259779411 seconds time elapsed// ваш, все ядра и thp


                                                                      0

                                                                      У меня был включен режим madvise.


                                                                      # cat /sys/kernel/mm/transparent_hugepage/enabled 
                                                                      always [madvise] never

                                                                      Попробовал переключать на always, never и обратно, но отличия были в пределах погрешности. Или нужно было как то иначе их включать?


                                                                      Вообще, я думаю, что в данном случае все немного проще. Обслуживание ~30000 горутин априори чуть более затратно, чем четырех горутин + chan. Однако из-за того что я тестирую это на процессоре 7 летней давности эта разница кажется куда более заметной для меня.

                                                                        0
                                                                        Попробовал переключать на always, never и обратно, но отличия были в пределах погрешности. Или нужно было как то иначе их включать?

                                                                        cat /proc/meminfo, perf stat -dddd Можете написать сюда выхлоп — разберёмся.

                                                                        Вообще, я думаю, что в данном случае все немного проще.

                                                                        Ну дак у меня же всё меняется(при переключении), практика соотносится с теорией.

                                                                        Обслуживание ~30000 горутин априори чуть более затратно, чем четырех горутин + chan.

                                                                        Это копейки на фоне всего остального. Там ниже есть мой код — там можно передать кол-во потоков. У меня на 30000потоков(на самом деле там создаётся далеко не 30к потоков, а гораздо больше) это добавляет 1-2секунды к 50 имеющимся. И это потоки ОС.

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

                                                                        Ну я вижу с never такую же разницу, которую видите вы. Эта разница ничем, кроме влияния thp, не объясняется. По крайней мере ничем предложенным вами.

                                                                          +1
                                                                          В общем, в итоге собрал все тесты которые смог скомпилировать в одном месте и прогнал их с perf stat gist.github.com/ilya-pirogov/8079ed7dca0185a1cb89ec20910e26c4:



                                                                          Если интересно, то весь исходный код выложил на github: github.com/ilya-pirogov/harb-test-1

                                                                          PS Не обращайте внимания на то что однопоточный Rust на первом, я просто перепутал бинарники. он на предпоследнем у меня, перед однопоточной версией Go.
                                                                            +1
                                                                            мой zig пропустили :(
                                                                              +1
                                                                              Я не пропустил. Я просто не знаю как его компилировать, а времени разбираться не было. Добавлю попозже, если надо. Или же PR всегда приветствуются :)
                                                                                0
                                                                                Тогда уж сделать статьюшку со всеми реализациями и разбором каждой
                                                                                  0
                                                                                  отправил.
                                                                                0
                                                                                Судя по вики ваш процессор может в:
                                                                                cat /proc/cpuinfo | grep pdpe1gb

                                                                                Но почему-то их у вас нет.

                                                                                Информация с perf абсолютно бесполезна. Нужно взять С++/раст-версию и запустить её на 1ккк вначале на never, а потом на always.

                                                                                #!/usr/bin/env bash

                                                                                set -e -o xtrace

                                                                                cat /proc/cpuinfo
                                                                                cat /proc/meminfo

                                                                                sudo bash -c "echo never > /sys/kernel/mm/transparent_hugepage/enabled"
                                                                                perf stat -dddd ./cpp-single $@

                                                                                sudo bash -c "echo always > /sys/kernel/mm/transparent_hugepage/enabled"
                                                                                perf stat -dddd ./cpp-single $@

                                                                                Как-то так.

                                                                  +1
                                                                  На Rust 2018:

                                                                  use clap::clap_app;
                                                                  
                                                                  fn main() {
                                                                      let matches = clap_app!(divs => (@arg maxN: +required)).get_matches();
                                                                      let n = matches.value_of("maxN").unwrap();
                                                                      let n: i64 = n.parse().unwrap();
                                                                      let mut arr = vec![0; (n+1) as usize];
                                                                      for k1 in 1 ..= (n as f64).sqrt() as i64 {
                                                                          for k2 in k1 ..= n / k1 {
                                                                              let val = if k1 != k2 { k1 + k2 } else { k1 };
                                                                              arr[(k1*k2) as usize] += val;
                                                                          }
                                                                      }
                                                                      println!("{}", arr.last().unwrap());
                                                                  }
                                                                  


                                                                  В Cargo.toml, добавить clap = "2".

                                                                  $ rustc --version
                                                                  rustc 1.32.0 (9fda7c223 2019-01-16)

                                                                  $ cargo rustc --release -- -C target-cpu=native -C opt-level=3

                                                                  $ time target/release/test7 1000000000
                                                                  2497558338

                                                                  real 2m42.108s
                                                                  user 2m32.219s
                                                                  sys 0m9.609s


                                                                  C++ отработал немного быстрее

                                                                  $ clang++ --version
                                                                  clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)
                                                                  Target: x86_64-pc-linux-gnu
                                                                  Thread model: posix
                                                                  InstalledDir: /usr/bin

                                                                  $ clang++ -O3 -march=native main.cpp

                                                                  $ time ./a.out 1000000000
                                                                  2497558338

                                                                  real 2m39.568s
                                                                  user 2m29.078s
                                                                  sys 0m10.344s
                                                                    +1
                                                                    Спасибо! Ну вот в расте я совсем не сомневался!

                                                                    А любопытства ради, как будет выглядеть распараллеливание с атомиками на манер этого? Интересно, как оно с borrow checker'ом себя поведет!
                                                                      0
                                                                      use clap::clap_app;
                                                                      use rayon::prelude::*;
                                                                      use std::sync::atomic::{AtomicIsize, Ordering};
                                                                      
                                                                      fn main() {
                                                                          let matches = clap_app!(divs => (@arg maxN: +required)).get_matches();
                                                                          let n = matches.value_of("maxN").unwrap();
                                                                          let n: i64 = n.parse().unwrap();
                                                                          let arr: Vec<_> = (0..=n).map(|_| AtomicIsize::new(0)).collect();
                                                                      
                                                                          let n_sqrt = (n as f64).sqrt() as i64;
                                                                          (1..n_sqrt + 1).into_par_iter().for_each(|k1| {
                                                                              (k1 .. 1 + n / k1).into_par_iter().for_each(|k2| {
                                                                                  let val = if k1 != k2 { k1 + k2 } else { k1 };
                                                                                  arr[(k1 * k2) as usize].fetch_add(val as isize, Ordering::Relaxed);
                                                                              });
                                                                          });
                                                                          println!("{}", arr.last().unwrap().load(Ordering::SeqCst));
                                                                      }
                                                                      


                                                                      На Core i7-4790K@4GHz с включенным multithreading (предыдущие результаты тоже на нём) отработало так:
                                                                      $ time target/release/test7 1000000000
                                                                      2497558338

                                                                      real 1m27.008s
                                                                      user 9m38.953s
                                                                      sys 0m10.516s


                                                                      87 секунд против 162 секунд в однопоточном варианте.

                                                                      Борроу-чекеру атомики практически не интересны. Все операции с ними производятся через константные ссылки, которые можно шарить.

                                                                      AtomicI64 пока не стабилизировали, поэтому использую AtomicIsize, который тоже 64-х битный на моей системе.
                                                                        0
                                                                        А можно ещё unsafe/unchecked обращение к массиву по индексу попробовать, как в обеих версиях из статьи («индексы корректны по построению») — интересно, получается ли у компилятора доказать, что проверки всегда проходят, и выкинуть их при оптимизации?
                                                                          0

                                                                          Да, я пробовал с get_unchecked(). Разница в пределах погрешности. Похоже LLVM видит, что k1*k2 не может быть больше n.


                                                                          Хотя это было в нераспараллеленой версии… Попозже посмотрю, что будет со вторым вариантом.


                                                                          Скорее всего мало что изменит. Там огромный оверхэд на раскидывание коротких операций по разным потокам.

                                                                          0
                                                                          Борроу-чекеру атомики практически не интересны. Все операции с ними производятся через константные ссылки, которые можно шарить.

                                                                          Это, на самом деле, очень разумно. Хорошо сделали.


                                                                          По идее (если я правильно читаю код), можно попробовать параллелить только внешний цикл, да и не для каждого k1, а через (логарифмически) отстоящие интервалы по сотне или тыще чисел.

                                                                      +1
                                                                      Заведи репку на гитхабе, по типу lol-qwop, думаю товарищи с радостью отправят свои варианты.
                                                                        +5
                                                                        Кроме того, наверняка есть более эффективные алгоритмы решения этой задачи, но представленный результат непродолжительных раздумий тоже сойдёт для этого небольшого воскресного приключения.

                                                                        Конечно, есть. Сумма делителей мультипликативна в смысле теории чисел: если n=ab и a,b взаимно просты, то сумма делителей n равна произведению сумм делителей для a и b. Так что достаточно посчитать суммы для степеней простых и перемножить:
                                                                            std::vector<int64_t> arr;
                                                                            arr.resize(n + 1, 1);
                                                                        
                                                                            int64_t p;
                                                                            for (p = 2; p * p <= n; p++) if (arr[p] == 1) {
                                                                                int64_t ppow = p;
                                                                                int64_t sum = 1;
                                                                                do {
                                                                                    sum += ppow;
                                                                                    int64_t q, residue = 1;
                                                                                    for (int64_t q = ppow; q <= n; q += ppow, residue++)
                                                                                        if (residue == p)
                                                                                            residue = 0;
                                                                                        else
                                                                                            arr[q] *= sum;
                                                                                    ppow *= p; // no overflow here if n**(3/2) < 2**63; we get std::bad_alloc long before this otherwise
                                                                                } while (ppow <= n);
                                                                            }
                                                                            for (; p <= n; p++) if (arr[p] == 1) {
                                                                                for (int64_t q = p; q <= n; q += p)
                                                                                    arr[q] *= 1 + p;
                                                                            }
                                                                            std::cout << arr.back() << std::endl;
                                                                        

                                                                        Получается быстрее в 2-3 раза.
                                                                          +6
                                                                          Каждый раз, когда читаю такие статьи и комментарии, поражаюсь, какой я тупой.
                                                                            0
                                                                            Изящно, спасибо! Мои познания в теории чисел околонулевые, так что тут у меня шансов не было.
                                                                            +3
                                                                            Раз в комментариях получилась спец-олимпиада, то было бы здорово собрать всё в одном месте и сравнить.
                                                                              +1
                                                                              У меня вот тупой перебор на Сях за три секунды отрабатывает на обычном ноуте.

                                                                              int main(int argc, char **argv) {
                                                                              	if (argc < 2) {
                                                                              		printf("Usage: %s N\n", argv[0]);
                                                                              	}
                                                                              	else {
                                                                              		unsigned n = atoi(argv[1]), sum = 0;
                                                                              		for (unsigned k = 1; k <= n/2; k++) {
                                                                              			if (n % k == 0) sum += k;
                                                                              		}
                                                                              		sum += n;
                                                                              		printf("result %u\n", sum);
                                                                              	}
                                                                              }
                                                                              
                                                                                0
                                                                                Это конечно ничего не говорит о сравнении языков, просто лишний раз показывает, что в наше время процессор в десятки и сотни раз быстрее чем память.
                                                                                  0
                                                                                  У всех по два цикла, а у вас один. подробнее не вглядывался — под рукой компилятора нет.
                                                                                    0

                                                                                    Так это ж только для одного числа, а не для всех чисел от 1 до n.


                                                                                    Кстати, правильный компилятор должен генерировать код, который вообще в память не лезет — это тут незачем, регистр на sum, пара регистров на i, остаток от деления и прочую подобную ерунду.

                                                                                      0
                                                                                      Значит я не правильно понял задачу. Пример в статье выводит только сумму делителей для самого N.
                                                                                        +1

                                                                                        Да, выводить вообще все суммы будет довольно дорого, да и для сравнения лишь одно из чисел вполне неплохо.


                                                                                        Код из задачи потом с этими числами делает что-то ещё (графички там всякие строит, гистограммы), но это уже не так интересно.

                                                                                          0
                                                                                          Можно было тогда для статьи сложить суммы сумм в качестве искомого.
                                                                                    0

                                                                                    del

                                                                                      +1

                                                                                      Решил принять участие, написал на Zig:


                                                                                      const std = @import("std");
                                                                                      const warn = std.debug.warn;
                                                                                      
                                                                                      pub fn main() !void {
                                                                                      
                                                                                          var timer = try std.os.time.Timer.start();
                                                                                      
                                                                                          var direct_allocator = std.heap.DirectAllocator.init();
                                                                                          defer direct_allocator.deinit();
                                                                                      
                                                                                          var arena = std.heap.ArenaAllocator.init(&direct_allocator.allocator);
                                                                                          defer arena.deinit();
                                                                                      
                                                                                          const allocator = &arena.allocator;
                                                                                      
                                                                                          const args = try std.os.argsAlloc(allocator);
                                                                                      
                                                                                          const n = try std.fmt.parseInt(u32, args[1], 10);
                                                                                      
                                                                                          var arr = std.ArrayList(u64).init(allocator);
                                                                                          try arr.resize(n+1);
                                                                                      
                                                                                          var k1: u32 = 1;
                                                                                          while (k1 <= @floatToInt(u32, @sqrt(f64, @intToFloat(f64, n)))) {
                                                                                              var k2: u32 = k1;
                                                                                              while (k2 <= n / k1) {
                                                                                                  const val = if (k1 != k2) k1+k2 else k1;
                                                                                                  const i = k1*k2;
                                                                                                  arr.set(i, arr.at(i) + val);
                                                                                                  k2 += 1;
                                                                                              }
                                                                                              k1 += 1;
                                                                                          }
                                                                                      
                                                                                          warn("{}\n", arr.at(n));
                                                                                          warn("ms: {}", timer.lap() / 1000000);
                                                                                      }

                                                                                      Как можно было и предположить — паритет с C++. Написал, так как хотелось проверить отстанет или нет.


                                                                                      C++ -O3: 7234 / 103683 ms
                                                                                      Zig --release-fast: 7096 / 102567 ms

                                                                                        0
                                                                                        Спасибо за пост, очень познавательно! Вообще производительность штука интересная: «замена accumArray на unsafe-версию даст такой прирост. Разумнее было бы ожидать процентов 10-20 (в конце концов, в плюсах замена operator[] на at() не даёт существенного снижения производительности), но никак не половину!»

                                                                                        Будучи C++-ником однажды по просьбе дорабатывал код на C#. В одном вычислительном блоке очень помог именно unsafe. Ребята, которые писали исходный код на C# были удивлены. Хотя это и несравнимые вещи ;)
                                                                                          +1
                                                                                          #include <iostream>
                                                                                          #include <vector>
                                                                                          
                                                                                          int main(int argc, char **argv)
                                                                                          {
                                                                                          	if (argc != 2)
                                                                                          	{
                                                                                          		std::cerr << "Usage: " << argv[0] << " maxN" << std::endl;
                                                                                          		return 1;
                                                                                          	}
                                                                                          	size_t n = static_cast<size_t>(std::stoi(argv[1]));
                                                                                          	std::vector<unsigned int> lowest_devider(n + 1);
                                                                                          	std::vector<unsigned int> primes;
                                                                                          	std::vector<unsigned long long> answer(n + 1);
                                                                                          	answer[1] = 1;
                                                                                          	for (unsigned int number = 2; number <= n; number++)
                                                                                          	{
                                                                                          		if (lowest_devider[number] == 0)
                                                                                          		{
                                                                                          			lowest_devider[number] = number;
                                                                                          			primes.push_back(number);
                                                                                          			answer[number] = number + 1;
                                                                                          			for (unsigned long long new_number = number; new_number * number <= n; new_number *= number)
                                                                                          			{
                                                                                          				answer[new_number * number] = answer[new_number] * number + 1;
                                                                                          				lowest_devider[new_number * number] = number;
                                                                                          			}
                                                                                          		}
                                                                                          		for (size_t j = 0;
                                                                                          				j < primes.size()
                                                                                          				and primes[j] < lowest_devider[number]
                                                                                          				and number * primes[j] <= n;
                                                                                          				j++)
                                                                                          		{
                                                                                          			for (unsigned int new_number = number; new_number * primes[j] <= n; new_number *= primes[j])
                                                                                          			{
                                                                                          				answer[new_number * primes[j]] = answer[new_number] * primes[j] + answer[number];
                                                                                          				lowest_devider[new_number * primes[j]] = primes[j];
                                                                                          			}
                                                                                          		}
                                                                                          	}
                                                                                          	std::cout << answer[n] << std::endl;
                                                                                          }
                                                                                          

                                                                                          Алгоритм за O(n). К сожалению не смог протестировать на миллиарде(мало памяти на компе). Для половины миллиарда работает 17 сек.
                                                                                          Основан на решете Эратосфена. И формуле суммы делителей по степеням входящих простых.
                                                                                          Также использована хитрая идея
                                                                                          • UFO just landed and posted this here
                                                                                              +1
                                                                                              впервые решил потестировать код из статьи и написать на своём любимом Lua (+ дописать для LuaJIT с FFI). переписал на Lua+FFI
                                                                                              Lua код
                                                                                              ffi=require("ffi")
                                                                                              args={...}
                                                                                              if #args~=1 then 
                                                                                                  print("maxN missing")
                                                                                              else
                                                                                                  num=ffi.new("long")
                                                                                                  num=tonumber(args[1])
                                                                                                  arr=ffi.new("int[?]",num+1)
                                                                                                  i=ffi.new("long")
                                                                                                  j=ffi.new("long")
                                                                                                  for i=1,num do
                                                                                                      arr[i]=0 
                                                                                                  end
                                                                                                  for i=1,math.sqrt(num) do
                                                                                                      for j=1,math.floor(num/i) do
                                                                                                          val= (i~=j) and (i+j) or i
                                                                                                          arr[i*j]=arr[i*j]+val
                                                                                                      end
                                                                                                  end
                                                                                                  sum=ffi.new("long")
                                                                                                  sum=0
                                                                                                  for i=1,num do
                                                                                                      sum=sum+arr[i]
                                                                                                  end
                                                                                              
                                                                                                  print(sum)
                                                                                              end
                                                                                              


                                                                                              Для миллиона считает за 88 мс и выдает ответ 822968117937, что уже противоречит приведенному выше. Код адаптировал из приведенного С++ кода в статье и условий задачи. Почему у меня получается такой ответ — не понимал. Решил запустить у себя С++ код из статьи, немного подточив напильником, чтобы у меня смогло запуститься
                                                                                              Код С++
                                                                                              компилировал так:
                                                                                              g++ -O3 -march=native m.cpp -o m

                                                                                              Код:
                                                                                              #include <vector>
                                                                                              #include <string>
                                                                                              #include <cmath>
                                                                                              #include <iostream>
                                                                                              #include <stdlib.h>
                                                                                              
                                                                                              int main(int argc, char **argv)
                                                                                              {
                                                                                                  if (argc != 2)
                                                                                                  {
                                                                                                      std::cerr << "Usage: " << argv[0] << " maxN" << std::endl;
                                                                                                      return 1;
                                                                                                  }
                                                                                                  long n = atol(argv[1]);
                                                                                                  long long sum=0;
                                                                                                  std::vector<long> arr;
                                                                                                  arr.resize(n + 1);
                                                                                                  long val=0;
                                                                                                  for (long k1 = 1; k1 <= static_cast<long>(std::sqrt(n)); ++k1)
                                                                                                  {
                                                                                                      for (long k2 = k1; k2 <= n / k1; ++k2)
                                                                                                      {
                                                                                                          val = k1 != k2 ? (k1 + k2) : k1;
                                                                                                          arr[k1 * k2] += val;
                                                                                                          sum+= val;
                                                                                                      }
                                                                                                  }
                                                                                                  std::cout << sum << std::endl;
                                                                                              }
                                                                                              


                                                                                              Такой код выдает 822468118437, что на 499999500 отличается от результата Lua. С++ код выполняется за 66 мс.
                                                                                              В статье меня смущало выражение arr.back(). Немного погуглив и проверив выхлоп Lua с аналогичным кодом
                                                                                              print(arr[#arr])

                                                                                              Получил такой же ответ, что и в указанном комментарии, и такой же, что и выдает мне С++ код (2480437).

                                                                                              И что же получается: приведенные алгоритмы выводят лишь последний элемент массива, или вовсе без вывода запускают программу, и все комментаторы выше соревнуются в скорости языков, но не в правильности работы алгоритма (я перепробовал немало комбинаций условий, чтобы «подогнать» ответ, но не получалось).

                                                                                              Затем в комментариях наткнулся на другой алгоритм. Вникать не стал, скомпилировал, запустил для миллиона. Последнее число в массиве выводит такое же, для всей суммы адаптировать не стал.
                                                                                              миллион считает за 44 мс.

                                                                                              Также запускал 100М, но результаты аналогичные по соотношениям скорости выполнения (LuaJIT+FFI < C++(статья) < C++(решето Эратосфена)). Но хочу ещё раз заметить, LuaJIT+FFI по скорости работы имеет тот же порядок скорости, что и С++ с -O3 и не сильно отстает.

                                                                                              ноутбук
                                                                                              Core i3-2310M CPU @ 2.10GHz (2 ядра, 2 потока на ядро)
                                                                                              система: Linux Mint 18.2 64-bit
                                                                                                +1
                                                                                                (defun divisorsum (n)
                                                                                                  (let ((arr (make-array n)))
                                                                                                    (loop for k1 from 1 to (isqrt n)
                                                                                                          do (loop for k2 from k1 to (1- (floor (/ n k1)))
                                                                                                                   do (let* ((index (* k1 k2))
                                                                                                                             (val (+ (aref arr index) (if (not (eq k1 k2)) (+ k1 k2) k1))))
                                                                                                                        (setf (aref arr index) val))))))
                                                                                                

                                                                                                Компилировал SBCL 1.5.0
                                                                                                для одного миллиарда
                                                                                                Evaluation took:
                                                                                                368.161 seconds of real time
                                                                                                364.901598 seconds of total run time (346.951906 user, 17.949692 system)
                                                                                                [ Run times consist of 6.223 seconds GC time, and 358.679 seconds non-GC time. ]
                                                                                                99.11% CPU
                                                                                                808,114,697,940 processor cycles
                                                                                                3 page faults
                                                                                                8,000,983,040 bytes consed

                                                                                                Для сравнения код на C++ 210.11 секунд

                                                                                                Код на лиспе, как по мне, получился элегантным, правда производительностью не очень
                                                                                                  +1
                                                                                                  Спасибо за статью — очень интересное открытие. Добавьте, пожалуйста, сравнение с gcc — у меня он чуть быстрее clang.
                                                                                                    0
                                                                                                    Это, вероятно, зависит от системы и конкретных версий компиляторов. У меня разница между gcc и clang в пределах погрешности (и в пользу clang).
                                                                                                      0
                                                                                                      Скорее всего у вас старый гцц. И у вас очень странные результаты. Покажи результат: cat /sys/kernel/mm/transparent_hugepage/enabled — ядро должно само закатывать хотя-бы 2m страницами такие случаи.
                                                                                                        0

                                                                                                        гцц 8.3. На самом деле clang уже давно примерно равен gcc в большинстве моих тестов, если код специально под gcc не затачивать.


                                                                                                        Покажи результат: cat /sys/kernel/mm/transparent_hugepage/enabled

                                                                                                        Нету такого, есть только /sys/kernel/mm/hugepages/hugepages-2048kB/

                                                                                                          +1
                                                                                                          Нету такого

                                                                                                          Это плохо, нужно включить в ядре:

                                                                                                          CONFIG_TRANSPARENT_HUGEPAGE=y
                                                                                                          CONFIG_TRANSPARENT_HUGEPAGE_ALWAYS=y

                                                                                                            +1
                                                                                                            Эт перезагружаться придётся.
                                                                                                    +1
                                                                                                    Покритикую. Для затравочки:
                                                                                                    62 sec //C++
                                                                                                    119 sec //хаскель


                                                                                                    Только факториалы и препроморфизмы на нём и писать! Или нет?

                                                                                                    Только вот проблема — ваша задача такой же факториал.

                                                                                                    Код по-прежнему идиоматичен.

                                                                                                    Нет. «идиоматичен» там С++. Так можно что угодно назвать чем угодно, допустим, этот жс тоже «идиоматичен».

                                                                                                    function f(n) {
                                                                                                      let arr = new Int32Array(n + 1);
                                                                                                      for(let k1 = 1; k1 <= Math.floor(Math.sqrt(n)); ++k1) {
                                                                                                        for (let k2 = k1; k2 <= n / k1; ++k2) {
                                                                                                          let val = k1 != k2 ? k1 + k2 : k1;
                                                                                                            arr[k1 * k2] += val;
                                                                                                        }
                                                                                                      }
                                                                                                      
                                                                                                      return arr;
                                                                                                    }

                                                                                                    Этот код, кстати, показывает результат почти такой же как и хаскель(с поправкой на 64битные инты). Правда, в жс нету 64 битных интов, но суть не в этом.

                                                                                                    Очевидно, что код не является идиоматичным, когда существуют подобные допущения:
                                                                                                    Почему бы нам не использовать массив

                                                                                                    необходимости индексироваться с нуля

                                                                                                    ленивость в нём нам не нужна.

                                                                                                    Попробуем заменить вызов accumArray на unsafeAccumArray:


                                                                                                    Думаю, можно сказать, что это победа.

                                                                                                    Нет, это не победа. Наоборот — проигрыш. Что вы хотели показать этим примером? «хаскель может как С++», но вы показали не это. Вы показали «существуют такие примеры, которые везде работают хренова и хаскель тут очередной жс».

                                                                                                    Да, существуют множество случаев, когда никакая оптимизация невозможна и случай прощает все(почти) недочёты «обычных» языков. Это один из них. Всё, что языку нужно для «показать производительность уровня си» — это value-типы, «массив» и jit. Это и было показано в теме. И подобные примеры все такие. Проблема только одна — такие случаи редки и это те самые факториалы. Они бесполезны, они ничего не показывают.

                                                                                                    И самое важное. Сравнение языков — глупость. Нет никакого «быстрого С/С++». Есть люди, которые обладают знанием, пониманием и опытом. А С/С++ — это просто инструмент, который позволяет им этот всё применить на практике. И именно в этом случае что-то становится быстрым. И проблема хаскеля(и иже с ним) не в том, что они как-то плохо считают факториалы(хотя и это тоже. Ведь сколько вы потратили времени на обходные пути). Проблема в том, что они не дают той свободы и той возможности.

                                                                                                    Поэтому, статьи на хабре с заголовками «очередной факториал на хаскеле не тормозит» — это хорошо, но мало что даёт. А вот затюнить ядро, чтобы исключить, если попроще, dtlb-промахи — это даёт х2.
                                                                                                      +1
                                                                                                      Очень даже полезно, особенно комментарии. Мне интересны числодробилки, и вот тут ребята предоставили много вариантов по выполнению одной и той же задачи (хотя на одном языке могут быть много реализаций с различными производительностями). Тут скорее фишка в том, чтобы сходу выполнить задачу на ЯП используя самый очевидный вариант и получить неплохую производительность не вдаваясь в дебри оптимизации
                                                                                                        +2
                                                                                                        Покритикую. Для затравочки:
                                                                                                        62 sec //C++
                                                                                                        119 sec //хаскель

                                                                                                        Это с каким из вариантов?


                                                                                                        Очевидно, что код не является идиоматичным, когда существуют подобные допущения:
                                                                                                        Почему бы нам не использовать массив

                                                                                                        Почему? ФП — это не про то, чтобы делать всё на одних списках. Data.Array — достаточно каноничная вещь, особенно для мемоизации через ленивые вычисления или через просто эффективный доступ ко dense целочисленным ключам (что в данном случае выполняется, тот же IntMap был бы более для sparse).


                                                                                                        необходимости индексироваться с нуля

                                                                                                        На самом деле это даже лишнее, но я уже не стал править статью — достаточно левую границу передвинуть с 1 на 0, и всё.


                                                                                                        ленивость в нём нам не нужна.

                                                                                                        См. выше про выбор структур данных под задачу.


                                                                                                        Попробуем заменить вызов accumArray на unsafeAccumArray

                                                                                                        Ну это ещё как-то можно притянуть, наверное, да. Хотя тогда и в C++ использование [] вместо .at() неидиоматично (или вы считаете идиоматичным потенциально опасный доступ?).


                                                                                                        Действительно неидиоматичным кодом было бы засунуть всё в ST, или взять, например, ghc-primops и нафигачить параллелизм через ручное ковыряние атомиков, или написать всё руками с unboxed-версией инта (которая Int#).


                                                                                                        Всё, что языку нужно для «показать производительность уровня си» — это value-типы, «массив» и jit. Это и было показано в теме.

                                                                                                        Но в хаскеле ghc нет jit, и нет value-типов (если вы не начинаете брать #-типы, а их тут никто не брал). Зато есть GC, и тот факт, что компилятор может развернуть декларативный код «возьми последовательность пар, формируемую по таким-то правилам, и сверни её по таким-то правилам» с нулём GC, с использованием внутри value-типов, и так далее — это хорошо, и это в каком-то смысле ответ на «да эта ваша функциональщина тормозит как не в себя». И, кстати, таковая декларативность этого кода — один из признаков идиоматичности.


                                                                                                        И подобные примеры все такие. Проблема только одна — такие случаи редки и это те самые факториалы. Они бесполезны, они ничего не показывают.

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


                                                                                                        Проблема в том, что они не дают той свободы и той возможности.

                                                                                                        За свободу приходится расплачиваться. Чуть большим объёмом кода, чуть меньшей безопасностью, чуть меньшей дружественностью к рефакторингу, вот это всё.


                                                                                                        Ну а про то, что задача на самом деле не настолько уж вычислительно требовательна, я сразу написал.

                                                                                                          0
                                                                                                          Это с каким из вариантов?

                                                                                                          Базовым вашим.

                                                                                                          Я только аллокатор на нормальный поменял:
                                                                                                          mmap(nullptr, (n + 1) * sizeof(int64_t), PROT_READ|PROT_WRITE, MAP_POPULATE|MAP_PRIVATE|MAP_ANONYMOUS|MAP_HUGETLB|(30 << MAP_HUGE_SHIFT), -1, 0)


                                                                                                          На самом деле с transparent hugepage это не совсем обязательно.

                                                                                                          Почему? ФП — это не про то, чтобы делать всё на одних списках.

                                                                                                          Ну вот вы целую статью написали о том, как победили тысячи проблем. Вам бы не пришлось об этом писать, если бы проблем не было. Вы ведь на С++ написали код сразу, ни о чём не думая и ничего не меняя. Вот именно поэтому.

                                                                                                          Data.Array — достаточно каноничная вещь

                                                                                                          Вот смотрите. Вы берёте С/С++ и у вас там есть массив. Это база языка. Не нужно решать, делать специальные либы и решать тысячи проблем. Это называется канонично.

                                                                                                          Если ещё проще. Канонично — это то, что вы пишете на языке сразу. И вы написали каноничный код на хаскеле в первом вашем примере, а далее попытались «написать как на си».

                                                                                                          На самом деле это даже лишнее, но я уже не стал править статью — достаточно левую границу передвинуть с 1 на 0, и всё.

                                                                                                          Это понятно, я говорил не об этом. Вы возмущались индексацией с нуля, а значит для вас подобное поведение не является привычным. Т.е. решение этой задачи «производительным» способом потребовало вас отказаться от «привычно».

                                                                                                          Ну это ещё как-то можно притянуть, наверное, да. Хотя тогда и в C++ использование [] вместо .at() неидиоматично (или вы считаете идиоматичным потенциально опасный доступ?).

                                                                                                          Да, считаю(и не только я). Именно поэтому at() там опция, а [] — дефолт. В этом опять же разница. Вам пришлось изменять своему видению, изменять видению языка и его базовой концепции. Именно это я и имел ввиду, когда приводил все эти примеры.

                                                                                                          Действительно неидиоматичным кодом было бы засунуть всё в ST, или взять, например, ghc-primops и нафигачить параллелизм через ручное ковыряние атомиков, или написать всё руками с unboxed-версией инта (которая Int#).

                                                                                                          Просто пример слишком просто и удачный. Вам не пришлось далеко уходить, но это просто хорошо подобранный пример. Причём, пример не особе адекватный реальному применению.

                                                                                                          Но в хаскеле ghc нет jit,

                                                                                                          Я написал это в контексте «как минимум».
                                                                                                          >>и нет value-типов (если вы не начинаете брать #-типы, а их тут никто не брал).
                                                                                                          Как так нету? А что такое ваш массив? Это именно value-тип.

                                                                                                          Зато есть GC

                                                                                                          Элемент массива неподвластен гц и является value-типом.
                                                                                                          и тот факт, что компилятор может развернуть декларативный код

                                                                                                          Неможет. В противном случае вы бы остановились на первом примере.

                                                                                                          и это в каком-то смысле ответ на «да эта ваша функциональщина тормозит как не в себя»

                                                                                                          Ещё раз, вы пытались доказать силу хаскеля и то, что он может не только в факториалы. Вы написали факториал и получили производительность жаваскрипта. Т.е. вы не сделали ни первого ни второго.

                                                                                                            +1
                                                                                                            Базовым вашим.

                                                                                                            А чего с базовым?


                                                                                                            Я только аллокатор на нормальный поменял

                                                                                                            А какая разница в производительности по сравнению со случаем без transparent hugepages?


                                                                                                            Вам бы не пришлось об этом писать, если бы проблем не было. Вы ведь на С++ написали код сразу, ни о чём не думая и ничего не меняя.

                                                                                                            Нет, не сразу. Я ж даже написал, что сделал две тупых ошибки сначала (сделал вектор длины n, а не n + 1, и в цикле условия были <, а не <=, потому что рука так привыкла, если делать ни о чём не думая).


                                                                                                            Не нужно решать, делать специальные либы и решать тысячи проблем.

                                                                                                            Брать специальные либы не нужно и в этом случае: Data.Array является частью спецификации языка.


                                                                                                            Канонично — это то, что вы пишете на языке сразу.

                                                                                                            Одна из целей (которая была в заметке аж в двух местах указана) — не только посмотреть, насколько эффективно можно сделать, но и какой разрыв между наиболее эффективным и заведомо неэффективным вариантом. Будет разница в 10 раз, в 100 раз, в 10000 раз? Для меня самого это ценная информация в копилку опыта.


                                                                                                            Если у меня нет времени играться с какими-то интмапами, то для этой задачи я беру Data.Array. Разве что, unsafe-функцию я бы не брал.


                                                                                                            Ну и, кстати, это вообще какой-то странный критерий, про то, как я пишу сразу. Это было бы имело смысл, если бы на языке писал бы только я.


                                                                                                            Вы возмущались индексацией с нуля, а значит для вас подобное поведение не является привычным.

                                                                                                            Я возмущался разницей между поведением этих двух функций.


                                                                                                            Просто пример слишком просто и удачный. Вам не пришлось далеко уходить, но это просто хорошо подобранный пример. Причём, пример не особе адекватный реальному применению.

                                                                                                            Вот я прям сидел подбирал примеры.


                                                                                                            Опыт показывает, что по сумме метрик «производительность кода» и «производительность программиста» хаскель выигрывает совсем и без всяких споров. Потому что если чуть приблизиться к реальному применению, то дальше, например, мне охота построить гистограмму распределения отношения суммы к самому числу. Или построить график максимума/минимума этого отношения в корзинах по 10000 элементов. На хаскеле я просто беру получившийся array, постпроцессирую как надо и засовываю в библиотеку типа Charts. Как это на плюсах делать — хз, скрипты для gnuplot'а писать, разве что. Который, по моему опыту, прожёвывает меньше данных, чем Charts.


                                                                                                            А вот если бы мне пришлось брать мутабельные хештаблицы, скажем, вот это тоже было бы неидиоматично.


                                                                                                            Как так нету? А что такое ваш массив? Это именно value-тип.

                                                                                                            А вы что именно имеете в виду? Я имею boxed/unboxed-типы, потому что reference семантику в контексте ФП обсуждать совсем бессмысленно. Да и дальнейший контекст на это намекает.


                                                                                                            Элемент массива неподвластен гц и является value-типом.

                                                                                                            Почему?


                                                                                                            В общем случае гц должен пройтись по массиву, чтобы пометить указывающие из массива thunk'и как доступные.


                                                                                                            Неможет. В противном случае вы бы остановились на первом примере.

                                                                                                            На нём я бы не остановился заведомо, см. выше.

                                                                                                              0
                                                                                                              >>А чего с базовым?
                                                                                                              С того, что мы говорим про «идиоматичный код», а это такой код, который пишет пользователь любого языка по-дефолту.

                                                                                                              А какая разница в производительности по сравнению со случаем без transparent hugepages?

                                                                                                              Аналогичная показанной. Именно хаскелю нужен transparent hugepages.

                                                                                                              Нет, не сразу. Я ж даже написал, что сделал две тупых ошибки сначала (сделал вектор длины n, а не n + 1, и в цикле условия были <, а не <=, потому что рука так привыкла, если делать ни о чём не думая).

                                                                                                              Это просто баги — эти обстоятельства ничего не меняют.

                                                                                                              Брать специальные либы не нужно и в этом случае: Data.Array является частью спецификации языка.

                                                                                                              Ну языки с одной имплементацией являются помойкойполигоном, в котором есть всё. В этом нет ничего удивительного. Абсолютно неважно где эта либа находится — она по-сути взламывает язык, привнося в него что-то непривычное. Если пример с массивом для вас слишком спорный — замените массив на ансейф. Это не особо важно.

                                                                                                              Одна из целей (которая была в заметке аж в двух местах указана) — не только посмотреть, насколько эффективно можно сделать, но и какой разрыв между наиболее эффективным и заведомо неэффективным вариантом. Будет разница в 10 раз, в 100 раз, в 10000 раз? Для меня самого это ценная информация в копилку опыта.

                                                                                                              Я уже говорил по этому поводу- нинасколько. Данный пример нельзя «сделать» эффективно. В этом и проблема. Вы не сделали ваш код эффективным — просто вы не дали С++ сделать его эффективным.

                                                                                                              Ну и, кстати, это вообще какой-то странный критерий, про то, как я пишу сразу. Это было бы имело смысл, если бы на языке писал бы только я.

                                                                                                              Вполне очевидный критерий. Да, везде и всюду можно пытаться эмулировать некий условный си, но зачем? Проще написать на си. Но суть заключается в том, что в реальных задачах вы же не станете так писать и ситуация измениться, координально.

                                                                                                              Вот я прям сидел подбирал примеры.

                                                                                                              Ну почему же подбирали. Просто нашли удобный пример.

                                                                                                              А вы что именно имеете в виду? Я имею boxed/unboxed-типы, потому что reference семантику в контексте ФП обсуждать совсем бессмысленно. Да и дальнейший контекст на это намекает.

                                                                                                              reference имеет смысл обсуждать всегда. В ситуации с гц есть два варианта. Объект — это объект гц и это всегда reference, со всеми вытекающими. Либо это value-type.

                                                                                                              Почему?

                                                                                                              Очень просто. Обычные объекты — существуют в скоупе gc и управляется гц, со всеми вытекающими. Элемент массива — это именно value-type, т.е. gc им не владеет(и не управляет), он хранит в себе только значение(и ничего больше).

                                                                                                              В общем случае гц должен пройтись по массиву, чтобы пометить указывающие из массива thunk'и как доступные.

                                                                                                              Это неважно. Важно лишь то, что гц владеет скоупом, т.е. куском памяти, которой является массив.

                                                                                                              Кстати, это ещё одна причина — почему массив не каноничный. Массив целиком и полностью противоречит концепции gc.

                                                                                                              На нём я бы не остановился заведомо, см. выше.

                                                                                                              Я не понял ответ. Если компилятор/хаскель смог — дальше бы идти не пришлось.

                                                                                                                +1
                                                                                                                С того, что мы говорим про «идиоматичный код», а это такой код, который пишет пользователь любого языка по-дефолту.

                                                                                                                Так по дефолту пишется с Array, в чём вопрос-то тогда?


                                                                                                                Это просто баги — эти обстоятельства ничего не меняют.

                                                                                                                Лол. Когда удобно — просто баги, ничего не меняют, и то, что думать надо, тоже не меняют.
                                                                                                                Когда неудобно — мне рассказывают, как у меня происходил мыслительный процесс, когда я писал код.


                                                                                                                Ну языки с одной имплементацией являются помойкойполигоном, в котором есть всё. В этом нет ничего удивительного.

                                                                                                                Почему тогда в языках с одной имплементацией и без репорта вообще даже такого нет?


                                                                                                                Да, мы сейчас про PyPy вспомним, конечно. Ну давайте ещё повспоминаем про Hugs, Frege, ещё там какой-то хаскель под JVM был кроме него, да мало ли их.


                                                                                                                Абсолютно неважно где эта либа находится — она по-сути взламывает язык, привнося в него что-то непривычное. Если пример с массивом для вас слишком спорный — замените массив на ансейф. Это не особо важно.

                                                                                                                Почему?


                                                                                                                Кстати, используемая денотационная семантика что для IntMap, что для Array тут одинаковая. Используемый синтаксис тоже одинаковый — формируем ленивый список как управляющую структуру данных и сворачиваем его. Всё. Канонично. Идиоматично.


                                                                                                                Данный пример нельзя «сделать» эффективно. В этом и проблема. Вы не сделали ваш код эффективным — просто вы не дали С++ сделать его эффективным.

                                                                                                                То есть, я правильно понимаю, что алгоритм плохой, потому что С++ на нём не сияет?


                                                                                                                Но суть заключается в том, что в реальных задачах вы же не станете так писать и ситуация измениться, координально.

                                                                                                                Как — так? С массивом? Стану.


                                                                                                                Нужно будет много операций и их фьюжн — возьму Data.Vector.


                                                                                                                Нужен будет нетривиальный параллелизм — возьму repa.


                                                                                                                И всё это каноничные вещи.


                                                                                                                Ну почему же подбирали. Просто нашли удобный пример.

                                                                                                                А искать не пришлось.


                                                                                                                reference имеет смысл обсуждать всегда.

                                                                                                                В чистом ФП нет reference'ов.


                                                                                                                Объект — это объект гц и это всегда reference, со всеми вытекающими. Либо это value-type.

                                                                                                                И это тоже не так. В ленивом языке у вас за термом типа Int в рантайме может лежать охренительный санк на стопицот вычислений. Который, если Int вам не нужен, можно подобрать GC.


                                                                                                                Очень просто. Обычные объекты — существуют в скоупе gc и управляется гц, со всеми вытекающими. Элемент массива — это именно value-type, т.е. gc им не владеет(и не управляет), он хранит в себе только значение(и ничего больше).

                                                                                                                А, мы таки точно на императивщину переключились, причём на какой-то микс из C++ и непонятно чего. Ну ок.


                                                                                                                Кстати, это ещё одна причина — почему массив не каноничный. Массив целиком и полностью противоречит концепции gc.

                                                                                                                Массив — это просто структура данных с определённой семантикой и определёнными гарантиями производительности. GC тут ортогонален.


                                                                                                                Я не понял ответ. Если компилятор/хаскель смог — дальше бы идти не пришлось.

                                                                                                                Я не знаю, как ещё написать, что это пример заведомо неэффективного кода, который писать не надо, и это очевидно сразу, заранее?

                                                                                                                  0
                                                                                                                  Так по дефолту пишется с Array, в чём вопрос-то тогда?

                                                                                                                  Ну почему тогда в хаскеле дефолт не array?

                                                                                                                  Лол. Когда удобно — просто баги, ничего не меняют, и то, что думать надо, тоже не меняют.

                                                                                                                  Нет, никаких удобно нет. Вы там сказали про «запутался в условиях», «перепутал, что массивы индексируются не с 1» — ничего из это не связано с оптимизацией, победами над каким-то там С++ и его идиомами — там нет.

                                                                                                                  Когда неудобно — мне рассказывают, как у меня происходил мыслительный процесс, когда я писал код.

                                                                                                                  Нет, разговор был не об этом.

                                                                                                                  Почему тогда в языках с одной имплементацией и без репорта вообще даже такого нет?

                                                                                                                  Какие языки? Вон раст — там есть. Такая же помойкаполигон. Везде и всюду.

                                                                                                                  Да, мы сейчас про PyPy вспомним, конечно. Ну давайте ещё повспоминаем про Hugs, Frege, ещё там какой-то хаскель под JVM был кроме него, да мало ли их.

                                                                                                                  Я не понял что это значит. Это совсем какие-то нонеймы. Очевидно, что если язык какая-то совсем дремучая маргинальная мертвечина, то там ничего не будет вне зависимости от есть/нет больше одно имплементации.

                                                                                                                  Почему?

                                                                                                                  Почему что?

                                                                                                                  Кстати, используемая денотационная семантика что для IntMap, что для Array тут одинаковая. Используемый синтаксис тоже одинаковый — формируем ленивый список как управляющую структуру данных и сворачиваем его. Всё. Канонично. Идиоматично.

                                                                                                                  Это попытка натянуть сову на глобус. Эта хрен генерирует индекс + значение, а вся неудобная магия происходит в кишках. Это по-сути та самая мутабельная хешмапа.

                                                                                                                  То есть, я правильно понимаю, что алгоритм плохой, потому что С++ на нём не сияет?

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

                                                                                                                  К тому же, нету такого алгоритма в котором С++ не будет сиять. Именно поэтому я говорю о важности всех этих понятий «Канонично. Идиоматично.». Ведь именно на это поле вы сможете ответить С++, ведь если вы в каком-то алгоритме будете успешны, то С++ без проблем повторит и обойдёт ваш успех. Это битва не имеет смысла. Но, С++ будет вынужден использовать ваш подход. И именно это для вас должно быть важно.

                                                                                                                  И всё это каноничные вещи.

                                                                                                                  Постфактум можно назвать каноничным всё, что угодно. Хорошо, я не против.

                                                                                                                  А искать не пришлось.

                                                                                                                  Это неважно.

                                                                                                                  В чистом ФП нет reference'ов.

                                                                                                                  Их нет на уровне абстракций, но матчасть абстракции очередного языка мало интересует.

                                                                                                                  И это тоже не так. В ленивом языке у вас за термом типа Int в рантайме может лежать охренительный санк на стопицот вычислений. Который, если Int вам не нужен, можно подобрать GC.

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

                                                                                                                  А, мы таки точно на императивщину переключились, причём на какой-то микс из C++ и непонятно чего. Ну ок.

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

                                                                                                                  Массив — это просто структура данных с определённой семантикой и определёнными гарантиями производительности. GC тут ортогонален.

                                                                                                                  Нет. Вы же сами свой тезис в статье и опровергли. Именно потому, что ваш массив обладает правильной семантикой, которую описал я — вы что-то получили. Не обладай он этим, а обладай вашими определениями — этой статьи бы не было.

                                                                                                                  Я не знаю, как ещё написать, что это пример заведомо неэффективного кода, который писать не надо, и это очевидно сразу, заранее?

                                                                                                                  Я не говорю про алгоритмическую часть и про то, что можно посчитать(алгоритмически) проще и быстрее. Я именно про конкретную имплементацию, вернее про то, что у этой задачи только одна имплементация и это проблема. Нету никакого манёвра, никаких возможностей что-то сделать.

                                                                                                                    +1
                                                                                                                    Ну почему тогда в хаскеле дефолт не array?

                                                                                                                    А в хаскеле есть какой-то дефолт?


                                                                                                                    Вы там сказали про «запутался в условиях», «перепутал, что массивы индексируются не с 1» — ничего из это не связано с оптимизацией, победами над каким-то там С++ и его идиомами — там нет.

                                                                                                                    Речь шла о том, сколько надо думать при написании кода. Даже если написание сводится к переписыванию готового и отлаженного алгоритма с другого языка.


                                                                                                                    Нет, разговор был не об этом.

                                                                                                                    Мне показалось, что у вас сложилось впечатление, будто действительно сначала пишется код с IntMap, а потом уже как-то там оптимизируется и переписывается. Это не так.


                                                                                                                    Какие языки?

                                                                                                                    Питон, на который вы сослались.


                                                                                                                    Почему что?

                                                                                                                    Почему Array что-то там взламывает?


                                                                                                                    Это попытка натянуть сову на глобус. Эта хрен генерирует индекс + значение, а вся неудобная магия происходит в кишках. Это по-сути та самая мутабельная хешмапа.

                                                                                                                    Только код, который я пишу, остаётся чистым. Целиком. Мне не нужно пачкаться о состояние. А что там в кишках или в процессоре при этом происходит — десятое дело.


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

                                                                                                                    Чем он подложный-то?


                                                                                                                    Это неважно.

                                                                                                                    Как неважно, если вы говорите, что я что-то там специально искал и подбирал?


                                                                                                                    Их нет на уровне абстракций, но матчасть абстракции очередного языка мало интересует.

                                                                                                                    Это не матчасть, это что-то, имеющее вполне ощутимые эффекты. Например, атомики и CAS на чистом языке реализовать чуть менее тривиально, потому что у объектов больше нет адреса, их характеризующего.


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

                                                                                                                    Нет. В любом другом мейнстримном языке, будь то Java, C++, Go, Rust или Julia, если у вас есть переменная типа int, то в ней лежит int, а не указание, как этот int вычислить, если вдруг понадобится.


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

                                                                                                                    Тут было бы иронично вспомнить про SSA в процессе компиляции, но то такое.


                                                                                                                    Именно потому, что ваш массив обладает правильной семантикой, которую описал я — вы что-то получили. Не обладай он этим, а обладай вашими определениями — этой статьи бы не было.

                                                                                                                    Это свойства конкретной структуры данных и её взаимодействия с компилятором, но не её семантика. Хотя, может, мы по-разному определяем семантику, хз.


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

                                                                                                                    Подумать надо. Может, там можно как-то на блоки это всё дело побить, чтобы оно более к кешу дружественно было, хз. Мне этим заниматься было уже лень, две с половиной минуты на миллиард меня устраивает более чем, а 1-10 секунд на 10-100 миллионов — достаточно хорошо, чтобы граифчки строить почти в риалтайме.


                                                                                                                    А, кстати, как строить графички на плюсах, вы так и не рассказали, увы :(

                                                                                                                      +1
                                                                                                                      А в хаскеле есть какой-то дефолт?

                                                                                                                      Да, именно поэтому вы не можете написать ваш код на голом хаскеле без либ, а я могу(написать аналогичный код на С/С++). Причина тому проста, и вы сами её где-то признали, что ваш массив и операции над ним — являются читами, а каноничным у вас является лишь интерфейс, который лишь создаёт видимость чистоты, ленивости и всего остального. Про соотношение массива и гц — я уже говорил.

                                                                                                                      Речь шла о том, сколько надо думать при написании кода. Даже если написание сводится к переписыванию готового и отлаженного алгоритма с другого языка.

                                                                                                                      Нет, речь шла не об этом. Речь шла о том, что вы вначале написали РАБОЧИЙ вариант на хаскеле(так, как привыкли), а далее началась борьба с его проблемами. И вы победили, в данном случае.

                                                                                                                      На С++ вы написали такой же РАБОЧИЙ вариант, но ни с чем вам воевать не пришлось. В этом разница.

                                                                                                                      Мне показалось, что у вас сложилось впечатление, будто действительно сначала пишется код с IntMap, а потом уже как-то там оптимизируется и переписывается. Это не так.

                                                                                                                      Ну почему же. Вы по-сути сделали нам ретроспективу вашей победы. В любом случае, абсолютно неважно что там — массив/не массив. Всё остальное никуда не уходит. Я не знаю как видите вы, но не могу верить вам. И я не сомневаюсь в вашей честности, просто человеку свойственно обманываться в пользу своих убеждений.

                                                                                                                      Питон, на который вы сослались.

                                                                                                                      Зачем вы врёте? Я не ссылался на питон — это вы на него ссылались. Я говорил о конкретных свойствах языков, которые пройдут этот тест — питон ему не соответствует. И вы его привели как контр-пример моим тезисам, но это не было контр-примером. Далее в своих рассуждениях на тему «почему примерно равная производительность равна»(в данном случае).

                                                                                                                      Почему Array что-то там взламывает?

                                                                                                                      Да, я уже много примеров приводил. гц/операции над массивом. Т.е. массив по-умолчанию мутабельная структура и из неё нельзя сделать иммутабельную структуру(дёшево). Ваши операции мутабельные, массив по-сути является множеством значений(переменных), что так же не особо канонично. Вы сам в этом признавались, что если бы не «готовые функции» — никакой массив я бы использовать не мог.

                                                                                                                      Вот возьмите, пожалуйста, массив. Без использования готовой функции(которая взламывает вашу концепцию) инициализируйте его своим алгоритмом.

                                                                                                                      Только код, который я пишу, остаётся чистым. Целиком. Мне не нужно пачкаться о состояние. А что там в кишках или в процессоре при этом происходит — десятое дело.

                                                                                                                      Нет, это ошибка. Ведь мы говорим об уровне языка и концепций. То, как именно пишите вы — мало на что влияет. Ведь я тоже могу писать на С++ безопасной и мой код будет безопасным, но концептуально это ничего не изменит, как и не изменит С++.

                                                                                                                      Это не матчасть, это что-то, имеющее вполне ощутимые эффекты. Например, атомики и CAS на чистом языке реализовать чуть менее тривиально, потому что у объектов больше нет адреса, их характеризующего.

                                                                                                                      Это ограничения сверху. А ограничения сверху — это то, что матчасть волнует мало. Низ первичен — верх вторичен. Низ диктует условия — верх подчиняется. Низ прорывает абстракции верха, но низу насрать на абстракции верха.

                                                                                                                      Поэтому да, у вас нету постоянных адресов и это накладывает какие-то ограничения на вас. Но это никак не влияет на матчасть. Для матчасти ваши ограничения — лишь один из множеств возможных вариантов.

                                                                                                                      Нет. В любом другом мейнстримном языке, будь то Java, C++, Go, Rust или Julia, если у вас есть переменная типа int, то в ней лежит int, а не указание, как этот int вычислить, если вдруг понадобится.

                                                                                                                      А причём тут «как вычислять»? «как вычислять» — это ваша локальная специфика, название уровня ваших абстракций. На уровне матчасти никаких «как вычислять нет», а есть код и данные, да и даже между ними разницы нет и код тоже данные.

                                                                                                                      Поэтому, что там навешано на объект — это неважно, неважно как оно называется на уровне абстракций.

                                                                                                                      Тут было бы иронично вспомнить про SSA в процессе компиляции, но то такое.

                                                                                                                      Тут никаких противоречий нет.

                                                                                                                      Это свойства конкретной структуры данных и её взаимодействия с компилятором, но не её семантика. Хотя, может, мы по-разному определяем семантику, хз.

                                                                                                                      Это именно семантика, в вашем случае. Ведь нужен был не просто массива, вы вкладывали в него иной смысл. И все вкладывают в него иной смысл. Возможно за вас кто-то уже вложил в используемый вами массив нужный смысл и именно этим вызвано ваше непонимание моих рассуждений.

                                                                                                                      Просто подумайте. У вас есть массив с value-типом. Подошел ли вам массив другой? Не с value-типом. Он бы соответствовал определённой вами семантики, но нет — он бы вам не подошел и вы бы искали другой. Потому что на этом уровне семантика чуть шире базовой.

                                                                                                                      А, кстати, как строить графички на плюсах, вы так и не рассказали, увы :(

                                                                                                                      Не знаю. Я не занимаюсь графиками. Если что-то нужно — использую упомянутый выше gnuplot, либо какой-нибудь онлайн-сервис. Но нужно это мне это крайне редко.

                                                                                                        0
                                                                                                        Отвечу на некоторые общие вопросы:

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

                                                                                                        Нет, это наивное допущение. Это лишь показывает существования таких алгоритмов, которые работают одинаково плохо ВЕЗДЕ, а декларативщина — это прост одно из этого множества «плохо».

                                                                                                        Это примерно как взять человека без ног и с ногами, замотать в ковёр и заставить кататься. А после сказать, что мы получили «нижнюю границу оверхеда отсутствия ног». Нет. Вы выбрали такую игру, в которой забрали у человека с ногами его преимущество — его ноги. По-сути сделав его таким безногим.

                                                                                                        За свободу приходится расплачиваться.

                                                                                                        За всё приходится, свобода в этом плане не является чем-то уникальным.
                                                                                                        Чуть большим объёмом кода

                                                                                                        Кода на хаскеле больше.

                                                                                                        чуть меньшей безопасностью, чуть меньшей дружественностью к рефакторингу, вот это всё.

                                                                                                        Это всё правильно, но есть нюансы. Говорить об этом попросту нету смысла. Если зада требует производительности и масштаба — все эти рассуждения тут же теряют смысл.

                                                                                                        Причина проста — все конкуренты тут же исчезаю и лоулевел мир остаётся сам с собою. И тут уже неважно насколько безопасен хаскель — он попросту выносится за скобки, т.к. применения не имеет.

                                                                                                          +1
                                                                                                          Это лишь показывает существования таких алгоритмов, которые работают одинаково плохо ВЕЗДЕ, а декларативщина — это прост одно из этого множества «плохо».

                                                                                                          Ну почему одинаково. Вон, с Go интересные своей неконсистентностью результаты, например. Питон работает на пару порядков медленнее.


                                                                                                          Кода на хаскеле больше.

                                                                                                          Чем на плюсах? Нет, даже тупо по строкам.


                                                                                                          Причина проста — все конкуренты тут же исчезаю и лоулевел мир остаётся сам с собою.

                                                                                                          Только мы не говорим сейчас о лоу-левеле.

                                                                                                            0
                                                                                                            Ну почему одинаково.

                                                                                                            Люди привели уже тысячи примеров, я привёл жаваскрипт. Везде результаты одного и того же порядка. К тому же, люди писали(как и я) просто первое, что придёт в голову. Вы же занимались оптимизацией.

                                                                                                            Вон, с Go интересные своей неконсистентностью результаты, например.

                                                                                                            Вполне типичные результаты.

                                                                                                            Питон работает на пару порядков медленнее.

                                                                                                            Питон не имеет jit, а я говорил именно о jit+. К тому же, я уверен что эти «порядки» были просто наивным кодом. Если там взять либу с массивчиком(как сделали вы), прикрутить unsafe и какое-нибудь pypy с житом — результат будут другие, я уверен.

                                                                                                            Чем на плюсах? Нет, даже тупо по строкам.

                                                                                                            Да, особенно по строкам:

                                                                                                                std::vector<int64_t> arr(n + 1);    
                                                                                                                for(int64_t k1 = 1; k1 <= int64_t(std::sqrt(n)); ++k1) {
                                                                                                                  for(int64_t k2 = k1; k2 <= n / k1; ++k2)
                                                                                                                    arr[k1 * k2] += (k1 != k2 ? k1 + k2 : k1);
                                                                                                                }


                                                                                                            Здесь меньше строк и во много раз меньше синтаксического мусора.

                                                                                                            Только мы не говорим сейчас о лоу-левеле.

                                                                                                            А о чём же? Любой unsafe это по определению лоулевел. Как минимум относительно абстракций. Любая производительность — лоулевел.

                                                                                                              +1
                                                                                                              Люди привели уже тысячи примеров, я привёл жаваскрипт. Везде результаты одного и того же порядка.

                                                                                                              Особенно на питоне и прологе.


                                                                                                              К тому же, люди писали(как и я) просто первое, что придёт в голову.

                                                                                                              Я про TLB знаю и слышал, но вот не пришло в голову. Снимаю перед вами шляпу, что заменить аллокатор на таковой с mmap или же поковырять transparent hugepages вам в голову приходит сразу, и вы так пишете всегда.


                                                                                                              Вы же занимались оптимизацией.

                                                                                                              И варианты оптимизации выше нигде не обсуждались? Замена accumArray на unsafeAccumArray порядок времени выполнения тоже не меняет так-то.


                                                                                                              Если там взять либу с массивчиком(как сделали вы)

                                                                                                              Если она будет частью стандартного питона (а у питона есть стандарт или хотя бы report?) — да без проблем.


                                                                                                              Здесь меньше строк и во много раз меньше синтаксического мусора.

                                                                                                              Ну так сравнивайте тогда с


                                                                                                              arr = A.accumArray (+) 0 (1, n) premap :: A.UArray Int Int
                                                                                                              premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1)
                                                                                                                       | k1 <- [ 1 .. floor $ sqrt $ fromIntegral n ]
                                                                                                                       , k2 <- [ k1 .. n `quot` k1 ]
                                                                                                                       ]

                                                                                                              Особенно от явных for в коде на плюсах меньше мусора, наверное.


                                                                                                              Фиг с ним, что n ещё надо получить, что последний элемент надо куда-то вернуть/показать, что с этим всем счастьем надо что-то дальше делать.


                                                                                                              Любой unsafe это по определению лоулевел. Как минимум относительно абстракций.

                                                                                                              Нет. Тот же Clean, я слышал, вообще чудеса творит. Но Clean я не знаю, и линейные типы чуть менее обобщаются, чем монады, увы, поэтому хаскель для практических применений интересен.


                                                                                                              Ну и про unsafe я не зря написал в заключении. Его можно убрать повышением абстракций и выразительности, а не понижением: просто требуя доказательство того, что индекс не вылезает за границы. Если его нельзя построить статически, во время компиляции, то будет классическая рантайм-проверка. Если его построить статически можно (а здесь можно) — никаких проверок в рантайме не будет.


                                                                                                              Увы, хаскель пока ещё не здесь. Ждём полноценные зависимые типы.

                                                                                                                0
                                                                                                                Особенно на питоне и прологе.

                                                                                                                Да что вы прицепились к пистону. Я не знаю питона и не могу вам точно сказать — можно или нет. Но раз в pypy есть jit — я уверен, что производительность он выдаст.

                                                                                                                И варианты оптимизации выше нигде не обсуждались? Замена accumArray на unsafeAccumArray порядок времени выполнения тоже не меняет так-то.

                                                                                                                Да не особо — тут нечего оптимизировать просто. Кто-то умеет в unsafe, у кого-то рантайм не такой тормозной.

                                                                                                                В любом случае вся эта борьба — борьба хаскелей с жаваскриптами. У нас есть просто наивный код на С++ и далее идёт соревнование уровня «кто сможет в этом хелоуворлде показать меньший оверхед». Замечу, оверхед не меньший/равный С++, не меньшей/равный в целом, а просто в рамках это задачи.

                                                                                                                У С/С++ по-сути отняли тут всё. Это нечестно.

                                                                                                                Если она будет частью стандартного питона (а у питона есть стандарт или хотя бы report?) — да без проблем.


                                                                                                                Но Clean я не знаю

                                                                                                                Как и я.

                                                                                                                Его можно убрать повышением абстракций

                                                                                                                Всё можно убрать, особенно постфактум. Как и в питоне можно сделать супер-массивы. Но мы имеем что имеем.
                                                                                                                  0
                                                                                                                  Кто-то умеет в unsafe, у кого-то рантайм не такой тормозной.

                                                                                                                  Так мы ж сверху договорились, что порядок величины не важен. Ну в два раза медленнее из-за проверок, подумаешь.


                                                                                                                  У С/С++ по-сути отняли тут всё. Это нечестно.

                                                                                                                  Чем отняли-то?


                                                                                                                  Всё можно убрать, особенно постфактум. Как и в питоне можно сделать супер-массивы. Но мы имеем что имеем.

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

                                                                                                                    0
                                                                                                                    Так мы ж сверху договорились, что порядок величины не важен. Ну в два раза медленнее из-за проверок, подумаешь.

                                                                                                                    Дело не в этом. Дело в том, что есть некая базовая(самая примитивная) и единственно возможная имплементация — она написана на условном С++, императивно. Т.е. она примитивна и убога — её может повторить кто угодно, вот все и занимаются эти.

                                                                                                                    И смысл олимпиады в том, что попытаться выпилить из своего языка тонны оверхеда и проблем, которые не дают написать аналогичный условному С++ код. А то, что у кого-то там на копейку меньше, а у кого-то больше — это мало что меняет.

                                                                                                                    Смысл тут в том, что быстрее вы уже не сделаете. А вот питонист может сделать и мы не может у него это право забрать. Поэтому мы уславливаемся, что если все решения ± равны — они равны.

                                                                                                                    Чем отняли-то?

                                                                                                                    Ну как чем — задачей, которая является каноничным антипаттерном для всего, что связано с оптимизацией. Везде и во всём.

                                                                                                                      0
                                                                                                                      Смысл тут в том, что быстрее вы уже не сделаете. А вот питонист может сделать и мы не может у него это право забрать. Поэтому мы уславливаемся, что если все решения ± равны — они равны.

                                                                                                                      Я всё равно не понимаю, в чём вопрос. Что C++ — бейзлайн? Что другие мейнстримные языки позволяют убирать оверхед?


                                                                                                                      Ну как чем — задачей, которая является каноничным антипаттерном для всего, что связано с оптимизацией. Везде и во всём.

                                                                                                                      Отсутствие дальнейших не-алгоритмических оптимизаций лично мне неочевидно.

                                                                                                                  0
                                                                                                                  А добавьте многопоточную хаскель-версию. Я могу добавить С++-версию.
                                                                                                                    +1

                                                                                                                    На атомиках будете делать или непересекающиеся куски массива в разных тредах обрабатывать? Я начал делать на C++ на атомиках ради интереса, когда кто-то там вверху привёл пример на Rust, потом мне стало лениво вычислять в очередной раз правильное разбиение интервалов для k1 по тредам, и я забил.


                                                                                                                    Я на хаскеле могу только с оверхедом по памяти масштаба размера чанка на количество потоков :(

                                                                                                                      0
                                                                                                                      На атомиках будете делать

                                                                                                                      Ну да, сравнить же нужно.

                                                                                                                      Я на хаскеле могу только с оверхедом по памяти масштаба размера чанка на количество потоков :(

                                                                                                                      Ну хоть что-то.
                                                                                                                        +1
                                                                                                                        Ну хоть что-то.

                                                                                                                        На атомиках тоже можно. Берёте primops, пишете императивный код в IO, получаете жутко неидиоматичный код с более-менее той же производительностью, как на плюсах. Смысла в этом нет, правда, для клиентского кода.


                                                                                                                        Хотя, судя по сигнатуре, можно и в чистую State завернуть. ХЗ, надо поиграться будет.

                                                                                                                          0
                                                                                                                          Не получается у меня запустить код на расте — там используется левая либа. Выбывает он из битвы.
                                                                                                                            0
                                                                                                                            cargo new test_divs --bin
                                                                                                                            cd test_divs
                                                                                                                            echo 'clap = "2"' >> Cargo.toml
                                                                                                                            echo 'rayon = "1"' >> Cargo.toml

                                                                                                                            Если на Windows, то echo делать без одинарных кавычек.

                                                                                                                            Положить исходник в src/main.rs и

                                                                                                                            cargo rustc --release -- -C target-cpu=native -C opt-level=3

                                                                                                                            Бинарник будет в target/release
                                                                                                            0
                                                                                                            #include <vector>
                                                                                                            #include <cmath>
                                                                                                            #include <iostream>
                                                                                                            #include <thread>
                                                                                                            #include <atomic>
                                                                                                            
                                                                                                            int main(int argc, char ** argv) {
                                                                                                              if(argc < 2) {
                                                                                                                std::cerr << "Usage: " << argv[0] << " maxN" << std::endl;
                                                                                                                return 1;
                                                                                                              }
                                                                                                            
                                                                                                              int64_t n = std::stoi(argv[1]);
                                                                                                              int64_t nthreads = std::stoi(argv[2]);
                                                                                                            
                                                                                                              std::vector<std::atomic<int64_t>> arr(n + 1);
                                                                                                              
                                                                                                              auto work = [&](size_t nthreads, size_t tnum, int64_t n) {
                                                                                                                for(int64_t k1 = tnum; k1 <= int64_t(std::sqrt(n)); k1 += nthreads) {
                                                                                                                  for(int64_t k2 = k1; k2 <= n / k1; ++k2)
                                                                                                                    arr[k1 * k2] += (k1 != k2 ? k1 + k2 : k1);
                                                                                                                }
                                                                                                              };
                                                                                                              
                                                                                                              auto run = [&](size_t nthreads) {
                                                                                                                std::vector<std::thread> out;
                                                                                                                for(size_t tnum = 1; tnum <= nthreads; ++tnum)
                                                                                                                  out.emplace_back(work, nthreads, tnum, n);
                                                                                                                return out;
                                                                                                              };
                                                                                                              
                                                                                                              for(auto & x: run(nthreads)) x.join();
                                                                                                              
                                                                                                              std::cout << arr[n] << std::endl;
                                                                                                            }


                                                                                                            Побенчил ещё то, что мог запустить:

                                                                                                            66,468976022 seconds time elapsed - go mt
                                                                                                            64,819841304 seconds time elapsed - go
                                                                                                            64,380398227 seconds time elapsed - go v3

                                                                                                            64,001787006 seconds time elapsed - hs
                                                                                                            62,100266396 seconds time elapsed - c++ + gcc
                                                                                                            47,760004537 seconds time elapsed - c++ mt + gcc
                                                                                                            51,243138067 seconds time elapsed - c++ mt + clang
                                                                                                            80 sec - nodejs(32 бита числа)

                                                                                                              0

                                                                                                              А у вас сколько ядер?


                                                                                                              Ускорение на четверть — это ж адски плохо для такого алгоритма. И вот тут бы у вас, кстати, плюсы засияли, потому что вы из разных тредов в один std::vector писать можете, а я из разных тредов в один array без потери ленивости по списку писать не могу.

                                                                                                                0
                                                                                                                А у вас сколько ядер?

                                                                                                                Там ненужно много ядер — оно уже двух перестаёт расти, а на 4х начинает деградировать.

                                                                                                                Ускорение на четверть — это ж адски плохо для такого алгоритма.

                                                                                                                Нет, с чего вдруг? Алгоритм говном — для него всё плохо.

                                                                                                                И вот тут бы у вас, кстати, плюсы засияли, потому что вы из разных тредов в один std::vector писать можете

                                                                                                                Нет. Дефолтная десктопная/e3 платформа штеуда утилизирует практически 70-80 трупута памяти. Поэтому никакие наивные представления про ускорение — здесь не прокатывают. Да, код подобного уровня никогда не снимет даже 10-20% трупута памяти, поэтому и существует какие-то наивные оценки на тему.

                                                                                                                Но тут есть одна проблема. Из-за того, что алгоритм говно — получается так, что он съедая 10-20% трупута — съедает почти весь.

                                                                                                                Причина заключается в следующим: кэш не умеет читать память байтами, 4 байта, 8 байтами, даже 32 не умеет — только кешлайнами, а это 64 байта.

                                                                                                                Поэтому, при RA в память в подобном кейсе на каждое чтение int64_t на самом деле читает 64 байта, то же самое и с записью. Именно поэтому и наблюдает такое поведение. Код говно, алгоритм говно, а каналы до памяти все сожраны.

                                                                                                                К тому же. не стоит забывать, что атомики сами по себе имеют большой оверхед и сравнивать надо не с дефолтным вариантом, а с запуском на одном треде(второй аргумент там — кол-во тредов). Там, скорее всего, будет секунд 100(если не больше) — я не проверял.

                                                                                                                  0
                                                                                                                  Нужно искать людей с amd, либо с e5/2011 платформой. Там должен быть профит куда сильнее. На худой конец можно на амазоне тачку снять и погонять бенчмарки.
                                                                                                                +1
                                                                                                                66,468976022 seconds time elapsed - go mt
                                                                                                                64,819841304 seconds time elapsed - go
                                                                                                                64,380398227 seconds time elapsed - go v3

                                                                                                                64,001787006 seconds time elapsed - hs
                                                                                                                62,100266396 seconds time elapsed - c++ + gcc
                                                                                                                47,760004537 seconds time elapsed - c++ mt + gcc
                                                                                                                51,243138067 seconds time elapsed - c++ mt + clang//я проверил множество раз
                                                                                                                80 sec - nodejs(32 бита числа)

                                                                                                                67,263350647 seconds time elapsed - rust(rustc 1.33.0)
                                                                                                                50,179576857 seconds time elapsed - rust mt
                                                                                                                47,933258835 seconds time elapsed - rust mt + taskset

                                                                                                                  0
                                                                                                                  мда, если не смотреть на mt, то раст слил не только хаскелю, но даже go — немного печалит этот факт.
                                                                                                                    +1
                                                                                                                    Проверил ещё раз:
                                                                                                                    Версия гцц:
                                                                                                                    gcc (Gentoo 8.3.0 p1.0) 8.3.0

                                                                                                                    Код автора против кода на расте из комментариев.
                                                                                                                    rust(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,588s
                                                                                                                    user 0m5,545s
                                                                                                                    sys 0m0,043s
                                                                                                                    cpp(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,188s
                                                                                                                    user 0m5,134s
                                                                                                                    sys 0m0,045s
                                                                                                                    rust(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,613s
                                                                                                                    user 0m5,572s
                                                                                                                    sys 0m0,040s
                                                                                                                    cpp(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,217s
                                                                                                                    user 0m5,173s
                                                                                                                    sys 0m0,043s
                                                                                                                    rust(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,620s
                                                                                                                    user 0m5,580s
                                                                                                                    sys 0m0,040s
                                                                                                                    cpp(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,192s
                                                                                                                    user 0m5,151s
                                                                                                                    sys 0m0,041s
                                                                                                                    rust(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,596s
                                                                                                                    user 0m5,556s
                                                                                                                    sys 0m0,040s
                                                                                                                    cpp(100kk):
                                                                                                                    249511591

                                                                                                                    real 0m5,206s
                                                                                                                    user 0m5,161s
                                                                                                                    sys 0m0,044s
                                                                                                                    rust(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m7,324s
                                                                                                                    user 1m6,325s
                                                                                                                    sys 0m0,995s
                                                                                                                    cpp(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m2,467s
                                                                                                                    user 1m2,069s
                                                                                                                    sys 0m0,395s
                                                                                                                    rust(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m7,135s
                                                                                                                    user 1m6,739s
                                                                                                                    sys 0m0,392s
                                                                                                                    cpp(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m2,446s
                                                                                                                    user 1m2,019s
                                                                                                                    sys 0m0,423s
                                                                                                                    rust(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m7,527s
                                                                                                                    user 1m7,133s
                                                                                                                    sys 0m0,390s
                                                                                                                    cpp(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m2,494s
                                                                                                                    user 1m2,051s
                                                                                                                    sys 0m0,440s
                                                                                                                    rust(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m7,133s
                                                                                                                    user 1m6,754s
                                                                                                                    sys 0m0,375s
                                                                                                                    cpp(1kkk):
                                                                                                                    2497558338

                                                                                                                    real 1m2,530s
                                                                                                                    user 1m2,139s
                                                                                                                    sys 0m0,383s



                                                                                                                      0
                                                                                                                      Как видно из habr.com/ru/post/445134/#comment_19961862, это не факт, а ошибка измерения.
                                                                                                                        +1
                                                                                                                        Какая ошибка? Нет никакой ошибки. Результаты аналогичные.
                                                                                                                          0
                                                                                                                          Да, извиняюсь. С группировкой строк не разобрался.

                                                                                                                  Only users with full accounts can post comments. Log in, please.