Думаю, многим хорошо знаком класс DataTable. Вычитывая из БД на клиент большие таблицы через ADO.NET, иногда приходится продлевать время жизни экземпляров этого класса на продолжительное время. Например, если нужна обработка и анализ полученных данных, не прибегая к ORM материализации (да, лучше бы это делать в БД, но далеко не всё порой удаётся туда вынести). Когда объём данных невелик, то особой проблемы с этим не возникает. Однако на широких таблицах с большим числом строк можно получить довольно толстые объекты в памяти. Сопоставив объём данных, приходящих из БД, и размер получаемого DataTable, можно прийти к двум выводам:
Вопрос замены DataTable на внутреннюю структуру рассмотрим в следующей статье, если будет интересно. А сейчас рассмотрим первый пункт. Как известно, интернирование строк заключается в устранении дубликатов string в памяти (подробнее можно почитать тут). Использовать встроенный механизм интернирования мы не будем, чтобы строки не висели в памяти процесса после того, как они перестанут быть нам нужны.
Идея состоит в том, чтобы обойти все varchar-колонки в таблице, и в каждой колонке все дубликаты заменить на ссылку из временного словаря, в котором строки будут лежать в единственном экземпляре. Состояние кучи до и после будут такими:
Стоит отметить, что данные в DataTable хранятся в колонках, а не в строках, как можно было бы предположить. Это обусловлено меньшими затратами по памяти – т.к. в колонках все значения одного типа, и можно использовать для хранения обычные массивы с постоянным временем доступа по индексу. Для скорости, будем читать напрямую из этих массивов через отражение (FieldInfo).
Как я упомянул выше, для хранения экземпляров строк в единственном экземпляре в памяти будем использовать Dictionary.
Key нужен будет только для хэша, Value – для ссылки на единственный экземпляр в памяти. Стоит отметить, что возникающие коллизии Dictionary разруливает с помощью метода корзин.
Полный код метода:
Оценим сложность получившегося алгоритма для конкретной колонки. Сложность в данном случае складывается из двух основных частей: обход всех n значений и поиска в Dictionary по ключу. С первой частью всё понятно, а вот с поиском чуть интереснее. В самом фантастически плохом случае, когда все n значений приведут к коллизии и лягут в одну корзину, сложность поиска сведётся к линейной. Но, учитывая реализацию хэш-функции для строки в .NET, ничего кроме улыбки эта мысль вызвать не может. Так же решили и разработчики Dictionary, т.к. в документации для TryGetValue заявлена сложность O(1). Таким образом, в рамках одной колонки ожидаемая сложность сводится к O(n). Для всей таблицы – O(mn), где m – число строковых колонок.
Рассмотрим скорость на реальных данных:
Как видно сложность линейная, как и следовало из анализа алгоритма. Касательно затрат памяти, то для алгоритма на каждом шагу, наполняя словарь, создаёт новый указатель и удаляет ссылки на строки, если находит дубликат.
Несложно заметить, что эффективность алгоритма зависит от входных данных: если дубликатов много, то и памяти освободится больше. В моих задачах память сокращалась на 30-50%. Но, повторюсь, у вас может быть иначе.
Надеюсь, кому-то это решение окажется таким же полезным, как и мне.
- При больших объёмах 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%. Но, повторюсь, у вас может быть иначе.
Надеюсь, кому-то это решение окажется таким же полезным, как и мне.