Почему массив быстрее словаря в этом тесте

Question

Почему массив в этом тесте быстрее, чем цикл словаря в 150 раз до конца массива размером 150, быстрее, чем доступ к одному и тому же ключу 150 раз?

Я думал, что это из-за оптимизации, но я отключил его

Пожалуйста, объясните

[MethodImplAttribute(MethodImplOptions.NoOptimization)]
    [Repeat(25)]
    [Test]
    public void DictionaryVSArray()
    {
        //array is faster from 0 up to 600 items;
        int collectionSize = 150;

        //populate array
        int[] array = new int[collectionSize];
        for (int i = 0; i < collectionSize; i++)
        {
            array[i] = i;
        }

        //populate dictionary
        Dictionary<int, int> dictionary = new Dictionary<int, int>();
        for (int i = 0; i < collectionSize; i++)
        {
            dictionary.Add(i, i);

        }

        //dictionary measurement
        Stopwatch dictStopWatch = new Stopwatch();
        dictStopWatch.Start();

        for(int i = 0; i< collectionSize; i++)
        {
            var s = dictionary[collectionSize-1];
        }
        dictStopWatch.Stop();
        TimeSpan elapsedDict = dictStopWatch.Elapsed;


        //array measurement
        Stopwatch arrayStopWatch = new Stopwatch();
        arrayStopWatch.Start();

        for (int i = 0; i < collectionSize; i++)
        {
            foreach (int item in array)
            {
                if (collectionSize-1 == item)
                {
                    break;
                }
            }
        }
        arrayStopWatch.Stop();
        TimeSpan elapsedArray = arrayStopWatch.Elapsed;

        Assert.Greater(elapsedArray, elapsedDict, $"array was faster by {(elapsedDict - elapsedArray).TotalMilliseconds} miliseconds");
    }

Answer 1

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

Для моей настройки

int collectionSize = 10000;

//populate array
_array = new int[collectionSize];

for (int i = 0; i < collectionSize; i++)
{
   _array[i] = i;
}

_dictionary = new Dictionary<int, int>();
for (int i = 0; i < collectionSize; i++)
{
   _dictionary.Add(i, i);

}

Код

[Test("List", "", true)]
public object Test1(int[] input, int scale)
{
   for (int i = 0; i < input.Length; i++)
   {
      foreach (int item in _array)
      {
         if (collectionSize - 1 == item)
         {
            break;
         }
      }
   }

   return null;
}

[Test("Dictionary", "", false)]
public object Test2(int[] input, int scale)
{
   for (int i = 0; i < input.Length; i++)
   {
      var s = _dictionary[input[i]];
   }

   return null;
}

Тесты

Я запускаю каждый тест 100 раз, Сбор мусора перед каждым запуском, выполняю прогрев и запускаю 1000 случайных чисел в диапазоне от 0 до 255 для тестирования (в режиме выпуска).

┌──────────────────┬────────────────────────────────────────────┐
│        Test Mode │ Release (64Bit)                            │
│   Test Framework │ .NET Framework 4.7.1 (CLR 4.0.30319.42000) │
╞══════════════════╪════════════════════════════════════════════╡
│ Operating System │ Microsoft Windows 10 Pro                   │
│          Version │ 10.0.17134                                 │
├──────────────────┼────────────────────────────────────────────┤
│       CPU System │ Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz    │
│  CPU Description │ Intel64 Family 6 Model 42 Stepping 7       │
├──────────────────┼──────────┬──────────────────┬──────────────┤
│  Cores (Threads) │ 4 (8)    │     Architecture │ x64          │
│      Clock Speed │ 3401 MHz │        Bus Speed │ 100 MHz      │
│          L2Cache │ 1 MB     │          L3Cache │ 8 MB         │
└──────────────────┴──────────┴──────────────────┴──────────────┘

Результаты

┌── Standard input ────────────────────────────────────────────────────────┐
│ Value      │   Average │   Fastest │   Cycles │ Garbage │ Test │    Gain │
├── Scale 1,000 ────────────────────────────────────────────── 0.784 sec ──┤
│ Dictionary │ 13.680 µs │ 13.208 µs │ 50.621 K │ 0.000 B │ N/A  │ 99.76 % │
│ List       │  5.706 ms │  5.485 ms │ 19.406 M │ 0.000 B │ Base │  0.00 % │
└──────────────────────────────────────────────────────────────────────────┘

Answer 2

В словаре есть таблица ключей для быстрого доступа к ней. И найти что-то по хешу в большинстве случаев быстрее, чем сравнивать содержимое. Но в вашем случае целочисленные значения быстро сравниваются, и, поскольку у вас есть просто 150 * 150 элементов (22500), это почти не занимает времени, ни для словаря, ни для массива.

Попробуйте что-нибудь около 1000 * 1000.

Сколько мс вы на самом деле измеряете?

Также вам следует «искать» i-значение цикла, не всегда с тем же «collectionSize». Может быть, компилятор тоже там оптимизирует.

Answer 3

в секундомере у вас есть условие if, которое может возникнуть при запуске повторения foreach.