Данная статья содержит ряд тестов по сравнению производительности для четырех различных коллекций реализующих интерфейс IDictionary: обобщенного Dictionary, обобщенного SortedDictionary, старого Hashtable и обобщенного SortedList.

Сравнение выполнялось по следующим параметрам: использование памяти (в байтах), время на добавление записей (в тактах), время на поиск записи в коллекции (в тактах) и время на итерирование при помощи foreach (в тактах).

Тестирование производилось 8000 раз для всех четырех коллекций в произвольном порядке, таким образом, каждая коллекция была протестирована как минимум 1000 раз.

Тестирование производилось в 5 этапов для того, чтобы определить влияние количества записей на производительность. На первом этапе количество записей составило 50, на втором - 500, на третьем - 5000, на четвертом - 50000.

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

Общая формула для получения коэффициента производительности для любой величины:
X = min(val1, val2, … valn)/X

Таким образом, лучшая (минимальная) производительность будет иметь значение единицы, в то время как любые другие значения будут дробной частью единицы.

Результирующий график использования памяти:

Результаты практически не изменяются при увеличении числа записей в коллекциях. Лучшее использование памяти наблюдается у SortedList, за ним следует Hashtable и SortedDictionary. Dictionary замыкает список наихудшим использованием памяти. Несмотря на данные выводы, важно отметить, что различия не столь велики и, если вашему приложению не установлены специальные ограничения по использованию памяти, вам стоит обратить внимание на 2 других параметра: время на добавление записей и время на поиск ключа в коллекции - как наиболее важного. Необходимо отметить, что данные тесты не учитывают влияние сборщика мусора и поэтому результаты можно принять только в самом общем виде.

Результирующий график времени на добавление записей:

При небольшом числе записей, разница между всеми 4 реализациями невелика. С увеличением количества записей в коллекциях, производительность SortedList сильно падает. SortedDictionary показывает чуть лучшие результаты, но все еще гораздо худшие, чем две других реализации. Второе место занимает Hashtable, а абсолютным лидером выходит обобщенный Dictionary.

Результирующий график времени на поиск записей в коллекциях:

Победителем выступает Hashtable. Однако, данный тест не принимает во внимание тип хранимых объектов: возможно, это будет темой для последующих тестов. Следующая по скорости коллекция - обобщенный Dictionary. SortedList и SortedDictionary замыкают список, при том что разница между ними невелика.

Стоит отметить, что превосходство Hashtable над обобщенным Dictionary для операций добавления и поиска записей показанное выше, на самом деле, вызвано тем, что тесты основаны на необобщенном интерфейсе IDictionary, поэтому каждое добавление или поиск записи сопровождается проверкой типа ключа. Использование обобщенного IDictionary дает совершенно другой результат, где обобщенный Dictionary работает быстрее чем Hashtable. Таким образом, обобщенный Dictionary - абсолютный победитель в данных операциях.

Результирующий график времени на итерации внутри цикла foreach:

В данном тесте лидирует SortedList, за ним следует Dictionary, который во всех случаях быстрее чем Hashtable. Список замыкает SortedDictionary.

Ниже представлен график менеджера задач, полученный во время тестирования. График отображает картину использования памяти. Зона A получена во время фазы добавления записей - когда выделяется все больше и больше памяти. Зона B начинается по завершению добавления записей и заканчивается сборкой мусора.

