Хочу поделиться недавно приобретенным в C# опытом по загрузке и обработке в памяти больших объемов данных. Все нижеуказанное касается Visual Studio 2008 и .Net Framework 3.5.1, на случай каких-либо отличий в других версиях языка или библиотек.
Итак, у нас возникли следующие задачи:
1. Расположить в памяти до 100 миллионов записей, состоящих из строки, длиной 16 символов (уникальный ключ) и двух целочисленных значений, длиной 4 байта каждый;
2. Быстро находить и редактировать запись по ключу.
Начнем с размещения. Суммарный размер полезной информации в записи составляет 24 байта. Весь массив данных должен занять примерно 2,4 Гб (не будем заниматься точными пересчетами по границе 1024). Здесь нас ждет первая неприятность: на x32 процесс ОС Windows может выделить только 2 Гб. На практике, в .Net процессе, это значение еще меньше, у меня получалось выделить где-то в районе 1,8 Гб. Предполагаю, что остальное место занимают библиотеки, которые используются в проекте. Т.о. полностью задачу мы сможем решить только на x64 платформе. В примере мы всё же будем рассматривать x32 для сравнения.
Итак, не мудрствуя лукаво, берем перо (мышь и клавиатуру) и начинаем ваять то, что сразу приходит в голову. Делаем представителя записи в памяти:
Псевдоним int – кроссплатформенный и всегда соответсвует Int32, поэтому будет одинаков для x32 и x64.
Делаем простой массив и загружаем в него 10 млн. записей:
И видим, что мы заняли примерно 760 Мб (х32) и 1040 Мб (х64), т.е. в аккурат 76/104 Б на запись, полезных из которых только 24. Получается, что 100 млн. займут 7,6/10,4 Гб!
Что же заняло 52/80 Б? Есть несколько моментов: инфраструктура объектов .Net и выравнивание расположения в памяти. Начнем с первого. Неплохую статью можно почитать здесь. Получается, что на инфраструктуре класса мы теряем 8/16 Б и еще 4/8 Б на ссылке (наш массив экземпляров классов на самом деле является массивом указателей на экземпляры). Проверим, заменив class на struct:
Замер показал затраты 64/80 Б на запись. Все сходится – мы сэкономили 12/24 Б. Структура является ValueType, поэтому логично предположить, что в массиве у нас теперь не ссылки, а сами значения. Так и есть, поэтому мы собственно и сэкономили 4/8 Б на ссылке. Сама инфраструктура структуры ничего не занимает. Прежде чем пойти дальше и начать оптимизировать Key, на котором мы, судя по всему, теряем очень много, остановимся на одном важном моменте. Переведя запись на структуру мы вырыли себе яму – если располагать данные в одном массиве структур, то нам понадобится один очень большой блок памяти. Даже если свободной памяти достаточно, из-за фрагментации такого сплошного блока может не оказаться. На практике я начал сталкиваться с проблемами выделения более 500 Мб. Этот вопрос мы будем решать во 2-й задаче. Дополнительно, при каждой передаче записи мы теперь будем терять на клонировании структуры, а при организации ссылки – на упаковке/распаковке(boxing/unboxing). Но деваться некуда, нужно экономить место.
Продолжим с полем Key. Тип String является классом, поэтому мы сходу теряем 12/24 Б на записи. На самом деле строка очень тяжелая, для примера можно почитать здесь. Практически, сделав массив строк длинной 16, мы убеждаемся в оккупировании полем Key 56/72 Б на запись. Итого:
Для класса: 8 (два int) + 56/72 (Key) +12/24 (инфраструктура класса + ссылка) = 76/104 Б.
Для структуры: 8 (два int) + 56/72 (Key) = 64/80 Б.
Попробуем перевести поле Key на char[]. Получаем выгоду в 8 Б на обеих платформах. Массив – тоже класс, поэтому на инфраструктуре мы не сэкономили, а только на внутренней организации самого string, учитывая, что внутри он тоже хранит массив char. Каждый символ – юникодный и занимает 2 байта. Плюс где-то может сыграть роль выравнивание в памяти. Самое время о нём поговорить.
Думаю, многие знают, что данные в памяти выгодно выравнивать по определенной платформой границе, например по границе Int32. Подробно об этом можно почитать здесь. В нашем случае на расположении класса/структуры Entry мы ничего не потеряли, т.к. все поля ложатся ровно по границе 4 байт (помним, о том, что Key – ссылка). Можно поэкспериментировать, меняя настройки атрибута StructLayout и используя замер Marshal.SizeOf(new Entry()). Но если сделать одно поле типа byte вместо int, окажется, что всего на массив мы занимаем то же количество памяти, что и при int даже если установить у StructLayout свойство Pack = 1. Т.е. структура сама по себе будет упакована по границе 1 байта, но элементы массива будут располагаться по границе 4 байт. Сразу скажу, что задачу упаковки массивов я не решал, т.к. финальное решение задачи этого не потребовало. Поэтому эта тема, равно как и тема строк/символов здесь полностью не раскрывается. Еще хочу добавить, что значение CharSet = CharSet.Ansi атрибута StructLayout никак не повлияло на размер занимаемой памяти ни строки ни char[].
Итак, на данный момент мы сэкономили 20/32 Б на записи. Т.к. строка в этой задаче подразумевалась не юникодная, было решено использовать byte[] вместо char[]. Экономим еще 16 Б на обеих платформах. Одна запись теперь занимает 40/56 Б. Излишек – 16/32 Б на организацию массива. Оказывается в .Net есть возможность организовать статический фиксированный буфер используя небезопасный режим:
Вот здесь наконец-то мы добиваемся 100% рациональности – наша запись занимает в памяти ровно 24 Б на обеих платформах. На х32 мы сможем загрузить около 75 млн. (1,8 Гб), на х64 все 100 млн. (2,4 Гб). Максимальное количество на x64 по сути ограничено размером доступной памяти. Использовать это счастье можно только в блоках unsafe и fixed. Есть подозрение, что здесь мы будем терять в производительности, но насколько — я не знаю, замеров не делал, т.к. финальный вариант полностью удовлетворил потребности.
Курим и переходим к решению второй задачи.
Для быстрого доступа к 100 млн. записей нам нужно что-то вроде хештаблицы. Стандартный Hashtable не подходит, т.к. использует Object, а это означает, что каждая запись-структура будет положена в специальный класс (boxing) и мы опять начнем терять на инфраструктуре класса. Нам нужен Generic. Есть такой — Dictionary<TKey, TValue>. После неудачной попытки использования и дизассемблирования обнаруживаем следующее (кто не знаком с принципами работы хештаблиц можно почитать здесь):
— избыток 8 Б на вхождение:
Теряем на хранении хешкода и организации связанного списка (используется метод цепочек). Здесь нам кстати нужны две структуры – одна для ключа, другая для значений.
— один сегмент для данных:
Тут остро возникает проблема выделения одного большого блока памяти.
— сегмент хеша больше или равен capacity (очень много вопросов возникает):
— при заполнении происходит ресайзинг с минимум двухкратным запасом, подгонка под этот размер хешсегмента и соответсвенно рехешинг:
Думаю, не стоит детально описывать к чему это всё приводит. Вдумайтесь хотя бы в логику двукратного роста на миллионных объемах.
Обнаружив такое неадекватное поведение, я уже не стал копаться в родных коллекциях на предмет чего-нибудь более рационального, а написал свой словарь. На самом деле всё достаточно тривиально, тем более мне не нужно 90% функциональности, которую реализует стандартный. Код приводить не буду, укажу лишь ключевые моменты:
— не оспльзуем отдельно ключ и значение, все в одной структуре Entry.
— в структуре Entry перекрыл (и как это в структуре что-то можно перекрывать?!) метод GetHashCode(). Использовал модифицированный метод ФНВ отсюда (fig.4)
— в структуре Entry перекрыл метод Equals(object obj). Сравнение идет только по ключу.
— размер хешсегмента сделал заказным в конструкторе. Изменение его размера и рехешинг не предусмотрен.
— индекс в хешсегменте высчитывается как остаток от деления хешкода на размер хешсегмента.
— каждая ячейка хешсегмента – обычный List, который наполняется записями с одинаковым хешкодом. Здесь как раз и решается проблема одного большого блока памяти.
Подсчитаем, сколько мы тратим памяти на организацию:
— хешсегмент = массив ссылок на списки (размер хешсегмента * 4/8 Б);
— экземпляры списков = инфраструктура класса + поля списка (размер хешсегмента * (8/16 +28/44)).
Итого, на организацию сегмента размером в 1 млн. мы затратим примерно 40/68 Мб.
Все бы замечательно и пора выпить шампанского. Но не тут-то было. Оказывается, что List:
— как и стандартный словарь растет с удвоением:
— функция по освобождению избыточно занимаемой памяти не освобождает 0,1 объема:
— ну и в довесок избыточен (для наших целей) по полям и тем, что является классом:
Пришлось написать свой список, с заказным линейным ростом, полным освобождением памяти и экономией 8 Б на полях _syncRoot и _version. Еще можно перевести его на структуру, сэкономив 12 Б.
Все, задача решена – пьем шампанское!
РС Core 2 Quad Q9400 @ 2,66, RAM 4 Gb, Windows Server 2008 R2 Standard x64
Хешсегмент 1 млн., рост списков 25.
Заполнение 100 млн. 5 мин 50 сек. Память 2,46 Гб, пик 3,36 Гб.
Статистика: заполнение 100%, минимальная цепочка 56, максимальная 152, стандартное отклонение 10.
Сравнение 100 млн. в памяти с внешними 100 млн. 4 мин 10 сек.
Хешсегмент 2 млн., рост списков 20.
Заполнение 100 млн. 4 мин 43 сек. Память 2,53 Гб, пик 3,57 Гб.
Статистика: заполнение 100%, минимальная цепочка 20, максимальная 89, стандартное отклонение 7.
Сравнение 100 млн. в памяти с внешними 100 млн. 2 мин 56 сек.
Небольшая ремарка: .Net не сразу освобождает память, даже если мы освободили большое количество объектов. Этого может не произойти и после сбора мусора. Память остается зарезервированной для будущего использования и освободится при острой нехватке памяти в системе (возможно еще по каким-то критериям).
Надеюсь данный опыт пригодится еще кому-то при решении оптимизационных задач.
Итак, у нас возникли следующие задачи:
1. Расположить в памяти до 100 миллионов записей, состоящих из строки, длиной 16 символов (уникальный ключ) и двух целочисленных значений, длиной 4 байта каждый;
2. Быстро находить и редактировать запись по ключу.
Решение задачи №1. Расположение в памяти.
Начнем с размещения. Суммарный размер полезной информации в записи составляет 24 байта. Весь массив данных должен занять примерно 2,4 Гб (не будем заниматься точными пересчетами по границе 1024). Здесь нас ждет первая неприятность: на x32 процесс ОС Windows может выделить только 2 Гб. На практике, в .Net процессе, это значение еще меньше, у меня получалось выделить где-то в районе 1,8 Гб. Предполагаю, что остальное место занимают библиотеки, которые используются в проекте. Т.о. полностью задачу мы сможем решить только на x64 платформе. В примере мы всё же будем рассматривать x32 для сравнения.
Итак, не мудрствуя лукаво, берем перо (мышь и клавиатуру) и начинаем ваять то, что сразу приходит в голову. Делаем представителя записи в памяти:
public class Entry
{
public string Key;
public int IntValue1;
public int IntValue2;
}Псевдоним int – кроссплатформенный и всегда соответсвует Int32, поэтому будет одинаков для x32 и x64.
Делаем простой массив и загружаем в него 10 млн. записей:
public Entry[] Entries = new Entry[10000000];
private void btnCreate_Click(object sender, EventArgs e)
{
int i;
for (i = 0; i < Entries.Length; i++)
{
Entries[i] = new Entry() {Key = i.ToString("0000000000000000")};
}
GC.Collect();
var msg = string.Format("Created {0}, Memory {1}",
i.ToString("0,0"), GC.GetTotalMemory(true).ToString("0,0"));
lbLog.Items.Add(msg);
}И видим, что мы заняли примерно 760 Мб (х32) и 1040 Мб (х64), т.е. в аккурат 76/104 Б на запись, полезных из которых только 24. Получается, что 100 млн. займут 7,6/10,4 Гб!
Что же заняло 52/80 Б? Есть несколько моментов: инфраструктура объектов .Net и выравнивание расположения в памяти. Начнем с первого. Неплохую статью можно почитать здесь. Получается, что на инфраструктуре класса мы теряем 8/16 Б и еще 4/8 Б на ссылке (наш массив экземпляров классов на самом деле является массивом указателей на экземпляры). Проверим, заменив class на struct:
public struct Entry
...Замер показал затраты 64/80 Б на запись. Все сходится – мы сэкономили 12/24 Б. Структура является ValueType, поэтому логично предположить, что в массиве у нас теперь не ссылки, а сами значения. Так и есть, поэтому мы собственно и сэкономили 4/8 Б на ссылке. Сама инфраструктура структуры ничего не занимает. Прежде чем пойти дальше и начать оптимизировать Key, на котором мы, судя по всему, теряем очень много, остановимся на одном важном моменте. Переведя запись на структуру мы вырыли себе яму – если располагать данные в одном массиве структур, то нам понадобится один очень большой блок памяти. Даже если свободной памяти достаточно, из-за фрагментации такого сплошного блока может не оказаться. На практике я начал сталкиваться с проблемами выделения более 500 Мб. Этот вопрос мы будем решать во 2-й задаче. Дополнительно, при каждой передаче записи мы теперь будем терять на клонировании структуры, а при организации ссылки – на упаковке/распаковке(boxing/unboxing). Но деваться некуда, нужно экономить место.
Продолжим с полем Key. Тип String является классом, поэтому мы сходу теряем 12/24 Б на записи. На самом деле строка очень тяжелая, для примера можно почитать здесь. Практически, сделав массив строк длинной 16, мы убеждаемся в оккупировании полем Key 56/72 Б на запись. Итого:
Для класса: 8 (два int) + 56/72 (Key) +12/24 (инфраструктура класса + ссылка) = 76/104 Б.
Для структуры: 8 (два int) + 56/72 (Key) = 64/80 Б.
Попробуем перевести поле Key на char[]. Получаем выгоду в 8 Б на обеих платформах. Массив – тоже класс, поэтому на инфраструктуре мы не сэкономили, а только на внутренней организации самого string, учитывая, что внутри он тоже хранит массив char. Каждый символ – юникодный и занимает 2 байта. Плюс где-то может сыграть роль выравнивание в памяти. Самое время о нём поговорить.
Думаю, многие знают, что данные в памяти выгодно выравнивать по определенной платформой границе, например по границе Int32. Подробно об этом можно почитать здесь. В нашем случае на расположении класса/структуры Entry мы ничего не потеряли, т.к. все поля ложатся ровно по границе 4 байт (помним, о том, что Key – ссылка). Можно поэкспериментировать, меняя настройки атрибута StructLayout и используя замер Marshal.SizeOf(new Entry()). Но если сделать одно поле типа byte вместо int, окажется, что всего на массив мы занимаем то же количество памяти, что и при int даже если установить у StructLayout свойство Pack = 1. Т.е. структура сама по себе будет упакована по границе 1 байта, но элементы массива будут располагаться по границе 4 байт. Сразу скажу, что задачу упаковки массивов я не решал, т.к. финальное решение задачи этого не потребовало. Поэтому эта тема, равно как и тема строк/символов здесь полностью не раскрывается. Еще хочу добавить, что значение CharSet = CharSet.Ansi атрибута StructLayout никак не повлияло на размер занимаемой памяти ни строки ни char[].
Итак, на данный момент мы сэкономили 20/32 Б на записи. Т.к. строка в этой задаче подразумевалась не юникодная, было решено использовать byte[] вместо char[]. Экономим еще 16 Б на обеих платформах. Одна запись теперь занимает 40/56 Б. Излишек – 16/32 Б на организацию массива. Оказывается в .Net есть возможность организовать статический фиксированный буфер используя небезопасный режим:
private unsafe fixed byte _key[16];Вот здесь наконец-то мы добиваемся 100% рациональности – наша запись занимает в памяти ровно 24 Б на обеих платформах. На х32 мы сможем загрузить около 75 млн. (1,8 Гб), на х64 все 100 млн. (2,4 Гб). Максимальное количество на x64 по сути ограничено размером доступной памяти. Использовать это счастье можно только в блоках unsafe и fixed. Есть подозрение, что здесь мы будем терять в производительности, но насколько — я не знаю, замеров не делал, т.к. финальный вариант полностью удовлетворил потребности.
Курим и переходим к решению второй задачи.
Решение задачи №2. Быстрый доступ.
Для быстрого доступа к 100 млн. записей нам нужно что-то вроде хештаблицы. Стандартный Hashtable не подходит, т.к. использует Object, а это означает, что каждая запись-структура будет положена в специальный класс (boxing) и мы опять начнем терять на инфраструктуре класса. Нам нужен Generic. Есть такой — Dictionary<TKey, TValue>. После неудачной попытки использования и дизассемблирования обнаруживаем следующее (кто не знаком с принципами работы хештаблиц можно почитать здесь):
— избыток 8 Б на вхождение:
[StructLayout(LayoutKind.Sequential)]
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}Теряем на хранении хешкода и организации связанного списка (используется метод цепочек). Здесь нам кстати нужны две структуры – одна для ключа, другая для значений.
— один сегмент для данных:
private Entry<TKey, TValue>[] entries;Тут остро возникает проблема выделения одного большого блока памяти.
— сегмент хеша больше или равен capacity (очень много вопросов возникает):
private void Initialize(int capacity) {
…
num = HashHelpers.GetPrime(capacity);
this.buckets = new int[num];
…— при заполнении происходит ресайзинг с минимум двухкратным запасом, подгонка под этот размер хешсегмента и соответсвенно рехешинг:
private unsafe void Resize() {
…
num = HashHelpers.GetPrime(this.count * 2);
numArray = new int[num];
…
entryArray = new Entry<TKey, TValue>[num];
…
this.buckets = numArray;
this.entries = entryArray;
}Думаю, не стоит детально описывать к чему это всё приводит. Вдумайтесь хотя бы в логику двукратного роста на миллионных объемах.
Обнаружив такое неадекватное поведение, я уже не стал копаться в родных коллекциях на предмет чего-нибудь более рационального, а написал свой словарь. На самом деле всё достаточно тривиально, тем более мне не нужно 90% функциональности, которую реализует стандартный. Код приводить не буду, укажу лишь ключевые моменты:
— не оспльзуем отдельно ключ и значение, все в одной структуре Entry.
— в структуре Entry перекрыл (и как это в структуре что-то можно перекрывать?!) метод GetHashCode(). Использовал модифицированный метод ФНВ отсюда (fig.4)
— в структуре Entry перекрыл метод Equals(object obj). Сравнение идет только по ключу.
— размер хешсегмента сделал заказным в конструкторе. Изменение его размера и рехешинг не предусмотрен.
— индекс в хешсегменте высчитывается как остаток от деления хешкода на размер хешсегмента.
— каждая ячейка хешсегмента – обычный List, который наполняется записями с одинаковым хешкодом. Здесь как раз и решается проблема одного большого блока памяти.
Подсчитаем, сколько мы тратим памяти на организацию:
— хешсегмент = массив ссылок на списки (размер хешсегмента * 4/8 Б);
— экземпляры списков = инфраструктура класса + поля списка (размер хешсегмента * (8/16 +28/44)).
Итого, на организацию сегмента размером в 1 млн. мы затратим примерно 40/68 Мб.
Все бы замечательно и пора выпить шампанского. Но не тут-то было. Оказывается, что List:
— как и стандартный словарь растет с удвоением:
private void EnsureCapacity(int min) {
…
num = (((int) this._items.Length) == null) ? 4 : (((int) this._items.Length) * 2);
…— функция по освобождению избыточно занимаемой памяти не освобождает 0,1 объема:
public void TrimExcess()
{
int num;
num = (int) (((double) ((int) this._items.Length)) * 0.9);
if (this._size >= num)
{
goto Label_002A;
}
this.Capacity = this._size;
Label_002A:
return;
}— ну и в довесок избыточен (для наших целей) по полям и тем, что является классом:
public class List...
{
private const int _defaultCapacity = 4;
private static T[] _emptyArray;
private T[] _items;
private int _size;
[NonSerialized]
private object _syncRoot;
private int _version;
...Пришлось написать свой список, с заказным линейным ростом, полным освобождением памяти и экономией 8 Б на полях _syncRoot и _version. Еще можно перевести его на структуру, сэкономив 12 Б.
Все, задача решена – пьем шампанское!
И немного практики
РС Core 2 Quad Q9400 @ 2,66, RAM 4 Gb, Windows Server 2008 R2 Standard x64
Хешсегмент 1 млн., рост списков 25.
Заполнение 100 млн. 5 мин 50 сек. Память 2,46 Гб, пик 3,36 Гб.
Статистика: заполнение 100%, минимальная цепочка 56, максимальная 152, стандартное отклонение 10.
Сравнение 100 млн. в памяти с внешними 100 млн. 4 мин 10 сек.
Хешсегмент 2 млн., рост списков 20.
Заполнение 100 млн. 4 мин 43 сек. Память 2,53 Гб, пик 3,57 Гб.
Статистика: заполнение 100%, минимальная цепочка 20, максимальная 89, стандартное отклонение 7.
Сравнение 100 млн. в памяти с внешними 100 млн. 2 мин 56 сек.
Небольшая ремарка: .Net не сразу освобождает память, даже если мы освободили большое количество объектов. Этого может не произойти и после сбора мусора. Память остается зарезервированной для будущего использования и освободится при острой нехватке памяти в системе (возможно еще по каким-то критериям).
Надеюсь данный опыт пригодится еще кому-то при решении оптимизационных задач.