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

может там свой особый TCP/IP стек, и ТС знает в лицо каждую инструкцию в его реализации

Там тоже свои меры приняты, гнездо, мягко говоря, не совсем обычное

Нее, ну или он какой-то отрешенный что-ли сегодня.

Если я правильно понял вопрос, то фактически тебе нужно определить наибольшую значимую цифру в числе и прибавить к ней единицу. Держи функцию из моей библиотечки. Реализацию mostSignificantBit приводить не буду, т.к. думаю ты все равно соптимизируешь ее через ассемблерную инструкцию или gcc'шный built-in. Реализацию я подсмотрел где-то в интернете и адаптировал под свои нужды, откуда взялась магическая константа 1233 уже не помню.

int mostSignificantDigit(uint64_t value)
{
	static const uint64_t kPowersOf10[] = {
		1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
		1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000,
		100000000000000, 1000000000000000, 10000000000000000,
		100000000000000000, 1000000000000000000, 10000000000000000000u
	};

	uint64_t temp = (mostSignificantBit(value) + 1) * 1233 >> 12;
	return temp - (value < kPowersOf10[temp]);
}

Считай constexpr-ами на compile-time, и не будет никаких потерь, в runtime уйдёт уже готовое число. А сколько часов оно будет конпелироваться — дело десятое.

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

ШТО?

Держи функцию из моей библиотечки. Реализацию mostSignificantBit приводить не буду, т.к. думаю ты все равно соптимизируешь ее через ассемблерную инструкцию или gcc'шный built-in.

Я очень сомневаюсь в этом, ибо только нулёвый даун вообще будет решать такую задачу. Скорее всего пациент болен либо на головку, либо анскиллом.

Ну и latency + c++ = fail, а уж «определить длину строкового представления беззнакового целого» - двойной фейл. Т.е. скорее всего это анскилл.

А уж когда кукарекающий о «латенси» пацан не осилил эту примитивщину - тут уже вероятность анскилла 100%.

Реализацию я подсмотрел где-то в интернете и адаптировал под свои нужды

Молодец.

откуда взялась магическая константа 1233 уже не помню.

lb(10)
3.32192809488736234789

Т.е. деление на 1/lb(10)

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

Судя по тебе она далеко не HF.

Нереентерабельная функция не пройдет.

И ты не осиливаешь примитивную задачку уровня детсада?

Аллокация на лету запрещена, даже на стеке.

А причем тут аллокация? Какой жопой на стеке что-то «аллоцируется»? Т.е. и представления о матчасти у тебя на уровне детсада.

Зачем тебе вообще этот log10()? Функция число_в_строка() итак знает какая там длинна. Или всё таки ты дёргаешь готовую число_в_строка(), которая не возвращает длину строки? HF, такой HF.

Зачем вообще в HF строки? Форфан, либо бинарь не осилился?

Да и тем более, ты же там задвигал об latency. Дак вот - latency даёт num_chars=8; для всех чисел, а не то, что ты делаешь.

Видишь - теперь все ок, царь во всей своей мерзости.

1234567 -> «1234567» num_chars = 7

#include<cstdio>
#include<string>
int main(int argv, char** argc){
  int val=1234567;
  printf("\"%d\" num_chars = %d\n",val,    std::to_string(val).size());
  return 0;
}

Какие же вы тупые. Ты реально настолько даун, что не понимаешь - твоё говно ты можешь запихнуть только себе в жопу, а не в нормальный код?

Какой же ты шизоид! Внимательно почитай ферстпост ТС, особенно последнее предложение, и подумай почему мой ответ ему соответствует. А про трейдинг он вообще в жопе упомянул, хотя по хорошему надо было бы и в посте написать, и в названии отразить, и тег прикрепить.
Какой запрос — такой ответ.
P.S. и да, нас не много: я один. Лечи шизу.

Что за царь?

Счас так:

