Производительность C # - линейный доступ к массиву и произвольный доступ

Question

Может кто-нибудь помочь мне понять, почему доступ к массивам с использованием линейного приращения для индекса примерно в 3-4 раза быстрее, чем с использованием случайного индекса?

Есть ли способ ускорить время доступа к случайному индексу?

Пожалуйста, рассмотрите следующий тестовый код, он возвращает ~ 3 секунды для линейного, ~ 9-10 секунд для случайного:

    public static void test()
    {
        var arr = new byte[64 * 1024 * 1024];
        byte b = 0;

        var sw = new Stopwatch();

        double timeSum = 0;

        for (var i = 0; i < arr.Length; i++)
        {

            sw.Restart();
            b = arr[i];
            sw.Stop();
            timeSum += sw.Elapsed.TotalMilliseconds;
        }


        Console.WriteLine("Linear access : " + timeSum + " ms");


        timeSum = 0;

        var rng = new Random();
        var rnum = 0;
        for (var i = 0; i < arr.Length; i++)
        {
            rnum = rng.Next(0, arr.Length - 1);
            sw.Restart();
            b = arr[rnum];
            sw.Stop();
            timeSum += sw.Elapsed.TotalMilliseconds;
        }

        sw.Stop();

        Console.WriteLine("Random access : " + timeSum + " ms");

    }

Answer 1

Различия, которые вы видите в своем тесте (от 4 до 5 раз), нельзя объяснить только строками кэша и последовательным доступом к массивам.Это правда, что последовательный предсказуемый доступ будет быстрее, но, если вы не управляете огромными массивами, я был бы удивлен, если бы прирост производительности был даже близок к этим цифрам.

РЕДАКТИРОВАТЬ Сразмер массивов в вашем тесте (64x 1024x1024) разница ошеломляет, если честно, намного больше, чем я ожидал.Таким образом, мое первое впечатление было совершенно неверным!

Проблема в вашем эталоне.Вы микро измерения;System.Diagnostics.Stopwatch.

Невозможно измерить с какой-либо степенью уверенности, что отдельные поиски можно найти с помощью *1009*. *1010* * 1011.уважать.Я не задумывался об этом, но по крайней мере следующее пытается сравнить яблоки с яблоками: хитрость заключается в том, чтобы предварительно генерировать случайные и последовательные массивы, а затем сравнивать двойные просмотры:

static void Main(string[] args)
{
    lookUpArray(1, new[] { 0 }, new[] {0}); //warmup JITTER

    var r = new Random();
    const int arraySize = 10000;
    const int repetitions = 10000;

    var lookupArray = new int[arraySize]; //values dont matter
    var sequentialArray = Enumerable.Range(0, arraySize).ToArray();
    var randomArray = sequentialArray.Select(i => r.Next(0, arraySize)).ToArray();

    for (var i = 0; i < 10; i++)
    {
        var sw = Stopwatch.StartNew();
        lookUpArray(repetitions, lookupArray, randomArray);
        sw.Stop();
        Console.WriteLine($"Random: {sw.ElapsedMilliseconds} ms");

        sw.Reset();
        sw.Start();
        lookUpArray(repetitions, lookupArray, sequentialArray);
        sw.Stop();
        Console.WriteLine($"Sequential: {sw.ElapsedMilliseconds} ms");
    }
}

private static void lookUpArray(int repetitions, int[] lookupArray, int[] indexArray)
{
    for (var r = 0; r < repetitions; r++)
    {
        for (var i = 0; i < indexArray.Length; i++)
        {
            var _ = lookupArray[indexArray[i]];
        }
    }
}

Я не бенчмаркингэксперт в любом случае, так что это, вероятно, ужасно во многих отношениях, но я думаю, что это более справедливое сравнение.