Ниже представлен код, использованный во время тестирования. Значения переменной NumberInsertedKeys поочередно: 50, 500, 5000, 50000 и 10000 для разных стадий.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
/*
to compile enter in the command prompt:
C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\csc IDictTest.cs
to run enter in the command prompt:
IDictTest
*/
namespace IDictTest{

public class RunResult{
public decimal MemoryUsed;
public decimal InsertTicks;
public decimal SearchTicks;
public decimal ForEachTicks;
}

public class Program
{

private static int SearchIndex = 27;
//private const int NumberInsertedKeys = 50;
//private const int NumberInsertedKeys = 500;
//private const int NumberInsertedKeys = 5000;
private const int NumberInsertedKeys = 50000;
//private const int NumberInsertedKeys = 100000;
private const int NumberTests = 8000;

private static readonly string[] Letters =
{”A”,”B”,”C”,”D”,”E”,”F”,”G”,”H”,”I”,”J”};

public static void Main(string[] args) {
try{
// TRY STARTS HERE ———-

List listDictionary = new List();
List listSortedDictionary = new List();
List listHashtable = new List();
List listSorderList = new List();
Stopwatch watch = Stopwatch.StartNew();

for(int i = 0; i < NumberTests; i++){
SearchIndex += 1;
Random rand = new Random();
int randInt = rand.Next(0, 4);
if(randInt == 0){
listDictionary.Add(
Test("Dictionary", new Dictionary(), i));
}else if(randInt == 1){
listSortedDictionary.Add(
Test(”SortedDictionary”,
new SortedDictionary(), i));
}else if(randInt == 2){
listHashtable.Add(
Test(”Hashtable”, new Hashtable(), i));
}else if(randInt == 3){
listSorderList.Add(
Test(”SortedList”, new SortedList(), i));
}
}

Console.Clear();
Msg(”Time taken (minutes): {0} or about {1} minutes and {2} seconds”,
watch.Elapsed.TotalMinutes,
watch.Elapsed.Minutes,
watch.Elapsed.Seconds);

RunResult resultDict = CalculateAvg(listDictionary);
RunResult resultSortDict = CalculateAvg(listSortedDictionary);
RunResult resultHash = CalculateAvg(listHashtable);
RunResult resultSortList = CalculateAvg(listSorderList);

RunResult min =
new RunResult{
MemoryUsed = Math.Min(Math.Min(Math.Min(resultDict.MemoryUsed, resultSortDict.MemoryUsed),resultHash.MemoryUsed),resultSortList.MemoryUsed),
InsertTicks = Math.Min(Math.Min(Math.Min(resultDict.InsertTicks, resultSortDict.InsertTicks), resultHash.InsertTicks), resultSortList.InsertTicks),
SearchTicks = Math.Min(Math.Min(Math.Min(resultDict.SearchTicks, resultSortDict.SearchTicks), resultHash.SearchTicks), resultSortList.SearchTicks),
ForEachTicks = Math.Min(Math.Min(Math.Min(resultDict.ForEachTicks, resultSortDict.ForEachTicks), resultHash.ForEachTicks), resultSortList.ForEachTicks)
};

// print the results
PrintResults(resultDict, listDictionary.Count, min, “Dictionary”);
PrintResults(resultSortDict, listDictionary.Count, min, “SortedDictionary”);
PrintResults(resultHash, listDictionary.Count, min, “Hashtable”);
PrintResults(resultSortList, listDictionary.Count, min, “SortedList”);

// TRY ENDS HERE ———-

}catch(Exception ex){
Msg(”{0}”, ex);
}
}

private static RunResult CalculateAvg(List list){
decimal sumMemory = 0;
decimal sumInsert = 0;
decimal sumSearch = 0;
decimal sumForEach = 0;
for(int i = 0; i < list.Count; i++){
RunResult curr = list[i];
sumMemory += curr.MemoryUsed;
sumInsert += curr.InsertTicks;
sumSearch += curr.SearchTicks;
sumForEach += curr.ForEachTicks;
// uncomment to print each line
//Msg("{0,11} {1,13} {2,14}",
//curr.MemoryUsed, curr.InsertTicks, curr.SearchTicks);
}
return new RunResult{
MemoryUsed = sumMemory / list.Count,
InsertTicks = sumInsert / list.Count,
SearchTicks = sumSearch / list.Count,
ForEachTicks = sumForEach / list.Count,
};
}

private static void PrintResults(RunResult result, int count, RunResult min, string name){
Msg("--------- Results for {0}", name);
Msg("# Tests {0}", count);
Msg("Memory Used Insert Ticks Search Ticks ForEach Ticks");
Msg("Average Values:");
Msg("{0,11:N} {1,13:N} {2,14:N} {3,14:N}",
result.MemoryUsed,
result.InsertTicks,
result.SearchTicks,
result.ForEachTicks);
Msg("Performance Coefficient:");
Msg("{0,11:N} {1,13:N} {2,14:N} {3,14:N}",
min.MemoryUsed/result.MemoryUsed,
min.InsertTicks/result.InsertTicks,
min.SearchTicks/result.SearchTicks,
min.ForEachTicks/result.ForEachTicks);
Msg("");
}

private static void Msg(string name, params object[] args){
Console.WriteLine(name, args);
}

private static RunResult Test(string name, IDictionary dict, int n){
Console.Clear();
Msg("Currently executing test {1} of {2} for {0} object",
name, n + 1, NumberTests);
RunResult rr = new RunResult();
Stopwatch watch;
Random rand = new Random( );
long memoryStart = System.GC.GetTotalMemory(true);
long insertTicksSum = 0;
for(int i = 0; i < NumberInsertedKeys; i++){
string key = GetRandomLetter(rand, i)+"_key"+i;
string value = "value"+i;

watch = Stopwatch.StartNew();
dict.Add(key, value);
watch.Stop();

insertTicksSum += watch.ElapsedTicks;
}
rr.MemoryUsed = System.GC.GetTotalMemory(true) - memoryStart;

rr.InsertTicks = insertTicksSum;

watch = Stopwatch.StartNew();
object searchResult = dict["C_key"+SearchIndex];
watch.Stop();

rr.SearchTicks = watch.ElapsedTicks;

watch = Stopwatch.StartNew();
foreach(var curr in dict){}
watch.Stop();

rr.ForEachTicks = watch.ElapsedTicks;

return rr;
}

private static string GetRandomLetter(Random rand, int i){
if(i == SearchIndex){
return "C";
}
return Letters[rand.Next(0, 10)];
}

}

}

Конфигурация компьютера, используемого во время тестирования:

Processor: Intel(R) Core(TM)2 Duo CPU T7300 @ 2.00GHz 2.GHz
Memory (RAM): 2.00 GB
System type: 32-bit Operating System
Windows Vista

Источник: blog.bodurov.com
Перевод: Игорь Кадуленков, www.kadulenkov.com