SHTrassEr29 авг 2012 в 02:47

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

4 мин

68K

.NET * C# *

+16

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

DIHALT 29 авг 2012 в 03:01

Смотря где, смотря где. В каком нибудь AVR в этой конвертации за каждый байт бьешься.

ertaquo 29 авг 2012 в 03:03

А как быстро будет работать такой вариант, в сравнении с вашим?

unsafe public static int ToInt(string s)
{
	if (s == null)
	{
		throw new ArgumentException();
	}
	
	int sign = 1, n = 0;
	fixed(char * p = s)
	{
		char * pS = p;
		while (*pS < ' ') pS++;
		switch(*pS)
		{
		case '-':
			sign = -1;
		case '+':
			ps++;
		}
		
		while (*pS >= '0' && *pS <= '9')
			n = 10 * n + *(pS++) - '0';
	}
	
	return sign * n;
}

Источник

SHTrassEr 29 авг 2012 в 03:46

Точно, совсем забыл про вариант с плюсом, спасибо, сейчас исправлю.

Предложенный вами вариант быстрее моего в среднем на 6,8%. Однако в этом варианте немного другая логика: убираются ведущие пробелы, и нет проверки на входной параметр (пустая строка преобразуется в 0, «12b» преобразуется в 12). Хотя если даже добавить такую проверку, то все равно она будет работать быстрее, в среднем на 5%.

проверялся следующий код:

        unsafe public static int ToIntNotMy(string s)
        {
            if (s == null)
            {
                throw new ArgumentException();
            }

            int sign = 1, n = 0;
            fixed (char* p = s)
            {
                char* pS = p;
                while (*pS == ' ') pS++;
                switch (*pS)
                {
                    case '-':
                        sign = -1;
                        pS++;
                        break;
                    case '+':
                        pS++;
                        break;
                    case '\0':
                        throw new ArgumentException();
                }

                while (*pS >= '0' && *pS <= '9')
                    n = 10 * n + *(pS++) - '0';
                if (*pS != '\0') throw new ArgumentException();
            }

            return sign * n;
        }

ertaquo 29 авг 2012 в 03:53

Тогда уж по вашим условиям лучше написать так:

unsafe public static int ToIntNotMy(string s)
{
	if (s == null)
		throw new ArgumentException();

	int sign = 1, n = 0;
	fixed (char* p = s)
	{
		char* pS = p;
		
		switch (*pS)
		{
			case '-':
				sign = -1;
			case '+':
				pS++;
		}

		while (*pS >= '0' && *pS <= '9')
			n = 10 * n + *(pS++) - '0';
			
		if (*pS != '\0') throw new ArgumentException();
	}

	return sign * n;
}

Дополнительный case не нужен, потому что если строка пустая, не выполнятся условия в switch и while и оно сразу перейдет к условию и выкинет исключение.

SHTrassEr 29 авг 2012 в 04:01

В данном случае case все-таки нужен: если была передана пустая строка, то условие

if (*pS != '\0')

так же не будет выполнено.

Проверка на ведущие пробелы на скорость почти не повлияла: так же на ~5% преимущество.

ertaquo 29 авг 2012 в 08:37

Если была передана пустая строка, то pS будет указывать на s[0], т. е. на '\0'. Другие case или while выполняться не будут, поэтому значение pS не изменится. Так что дополнительный case не нужен.

voff 29 авг 2012 в 03:37

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

Как сейчас все сложно. В мое время, что бы произвести впечатление на девушку, достаточно было уметь винду переустанавливать :-)

nadenok 29 авг 2012 в 10:11

как тогда, так и сейчас: смотря какую девушку.

astudent 29 авг 2012 в 03:39

В вашем методе затаился баг: число +123 не распознается.

SHTrassEr 29 авг 2012 в 03:55

Спасибо, совсем забыл про этот вариант, сейчас поправил. На производительность это почти не повлияло (в пределах погрешности).

Внимательности не хватает.

petuhov_k 29 авг 2012 в 04:05

Прогрев был? Всё таки, одна и функций грузится из сборки, а вторая уже загружена.

SHTrassEr 29 авг 2012 в 04:11

Да, время первого выполнения каждого из тестов не учитывалось. Хотя это время почти не отличается от среднего.

Fed_Mikron 29 авг 2012 в 04:28

Ассемблерную вставку делать не пробовали, раз уж на то пошло?

elw00d 29 авг 2012 в 06:04

Я считал, что компилятор (или же CLR) сможет понять, что так как внутри цикла мы не изменяем переменную s, то значение s.Length будет получено только один раз.

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

lair 29 авг 2012 в 07:01

Вообще, это архистранно, потому что мы-то знаем, что string — immutable. И компилятор знает. Так что это значение не может измениться.

shai_hulud 29 авг 2012 в 07:09

Это вы в книжке прочитали. А на самом деле строка может быть изменена(к примеру StringBuilder изменяет строки). Так что у оптимизатора нет гарантии. Другое дело это длинна массива.

lair 29 авг 2012 в 07:52

А на самом деле строка может быть изменена(к примеру StringBuilder изменяет строки).

Это, простите, как?

Если что, StringBuilder работает с буфером символов вообще.

shai_hulud 29 авг 2012 в 11:33

Ну к примеру:

StringBuilder.ToString()

string str = string.FastAllocateString(this.Length);
…
fixed (char* str2 = ((char*) str))
{
char* chPtr = str2;
do
{
…
string.wstrcpy(chPtr + chunkOffset, chRef, chunkLength);
…
}
}

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

lair 29 авг 2012 в 11:59

Это не модификация String, это прямая операция с памятью (и еще и unsafe).

(хотя за пример все равно спасибо, он поучительный)

shai_hulud 29 авг 2012 в 12:52

Ну эта конструкция "(char*) str" в сишарпе имеет особое значение. т.к. строка это объект(а на reference типы пойнтеры обычно иметь нельзя), и строка не начинается с символов, а смысл конструкции «получить адрес объекта типа строка и обращаться к нему как символам», а на самом деле это разворачивается в «получить адрес первого символа строки и обращаться к нему как к символам».

т.е. это вполне «нормальная» конструкция к сишарпе, а не «еще и unsafe».

lair 29 авг 2012 в 13:10

т.е. это вполне «нормальная» конструкция к сишарпе, а не «еще и unsafe».

Эх.

internal static unsafe void wstrcpy(char* dmem, char* smem, int charCount)

Слово unsafe видите?

shai_hulud 29 авг 2012 в 13:31

отлично вижу, дак весь StringBuilder.ToString() является unsafe.
Но unsafe контекст не является отменой всех правил. Нельзя говорить «это unsafe, значит там может быть что угодно и стандартные правила .NET там не работают». Вам, к примеру, будут мешать получить поинтер на non-blittable объект т.к. это может привести к порче состояния рантайма.

shai_hulud 29 авг 2012 в 13:41

отлично вижу, да и весь StringBuilder.ToString() является unsafe.

Но unsafe контекст не является отменой всех правил. Нельзя говорить «это unsafe, значит там может быть что угодно и стандартные правила .NET там не работают». Вам, к примеру, будут мешать получить поинтер на non-blittable объект т.к. это может привести к порче состояния рантайма.

Вот это вполне нормальный код

fixed (char* str2 = ((char*) str)) *str2 = 'a'

может быть использован для быстрой сериализации/десериализации строк

AlexS 29 авг 2012 в 16:30

m_stringLength не использовался и был убран в последнем дотнете.

GraD_Kh 29 авг 2012 в 07:10

Объект — immutable, а вот ссылка может внезапно начать указывать на другой объект. Если другой поток поменяет значение ссылки — то разработчик, столкнувшийся с подобной оптимизацией, будет долго ругаться.

GraD_Kh 29 авг 2012 в 07:16

На самом деле деле я немного покривил душой, код, генерируемый компилятором может проводить оптимизации, которые некорректны в многопоточном окружении, именно для этого служат volatile, но как было сказано выше, c классом string не все так просто.

shai_hulud 29 авг 2012 в 07:19

Это не указатель на ссылку(ref string value), а просто ссылка, её извне поменять нельзя.

lair 29 авг 2012 в 07:54

а вот ссылка может внезапно начать указывать на другой объект

