вторник, 10 мая 2016 г.

Конкатенация строк в .NET

Строки

Ходит распространённое заблуждение о том, что конкатенация строк в .NET с использованием оператора + менее предпочтительна, чем использование класса StringBuilder. Обычно это аргументируется тем, что класс string является immutable-классом и конкатенация строк влечёт создание нового экземпляра с выделением памяти, копированием и прочими свистоплясками. StringBuilder же в свою очередь выделяет память с лихвой изначально (свойство Capacity), при необходимости выделяя память под новый массив большего размера и копируя себя туда. В общем случае всё так, "но есть ньюансы".
Однако, давайте разберёмся так ли прост оператор конкатенации?

String.Concat

Начнём с того, что если вы посмотрите исходники FCL, то не найдёте оператора + в классе String. Строго говоря, из операторов там определены всего два: == и !=. Функционал оператора + обеспечивает сам механизм CLR, заменяя его на вызов статического метода String.Concat (за исключением, когда оба аргумента являются строковыми литералами, тогда конкатенация происходит при компиляции).
Т.е., например, все три определённых оператора + в спецификации языка C#:

string operator + (string x, string y)
string operator + (string x, object y)
string operator + (object x, string y)

 реально разворачиваются в вызов одного из перегруженных методов Concat:

public static String Concat(String str0, String str1)
public static String Concat(String str0, String str1, String str2)
public static String Concat(String str0, String str1, String str2, String str3)
public static String Concat(params String[] values)
public static String Concat(IEnumerable<String> values)

public static String Concat(Object arg0)
public static String Concat(Object arg0, Object arg1)
public static String Concat(Object arg0, Object arg1, Object arg2)
public static String Concat(Object arg0, Object arg1, Object arg2, Object arg3, __arglist) 

public static String Concat<T>(IEnumerable<T> values)

Обилие перегрузок в данном случае и несёт основную ценность. Если опять же заглянуть в реализацию, то мы увидим следующий код:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
        public static String Concat(String str0, String str1, String str2) {
            Contract.Ensures(Contract.Result<String>() != null);
            Contract.Ensures(Contract.Result<String>().Length ==
                (str0 == null ? 0 : str0.Length) +
                (str1 == null ? 0 : str1.Length) +
                (str2 == null ? 0 : str2.Length));
            Contract.EndContractBlock();
 
            if (str0==null && str1==null && str2==null) {
                return String.Empty;
            }
 
            if (str0==null) {
                str0 = String.Empty;
            }
 
            if (str1==null) {
                str1 = String.Empty;
            }
 
            if (str2 == null) {
                str2 = String.Empty;
            }
 
            int totalLength = str0.Length + str1.Length + str2.Length;
 
            String result = FastAllocateString(totalLength);
            FillStringChecked(result, 0, str0);
            FillStringChecked(result, str0.Length, str1);
            FillStringChecked(result, str0.Length + str1.Length, str2);
 
            return result;
        }

Самой интересной в данном случае является 25ая строка (выделил отдельно в коде). В ней происходит вычисление длины финальной строки, получаемой после сложения сразу всех аргументов. Это значит, что выражение a + b + c + d + e + f повлечёт за собой лишь одно выделение памяти, а не 5, как можно было подумать. Основным (и единственным) преимуществом метода Concat является, то, что CLR знает про контекст выполнения "чуть" больше, чем метод StringBuilder.Append и способен самостоятельно выбрать подходящую перегрузку метода Concat, который обработает все аргументы разом.

StringBuilder.Append

В отличие от String.Concat, вызов данного метода всегда производится пользователем явно. Поэтому цепочка вызовов:

1
2
3
4
5
var sb = new StringBuilder();
sb.Append(a);
sb.Append(b);
sb.Append(c);
string result = sb.ToString();

теоретически может привести к многократному выделению памяти (зависит от capcity и размеров конкретных строк a, b и c).

Заключение

Таким образом, использование явной конкатенации в условии отсутствия цикла и при разумном числе аргументов вполне оправдано. А если учесть, что использование StringBuilder сделает код намного менее читабельным, то выбор оператора + в данном случае будет предпочтителен.
Во всех остальных случаях (при сложных ветвлениях и циклах) выбор в пользу StringBuilder будет вполне очевиден.

понедельник, 9 мая 2016 г.

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

Думаю, многим хорошо знаком класс DataTable. Вычитывая из БД на клиент большие таблицы через ADO.NET, иногда приходится продлевать время жизни экземпляров этого класса на продолжительное время. Например, если нужна обработка и анализ полученных данных, не прибегая к ORM материализации (да, лучше бы это делать в БД, но далеко не всё порой удаётся туда вынести). Когда объём данных невелик, то особой проблемы с этим не возникает. Однако на широких таблицах с большим числом строк можно получить довольно толстые объекты в памяти. Сопоставив объём данных, приходящих из БД, и размер получаемого DataTable, можно прийти к двум выводам:

  • При больших объёмах varchar данных, среди которых есть дублирование, можно попробовать организовать некое подобие интернирования строковых данных внутри DataTable;
  • DataTable содержит довольно увесистую внутреннюю инфраструктуру. Манипулируя с типами данных и числом строк в таблице, удалось установить, что процент накладных расходов составляет 15-20% для таблиц от 100 тыс. записей. Большая часть инфраструктуры обеспечивает корректное редактирование и прочий функционал таблицы. В случае, когда вам требуется, чтобы DataTable был простым контейнером для данных, полученных из БД, то можно написать лёгкий выпотрошенный аналог этого класса.

Вопрос замены DataTable на внутреннюю структуру рассмотрим в следующей статье, если будет интересно. А сейчас рассмотрим первый пункт. Как известно, интернирование строк заключается в устранении дубликатов string в памяти (подробнее можно почитать тут). Использовать встроенный механизм интернирования мы не будем, чтобы строки не висели в памяти процесса после того, как они перестанут быть нам нужны.

Идея состоит в том, чтобы обойти все varchar-колонки в таблице, и в каждой колонке все дубликаты заменить на ссылку из временного словаря, в котором строки будут лежать в единственном экземпляре. Состояние кучи до и после будут такими:



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


1
2
3
4
5
6
7
        // Приватные поля, используемые для оптимизации потребления таблицей памяти и быстрого доступа к данным
        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 разруливает с помощью метода корзин.

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


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
        /// <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%. Но, повторюсь, у вас может быть иначе.

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

воскресенье, 8 мая 2016 г.

Entity Framework Code-Frist. Маппинг enum свойств в nvarchar

По умолчанию Entity Framework Code-First маппит enum свойства к sql колонкам типа integer. Мапинг в обе стороны проходит без проблем, и вообще всё работает отлично. Однако, может возникнуть необходимость изменить тип sql колонки на nvarchar. Стандартными средствами Code-First подход настраивать типы колонок не позволяет. Тем не менее можно провернуть следующие ухищрения.
Пусть у нас есть тип AuditRecord, который маппится в БД. В нём находится поле ActionType типа AuditActionType (enum). Таким образом, получаем следующее:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class AuditRecord
{
    [Required]
    [Column("ActionType")]
    [MaxLength(32)]
    public string ActionTypeString
    {
        get { return ActionType.ToString(); }
        private set { ActionType = EnumExtensions.ParseEnum<AuditActionType>(value); }
    }
 
    [NotMapped]
    public AuditActionType ActionType { get; set; }
}

Здесь я использовал extension-метод ParseEnum, который выглядит следующим образом:

1
2
3
4
5
6
7
public class EnumExtensions
{
    public static T ParseEnum<T>(String text)
    {
        return (T)Enum.Parse(typeof(T), text, true);
    }
}
Сеттер свойства ActionTypeString сделан приватным, чтобы предотвратить присвоения произвольных строк извне.
Основные минусы такого подхода:
  1. Работа со строковыми полями на больших объёмах данных в общем случае в БД медленнее, чем с integer.
  2. При фильтрации сущностей по данному полю для получения эффективного запроса в БД необходимо писать подобную лапшу:

context.AuditRecords.Where(ar => ar.ActionTypeString == AuditActionType.SomeAction.ToString());
Последнюю проблему можно решить изоляцией логики фильтрации на уровне репозиториев, чтобы знания об особенностях реализации не расползались за уровень DAL.