Comments 58
Смотря где, смотря где. В каком нибудь AVR в этой конвертации за каждый байт бьешься.
А как быстро будет работать такой вариант, в сравнении с вашим?
Источник
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;
}
Источник
Точно, совсем забыл про вариант с плюсом, спасибо, сейчас исправлю.
Предложенный вами вариант быстрее моего в среднем на 6,8%. Однако в этом варианте немного другая логика: убираются ведущие пробелы, и нет проверки на входной параметр (пустая строка преобразуется в 0, «12b» преобразуется в 12). Хотя если даже добавить такую проверку, то все равно она будет работать быстрее, в среднем на 5%.
проверялся следующий код:
Предложенный вами вариант быстрее моего в среднем на 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;
}
Тогда уж по вашим условиям лучше написать так:
Дополнительный case не нужен, потому что если строка пустая, не выполнятся условия в switch и while и оно сразу перейдет к условию и выкинет исключение.
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 и оно сразу перейдет к условию и выкинет исключение.
Помогал на днях одной своей знакомой разобраться в программировании
Как сейчас все сложно. В мое время, что бы произвести впечатление на девушку, достаточно было уметь винду переустанавливать :-)
В вашем методе затаился баг: число +123 не распознается.
Прогрев был? Всё таки, одна и функций грузится из сборки, а вторая уже загружена.
Ассемблерную вставку делать не пробовали, раз уж на то пошло?
Я считал, что компилятор (или же CLR) сможет понять, что так как внутри цикла мы не изменяем переменную s, то значение s.Length будет получено только один раз.
Дело в том, что это не локальная переменная внутри функции (жизненный цикл которой JIT-компилятор может отследить), а проперти стороннего объекта. JIT-компилятор не может гарантировать, что значение, возвращаемое этим свойством (по сути являющимся вызовом метода) не изменится на следующей итерации цикла (вдруг другой поток его меняет, или код внутри цикла неявно взаимодействует с тем объектом ?). Поэтому естественно, что нужно кешировать такие вещи в локальной переменной вручную.
Вообще, это архистранно, потому что мы-то знаем, что string — immutable. И компилятор знает. Так что это значение не может измениться.
Это вы в книжке прочитали. А на самом деле строка может быть изменена(к примеру StringBuilder изменяет строки). Так что у оптимизатора нет гарантии. Другое дело это длинна массива.
А на самом деле строка может быть изменена(к примеру StringBuilder изменяет строки).
Это, простите, как?
Если что, StringBuilder работает с буфером символов вообще.
Ну к примеру:
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, которые имеют динамический размер.
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, которые имеют динамический размер.
Это не модификация String, это прямая операция с памятью (и еще и unsafe).
(хотя за пример все равно спасибо, он поучительный)
(хотя за пример все равно спасибо, он поучительный)
Ну эта конструкция "(char*) str" в сишарпе имеет особое значение. т.к. строка это объект(а на reference типы пойнтеры обычно иметь нельзя), и строка не начинается с символов, а смысл конструкции «получить адрес объекта типа строка и обращаться к нему как символам», а на самом деле это разворачивается в «получить адрес первого символа строки и обращаться к нему как к символам».
т.е. это вполне «нормальная» конструкция к сишарпе, а не «еще и unsafe».
т.е. это вполне «нормальная» конструкция к сишарпе, а не «еще и unsafe».
т.е. это вполне «нормальная» конструкция к сишарпе, а не «еще и unsafe».
Эх.
internal static unsafe void wstrcpy(char* dmem, char* smem, int charCount)
Слово unsafe видите?
отлично вижу, дак весь StringBuilder.ToString() является unsafe.
Но unsafe контекст не является отменой всех правил. Нельзя говорить «это unsafe, значит там может быть что угодно и стандартные правила .NET там не работают». Вам, к примеру, будут мешать получить поинтер на non-blittable объект т.к. это может привести к порче состояния рантайма.
Но unsafe контекст не является отменой всех правил. Нельзя говорить «это unsafe, значит там может быть что угодно и стандартные правила .NET там не работают». Вам, к примеру, будут мешать получить поинтер на non-blittable объект т.к. это может привести к порче состояния рантайма.
отлично вижу, да и весь StringBuilder.ToString() является unsafe.
Но unsafe контекст не является отменой всех правил. Нельзя говорить «это unsafe, значит там может быть что угодно и стандартные правила .NET там не работают». Вам, к примеру, будут мешать получить поинтер на non-blittable объект т.к. это может привести к порче состояния рантайма.
Вот это вполне нормальный код
fixed (char* str2 = ((char*) str)) *str2 = 'a'
может быть использован для быстрой сериализации/десериализации строк
Но unsafe контекст не является отменой всех правил. Нельзя говорить «это unsafe, значит там может быть что угодно и стандартные правила .NET там не работают». Вам, к примеру, будут мешать получить поинтер на non-blittable объект т.к. это может привести к порче состояния рантайма.
Вот это вполне нормальный код
fixed (char* str2 = ((char*) str)) *str2 = 'a'
может быть использован для быстрой сериализации/десериализации строк
m_stringLength не использовался и был убран в последнем дотнете.
Объект — immutable, а вот ссылка может внезапно начать указывать на другой объект. Если другой поток поменяет значение ссылки — то разработчик, столкнувшийся с подобной оптимизацией, будет долго ругаться.
На самом деле деле я немного покривил душой, код, генерируемый компилятором может проводить оптимизации, которые некорректны в многопоточном окружении, именно для этого служат volatile, но как было сказано выше, c классом string не все так просто.
Это не указатель на ссылку(ref string value), а просто ссылка, её извне поменять нельзя.
а вот ссылка может внезапно начать указывать на другой объект
Каким образом? В методе она не меняется, а после передачи в метод поменять переданную ссылку никак нельзя. Это же не ref.
Пусть String — immutable, но это только мы с вами знаем. CLR не знает, что String — immutable. И у CLR нет никаких гарантий на то, что возвращаемое методом (а геттер по сути — метод) значение не изменится. Да и даже если бы были такие атрибуты константности (как в С++)… По-моему, даже С++ с константными ссылками и константными функциями не производит такой оптимизации.
CLR не знает, что String — immutable
Это утверждение, гм, спорно.
То есть, на ваш взгляд, CLR именно для строк должна поддерживать специальную оптимизацию? По-моему, для CLR не должно быть разницы между классами. Либо должен быть способ пометить свой любой класс как immutable, либо иммутабельность конкретно класса String не должна приниматься во внимание.
CLR именно для строк должна поддерживать специальную оптимизацию
CLR может это делать (и в ряде случае делает, смотрите на string interning).
А чего вы видите плохого в оптимизации часто-используемого встроенного в BCL типа?
Ничего плохого не вижу. Вообще мы не про строки говорили изначально, а о конкретном случае оптимизации выполнения цикла. И до сих пор я так и не получил доказательств того, что значение свойства Length строки может быть закешировано CLR, несмотря на особый статус строк и их иммутабельность. Поэтому мне кажется эта возможность сомнительной. Ну и основное, я считаю, — это не то, как CLR работает со строками, а то, как она работает со всеми остальными классами.
В большинстве случаев эта оптимизация не требуется, т.к. большинство коллекций имеющих свойство Count на самом деле внутри него просто возвращают приватное поле, а JIT как известно при возможности инлайнит свойства. Поэтому для коллекций это будет просто чтение переменной. А вот для массивов и строк — это нативный вызов, так что вполне логично что JIT про них знает. Более того в масивах в случае простого for'а JIT даже проверку на границы массива за цикл выносит, для повышения производительности.
> Я считал, что компилятор (или же CLR) сможет понять, что так как внутри цикла мы не изменяем переменную s, то значение s.Length будет получено только один раз.
Вы правильно считали.
Если бы Вы запускали измерения в релизной сборке (с оптимизацией) без подключенного дебагера, то разницы бы не заметили от такого «улучшения»:
int length = s.Length;
for (int i = start; i < length; i++)
Вы правильно считали.
Если бы Вы запускали измерения в релизной сборке (с оптимизацией) без подключенного дебагера, то разницы бы не заметили от такого «улучшения»:
int length = s.Length;
for (int i = start; i < length; i++)
Занятная статья.
Интересно, будут ли меняться результаты вычислений в зависимости от версии .net?
Интересно, будут ли меняться результаты вычислений в зависимости от версии .net?
MyConvert.ToInt( int.MinValue.ToString() )
не работает
Эх, все надо тестировать.
Действительно, int.MinValue по модулю на единицу больше, чем int.MaxValue. А так как в промежуточном вычислении в качестве буфера используется положительный диапазон от int, то int.MinValue в него не входит.
По всей видимости, самым простым способом исправить этот косяк — это внести следующие исправления
Действительно, int.MinValue по модулю на единицу больше, чем int.MaxValue. А так как в промежуточном вычислении в качестве буфера используется положительный диапазон от int, то int.MinValue в него не входит.
По всей видимости, самым простым способом исправить этот косяк — это внести следующие исправления
unsafe public static int ToInt(string s)
{
....
result = result * 10 - (ch - '0');
.....
return (isNegative) ? result : -result;
}
Если посмотреть рефлектором код функций парсинга чисел, то все функции(и для double) всегда используют информацию о культуре и в итоге вызывают unsafe метод Number.ParseNumber, который умеет парсить и HEX числа, понимает символ валюты в конце, разделители тысяч, поэтому неудивительно, что код, анализирующий только цифры работает быстрее. Странно даже, что прирост всего лишь 40%, ведь тут даже нет удаления пробелов, почему Вы не выложили полный исходный код решения, чтобы можно было все проверить?
А как же экспоненциальная форма?
1.1E2 вполне себе int
1.1E2 вполне себе int
Кстати в string есть метод IndexOf, ищущий подстроку. Собственный велосипед работал раз в 10 быстрее, я тоже сокрушался, как же так. Потом тоже накопал про культур-мультур, оказалось, что если эту мультикультурность отключить, то CLR возвращает себе пальму. string.IndexOf(substring, StringComparison.Ordinal); работает раз в 40 быстрее, чем без параметра.
Посему есть подозрение, что если в int.TryParse поставить правильный NumberStyles, например System.Globalization.NumberStyles.Integer, для сабжевого случая, то результат сравнения будет другой, советую проверить.
Посему есть подозрение, что если в int.TryParse поставить правильный NumberStyles, например System.Globalization.NumberStyles.Integer, для сабжевого случая, то результат сравнения будет другой, советую проверить.
А вы точно пробовали запускать в релизи и без отладчика (Ctrl + F5) или просто .exe без студии?
Слабо верится, что компилятор не оптимизирует подобные моменты.
Слабо верится, что компилятор не оптимизирует подобные моменты.
А как вы все это компилировали перед запуском?
Релиз/Дебаг, AnyCPU/x64/x86?
Релиз/Дебаг, AnyCPU/x64/x86?
А стандартная функция только 10-чные числа поддерживает, или с разной базой?
Тест:
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
{
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();
}
}
}
}
Вы точно не использовали debug mode для тестирования?
Я когда-то анализировал код библиотеки C++, занимающийся поточным вводом-выводом. Это какой-то кошмар и мрак. Сложно и неэффективно. Возможно, положения стандарта трудно реализовать лучше, но тогда это уже вопрос к авторам стандарта — почему принимался именно такой стандарт. Все равно для серьезных целей, вроде парсинга языка программирования, разборщики чисел из стандартной библиотеки плохо подходят. Они капризные, их поведение меняется от версии к версии и стандартом жестко не задано; отсутствует диагностика ошибок. Вдобавок, когда ввели интернационализацию формата чисел в стандартных библиотеках — это сломало мои программы загрузки данных из текстовых файлов или разбора командной строки. Пришлось все перекомпилировать, вставляя где надо инициализацию национального формата чисел.
Один знакомый программист, который разрабатывает серверное п/о, рассказывал, что ему приходится оптимизировать парсеры текста вплоть до перевода их на ассемблер с использованием SIMD-инструкций. Что такая оптимизация дает существенный прирост быстродействия, и для серверного п/о это важно.
Так что собственноручно написанные разборщики чисел — это далеко не учебная задача. Их приходится делать при создании компиляторов, парсеров для текстовых форматов файлов или текстовых протоколов передачи данных.
Один знакомый программист, который разрабатывает серверное п/о, рассказывал, что ему приходится оптимизировать парсеры текста вплоть до перевода их на ассемблер с использованием SIMD-инструкций. Что такая оптимизация дает существенный прирост быстродействия, и для серверного п/о это важно.
Так что собственноручно написанные разборщики чисел — это далеко не учебная задача. Их приходится делать при создании компиляторов, парсеров для текстовых форматов файлов или текстовых протоколов передачи данных.
Все равно для серьезных целей, вроде парсинга языка программирования, разборщики чисел из стандартной библиотеки плохо подходят. Они капризные, их поведение меняется от версии к версии и стандартом жестко не задано; отсутствует диагностика ошибок.
Вы точно про .net говорите? А то там-то поведение int.Parse формализуется весьма строго.
Один знакомый программист, который разрабатывает серверное п/о, рассказывал, что ему приходится оптимизировать парсеры текста вплоть до перевода их на ассемблер с использованием SIMD-инструкций. Что такая оптимизация дает существенный прирост быстродействия, и для серверного п/о это важно.
Интересно, какого именно серверного ПО он разработчик. А то я что-то пока ни разу не видел, чтобы в традиционном корпоративном (т.е., прикладном) серверном ПО потери на int.Parse превышали накладные расходы на подъем обработчика или запрос в БД.
Вдобавок, когда ввели интернационализацию формата чисел в стандартных библиотеках — это сломало мои программы загрузки данных из текстовых файлов или разбора командной строки. Пришлось все перекомпилировать, вставляя где надо инициализацию национального формата чисел.
Ну так это, FxCop не зря пишет: «CA1305: Specify IFormatProvider»
Нет, я вел речь о C++.
Какое именно ПО — он рассказывал о сервере онлайн-рекламы, который должен быстро отвечать на запросы. Говорил, что разбор текстовых протоколов передачи данных занимает существенную часть времени, требуемого на формирование ответа, и поэтому оптимизация такого разбора себя оправдывает. Подробности мне неизвестны; за что купил — за то и продаю.
Какое именно ПО — он рассказывал о сервере онлайн-рекламы, который должен быстро отвечать на запросы. Говорил, что разбор текстовых протоколов передачи данных занимает существенную часть времени, требуемого на формирование ответа, и поэтому оптимизация такого разбора себя оправдывает. Подробности мне неизвестны; за что купил — за то и продаю.
Мой вариант:
еще чуть-чуть быстрее. По ходу написания обнаружилось, что:
— foreach по строке работает намного быстрее, чем вариант с fixed char*;
— в C# умножение целых чисел несколько быстрее логических (битовых) операций.
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# умножение целых чисел несколько быстрее логических (битовых) операций.
Sign up to leave a comment.
Конвертация строки в число