Rust 1.21

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

Там про codegen units, который по умолчанию равен 1. И пока, если не ошибаюсь, этот флаг ещё не попал в стабильную ветку.

А можно поподробнее про «ненастоящность» map-а?

Конечно можно! Поехали

Функциональный подход

Функциональный map — это наложение чистой функции на список значений. Так как функция чистая, то вместе с ленивостью это даёт возможность вычислять map как угодно, хоть задом наперёд, хоть параллельно. Ты же хочешь вычислять map veryHeavyFunc [1..100000] в 8 раз быстрее на своём 8-ядернике, не так ли?

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

Следующий код на Haskell вычисляет map параллельно

using (map f xs) (parList rdeepseq)

Императивный подход

Теперь, возвращаемся к Rust и заодно к Python.

Чистых функций нет, поэтому мы в любом случае жёстко привязаны к порядку вычисления map — строго слева направо. И никаких фокусов! Иначе будут другие побочные эффекты.

Хорошо, а если мы уверены, что наши функции всё же без побочных эффектов? Теперь-то можно посчитать параллельно? И снова нет! Здесь стреляет отсутствие ленивости (итераторы - это лишь суррогат ленивости). map обещает нам выдавать результаты строго по-одному «по мере надобности». Если мы запросим 8 значений, то они будут вычислять последовательно, потому что так написан код функции map. И этот никак не изменить. А для того, чтобы считать параллельно, нам придётся писать свою, отдельную функцию map8, которая будет выплевывать итератором уже не одно, а восемь значений за раз.

Вывод

В императивных языках типа Rust или Python итераторы (например, map) представляют собой инкапсулированную императивную подпрограмму. Подпрограмма имеет состояние, которые сохраняется между вызовами, и при каждом своём новом вызове вычисляет новый элемент. Когда вычислять больше нечего - сигнализирует об этом. Никакой функциональности здесь на самом деле нет. Ленивость есть, но на уровне кода (ведь такую же подпрограмму можно написать хоть на ANSI C, и в C будут итераторы!), а не на уровне языка.

P.S. Хотел ещё рассказать про fmap, но для одного поста будет многовато, пожалуй.

Если подать одно длинное слово (>80), то оно напечатется с лишним переносом строки в начале. Поправь.

Чистых функций нет, поэтому мы в любом случае жёстко привязаны к порядку вычисления map — строго слева направо. И никаких фокусов! Иначе будут другие побочные эффекты.

Fn — это чистая функция.

Хорошо, а если мы уверены, что наши функции всё же без побочных эффектов? Теперь-то можно посчитать параллельно? И снова нет!

Есть Rayon.

https://play.rust-lang.org/?gist=fe6b6f59f1405c1aefc5248c634a8b01&version... позапускай пару раз или увеличь N и посмотри на вывод.

const N: u32 = 10;
    
println!("singlethread");
(0..N)
    .filter(|x| x % 2 == 0)
    .map(|x| x * x)
    .for_each(|x| {
        println!("thread {:?}, got {}", thread::current().id(), x);
    });

println!("multithread");
(0..N)
    .into_par_iter() // вот в чём разница
    .filter(|x| x % 2 == 0)
    .map(|x| x * x)
    .for_each(|x| {
        println!("thread {:?}, got {}", thread::current().id(), x);
    });

Если ты попробуешь взять mut ссылку на внешнее значение, то получишь ошибку времени компиляции.

Fn — это чистая функция.

Ты точно в этом уверен? Ты знаешь определение чистой функции?

Я почитал описание трейта. Там ничего не говорится про чистоту или побочные эффекты. Только вот это:

The version of the call operator that takes an immutable receiver.
Instances of Fn can be called repeatedly without mutating state.

Но это совсем не одно и то же.

Чтобы проверить это, мне пришлось написать второй в моей жизни код на Rust (первый код был выше в этой же теме). Так что снова предупреждаю, что там могут быть косяки.

Я просто немного переделал код из секции Examples

fn call_with_one<F>(func: F) -> usize
    where F: Fn(usize) -> usize {
    func(1)
}

fn double(x: usize) -> usize {
    println!("{} has just been doubled", x);
    x * 2
}

fn main() {
    assert_eq!(call_with_one(double), 2);
    for i in (0..10).map(double) {
        println!("{}", i);
    }
}

Однако чистая функция не имеет правда что-то печатать! И это критично для нашего разговора о map, потому что раз это итератор, то он может быть завершен досрочно, если оставшиеся значения нам больше не нужны. Получается, что побочные эффекты (вывод на экран) от (0..10).map(double) начинают зависеть от того, что с этим итератором дальше делают. Это недопустимо для чистых функций.

в хаскеле тоже есть Debug.Trace

хотя не утверждаю, что Fn = pure

в хаскеле тоже есть Debug.Trace

Да, как и System.IO.Unsafe... Но мы оба понимаем, в чём разница, не так ли?

Ты точно в этом уверен? Ты знаешь определение чистой функции? ... Однако чистая функция не имеет правда что-то печатать!

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

Всё же, твой пример с Rayon выглядит довольно интересно.

(0..N)
    .into_par_iter() // вот в чём разница
    .filter(|x| x % 2 == 0)
    .map(|x| x * x)
    .for_each(|x| {
        println!("thread {:?}, got {}", thread::current().id(), x);
    });

Как это работает?

Мне не на чем это запустить, остаётся только гадать. Предполагаю, что into_par_iter() оборачивает входные u32 во что-то типа pair{u32, u32}, и для этих pair перегружены арифметические операции. Тогда это работает только за счёт того, что |x| x * x и |x| x % 2 == 0 полиморфны по x. Если вместо лямбды в map передать функцию с сигнатурой u32 -> u32, которая объявленая где-то выше, то это просто не скомпилируется. Угадал? Если всё же нет, и это скомпилируется и будет работать, то я прям поверю в Rust =) Хотя я и так давно к нему присматриваюсь, вон даже на тег подписался...

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

Короче, «специальный параллельный map», о котором я и писал, в общем-то. Только наличие перегрузок позволяет использовать то же ключевое слово map, но сути это не меняет.

Мне не на чем это запустить, остаётся только гадать.

Запускай на https://play.rust-lang.org.

Как это работает?

Ничего выдающегося, все параллельные итераторы сделаны вручную.

Если вместо лямбды в map передать функцию с сигнатурой u32 -> u32, которая объявленая где-то выше, то это просто не скомпилируется. Угадал? Если всё же нет, и это скомпилируется и будет работать, то я прям поверю в Rust =)

Можно использовать обычные функции.

fn is_even(x: &u32) -> bool {
    *x % 2 == 0
}

fn double(x: u32) -> u32 {
    x * x
}
    
(0..N)
    .into_par_iter()
    .filter(is_even)
    .map(double)
    .for_each(|x| {
        println!("{:?}, got {}", thread::current().id(), x);
    });

все параллельные итераторы сделаны вручную.

То есть всё-таки «специальный параллельный map», точнее параллельный итератор. Спасибо.

Ну и всё равно выглядит очень даже неплохо. Разумный трейд-офф в условиях системщины.

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

В Rust нет перегрузок функций, а map не ключевое слово.

нет, я не в курсе

Кейворд тот же, а сигнатура другая

сигнатура та же, реализация другая

вот следующая итерация: дан итератор по словам (в случае хаскеля - список) ... нужно их разбавить пробелами и \n, чтобы по ширине влезло в 80 символов

Вот тебе функциональное решение на функциональном хаскеле.

format words width sep line_sep = fst $ foldl append ("", 0) words where
    append (lines, len) word
        | len == 0                               = (lines ++ word, length word)
        | len + length sep + length word > width = (lines ++ line_sep ++ word, length word)
        | otherwise                              = (lines ++ sep ++ word, len + length sep + length word)

Тестировать можешь в REPL

λ> let words = ["alpha", "beta", "gamma", "delta", "epsilon", "zeta", "eta", "theta", "iota", "kappa", "lambda"]
λ> putStrLn $ format words 20 " " "\n"

alpha beta gamma
delta epsilon zeta
eta theta iota kappa
lambda

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

скажи только, если в итеративной функции будет штук 5 локальных переменных, ты их так же будешь таскать в tuple?

скажи только, если в итеративной функции будет штук 5 локальных переменных, ты их так же будешь таскать в tuple?

Всё зависит от задачи, надо смотреть.

Конкретно в этой эффективнее хранить «локальную переменную» в фолде, чем честно вычислять каждый раз эту len, потому что для этого пришлось бы решать подзадачу «поиск подстроки в строке» (line_sep в lines), да ещё и с конца строки, что мягко говоря неоптимально.

Конкретно в этой эффективнее хранить «локальную переменную» в фолде

само собой, что не пересчитывать на каждой итерации

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

Ассемблер — не язык. 

Что за редкостный бред?

Вычисления с состоянием делаются через монаду State

Ты неправ, Fn не гарантирует чистоту, так как Fn может захватывать Rc<RefCell<T>>.

Предполагается, что если ты написал RefCell<T>, то ты берешь на себя заботу о внутреннем состоянии T, таким образом функция получается «чистая» в том смысле, что нет побочных эффектов у тех ресурсов, за которые ответственнен раст

Не согласен. В расте все что «ты берешь на себя заботу о внутреннем состоянии» явно отмечено unsafe. Что, кстати, большой плюс раста.

В расте можно явно снимать гарантии. RefCell снимает RWLock, точнее переносит его в рантайм, а unsafe - согласованность памяти на плечи разработчика, получаются немного разные уровни согласованности