Каким образом? В методе она не меняется, а после передачи в метод поменять переданную ссылку никак нельзя. Это же не ref.

elw00d 29 авг 2012 в 08:28

Пусть String — immutable, но это только мы с вами знаем. CLR не знает, что String — immutable. И у CLR нет никаких гарантий на то, что возвращаемое методом (а геттер по сути — метод) значение не изменится. Да и даже если бы были такие атрибуты константности (как в С++)… По-моему, даже С++ с константными ссылками и константными функциями не производит такой оптимизации.

lair 29 авг 2012 в 08:39

CLR не знает, что String — immutable

Это утверждение, гм, спорно.

elw00d 29 авг 2012 в 11:52

То есть, на ваш взгляд, CLR именно для строк должна поддерживать специальную оптимизацию? По-моему, для CLR не должно быть разницы между классами. Либо должен быть способ пометить свой любой класс как immutable, либо иммутабельность конкретно класса String не должна приниматься во внимание.

lair 29 авг 2012 в 12:01

CLR именно для строк должна поддерживать специальную оптимизацию

CLR может это делать (и в ряде случае делает, смотрите на string interning).

knott 29 авг 2012 в 12:59

А чего вы видите плохого в оптимизации часто-используемого встроенного в BCL типа?

elw00d 29 авг 2012 в 13:34

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

xXxVano 29 авг 2012 в 14:38

В большинстве случаев эта оптимизация не требуется, т.к. большинство коллекций имеющих свойство Count на самом деле внутри него просто возвращают приватное поле, а JIT как известно при возможности инлайнит свойства. Поэтому для коллекций это будет просто чтение переменной. А вот для массивов и строк — это нативный вызов, так что вполне логично что JIT про них знает. Более того в масивах в случае простого for'а JIT даже проверку на границы массива за цикл выносит, для повышения производительности.

astudent 29 авг 2012 в 06:10

> Я считал, что компилятор (или же CLR) сможет понять, что так как внутри цикла мы не изменяем переменную s, то значение s.Length будет получено только один раз.
Вы правильно считали.
Если бы Вы запускали измерения в релизной сборке (с оптимизацией) без подключенного дебагера, то разницы бы не заметили от такого «улучшения»:
int length = s.Length;
for (int i = start; i < length; i++)

sashak 29 авг 2012 в 06:32

Занятная статья.

Интересно, будут ли меняться результаты вычислений в зависимости от версии .net?

it4_kp 29 авг 2012 в 06:33

MyConvert.ToInt( int.MinValue.ToString() )

не работает

SHTrassEr 29 авг 2012 в 06:49

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

По всей видимости, самым простым способом исправить этот косяк — это внести следующие исправления

    unsafe public static int ToInt(string s)
    {
            ....
            result = result * 10 - (ch - '0');
         .....
        return (isNegative) ? result : -result;
    }

SHTrassEr 29 авг 2012 в 06:57

Хотя в этом случае нужно проверять на переполнение после смены знака. То есть:

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

Yakhnev 29 авг 2012 в 07:22

Если посмотреть рефлектором код функций парсинга чисел, то все функции(и для double) всегда используют информацию о культуре и в итоге вызывают unsafe метод Number.ParseNumber, который умеет парсить и HEX числа, понимает символ валюты в конце, разделители тысяч, поэтому неудивительно, что код, анализирующий только цифры работает быстрее. Странно даже, что прирост всего лишь 40%, ведь тут даже нет удаления пробелов, почему Вы не выложили полный исходный код решения, чтобы можно было все проверить?

Mrrl 29 авг 2012 в 20:32

Прирост 40% потому, что int.ToString() работает в том же цикле для всех чисел. Если строки предварительно сохранить в массив, выигрыш будет около 7.5 раз.

s0rr0w 29 авг 2012 в 07:31

А как же экспоненциальная форма?
1.1E2 вполне себе int

B08AH 29 авг 2012 в 07:40

Кстати в string есть метод IndexOf, ищущий подстроку. Собственный велосипед работал раз в 10 быстрее, я тоже сокрушался, как же так. Потом тоже накопал про культур-мультур, оказалось, что если эту мультикультурность отключить, то CLR возвращает себе пальму. string.IndexOf(substring, StringComparison.Ordinal); работает раз в 40 быстрее, чем без параметра.

