C#*, .NET*

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

из песочницы
Dentty 29 мая 2015 в 10:46 8,9k
Думаю, многим хорошо знаком класс 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
Сохранить: