2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 03.08.20 06:08
Оценка: 141 (9)
Обещанного три года ждут, а прошло
Автор: Sinclair
Дата: 10.08.18
всего лишь два.
Столкнувшись с некоторыми трудностями, я проект подзабросил, и почти не вспоминал о нём до этой весны.
В самоизоляции я решил-таки откопать стюардессу, и продолжить с того места, где остановился в прошлый раз
Автор: Sinclair
Дата: 29.06.18
.

Итак, что у нас с тех пор?
Предыдущие жалкие, ничтожные попытки манипулировать IL-кодом были безжалостно выброшены.
С нуля был начат проект linq2d на основе expression trees, и доведён до некоторой минимальной работоспособности.
Подробности — https://github.com/evilguest/linq2d/blob/master/README.md
Функционально, по сравнению с прошлым разом, добавилось:
1. Рекурсивные обращения
2. Поддержка одновременного вычисления нескольких результатов
3. Кэширование трансформаций, чтобы для повторных вычислений не заниматься трансляцией linq-выражений

С этими расширениями можно наконец-то замутить адаптивную бинаризацию по Савола
Автор: Pavel Dvorkin
Дата: 29.06.18
:
public static byte[,] SauvolaBinarize(byte[,] grayScale, int WHalf, double K)
{
        var integrate = 
            from g in grayScale
            from ri in Result.SubstBy(0)    // сумма элементов - int32
            from rq in Result.SubstBy(0L)    // сумма квадратов - int64. Можно обойтись и int32, если площадь окна просмотра не более 2^16, но так честнее
            select ValueTuple.Create(
                ri[-1, 0] + ri[0, -1] - ri[-1, -1] + g,
                rq[-1, 0] + rq[0, -1] - rq[-1, -1] + g * g);
        var (p, sq) = integrate.ToArrays();    // вычисляем оба интеграла сразу

    var detect = 
            from g in grayScale
            from i in p.With(OutOfBoundsStrategy.Integral(0))    // специальная стратегия подстановки для значений за пределами массива - 0 для слева-сверху,
            from q in sq.With(OutOfBoundsStrategy.Integral(0L)) // ближайший сосед для справа-снизу.
            let tl = i.Offset(-WHalf - 1, -WHalf - 1)        // самая громоздкая часть: вычисляем эффективное окно просмотра, смещая текущую точку на +-Whalf
            let tr = i.Offset(-WHalf - 1, WHalf)        // нам нужны 8 точек, т.к. мы используем оба предынтегрированных массива
            let bl = i.Offset(WHalf, -WHalf - 1)
            let br = i.Offset(WHalf, WHalf)
            let tlq = q.Offset(-WHalf - 1, -WHalf - 1)
            let trq = q.Offset(-WHalf - 1, WHalf)
            let blq = q.Offset(WHalf, -WHalf - 1)
            let brq = q.Offset(WHalf, WHalf)
            let area = (br.X - tl.X) * (br.Y - tl.Y)        // площадь окна разная, в зависимости от того, куда попала точка; все поправки в X и Y учитываются OutOfBoundsStrategy.Integral
            let diff = br.Value + tl.Value - tr.Value - bl.Value
            let sqdiff = brq.Value + tlq.Value - trq.Value - blq.Value
            let mean = (double)diff / area            // вообще, здесь можно и не приводить к double. Но это мешает векторизации, т.к. целочисленный div есть только в AVX-512. 
            let std = Math.Sqrt((sqdiff - diff * mean) / (area - 1)) // А вот double делятся уже в avx2.

            let threshold = mean * (1 + K * ((std / 128) - 1))

            select g > threshold ? byte.MaxValue : byte.MinValue;
}

Все приседания вокруг границ массива спрятаны в SubstBy и OutOfBoundsStrategy.Integral.
Два прохода по исходному массиву для интегрирования заменены на один — так быстрее.
В бенчмарке этот код разрезан на две части, чтобы проще было кэшировать.
В честных LinqSauvola*() эти методы вызываются один за другим.
В CachedLinqSauvola* вызываются заранее подготовленные Transform-делегаты.

Дополнительные затраты памяти — только на промежуточные массивы p и sq, как и в оригинальном С++ коде.
Нынешняя производительность на моём стареньком T460:
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.1.302
[Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
|                  Method | WHalf |   FileName |    Mean |    Error |   StdDev |  Median | Ratio | RatioSD |
|------------------------ |------ |----------- |--------:|---------:|---------:|--------:|------:|--------:|
|             SafeSauvola |     5 | p00743.bmp | 2.795 s | 0.0624 s | 0.1812 s | 2.744 s |  1.91 |    0.20 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp | 1.475 s | 0.0494 s | 0.1455 s | 1.410 s |  1.00 |    0.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 2.433 s | 0.0485 s | 0.0664 s | 2.439 s |  1.47 |    0.09 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 2.598 s | 0.1468 s | 0.4328 s | 2.607 s |  1.77 |    0.34 |
| CachedLinqSauvolaVector |     5 | p00743.bmp | 1.018 s | 0.0202 s | 0.0283 s | 1.014 s |  0.62 |    0.04 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp | 1.140 s | 0.0226 s | 0.0338 s | 1.139 s |  0.69 |    0.04 |

За baseline взят
  простой unsafe метод
    public static unsafe byte[,] UnsafeSauvola(byte[,] grayScale, int whalf)
        {
            int height = grayScale.Height();
            int width = grayScale.Width();
            var p = new int[height, width];
            var sq = new long[height, width];
            byte[,] result = new byte[height, width];

            fixed (byte* gPtr = &grayScale[0, 0])
            fixed (int* pPtr = &p[0, 0])
            fixed (long* sqPtr = &sq[0, 0])
            fixed (byte* rPtr = &result[0, 0])
            {
                for (int i = 0; i < height; i++)
                    for (int j = 0; j < width; j++)
                    {
                        pPtr[i * width + j] = gPtr[i * width + j];
                        sqPtr[i * width + j] = gPtr[i * width + j] * gPtr[i * width + j];
                        if (i > 0)
                        {
                            pPtr[i * width + j] += pPtr[(i - 1) * width + j];
                            sqPtr[i * width + j] += sqPtr[(i - 1) * width + j];
                        }
                        if (j > 0)
                        {
                            pPtr[i * width + j] += pPtr[i * width + j - 1];
                            sqPtr[i * width + j] += sqPtr[i * width + j - 1];
                        }
                        if (i > 0 && j > 0)
                        {
                            pPtr[i * width + j] -= pPtr[(i - 1) * width + j - 1];
                            sqPtr[i * width + j] -= sqPtr[(i - 1) * width + j - 1];
                        }
                    }
                for (int i = 0; i < height; i++)
                    for (int j = 0; j < width; j++)
                    {
                        var xmin = Math.Max(0, i - whalf);
                        var ymin = Math.Max(0, j - whalf);
                        var xmax = Math.Min(height - 1, i + whalf);
                        var ymax = Math.Min(width - 1, j + whalf);

                        var area = (xmax - xmin + 1) * (ymax - ymin + 1);

                        var diff = pPtr[width * xmax + ymax];
                        var sqdiff = sqPtr[width * xmax + ymax];
                        if (xmin > 0)
                        {
                            diff -= -pPtr[width * (xmin - 1) + ymax];
                            sqdiff -= -sqPtr[width * (xmin - 1) + ymax];
                        }
                        if (ymin > 0)
                        {
                            diff -= pPtr[width * xmax + ymin - 1];
                            sqdiff -= sqPtr[width * xmax + ymin - 1];
                        }
                        if (xmin > 0 && ymin > 0)
                        {
                            diff += pPtr[width * (xmin - 1) + ymin - 1];
                            sqdiff += sqPtr[width * (xmin - 1) + ymin - 1];
                        }
                        var mean = (double)diff / area;
                        var std = Math.Sqrt((sqdiff - diff * mean) / (area - 1));

                        var threshold = mean * (1 + K * ((std / 128) - 1));

                        rPtr[i * width + j] = gPtr[i * width + j] > threshold ? byte.MaxValue : byte.MinValue;
                    }
                return result;
            }
        }

Идиоматический С#-код проигрывает ему почти в два (1.91) раза. Это — плата за контроль обращений к элементам массива.
Linq-код проигрывает в 1.4-1.7 раз. Но это — от небольшого количества повторов, так что стоимость рантайм-компиляции вносит существенный вклад.
А вот с кэшированием результат уже существенно лучше: "обычная" версия наигрывает 30% производительности за счёт более агрессивной оптимизации кода по сравнению с JIT.
Частичная AVX-векторизация выигрывает ещё 7%, итого "абстрактный" код выезжает за ~0.6 времени работы "конкретного".
Всё это — однопоточный код; прикрутить обратно параллелизацию руки пока не дошли. Но у неё основной недостаток — она бесполезна при массовом обслуживании, где важен throughput, а не response time.
С кодом на C++ пока не сравнивал, надо напилить внешнюю DLL и выполнить забег с ней.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 03.08.20 15:28
Оценка: 117 (1)
Здравствуйте, Sinclair, Вы писали:

Мой старичок показывает такие показометры, в целом повторяя наблюдения (кроме CachedLinqSauvolaScalar):

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.388 (2004/?/20H1)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.100-preview.6.20318.15
  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  DefaultJob : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT


|                  Method | WHalf |   FileName |       Mean |   Error |  StdDev | Ratio |
|------------------------ |------ |----------- |-----------:|--------:|--------:|------:|
|             SafeSauvola |     5 | p00743.bmp | 1,290.8 ms | 4.50 ms | 4.21 ms |  1.80 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   718.5 ms | 5.46 ms | 5.10 ms |  1.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,167.0 ms | 5.14 ms | 4.30 ms |  1.62 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,293.6 ms | 6.25 ms | 5.84 ms |  1.80 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   694.3 ms | 4.94 ms | 4.63 ms |  0.97 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   825.1 ms | 6.13 ms | 5.73 ms |  1.15 |


А вот, ещё .NET 5 preview:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.388 (2004/?/20H1)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.100-preview.6.20318.15
  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  Job-HMFQFC : .NET Core 5.0.0 (CoreCLR 5.0.20.30506, CoreFX 5.0.20.30506), X64 RyuJIT

Runtime=.NET Core 5.0  Toolchain=netcoreapp50

|                  Method | WHalf |   FileName |       Mean |   Error |  StdDev | Ratio | RatioSD |
|------------------------ |------ |----------- |-----------:|--------:|--------:|------:|--------:|
|             SafeSauvola |     5 | p00743.bmp | 1,242.5 ms | 5.74 ms | 4.79 ms |  1.84 |    0.01 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   674.4 ms | 5.80 ms | 5.43 ms |  1.00 |    0.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,107.7 ms | 8.42 ms | 7.46 ms |  1.64 |    0.02 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,209.5 ms | 6.75 ms | 5.64 ms |  1.79 |    0.01 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   625.2 ms | 5.65 ms | 5.01 ms |  0.93 |    0.01 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   778.4 ms | 5.66 ms | 5.02 ms |  1.15 |    0.00 |


Получается что UnsafeSauvolaScalar — по прежнему очень и очень хорош.
Re[2]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 03.08.20 15:44
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:
MA>Мой старичок показывает такие показометры, в целом повторяя наблюдения (кроме CachedLinqSauvolaScalar):
MA>Получается что UnsafeSauvolaScalar — по прежнему очень и очень хорош.
Спасибо за данные. Видно, что переход на 5.0 не даёт выигрыша по сравнению с Core 3.1, что более-менее предсказуемо. Разница — в пределах погрешности.
Интересно опять же, что если брать чистое время исполнения, то классический unsafe код исполняется у тебя сильно шустрее, чем у меня.
Относительные времена Vector/Scalar примерно совпадают; что означает, что используется тот же instruction set.
Пока что ещё есть куда крутить оптимизацию — например, фаза предынтегрирования пока что не векторизуется из-за накладок при доступе к r[0, -1].
Ещё там не очень оптимально сделан тернарный оператор; но я пока что даже в disassembly ему не смотрел — там нужно прямо очень приседать; обычные способы для динамического кода не работают.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 03.08.20 16:15
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Интересно опять же, что если брать чистое время исполнения, то классический unsafe код исполняется у тебя сильно шустрее, чем у меня.

S>Относительные времена Vector/Scalar примерно совпадают; что означает, что используется тот же instruction set.
S>Пока что ещё есть куда крутить оптимизацию — например, фаза предынтегрирования пока что не векторизуется из-за накладок при доступе к r[0, -1].
S>Ещё там не очень оптимально сделан тернарный оператор; но я пока что даже в disassembly ему не смотрел — там нужно прямо очень приседать; обычные способы для динамического кода не работают.

Да я тоже обратил внимание на разницу... но не знаю в чём дело. i7-6600U просто поскромнее, думаю вот и вся разница... Стало интересно, и вот взял ещё ноут с DDR4 памятью и соответственно другим процессором (на i7-4770 была DDR3 память, но в который раз убеждаюсь — это вообще без разницы ):

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.329 (2004/?/20H1)
Intel Core i5-7300HQ CPU 2.50GHz (Kaby Lake), 1 CPU, 4 logical and 4 physical cores
.NET Core SDK=3.1.301
  [Host]     : .NET Core 3.1.5 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.27001), X64 RyuJIT
  DefaultJob : .NET Core 3.1.5 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.27001), X64 RyuJIT