Посему есть подозрение, что если в int.TryParse поставить правильный NumberStyles, например System.Globalization.NumberStyles.Integer, для сабжевого случая, то результат сравнения будет другой, советую проверить.

KvanTTT 29 авг 2012 в 09:09

А вы точно пробовали запускать в релизи и без отладчика (Ctrl + F5) или просто .exe без студии?
Слабо верится, что компилятор не оптимизирует подобные моменты.

anarleen 29 авг 2012 в 09:11

А как вы все это компилировали перед запуском?
Релиз/Дебаг, AnyCPU/x64/x86?

Sauron 29 авг 2012 в 09:42

А стандартная функция только 10-чные числа поддерживает, или с разной базой?

Weageoo 29 авг 2012 в 11:41

Тест:

using System;
using System.Diagnostics;
using System.Globalization;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            const int count = 100000000;

            var test = int.MinValue.ToString();
            var res = default(int);


            res = int.Parse(test, NumberStyles.Integer);
            Console.WriteLine(res);

            var stopwatch = Stopwatch.StartNew();
            foreach (var _ in Enumerable.Range(0, count))
            {
                res = int.Parse(test);
            }
            stopwatch.Stop();

            Console.WriteLine(res);
            Console.WriteLine("int.Parse: {0} ms", stopwatch.ElapsedMilliseconds);


            res = ToInt(test);
            Console.WriteLine(res);

            stopwatch = Stopwatch.StartNew();
            foreach (var _ in Enumerable.Range(0, count))
            {
                res = ToInt(test);
            }
            stopwatch.Stop();

            Console.WriteLine(res);
            Console.WriteLine("ToInt: {0} ms", stopwatch.ElapsedMilliseconds);

            Console.ReadKey();
        }

        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++);
                switch (ch)
                {
                    case '-':
                        isNegative = true;
                        ch = *(chPtr++);
                        break;
                    case '+':
                        ch = *(chPtr++);
                        break;
                }
                do
                {
                    if (ch < '0' || ch > '9')
                    {
                        throw new ArgumentException();
                    }
                    result = result * 10 + (ch - '0');
                    ch = *(chPtr++);
                } while (ch != '\0');

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

Output release (запускал exe вручную):

-2147483648
-2147483648
int.Parse: 18884 ms
-2147483648
-2147483648
ToInt: 2905 ms

Прирост скорости: 550%

Output debug:

-2147483648
-2147483648
int.Parse: 17220 ms
-2147483648
-2147483648
ToInt: 11090 ms

Прирост скорости: 55%

IL-код для Release-версии:

using System;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
namespace ConsoleApplication1
{
	internal class Program
	{
		private static void Main()
		{
			string test = -2147483648.ToString();
			int res = 0;
			res = int.Parse(test, NumberStyles.Integer);
			Console.WriteLine(res);
			Stopwatch stopwatch = Stopwatch.StartNew();
			foreach (int arg_3F_0 in Enumerable.Range(0, 100000000))
			{
				res = int.Parse(test);
			}
			stopwatch.Stop();
			Console.WriteLine(res);
			Console.WriteLine("int.Parse: {0} ms", stopwatch.ElapsedMilliseconds);
			res = Program.ToInt(test);
			Console.WriteLine(res);
			stopwatch = Stopwatch.StartNew();
			foreach (int arg_AD_0 in Enumerable.Range(0, 100000000))
			{
				res = Program.ToInt(test);
			}
			stopwatch.Stop();
			Console.WriteLine(res);
			Console.WriteLine("ToInt: {0} ms", stopwatch.ElapsedMilliseconds);
			Console.ReadKey();
		}
		public unsafe 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* expr_20 = chPtr;
				chPtr = expr_20 + (IntPtr)2 / 2;
				char ch = *expr_20;
				switch (ch)
				{
					case '+':
					{
						char* expr_52 = chPtr;
						chPtr = expr_52 + (IntPtr)2 / 2;
						ch = *expr_52;
						break;
					}
					case '-':
					{
						isNegative = true;
						char* expr_47 = chPtr;
						chPtr = expr_47 + (IntPtr)2 / 2;
						ch = *expr_47;
						break;
					}
				}
				while (ch >= '0' && ch <= '9')
				{
					result = result * 10 + (int)(ch - '0');
					char* expr_78 = chPtr;
					chPtr = expr_78 + (IntPtr)2 / 2;
					ch = *expr_78;
					if (ch == '\0')
					{
						string text = null;
						if (!isNegative)
						{
							return result;
						}
						return -result;
					}
				}
				throw new ArgumentException();
			}
		}
	}
}