/**
     * Calculates binary logarithm
     * @param x Value to take logarithm from
     * @return Binary logarithm value
     * source:  https://code.google.com/p/fastapprox/
     *          https://code.google.com/p/fastapprox/source/browse/trunk/fastapprox/src/fastlog.h
     */
    static inline float fasterlog2 (float x)
    {
      union
      {
          float f;
          uint32_t i;
      } vx = { x };

      return vx.i * 1.1920928955078125e-7f - 126.94269504f;
    }

    /**
     * Calculates decimal logarithm
     * @param x Value to take logarithm from
     * @return Decimal logarithm value
     */
    static inline float fasterlog10(float x)
    {
        constexpr static float multiplier = 1 / log2(10);
        return fasterlog2(x) * multiplier;
    }

    /**
     * Determines number of decimal digits in an unsigned value
     * @param value Unsigned value
     */
    inline size_t __decimal_digits(size_t value)
    { return fasterlog10(value) + 1; }

В вашем варианте немного смущает в RVO как себя поведет branch prediction при несистематических паттернах.

Спасибо, посмотрю тоже.

Интересное решение, по сути эквивалентное вычислительному циклу. Думаю, на типичных числах (4-7 разрядов) будет хуже логарифмов или таблиц.

Не пройдет, считать нечего, все числа известны в рантайме.

Какой же ты шизоид!

До, до.

Внимательно почитай ферстпост ТС, особенно последнее предложение, и подумай почему мой ответ ему соответствует.

Пацан написал, что ему не нравится латенси. Твоё говно мало того, что имеет дожопы и может в любой момент встать раком на тысячи тактов, я уж не говорю о том, что на спинлоке встанут раком все нити с вероятностью в районе сотки.

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

Он сказал, что ему не нравится латенси - об этом уже было ясно. Конечно его «трейдинг» бездарное говно и никакой лоулатенси и HF там не пахнет, но всё же он наверное не настолько туп, чтобы не заюзать твой std::string, если оно ему надо.

Ну и да:

Задача: Без каких-либо циклов необходимо определить длину строкового представления беззнакового целого

Твой to_string() имеет цикл. Конечно по вашему недопониманию не надо знать ничего про to_string(), но повадки бабуинов в твоей нулёвой стаи никак не отменяют наличия цикла в твоей портянке.

Комментарии.

1. Балаган неуместен, тем более что вы явно далеки от тематики. 2. В детсад рекомендую Вам, не понимаете элементарщины. 3. В рантайме вы получаете size_t, ваша задача превратить его в строку по адресу, определенному через данный вам char*. Чем балаганить, предложите, обсудим. Я свой код привел выше. 4. Строки затем, что есть такая штука как FIX Engine. Гугл расскажет что это такое и с чем его едят. Намекну, что без этого самого фикса на приличных трейдинговых платформах делать нечего. 5. num_chars = 8 не прокатит, ибо противоречит стандартам FIX и вместо latency вы получите reject с музыкой

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

В вашем варианте немного смущает в RVO как себя поведет branch prediction при несистематических паттернах.

А можно мне узнать: причем тут RVO и где тут «branch prediction»?

1. Число известно в рантайме 2. Вы почитали, что критична латенси, в состоянии в уме прикинуть скорость вычисления десятичного логарифма и ваше творение?

Все условия задачи были озвучены в заголовке поста, а зачем и почему - разъяснено потом, когда последовали вопросы и советы не по теме.

branch prediction в операторе ?:

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

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

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

Еще раз.

Число (иначе было бы названо константой) известно в рантайме. Иначе этой темы не было бы в принципе. И это должно быть ну совершенно очевидно.

По трейдингу. Когда сделаете encoding числа любой длины вплоть до 15 символов в пределах 5 нс, приходите.

По стандартной библиотеке все верно, в таких случаях или intrinics или builtins, но даже они частенько сливают.

Это местный юродивый по кличке «Царь», не надо на него обращать внимание.

branch prediction в операторе ?:

