2D-Linq и оптимизация цифровых фильтров - 3.5
От: Sinclair Россия https://github.com/evilguest/
Дата: 10.08.18 03:18
Оценка: 104 (3) +1 :)
Ну, вот и пятница.
It's been a while, коллеги, it's been a while.

В прошлый раз у нас развернулась жаркая дискуссия, в которой было сформулировано несколько ценных идей.
К сожалению, заявленных высот
Автор: Sinclair
Дата: 29.06.18
достичь пока не удалось, но "в нашем проекте достигнут важный майлстоун: нам удалось собрать его без ошибок компиляции!"
Поэтому эта часть имеет номер не 4, а 3.5.
Нужно было решить вопрос с "нечестностью", поднятый некоторыми коллегами в прошлый раз.
Так что код теперь — на гитхабе: https://github.com/evilguest/linq2d
Любой желающий может его собрать и запустить у себя.
А заодно и попробовать свои силы в конкурсе красоты кода.

Для того, чтобы это сделать, нужно
  1. Добавить свой класс-фильтр в проект FilterTests. Он должен реализовывать либо IArrayFilter<int>, либо IWrapperFilter<int>. Можно отнаследоваться от ArrayFilterBase, тогда в свойстве Data будет доступен массив, заготовленный для фильтрации.
  2. Добавить этот тип в список параметров для FilterType
И, собственно, всё.
На самом деле, достаточно реализовать интерфейс IFilter<int> и в методе Initialize подготовить какую угодно структуру данных (если не устраивают ни встроенные массивы, ни интерфейс IArray).
Методы C4 и С8 ищутся по имени.
Главное, чтобы тип возвращаемого результата реализовывал IStructuralEquatable и умел поэлементно сравниваться с IArray2d<int> — см. ArrayWrapper<T>, и, в частности, static private bool Equals(IArray2d<T> left, IArray2d<T> right, IEqualityComparer comparer)

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

Ну, а дальше мы будем сравнивать красоту и производительность
В текущей версии теста сравниваются не все фильтры, которые я реализовал в процессе творческих поисков, а только наиболее характерные:
  1. BasicArrayFilter — самый простой и очевидный код, двойной цикл по входному массиву. Никаких косвенных вызовов, но проверки выхода за диапазоны пять раз за итерацию. Выступает в качестве критерия корректности.
  2. UnsafeFilter — код, написанный упоротым шарпистом, который любит ансейф. Ни косвенных вызовов, ни проверок границ. Там, в принципе, есть ещё способ выжать пару тактов во внутреннем цикле, но уже с трудом
  3. BestLinkFilter — это "мой кандидат", который претендует на победу:
    using System.Linq.Processing2d;
    using System.Linq.Processing2d.FastUnsafe;
    
    namespace FilterTests
    {
        public class BestLinqFilter : ArrayFilterBase, IArrayFilter<int>
        {
            public int[,] C4() =>
                    from d in Data.AsRelative(Bounds.Skip) select (d[-1, 0] + d[0, -1] + d[0, 1] + d[1, 0]) / 4;
    
            public int[,] C8() =>
                    from d in Data.AsRelative(Bounds.Skip)
                    select (d[-1, -1] + d[-1, 0] + d[-1, 1]
                          + d[ 0, -1]       +      d[ 0, 1]
                          + d[ 1, -1] + d[ 1, 0] + d[ 1, 1]) / 8;
        }
    }

    Критика того, что фильтр неявно принимает решение скипнуть границу, в которой ядро вычислить не удастся, принята — теперь мы явно задаём желаемую семантику в .AsRelative(). Никакие другие варианты, понятное дело, пока не работают, оставлены как задел на будущее.
  4. Фильтры DeferredLinqFilter и FastLinqFilter в бенчмарк не входят. Они иллюстрируют концепцию:
    • Во-первых, разные реализации Linq разведены в библиотеке Linq2d по разным неймспейсам. Таким образом, меняя using, можно легко переключаться между "экспериментальной" и "стабильной" версиями в коде клиента
    • Во-вторых, для отложенных вычислений приходится принудительно вызывать на результате ToArray(), иначе этот бенчмарк выигрывает с большим отрывом . Если вы будете строить аналогичную конструкцию, то не забудьте обеспечить готовность результата внутри бенчмарка, т.к. валидация с проверкой каждого значения в измерения производительности не входит.
Ну, и на десерт: сравнение, собственно, производительности у трёх упомянутых фильтров. BasicArrayFilter, конечно же, брать за ориентир не стоит — как было эмоционально отмечено в предыдущей дискуссии, "такое никто не пишет".
Поэтому за 100% мы берём UnsafeFilter. Для массива 1000*1000, на моём Lenovo T460 получается вот такой результат:

Filter Class C4 C8
BestLinqFilter 69.18% 70.44%
UnsafeFilter 100.00% 100.00%
BasicArrayFilter 293.76% 378.16%
То есть "красивый" фильтр отрабатывает примерно на треть быстрее, чем "некрасивый, но быстрый". И это ещё не предел

Обязательно отпишитесь, если скачанный проект не заработает — это мой первый опыт с гитхабом, запросто мог напороть. Очень интересно посмотреть на статистику на более другом железе.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Отредактировано 10.08.2018 3:23 Sinclair . Предыдущая версия . Еще …
Отредактировано 10.08.2018 3:20 Sinclair . Предыдущая версия .
linq2d ямогуещёинетакупороться
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.