Конвертация строки в число

в 2:47, , рубрики: .net, оптимизация, метки: ,

Помогал на днях одной своей знакомой разобраться в программировании. По ходу дела написали учебную программу, которая умеет конвертировать строку (string) в число (int). И как-то само собой захотелось сравнить скорость работы собственной нетленки, со скоростью работы стандартных инструментов (Convert.ToInt32 и Int32.Parse). Результат такого сравнения, на первый взгляд, получился несколько необычным.

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

    class MyConvert
    {
        private static int CharToInt(char c)
        {
            return c - '0';
        }
        public static int ToInt(string s)
        {
            if (s == null) throw new ArgumentException();
            if (s.Length == 0) throw new ArgumentException();
            bool isNegative = false;
            int start = 0;
            if (s[0] == '-')
            {
                if (s.Length == 1) throw new ArgumentException();
                isNegative = true;
                start = 1;
            }
            int result = 0;
            for (int i = start; i <  s.Length; i++)
            {
                if (c < '0' || c > '9') throw new ArgumentException();
                result = checked(result * 10 + CharToInt(s[i]));
            }
            return (isNegative) ? -result : result;
        }
    }

Сравнивать будем скорость работы следующих функций:

        static void MyConvertTest(int numbersCount)
        {
            for (int i = - numbersCount; i < numbersCount; i++)
            {
                if (i != MyConvert.ToInt(i.ToString()))
                {
                    throw new ArgumentException();
                }
            }
        }

        static void ConvertTest(int numbersCount)
        {
            for (int i = - numbersCount; i < numbersCount; i++)
            {
                if (i != Int32.Parse(i.ToString()))
                {
                    throw new ArgumentException();
                }
            }
        }

На моей машине (Windows 7, .NET 4.0, intel i5) при numbersCount=16 000 000 получаются в среднем следующие результаты:
ConvertTest: 08.5859994 секунды
MyConvertTest: 07.0505985 секунды

Если вместо Int32.Parse использовать Convert.ToInt32, то результат никак не изменится. Но это и понятно, если учесть, что функция Convert.ToInt32 сама вызывает Int32.Parse. Таким образом, получаем, что скорость работы собственного велосипеда быстрее скорости работы стандартной функции на ~ 18 %.

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

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

    for (int i = start; i <  s.Length; i++)

на

    int length = s.Length;
    for (int i = start; i < length; i++)

В этом случае получаем:
MyConvertTest: 06.2629928 секунды
То есть теперь скорость работы нашей функции быстрее стандартной на ~ 27%. Это довольно неожиданно. Я считал, что компилятор (или же CLR) сможет понять, что так как внутри цикла мы не изменяем переменную s, то значение s.Length будет получено только один раз.

Теперь попробуем вместо вызова функции CharToInt, встроить ее тело в функцию ToInt. В этом случае
MyConvertTest: 05.5496214 секунды
Так, скорость работы относительно стандартной функции увеличилась на ~ 35%. Это тоже в свою очередь довольно неожиданно, так как компилятор (или CLR) в некоторых случаях самостоятельно может это сделать.

Уже почти все перепробовали. Осталось только попробовать отказаться от цикла for. Это можно сделать, например, следующим образом:

        unsafe public static int ToInt(string s)
        {
            if (s == null)
            {
                throw new ArgumentException();
            }
            int result = 0;
            bool isNegative = false;
            fixed(char* p = s)
            {
                char* chPtr = p;
                char ch = *(chPtr++);
                if (ch == '-')
                {
                    isNegative = true;
                    ch = *(chPtr++);
                }
                do
                {
                    if (ch < '0' || ch > '9')
                    {
                        throw new ArgumentException();
                    }
                    result = result * 10 + (ch - '0');
                    ch = *(chPtr++);
                }while (ch != '');

            }
            return (isNegative) ? -result : result;
        }

Результат:
MyConvertTest: 05.2410683 секунды
Это на ~39% быстрее стандартной функции (и всего лишь на 3% быстрее варианта с for).

Выводы

Конечно же никакой особой ценности попытки увеличить скорость работы функции перевода строки в число не имеют. Я не могу представить ни одной ситуации, в которой бы такой прирост производительности оказывал бы хоть какое-то значимое влияние. Тем не менее, некоторые вполне очевидные выводы сделать можно:

  • В некоторых случаях свои собственные творения могут работать лучше стандартных решений.
  • В некоторых случаях выделение отдельной переменной для конечного значения цикла for (то есть замена «i < s.Length» на «i < length») может дать неплохой прирост в скорости (почти 10% в данном случае). Хотя это во многом зависит от настроения CLR.
  • В некоторых случаях встраивание в функцию тела метода вместо вызова самого метода так же имеет значение. Хотя это так же зависит от настроения CLR.

Довольно часто в различной литературе встречаются вполне справедливые утверждения о том, что всю низкоуровневую оптимизацию нужно возложить на плечи компилятора и среды выполнения. Они мол достаточно интеллектуальные и сами лучше знают, как будет лучше. Однако, как показывают подобные тесты, оптимизация циклов и развертывание функций может обернуться 20-ти процентным приростом в скорости (если сравнить 1-й вариант).

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

Автор: SHTrassEr


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js