Покажи мне вот тут:

int mostSignificantDigit(uint64_t value)
{
	static const uint64_t kPowersOf10[] = {
		1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
		1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000,
		100000000000000, 1000000000000000, 10000000000000000,
		100000000000000000, 1000000000000000000, 10000000000000000000u
	};

	uint64_t temp = (mostSignificantBit(value) + 1) * 1233 >> 12;
	return temp - (value < kPowersOf10[temp]);
}

оператор ?:.

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

Рили? Какой особенности?

По RVO - чисто из опыта, в данной конструкции когда будет развернуто в возврате

Что тут будет развернуто? В какой конкретно конструкции?

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

Какие неожиданности, ты же мне скажешь?

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

Аргументировать осилишь?

return temp - (value < kPowersOf10[temp]); - это эквивалент того что я писал, в контексте branch prediction практически полное совпадение будет, скажу даже без дизасма, это уже выверенный кейс

про branch prediction и RVO в контексте стеба нет желания обсуждать, и не все могу писать, могу сказать лишь, что в продакшне чувствительные компоненты показывают branch misprediction не выше 0,1 процента, последствия вам должны быть понятны

ну и с анонимусами разговора точно не будет, некошерно

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

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

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

ну и еще момент - в моем опыте профессионализм и умение себя вести на публике, вещи, как правило, взаимосвязанные

ПС Я код привел, ваша болтовня неуместна, предлагаю или обсуждать код, или предоставить свой вариант

Число (иначе было бы названо константой) известно в рантайме.

Причем тут твои числа и рантайм?

Иначе этой темы не было бы в принципе. И это должно быть ну совершенно очевидно.

Ты откуда вылез? Причем тут твой рантайм?

По трейдингу. Когда сделаете encoding числа любой длины вплоть до 15 символов в пределах 5 нс, приходите.

Енкодинг - это что? Во первых ты же мне покажешь свой сделанный?

Во вторых 5нс - это 20тактов. Это банальный посимвольный цикл.

По стандартной библиотеке все верно, в таких случаях или intrinics или builtins, но даже они частенько сливают.

Сливают чему?

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

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

И тут уже не 20 тактов даже близко.

К тому же, 5 нс это 135 тактов, для сведения, на платформах 2,667 ГГц. У меня средняя ниже уже, порядка 95. Можете пробовать повторить.

return temp - (value < kPowersOf10[temp]); - это эквивалент того что я писал, в контексте branch prediction практически полное совпадение будет, скажу даже без дизасма, это уже выверенный кейс

Рили? Естественно без дизасма, ибо ты его не знаешь. Т.е. ты даже что такое cmp не знаешь?

mostSignificantDigit:
.LFB2530:
	.cfi_startproc
	leaq	1(%rdi), %rax
	xorl	%edx, %edx
	imulq	$1233, %rax, %rax
	shrq	$12, %rax
	cmpq	%rdi, kPowersOf10.17294(,%rax,8)
	seta	%dl
	subl	%edx, %eax
	ret

Где тут branch? Покажи мне.

про branch prediction и RVO в контексте стеба нет желания обсуждать, и не все могу писать, могу сказать лишь, что в продакшне чувствительные компоненты показывают branch misprediction не выше 0,1 процента, последствия вам должны быть понятны

Т.е. тебе ответить просто нечего? Ты заюзал какую-то тулзу? Даже не понимая что такое «branch prediction»?

Ты мне не про последсвия кукарекай, а расскажи - к чему ты приплёл rvo.

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

Ещё раз, ты кукарекал про конпелятор, а не про кеш. Дак вот кукарекай про конпелятор.

Префетчером? Что это? Ты хоть знаешь что это такое, да и вообще как он тебя спасёт? Как им управлять?

В каком неудобном, какая инвалидация?

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

Какой опыт, каких решений?

Ты обосрался с ?:, обосрался с rvo, обосрался с конпелятором, а я виноват? Куллстори.

ну и еще момент - в моем опыте профессионализм и умение себя вести на публике, вещи, как правило, взаимосвязанные

Мне без разницы что ты там считаешь.

ПС Я код привел, ваша болтовня неуместна, предлагаю или обсуждать код, или предоставить свой вариант

Что ты привёл? Стыренный где-то log10()? Твоих вариантов я не вижу. Вариант чего я должен привести?

Запомни одно - если ты хочешь получить внятный ответ - ты должен написать: из чего и зачем тебе надо запилить превращалку - я не должен идти гуглить и догадываться что там тебе надо.

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

Балаган неуместен, тем более что вы явно далеки от тематики.

Конкретно в чем?

В детсад рекомендую Вам, не понимаете элементарщины.

Дак, кто не осилил - я или ты?

В рантайме вы получаете size_t, ваша задача превратить его в строку по адресу, определенному через данный вам char*.

Ещё раз. Ты мне свою превращалку покажи.

Чем балаганить, предложите, обсудим.

Я тебе предложил - покажи превращалку. Как твоя превращалка пишет в твой char *, если она не знает длинны результирующей строки? Либо, это тебе нужно для превращалки?

Тыж профессионал - ты не понимаешь, что strlen() дешевле твоего log10().

Я свой код привел выше.

Это не тот код.

Строки затем, что есть такая штука как FIX Engine.

Мне без разницы что там у тебя есть. Передача через строку имеет большую latency, чем передача изначального бин представления. Тебе хоть это ясно?

Гугл расскажет что это такое и с чем его едят.

Мне абсалютно без разницы.

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

Значит твоя область не осилила бинарь. Т.е. никакого llatency там нет, а есть чистая фикция.

Чтож в xml не передаёшь?

num_chars = 8 не прокатит, ибо противоречит стандартам FIX и вместо latency вы получите reject с музыкой

Это не мои проблемы. Твоя область заствляет тебя работать с говном, только вот от этого оно не перестаёт быть говно и оверхед на преобразование число->строка->число никуда не исчезает.

А отсутствие num_chars = 8 не позволяет написать хотябы быстрое преобразование, если уж нельзя бинарь.

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

Я не заметил у тебя профессиональности нивчем, кроме балабольства естественно.

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

Понимаешь, твои бла-бла мне не интересны. Код где?

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

Не зная длинны чего? Тыж там отправляешь длину, не?

И тут уже не 20 тактов даже близко.

Датычё.

К тому же, 5 нс это 135 тактов, для сведения, на платформах 2,667 ГГц.

Как всё запущенно.

5 нс - это 5 * 1/(10^9) секунды. ГГц - это 1*(10^9) герц. Герц привязан к секунде(1 Hz = 1s^-1).

Т.е. один такт - это ((2.667 * 10^9) ^ -1) sec, а (5 * 1/(10^9)) / ((2.667 * 10^9) ^ -1) = 13.3 такта.

У меня средняя ниже уже, порядка 95. Можете пробовать повторить.

У меня 27тактов - попробуй повтори.

Неинтересно, свободен

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

Бай.

Модераторам - просьба закрыть тему и призвать к порядку сие явление.

Зечем предварительные проверки? Конвертируй сразу в 20-байтовом буфере. Потом лишние не-цифры обрежешь, когда будешь возвращать строку.

1. Строка не возвращается, она пишется в положенное место. Копирования запрещены.

2. Как вы знаете, наверно, любые аналоги itoa работают начиная с младших разрядов. В этой задаче я для нормального ее решения должен знать длину строки

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

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

Дак что там, с 135-ю тактами в 5нс, при ТТ 2.7ггц? Что там с оператором ?:? что там с бренчами? Что там с rvo? Что там с конпелятором? Что там с твоим кодом, который ты вылажил - где он? Что там с «префетчером»? Ответы будут?

Это прям эталонное днище, такое мне ещё не попадалось. Если там пацаны обсираются, то они и не претендуют на HF и llatency - им простительно. Но нулёвый балабол, при этом толкающий про HF и llatency - это в первые. Есть ещё mv, но он хотябы что-то понимает и такты посчитать может.

Спасибо

Будете должны :)

проблема решена

Кстати, на Xeon E5 (точнее, на AVX) можно считать за раз 8 float логарифмов(или 8 длин строк). Решения легко гуглятся по «avx logarithm». Или можно написать по приближенным формулам

Реализация алгоритма через lzcnt и деление на log2(10)?

не будет ничо быстрее логарифма

Делал, кастомный логарифм оказался быстрее с учетом header implementation (на вход подается и на выход принимается unsigned)

Сейчас средняя теста с учетом оверхеда цикла 12 тактов на итерацию. Соответственно, 34 такта на моей машине на решение задачи при условии локализации памяти буфера.

Кастомный это какой? Который в fastlog был?

Да, он

мне кажется, что вы не верно воспринимаете приближенные вычисления.

http://pastebin.com/QyCcU5PU

держи число в двоично-десятичном виде.

потом какой-нибудь битовой магией считаешь кол-во бит и делишь на 4 с округлением вверх

строки константные? (в противном случае, они должны откуда-то браться, вот там и будет лишний цикл так и так)

у вас есть указатель char*, писать вы должны начать с этого места, пропуски в начале (trailing whitespaces, trailing zeroes и тп) не допускаются

копирование после операции, мувы и прочие радости под запретом

упрощенно, вам нужно сделать вызов типа emplace(char*, size_t), буфер достаточной длины, но более о нем вы ничего не знаете

Решение в итоге перешло на табличный вариант, но серьезно модифицированный.

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

Сделано для 64 бит.

8 тактов на 2,67 ГГц машине.

Код:

    /**
     * Determines number of decimal digits in an unsigned value
     * @param value Unsigned value
     */
    static inline size_t decimal_digits_tbl(size_t value)
    {
#define NUM_DIGITS(bit) static_cast<size_t>(log10(static_cast<size_t>(pow(2, bit))) + 1)
#define NEXT_EXPANSION(bit) static_cast<size_t>(pow10(NUM_DIGITS(bit)))
#define BIT_DESCRIPTOR(bit) { NUM_DIGITS(bit), NEXT_EXPANSION(bit) }
#pragma GCC diagnostic ignored "-Wnarrowing"
        constexpr static size_t tbl[][2] =
        {
                        BIT_DESCRIPTOR(0),
                        BIT_DESCRIPTOR(1),
                        BIT_DESCRIPTOR(2),
                        BIT_DESCRIPTOR(3),
...
                        BIT_DESCRIPTOR(61),
                        BIT_DESCRIPTOR(62),
                        BIT_DESCRIPTOR(63)
        };

        size_t idx = 63 - __builtin_clzl(value);
        return tbl[idx][0] + (value >= tbl[idx][1]);
    }

Больная на всю голову у вас область. В память писать один раз, бранчи не юзать, в серверной не дышать. Но передача инфы в формате «текст с разделителями», победа, не иначе.

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

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

Цикл-то есть, но он только на вывод в конкретное место, без всяких побочных дел. Почему - кодирование целого занимает около 30 тактов, копирование памяти будет примерно столько же. Вот и делайте выводы.

И да, обычно это делается не в хипе, а в собственных аллокаторах на hugepages

Серверная вообще в биржевых датацентрах, посещение, например, в Москве стоит 3000 рублей за 15 минут. Я сопровождающих весело называю эскортом :)

Да, много чего тут интересного

Максимальная длина целого (в строковом представлении) 10. Миллиард (плюс минус два опускаем, т.к. это единицы и на длину не влияют.

Стандарт фикса устанавливает 15. Но в моем примере максимальная длина не фигурирует.

Реально же максимальная длина в size_t строкового представления составляет log10(2^63) + 1 = 19