спецолимпиадное

[thedeemon]

По мотивам поста Никиты про разницу в производительности "высокоуровнего/функционального" и "низкоуровнего/императивного" кода. Взял буквально его пример с созданием массива пар чисел. Его оригинал на кложе:

(concat
(mapv
(fn [y] [from-x y])
(range from-y (quot to-y 2)))
(mapv
(fn [y] [to-x y])
(range (quot to-y 2) to-y)))

Как быстро он работает - не представляю.

Попробовал обе версии - "функциональную" и "императивную" - записать на D в качестве эксперимента, посмотреть, насколько компилятор справляется это дело развернуть.

struct Point { int x, y; }

auto f(int from_y, int to_y, int from_x, int to_x) {
return chain( iota(from_y, to_y/2).map!(y => Point(from_x, y)),
iota(to_y/2, to_y) .map!(y => Point(to_x, y)) ).array;
}

auto g(int from_y, int to_y, int from_x, int to_x) {
auto res = new Point[to_y - from_y];
foreach(y; from_y .. to_y)
res[y - from_y] = Point(y < to_y / 2 ? from_x : to_x, y);
return res;
}

На 60 миллионах точек ( f(20_000_000, 80_000_000, 1, 2) ) "функциональный" у меня работает 167 мс, "императивный" - 146 мс, разница в пределах 15%. Терпимо.
(полный текст тут, компилятор - LDC)

Попробовал записать это дело на хаскеле, но в нем я нуб, не знаю, как правильно его готовить. Вот такой вариант

import qualified Data.Vector.Unboxed as V
type Point = (Int, Int)

f :: Int -> Int -> Int -> Int -> V.Vector Point
f from_y to_y from_x to_x =
let a = V.generate (to_y `div` 2 - from_y) (\y -> (from_x, y+from_y))
b = V.generate (to_y - to_y `div` 2) (\y -> (to_x, y + to_y `div` 2))
in V.concat [a, b]

на тех же исходных данных работает 1.33 сек, т.е. примерно на порядок медленнее. Другие варианты, что я пробовал, еще медленнее. Например, если data Point = P {-# UNPACK #-} !Int !Int, то оно уже не Unboxed, и если просто Data.Vector для них использовать, то время больше трех секунд уже.
Вопрос хаскелистам: как вы unboxed массив простых структур делаете?