haskell vs cpp

[Stalkert]

Продолжаем тему: www.linux.org.ru/forum/development/15224304

В чём цимес:

1. люди бенчили перемножение матриц;

2. вылез некий адепт Haskell с ленивостью, которая давала уменьшение асимптотики с O(N^3) до O(N);

3. было написано умножение строки на столбец с использованием ranges, которое как минимум на 3 порядка обгоняло Haskell;

4. так как в Haskell лень, видимо, несовметима с производительностью, была запрещена лень (!) и предоставлено какое-то другое решение на Haskell;

5. byko3y добавил в код на C++ цикл, который явно имеет асимптотику O(N^3). На основании бенчей этой версии и последней Haskell-версии он утверждает, что Haskell «не хуже» C++ ranges (к сожалению, само сообщение уже потёрли: www.linux.org.ru/forum/development/15204387?cid=15224273).

Проблема в том, что якобы «не ленивая» Haskell-версия имеет асимптотику O(N^2).

byko3y Там квадрат — ты просто бенчишь код разных асимптотик, т.е. то, чего ты пытался избежать, дописывая эту сумму в код на плюсах. Жду объяснений.

Дублирую своё сообщение:

смотри, что у меня есть:

* исправляем код на Haskell, чтобы он выводил время в наносекундах:

--- prog_orig.hs	2019-09-15 17:07:11.037239231 +0300
+++ prog.hs	2019-09-15 17:07:29.213158203 +0300
@@ -30,7 +30,7 @@
   printf "% 8.6f\n" (c' ! ((n `div` 2), (n `div` 2)) )
   
   t2 <- clock
-  printf "%ds\n" $ (t2 - t1) `div` 1000000000
+  printf "%.0f\n" (fromIntegral (t2 - t1) :: Double)
 
 newMatrix :: Int -> Matrix
 newMatrix n =

* компилируем: ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math prog.hs -o hs

* бенчим его следующим образом:

for n in 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000; do
    { read ans; read time; } < <(./hs $n)
    echo "$n $time"
done | tee ans

Получаем следующее:

300 80075088
400 164785062
500 322816474
600 559779632
700 885822519
800 1320158619
900 1871346121
1000 2557781529
1100 3745216222
1200 4540687171
1300 5593409421
1400 6989378443
1500 8575799688
1600 10421996451
1700 12478071662
1800 14808936430
1900 17376381098
2000 20289554452

А теперь смотри, клоун: https://i.imgur.com/0FvLb08.png

 c++, haskell