#prog #article

Статья про специализированный язык программирования для манипуляций с массивами. Интересен тот факт, что язык фактически является подмножеством F#, а реальная компиляция проводится с трансляцией в C.

We show how to compile high-level functional array-processing programs, drawn from image processing and machine learning, into C code that runs as fast as hand-written C. The key idea is to transform the program to destination-passing style, which in turn enables a highly-efficient stack-like memory allocation discipline.

Спойлер: производительность на уровне Eigen. Да, настолько круто.

https://www.microsoft.com/en-us/research/publication/using-destination-passing-style-compile-functional-language-efficient-low-level-code/

#prog #science

Залипательная симуляция гравитации с открытым исходным кодом (к сожалению, на JS — идеальный кандидат на переписывание на Wasm!).

https://hermann.is/gravity/

#prog #haskell #meme

И ведь не поспоришь

#prog #rust #моё

В стандартной библиотеке Rust есть замечательное определение итератора. Оно выглядит следующим образом:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // и ещё уйма методов, все из которых имеют реализацию по умолчанию
}

Это определение замечательно тем, что, в отличие от канонического определения из GoF здесь нет места вопросу "что возвращает next, если hasNext вернул false": при использовании итератора элементы достаются, пока .next() возвращает Some(_). Тем не менее, поведение итератора после того, как он вернул None, не является частью контракта итератора: разные конкретные реализации могут возвращать, а могут и не возвращать новые элементы. Конечно, большинство итераторов возвращают None после того, как в них закончились элементы, но в общем случае это не так. В частности, std::iter::from_fn создаёт итератор, который для получения следующего f просто вызывает замыкание, переданное в функцию аргументом. Не зная ничего об этом замыкании, нельзя сделать никаких выводов по поведению итератора.

В некоторых случаях, когда итератор используется более интересным образом, чем просто из цикла for, для корректности кода нужно, чтобы вызовы next после возврата None продолжали возвращать None. Такие итераторы называют плавлеными слитыми обезвреженными fused iterators. Для того, чтобы отделять агнцев от козлищ, стандартная библиотека предоставляет два инструмента:
1. Трейт FusedIterator, который, по идее, должен быть реализован всеми итераторами, которые ведут себя желаемым образом (к сожалению, корректность подобной реализации находится целиком и полностью на совести программиста (где, чёрт возьми, мой прувер для раста?!));
2. Метод Iterator::fuse, который оборачивает итератор в адаптер Fuse, гарантирующий fused поведение.

Второй метод связан со вторым: благодаря специализации, если Fuse оборачивает итератор, реализующий FusedIterator, то вызов next у Fuse просто вызывает метод next у нижележащего оператора. Как написано в документации к FusedIterator:

"Note: In general, you should not use FusedIterator in generic bounds if you need a fused iterator. Instead, you should just call Iterator::fuse on the iterator. If the iterator is already fused, the additional Fuse wrapper will be a no-op with no performance penalty."

Часть про no-op верна, а вот часть про "with no performance penalty" несколько сомнительна: Fuse хранит булев флаг, говорящий, вернул ли нижележащий итератор None или нет, даже несмотря на то, что для fused итераторов он не используется. Можно представить себе ситуацию, когда дополнительный флаг может привести к тому, что итератор перестаёт влезать в кэш процессора, что несколько ударяет по производительности. Это не zero-cost abstraction! Сегодня я займусь тем, что буду это исправлять.

Посмотрим, как реализован Iterator::next для Fuse:

    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
        if self.done {
            None
        } else {
            let next = self.iter.next();
            self.done = next.is_none();
            next
        }
    }

Здесь нагло эксплуатируется тот факт, что поле done имеет булев тип. Если мы хотим, чтобы адаптер не содержал флаг для fused итератора, нам нужно сделать тип флага зависящим от типа итератора. Т. к. теперь мы не можем считать флаг булевым, нам нужно абстрагироваться от конкретного типа. Немного перепишем реализацию метода:

    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
        if self.done {
            None
        } else {
            let next = self.iter.next();
            if next.is_none() {
                self.done = true;
            }
            next
        }
    }

Как видно, от флага требуется две операции: проверка на то, выставлен ли он, и его установка в положение "да, сэр, к сожалению, этот джентельмен вернул None". Также нам нужно каким-то образом получить начальное значение флага, когда мы создаём адаптер. Выразим это в трейте:

trait Flag: Default {
    fn is_set(&self) -> bool;
    fn set(&mut self);
}

Этот трейт тривиально реализуется для bool:

impl Flag for bool {
    fn is_set(&self) -> bool {
        *self
    }

    fn set(&mut self) {
        *self = true
    }
}

Теперь подумаем, что нам требуется для fused итератора. Наш метод next будет эквивалентен вызову next у нижележащего итератора, если флаг всё время ведёт себя так, как будто он не выставлен (рекомендую ещё раз посмотреть на код выше, чтобы убедиться в этом). Создадим соответствующий тип и реализуем для него Flag:

#[derive(Default)]
struct False;

impl Flag for False {
    fn is_set(&self) -> bool {
        false
    }

    fn set(&mut self) {}
}

Теперь нам нужно сопоставить каждому итератору соответствующий тип флага. Именно здесь нам понадобится специализация: по умолчанию для итератора флагом является булев тип, но для fused итераторов (т. е. реализующих FusedIterator) это будет False. Непосредственно функций на уровне типов в Rust нет, но их роль играют трейты с ассоциированными типами.

trait FlagType: Iterator {
    type Flag: Flag + Default;
}

impl<I: Iterator> FlagType for I {
    // ключевое слово default позволяет нам переопределять элементы трейтов
    // в более специфичных impl-ах...
    default type Flag = bool;
}

impl<I: FusedIterator> FlagType for I {
    // ...что мы и делаем
    type Flag = False;
}

Теперь напишем сам адаптер. Ничего сложного в нём нет, нужно только иметь в виду, что нам требуется тип, для которого определён флаг:

struct SlimFuse<I: FlagType> {
    iter: I,
    finished: I::Flag,
}

После всего описанного выше нетрудно написать реализацию Iterator:

impl<I: FlagType> Iterator for SlimFuse<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        if self.finished.is_set() {
            return None;
        }

        let ret = self.iter.next();
        if ret.is_none() {
            self.finished.set();
        }
        ret
    }
}

Осталось только приправить extension trait для того, чтобы адаптер было удобно создавать:

trait IteratorExt: Sized + FlagType {
    fn fuse_slim(self) -> SlimFuse<Self>;
}

impl<I: Sized + FlagType> IteratorExt for I {
    fn fuse_slim(self) -> SlimFuse<Self> {
        SlimFuse {
            iter: self,
            finished: <_>::default(),
        }
    }
}

Теперь проверим, как это всё работает:
use std::mem::size_of_val;
use std::iter;

// FromFn не реализует FusedIterator по понятным причинам
let it1 = iter::from_fn(|| None::<i32>).fuse();
let it2 = iter::from_fn(|| None::<i32>).fuse_slim();

// В этом случае SlimFuse не лучше (но и не хуже!), чем Fuse
assert_eq!(size_of_val(&it1), size_of_val(&it2));

// Итераторы возвращают одно и то же
assert!(it1.eq(it2));

// Теперь возьмём fused итератор. Все итераторы коллекций являются fused —
// в частности, std::slice::Iter.
let it1 = [1, 2, 3].iter().fuse();
let mut it2 = [1, 2, 3].iter().fuse_slim();

// Наш адаптер эксплуатирует свойства итератора и оказывается менее жирным!
assert!(size_of_val(&it1) > size_of_val(&it2));

// Проверим, что наш итератор выдаёт то же самое, что и стандартный
assert!(it1.eq(it2.by_ref()));

// Проверим, что с наш адаптер действительно fused
assert!(it2.by_ref().eq(iter::empty::<&i32>()));
assert!(it2.by_ref().eq(iter::empty::<&i32>()));

Замечательно. Торжество zero-cost абстракций!

Весь код в этих постах я выложил гистом на GitHub

#prog #kotlin #meme

Уже 150 подписчиков! 🎉 Хорошая скорость, однако

Me: can we have some Java?
Mom: we have Java at 3 bn devices
Java on 3 bn devices:

Тут, кстати, один технический блог в телеграме ожил: https://t.me/brain_dump_etc/366

Как бы и #meme, но держать в голове всё же стоит