Weageoo 29 авг 2012 в 11:44

То есть не IL-код, а результат декомпиляции.

pletinsky 29 авг 2012 в 16:44

Вы точно не использовали debug mode для тестирования?

MichaelBorisov 29 авг 2012 в 18:25

Я когда-то анализировал код библиотеки C++, занимающийся поточным вводом-выводом. Это какой-то кошмар и мрак. Сложно и неэффективно. Возможно, положения стандарта трудно реализовать лучше, но тогда это уже вопрос к авторам стандарта — почему принимался именно такой стандарт. Все равно для серьезных целей, вроде парсинга языка программирования, разборщики чисел из стандартной библиотеки плохо подходят. Они капризные, их поведение меняется от версии к версии и стандартом жестко не задано; отсутствует диагностика ошибок. Вдобавок, когда ввели интернационализацию формата чисел в стандартных библиотеках — это сломало мои программы загрузки данных из текстовых файлов или разбора командной строки. Пришлось все перекомпилировать, вставляя где надо инициализацию национального формата чисел.

Один знакомый программист, который разрабатывает серверное п/о, рассказывал, что ему приходится оптимизировать парсеры текста вплоть до перевода их на ассемблер с использованием SIMD-инструкций. Что такая оптимизация дает существенный прирост быстродействия, и для серверного п/о это важно.

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

lair 29 авг 2012 в 18:36

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

Вы точно про .net говорите? А то там-то поведение int.Parse формализуется весьма строго.

Один знакомый программист, который разрабатывает серверное п/о, рассказывал, что ему приходится оптимизировать парсеры текста вплоть до перевода их на ассемблер с использованием SIMD-инструкций. Что такая оптимизация дает существенный прирост быстродействия, и для серверного п/о это важно.

Интересно, какого именно серверного ПО он разработчик. А то я что-то пока ни разу не видел, чтобы в традиционном корпоративном (т.е., прикладном) серверном ПО потери на int.Parse превышали накладные расходы на подъем обработчика или запрос в БД.

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

Ну так это, FxCop не зря пишет: «CA1305: Specify IFormatProvider»

MichaelBorisov 29 авг 2012 в 20:30

Нет, я вел речь о C++.

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

lair 29 авг 2012 в 21:12

Нет, я вел речь о C++.

Ну, я хочу заметить, что в .net ситуация несколько другая.

Mrrl 29 авг 2012 в 20:28

Мой вариант:

        static int ToInt(string x) {
            bool qd=true;
            int n=0,s=-5,qs=1;
            foreach(char c in x) {
                int m=c-'0';
                if((uint)m<10) {
                    n=(n*10+m);
                    qd=false;
                } else s=m*qs;
                qs=0;
            }
            if(qd || (s!=-3 && s!=-5)) throw new ArgumentException();
            return (-4-s)*n;
        }

еще чуть-чуть быстрее. По ходу написания обнаружилось, что:
— foreach по строке работает намного быстрее, чем вариант с fixed char*;
— в C# умножение целых чисел несколько быстрее логических (битовых) операций.

Joshua 30 авг 2012 в 10:44

Изящно.

vmysla 18 сен 2012 в 02:36

действительно круто,
но мне как читателю — было «не прозрачно» въехать:

1. нет комментария — 1шт.
2. магические числа — 3шт.
3. именование переменных

благо, charmap и calc сделали свое дело
вы или математик или специально так сделали)

Mrrl 20 сен 2012 в 21:45

Я математик. И сделал специально, чтобы читатели поломали голову, при чем тут -4 и как это может вообще работать :) Но, в сущности, это не сложнее, чем Hello World на брейнфаке, там коды символов используются гораздо активнее.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий