[Из песочницы] Оптимизация DataTable по памяти29.05.2015 12:33

Думаю, многим хорошо знаком класс DataTable. Вычитывая из БД на клиент большие таблицы через ADO.NET, иногда приходится продлевать время жизни экземпляров этого класса на продолжительное время. Например, если нужна обработка и анализ полученных данных, не прибегая к ORM материализации. Когда объём данных невелик, то особой проблемы с этим не возникает. Однако на широких таблицах с большим числом строк можно получить довольно толстые объекты в памяти. Сопоставив объём данных, приходящих из БД, и размер получаемого DataTable, можно прийти к двум выводам: При больших объёмах varchar данных, среди которых есть дублирование, можно попробовать организовать некое подобие интернирования строковых данных внутри DataTable; DataTable содержит довольно увесистую внутреннюю инфраструктуру. Манипулируя с типами данных и числом строк в таблице, удалось установить, что процент накладных расходов составляет 15–20% для таблиц от 100 тыс. записей. Большая часть инфраструктуры обеспечивает корректное редактирование и прочий функционал таблицы. В случае, когда вам требуется, чтобы DataTable был простым контейнером для данных, полученных из БД, то можно написать лёгкий выпотрошенный аналог этого класса. Вопрос замены DataTable на внутреннюю структуру рассмотрим в следующей статье, если будет интересно. А сейчас рассмотрим первый пункт. Как известно, интернирование строк заключается в устранении дубликатов string в памяти (подробнее можно почитать тут). Использовать встроенный механизм интернирования мы не будем, чтобы строки не висели в памяти процесса после того, как они перестанут быть нам нужны.Идея состоит в том, чтобы обойти все varchar-колонки в таблице, и в каждой колонке все дубликаты заменить на ссылку из временного словаря, в котором строки будут лежать в единственном экземпляре. Состояние кучи до и после будут такими:

Стоит отметить, что данные в DataTable хранятся в колонках, а не в строках, как можно было бы предположить. Это обусловлено меньшими затратами по памяти — т.к. в колонках все значения одного типа, и можно использовать для хранения обычные массивы с постоянным временем доступа по индексу. Для скорости, будем читать напрямую из этих массивов через отражение (FieldInfo).

// Приватные поля, используемые для оптимизации потребления таблицей памяти и быстрого доступа к данным private static readonly FieldInfo StorageField = typeof (DataColumn).GetField (»_storage», BindingFlags.Instance | BindingFlags.NonPublic);

private static readonly FieldInfo ValuesField = typeof (DataTable).Assembly.GetType («System.Data.Common.StringStorage») .GetField («values», BindingFlags.Instance | BindingFlags.NonPublic); Как я упомянул выше, для хранения экземпляров строк в единственном экземпляре в памяти будем использовать Dictionary. var exclusiveStrings = new Dictionary(); Key нужен будет только для хэша, Value — для ссылки на единственный экземпляр в памяти. Стоит отметить, что возникающие коллизии Dictionary разруливает с помощью метода корзин.Полный код метода:

///

/// Оптимизация таблицы по использованию памяти. По сути делает интернирование строк в рамках таблицы. ///

/// Таблица. /// Ссылка на себя. public static DataTable Compact (this DataTable table) { if (table.Rows.Count == 0) return table;

var exclusiveStrings = new Dictionary(); for (int column = 0; column < table.Columns.Count; ++column) { if (table.Columns[column].DataType == typeof(string)) { // Прямой доступ к массиву (вертикальное хранилище) var values = (string[])ValuesField.GetValue(StorageField.GetValue(table.Columns[column])); int rowCount = table.Rows.Count; for (int row = 0; row < rowCount; ++row) { var value = values[row]; if (value != null) { string hashed; if (!exclusiveStrings.TryGetValue(value, out hashed)) // строка встречается впервые exclusiveStrings.Add(value, value); else // дубликат values[row] = hashed; } } exclusiveStrings.Clear(); } } return table; } Оценим сложность получившегося алгоритма для конкретной колонки. Сложность в данном случае складывается из двух основных частей: обход всех n значений и поиска в Dictionary по ключу. С первой частью всё понятно, а вот с поиском чуть интереснее. В самом фантастически плохом случае, когда все n значений приведут к коллизии и лягут в одну корзину, сложность поиска сведётся к линейной. Но, учитывая реализацию хэш-функции для строки в .NET, ничего кроме улыбки эта мысль вызвать не может. Так же решили и разработчики Dictionary, т.к. в документации для TryGetValue заявлена сложность O(1). Таким образом, в рамках одной колонки ожидаемая сложность сводится к O(n). Для всей таблицы – O(mn), где m – число строковых колонок.Рассмотрим скорость на реальных данных:

Как видно сложность линейная, как и следовало из анализа алгоритма. Касательно затрат памяти, то для алгоритма на каждом шагу, наполняя словарь, создаёт новый указатель и удаляет ссылки на строки, если находит дубликат.

Несложно заметить, что эффективность алгоритма зависит от входных данных: если дубликатов много, то и памяти освободится больше. В моих задачах память сокращалась на 30–50%. Но, повторюсь, у вас может быть иначе.

Надеюсь, кому-то это решение окажется таким же полезным, как и мне.

© Habrahabr.ru