C++ Самая быстрая числовая строка для длинного синтаксического анализа
Вот что я придумал.
lenгарантированно имеет значимое значение (положительный и истинный размер массива символов)s- это длинное число без знака в виде строки без нулевого завершения (полученной из сторонней библиотеки), обычно 11-12 символов, например. "123456789000"- работает на х86 линуксе
Я не C++ разработчик, не могли бы вы помочь сделать быстрее?
inline uint64_t strtol(char* s, int len)
{
uint64_t val = 0;
for (int i = 0; i < len; i++)
{
char c = *(s + i) - '0';
val = val * 10 + c;
}
return val;
};
Это примерно так быстро, как вы можете получить. Все стандартные функции требуют строки с завершающим нулем или std::string, и их построение занимает примерно столько же времени, сколько просто запуск этой функции. Вы уверены, что это те функции, которые нужно улучшить? Вы использовали профилировщик, чтобы определить, что эта функция замедляет ваш код?
@ 463035818_is_not_a_number Для этого требуется строка с нулевым завершением, которой нет у OP.
Это не все, что связано с C++. На данный момент вы смотрите на сборку. Кстати, так и должно быть const char*.
Я сомневаюсь, что эта функция может быть узким местом. Чтение памяти из char* скорее всего.
Обратите внимание, что inline, вероятно, здесь ничего не делает. Компилятор встраивает функции, которые он хочет встроить, и для большинства компиляторов наличие или отсутствие ключевого слова игнорируется. Я бы также сделал sconst char* s, это просто упрощает использование функции и неявно разъясняет использование.
@FrançoisAndrieux inline действительно что-то делает, просто не контролирует оптимизацию встраивания. Если функция определена в заголовочном файле, inline равно требуется, чтобы избежать множественных ошибок определения.
Вы можете уточнить, почему вы хотите, чтобы это было быстрее? Как быстро сейчас? Как быстро вам это нужно? Если вы просто ищете быстрый, потому что быстрый это хорошо, тогда используйте что-то из стандартной библиотеки. Обычно его сложно превзойти по производительности, накатывая собственный
что я имею в виду: вы должны уточнить вопрос. Вы ищете способ получить целое число из строки или вам нужен именно этот код, чтобы работать быстрее? Если это последнее, вы могли бы объяснить больше
@OP Пожалуйста, поймите, что код, который вы пишете, - это только описание того, что вы хотите. Оптимизатор компилятора вступает во владение и, скорее всего, изменит ваш код так, что он будет очень мало похож на код, который вы разместили. Таким образом, вам нужно посмотреть на сгенерированный язык ассемблера после выполнения оптимизации и сделать выводы из этого кода.
@AlanBirtles Может быть, мне следовало указать, что это ничего не делает в отношении заявленной цели «сделать это быстрее». Но я думал, что это подразумевается, учитывая контекст.
SIMD и std::from_chars были бы почти самым быстрым способом: Самый безумно быстрый способ преобразовать 9 цифр char в int или unsigned int, Как реализовать atoi с помощью SIMD?
Ответы 1
Возможно, вы захотите взглянуть на развертывание цикла. Когда тело цикла достаточно короткое, проверка условия цикла на каждой итерации может быть относительно дорогой.
Специфический и интересный способ реализации развертывания цикла называется устройством Даффа: https://en.wikipedia.org/wiki/Duff%27s_device.
Вот версия для вашей функции:
inline uint64_t strtol_duff(char* s, int len)
{
uint64_t val = 0;
int n = (len + 7) / 8;
int i = 0;
switch (len % 8) {
case 0: do {
val = val * 10 + (*(s + i++) - '0');
case 7: val = val * 10 + (*(s + i++) - '0');
case 6: val = val * 10 + (*(s + i++) - '0');
case 5: val = val * 10 + (*(s + i++) - '0');
case 4: val = val * 10 + (*(s + i++) - '0');
case 3: val = val * 10 + (*(s + i++) - '0');
case 2: val = val * 10 + (*(s + i++) - '0');
case 1: val = val * 10 + (*(s + i++) - '0');
} while (--n > 0);
}
return val;
};
Честно говоря, я считаю, что в вашем случае вы не увидите огромной выгоды, потому что тело цикла не такое уж маленькое. Все это очень сильно зависит от системы и требует экспериментов (как и большинство оптимизаций). Хорошие оптимизаторы компилятора могут автоматически разворачивать цикл, если это действительно выгодно.
Но стоит попробовать.
что не так с
std::strtol?