Вычисление количества символов в строке

зачем вычислять длину «предварительно»?

Затабулируй пороговые значения и каскадный if забульбень.

Не пойдет, слетит branch prediction Будет хуже

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

Это проблема FIX, в котором строки вот такие 12=12345666\114=1222345\110=124\1

Или так:

size_t get_sym_num(uint64_t N){
  if(N < 10) return 1;
  if(N < 100) return 2;
  if(N < 1000) return 3;
  if(N < 10000) return 4;
 ...
}

а то и просто так:

size_t get_sym_num(uint64_t N){
  size_t ret = 0;
  do{
    ret++;
    N /= 10;
  }while(N);
  return ret;
}

без каких-либо циклов

Но я бы сам выбрал второй вариант. Первый попахивает индуизмом

Это неизбежно выйдет дороже логарифма, проверено

И вообще, тебе куда надо? На микроконтроллер или на контупер?

В любом случае, если это нужно для того, чтобы тупо сделать itoa, я бы поступил просто: 1) вычисляем заранее максимальную длину текста; 2) в функции выделяем массив нужной длины; 3) заполняем его; 4) возвращаем strdup

Зато первый значительно быстрей!

Да что ты говоришь! Первый вариант будет самым быстрым явно!

Второй вариант будет намного быстрей десятичного логарифма для double, либо таким же по скорости, как десятичный логарифм для int.

До тех пор пока у тебя не utf8 все очень просто и понятно.

А вот с utf8 или любым другим unicode начинается интересный акт, да.

исходник /usr/bin/wc посмотри, вдруг что-то годное найдешь

Этой проблемы нет

При чем здесь хрюникод? Цифры же в ASCII! Они стопроцентно будут по 1 байту занимать в любой кодировке.

Скажи это UCS-2 или UCS-4

Это задача HFT если знаете что это такое

Нереентерабельная функция не пройдет. Аллокация на лету запрещена, даже на стеке. Стандартная библиотека в таком месте не используется вообще.

На кону наносекунды, только просьба не рассказывать про overoptimizing

в жирноутилс вряд ли что интересное найдёшь

просьба не рассказывать про overoptimizing

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

Копирование не допускается, оно дороже вычисления логарифма.

Даже если хранить в регистрах?

На этой неправильной постановке задачи работают все торговые дески ведущих банков мира.

Я выше описал, что это FIX messaging encoding.

Строка в совершенно определенном формате потом уходит в TCP socket.

так никто и не предлагает жирноту
реализаций много - бери да и читай

В общем случае, нет такой возможности или условия, что вам хватит 8 байт на значение, как минимум 15.

Это задача HFT если знаете что это такое

А если не знает то уже не задача ХЕТЭЭФ? Ты слюни та собери мальца, а то я из под стола не могу вылезти, када плюсовое быдло распальцовывать начинает.

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

Уважаемый, распальцовками занялись вы. Несолидно по меньшей мере

В этом случае не выпендривайся, а отправляй пакет фиксированной (максимальной) длины!

А как вы считаете log10? Вот сходу нагуглилось такое http://code.google.com/p/fastapprox/source/browse/trunk/fastapprox/src/fastlog.h , там всего несколько умножений/вычитаний, должно быть быстро

Нарушение формата сообщения означает reject, оно стандартизировано до байта, без каких либо плюс - минус, то что я написал выше - все до последней буквы бизнес-требования, обойти их невозможно

В общем случае, нет такой возможности или условия, что вам хватит 8 байт на значение, как минимум 15.

кол-во десятичных знаков ограничено сверху?

Для целых нет, но можно их ограничить искусственно и сделать для исключений отдельный вызов в API, но базово там ограничение 15

Тогда сам решай. По-моему, простейшим таки было бы кучу if'ов использовать либо strdup.

Применяются gcc builtins, там даже текста функции нет Думаю, что там оптимально.

За подсказку спасибо, погляжу.

15 штук влезет в один 64битный регистр, в два до 32х знаков.

А это конкретное железо сильно хитрое? В SSE4.2 вон есть какие-то быстрые функции для работы со строками.

Первый вариант the best, т.к. не надо производить «дорогое» деление. Сам цикл по себе ничего не стоит, важно что делает цикл :) При этом для первого варианта можно сделать оптимизацию по частоте используемых циферек, что приведет к 1-2 сравненям в 95% случаев.

P.S. А чем ТС не устроил strlen() ?

а что дальше с этой цифрой делается? может по ходу вычисления длины собирать данные для дальнейшей работы?

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

Железо - топовые Xeon E5

По дорогому делению - branch misprediction выйдет значительно дороже. По частоте значений - бесполезно, это могут быть и количество вагонов и цены и суммы оборота за день, тут не прокатит.

И еще, мне кажется вы не поняли, что на входе число.

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

И еще, мне кажется вы не поняли, что на входе число.

Я думал, что можно заинланить как-то.

ИМХО, первый вариант Eddy_Em можно переписать так, что все будет красиво и чики-пуки в виде цикла, просто создать ассоциативный массив (или подобие), забить его числами и просто по нему бегать. Заполнить его можно скриптом каким-нить, и при этом сама проверка в цикле будет производить одно единственное сравнение.

огранизовать бинарное дерево сравнений...

Спасибо, в итоге взял из этого сорца fastlog2 с мультипликатором, проблема решена, осталось юниттестами проверить на широком диапазоне.

Спасибо.

а что если табличку значений для каждого числа завести? :) Если по полбайта на число, то всего 2ГиБ получится

Что-то меня терзают смутные сомнения насчёт этичности оказания помощи людям, вредящим мировой экономике :)

В итоге средняя 15 тактов на вычисление десятичного логарифма, в 10 раз разница.

Почему нельзя писать со сдвигом-запасом, потом по факту переносить? По бранч-миссам, как насчет попробовать cmp/cmov, или его выпилили в новых процах?

И внесите уже царя, кто-нибудь.

Существует много точек зрения насчет вредности, ни одна не может быть признана безупречной.

Мое мнение - все мы лишь звено в пищевой и кормовой цепочке. Касательно плюсов для общества от этой деятельности - они точно так же безусловно есть, и немалые.

царь уже здесь, судя по всему

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

В продакшне память будет cache friendly, так что проблем тут не будет, префетчер обычно настраивается.

Первый вариант можно на дихотомию переделать. Будет быстрей.

Массив, как предлагаешь, — не самое лучшее решение, т.к. разыменовывание — операция дорогая. Нужно использовать именно сравнение с константами.

Строка в совершенно определенном формате потом уходит в TCP socket.

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