Эффективный метод пакетного чтения из таблицы поиска - PullRequest
Новая
       9

Эффективный метод пакетного чтения из таблицы поиска

0 голосов
/ 03 августа 2020

Следующий метод должен читать все значения из источника с индексами в ключах и сохранять их в назначении . Для простоты предположим, что длины ключей destination и равны, а все индексы в keys равны> = 0 и <<em> source. Длина . Длина ключей мала (<1000), длина <em>источника высокая (миллионы). 

public static void Gather<T>(Span<T> destination, ReadOnlySpan<T> source, 
    ReadOnlySpan<int> keys)
{
    for (int i = 0; i < keys.Length; i++)
    {
        destination[i] = source[keys[i]];
    }
}

Какой метод будет эффективным в современных оборудование (SSE2, AVX2) для смешанного набора сценариев ios:

  • ключи случайны
  • ключи являются последовательными
  • ключи частично последовательны

Benchmark

Обычно я использую Benchmark. net для микробенчмарков, но я не нашел способа проверить sh кеш процессора между операциями. 

 class Program
 {
        public class GatherTest
        {
            private readonly int[] sequentialKeys;
            private readonly int[] partiallySequentialKeys;
            private readonly int[] randomKeys;
            private readonly int[] source;
            private readonly int[] destination;

            private const int KEYS_LENGTH = 1_000;
            private const int SOURCE_LENGTH = 10_000_000;

            public GatherTest()
            {
                var rng = new Random(0);
                this.sequentialKeys = Enumerable.Range(0, KEYS_LENGTH).ToArray();
                this.partiallySequentialKeys = Enumerable.Range(0, KEYS_LENGTH / 4).SelectMany(_ => Enumerable.Range(rng.Next(SOURCE_LENGTH - 4), 4)).ToArray();
                this.randomKeys = Enumerable.Range(0, KEYS_LENGTH).Select(_ => rng.Next(SOURCE_LENGTH)).ToArray();
                this.source = Enumerable.Range(0, SOURCE_LENGTH).ToArray();
                this.destination = new int[KEYS_LENGTH];
            }

            public static void Gather<T>(Span<T> destination, ReadOnlySpan<T> source, ReadOnlySpan<int> keys)
            {
                for (int i = 0; i < keys.Length; i++)
                {
                    destination[i] = source[keys[i]];
                }
            }

            public static void Gather_Unnrolled<T>(Span<T> destination, ReadOnlySpan<T> source, ReadOnlySpan<int> keys)
            {
                int i = 0;
                for (; i + 4 < keys.Length; i += 4)
                {
                    destination[i] = source[keys[i]];
                    destination[i + 1] = source[keys[i + 1]];
                    destination[i + 2] = source[keys[i + 2]];
                    destination[i + 3] = source[keys[i + 3]];
                }

                for (; i < keys.Length; i++)
                {
                    destination[i] = source[keys[i]];
                }
            }

            public void FlushCache()
            {
                for (int i = 0; i < this.source.Length; i++) _ = this.source[i];
            }

            public void Gather_Sequential()
            {
                Gather<int>(this.destination, this.source, this.sequentialKeys);
            }

            public void Gather_Sequential_Unrolled()
            {
                Gather_Unnrolled<int>(this.destination, this.source, this.sequentialKeys);
            }

            public void Gather_Random()
            {
                Gather<int>(this.destination, this.source, this.randomKeys);
            }

            public void Gather_Random_Unrolled()
            {
                Gather_Unnrolled<int>(this.destination, this.source, this.randomKeys);
            }

            public void Gather_Partially_Sequential()
            {
                Gather<int>(this.destination, this.source, this.partiallySequentialKeys);
            }

            public void Gather_Partially_Sequential_Unrolled()
            {
                Gather_Unnrolled<int>(this.destination, this.source, this.partiallySequentialKeys);
            }
            
            public void Test(Action body, string name)
            {
                var sw = new Stopwatch();
                for (int i = 0; i < 10000; i++)
                {
                    this.FlushCache();
                    sw.Start();
                    body();
                    sw.Stop();
                }

                Console.WriteLine(name + ": " + sw.Elapsed.TotalMilliseconds+" ms");
            }
        }

        static void Main(string[] args)
        {
            var benchmark = new GatherTest();
            benchmark.Test(benchmark.Gather_Sequential, nameof(benchmark.Gather_Sequential));
            benchmark.Test(benchmark.Gather_Sequential_Unrolled, nameof(benchmark.Gather_Sequential_Unrolled));
            benchmark.Test(benchmark.Gather_Partially_Sequential, nameof(benchmark.Gather_Partially_Sequential));
            benchmark.Test(benchmark.Gather_Partially_Sequential_Unrolled, nameof(benchmark.Gather_Partially_Sequential_Unrolled));
            benchmark.Test(benchmark.Gather_Random, nameof(benchmark.Gather_Random));
            benchmark.Test(benchmark.Gather_Random_Unrolled, nameof(benchmark.Gather_Random_Unrolled));
        }
    }

Вывод 

Gather_Sequential: 18.8414 ms
Gather_Sequential_Unrolled: 18.0061 ms
Gather_Partially_Sequential: 63.0309 ms
Gather_Partially_Sequential_Unrolled: 54.9459 ms
Gather_Random: 127.5608 ms
Gather_Random_Unrolled: 116.4456 ms

Как видите, произвольный доступ намного медленнее, чем последовательный. Я предполагаю, что это связано с тем, что для каждого скопированного значения загружается вся строка кэша процессора.

Обновление: я попробовал инструкции AVX из System.Runtime.Intrinsics.X86 и протестировал функции в двух сценариях ios: cold ( значения не в cpu-cache) и теплые (значения уже в cpu-cache). 

class Program
    {
        public class GatherTest
        {
            private readonly int[] sequentialKeys;
            private readonly int[] partiallySequentialKeys;
            private readonly int[] randomKeys;
            private readonly int[] source;
            private readonly int[] destination;

            private const int KEYS_LENGTH = 1_000;
            private const int SOURCE_LENGTH = 10_000_000;

            public GatherTest()
            {
                var rng = new Random(0);
                this.sequentialKeys = Enumerable.Range(0, KEYS_LENGTH).ToArray();
                this.partiallySequentialKeys = Enumerable.Range(0, KEYS_LENGTH / 4).SelectMany(_ => Enumerable.Range(rng.Next(SOURCE_LENGTH - 4), 4)).ToArray();
                this.randomKeys = Enumerable.Range(0, KEYS_LENGTH).Select(_ => rng.Next(SOURCE_LENGTH)).ToArray();
                this.source = Enumerable.Range(0, SOURCE_LENGTH).ToArray();
                this.destination = new int[KEYS_LENGTH];
            }

            public static void Gather<T>(Span<T> destination, ReadOnlySpan<T> source, ReadOnlySpan<int> keys)
            {
                for (int i = 0; i < keys.Length; i++)
                {
                    destination[i] = source[keys[i]];
                }
            }

            public static void Gather_Unnrolled<T>(Span<T> destination, ReadOnlySpan<T> source, ReadOnlySpan<int> keys)
            {
                int i = 0;
                for (; i + 4 <= keys.Length; i += 4)
                {
                    destination[i] = source[keys[i]];
                    destination[i + 1] = source[keys[i + 1]];
                    destination[i + 2] = source[keys[i + 2]];
                    destination[i + 3] = source[keys[i + 3]];
                }

                for (; i < keys.Length; i++)
                {
                    destination[i] = source[keys[i]];
                }
            }

            public static unsafe void Gather_Avx(Span<int> destination, ReadOnlySpan<int> source, ReadOnlySpan<int> keys) 
            {
                var vectorLength = Vector256<int>.Count;

                fixed (int* dst = destination)
                fixed (int* src = source)
                fixed (int* k = keys)
                {
                    int i = 0;
                    for (; i + vectorLength <= keys.Length; i += vectorLength)
                    {
                        var keyVector = Avx.LoadVector256(k + i);
                        var destVector = Avx2.GatherVector256(src, keyVector, sizeof(int));
                        Avx.Store(dst + i, destVector);
                    }

                    for (; i < keys.Length; i++)
                    {
                        destination[i] = source[keys[i]];
                    }
                }
            }

            public void FlushCache()
            {
                for (int i = 0; i < this.source.Length; i++) _ = this.source[i];
            }

            public void Gather_Sequential()
            {
                Gather<int>(this.destination, this.source, this.sequentialKeys);
            }

            public void Gather_Sequential_Unrolled()
            {
                Gather_Unnrolled<int>(this.destination, this.source, this.sequentialKeys);
            }
            
            public void Gather_Sequential_Avx()
            {
                Gather_Avx(this.destination, this.source, this.sequentialKeys);
            }

            public void Gather_Random()
            {
                Gather<int>(this.destination, this.source, this.randomKeys);
            }

            public void Gather_Random_Unrolled()
            {
                Gather_Unnrolled<int>(this.destination, this.source, this.randomKeys);
            }
            
            public void Gather_Random_Avx()
            {
                Gather_Avx(this.destination, this.source, this.randomKeys);
            }

            public void Gather_Partially_Sequential()
            {
                Gather<int>(this.destination, this.source, this.partiallySequentialKeys);
            }

            public void Gather_Partially_Sequential_Unrolled()
            {
                Gather_Unnrolled<int>(this.destination, this.source, this.partiallySequentialKeys);
            }
            
            public void Gather_Partially_Sequential_Avx()
            {
                Gather_Avx(this.destination, this.source, this.partiallySequentialKeys);
            }
            
            public void Test(Action body, string name)
            {
                this.Test(body, name + " (cold)", true);
                this.Test(body, name + " (warm)", false);
            }
            
            public void Test(Action body, string name, bool flush)
            {
                var sw = new Stopwatch();
                for (int i = 0; i < 10000; i++)
                {
                    if (flush) this.FlushCache();
                    sw.Start();
                    body();
                    sw.Stop();
                }

                Console.WriteLine(name + ": " + sw.Elapsed.TotalMilliseconds+" ms");
            }
        }

        static void Main(string[] args)
        {
            var benchmark = new GatherTest();
            benchmark.Test(benchmark.Gather_Sequential, nameof(benchmark.Gather_Sequential));
            benchmark.Test(benchmark.Gather_Sequential_Unrolled, nameof(benchmark.Gather_Sequential_Unrolled));
            benchmark.Test(benchmark.Gather_Sequential_Avx, nameof(benchmark.Gather_Sequential_Avx));
            benchmark.Test(benchmark.Gather_Partially_Sequential, nameof(benchmark.Gather_Partially_Sequential));
            benchmark.Test(benchmark.Gather_Partially_Sequential_Unrolled, nameof(benchmark.Gather_Partially_Sequential_Unrolled));
            benchmark.Test(benchmark.Gather_Partially_Sequential_Avx, nameof(benchmark.Gather_Partially_Sequential_Avx));
            benchmark.Test(benchmark.Gather_Random, nameof(benchmark.Gather_Random));
            benchmark.Test(benchmark.Gather_Random_Unrolled, nameof(benchmark.Gather_Random_Unrolled));
            benchmark.Test(benchmark.Gather_Random_Avx, nameof(benchmark.Gather_Random_Avx));
        }
    }