|                  Method | WHalf |   FileName |       Mean |    Error |   StdDev | Ratio | RatioSD |
|------------------------ |------ |----------- |-----------:|---------:|---------:|------:|--------:|
|             SafeSauvola |     5 | p00743.bmp | 1,369.5 ms | 26.42 ms | 25.94 ms |  1.89 |    0.03 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   727.7 ms | 13.48 ms | 11.26 ms |  1.00 |    0.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,283.9 ms |  8.68 ms |  8.12 ms |  1.77 |    0.02 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,284.4 ms |  8.86 ms |  7.86 ms |  1.76 |    0.03 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   681.5 ms |  9.41 ms |  7.86 ms |  0.94 |    0.02 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   789.0 ms |  8.12 ms |  6.78 ms |  1.08 |    0.02 |


По тесту видно, что кто-то его давненько не обновлял, но абсолютные цифры похожи на десктоп.
Re[4]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 04.08.20 02:45
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:

MA> По тесту видно, что кто-то его давненько не обновлял, но абсолютные цифры похожи на десктоп.

Кстати, странно, что CachedLinqSauvolaScalar проигрывает честной unsafe версии. Может, у меня там что-то отвалилось?..
Там же порождается вполне себе сопоставимый код.
В прошлый раз когда я на такое налетел, обнаружилась разница между JIT-ом динамического и статического кода.
Но её я заборол улучшением оптимизации. Попробуй прогнать тест с WHalf = 4, а?
И, если не затруднит, скинь сборку Linq2d.GetQuery, которая записывается в папочку Dynamic в выхлопе проекта.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 04.08.20 16:38
Оценка:
Здравствуйте, Sinclair, Вы писали:

MA>> По тесту видно, что кто-то его давненько не обновлял, но абсолютные цифры похожи на десктоп.

S>Кстати, странно, что CachedLinqSauvolaScalar проигрывает честной unsafe версии. Может, у меня там что-то отвалилось?..
S>Там же порождается вполне себе сопоставимый код.
S>В прошлый раз когда я на такое налетел, обнаружилась разница между JIT-ом динамического и статического кода.
S>Но её я заборол улучшением оптимизации. Попробуй прогнать тест с WHalf = 4, а?
S>И, если не затруднит, скинь сборку Linq2d.GetQuery, которая записывается в папочку Dynamic в выхлопе проекта.

Если ты говоришь, что там попрождается сопоставимый код — то на самом деле не совсем понятно откуда у тебя возникает 30-40% прироста...

Конечно, пожалуйста:

WHalf = 4

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.388 (2004/?/20H1)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.100-preview.6.20318.15
  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  DefaultJob : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT


|                  Method | WHalf |   FileName |       Mean |    Error |   StdDev | Ratio | RatioSD |
|------------------------ |------ |----------- |-----------:|---------:|---------:|------:|--------:|
|             SafeSauvola |     4 | p00743.bmp | 1,299.4 ms | 18.59 ms | 16.48 ms |  1.82 |    0.02 |
|     UnsafeSauvolaScalar |     4 | p00743.bmp |   714.8 ms |  4.33 ms |  4.05 ms |  1.00 |    0.00 |
|       LinqSauvolaVector |     4 | p00743.bmp | 1,017.6 ms | 11.79 ms |  9.20 ms |  1.42 |    0.01 |
|       LinqSauvolaScalar |     4 | p00743.bmp | 1,138.0 ms |  5.30 ms |  4.69 ms |  1.59 |    0.01 |
| CachedLinqSauvolaVector |     4 | p00743.bmp |   695.6 ms |  5.89 ms |  5.22 ms |  0.97 |    0.01 |
| CachedLinqSauvolaScalar |     4 | p00743.bmp |   828.5 ms |  7.10 ms |  6.64 ms |  1.16 |    0.01 |


---

Вернул WHalf = 5, всё пересобрал. Запустил linq2d.benchmarks --keepFiles, и из него уже выковырял файлы.

  результаты тоже нормальные
Кстати, смешно, но он мне несколько раз подряд для CachedLinqSauvolaVector показывал результат хуже чем у CachedLinqSauvolaScalar, где-то 850ms, хотя при warmup — 700ms, и это произошло, как только я сказал ему keepFiles. Уж не знаю, что за магия случилось. Потом всё очистил, пересобрал и стало всё нормально.

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.388 (2004/?/20H1)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.100-preview.6.20318.15
  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  DefaultJob : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT


|                  Method | WHalf |   FileName |       Mean |   Error |  StdDev | Ratio |
|------------------------ |------ |----------- |-----------:|--------:|--------:|------:|
|             SafeSauvola |     5 | p00743.bmp | 1,286.4 ms | 8.26 ms | 7.72 ms |  1.80 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   715.6 ms | 4.55 ms | 4.26 ms |  1.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,153.0 ms | 5.63 ms | 5.26 ms |  1.61 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,282.5 ms | 4.84 ms | 4.53 ms |  1.79 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   690.4 ms | 6.19 ms | 5.49 ms |  0.97 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   824.2 ms | 6.39 ms | 5.66 ms |  1.15 |


И вот от этого запуска содержимое каталога Dynamic.

UPD: Ну и там только Linq2d.GetDetect.dll и Linq2d.GetIntegral.dll — никакого Linq2d.GetQuery там не лежит... а внутри GetDetect-а Transform с около 600 локалами!

ADD: Ну и разницы во времени между WHalf 4 и 5 я не вижу. Я не знаю должна ли она быть.
Отредактировано 04.08.2020 17:12 Mystic Artifact . Предыдущая версия . Еще …
Отредактировано 04.08.2020 17:09 Mystic Artifact . Предыдущая версия .
Отредактировано 04.08.2020 17:09 Mystic Artifact . Предыдущая версия .
Отредактировано 04.08.2020 17:06 Mystic Artifact . Предыдущая версия .
Re: 2D-Linq и оптимизация цифровых фильтров - 4
От: VladCore  
Дата: 04.08.20 17:56
Оценка: 78 (1)
Здравствуйте, Sinclair, Вы писали:

Прикольно

