.NET
C#
29 мая 2015

Оптимизация DataTable по памяти

Из песочницы
Думаю, многим хорошо знаком класс 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<string, string>();

Key нужен будет только для хэша, Value – для ссылки на единственный экземпляр в памяти. Стоит отметить, что возникающие коллизии Dictionary разруливает с помощью метода корзин.

Полный код метода:

        /// <summary>
        /// Оптимизация таблицы по использованию памяти. По сути делает интернирование строк в рамках таблицы.
        /// </summary>
        /// <param name="table">Таблица.</param>
        /// <returns>Ссылка на себя.</returns>
        public static DataTable Compact(this DataTable table)
        {
            if (table.Rows.Count == 0)
                return table;

            var exclusiveStrings = new Dictionary<string, string>();
            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%. Но, повторюсь, у вас может быть иначе.

Надеюсь, кому-то это решение окажется таким же полезным, как и мне.
+9
9k 41
Комментарии 12
Похожие публикации
Популярное за сутки