О разворачивании строк в .Net/C# и не только

    Давайте поговорим о строках, точнее об их переворачивании средствами .Net/C#. Так уж сложилось, что в стандартной библиотеке соответсвующей функции не наблюдается. И как мне подсказывают, написание функции обращения строки довольно популярный вопрос на собеседованиях при приеме на работу. Давайте посмотрим, как можно эффективно перевернуть строку средствами данной платформы.

    Под катом приведен сравнительный анализ быстродействия разных методов переворачивания строки.



    Кхрр-р-р… — сказала бензопила.
    Тююю… — сказали мужики.
    © Старый анекдот.


    Ну что ж, начнем. Все реализации проверялись на быстродействие с одной строкой размером 256 мегабайт (128×1024×1024 символа) и 1024×1024 строками размером 256 байт (128 символов). Перед каждым замером форсировалась сборка мусора (что важно при таком размере тестовых данных), замер проводился 50 раз, 20 крайних отбрасывались, остальные значения усреднялись. Условными попугаями было выбрано количество тиков, выдаваемое объектом класса Stopwatch.

    Тест проводился на двух компьютерах: Athlon64 x2 4200+, 2GB Dual-Channel DDR2 RAM и Pentium4 HT 3GHz, 3GB DDR RAM. Главным отличием между конфигурациями в данном тесте является быстродействие связки память-кэш — вторая система в этом отношении заметно медленнее.

    С техническими формальностями покончено, теперь перейдем к собственно реализациям. Для большей наглядности, здесь не учтены unicode surrogate code points. Рассматривать подходы будем в порядке логичности и «красивости» реализации в контексте окружающей ее «экосистемы».

    Сравнительные результаты замеров находятся в последней части этой заметки. Оптимальной в общем случае оказалась функция ReverseUnsafeCopy, если же ограничиваться только safe code — ReverseArrayManual. Если необходим safe code и огромные строки — прийдется мучаться с ReverseStringBuilder.

    Часть первая: «нормальные» методы.


    1. ReverseStringBuilder

    Будем следовать рекомендациям и для построения «большой» строки возьмем специальный инструмент — класс StringBuilder. Идея проста до ужаса: создаем builder нужного размера и идем по строке в обратном порядке, добавляя символы в новую строку.

    Copy Source | Copy HTML
    1. static string ReverseStringBuilder(string str)
    2. {
    3.     StringBuilder sb = new StringBuilder(str.Length);
    4.     for (int i = str.Length; i-- != 0; )
    5.         sb.Append(str[i]);
    6.     return sb.ToString();
    7. }

    Пробуем, запускаем, да… Как-то медленно работает это все, будем копать дальше.

    2. ReverseArrayFramework

    Ха! Так этот билдер же обставлен проверками для обеспечения потокобезопасности со всех сторон, не, нам такое не надо. Но строка — это ведь массив сиволов. Так давайте его и перевернем, а результат преобразуем обратно в строку:

    Copy Source | Copy HTML
    1. static string ReverseArrayFramework(string str)
    2. {
    3.     char[] arr = str.ToCharArray();
    4.     Array.Reverse(arr);
    5.     return new String(arr);
    6. }

    Совсем другое дело, получилось в 3.5 раза быстрее. Хм, а может можно еще лучше?

    3. ReverseArrayManual

    Так, думаем. Во-первых у нас данные копируются дважы: сначала из строки в массив, потом внутри массива. Во-вторых Array.Reverse — библиотечный метод, значит в нем есть проверки входных данных. Более того, для атомарных типов он явно реализован в виде native метода, а это дополнительное переключение контекста выполнения. Попробуем перевернуть строку в массив вручную:

    Copy Source | Copy HTML
    1. static string ReverseArrayManual(string originalString)
    2. {
    3.     char[] reversedCharArray = new char[originalString.Length];
    4.     for (int i = originalString.Length - 1; i > -1; i--)
    5.         reversedCharArray[originalString.Length - i - 1] = originalString[i];
    6.     return new string(reversedCharArray);
    7. }

    4. ReverseManualHalf

    Идем дальше. У нас же действия симметричны относительно середины строки, значит можно пустить два индекса навстречу и ученьшить количество итераций вдвое:

    Copy Source | Copy HTML
    1. static string ReverseManualHalf(string originalString)
    2. {
    3.     char[] reversedCharArray = new char[originalString.Length];
    4.     int i = 0;
    5.     int j = originalString.Length - 1;
    6.     while (i <= j)
    7.     {
    8.         reversedCharArray[i] = originalString[j];
    9.         reversedCharArray[j] = originalString[i];
    10.         i++; j--;
    11.     }
    12.     return new string(reversedCharArray);
    13. }

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

    LINQ и метод Reverse

    Есть еще относительно красивый и короткий способ с LINQ, но он не выдерживает никакой критики в плане производительности — работает в 3-3.5 раза медленнее метода на базе StringBuilder. Виной тому прокачивание данных через IEnumerable и виртуальный вызов на каждую итерацию. Для желающих, ниже приведена реализация:

    Copy Source | Copy HTML
    1. static string ReverseStringLinq(string originalString)
    2. {
    3.     return new string(originalString.Reverse().ToArray());
    4. }

    Использование памяти

    Проблема не столь критичная в большинстве случаев, но все «быстрые» из рассмотренных методов делают промежуточную копию строки в виде массива символов. На синтетических тестах это проявляется в том, что обернуть строку размером 512МБ смог только первый метод, остальные свалились по System.OutOfMemoryException. Также, не следует забывать, что лишние временные объекты повышают частоту срабатывания GC, а он хоть и оптимизирован до ужаса, но все-равно время кушает. В следующей части будем кроме скоростных оптимизаций также искать решение этой проблемы.

    Часть вторая: когда хочется быстрее и эффективнее, или unsafe code.


    Использование unsafe кода дает нам одно интересное преимущество: строки, которые раньше были immutable, теперь можно менять, но нужно быть предельно осторожным и изменять только копии строк — библиотека минимизирует количество копий одной строки, а вместе с интернированием строк это может привести к печальным последствиями для приложения.

    Итак, создав новую строку нужного размера, мы можем смотреть на нее, как на массив и заполнить нужными данными. Ну и не стоит забывать об отстутствии проверок на валидность индексов, что тоже ускорит работу кода. Однако в силу специфики строк в .Net, мы не можем вот так просто создать строку нужной длины. Можно либо сделать строку из повторяющегося символа (например проблела) при помощи конструктора String(char, int), либо скопировать исходную строку используя String.Copy(String).

    Вооружившись этими знаниями пишем следующие две реализации.

    5. ReverseUnsafeFill

    Делаем строку из пробелов и заполняем ее в обратном порядке:

    Copy Source | Copy HTML
    1. static unsafe string ReverseUnsafeFill(string str)
    2. {
    3.     if (str.Length <= 1) return str;
    4.     String copy = new String(' ', str.Length);
    5.     fixed (char* buf_copy = copy)
    6.     {
    7.         fixed (char* buf = str)
    8.         {
    9.             int i = 0;
    10.             int j = str.Length - 1;
    11.             while (i <= j)
    12.             {
    13.                 buf_copy[i] = buf[j];
    14.                 buf_copy[j] = buf[i];
    15.                 i++; j--;
    16.             }
    17.         }
    18.     }
    19.     return copy;
    20. }

    6. ReverseUnsafeCopy

    Копируем и переворачиваем строку:

    Copy Source | Copy HTML
    1. static unsafe string ReverseUnsafeCopy(string str)
    2. {
    3.     if (str.Length <= 1) return str;
    4.     char tmp;
    5.     String copy = String.Copy(str);
    6.     fixed (char* buf = copy)
    7.     {
    8.         char* p = buf;
    9.         char* q = buf + str.Length - 1;
    10.         while (p < q)
    11.         {
    12.             tmp = *p;
    13.             *p = *q;
    14.             *q = tmp;
    15.             p++; q--;
    16.         }
    17.     }
    18.     return copy;
    19. }

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

    7. ReverseUnsafeXorCopy

    А что дальше? Ходят слухи, что обмен при помощи оператора XOR работает быстрее копирования через третью переменную (кстати в плюсах это еще и смотрится довольно красиво: «a ^= b ^= a ^= b;», в C#, увы, такая строка не cработает). Ну что, давайте проверим на деле.

    Copy Source | Copy HTML
    1. static unsafe string ReverseUnsafeXorCopy(string str)
    2. {
    3.     if (str.Length <= 1) return str;
    4.     String copy = String.Copy(str);
    5.     fixed (char* buf = copy)
    6.     {
    7.         char* p = buf;
    8.         char* q = buf + str.Length - 1;
    9.         while (p < q)
    10.         {
    11.             *p ^= *q;
    12.             *q ^= *p;
    13.             *p ^= *q;
    14.             p++; q--;
    15.         }
    16.     }
    17.     return copy;
    18. }

    В итоге получается в 1.2-1.5 раза медленнее обмена копированием. Трюк, работавший для быстрого обмена значений на регистрах, для переменных себя не оправдал (что характено, во многих компиляторах С/С++ он тоже выиграша не дает).

    В поисках объяснения этого факта полезем внутрь приложения и почитаем результирующий CIL код.

    Часть третья: лезем в CIL и коды библиотек .Net.


    Почему обмен через XOR оказался хуже

    Для получения ответа на этот вопрос стоит посмотреть на CIL-код, сгенерированный для двух способов обмена. Чтоб эти инструкции казались понятнее, поясню их назначение: ldloc.N — загружает на стек локальную переменную под номером N, stloc.N — считывает верхушку стека в локальную переменную номер N, xor — вычисляет значение операции XOR для двух значений наверху стека и загружает результат на стек вместо них.

    Обмен копированием Обмен на базе XOR Идеальный обмен CIL
    1. int a, b;
    2. int tmp = a;
    3. a = b;
    4. b = tmp;
    1. int a, b;
    2. a ^= b;
    3. b ^= a;
    4. a ^= b;
     
    .locals init (<br/>
        [0] int32 a,<br/>
        [1] int32 b,<br/>
        [2] int32 tmp)
    .locals init (<br/>
        [0] int32 a,<br/>
        [1] int32 b)<br/> 
    .locals init (<br/>
        [0] int32 a,<br/>
        [1] int32 b)<br/> 
    L_0004: ldloc.0<br/>
    L_0005: stloc.2<br/>
    L_0006: ldloc.1<br/>
    L_0007: stloc.0<br/>
    L_0008: ldloc.2<br/>
    L_0009: stloc.1<br/> <br/> <br/> <br/> <br/> <br/> 
    L_0004: ldloc.0<br/>
    L_0005: ldloc.1<br/>
    L_0006: xor<br/>
    L_0007: stloc.0<br/>
    L_0008: ldloc.1<br/>
    L_0009: ldloc.0<br/>
    L_000a: xor<br/>
    L_000b: stloc.1<br/>
    L_000c: ldloc.0<br/>
    L_000d: ldloc.1<br/>
    L_000e: xor<br/>
    L_000f: stloc.0<br/>
    L_0004: ldloc.0<br/>
    L_0005: ldloc.1<br/>
    L_0006: stloc.0<br/>
    L_0007: stloc.1<br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> 

    Как легко заметить, версия с оператором XOR требует больше операций виртуальной машины. Более того, при последующей компиляции в native код, вполне вероятно наличие оптимизации, которая типичный обмен через третью переменную заменит более эффективной операцией обмена с учетом возможностей используемого процессора. Как побочный эффект анализа, получаем гипотетический «идеальный» обмен на CIL, было бы интересно проверить, даст ли его использование какой-либо эффект, но для этого надо возиться с ilasm или reflection/emit, может еще соберусь. Впрочем полученный код будет еще менее применим, чем unsafe c# поэтому практичекого интереса особо не представляет.

    Как работает Array.Reverse?

    Ну и пока мы смотрим на внутренности сборок рефлектором, есть смысл взглянуть на реализацию библиотечных методов, использованных в первой части. Особняком здесь стоит Array.Reverse, который опирается на некую функцию Array.TrySZReverse, реализованную в виде native метода. Итак качаем Shared Source Common Language Infrastructure 2.0 — исходник .net 2.0 и смотрим, что ж это за зверь такой :) После недолгих поисков, в файле «sscli20\clr\src\vm\comarrayhelpers.h» находится шаблонная функция Reverse (в данном случае KIND будет соответствовать UINT16), которая (сюрприз!) до ужаса похожа на реализацию ReverseUnsafeCopy.

    Copy Source | Copy HTML
    1. static void Reverse(KIND array[], UNIT32 index, UNIT32 count) {
    2.     LEAF_CONTRACT;
    3.  
    4.     _ASSERTE(array != NULL);
    5.     if (count == 0) {
    6.         return;
    7.     }
    8.     UNIT32 i = index;
    9.     UNIT32 j = index + count - 1;
    10.     while(i < j) {
    11.         KIND temp = array[i];
    12.         array[i] = array[j];
    13.         array[j] = temp;
    14.         i++;
    15.         j--;
    16.     }
    17. }

    Часть четвертая: результаты бинарного марафона.


    Анализ результатов замеров приведен в первых двух частях, здесь же изображены лишь сравнительные диаграммы отображающие отношение быстродействия рассмотренных выше функций. Точные числа в «ticks» слишком зависят от конфигурации и вряд-ли представляют особый интерес, все желающие могут самостоятельно замерить быстродействие используя предоставленные куски кода.

    Сравнение лучших методов из первых двух частей

    На быстрой памяти
    Image and video hosting by TinyPic
    На медленной памяти
    Image and video hosting by TinyPic

    Сравнение всех методов в Debug и Release конфигурациях на быстрой памяти

    Большие строки
    Image and video hosting by TinyPic
    Короткие строки
    Image and video hosting by TinyPic

    Сравнение всех методов в Debug и Release конфигурациях на медленной памяти

    Большие строки
    Image and video hosting by TinyPic
    Короткие строки
    Image and video hosting by TinyPic
    Поделиться публикацией

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

      +14
      очень вкусная статья, спасибо :)
      столько трудов вложили, оценил
        0
        Ого. Спасибо за вкусную пищу для ума :) ++ вам в карму.
          0
          Спасибо за графики.
          Было бы интересно посмотреть как на разных процессорах пройдут тесты :)
            0
            очень интересно и видно, что большой труд проделан.
            пару вопросов:
            а) а такую строку вы из файла брали?
            б) считали время выполнения только самого метода? Считали время выполнения за раз или несколько раз проводили тесты?
            в) а многопоточность не пробовали как то использовать? Например разбить на два — обработать каждый в своем потоке и потом склеить.
              0
              а) new String(' ', );
              б) примерно так: «sw.Start(); Reverse*(s); sw.Stop();». сколько раз и как — там написано ;)
              в) вряд-ли это поможет — основной затык в обращениях к памяти, так их будет еще больше и еще менее централизовано. да и склеивание не есть быстрая операция.
                0
                а) new String(' ', N);
              0
              Спасибо за интересную статью.
              Всегда было интересно как оно там под капотом работает. Пишите еще.
                +1
                Полноценное исследование. Некоторые студенты для диплома такого не сделают :)
                Присоединяюсь к желанию посмотреть зависимость методов от используемого процессора
                  0
                  Скорость для ReverseManualHalf упала потому, что дергаются постоянно разные участки памяти. Подготовка данных просто обламывается (готовится один блок, а дергается из другого, идет переподготовка, и опять облом).

                  Чтобы максимально ускорить копирование, надо копировать несколько байт или (хотя бы) последовательно:
                  dest[i] = src[j];
                  dest[i+1] = src[j-1];
                  dest[i+2] = src[j-2];
                  dest[i+3] = src[j-3];
                    0
                    Вряд-л там идет захват по 8 байт :) Но, да, такая оптимизация должна ускорить работу. Впрочем она применима практически ко всем рассмотреным функциям.
                    А еще это уменьшает накладные расходы на организацию цикла.
                      0
                      в кеш загружается X байт, X зависит от железа :)
                        0
                        логично ) а поскольку точные алгоритмы кэширования нам никто не расскажет, то мы можем лишь оценить идеальную ситуацию: X = CacheSize/2 в случае с полным проходом и X = CacheSize/4 в случаем с проходом накрест.
                          0
                          Расскажут и с удовольствием! На этом держатся все ресурсоемкие приложения (от типа и версии процессора выбирается оптимальная для него функция, иногда встречаются даже разные exe и инсталлер создает ярлык на тот exe, который оптимизирован под CPU).
                            0
                            помню как AMD размещали у себя на сайте примеры (с++) для оптимальной работы с памятью для K6. :)
                              0
                              Ну это же скорее рекомендации, чем алгоритм выбора данных для захвата в кэш :)
                              0
                              Точные алгоритмы вот так публично не расскажут — конкурент ведь не спит :) Основные идеи — да, наверняка доступны.

                              Компании, которые делают такие оптимизации как правило тесно сотрудничают с производителями процессоров (и, что важно, могут себе это позволить). Оптимизации уровня «запросить размер кэша и работать с блоками примерно такого размера» не в счет :)

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

                              Однако если есть желание рассказать — с удовольствием почитаю :)
                                0
                                Сейчас посмотреть оптимизацию для Intel можно наглядно с помощью их компилятора (он развернет циклы “как надо”, слегка оптимизирует алгоритмы (если возможно), может немного поменять логику работы с памятью). Всё что делает компилятор описано в соответствующих спеках. Логика работы в общем виде всегда была доступна, чтобы программер точно понимал где горлышко и почему все тормозит из-за жутких пенальти. Я довольно далеко ушел от архитектур, последним процем за которым я следил был AMD K7.

                                Многозадачность — это особенная фишка, которая заставляет постоянно перезагружать данные в кеш. :) При смене контекста, естественно, данные сбрасываются в кеш нижнего уровня (“ниже” нижнего уровня кеша – медленная RAM). Чем больше поток потребляет памяти, тем дороже его переключение, при желании или большой удаче можно “подвесить” поток – вся его работа будет заключатся в ожидании ответа от памяти, а когда ответ придет, квант времени будет исчерпан и уже другой поток запросит свою область.

                                Тема очень обширна для коммента. :(
                                  0
                                  Я прекрасно понимаю обширность темы, это я так намекаю что с удовольствием почитал бы что-то более обширное, нежели комментарии :) Если время позволяет, конечно.
                                    0
                                    Кстати, вернулись же к исходному — алгоритм кэширования (как и предсказания ветвлений) остается «черным ящиком», известно только что он должен делати и есть рекомендации что лучше на вход скармливать.
                                      0
                                      «То, что скармливать» проистекает из
                                      1. какой объем кешей.
                                      2. какая разрядность у шины
                                      3. какая задержка/частота у шины
                                      4. какое время поиска/открытия ячейки памяти
                                      Это уже не «черный ящик»… В крайнем случае «серый прозрачный» :)
                                        0
                                        Нее, черный :) Он подключен к кэшам по быстрому каналу и к памяти по медленной шине.

                                        А вот какой логикой он руководствуется при захвате блока памяти мало кому известно. Например высока вероятность, что при линейном чтении большого массива, через пару итераций будет захватываться блок большого размера (тем более что спекулятивное выполнение заглядывает на нексколько инструкций вперет и можно предугадывать, что надо подгрузить).
                                          +1
                                          я задумался на тему «что дать почитать». Вспомнил отличные и прозрачные материалы Николая Радовского. Если надо более серьезное, то могу посоветовать почитать «Архитектуру микропроцессоров» г. 1998 Питер (автора не помню, очень давно было :( ).
                        0
                        что-то я не понял, почему ReverseManualHalf должна работать быстрее ReverseArrayManual (((
                        количество итераций уменьшилось вдвое, размер итерации увеличился вдвое, в чём выгода?
                          0
                          Расходы на организацию цикла. В данном случае они соизмеримы со сложностью одной итерации.
                            0
                            как думаешь, что быстрее будет — десять операций типа х = х + 1 подряд или цикл от одного до десяти с той же самой операцией?

                            цикл-то не бесплатный, там проверки счетчика стоят, определение куда прыгать и т.д.

                            поэтому существует такой метод оптимизации скорости, как разворачивание циклов (хотя в памяти такая программа больше места займет, конечно)
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Действительно можно попробовать копировать блоки помещающиеся в L1 и переворачивать их in-place. Я хотел это проверить, но по ходу реализации пришел к выводу что это вряд-ли будет быстрее ReverseArrayManual :)

                                Что касается ReverseArrayFramework — ну так там и особо думать не о чем, прирост производительности в других реализациях достигается исключительно за счет отброса лишних копирований. А в случае unsafe еще исключается лишний промежуточный буфер.
                                +1
                                графики — юзеранфрендли… у-шкала — это что: время или скорость? Если я не вникая в суть статьи пролистну сразу до графиков — из них не пойму, какой метод лучший.
                                  +1
                                  Замечательная статья!
                                  Если честно, прочитав сначала заголовок, подумал, что речь пойдет о разворачивании/сворачивании (expanding/collapsing) строчек кода в время редактирования сорца :)
                                    0
                                    Звездец.

                                    Строка переворачивается элементарно:

                                    reverse = foldl (flip (:)) []

                                    А если серьезно, то вы впустую тратите время. Расскажите, какие задачи вы решаете, в которых настоящим ботлнеком является тупое переворачивание строки. Иначе же в топку.
                                      0
                                      Знаете, а я вот думаю, что strrev(s) в С работает быстрее и эффективнее этого примера. и пишется короче :)

                                      А если серъезно, то дело ведь не столько в самом акте разворачивания строки, лично мне интересней посмотреть, что вообще можно выжать из этой среды.

                                      Есть два противостоящих «мира»: одни строят приложение на сверхвысокоуровневой платформе не думая об эффективности и производительности (об этом за нас подумает платформа ©), другие же пытаются выжать максимум чтою эта «платформа» таки думала за первых. Лично мне ближе второе, закономерно, что я буду везде искать интересные мне аспекты.

                                      А конкретно это пример был «высосан из пальца» в пятницу вечером :)
                                        0
                                        > Есть два противостоящих «мира»: одни строят приложение на сверхвысокоуровневой платформе не думая об эффективности и производительности (об этом за нас подумает платформа ©), другие же пытаются выжать максимум чтою эта «платформа» таки думала за первых. Лично мне ближе второе, закономерно, что я буду везде искать интересные мне аспекты.

                                        Ну так эта, если хоцца скорости, то strrev будет вин. А так очередной abuse.

                                        > Кстати вопрос еще что считать «боттлнеком»: если требуется высокая интерактивность, то лишняя экономия не помешает :)

                                        Неправильно. Оптимизировать надо только тогда, когда это действительно скажется на скорости. Ну а если оптимизировать, то скорость должна вырасти НА ПОРЯДОК, а не в два-три-четыре-пять раз (другими словами, 2x буст хоть и заметен пользователю, но жизни его не упростит, и следовательно, не нужен).
                                          0
                                          Вы видимо никогда игрушки не писали :) Там даже за прирост скорости в 15% борются.
                                          Согласен, писать динамичные игры на .Net в данный момент глупость, но так уж сложилось что я в силу определенный факторов пришел на эту платформу, а привычки и взгляды остались.
                                            +1
                                            > Вы видимо никогда игрушки не писали :)

                                            Ну как же. Писывал, было дело (непрофессионально). На Си, правда. Это был отборрный лапшекод, но тогда я этого не знал. :)

                                            > Там даже за прирост скорости в 15% борются.

                                            Везде одна и та же тенденция: сает — разгоним, игрушку — разгоним, переворачивание строк — разгоним… Это все бессмысленно.

                                            Еще раз повторяю: если игрушка грузилась минуту, а мы ее загрузку ускорили в два раза, то пользователю от этого не стало легче. Он все равно так же уныло смотрит в монитор. Стоит ли такое ускорение проводить или нет? (Ответ, разумеется, нет.)

                                            Что же касается скорости рантайма, то тут надобно находить ботлнеки, и бороться именно с ними, ибо, как известно, 90% времени программа проводит в 10% кода. Алгоритмические оптимизации рулят, а низкоуровневые — нет. (Исключения бывают, конечно, но только как исключения.)
                                              0
                                              > Везде одна и та же тенденция: сает — разгоним, игрушку — разгоним, переворачивание строк — разгоним… Это все бессмысленно.

                                              Вопрос не во времени загрузки игрушки, а в скорости отклика на действия пользователя.
                                                0
                                                > Вопрос не во времени загрузки игрушки, а в скорости отклика на действия пользователя.

                                                Дык а причем здесь переворачивание строки-то? :)

                                                Хорошая программа, однако, которая отзывчиво переворачивает строку…
                                              0
                                              >писать динамичные игры на .Net в данный момент глупость
                                              для динамических игр есть XNA, так что не совсем глупость )
                                                0
                                                Ну во-первых далеко не любой игровой платформе он есть :)
                                                А во вторых… есть некоторые познания о жизнеспособности .Net CF в условиях ограниченых ресурсов (около 2М памяти, остальное железо тоже на уровне, .Net CF официальная среда), и они не очень позитивные. Впрочем писали же люди… И работало, правда с гайдлайнами .Net в итоге мало общего имело :)
                                                  0
                                                  Для таких сред есть .NET Micro Framework, правда его надо затачивать под каждое конкретное железо самостоятельно (т.к. он выполняет функции OS, которой как таковой нет).
                                                    0
                                                    Ну вообще-то девайс мелкософтовский был и они почему-то решили выбрать .Net CF :)

                                                    Впрочем я не уверен, что девайс для игрушек предназначался, но такова специфика у gamedev индустрии — прикрутить игрушку на все, где ее можно продать :)
                                          0
                                          Кстати вопрос еще что считать «боттлнеком»: если требуется высокая интерактивность, то лишняя экономия не помешает :)
                                          +2
                                          А теперь добавьте к исходным условиям задачи кодировку UTF-8 — что для современных приложений by default, и сложность задачи возрастет существенно.
                                            0
                                            Ну не знаю, в мирах win32 и .Net все оперативные данные хранят в UTF-16, а UTF-8 используется только для ввода-вывода, поэтому замечание к .Net не применимо. А конвертация в обе стороны делается за один проход.

                                            Кстати сложность будет сравнима со сложностью обработки суррогатных пар.
                                            0
                                            for (int i = str.Length; i-- !=; )
                                              0
                                              int i =;

                                              С чем связано использование такого не совсем очевидного стиля? Какая практическая польза? (раз уж речь об оптимизации)
                                                0
                                                1. Хабр нолик сожрал в условии
                                                2. Стиль, как стиль. На С/С++ сплошь и рядом так пишут, главная польза в единоразовом вычислении str.Length. Ну и потенциальном схлопывании сравнения с нулем в одну операцию целевого процессора, хотя и мелочь второе.
                                                  0
                                                  Хабр что-то вообще много чего жрёт )

                                                  Я имел ввиду, почему не for (int i = str.Length; i != 0; i-- )?

                                                  Кстати, всегда интересно было, i>=0 идёт как одно сравнение? Или лучше использовать i>-1? Есть вообще разница?
                                                    +1
                                                    > Есть вообще разница?

                                                    Нету разницы. Ускорять такие циклы на таком уровне — это пустая трата времени. [1]

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

                                                    [1] поменять время выполнения с 0.99с до 0.98с — велика разница? :)
                                                      0
                                                      глобально — да, нету разницыБ нормальный компилятор развернет одинаково. просто в плюсах "!= 0" писать не надо, получается for (int i = str.Length; i--; ). писал, как привык.
                                                        0
                                                        Точно, спасибо.
                                              –2
                                              сизифов труд, очевидные и никому не нужные результаты
                                                0
                                                Ошибаетесь. Как минимум, будет что рассказать на собеседовании. Да и время сэкономит, случись озаботиться такой задачей.
                                                0
                                                for (int i = str.Length; i-- != ; )

                                                ошибка, вроде бы?
                                                  0
                                                  да, выше написано. хабр нолик сожрал после "!=" :)
                                                  0
                                                  Все неправильно. Unicode-строки так не разворачивают: StringInfo.GetTextElementEnumerator() и далее.
                                                    0
                                                    Очень даже разворачивают, только чуть более громоздко это будет.
                                                    Для большей наглядности, здесь не учтены unicode surrogate code points.


                                                    А фреймворк не есть единственно верное решение, кстати что-то мне кажется что энумератор тормозить ужасно будет. Ну примерно как версия с LINQ, по тем же причинам.

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

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