1.
А какой AVX юзается? В старых облачных датацентрах все еще есть SandyBridge. Там целочисленного AVX нет. Только плавающий.

2. Если запустить все бенчмарки (cd Linq2d.Benchmarks && dotnet run -c Release --filter '*') то они вешаются. вот концовка в консоли:

RPI 4 64 бит, AVX есть, но называется он NEON Я не спец по NEON-инструкциям но они и целые и плавающие векторы поддерживают.
// **************************
// Benchmark: SauvolaBenchmark.SafeSauvola: DefaultJob [WHalf=5, FileName=p00743.bmp]
// *** Execute ***
// Launch: 1 / 1
// Execute: dotnet "384c5e76-727b-4c44-90b0-8f10ff201d74.dll" --benchmarkName "Linq2d.Benchmarks.SauvolaBenchmark.SafeSauvola(WHalf: 5, FileName: "p00743.bmp")" --job "Default" --benchmarkId 9 in /root/build/linq2d-src/linq2d/Linq2d.Benchmarks/bin/Release/netcoreapp3.1/384c5e76-727b-4c44-90b0-8f10ff201d74/bin/Release/netcoreapp3.1
// BeforeAnythingElse

// Benchmark Process Environment Information:
// Runtime=.NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), Arm64 RyuJIT
// GC=Concurrent Workstation
// Job: DefaultJob

Working at the directory '/root/build/linq2d-src/linq2d/Linq2d.Benchmarks/bin/Release/netcoreapp3.1/384c5e76-727b-4c44-90b0-8f10ff201d74/bin/Release/netcoreapp3.1'
Loading file p00743.bmp...
Found the bitmap of 5184*6433
Loaded file p00743.bmp.
Sauvola Edge Detect vectorization failed due to the expression
source2[var_$0, var_$1]
  :Failed to find a suitable load operation for the System.Int32 vector of size 4


Ivy Bridge 64 бит
// **************************
// Benchmark: SauvolaBenchmark.SafeSauvola: DefaultJob [WHalf=5, FileName=p00743.bmp]
// *** Execute ***
// Launch: 1 / 1
// Execute: dotnet "2278c1b6-9536-4523-9208-84d5654de6da.dll" --benchmarkName "Linq2d.Benchmarks.SauvolaBenchmark.SafeSauvola(WHalf: 5, FileName: "p00743.bmp")" --job "Default" --benchmarkId 9 in U:\Lab\linq2d\Linq2d.Benchmarks\bin\Release\netcoreapp3.1\2278c1b6-9536-4523-9208-84d5654de6da\bin\Release\netcoreapp3.1
// BeforeAnythingElse

// Benchmark Process Environment Information:
// Runtime=.NET Core 3.1.3 (CoreCLR 4.700.20.11803, CoreFX 4.700.20.12001), X64 RyuJIT
// GC=Concurrent Workstation
// Job: DefaultJob

Working at the directory 'U:\Lab\linq2d\Linq2d.Benchmarks\bin\Release\netcoreapp3.1\2278c1b6-9536-4523-9208-84d5654de6da\bin\Release\netcoreapp3.1'
Loading file p00743.bmp...
Found the bitmap of 5184*6433
Loaded file p00743.bmp.
Sauvola Edge Detect vectorization failed due to the expression
source3[var_$0, var_$1] + source3[var_$2, var_$3]
  :Failed to find a vector Add operation over System.Runtime.Intrinsics.Vector256`1[System.Int64] and System.Runtime.Intrinsics.Vector256`1[System.Int64]


я не смотрел исходники но возможно требуется AVX2 (целочисленный)? но тогда непонятно почему вешается а не падает с ошибкой?
Отредактировано 04.08.2020 18:09 VladCore . Предыдущая версия . Еще …
Отредактировано 04.08.2020 17:58 VladCore . Предыдущая версия .
Re[2]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.08.20 01:56
Оценка: 7 (1)
Здравствуйте, VladCore, Вы писали:

VC>1.

VC>А какой AVX юзается? В старых облачных датацентрах все еще есть SandyBridge. Там целочисленного AVX нет. Только плавающий.
Используется линейка x86 AVX — то есть начиная с SSE и до AVX2. Оппортунистически. То есть смотрим, что есть — то и используем. Если ничего не нашли, то компилируем скалярный код.
Чем сложнее выражение, тем меньше шансов успешно векторизоваться. Савола в этом смысле очень чувствителен — там смешаны операнды четырёх типов трёх разных размеров, а в операциях есть и деление, и корень.

VC>Ivy Bridge 64 бит

VC>
VC>// **************************
VC>// Benchmark: SauvolaBenchmark.SafeSauvola: DefaultJob [WHalf=5, FileName=p00743.bmp]
VC>// *** Execute ***
VC>// Launch: 1 / 1
VC>// Execute: dotnet "2278c1b6-9536-4523-9208-84d5654de6da.dll" --benchmarkName "Linq2d.Benchmarks.SauvolaBenchmark.SafeSauvola(WHalf: 5, FileName: "p00743.bmp")" --job "Default" --benchmarkId 9 in U:\Lab\linq2d\Linq2d.Benchmarks\bin\Release\netcoreapp3.1\2278c1b6-9536-4523-9208-84d5654de6da\bin\Release\netcoreapp3.1
VC>// BeforeAnythingElse

VC>// Benchmark Process Environment Information:
VC>// Runtime=.NET Core 3.1.3 (CoreCLR 4.700.20.11803, CoreFX 4.700.20.12001), X64 RyuJIT
VC>// GC=Concurrent Workstation
VC>// Job: DefaultJob

VC>Working at the directory 'U:\Lab\linq2d\Linq2d.Benchmarks\bin\Release\netcoreapp3.1\2278c1b6-9536-4523-9208-84d5654de6da\bin\Release\netcoreapp3.1'
VC>Loading file p00743.bmp...
VC>Found the bitmap of 5184*6433
VC>Loaded file p00743.bmp.
VC>Sauvola Edge Detect vectorization failed due to the expression
VC>source3[var_$0, var_$1] + source3[var_$2, var_$3]
VC>  :Failed to find a vector Add operation over System.Runtime.Intrinsics.Vector256`1[System.Int64] and System.Runtime.Intrinsics.Vector256`1[System.Int64]
VC>


VC>я не смотрел исходники но возможно требуется AVX2 (целочисленный)? но тогда непонятно почему вешается а не падает с ошибкой?

Там для отладки воткнут Console.Readline — если его убрать, то просто будет падать. Ну, и падение тоже искусственное — сам бенчмарк проверяет, удалось ли векторизовать; если не удалось, то пишет причину.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[6]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.08.20 03:23
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:


