StringBuilder прошлое и настоящее

    Вступление


    Моя прошлая статья была посвящена особенностям строкового типа данных String в .NET. Эта статья продолжает традицию, однако на этот раз мы рассмотрим класс StringBuilder.

    Как известно, строки в .NET являются неизменяемыми (не используя unsafe), а поэтому проводить с ними операцию конкатенации в больших количествах не самая лучшая идея. Это значит, что следующий код имеет весьма серьезные проблемы с нагрузкой на память:

    string s = string.Empty;
    for (int i = 0; i < 100; i++)
     {
        s += "T";
     }
    

    Что же плохого в этом коде? А то, что на каждой итерации создается строка длиною на единицу больше чем на предыдущем шаге с последующим копированием символов из старой строки. Таким образом, суммарное количество задействованных символов равно:


    Данная формула есть не что иное, как сумма арифметической прогрессии:

    То есть такой сценарий конкатенации требует памяти пропорционально O(n2), n — длина строки.

    Для устранения проблем в подобном коде мы используем класс StringBuilder, зная, что операции с ним не приводят к таким растратам памяти как со String. Фактически StringBuilder представляет собой изменяемую строку.

    var strB = new StringBuilder();
    for (int i = 0; i < 100; i++)
    {
      strB.Append("T");
    }
    string str = strB.ToString();
    

    Такой код хоть и не лишен всех недостатков и тратит некоторую память на ветер, но делает это более сдержанно, по сравнению с предыдущим кодом.

    Реализация класса StringBuilder кардинально изменилась в .NET 4.0 по сравнению с предыдущими версиями, а потому я думаю, будет интересно написать, что же с ним случилось.

    StringBuilder в .NET 2.0


    Класс StringBuilder в .NET 2.0 имеет следующие поля:

    public sealed class StringBuilder : ISerializable
    {
        internal const int DefaultCapacity = 16;
        private const string CapacityField = "Capacity";
        private const string MaxCapacityField = "m_MaxCapacity";
        private const string StringValueField = "m_StringValue";
        private const string ThreadIDField = "m_currentThread";
        internal IntPtr m_currentThread;
        internal int m_MaxCapacity;
        internal volatile string m_StringValue; <-------------------------------------
    }
    

    m_currentThread — идентификатор потока, в котором создавался экземпляр объекта;
    m_MaxCapacity — максимальная емкость данного экземпляра;
    m_StringValue — строка, содержащая символы.

    Фактически класс StringBuilder внутри работает со строковым типом данных String. Поскольку строки со стороны mscorlib.dll являются изменяемыми, то StringBuilder-у ничего не стоит изменить строку, находящуюся в m_StringValue.

    Первоначальная длина составляет 16 символов, а при нехватке места для добавления новых символов StringBuilder заменяет внутреннюю строку на строку длиною в два раза больше и копирует во вновь созданную все символы из предыдущей + новые. Удвоение длины строки приводит к линейной сложности (O(n)) по памяти, в отличие от квадратичной, которая присуща обычным строкам.

    Важным дополнением к увеличению производительности является задание нужной емкости при создании экземпляра класса StringBuilder. Тем самым нам не требуется очередное удвоение размера и копирование данных при нехватке памяти. Однако, это возможно лишь в том случае, если мы заранее знаем размер получаемой строки.

    Рассмотрим реализации наиболее часто используемых методов. Для читаемости кода я убрал условия проверки входных параметров.

    Метод Append()

    Исходный код
      public StringBuilder Append(string value)
        {
          if (value == null)
            return this;
          string currentString = this.m_StringValue;
          IntPtr currentThread = Thread.InternalGetCurrentThread();
          if (this.m_currentThread != currentThread)
            currentString = string.GetStringForStringBuilder(currentString, currentString.Capacity);
          int length = currentString.Length;
          int requiredLength = length + value.Length;
          if (this.NeedsAllocation(currentString, requiredLength)) //проверка хватает ли места для добавления символов
          {
    	     //создаем строку длиною в 2 раза больше и копируем все символы из старой строки
             string newString = this.GetNewString(currentString, requiredLength); 
    	     newString.AppendInPlace(value, length);     
             this.ReplaceString(currentThread, newString);  //заменяем старую строку новой
          }
          else
          {
            currentString.AppendInPlace(value, length); 
    	    this.ReplaceString(currentThread, currentString); 
          }
        return this;
       }   
    


    Данный метод просто проверяет, хватает ли места в текущем экземпляре для добавления новой строки, если да, то просто происходит копирование на месте в незанятую часть строки, иначе удвоение размера и копирование старой и новой строки.

    Метод Insert()

    Исходный код
      public StringBuilder Insert(int index, string value)
        {
          if (value == null)
            return this.Insert(index, value, 0);
          else
            return this.Insert(index, value, 1);
        }
      public StringBuilder Insert(int index, string value, int count)
        {
          IntPtr tid;
          string threadSafeString = this.GetThreadSafeString(out tid);
          int length = threadSafeString.Length;
          if (value != null && value.Length != 0)
          {
            if (count != 0)
            {
              int requiredLength;
              try
              {    
                requiredLength = checked (length + value.Length * count);//вычисляем длину новой строки
              }
              catch (OverflowException ex)
              {
                throw new OutOfMemoryException();
              }   
              if (this.NeedsAllocation(threadSafeString, requiredLength))//проверка хватает ли места для добавления символов
              {
    		    //создаем строку длиною в 2 раза больше и копируем все символы из старой строки
                string newString = this.GetNewString(threadSafeString, requiredLength);	  
                newString.InsertInPlace(index, value, count, length, requiredLength);//вставляем новые символы
                this.ReplaceString(tid, newString);//заменяем старую строку новой
              }
              else
              {
                threadSafeString.InsertInPlace(index, value, count, length, requiredLength);
                this.ReplaceString(tid, threadSafeString);
              }
              return this;
            }
          }
          return this;
        }
    


    Данный метод аналогично предыдущему проверяет, хватает ли места в текущем экземпляре для вставки новой строки и в зависимости от этого удваивает размер строки или же вставляет на месте в исходную строку без изменения размера.

    Метод Remove()

    Исходный код
    public StringBuilder Remove(int startIndex, int length)
        {
          IntPtr tid;
          string threadSafeString = this.GetThreadSafeString(out tid);
          int length1 = threadSafeString.Length; 
          //удаляем ненужные символы, сдвигая оставшуюся часть строки влево
          threadSafeString.RemoveInPlace(startIndex, length, length1);
          this.ReplaceString(tid, threadSafeString);//заменяем старую строку новой
          return this;
        }
    


    Данный метод удаляет ненужные символы, сдвигая оставшуюся часть строки влево. При удалении последнего символа фактически ничего сдвигать не надо, поэтому удаление с конца происходит намного быстрее, чем из любой другой части строки.

    Метод ToString()

    Исходный код
    public override string ToString()
        {
          string str = this.m_StringValue;
          if (this.m_currentThread != Thread.InternalGetCurrentThread() || 2 * str.Length < str.ArrayLength) 
            return string.InternalCopy(str);//возвращаем копию строки
          str.ClearPostNullChar();
          this.m_currentThread = IntPtr.Zero; 	
          return str; //возвращаем ссылку на текущую строку
        }
    


    Данный метод, как видно из реализации, возвращает либо копию строки, либо строку, которой оперирует. Как правило, первый вызов данного метода возвращает ссылку на исходную строку, поэтому выполняется очень быстро, однако каждый последующий вызов приводит к копированию строки. Класс StringBuilder в .NET 2.0 делает упор именно на быстроту работы этого метода.

    В общем, класс StringBuilder в .NET 2.0 реализован достаточно просто. Он использует изменяемую строку, а при нехватке места создает новую строку, длина которой в два раза больше предыдущей. Такой сценарий удвоения длины приводит к линейной сложности по памяти, что на порядок лучше квадратичной. Однако, при больших длинах строк и это не эффективно. Кстати, из-за своего большего размера, строка часто может располагаться в куче для больших объектов(LOH), что так же ни есть хорошо.

    StringBuilder в .NET 4.0


    Как я уже сказал, в .NET 4.0 реализация класса StringBuilder поменялась. Теперь для хранения символов вместо String используется Char[], а сам класс представляет собой связный список StringBuilder-ов подобно RopeString.

    Причина такого изменения достаточно очевидна: при такой реализации не требуется перевыделять память при ее нехватке, что присуще предыдущей реализации. Это так же означает, что метод ToString() работает немного медленнее, поскольку окончательную строку необходимо сначала сформировать, а метод Append() работает быстрее, поскольку не требует копирования. Однако это вписывается в типичный сценарий использования для StringBuilder: много вызовов Append(), а затем один вызов ToString().

    Класс StringBuilder в .NET 4.0 имеет следующие поля:

    public sealed class StringBuilder : ISerializable
      {
        internal const int DefaultCapacity = 16;
        internal const int MaxChunkSize = 8000;
        internal char[] m_ChunkChars; <-------------------------------------
        internal StringBuilder m_ChunkPrevious; <-------------------------------------
        internal int m_ChunkLength;
        internal int m_ChunkOffset;
        internal int m_MaxCapacity;
        private const string CapacityField = "Capacity";
        private const string MaxCapacityField = "m_MaxCapacity";
        private const string StringValueField = "m_StringValue";
        private const string ThreadIDField = "m_currentThread";
      }
    

    m_ChunkChars — массив содержащий символы текущего элемента связного списка (кусочка строки);
    m_ChunkPrevious — ссылка на предыдущий элемент (StringBuilder) в списке;
    m_ChunkLength — реальная длина текущего элемента списка (количество используемых символов);
    m_ChunkOffset — суммарное количество используемых строкой символов (логическая длина);
    m_MaxCapacity — максимальная емкость текущего экземпляра StringBuilder.

    В .NET Framework 4 и .NET Framework 4.5 при создании экземпляра объекта StringBuilder путем вызова конструктора StringBuilder(Int32, Int32) и длина и емкость экземпляра StringBuilder может увеличиваться за значением его свойства MaxCapacity. Это может произойти в частности, при вызове методов Append и AppendFormat.

    Максимальная длина элемента списка MaxChunkSize равна 8000. Как вы понимаете это сделано не просто так. Вот комментарий разработчиков класса:

    We want to keep chunk arrays out of large object heap (< 85K bytes ~ 40K chars) to be sure. Making the maximum chunk size big means less allocation code called, but also more waste in unused characters and slower inserts / replaces.

    Мы хотим, чтобы массив символов не попадал в кучу для больших объектов. Делая максимальный размер элемента списка (кусочка) большим, значило бы, что нужно меньше аллокации памяти, но больше символов остаются не используемыми и операции insert / replace выполняются медленнее.


    Рассмотрим реализации наиболее часто используемых методов.

    Метод Append()

    Исходный код
    public unsafe StringBuilder Append(string value)
        {
          if (value != null)
          {
            char[] chArray = this.m_ChunkChars;
            int index = this.m_ChunkLength;
            int length = value.Length;
            int num = index + length;
            if (num < chArray.Length)// Если хватает места в текущем экземпляре для вставки новой строки
            {
              if (length <= 2)
              {
                if (length > 0)
                  chArray[index] = value[0];
                if (length > 1)
                  chArray[index + 1] = value[1];
              }
              else
              {
                fixed (char* smem = value)
                  fixed (char* dmem = &chArray[index])
                    string.wstrcpy(dmem, smem, length);
              }
              this.m_ChunkLength = num;
            }
            else
              this.AppendHelper(value);
          }
          return this;
        }
       private unsafe void AppendHelper(string value)
        {
          fixed (char* chPtr = value)
            this.Append(chPtr, value.Length);
        }
    
    
    internal unsafe StringBuilder Append(char* value, int valueCount)
        {
          // Оптимизация
          int num1 = valueCount + this.m_ChunkLength;
          if (num1 <= this.m_ChunkChars.Length)
          {
            StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, valueCount);
            this.m_ChunkLength = num1;
          }
          else
          {
     	// Копируем первую часть(кусочек)
            int count = this.m_ChunkChars.Length - this.m_ChunkLength;
            if (count > 0)
            {
              StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, count);
              this.m_ChunkLength = this.m_ChunkChars.Length;
            }
    	    // Увеличиваем билдер, добавляя еще один кусочек
            int num2 = valueCount - count;
            this.ExpandByABlock(num2);
    	    // Копируем вторую часть (кусочек)
            StringBuilder.ThreadSafeCopy(value + count, this.m_ChunkChars, 0, num2);
            this.m_ChunkLength = num2;
          }
          return this;
        }
    


    Метод Append() работает следующим образом: если в текущем элементе списка хватает символов для вставки новой строки, то происходит копирование в нее, если же нет, то копируется та часть которая помещается, а для того, что не поместилось, создается новый элемент списка (экземпляр StringBuilder-a), у которого длина массива равна длине всей исходной строки либо длине оставшейся строки в зависимости от того что больше. Однако, как было сказано, выше максимальная длина массива составляет 8000.

    В общем, формула для вычисления длины нового элемента списка выглядит так:

    int length = Math.Max(minBlockCharCount, Math.Min(this.Length, 8000))
    

    где minBlockCharCount — оставшаяся длина строки после копирования ее части которая помещается в текущий экземпляр.

    Таким образом, в результате работы такого кода

    StringBuilder s = new StringBuilder ();
    for (int i = 0; i < 10000; i++) {
      s.Append ("T");
    }
    

    длины массивов у элементов списка будут равны: 8000, 4092, 2048, 1024, 512, 256, 128, 64, 32, 16, 16.

    При таких длинах массивов операция обращения к определенному символу в исходной строке выполняется достаточно быстро практически за O(1), так как элементов списка не так много.

    Метод Insert()

    Исходный код
    public unsafe StringBuilder Insert(int index, string value)
        {
          if (value != null)
          {
            fixed (char* chPtr = value)
              this.Insert(index, chPtr, value.Length);
          }
          return this;
        }
    private unsafe void Insert(int index, char* value, int valueCount)
        {
          if (valueCount <= 0)
            return;
          StringBuilder chunk;
          int indexInChunk;
          //Вставляет символы в строку при необходимости создавая новый элемент списка (StringBuilder)
          this.MakeRoom(index, valueCount, out chunk, out indexInChunk, false);
          this.ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, value, valueCount);
        }
    


    Метод Insert() работает следующим образом: если в текущем элементе списка(StringBuilder-е) хватает места для вставки, то имеющиеся символы сдвигаются, чтобы дать место новому тексту. Иначе же создается новый элемент списка (StringBuilder), в который копируется часть символов из предыдущего элемента, которые не поместились. Последующие символы не смещаются влево.

    Что будет в результате такого кода?

    StringBuilder s = new StringBuilder ();
    for (int i = 0; i < 10000; i++) {
      s.Insert (0, "T");
    }
    

    Результат будет отличаться от кода использующего Append(), причем весьма серьезно!

    Мы получим очень большой список StringBuilder-ов каждый элемент, которого будет иметь длину 16 символов. В результате чего операция обращения к определенному символу по индексу будет выполняться медленней, чем ожидалось, а именно пропорционально длине списка, то есть O(n).

    Метод Remove()

    Исходный код
    public StringBuilder Remove(int startIndex, int length)
        {
          if (this.Length == length && startIndex == 0)
          {
    	    // Оптимизация. Если мы удаляем всю строку.
            this.Length = 0;
            return this;
          }
          else
          {
            if (length > 0)
            {
              StringBuilder chunk;
              int indexInChunk;
              this.Remove(startIndex, length, out chunk, out indexInChunk);
            }
            return this;
          }
        }
    private void Remove(int startIndex, int count, out StringBuilder chunk, out int indexInChunk)
        {
          int num = startIndex + count;
    	  //Находим элементы списка(кусочки) в которых находятся начальный и конечный символ для удаления.
          chunk = this;
          StringBuilder stringBuilder = (StringBuilder) null;
          int sourceIndex = 0;
          while (true)
          {
            if (num - chunk.m_ChunkOffset >= 0)
            {
              if (stringBuilder == null)
              {
                stringBuilder = chunk;
                sourceIndex = num - stringBuilder.m_ChunkOffset;
              }
              if (startIndex - chunk.m_ChunkOffset >= 0)
                break;
            }
            else
              chunk.m_ChunkOffset -= count;
            chunk = chunk.m_ChunkPrevious;
          }
          indexInChunk = startIndex - chunk.m_ChunkOffset;
          int destinationIndex = indexInChunk;
          int count1 = stringBuilder.m_ChunkLength - sourceIndex;
          //Если начальный и конечный кусочки не равны 
         if (stringBuilder != chunk)
          {
            destinationIndex = 0;
    	    // Удаляем символы после startIndex до конца начального элемента списка(кусочка)  
            chunk.m_ChunkLength = indexInChunk;
    	    // Удаляем символы между начальным и конечным кусочком.
            stringBuilder.m_ChunkPrevious = chunk;
            stringBuilder.m_ChunkOffset = chunk.m_ChunkOffset + chunk.m_ChunkLength;
    	    // Если стартовый индекс для удаления ноль в начальном кусочке то мы можем выкинуть весь элемент списка(кусочек)      
          if (indexInChunk == 0)
            {
              stringBuilder.m_ChunkPrevious = chunk.m_ChunkPrevious;
              chunk = stringBuilder;
            }
          }
          stringBuilder.m_ChunkLength -= sourceIndex - destinationIndex;
          if (destinationIndex == sourceIndex)  // Иногда не требуется перемещения
            return;
    	// Удаляем символы в конечном кусочке перемещая оставшиеся символы влево
          StringBuilder.ThreadSafeCopy(stringBuilder.m_ChunkChars, sourceIndex, stringBuilder.m_ChunkChars, destinationIndex, count1);
        }
    


    Реализация данного метода существенно усложнилась. Однако надо учесть, что предыдущая реализация копировала большое количество символов, смещая их влево. Здесь же необходимо производить смещение только в пределах одного элемента (StringBuilder-а) в списке.

    Метод ToString()

    Исходный код
    public override unsafe string ToString()
        {
          if (this.Length == 0)
            return string.Empty;
          string str = string.FastAllocateString(this.Length);
          StringBuilder stringBuilder = this;
          fixed (char* chPtr = str)
          {
            do
            {
              if (stringBuilder.m_ChunkLength > 0)
              {
                char[] chArray = stringBuilder.m_ChunkChars;
                int num = stringBuilder.m_ChunkOffset;
                int charCount = stringBuilder.m_ChunkLength;
                fixed (char* smem = chArray)
                  string.wstrcpy(chPtr + num, smem, charCount);
              }
              stringBuilder = stringBuilder.m_ChunkPrevious;
            }
            while (stringBuilder != null);
          }
          return str;
        }
    


    Данный метод проходит по всему связному списку StringBuilder-ов и последовательно копирует символы каждого из элементов списка в результирующую строку.

    Сравнение производительности


    Пожалуй, самая интересная часть — это сравнение производительности между двумя версиями класса.

    Тест 1. Сколько требуется памяти для хранения строки заданной длины.



    Как видите, при небольшой длине строки новая реализация проигрывает старой. Оно и понятно, ведь для каждого элемента списка(StringBuilder) требуется информация о длине, емкости, смещении от начала строки + для массива символов overhead. Но как только длина строки становится больше 16384, старая реализация начинает проигрывать (из-за удвоения размера строки, она содержит много неиспользуемых символов).

    Тест 2. Метод Append()



    Пожалуй, это тот самый метод, в котором новая реализация побеждает. Поскольку при нехватке памяти теперь удваивать длину строки и копировать в нее символы не требуется, то данный метод выполняется значительно быстрее, почти в два раза (точнее в 1,8 раз).

    Тест 3. Метод Insert()

    Будем производить вставку в строку уже заполненную символами, длиною 1000 символов.

    1. Вставка в начало строки



    2. Вставка в середину строки



    3. Вставка в конец строки



    Комментарии излишне — новая реализация проигрывает при вставке в любое место.

    Тест 4. Метод Remove()

    Будем производить удаление 10 символов из строки уже заполненной символами до тех пор, пока не исчерпаем ее.



    Новая реализация выигрывает при удалении почти из любого места, так как теперь не требуется смещать символы оставшейся строки влево (точнее требуется, но не так часто и много как раньше).

    Тест 5. Метод ToString()

    Как было сказано выше, данный метод проигрывает предыдущей реализации. Предыдущая реализация возвращала просто ссылку на строку, которой она оперировала (при первом вызове), а новая вынуждена собирать результирующую строку по кускам, обходя каждый элемент связного списка.



    Новая реализация работает заметно медленнее, если строка формировалась с помощью метода Insert(), поскольку список будет состоять из множества элементов(StringBuilder-ов) длиною в 16 символов.

    Тест 6. Обращение по определенному индексу

    Учитывая, что теперь StringBuilder представляет собой связный список, операция обращения к строке по определенному индексу становится дорогостоящей. Особенно если он формировался с помощью метода Insert.



    Тест 7. Обычный сценарий: множество вызовов Append(), а затем вызов ToString()

    Как правило, мы работаем с данным классом по определенному сценарию: множественный вызов метода Append(), за которым следует один вызов ToString(). Реализации данного класса поменялась именно в расчете на данный сценарий.



    Вывод


    Как мы увидели, класс StringBuilder в .NET 2.0 был оптимизирован на быстроту работы метода ToString(), в то время как в .NET 4.0 на быстроту метода Append(). Новая реализация метода Append() работает почти в 2 раза быстрее, в то время как методы Insert() и ToString() работают медленнее. Но поскольку, мы работаем с данным классом по определенному сценарию: вызываем множественно раз метод Append(), за которым последует единственный вызов метода ToString(), то увеличение производительности имеет место.

    Учитывая новую реализацию класса, при которой лишь множественный вызов метода Append() приводит к увеличению производительности, класс теперь можно было бы назвать StringAppender *)
    Поделиться публикацией

    Похожие публикации

    Комментарии 32

      +13
      Спасибо за детальное исследование. Иногда полезно знать такие мелочи.
        +2
        Да, иногда полезно. На собеседованиях.

        Меня вот однажды спросили: а какое приведение типов работает быстрее: явное или через оператор as.
          +2
          Чую вопрос с подвохом. Само по себе приведение работает одинаково, а вот способы обработки ошибок, предлагаемые этими вариантами, различаются по скорости. Или нет?
            +2
            Тут есть подробный ответ.
              0
              Ответ крайне подробный, но экспериментально не подтверждается. Проверяю в LinqPad:
              void Main()
              {
              	var times = 100000000;
              	A a;
              	B b = new B();
              	DateTime st, res;
              	
              	st = DateTime.Now;
              	for(var idx = 0; idx < times; idx++)
              		a = (A)b;
              	res = DateTime.Now;
              	(res - st).TotalMilliseconds.Dump();
              	
              	st = DateTime.Now;
              	for(var idx = 0; idx < times; idx++)
              		a = b as A;
              	res = DateTime.Now;
              	(res - st).TotalMilliseconds.Dump();
              }
              
              class A { }
              class B : A { }
              

              Выдает 245 и 220 секунд соответствено. Но что любопытно — если поменять порядок проверок, результаты не изменятся! Из чего делаю вывод, что разница в 25 миллисекунд вызвана накладными расходами jit-компилятора, а не разницей в производительности подходов.
                0
                Интересно. Практически я не проверял, сегодня тоже попробую получить разницу во времени экспериментально.
                Я подозреваю, что тут пример немного не показательный: 1. каст в базовый класс, должно быть наоборот (так его скорее всего вообще оптимизатор вырежет), 2. классы пустые и с объектами ничего не делается. Хотя я вот попробовал сейчас по-другому, разницы во времени тоже не заметил. Надо будет покрутить ещё вечером.
                  +2
                  В-общем, практическая разница на самом деле есть. Пример: тык.
                  На моей машине (собирал в Release AnyCPU) выводит это
                  Warming up...
                  Testing...
                  (B)b  : 1507 ms
                  b as B: 1720 ms
                  (B)b  : 1506 ms
                  b as B: 1723 ms
                  (B)b  : 1506 ms
                  b as B: 1723 ms
                  (B)b  : 1508 ms
                  b as B: 1722 ms
                  (B)b  : 1507 ms
                  b as B: 1723 ms
                  (B)b  : 1528 ms
                  b as B: 1744 ms
                  (B)b  : 1520 ms
                  b as B: 1721 ms
                  (B)b  : 1516 ms
                  b as B: 1734 ms
                  (B)b  : 1526 ms
                  b as B: 1743 ms
                  (B)b  : 1515 ms
                  b as B: 1722 ms
                  ===== Total times =====
                  (B)b  : 15139 ms
                  b as B: 17275 ms
                  Done
                  
                    0
                    Зачем DateTime, если есть Stopwatch? Раз.
                    Два: сделав times константой, получишь повышение производительности по очевидным причинам.
                    Три: ты меряешь здесь ещё и предсказания выбора, чего делать не надо. В идеале, в тестируемом коде вообще не должно быть if'ов, если они — не часть алгоритма.

                    На моей машине в MSVS 2015 твой код (переписанный на Stopwatch)
                    Код
                    private static void Main()
                    {
                    	int times = 1000 * 1000 * 100;
                    	A a;
                    	B b = new B();
                    
                    	Stopwatch sw1 = new Stopwatch();
                    
                    	sw1.Start();
                    	for (int i = 0; i < times; i++)
                    	{
                    		a = (A)b;
                    	}
                    	sw1.Stop();
                    	Console.WriteLine(sw1.ElapsedTicks);
                    
                    	Stopwatch sw2 = new Stopwatch();
                    
                    	sw2.Start();
                    	for (int i = 0; i < times; i++)
                    	{
                    		a = b as A;
                    	}
                    	sw2.Stop();
                    	Console.WriteLine(sw2.ElapsedTicks);
                    }
                    
                    private class A
                    { }
                    
                    private class B : A
                    { }
                    


                    выдавал 735 187 и 738 557 тиков, мой же —
                    Код
                    private static void Main()
                    {
                    	const int times = 1000 * 1000 * 100 / 16;
                    	A a;
                    	B b = new B();
                    
                    	Stopwatch sw = new Stopwatch();
                    
                    	sw.Start();
                    	for (int i = 0; i < times; i++)
                    	{
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    		a = (A)b;
                    	}
                    	sw.Stop();
                    	Console.WriteLine(sw.ElapsedTicks);
                    
                    	Stopwatch sw2 = new Stopwatch();
                    
                    	sw2.Start();
                    	for (int i = 0; i < times; i++)
                    	{
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    		a = b as A;
                    	}
                    	sw2.Stop();
                    	Console.WriteLine(sw2.ElapsedTicks);
                    }
                    
                    private class A
                    { }
                    
                    private class B : A
                    { }
                    


                    отрабатывает за 118 109 и 117 323 тиков.
                      0

                      Ваша оптимизация впечатляет, однако на результаты теста это никак не повлияло — в любом случае оба варианта приведения типов работают одинаково быстро.

                        0
                        Более того, первый стал работать дольше)
                        В итоге, и правда всё равно.
                +2
                После прочтения Вашего комментария остаётся дивное ощущение — как после упоминания анекдота в компании, когда все сдержанно отсмеялись, и только ты один теряешься, ни разу этот анекдот не слышав.
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Заинтриговали.
                    Не томите, расскажите, в чём подвох (:
                      0
                      Эх… тяжкий вчера был день, даже некогда было сюда заглянуть, так что извиняюсь за столь поздний ответ.

                      Выше уже все ответили по существу. А на собеседовании я столько теорий выдвинул, рассуждая на эту тему. Это было самое запоминающее собеседование в моей жизни.

                      Если собеседующий не задается целью добиться именно правильного ответа, а хочет просто посмотреть как человек умеет рассуждать, то, в целом, это любопытный вопрос и показывает как человек может подходить к решению подобного рода задач.
                        0
                        А взяли?:)
                          0
                          Мы на финансовом вопросе не сошлись тогда ;)
                      0
                      В случае успешного приведения одинаково быстро.
                        0
                        **комментарий удален пользователем
                          0
                          Насколько я знаю, прямое приведение быстрее, потому что с помощью as Работает примерно так:
                          public T OperatorAs<T>(object source)
                          {
                             return source is T ? (T) source : null;
                          }
                          
                        +1
                        На моей памяти это уже 4ая статья про .net строки и SB на хабре :-)
                          +2
                          Не порядок! Версий .NET Framework уже явно больше 4! Надо больше статей про StringBuilder.
                          +2
                          >>> То есть такой сценарий конкатенации требует памяти пропорционально O(n2), n — длина строки.
                          Что-то не понятно как вы так посчитали… Проверьте, память линейна.
                            0
                            Я ведь указал, что полученная сумма есть сумма арифметической прогрессии.
                            (n2+n) / 2 = O(n2)
                              0
                              Ну так эти строки не используются одновременно. старые строки могут освобождаться. Так что если GC их освобождает, то потребление памяти будет линейно, в вот нагрузка на процессор будет квадратична.
                                0
                                Конечно старые строки будут освобождаться сборщиком мусора. Имелось виду, что на создание строки потребуется памяти пропорционально квадрату длины, а не то что она будет использовать столько памяти.
                                  0
                                  К чему все эти рассуждения можно же померить

                                  Исходный код
                                  public static void main(String[] args) {
                                  String s = "";
                                  measure(s, 1000);
                                  measure(s, 2000);
                                  measure(s, 3000);
                                  measure(s, 4000);
                                  measure(s, 5000);
                                  }

                                  private static String measure(String s, int n) {
                                  long t = System.currentTimeMillis();
                                  for(int i = 0; i <= n; i++ ) {
                                  s += «T»;
                                  }
                                  System.out.println(«N=» + n + " " + (System.currentTimeMillis() — t) + " ms");
                                  return s;
                                  }


                                  Результаты измерений для малых чисел показывают что скорость линейна
                                  N=1000 4 ms
                                  N=2000 10 ms
                                  N=3000 15 ms
                                  N=4000 21 ms
                                  N=5000 19 ms


                                  Результаты измерений для больших чисел
                                  N=10000 133 ms
                                  N=20000 297 ms
                                  N=30000 512 ms
                                  N=40000 911 ms
                                  N=50000 1552 ms


                                  Результаты измерений с GC logging
                                  [GC 16448K->176K(62848K), 0.0010550 secs]
                                  [GC 16622K->144K(79296K), 0.0006340 secs]
                                  [GC 33040K->176K(79296K), 0.0005890 secs]
                                  [GC 33072K->184K(112192K), 0.0005770 secs]
                                  [GC 65974K->179K(112192K), 0.0007630 secs]
                                  N=10000 122 ms
                                  [GC 65971K->168K(175552K), 0.0004370 secs]
                                  [GC 131752K->175K(175552K), 0.0008520 secs]
                                  [GC 131759K->164K(307136K), 0.0004220 secs]
                                  [GC 263332K->173K(307136K), 0.0007190 secs]
                                  N=20000 301 ms
                                  [GC 263341K->140K(392960K), 0.0003920 secs]
                                  [GC 349132K->167K(392960K), 0.0003900 secs]
                                  [GC 349159K->177K(376128K), 0.0004860 secs]
                                  [GC 332529K->185K(360512K), 0.0004810 secs]
                                  [GC 316729K->191K(345344K), 0.0004400 secs]
                                  [GC 301695K->197K(331072K), 0.0005320 secs]
                                  N=30000 530 ms
                                  [GC 287429K->160K(317440K), 0.0005690 secs]
                                  [GC 273824K->170K(304768K), 0.0007380 secs]
                                  [GC 260970K->178K(292352K), 0.0005290 secs]
                                  [GC 248754K->183K(280896K), 0.0004380 secs]
                                  [GC 237111K->188K(269696K), 0.0005000 secs]
                                  [GC 226044K->193K(259200K), 0.0005720 secs]
                                  [GC 215553K->197K(249216K), 0.0005790 secs]
                                  [GC 205573K->200K(239744K), 0.0004120 secs]
                                  [GC 196104K->203K(230720K), 0.0005490 secs]
                                  [GC 187083K->206K(222144K), 0.0004270 secs]
                                  [GC 178510K->208K(214016K), 0.0003710 secs]
                                  [GC 170354K->211K(206272K), 0.0004750 secs]
                                  [GC 162643K->213K(198912K), 0.0003800 secs]
                                  [GC 155285K->215K(191936K), 0.0005550 secs]
                                  [GC 148307K->217K(185280K), 0.0005060 secs]
                                  N=40000 949 ms
                                  [GC 141657K->151K(178944K), 0.0004260 secs]
                                  [GC 135319K->159K(172928K), 0.0006030 secs]
                                  [GC 129311K->165K(167360K), 0.0003990 secs]
                                  [GC 123621K->169K(198144K), 0.0006310 secs]
                                  [GC 154537K->174K(191360K), 0.0004140 secs]
                                  [GC 147630K->178K(184640K), 0.0004070 secs]
                                  [GC 141042K->181K(178432K), 0.0005010 secs]
                                  [GC 134773K->184K(212032K), 0.0005700 secs]
                                  [GC 168440K->188K(204480K), 0.0003480 secs]
                                  [GC 160828K->191K(197248K), 0.0005430 secs]
                                  [GC 153599K->194K(190336K), 0.0005200 secs]
                                  [GC 146690K->184K(183744K), 0.0004400 secs]
                                  [GC 140098K->259K(177600K), 0.0005770 secs]
                                  [GC 133963K->321K(171648K), 0.0003460 secs]
                                  [GC 128071K->323K(166016K), 0.0005310 secs]
                                  [GC 122459K->324K(160576K), 0.0003830 secs]
                                  [GC 117124K->391K(155584K), 0.0003710 secs]
                                  [GC 112111K->393K(180224K), 0.0005830 secs]
                                  [GC 136727K->395K(208896K), 0.0004890 secs]
                                  [GC 165403K->397K(243520K), 0.0006960 secs]
                                  [GC 200141K->472K(234368K), 0.0004700 secs]
                                  [GC 191000K->475K(225600K), 0.0003940 secs]
                                  [GC 182235K->477K(217280K), 0.0004250 secs]
                                  [GC 173917K->479K(209408K), 0.0003490 secs]
                                  [GC 165967K->481K(201920K), 0.0004630 secs]
                                  [GC 158495K->483K(194816K), 0.0004200 secs]
                                  [GC 151393K->485K(188032K), 0.0004890 secs]
                                  [GC 144620K->486K(181568K), 0.0005560 secs]
                                  [GC 138151K->488K(175424K), 0.0005800 secs]
                                  [GC 132009K->489K(169600K), 0.0005440 secs]
                                  [GC 126196K->490K(164096K), 0.0005160 secs]
                                  [GC 120722K->492K(158848K), 0.0004920 secs]
                                  [GC 115497K->493K(153856K), 0.0005540 secs]
                                  [GC 110452K->494K(149120K), 0.0003550 secs]
                                  N=50000 1571 ms


                                  Результаты измерений для огромных чисел для StringBuilder зависимость линейная
                                  N=10000000 218 ms
                                  N=20000000 402 ms
                                  N=30000000 628 ms
                                  N=40000000 877 ms
                                  N=50000000 1033 ms


                                  Так что делаем простой и однозначный вывод, скорость обоих алгоритмов линейна при наличии достаточной памяти!!! При нехватке памяти скорость алгоритма памяти падает в прямой зависимости от нехватки памяти! У String метода память действительно выделяется квадратично и освобождается (посчитать количество GC), у StringBuilder скорость линейна и при нехватки памяти, так как память выделяется маленькими кусочками.
                                +1
                                Да, там дело не в памяти, она вернется в кучу после конкатенации, а во времени на аллокации+копирование+релиз
                                +2
                                >>> Это значит, что следующий код имеет весьма серьезные проблемы с нагрузкой на память.

                                Большая проблема с производительностью — такой код работает за O(n^2). Кстати, можно вспомнить аналогичный пример из мира С:

                                for (i = 0; i < strlen(s); i++) {
                                    // process s[i]
                                }
                                
                                  +1
                                  Не знаю я никакой аналогии не вижу :) Компилириуемый и managed языки видут себя по разному. Тут да квадратична :)
                                  +2
                                  Стоит заметить, что StringBuilder на деле не так часто требуется. Во многих местах достаточно слепить массив и позвать String.Contat. В других — можно выплевывать строки прямо в выходной TextWriter, без промежуточного склеивания. Как это делается, скажем, при рендеринге html-страничек в ASP.NET. Я уже даже и не помню когда мне StringBuilder требовался в последний раз.

                                  Стоит присматриваться к местам где используется StringBuilder на предмет нельзя ли переделать метод, например, из string GetTable() в void WriteTable(TextWriter writer). Второй вариант позволяет и в поток писать, и в буфер через StringWriter (который является оберткой того же StringBuilder-а)
                                    +1
                                    Тема потокобезопасности не раскрыта.
                                      0
                                      Интересно.
                                      Интересно бы еще сравнить с Java-подходом в плане эффективности. Кстати, судя по исходникам, подход Java проще всего:

                                          /**
                                           * The value is used for character storage.
                                           */
                                          char[] value;
                                      
                                          /**
                                           * The count is the number of characters used.
                                           */
                                          int count;

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое