- При больших объёмах 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%. Но, повторюсь, у вас может быть иначе.
Надеюсь, кому-то это решение окажется таким же полезным, как и мне.
Комментарии (12)
perfectdaemon
29.05.2015 10:56exclusiveStrings.Add(value, value);
Здесь нет ошибки? Может hashed, value?
И я что-то совсем не понимаю, каким образом восстановить данные, ведь exclusiveStrings будет уничтожен после выхода из метода.perfectdaemon
29.05.2015 11:00Пятница все-таки сказывается, не сразу понял суть вашего решения.
Отвечу сам себе — ошибки нет и данные будут корректны
Dentty Автор
29.05.2015 11:03В словарь кладётся один и тот же объект в качестве ключа и в качестве значения. По ключу словарь считает хэш и хранит дальше его. В Value оседает ссылка на экземпляр из кучи. Когда данная строка встречается нам вновь, то словарь найдёт её и вернёт ссылку на уже существующий в куче объект. Эту ссылку мы и присвоем вместо дубликата. Dictionary тут исключительно для линейной скорости поиска.
exclusiveStrings будет уничтожен — вы правы, но экземляру строк будут жить в памяти, т.к. таблица будет держать на них ссылки.
lair
29.05.2015 14:22В словарь кладётся один и тот же объект в качестве ключа и в качестве значения.
Чем вам хэшсет-то не угодил?Dentty Автор
29.05.2015 15:50+1Используя хэшсет, вы не сможете получить по дубликату ссылку на тот элемент, который уже лежит в хэшсете. Есть Contains, который может просто проверить есть ли уже такой элемент в контейнере. Т.е. в случае дубликата, он вам просто скажет, что есть и всё. Что в принципе логично, потмоу что HashSet — это множество, а не хэш-таблица в чистом виде.
a_mastrakov
29.05.2015 12:48Вы по сути сделали нормализацию своей таблицы на стороне клиента, это слегка попахивает костылем. Не проще ли было, сделать это на стороне базы, и просто прочитать две таблицы?
Dentty Автор
29.05.2015 12:56Никто не говорит, что именно так в БД данные и лежат. Как правило, много дубликатов приходит в результате выполнения вьюх (которые джойнят несколько таблиц). Да и заниматься блужданием по FK на стороне клиента — то ещё развлечение.
olen
29.05.2015 14:30А не проще ли использовать EF с обычными объектами для entity?
В свое время (еще до появления EF) я использовал ADO.NET в одном проекте. В целом все было нормально, но для особо сложной бизнес логики содавали объекты, наполняя их с помощью DataReader. Работать с такими объектами было на порядок удобнее, чем с табличными данными. Так что я не понимаю, зачем сейчас извращаться.Dentty Автор
29.05.2015 16:06DataTable, при всей своей избыточности в задачах с readonly-данными, довольно эффективно хранит данные поколоночно (особенно если много value-типов). И если выкинуть с него всю мишуру (о чём я напишу в следующей статье), то получится довольно эффективная структура. Т.е. фактически переписать с нуля, взяв за основу поколоночное хранение. Будет ничем не хуже DTO. По удобству использования, если нужен только произвольный доступ по индексам и именам колонок — самое оно, при минимуме накладных расходов.
То, про что пишете вы, несомненно хорошо, но для другого типа задач, когда DTO переходит в доменные объекты. У нас же была несколько иная задача — к таблице применяются различные формулы и скриптованые действия, которые пока не удалось полностью перенести в БД.
Возвращаясь к статье, подобный подход может помочь не только для DataTable, но и в других задачах — например, XML.
Rupper
Мы намаялись с этим классом так, что в итоге написали свою версию.
У DataTable кроме того, что он невероятно тяжеловесный в памяти, еще и при сериализации распухает невероятно. Время сериализации-десериализации ужасное. Для целей получить табличку-пробежать по строчкам (что и должно происходить при наличии БД) этой ИМХО лучший вариант. Если задачи еще какие-то, то может подумать о БД? Там все равно работа с большими таблицами лучше организована чем в DataTable.
Dentty Автор
Согласен, по возможности, всё нужно выносить в БД. Но в моём случае к таблице применяются различные формулы и скриптованые действия, что пока не удалось полностью перенести в БД. Естественно мы стараемся по минимуму выкачивать данных на клиент, но бывают прецеденты…