MA> Если ты говоришь, что там попрождается сопоставимый код — то на самом деле не совсем понятно откуда у тебя возникает 30-40% прироста...

Магия
MA> Конечно, пожалуйста:
MA>Кстати, смешно, но он мне несколько раз подряд для CachedLinqSauvolaVector показывал результат хуже чем у CachedLinqSauvolaScalar, где-то 850ms, хотя при warmup — 700ms, и это произошло, как только я сказал ему keepFiles. Уж не знаю, что за магия случилось. Потом всё очистил, пересобрал и стало всё нормально.
Фантастика какая-то. Надо продолжать ковырять.

MA>
MA>BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.388 (2004/?/20H1)
MA>Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
MA>.NET Core SDK=5.0.100-preview.6.20318.15
MA>  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
MA>  DefaultJob : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT

MA>|                  Method | WHalf |   FileName |       Mean |   Error |  StdDev | Ratio |
MA>|------------------------ |------ |----------- |-----------:|--------:|--------:|------:|
MA>|             SafeSauvola |     5 | p00743.bmp | 1,286.4 ms | 8.26 ms | 7.72 ms |  1.80 |
MA>|     UnsafeSauvolaScalar |     5 | p00743.bmp |   715.6 ms | 4.55 ms | 4.26 ms |  1.00 |
MA>|       LinqSauvolaVector |     5 | p00743.bmp | 1,153.0 ms | 5.63 ms | 5.26 ms |  1.61 |
MA>|       LinqSauvolaScalar |     5 | p00743.bmp | 1,282.5 ms | 4.84 ms | 4.53 ms |  1.79 |
MA>| CachedLinqSauvolaVector |     5 | p00743.bmp |   690.4 ms | 6.19 ms | 5.49 ms |  0.97 |
MA>| CachedLinqSauvolaScalar |     5 | p00743.bmp |   824.2 ms | 6.39 ms | 5.66 ms |  1.15 |
MA>


MA>UPD: Ну и там только Linq2d.GetDetect.dll и Linq2d.GetIntegral.dll — никакого Linq2d.GetQuery там не лежит... а внутри GetDetect-а Transform с около 600 локалами!

А, точно, это у меня мусор от пред-предыдущего запуска остался. Он пытается придумать имя dll на основе имени метода, из которого вызывается построение выражения.
Да, 600 локалов — норм. Там же выполняется специализация для краевых элементов, чтобы избежать ветвлений в основном теле цикла.
И в каждой специализации отдельно выполняется common subexpression elimination — отсюда и локалы. У них короткое время жизни, поэтому регистров должно хватать.
Можно прикрутить повторное использование, но я не ожидаю от него улучшений для порождаемого кода: скорее наоборот, будет больше нагрузка на JIT.
MA>ADD: Ну и разницы во времени между WHalf 4 и 5 я не вижу. Я не знаю должна ли она быть.
Вообще — не должна. Но пока я не прикрутил CSE, при переходе от 4 к 5 ломался оптимизатор JIT. Влиял, судя по всему, размер метода.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[7]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 05.08.20 04:20
Оценка:
Здравствуйте, Sinclair, Вы писали:

MA>> Если ты говоришь, что там попрождается сопоставимый код — то на самом деле не совсем понятно откуда у тебя возникает 30-40% прироста...

S>Магия
Вот я и не пойму: то ли ты нашел как накормить свой процессор правильно и поэтому ты победил unsafe вариант (и следовательно JIT не учитывает какие-то особенности твоего процессора при генерации кода), то ли моему процессору пофигу на эти нюансы... (это я вообще без относительно сути происходящего). Тут бы побольше статистики.

S>Да, 600 локалов — норм. Там же выполняется специализация для краевых элементов, чтобы избежать ветвлений в основном теле цикла.

S>И в каждой специализации отдельно выполняется common subexpression elimination — отсюда и локалы. У них короткое время жизни, поэтому регистров должно хватать.
Да я в целом то так и понял. После, JIT и сам должен схлопнуть лишние локалы. Единственный вопрос, нет ли у него каких-то внутренних ограничений, которые могут повлиять на процесс. (Ну вроде как и не должно...)

S>Можно прикрутить повторное использование, но я не ожидаю от него улучшений для порождаемого кода: скорее наоборот, будет больше нагрузка на JIT.

Согласен.

S>Вообще — не должна. Но пока я не прикрутил CSE, при переходе от 4 к 5 ломался оптимизатор JIT. Влиял, судя по всему, размер метода.

Я думаю влияние можно немного уменьшить, если генерируемому методу поставить флаг aggressive optimization. На сейчас (беглый взгляд по coreclr) данный хинт исключит применение всяких спекуляций (tier0, quick jit) и даже пока исключает его из ready-to-run сборок. Но, судя по всему он никак не улучшает качество самого JIT (по крайней мере пока). В net5 должен появиться "OSR" (on-stack code replacement) который должен динамически заменять тела методов посреди дороги (в частности циклов) и интерпретатор IL у них почти есть. Как будет работать эта вся кухня, трудно сказать, ясно только, что в таком бенчмарке этого будет не разглядеть, но с точки зрения традиционного подхода — "долго запрягаем, кешируем и потом быстро едем" — данный хинт определенно имеет смысл.
Re[7]: 2D-Linq и оптимизация цифровых фильтров - 4
От: rameel https://github.com/rsdn/CodeJam
Дата: 05.08.20 06:18
Оценка: 105 (2)
Здравствуйте, Sinclair, Вы писали:

S>Да, 600 локалов — норм. Там же выполняется специализация для краевых элементов, чтобы избежать ветвлений в основном теле цикла.

S>И в каждой специализации отдельно выполняется common subexpression elimination — отсюда и локалы. У них короткое время жизни, поэтому регистров должно хватать.

У джита ограничение на 512 локалов

https://github.com/dotnet/runtime/issues/13423#issuecomment-531854959

@jkotas

The problem is limit on tracked locals in the JIT.
The JIT is able to do efficient register allocation for the 512 most frequently used local variables only. Above this limit, the local variables are spilled to stack.
There are number of layers of aggressive inlined methods in the repro. The aggressive inlining creates hundreds of locals in this case (e.g. inlined arguments tend to create a local). Once the 512 limit is hit, the code quality degrades.

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re[8]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 05.08.20 06:32
Оценка:
Здравствуйте, rameel, Вы писали:

