Проблема производительности C ++: преобразование целых чисел в std :: string - PullRequest
Новая
       80

Проблема производительности C ++: преобразование целых чисел в std :: string

118 голосов
/ 04 декабря 2010

Может ли кто-нибудь побить производительность моего целого числа до кода std :: string, связанного ниже?

Уже есть несколько вопросов, объясняющих, как преобразовать целое число в std::stringв C ++, например , это , но ни одно из предоставленных решений не является эффективным.

Вот код, готовый к компиляции, для некоторых распространенных методов, с которыми можно конкурировать:

  • "C ++ way", использующий stringstream: http://ideone.com/jh3Sa
  • sprintf, который обычно рекомендуют SO для тех, кто заботится о производительности: http://ideone.com/82kwR

В отличие от распространенное мнение , boost::lexical_cast имеет собственную реализацию ( white paper ) и не использует stringstream и числовые операторы вставки.Я действительно хотел бы сравнить его производительность, потому что этот другой вопрос предполагает, что он жалок .

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

Если вы хотите использовать этот код, я 'Я сделаю его доступным по упрощенной лицензии BSD (разрешено коммерческое использование, требуется указание авторства).Просто спросите.

Наконец, функция ltoa является нестандартной, но широко доступной.

  • ltoa-версия для тех, у кого есть компилятор, который ее предоставляет (ideone не делает): http://ideone.com/T5Wim

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

Правила для алгоритмов

  • Укажите код для преобразованияне менее 32-разрядных целых чисел со знаком и без знака в десятичное число.
  • Выводит в виде std::string.
  • Нет трюков, несовместимых с потоками и сигналами (например, статические буферы).
  • Вы можете принять набор символов ASCII.
  • Обязательно протестируйте свой код на INT_MIN на машине с двумя дополнительными символами, где абсолютное значение не представимо.
  • В идеале,вывод должен быть посимвольным, идентичным канонической версии C ++ с использованием stringstream, http://ideone.com/jh3Sa,, но все, что понятно для правильного числа, тоже в порядке.
  • NEW : хотя вы можете использовать WНезависимо от того, какие параметры компилятора и оптимизатора (кроме полностью отключенных) вы хотите использовать для сравнения, код также должен компилироваться и давать правильные результаты как минимум в соответствии с VC ++ 2010 и g ++.

Надеемся на обсуждение

Помимо более совершенных алгоритмов, я также хотел бы получить некоторые тесты для нескольких различных платформ и компиляторов (давайте используем пропускную способность МБ / с в качестве нашей стандартной единицы измерения).Я полагаю, что код для моего алгоритма (я знаю, что для теста sprintf используются некоторые ярлыки - теперь он исправлен) - это четко определенное поведение по стандарту, по крайней мере в предположении ASCII, но если вы видите какое-либо неопределенное поведение или входные данные длякоторый вывод является недействительным, пожалуйста, укажите это.

Выводы:

Различные алгоритмы работают для g ++ и VC2010, вероятно, из-за различных реализаций std::string на каждом.VC2010 явно лучше справляется с NRVO, избавляясь от возврата по значению, помогая только в gcc.

Обнаружен код, превосходящий sprintf на порядок.ostringstream отстает в 50 и более раз.

Победителем соревнования является user434507, который создает код, который выполняет 350% моей скорости на gcc.Дальнейшие записи закрыты из-за прихотей сообщества SO.

Текущие (окончательные?) Рекордсмены по скорости:

Ответы [ 12 ]

0 голосов
/ 28 февраля 2014

Модификация для решения user434507. Изменено использование массива символов вместо строки C ++. Работает немного быстрее. Также перенес проверку на 0 ниже в коде ... как это никогда не происходит в моем конкретном случае. Переместите его назад, если оно более распространено в вашем случае. 

// Int2Str.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <iostream>
#include "StopWatch.h"

using namespace std;

const char digit_pairs[201] = {
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899"
};

void itostr(int n, char* c) {
    int sign = -(n<0);
    unsigned int val = (n^sign)-sign;

    int size;
    if(val>=10000) {
        if(val>=10000000) {
            if(val>=1000000000) {
                size=10;
            }
            else if(val>=100000000) {
                size=9;
            }
            else size=8;
        }
        else {
            if(val>=1000000) {
                size=7;
            }
            else if(val>=100000) {
                size=6;
            }
            else size=5;
        }
    }
    else {
        if(val>=100) {
            if(val>=1000) {
                size=4;
            }
            else size=3;
        }
        else {
            if(val>=10) {
                size=2;
            }
            else if(n==0) {
                c[0]='0';
                c[1] = '\0';
                return;
            }
            else size=1;
        }
    }
    size -= sign;
    if(sign)
    *c='-';

    c += size-1;
    while(val>=100) {
        int pos = val % 100;
        val /= 100;
        *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
        c-=2;
    }
    while(val>0) {
        *c--='0' + (val % 10);
        val /= 10;
    }
    c[size+1] = '\0';
}

void itostr(unsigned val, char* c)
{
    int size;
    if(val>=10000)
    {
        if(val>=10000000)
        {
            if(val>=1000000000)
                size=10;
            else if(val>=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(val>=1000000)
                size=7;
            else if(val>=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(val>=100)
        {
            if(val>=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(val>=10)
                size=2;
            else if (val==0) {
                c[0]='0';
                c[1] = '\0';
                return;
            }
            else
                size=1;
        }
    }

    c += size-1;
    while(val>=100)
    {
       int pos = val % 100;
       val /= 100;
       *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
       c-=2;
    }
    while(val>0)
    {
        *c--='0' + (val % 10);
        val /= 10;
    }
    c[size+1] = '\0';
}

void test() {
    bool foundmismatch = false;
    char str[16];
    char compare[16];
    for(int i = -1000000; i < 1000000; i++) {
        int random = rand();
        itostr(random, str);
        itoa(random, compare, 10);
        if(strcmp(str, compare) != 0) {
            cout << "Mismatch found: " << endl;
            cout << "Generated: " << str << endl;
            cout << "Reference: " << compare << endl;
            foundmismatch = true;
        }
    }
    if(!foundmismatch) {
        cout << "No mismatch found!" << endl;
    }
    cin.get();
}

void benchmark() {
    StopWatch stopwatch;
    stopwatch.setup("Timer");
    stopwatch.reset();
    stopwatch.start();
    char str[16];
    for(unsigned int i = 0; i < 2000000; i++) {
        itostr(i, str);
    }
    stopwatch.stop();
    cin.get();
}

int main( int argc, const char* argv[]) {
    benchmark();
}
0 голосов
/ 15 января 2013

Почему никто не использует функцию div из stdlib, когда требуются и коэффициент, и остаток?Используя исходный код Тимо, я получил что-то вроде этого: 

if(val >= 0)
{
    div_t   d2 = div(val,100);
    while(d2.quot)
    {
        COPYPAIR(it,2 * d2.rem);
        it-=2;
        d2 = div(d2.quot,100);
    }
    COPYPAIR(it,2*d2.rem);
    if(d2.quot<10)
        it++;
}
else
{
    div_t   d2 = div(val,100);
    while(d2.quot)
    {
        COPYPAIR(it,-2 * d2.rem);
        it-=2;
        d2 = div(d2.quot,100);
    }
    COPYPAIR(it,-2*d2.rem);
    if(d2.quot<=-10)
        it--;
    *it = '-';
}

Хорошо, для беззнаковых целых, функция div не может использоваться, но беззнаковые могут обрабатываться отдельно.Я определил макрос COPYPAIR следующим образом, чтобы проверить варианты, как скопировать 2 символа из digit_pairs (не обнаружил очевидного преимущества любого из этих методов): 

#define COPYPAIR0(_p,_i) { memcpy((_p), &digit_pairs[(_i)], 2); }
#define COPYPAIR1(_p,_i) { (_p)[0] = digit_pairs[(_i)]; (_p)[1] = digit_pairs[(_i)+1]; }
#define COPYPAIR2(_p,_i) { unsigned short * d = (unsigned short *)(_p); unsigned short * s = (unsigned short *)&digit_pairs[(_i)]; *d = *s; }

#define COPYPAIR COPYPAIR2
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...