Должен ли я накатить свою собственную версию ParseInt32?

Question

Я пишу высокопроизводительный синтаксический анализатор, и мне кажется, что Int32.Parse может быть слишком медленным. Я написал простую версию, которая предполагает правильный ввод, и она работает намного лучше. Так я должен создать свою собственную версию вместо этого? Или уже есть другой, более быстрый метод?

Мой метод такой:

// parse simple int, assuming relatively correct input (i.e. all digits)
public static int ParseInt32Simply(string str) {
    if (str == null) throw new ArgumentNullException("str");
    if (str.Length == 0) throw new ArgumentException("str is empty");

    int sign = 1, index = 0;
    if (str[0] == '-') { sign = -1; index = 1; }
    else if (str[0] == '+') { index = 1; }

    int result = 0;
    for (; index < str.Length; ++index) {
        result = 10 * result + (str[index] - '0');
    }

    if (result < 0) throw new OverflowException(str + " is too large for Int32");

    return result * sign;
}

Мои результаты сильно отличаются от встроенного эквивалента:

Int32.Parse      took 8.2775453 seconds
ParseInt32Simply took 0.6511523 seconds
Int32.Parse      took 6.7625807 seconds
ParseInt32Simply took 0.4677390 seconds

(Выполнение 25 миллионов итераций на моей машине; P4 3 ГГц с VS 2008 SP1)

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

Answer 1

Вы уже профилировали свой код, чтобы определить, что ParseInt32 на самом деле является узким местом? Я бы не стал заменять то, что входит в «стандартную библиотеку» среды, в которой вы кодируете, если вы не уверены наверняка, что получите выгоду.

Answer 2

In .net Int32.Parse очень очень быстро, когда это успешно.

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

Вам нужно расширить свой тест - вам нужно проверить время для последовательности хороших и плохих строк, которая похожа на то, что вам нужно сделать.

Если вы уверены, что все ваши строки являются действительными целочисленными значениями, тогда Int32.Parse - это то, что вам нужно. Если вы подозреваете, что допустимым будет немногим более незначительного числа, то гораздо быстрее использовать Int32.TryParse, чем try-catch в вашем цикле.

Обычно, если ваш try-catch находится за пределами цикла, используйте Int32.Parse - вы получите исключение и остановитесь, когда в первый раз получите недопустимое значение.

Если ваш try-catch находится внутри цикла, используйте Int32.TryParse.

Оба Int32.Parse и Int32.TryParse довольно высокооптимизированы и относительно зрелы - я ожидаю, что их будет очень сложно улучшить, если у вас нет особых обстоятельств.

Answer 3

Если ваши тесты поддаются проверке, и вам действительно нужно повышение производительности (например, вы вызываете функцию десятки тысяч раз в секунду), чем идти на это.

Я бы просто изменил имя ... потому что ParseInt32Simply ничего не говорит программисту по обслуживанию. Я думаю, что имя типа TrustedSourceInt32Parse или GuaranteedInt32Parse или что-то в этом роде является лучшим именем.

Answer 4

Да - вы можете использовать собственную версию синтаксического анализа int до тех пор, пока вы на 100% уверены, что исходные данные находятся под вашим контролем (и, следовательно, всегда соответствуют вашему формату Int32). Кроме того, вы должны использовать свой собственный код, изолированный от остального мира, потому что, если у вас есть это в какой-то публикуемой вами библиотеке, люди могут захотеть иметь стандартное поведение Int32.Parse. Если вы не можете предоставить это, это не хорошо для них. Однако, как полагают многие, вы должны быть уверены, что это то, что действительно нужно делать, если вы пытаетесь выжать большую часть своей производительности. Тем не менее, вы, вероятно, знаете свой собственный код лучше, чем кто-либо здесь.

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

Answer 5

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

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

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

Answer 6

Я думаю, что главная проблема здесь в вашем предложении предполагает правильный ввод . После прочтения вашего кода он не может правильно обрабатывать «12x».

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

Вы уверены, что узким местом является Int32 в вашем коде?

Answer 7

Посмотрите на эту запись в блоге: Быстрое преобразование строки в целое число . Автор Karl Seguin.

Answer 8

Если вы анализируете формат, который, как вы знаете, являются действительными числами, вы действительно можете написать более быстрый пользовательский анализатор. Я однажды написал функцию Double.Parse для той же цели. И это быстрее начать с наименее значимой цифры. Таким образом, вы можете просто увеличить мощность разряда при разборе.

Я создал быструю реализацию этого,

public static Int32 ParseValidNumberAsInt32(string str)
{
    if (str == null) 
        throw new ArgumentNullException("str");
    if (str.Length == 0) 
        throw new ArgumentException("str is empty");
    Int32 result = 0;
    Int32 currentPower = 1;
    Boolean isNegative = str[0] == '-';

    for (int currentCharIndex = str.Length - 1; currentCharIndex > 0; currentCharIndex--)
    {
        result += (str[currentCharIndex] - '0') * currentPower;
        currentPower *= 10;
    }
    return isNegative ? -1 * result : result + ((str[0] - '0') * currentPower);
}

Если вам действительно нужна скорость, вы можете написать небезопасную реализацию.

Если вы анализируете большой файл, вы можете читать файлы как необработанные байты и работать с ними. Это сделает его намного быстрее (без преобразования в строку в юникоде, без разделения строк по строкам, без разделения строк в подстроках, без анализа подстрок), но вы потеряете удобство сопровождения.

Answer 9

Как вы измеряете скорость? Я попробовал это:

Stopwatch sw = new Stopwatch();
Random rand = new Random();

for (int n = 0; n < 10; n++)
{
    sw.Start();
    for (int i = 0; i < 1000000; i++)
    {
        ParseInt32Simply(rand.Next().ToString());
    }
    sw.Stop();
    Console.WriteLine(sw.Elapsed.Ticks + " - ParseInt32Simply");
    sw.Reset();

    sw.Start();
    for (int i = 0; i < 1000000; i++)
    {
        int.Parse(rand.Next().ToString());
    }
    sw.Stop();
    Console.WriteLine(sw.Elapsed.Ticks + " - int.Parse");
    sw.Reset();
    Console.WriteLine();
}

и результаты совсем другие:

2932852 - ParseInt32Просто
4684522 - Int.Parse

3003988 - ParseInt32Просто
4666928 - int.Parse

2892545 - ParseInt32Simply
4660209 - Int.Parse

2888998 - ParseInt32Simply
4636007 - int.Parse

2955727 - ParseInt32Simply
4668501 - Int.Parse

2929210 - ParseInt32Simply
4653799 - Int.Parse

2893706 - ParseInt32Simply
4671503 - Int.Parse

2899547 - ParseInt32Simply
4633957 - Int.Parse

Ваш простой метод все еще быстрее, но менее чем в 2 раза (на самом деле это очень хорошая производительность!).

Answer 10

как выглядит ваш тест? Кажется, ваш тест не в порядке.

У меня есть небольшая разница, когда я повторяю 50000 раз и тогда у меня есть разница около 30 тыс. тиков в пользу вашего пользовательского метода, но это пренебрегает преимуществами обычного метода