Просто обращу внимание, что там же так же есть ссылка на [Proposal][Crossgen] Relax throughput impacting JIT parameters for crossgen в котором есть ссылка на ченджсет с конфигурированием этого лимита. Я постараюсь не забыть и смогу попробовать повторить тест с увеличенным лимитом. Хоть будет видно, насколько это сильно поменяет ситуацию.
Re[9]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.08.20 09:00
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:
MA>Просто обращу внимание, что там же так же есть ссылка на [Proposal][Crossgen] Relax throughput impacting JIT parameters for crossgen в котором есть ссылка на ченджсет с конфигурированием этого лимита. Я постараюсь не забыть и смогу попробовать повторить тест с увеличенным лимитом. Хоть будет видно, насколько это сильно поменяет ситуацию.
Попробуй новую версию — я сократил количество временных переменных путём переиспользования.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[10]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 05.08.20 11:01
Оценка: 114 (1)
Здравствуйте, Sinclair, Вы писали:

MA>>Просто обращу внимание, что там же так же есть ссылка на [Proposal][Crossgen] Relax throughput impacting JIT parameters for crossgen в котором есть ссылка на ченджсет с конфигурированием этого лимита. Я постараюсь не забыть и смогу попробовать повторить тест с увеличенным лимитом. Хоть будет видно, насколько это сильно поменяет ситуацию.

S>Попробуй новую версию — я сократил количество временных переменных путём переиспользования.
Попробовал. 20 локалов вместо 600 это безусловно прогресс.

Тесты:
Pooling of CSE vars

|                  Method | WHalf |   FileName |       Mean |   Error |  StdDev | Ratio |
|------------------------ |------ |----------- |-----------:|--------:|--------:|------:|
|             SafeSauvola |     5 | p00743.bmp | 1,285.3 ms | 8.81 ms | 8.24 ms |  1.80 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   714.5 ms | 4.02 ms | 3.76 ms |  1.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,153.9 ms | 7.31 ms | 6.48 ms |  1.62 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,281.3 ms | 5.12 ms | 4.53 ms |  1.79 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   687.0 ms | 5.03 ms | 4.71 ms |  0.96 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   815.4 ms | 5.02 ms | 4.70 ms |  1.14 |


BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.388 (2004/?/20H1)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.100-preview.6.20318.15
  [Host]     : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
  DefaultJob : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT


|                  Method | WHalf |   FileName |       Mean |   Error |  StdDev | Ratio |
|------------------------ |------ |----------- |-----------:|--------:|--------:|------:|
|             SafeSauvola |     5 | p00743.bmp | 1,280.9 ms | 8.19 ms | 7.66 ms |  1.79 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   714.7 ms | 4.36 ms | 4.08 ms |  1.00 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,153.1 ms | 5.11 ms | 4.78 ms |  1.61 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,277.9 ms | 6.96 ms | 6.51 ms |  1.79 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   693.5 ms | 5.69 ms | 5.04 ms |  0.97 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   815.9 ms | 4.73 ms | 4.43 ms |  1.14 |


В принципе результаты полностью повторяют предыдущие...

Поковыряв JIT, я обнаружил, что число локальный переменных для GetDetect:Transform, нужно фактически вдвое больше чем тот, что был указан в IL... Их число происходит из количества стэковых операций, и не уверен что связано с локалами, так что лимит который будет работать это... скорее 1200. С лимитом в 2048 вместо 48Kb кода, получается 38Kb, а так же требуется практически в два раза меньше места на стэке. Время исполнения безусловно улучшается тоже, но ни о каких 30%-40% речи там нет. Таким образом что первая, что вторая версия обламывается с сообщением "Stopped promoting struct fields, due to too many locals.", и только JIT с умеличенным лимитом не обламывается. Но даже если он не обламывается — судя по всему это тот случай где ты много не теряешь (там остается именно каких-то 4 структуры, 1x ValueTuple`2 и 3x Vector32`1). Хрен его знает. Безусловно, более качественная компиляция помогает. Но размер кода с оптимизированными locals так же уменьшается до 43Кб, что как бы всё равно лучше.

lclMAX_TRACKED = 512

|                  Method | WHalf |   FileName |     Mean |   Error |  StdDev | Ratio |
|------------------------ |------ |----------- |---------:|--------:|--------:|------:|
|     UnsafeSauvolaScalar |     5 | p00743.bmp | 671.6 ms | 4.69 ms | 4.38 ms |  1.00 |
| CachedLinqSauvolaVector |     5 | p00743.bmp | 638.0 ms | 7.64 ms | 7.15 ms |  0.95 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp | 773.9 ms | 4.66 ms | 4.36 ms |  1.15 |


lclMAX_TRACKED = 2048

|                  Method | WHalf |   FileName |     Mean |   Error |  StdDev | Ratio |
|------------------------ |------ |----------- |---------:|--------:|--------:|------:|
|     UnsafeSauvolaScalar |     5 | p00743.bmp | 673.9 ms | 5.37 ms | 4.76 ms |  1.00 |
| CachedLinqSauvolaVector |     5 | p00743.bmp | 610.2 ms | 0.77 ms | 0.72 ms |  0.91 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp | 732.3 ms | 4.65 ms | 4.35 ms |  1.09 |


В общем как-то много мороки, а профита не виднос с ковыряниями вокруг JIT. Надоел он что-то. Там выхлоп его данных в 100Мб на этот метод. Не хочу больше читать. Ничего не понятно всё равно.


Вот альтернативный замер для подумать:

Run 1:

|                  Method | WHalf |   FileName |       Mean |    Error |   StdDev | Ratio | RatioSD | BranchInstructions/Op | BranchMispredictions/Op |
|------------------------ |------ |----------- |-----------:|---------:|---------:|------:|--------:|----------------------:|------------------------:|
|             SafeSauvola |     5 | p00743.bmp | 1,256.5 ms |  5.32 ms |  4.44 ms |  1.82 |    0.01 |           783,368,081 |               3,552,007 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   689.6 ms |  3.19 ms |  2.98 ms |  1.00 |    0.00 |           314,035,883 |                 970,411 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,276.0 ms |  6.58 ms |  6.15 ms |  1.85 |    0.01 |           533,759,280 |               5,058,339 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,267.0 ms |  6.60 ms |  5.51 ms |  1.84 |    0.01 |           400,418,238 |               5,938,255 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   677.1 ms |  5.66 ms |  5.30 ms |  0.98 |    0.01 |           214,382,434 |                 801,792 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   815.8 ms | 16.20 ms | 15.91 ms |  1.18 |    0.02 |            97,124,131 |               1,867,112 |

Run 2:
|                  Method | WHalf |   FileName |       Mean |    Error |   StdDev | Ratio | RatioSD | BranchInstructions/Op | BranchMispredictions/Op |
|------------------------ |------ |----------- |-----------:|---------:|---------:|------:|--------:|----------------------:|------------------------:|
|             SafeSauvola |     5 | p00743.bmp | 1,256.7 ms |  2.48 ms |  2.32 ms |  1.83 |    0.01 |           803,031,495 |               3,632,242 |
|     UnsafeSauvolaScalar |     5 | p00743.bmp |   685.3 ms |  3.28 ms |  3.07 ms |  1.00 |    0.00 |           305,128,752 |                 916,065 |
|       LinqSauvolaVector |     5 | p00743.bmp | 1,115.8 ms |  4.97 ms |  4.41 ms |  1.63 |    0.01 |           561,164,990 |               5,154,875 |
|       LinqSauvolaScalar |     5 | p00743.bmp | 1,241.6 ms |  3.64 ms |  3.41 ms |  1.81 |    0.01 |           425,470,320 |               6,090,332 |
| CachedLinqSauvolaVector |     5 | p00743.bmp |   671.9 ms | 12.92 ms | 13.27 ms |  0.98 |    0.02 |           205,053,288 |                 729,199 |
| CachedLinqSauvolaScalar |     5 | p00743.bmp |   785.7 ms |  3.74 ms |  3.50 ms |  1.15 |    0.00 |            99,804,388 |               1,917,611 |
Отредактировано 05.08.2020 11:15 Mystic Artifact . Предыдущая версия .
Re[11]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.08.20 12:09
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:

MA>Поковыряв JIT, я обнаружил, что число локальный переменных для GetDetect:Transform, нужно фактически вдвое больше чем тот, что был указан в IL... Их число происходит из количества стэковых операций, и не уверен что связано с локалами, так что лимит который будет работать это... скорее 1200. С лимитом в 2048 вместо 48Kb кода, получается 38Kb, а так же требуется практически в два раза меньше места на стэке. Время исполнения безусловно улучшается тоже, но ни о каких 30%-40% речи там нет. Таким образом что первая, что вторая версия обламывается с сообщением "Stopped promoting struct fields, due to too many locals.", и только JIT с умеличенным лимитом не обламывается. Но даже если он не обламывается — судя по всему это тот случай где ты много не теряешь (там остается именно каких-то 4 структуры, 1x ValueTuple`2 и 3x Vector32`1). Хрен его знает. Безусловно, более качественная компиляция помогает. Но размер кода с оптимизированными locals так же уменьшается до 43Кб, что как бы всё равно лучше.

Я, если честно, не понимаю, откуда он (дотнет) берёт такие глубины стека. Там же вполне себе прямолинейный код, два вложенных цикла. Ну, выражение там есть. Откуда там эти тысячи-то? Едва ли 20 maxstack должен быть.

MA>
MA>lclMAX_TRACKED = 512

MA>|                  Method | WHalf |   FileName |     Mean |   Error |  StdDev | Ratio |
MA>|------------------------ |------ |----------- |---------:|--------:|--------:|------:|
MA>|     UnsafeSauvolaScalar |     5 | p00743.bmp | 671.6 ms | 4.69 ms | 4.38 ms |  1.00 |
MA>| CachedLinqSauvolaVector |     5 | p00743.bmp | 638.0 ms | 7.64 ms | 7.15 ms |  0.95 |
MA>| CachedLinqSauvolaScalar |     5 | p00743.bmp | 773.9 ms | 4.66 ms | 4.36 ms |  1.15 |


MA>lclMAX_TRACKED = 2048

MA>|                  Method | WHalf |   FileName |     Mean |   Error |  StdDev | Ratio |
MA>|------------------------ |------ |----------- |---------:|--------:|--------:|------:|
MA>|     UnsafeSauvolaScalar |     5 | p00743.bmp | 673.9 ms | 5.37 ms | 4.76 ms |  1.00 |
MA>| CachedLinqSauvolaVector |     5 | p00743.bmp | 610.2 ms | 0.77 ms | 0.72 ms |  0.91 |
MA>| CachedLinqSauvolaScalar |     5 | p00743.bmp | 732.3 ms | 4.65 ms | 4.35 ms |  1.09 |
MA>


MA> В общем как-то много мороки, а профита не виднос с ковыряниями вокруг JIT. Надоел он что-то. Там выхлоп его данных в 100Мб на этот метод. Не хочу больше читать. Ничего не понятно всё равно.



MA> Вот альтернативный замер для подумать:


MA>
MA>Run 1:

MA>|                  Method | WHalf |   FileName |       Mean |    Error |   StdDev | Ratio | RatioSD | BranchInstructions/Op | BranchMispredictions/Op |
MA>|------------------------ |------ |----------- |-----------:|---------:|---------:|------:|--------:|----------------------:|------------------------:|
MA>|             SafeSauvola |     5 | p00743.bmp | 1,256.5 ms |  5.32 ms |  4.44 ms |  1.82 |    0.01 |           783,368,081 |               3,552,007 |
MA>|     UnsafeSauvolaScalar |     5 | p00743.bmp |   689.6 ms |  3.19 ms |  2.98 ms |  1.00 |    0.00 |           314,035,883 |                 970,411 |
MA>|       LinqSauvolaVector |     5 | p00743.bmp | 1,276.0 ms |  6.58 ms |  6.15 ms |  1.85 |    0.01 |           533,759,280 |               5,058,339 |
MA>|       LinqSauvolaScalar |     5 | p00743.bmp | 1,267.0 ms |  6.60 ms |  5.51 ms |  1.84 |    0.01 |           400,418,238 |               5,938,255 |
MA>| CachedLinqSauvolaVector |     5 | p00743.bmp |   677.1 ms |  5.66 ms |  5.30 ms |  0.98 |    0.01 |           214,382,434 |                 801,792 |
MA>| CachedLinqSauvolaScalar |     5 | p00743.bmp |   815.8 ms | 16.20 ms | 15.91 ms |  1.18 |    0.02 |            97,124,131 |               1,867,112 |

