GLU-1: FusedFunctor
Введение
Дальнейшее развитие программы-демонстратора триангуляции средствами GLU.
В качестве эксперимента была опробована методика, названная здесь «fused functors» («слияние функторов»). Это эксперимент, а не пример распространённой или рекомендуемой практики. Суть методики в объединении нескольких действий, выполняемых над одними и теми же элементами массива (первоначально вершинами контура) и/или их последовательными парами (первоначально отрезками, составляющими контур). Можно продолжить на n-ки произвольной длины (например, все последовательные тройки вершин позволяют обработать углы контура). Код здесь: GLUPoly-1.2.7z. Объединение нескольких действий задумано с тем, чтобы выполнять их не за несколько проходов, а за один.
FusedFunctor
Итак, функтор, допускающий «слияние», строго говоря не является функтором в терминах C++, так как не переопределяет operator(). Класс, который можно назвать «FusedFunctor» должен предоставлять следующее.
- Вложенные типы argument_type (тип обрабатываемых элементов массива) и result_type (результат обработки, возвращаемый в конце, может быть void, например, если begin/fuse складывают элементы в контейнер или выводят в поток).
- Функции начала процесса void begin (argument_type) и void begin (argument_type, size_t n), в качестве первого параметра принимающие первый обрабатываемый элемент, в качестве n может передаваться общее количество элементов, если оно известно заранее (да, элементы могут поступать произвольным образом, а не выбираться из массива).
- Функция обработки следующего элемента void fuse (argument_type), вызывается для всех элементов кроме первого в порядке их поступления.
- Функция завершения процесса result_type end(), возвращающая конечный результат (если result_type не void).
Функционал разбит на три заголовочных файла. На диаграмме ниже показано их содержимое.
Стрелочкой «A ← b» показаны случаи, когда функция b возвращает объект класса A. Назначение этих функций в увеличении удобства использования классов (аналогично std::pair ← std::make_pair, чтобы не выписывать явно параметры шаблонов, если они выводимы).
FusedFunctor.h
Функция applyFused применяет fused functor к диапазону, заданному парой итераторов. Если итераторы относятся к категории RandomAccessIterator, то используется вариант begin с указанием количества элементов.
Два fused functor’а можно объединить, используя combineFused. При этом результат второго функтора игнорируется. Данная функция используется в конструкторе Mesh2.
Остальное содержимое файла имеет вспомогательное назначение. Функции fuseVoidBy1, fuseBy1 и fuseBy2 позволяют «конвертировать» обычный функтор в fused functor (соответственно FusedVoidBy1, FusedBy1 и FusedBy2). Первая из них полагает, что функтор не возвращает результата (результат игнорируется). By1-варианты обрабатывают по одной вершине. By2-варианты обрабатывают все последовательные пары, в конце пару (последний элемент, первый элемент). Не-void варианты используют функтор «аккумулятор» для объединения результатов вызовов исходного функтора. По умолчанию используется InPlaceAdd, вызывающий operator+=.
Шаблоны ResultOf и ArgumentOf используются для вычисления типа (через вложенный тип type, такие шаблоны ещё называют метафункциями) результата функтора (для классов по умолчанию используется вложенный тип result_type) и типа аргумента (для классов используется вложенный тип argument_type). ArgumentOf работает и для бинарных функций (но не для функторов-наследников std::binary_function), однако, при необходимости можно либо явно задать тип аргумента в шаблоне, либо определить частную специализацию шаблона ArgumentOf, возвращающую нужный тип. Аналогично можно поступить и с ResultOf, впрочем, этот шаблон несколько «сильнее» засчёт того, что опирается на boost::result_of (который, в свою очередь, использует возможности C++11, если они доступны).
Вспомогательную роль играют boost::type_traits (common_type) и boost::call_traits (для вывода типа параметра из типа аргумента, для пользовательских классов по умолчанию выводится константная ссылка).
FusedForContour.h
В этот заголовочный файл включены средства, предназначенные для использования с объектами Contour, основанные на FusedFunctor.h. FusedPerimeter и FusedArea являются fused functor, и вычисляют соответственно периметр и площадь многоугольника. Они используются в Contour::perimeter() и Contour::area(). FusedContourPushBack заполняет объект контура вершинами.
FusedFunctorTuple.h
Данный файл не проверялся в деле, и, хотя некоторые ошибки относительно 1.1 были исправлены, вполне возможно, что остались ещё.
Функции functorsTuple/functorsTupleVoid можно использовать для объединения нескольких обычных функторов в один функтор, возвращающий n-ку («tuple», «кортеж») результатов (не-Void-вариант). Для конвертирования n-ки fused functor’ов в один fused functor предназначены fuseTuple/fuseVoidTuple (Void-вариант игнорирует результаты). Далее их опять же можно объединить с помощью combineFused (цель которой, собственно, не в объединении пары функторов, а в объединении того, что возвращает результат и того, что не возвращает).
Используется реализация n-ки из boost::fusion.
Вычисление чисел Фибоначчи во время компиляции
Не думаю, что кого-нибудь из программистов на C/C++, кроме, может быть, самых начинающих, затруднит написать функцию, вычисляющую по заданному целому числу n число Фибоначчи с номером n, используя O(n) цикл вместо O(n^2) рекурсии (получаемой переписыванием определения числа Фибоначчи на языке программирования).
В данный момент моя цель состоит не в демонстрации эффективного вычисления чисел Фибоначчи (их можно считать по аналитической формуле, кроме того, есть коллекция реализаций), а в демонстрации реализации линейного алгоритма на шаблонах C++ (похожий пример на Scheme).
Надеюсь, мой пример будет полезен изучающим обобщённое программирование на C++. Итак, заставим компилятор вычислить числа Фибоначчи «по определению».
// Fibonacci numbers via templates by definition
template <unsigned N> struct Fib
{
static const unsigned value =
Fib<N - 1>::value + Fib<N - 2>::value;
};
template <> struct Fib <0>
{
static const unsigned value = 0;
};
template <> struct Fib <1>
{
static const unsigned value = 1;
};
Теперь, например, Fib<10>::value == 55, что и требовалось. Естественно, параметр шаблона должен быть известен на момент компиляции. Линейный алгоритм использует предыдущее число, поэтому введём дополнительную константу prev. Далее, мы можем избавиться от упоминания Fib<N-2>, сохранив только Fib<N-1>.
// linear calculation of n-th Fibonacci number on templates
template <unsigned N>
struct Fib: protected Fib<N - 1>
{
protected:
static const unsigned prev =
Fib<N - 1>::value;
public:
static const unsigned value =
Fib<N - 1>::prev + prev;
};
template <> struct Fib <0>
{
protected:
static const unsigned prev = 0;
public:
static const unsigned value = 0;
};
template <> struct Fib <1>
{
protected:
static const unsigned prev = 0;
public:
static const unsigned value = 1;
};
Замечание 1. Использовать protected, конечно, необязательно (тем более в таком простом случае), это было сделано в целях разделения «интерфейса» (value) и «реализации».
Замечание 2. На самом деле первый вариант квадратичным не является, т.к. инстанцирование (подстановка формальных параметров шаблона) Fib<N> для разных N происходит только однажды. Например, вычислим Fib<6>::value.
Fib<6>::value = Fib<5>::value + Fib<4>::value
Fib<5>::value = Fib<4>::value + Fib<3>::value
Fib<4>::value = Fib<3>::value + Fib<2>::value
Fib<3>::value = Fib<2>::value + 1 // Fib<1>::value
Fib<2>::value = 1 + 0 // Fib<0>::value
=> Fib<2>::value = 1
=> Fib<3>::value = 2
=> Fib<4>::value = 3
=> Fib<5>::value = 5
=> Fib<6>::value = 8
Аналогичный (однократному инстанцированию) приём можно использовать в run-time вычислениях (w:memoization, пример на C++11).
2Dv3D
2Dv3D это GUI приложение, основная часть которого была написана мной в 2006 (затем оно обновлялось несколько раз), предназначенное для визуализации наборов (например, изменяющиеся во времени области плоскости) плоских множеств («слоёв»), заданных многоугольниками («контурами»). Для триангуляции многоугольников используется GLU. К слову, разработчикам, использующим OpenGL в FreePascal / Lazarus или Delphi, может быть полезен dglOpenGL.
Итак, я решил выложить 2Dv3D здесь. Приложение довольно специфическое, но может оказаться кому-нибудь полезным. Исходный код не выкладываю, ибо он страшен есть :). Файл readme.txt (как и manual) устарели, сначала читать readme_first.txt. Кроме того, в файле openfile.txt даётся описание опций диалога загрузки файлов. Некотрые окна (главная панель, отчёт) имеют меню, вызываемое правым кликом.
В папке samples (отсутствует в архиве 2Dv3D-0.48j-no-samples.7z) приведены три примера (промежуточные результаты работы программ построения решений в дифференциальных играх): screw.txt и pipe.txt имеют формат с «многосвязными слоями» (на самом деле односвязны), bridge.txt — с односвязными. Файлы pipe.txt и bridge.txt являются элементами «одной сцены» (трубка достижимости, огибающая мост).
2Dv3D-0.48j.7z (MD5: ce21e49106802cd298ac6dafac0a942b)
2Dv3D-0.48j-no-samples.7z (MD5: 06b69a832f3aaf4163f0935776403858)
Дальнейшее развитие этого приложения и исправление в нём ошибок не планируется.
GLU-1: SSE2 реализация Vec2
Введение
Старый вариант GLUPoly переименован в GLUPoly-1.0.7z. Ниже описаны отличия GLUPoly-1.1.7z.
Написана реализация Vec2 поверх SSE2, использующая интринсики (помещена в Vec2sse2.h). Старый Vec2.h переименован в Vec2std.h. Новый Vec2.h включает Vec2sse2.h, если компилируется MSVC под x64 или с параметром /arch:SSE2 (или /arch:AVX), иначе включает Vec2std.h.
Некоторые изменения были внесены в Bbox2.h (ускорение построения Bbox2 по набору Vec2).
Проблема 1
Для эффективного использования SSE следует выравнивать данные по 16-байтной границе, поэтому значения типа __m128d (пара 64-битных чисел с плавающей точкой, упакованная в 128-битное значение) выравниваются по 16-байт. Это свойство автоматически передаётся всем структурам/классам, включающим в себя __m128d.
Однако стандартные средства выделения памяти не гарантируют выравнивания нестандартных размеров (т.е., например, new int[100] будет выровнен по 4-байтной границе для 4-байтного int, а вот new __m128d[100] по 16-байтной границе уже может быть и не выровнен).
Простое решение этой проблемы достигается перегрузкой operator new и operator delete (попарно всех нужных форм, избыточные варианты delete требуются из-за того, что в случае бросания исключения из конструктора автоматически вызываются только «симметричные» delete, поэтому в случае отсутствия такого delete память не будет освобождена). Эти перегруженные операторы могут выделять память системно-зависимыми функциями, гарантирующими нужное выравнивание.
Недостаток такого решения — невозможность использования с контейнерами, использующими rebind::other аллокатора (например, std::list).
Принятое решение основано на двух дополнительных классах, размещённых в новом файле AlignedAllocator.h.
AlignedNewDeleteImpl<Align> реализует набор operator new/operator delete, выравнивающих по Align байт (Align == 16 для __m128d и, соответственно, SSE2-версии Vec2). Класс, которому нужно обеспечить выравнивание своих объектов, может наследовать от AlignedNewDeleteImpl. С другой стороны, AlignedNewDeleteImpl является обёрткой системно-зависимых функций выделения памяти (только отсюда они вызываются напрямую).
Замечание. Vec2 для простоты использует public-наследование. С точки зрения принципов использования наследования следует использовать private-наследование, однако оказалось, что using AlignedNewDeleteImpl::operator new и т.д. в public-секции не работает. Пока мне не ясно, с чем это связано. Конечно, можно это обойти, написав явную переадресацию вызовов.
AlignedAllocator<T, Align> реализует STL-совместимый аллокатор, для выделения объектов T средствами AlignedNewDeleteImpl. Его можно использовать непосредственно (Align по умолчанию устанавливается равным __alignof T) в качестве параметра шаблона STL-контейнера. «Правильный» аллокатор решает проблему rebind::other.
Кроме того, для удобства можно определить std::allocator для своего класса, чтобы каждый раз не приходилось указывать аллокатор (т.к. стандартный аллокатор всё равно не подходит, и его использование может оказаться латентной ошибкой), что и сделано для Vec2 путём наследования std::allocator<Vec2> от AlignedAllocator<Vec2>.
Проблема 2
Компилятор может «отказаться» передавать объекты с выравниванием поверх стандартных встроенных типов в функции как копии. Например, void foo (const __m128d&); компилируется, а void foo (__m128d); — нет.
К сожалению, в std::vector нашлась такая функция, а именно — resize (size_type, T), принимающая заполняющее значение как копию. Можно по-разному пытаться обойти эту проблему. В данном случае я выбрал решение «в лоб»: написать свою реализацию динамического массива Vec2: Contour (Contour.h и Contour.cpp). Данная реализация также использует SSE2 (для копирования /заполнения диапазонов), если был включен Vec2sse2.h.
UPDATE 08/12. В стандартной библиотеке C++11 эта функция изменена и теперь принимает ссылку. Таким образом, можно использовать std::vector из современных дистрибутивов STL (например, в составе Visual Studio 2012).
Тестирование
Solution теперь содержит два проекта: исходный GLUPoly и вспомогательный Tests (содержит только один файл test.cpp). Цель второго проекта — аккумуляция unit-тестов, проверяющих код из GLUPoly. На данный момент тестами покрыты Vec2, Bbox2 и Contour. Тесты построены на библиотеке Boost.Test.
Своевременное написание тестов позволяет быстро найти и исправить множество ошибок, способствует повышению производительности труда и качества кода.
Ещё
Добавлены FusedFunctor.h и FusedFunctorTuple.h, но о них я намерен написать в следующий раз (планируется внести некоторые изменения).
evetro 