Недавно узнал о новой для себя технике –
expression templates, это то знание, которого мне в свое время не хватило, когда
я писал парсер а-ля boost::spirit (нашел, кстати,
статью, в которой довольно подробно описано как устроен не весть, но часть boost::spirita).
Недавно встала задача выполнения простейших арифметических операций над большими массивами данных. Конечно, это дело можно запрограммировать по старинке, но хочется, чтобы все было красиво и прозрачно – и тут я решил поискать, как, же все таки работает boost::spirit, оказалось, что в его основе лежит очень красивая и элегантная идея (и все менее слоупоки чем я с ней давно знакомы, я думаю). Идея в том, что операции над операндами выполняются не в момент, когда эти операции встречаются в выражении, а только в тот момент, когда результат данного выражения нужен.
Как это делается? Для выражения на этапе компиляции строится дерево и для того, чтобы получить результат вычисления дерево просто обходится. Как это делается на плюсах? Основным строительным блоком является шаблонный оператор, состоящий из левого и правого операндов и операции между ними. Т.к. оператор шаблонный, то любой из операндов может быть точно таким же оператором (или любым типом, соответствующим требуемому интерфейсу).
Я уже говорил, что я решил использовать эту технику для операций над массивами, и тут есть два варианта:
- использовать готовую библиотеку (например,
tvmet).
- или написать свою примитивную.
Во втором случае, либо вектора должны соответствовать нужному интерфейсу, либо надо сделать небольшой адаптер (в этом случае придется написать большую кучу операторов, это видно у меня в примере). Как видно я выбрал второй вариант.
Набор классов для базовых операций (+, -, *, /) пишется за пол часа, ничего сложного нет.
Набор классов позволит нам довольно наглядно описывать действия над массивами. Кроме того, эта техника позволит избавиться от временных переменных для хранения результатов конкретных операций. В случае, когда массивы имеют большую размерность это приятный бенефит.
Второе, что я хотел сделать – это реализовать эти операции с использованием sse – во-первых хотелось наконец руками потрогать sse, во-вторых хотелось хоть не много сгладить потери в реализации, которые возможно (?) будут привнесены техникой.
Для эффективной реализации алгоритмов с sse необходимо, чтобы данные были выровнены на границу 16-байтного слова. По умолчанию стандартный аллокатор не выравнивает память и необходимо либо написать свой, либо найти аллокатор, совместимый со стандартным, который бы выравнивал выделяемую память. Как оказалось, простой аллокатор с такой функциональностью сделать совсем не сложно. Что я, конечно, и сделал.
Я сравнил что у меня получилось. Версия SSE2 обгоняет простую реализацию раза в полтора, а захардкоженная реализация тестового выражения обгоняет простую реализацию раза в два с половиной. Цифры:
Вот вроде и все.
Source code.