Output 

Gather_Sequential (cold): 18.3606 ms
Gather_Sequential (warm): 8.6091 ms
Gather_Sequential_Unrolled (cold): 16.8114 ms
Gather_Sequential_Unrolled (warm): 7.092 ms
Gather_Sequential_Avx (cold): 14.6569 ms
Gather_Sequential_Avx (warm): 2.4619 ms
Gather_Partially_Sequential (cold): 76.0622 ms
Gather_Partially_Sequential (warm): 12.1919 ms
Gather_Partially_Sequential_Unrolled (cold): 71.6684 ms
Gather_Partially_Sequential_Unrolled (warm): 8.1956 ms
Gather_Partially_Sequential_Avx (cold): 48.2327 ms
Gather_Partially_Sequential_Avx (warm): 4.2666 ms
Gather_Random (cold): 116.286 ms
Gather_Random (warm): 15.2227 ms
Gather_Random_Unrolled (cold): 109.3275 ms
Gather_Random_Unrolled (warm): 12.5555 ms
Gather_Random_Avx (cold): 110.4421 ms
Gather_Random_Avx (warm): 6.6867 ms

Хотя нет значительного ускорения в «холодный» сценарий, AVX действительно светит, если все значения уже находятся в cpu-cache. Остающиеся проблемы:

  • Вы должны использовать небезопасный код, который может быть невозможен в вашем проекте
  • Невозможно иметь единственную общую c версию функции, даже с неуправляемым ограничением
  • Тестовая функция здесь для AVX не является надежной (без проверки функций процессора, может не работать при неправильном выравнивании), поэтому, пожалуйста, не используйте ее в текущем форма
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...