MA>Run 2:
MA>|                  Method | WHalf |   FileName |       Mean |    Error |   StdDev | Ratio | RatioSD | BranchInstructions/Op | BranchMispredictions/Op |
MA>|------------------------ |------ |----------- |-----------:|---------:|---------:|------:|--------:|----------------------:|------------------------:|
MA>|             SafeSauvola |     5 | p00743.bmp | 1,256.7 ms |  2.48 ms |  2.32 ms |  1.83 |    0.01 |           803,031,495 |               3,632,242 |
MA>|     UnsafeSauvolaScalar |     5 | p00743.bmp |   685.3 ms |  3.28 ms |  3.07 ms |  1.00 |    0.00 |           305,128,752 |                 916,065 |
MA>|       LinqSauvolaVector |     5 | p00743.bmp | 1,115.8 ms |  4.97 ms |  4.41 ms |  1.63 |    0.01 |           561,164,990 |               5,154,875 |
MA>|       LinqSauvolaScalar |     5 | p00743.bmp | 1,241.6 ms |  3.64 ms |  3.41 ms |  1.81 |    0.01 |           425,470,320 |               6,090,332 |
MA>| CachedLinqSauvolaVector |     5 | p00743.bmp |   671.9 ms | 12.92 ms | 13.27 ms |  0.98 |    0.02 |           205,053,288 |                 729,199 |
MA>| CachedLinqSauvolaScalar |     5 | p00743.bmp |   785.7 ms |  3.74 ms |  3.50 ms |  1.15 |    0.00 |            99,804,388 |               1,917,611 |
MA>

Всё равно не понимаю, куда он тормозит при исполнении. Я сейчас вывожу ручки для отключения оптимизаций; можно будет попробовать сгенерировать код, максимально близкий к UnsafeSauvolaScalar.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[12]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 05.08.20 12:36
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Я, если честно, не понимаю, откуда он (дотнет) берёт такие глубины стека. Там же вполне себе прямолинейный код, два вложенных цикла. Ну, выражение там есть. Откуда там эти тысячи-то? Едва ли 20 maxstack должен быть.

Я полагаю это исходит из SSA формы и получается что каждый блок имеет свои входы-выходы. (Ну или чего-то подобного. У меня сложилось впечатление что он их назначает исходя из загрузок на IL-стэк.) Вот они и считаются temp locals. Вот когда их становится дохрена — тут мы и упираемся в лимит. Теоретически он должен был схлопнуть их но вместо этого он отлистывает rsp на внушительное расстояние (может он там и не использует большую часть). И это расстояние вдвое меньше в последней версии. Но, что-то он схлопывает. Когда не упирается в лимит. Я получал дампы вызывая один бенчмарк *Scalar но финальный асм бодро напихан какими-то векторными инструкциями. Если еще раз полезу — то надо будет вызывать отдельным примером, потому что есть риск что что-то идет не так. По крайней мере я себя чувствую некомфортно. Еще если бы я представлял что там должно быть... а так, ну вижу асм, ну и толку. Заодно сграбить unsafe.
Я пытался натравить kdiff3 на логи, но он сказал нечего там и пытаться смотреть (крешнулся ).
В общем сейчас остался осадок что чего-то недопонял. Надо переждать, мож чего интересного еще

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

Ты разглядел последние два (новых) столбика в последних запусках? (Бранчинг)
Re[13]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 05.08.20 17:41
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:
S>>Всё равно не понимаю, куда он тормозит при исполнении. Я сейчас вывожу ручки для отключения оптимизаций; можно будет попробовать сгенерировать код, максимально близкий к UnsafeSauvolaScalar.
MA> Ты разглядел последние два (новых) столбика в последних запусках? (Бранчинг)
Ну, в каком-то смысле понятно — в векторном случае бранчинга немножко меньше, т.к. там финальное сравнение с порогом выполнено через SIMD и пень-колоду.
В скалярном всё же 1 бранч на цикл + 1 бранч на тернарный оператор.
В обычном unsafe варианте мы имеем + 3 бранча на "если xmin<0", но они, похоже, хорошо предсказываются процессором. Более того, я не понимаю, каким хреном у unsafe получается вдвое меньше mispredictions чем у LinqScalar.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[14]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Mystic Artifact  
Дата: 05.08.20 18:06
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>В скалярном всё же 1 бранч на цикл + 1 бранч на тернарный оператор.

S>В обычном unsafe варианте мы имеем + 3 бранча на "если xmin<0", но они, похоже, хорошо предсказываются процессором. Более того, я не понимаю, каким хреном у unsafe получается вдвое меньше mispredictions чем у LinqScalar.
Я не знаю, но в том асме, что я видел — куча short-forward бранчей. Это то что почти все процессоры понимают, но я х.з.
Я пока вывел такую закономерность: мой проц выигрывает когда не ошибается в бранчах, но ему почти пофигу на их количество. Твой проц — напротив сильно выигрывает от уменьшения кол-ва бранчинга (что странно, ведь он помоднее моего). Unsafe версия так же содержит идексеры a * b + c которые в идеале должы пониматься процессорами, если правильно скомпилировано. Я пробовал вручныю их вынести в отнельную переменную — получалось только хуже.

На самом деле хотелось бы увидеть еще пару железок и тогда можно сделать выводы.
Re[2]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.08.20 04:36
Оценка:
Здравствуйте, VladCore, Вы писали:
VC>я не смотрел исходники но возможно требуется AVX2 (целочисленный)? но тогда непонятно почему вешается а не падает с ошибкой?

Перепроверь на новой версии — там не будет векторизованных операций, но интересно посмотреть скалярную статистику на твоих железках.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[15]: 2D-Linq и оптимизация цифровых фильтров - 4
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.08.20 04:40
Оценка:
Здравствуйте, Mystic Artifact, Вы писали:

MA> Я не знаю, но в том асме, что я видел — куча short-forward бранчей. Это то что почти все процессоры понимают, но я х.з.

Ну да — собственно каждый if или ?: — это short-forward branch.
MA> Я пока вывел такую закономерность: мой проц выигрывает когда не ошибается в бранчах, но ему почти пофигу на их количество. Твой проц — напротив сильно выигрывает от уменьшения кол-ва бранчинга (что странно, ведь он помоднее моего).
Да, похоже у моего зарезано предсказание переходов, или конвеер сделан по-другому. Влияет либо поколение, либо то, что у меня ноутбучная версия.
MA>Unsafe версия так же содержит идексеры a * b + c которые в идеале должы пониматься процессорами, если правильно скомпилировано. Я пробовал вручныю их вынести в отнельную переменную — получалось только хуже.
Да, я это тоже пробовал. В ранних версиях я упирался в скользящие указатели, чтобы избежать вот этой арифметики. На практике JIT достаточно умный чтобы применить косвенную адресацию для более-менее всех интересных нам случаев.
MA> На самом деле хотелось бы увидеть еще пару железок и тогда можно сделать выводы.
Ага. Можешь ещё выложить статистику по C4 бенчмарку?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.