0xd34df00d
13.03.2012 16:28 Azoth_primary
Господа, как быстрее, по-вашему, определить число цифр в числе — взять от него десятичный логарифм и округлить вверх или последовательно делить на десять, пока не упрусь в ноль?
Я просто слышал, что логарифм брать пипец как долго в известном смысле.
Recommended by:
@pooq: моча съела говно
202 comments
recommend
bookmark
subscribe
перевести в строку и выдать length?
число какое? если int быстрее тупо двоичным поиском
Пиздец.
Еще один пизедц.
чем пиздец ты можешь объяснить?
а если через log2 пересчитать — его ж быстро брать
Переводить в строку число — это пиздец.
Ты глупый штоле? Берешь и считаешь: раз, два, три, четыре... Дошел до конца — все, до скольки досчитал, столько и цифр.
Я на хаскеле пишу, там что угодно в одну строку.
в плане затратности?
У меня не строка, а число.
Да.
ok
Хм, почему его быстрее, чем log_10 брать?
дедфуд, сука, -→ /2
Хм. Разверни мысль.
переведи в строку и возьми от строки strlen :3. я думаю логарифм на сопроцессоре ок.
и вообще, напейши бенчмарк.
я бы биномиально делил на степени десятки
WTF биномиально?
ну потомшто уоррен пишет что Число значащих бит — целая часть двоичного логарифма от самого числа. =)
int ints[] = { 1, 10, 100, 1000, .... }
lower_bound(ints, ints + count, x) — ints + 1
Число так число, все равно считай. Карандашиком точечки можешь ставить над цифрами, чтобы не сбиться.
вернее даже не так, биномиально проверял на что больше или меньше степени десятки. вот
std::lower_bound
Э, чо?
во! именно так. хороший план
Я не очень понял — ints
название массива
Я не могу искать бинарным поиском по [1,10,..], а там уже линейно. Хотя, подозреваю, это будет существенно быстрее и логарифма, и деления на 10. Спасибо за идею, клеви.
это степени десятки, ёпта. loverbound будет совпадать с минимальной степенью десятки, которая меньше твоего числа. берёшь std::distance и получаешь значение степени
> loverbound
Оук.
Я не понял вычитание указателя из возвращаемого lower_bounds итератора, но похуй.
И нет никаких дистансов. Лучше посчитаю глубину рекурсии, конпелятор все равно в цикл развернет ;3
вычитание = std::distance
всё равно профильни, хуй его знает
кстати, я правильно помню, log2(n)/log2(10) = log10(n), если так, то надо найти тупо старший бит и его номер поделить на константу. имхо быстрее не придумаешь.
>найти тупо старший бит и его номер поделить на константу. имхо быстрее не придумаешь.
127 и 65 имеют одинаковое число цифр, ага
логарифм — красивое решение, но "тяжелое". деление — цикл, и это не Ъ. проще всего преобразовать в строку и взять длинну. имхо.
где-то тут проеб. ты прав. вот где?
ахуеть, а как число в строку превращается? не делениями с остатком случайно??
нет, оно само.
наверное он в том, что я логарифм округляю.
ага. двоичный логарифм ты округляешь до целого
Оук.
Ваще пойду хоть что-то заимплемечну.
О. А как нынче модно искать старший бит?
Мне нужно оценить число сверху, желательно поточнее, чтобы не вылезло за 2^64. Если у 65 появится ВНЕЗАПНО три цифры, я переживу.
Деление — рекурсия.
А если речь о строках, то я лучше буду исходно строками манипулировать. Мне нужно строить ID дерева по ID поддеревьев и ID операции, да.
я хз, ассемблер забыл. а так в принципе смотри сверху пока байт 0, а потом уже сдвигом пока бит 0
А у меня все равно асма тут нет, а с битовыми операциями в х-ле я еще не работал.
я не говорю что писать это на асме. я говорю о тех вещах, которые быстро сработают в процессоре и при умном компилере.
в хаскелле нет битовых операций? мб он деление на явные степени двойки соптимизирует хотябы?
и я, к сожалению еще не осилил х-ль, посему не знаю что он умеет с числами.
Должен, гохаце вообще умный. И битовые операции были, но мне еще и там мозг ломать не хватало, как искать старший бит.
А похую, сделаю ваще все на строках, а то от треда пахнет ПРЕЖДЕВРЕМЕННЫМИ ОПТИМИЗАЦИЯМИ.
Ъ. и вообще, если это не критично, самый лучший код — это самый читаемый. Короче без лямбд и хаскеля.
нет такой хуйни как "преждевременная оптимизация", если ленивые мозги и тормозное говно размазанное мелким слоем
Как-то так толсто про хаскель, что даже тонко.
Вообще мне нужно в дереве находить одинаковые поддеревья максимального размера, и я ничего не придумал умнее, чем присваивать вершинам айдишники, соответствующие поддеревьям от этих вершин, и потом искать одинаковые у наиболее близких к корням вершин.
Посмотрите, какой оптимизатор.
когда у тебя тормозит в любой эпсилон окрестности — вот тогда ты будешь вспоминать и матюкаться о "преждевременных оптимизациях"
Когда профайлер мне покажет, что в этом месте я 1% времени, я над тобой посмеюсь.
смех без причины — признак психического заболевания
если тормозное говно размазано мелким слоем — надо менять компилятор и/или язык. А обычно тормозное говно концентрируется в бутылочном горлышке, там профайлер поможет.
ну хаскель он не поменяет
Да. У меня как-то раз 60% времени код жрал в лукапе функций по айдишникам. Заменил lookup по [(a, b)] на паттерн-матчинг, и все стало ваще заебись.
не понял что конкретно ты делаешь с айдишниками. суммируешь низлежащие ноды? или как? впрочем хрен с ним, это надолго, меня ПЫХ ждет ;(
Ну, я хотел домножать идентификатор нижележащей ноды на число цифр в нем и складывать с вышележащим. Правда, это все говно, похоже, и неоднозначно. Лучше поебу строки, да, а на алгоритме помечания сделаю отдельную публикацию :3
Быстрый логарифм тебя спасет.
#define LOG2E 1.44269504088896340736f
float fastLog2( float x )
{
ADVFLOAT ax;
int exp;
ax.x = x;
exp = ax.exp — 127;
ax.sign = 0;
ax.exp = 127;
return (ax.x — 1.0f) * LOG2E + exp;
}
если у тебя размер числа фиксирован (типа максимум 128 бит), то можно попробовать найти наибольший старший разряд (позицию) при помощи операций OR побитовых
вот я построил список 10**i степени
http://paste.pocoo.org/show/565203/
в большинстве случаев становится всё ясно, но когда количество разрядов одинаково можно делать cmp.
впрочем, может и cmp операция достаточно дешёвая на современных ЦПУ чтоб не выёбываться и делать таки двоичный поиск как кто-то уже сказал.
Похоже, не фиксирован нифига :(
Если бы мне нужна была хардкорная оптимизация конкретно в этом месте, я определял бы по старшему установленному биту. Из ассемблера это мгновенно выполняется, в сравнении со взятием логарифма или пачкой делений. Если числа целые, конечно; впрочем, для fp тоже можно что-то подобное запилить.
Охуеть, откуда в таком треде 70+ комментов?
старший установленный бит — это и есть целая часть логарифма, если чо.
от дедфуда. он катализатор флуда.
изначально вопрос стоял о кол-ве цифр в десятичной записи, а не об последующих еротических фантазиях дедфуда
ну да. это я вперед забежал
python-way.
Как толсто.
Когда люди очень сильно выебываются "ололо аптимезация не нужна, у меня нет времени ебаться с ней, лучше я запилю еще парочку уровней абстракции", получается фаерфокс. Который уже нихуя и не читаемый. Впрочем, даже если бы он был охуенно читаемым, встал бы вопрос "чем вы вообще там блядь занимаетесь? Программы пишете, чтобы они работали, или просто код, чтобы он читался?". Я как-то запилю длинную гневную простыню об этом, да, уже пару месяцев собираюсь.
Я не говорю, что оптимизация не нужна. Я говорю, что не нужно заранее тратить время на то место, которое далеко не факт, что будет узким.
И да, это research project, проверка работоспособности алгоритма и изучение поведения всякого говна. Вопрос порождения айдишников там далеко не на первом и даже не на десятом месте.
чуть ли не единственное здравое предложение в треде.
Верно. Но и писать его "абы как" в надежде, что профилировщик не ткнет туда пальцем, тоже как-то дико. Задумываться над оптимизацией стоит всегда, соблюдая trade-off с читабельностью, конечно; только вот многие людишки возвели эту читабельность в охуевший абсолют и не хотят замечать вокруг больше ничего. От того и растет потребление ресурсов чуть ли не быстрее, чем развитие железа; функционал же при этом фактически стоит на месте. Точнее двигается вперёд, но на несколько порядков медленнее, чем можно было бы предположить, глядя на скорость роста системных требований софта.
Олсо, я ж не про твой прожект говорю, а про общие тенденции в программировании.
ты сейчас опять про личкрафты?
Конечно. Зачем нам думать, оценивать алгоритм с точки зрения количества выполняемых операций? Лучше мы напишем еще один ололо-бенчмарк.
Просто я ебанусь придумывать и доказывать корректность такого алгоритма расчета цифровых айдишников, чтобы он на дереве хотя бы глубиной в 10 не вылез за 64 бита, и чтобы оно того стоило по сравнению со строками.
Препендить строки друг к другу сейчас быстрее. И я надеюсь, что такой трейдофф позволит мне быстрее реализовать алгоритм в общем и, если потребуется, заниматься уже битоебством и менять деления на сравнения.
а ты можешь гарантировать что цикл на CPU будет быстрее одной операции FPU или наоборот?
конечно, зачем нам возвращаться к действительности — лучше покукарекаем с дивана.
Што. Я сейчас про игры, про венду, про браузеры, да про 95% софта.
:-(
Вспоминается кутим с действительностью, в которой зависимости между плагинами разруливаются переименованием и повторными попытками загрузить.
казалось бы, причём здесь оптимизация как таковая.
Хуй знает, но грех не обосрать кутим :3
;3
so deadfood.
Смотря какой цикл, смотря какая операция. В некоторых пределах я смогу гарантировать это, используя здравый смысл и знания о принципах работы процессора. В спорных случаях я загляну в Интеловские даташиты.
Бенчмарки могут понадобиться в более сложных случаях, когда я заебусь учитывать все нюансы. Но вопрос про логарифм к таким случаям аж никак не относится.
В твоей действительности у всех людей размер мозга не больше твоего? Тогда, конечно, без костылей никуда.
нерелевантный слив.
А ты и правда любитель вести дискуссии, как я погляжу.
если мне не изменяет память, логарифмов есть несколько — x87, sse и т.д.
> streaming simd extensions
> логарифм
Щито.
тащемта, ничто не мешает написать свой собственный логарифм. Особенно воспользовавшись невысокими требованиями к точности, обменяв её на лучшую скорость.
Нерелевантный слив был выше про диван. Мне пришлось лишь релевантно поддержать его, дабы не ввергать тебя в пучину фрустрации.
Ты можешь реализовать его с использованием sse, и он при некоторых условиях даже будет рвать по производительности fpu-версию. Специальных инструкций для этого нет.
Так, например => http://gruntthepeon.free.fr/ssemath/
в сложных системах заебешся оценивать сложность всевозможных алгоритмов + есть еще ОС, треды, IO, другие задачи в фоне, в которые ты не залезешь.
нет, это был ответ на агрессию с твоей стороны.
Но хорошо, я разверну мысль. В данной задаче теоретизировать нецелесообразно и даже опасно. Цикл с делениями и fp логарифм зависят от разных функциональных частей процессора (взаимоотношение между которыми сильно варьирует от системы к системе), имеют разное влияние на пайплайн и кеш инструкций. Проанализировать все возможные варианты взаимодействия кода и системы, конечно же, можно, — но при этом появляется слишком большой риск принять в процессе ошибочные или ненадёжные допущения (например, построить свои гарантии на негарантируемых деталях реализации). Непосредственное измерение избавляет от этого риска — а заодно и от трудоёмкого анализа.
во-во, примерно об этом же и я.
Не надо пытаться быть слишком умным в сложных системах. Потому что будешь подводить ожидания других.
Про сложные системы я сделал ремарку ниже. А вот как раз бенчмарки и покажут тебе охуенно влияние счедулера и прочих ништяков на твою задачу.
В данной (достаточно простой) задаче вполне достаточно среднего уровня знаний о принципах взаимодействия разных модулей cpu и представления о том, как работает конвеер/branch prediction unit для того, чтобы оценить оптимальность обоих подходов с достаточной точностью. Никто же не просит нас считать точное число тактов в разных случаях? Мы видим, что один из способов заведомо быстрее; можем обосновать, почему это так; понимаем, какие внешние факторы могут повлиять на соотношение и представляем, что можно изменить, чтобы ослабить/усилить это влияние. В результате имеем куда более глубокое понимание ситуации и потенциал для ее изменения, чем после слепого, бездумного взгляда на цифры из бенчмарка.
Тут, кстати, в соседнем окне чувак запилил бенчмарк, и у него деление сосало у логарифма уже для семизначных чисел.
можно посмотреть?
> представления о том, как работает конвеер/branch prediction unit
о даа, это точно средний уровень представлений software developer-ов.
Где-то в http://0xd34df00d.me/logs/chat/c_plus_pl...
Средний софтваре девелопер пишет CMS на джангопитонах и даже не знает, что такое логарифм.
я не отрицаю, что интерпретировать результаты бенчмарка нужно. Неожиданные результаты должны удивлять, а не убеждать. Скажем, я удивился, когда плюсовый std::set работал медленнее питоновского set — и этому нашлось объяснение.
Но пустое, «диванное» теоретизирование здесь без фактического материала неуместно. Это моя точка зрения.
и получает нехуёвые деньги при этом!
Я лучше буду получать свои 60к за ненапряжную и приятную удаленочку с плюсами и NLP, а также получать удовольствие и кавай от научечек на хаскеле.
тащемта, к тебе претензий никаких и нет. Занимайся, чем нравится, няша. Но не стоит судить других по тому, что предпочитают они.
Я осуждаю людей, которые осилили бедон и жангу и теперь гордо именуются ПРОГРАММИСТАМИ.
// сам жангу ниасилил
ну если это задевает твоё чувство элитизма, именуйся не программистом. Гордое СОФТВАРЕ ДЕВЕЛОПЕР или СОФТВАРЕ ИНЖИНИАР — гораздо элитнее, чем the dreaded «программист».
Кокой ты, элитизм, кококо.
ну а что это, не элитизм? Именно он.
посмотрел, затестил:
700000
750000
увеличил на ноль бенч-цикл (т. е. в 10 раз):
7.11e+06
7.5e+06.
логарифм — второе. amd64, core 2 duo 2gHz, gentoo. Такое. Странно что результат близок по времени. Очень странно.
На числе 1234567891:
7.85e+06
7.51e+06
логарифм немного выигрывает. больше — переполнение int, не хочу менять тип.
Поменяй, uint64_t же. Интересно.
послало uint, поставил long:
1.61e+07
7.58e+06 логарифм хуярит в 2 с лишним раза лучше чем деление. это на 123456789123456789
Да. При этом он не посмотрел на то, во что компилятор превратил цикл и что происходит с бренч предиктором при его работе.
давайте не будем эту хуйню дизассемблировать, ок? я бы на месте дедфуда ебанул бенч на х-ле и закрыл бы срач.
хуле там дизассемблировать-то, делов
Я считаю, что хороший программист должен иметь хорошее представление о таких вещах. Средний, соответственно, хотя бы среднее. Впрочем, хорошие программисты сейчас не в моде, согласен.
Гм, любопытно. Я не ожидал, что деление соснет так быстро, да.
кстати, я бы всё-таки сделал округление явно. А то int(x + 1.0) совсем не то же самое, что int(x) + 1.
да нехуй, но это не даст ответа, что сделает х-ль. Для несмотряторов:
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
int nDigDiv(long chi){
int n=1;
while(chi/=10)
++n;
return n;
}
int nDigLog(long chi){
return log10(chi)+1;
}
int main(){
double t=clock();
for(int i=0;i<100000000;++i)
nDigDiv(123456789123456789);
clog<<clock()-t<<'\n';
t=clock();
for(int i=0;i<100000000;++i)
nDigLog(123456789123456789);
clog<<clock()-t;
}
gcc -S отменили?
Вот на хаскеле я бы точно засцал дизассемблировать. Монады ленивость хуе-мое.
То есть, блин. Среднему девелоперу, если он не хуевый ремесленник "пришел-набыдлокодил-забыл" должно быть как минимум интересно, что там и как внутри. И он откроет интеловский документ, где специально для таких как он в картиночках все нарисовано. И этого будет вполне достаточно, если он не захочет вникнуть глубже.
ну так. Хотя я бы поюзал gcc -g -O2, objdump -S
и это даст ответ, что сделает в этих случаях ghc?
нет. А причём здесь ghc?
Кстати, и это тоже любопытно, я бы на досуге как-нибудь занялся бенчем четырех предложенных в этом треде подходов на плюсцах.
Правда, во внутреннюю кухню процессора, чую, мне бессмысленно лезть на моем текущем уровне развития. :(
Я даже в сишный высер ghc не хочу лезть, а ты про асм :(
Разница в подходах. Ты считаешь, что бенчмарк первичен, и что там внутри — знать особо и не нужно; потому все, где не было бенчмарка — "диванное теоретизирование". Я же считаю наоборот — первичным должно быть понимание, а бенчмарки — лишь вспомогательные тулзы для упрощения&убеждения; и в простейших случаях без них можно обойтись. Обе точки зрения имеют право на существование, наверное; вот только у меня баттхёрт от такого положения вещей.
бля, вы меня за хаскель посадите этим бенчмарком :D.
столкнулись практик и теоретик.
++
а в итоге теория должна подтверждаться практикой, и практики без теории хуевые получаются. посему давайте жить дружно.
Нет, это не элитизм. Вот объективно, есть более простые вещи, и есть более сложные (либо сложные для осознания, либо просто задротские, требующие временных инвестиций для погружения). Закономерно, что за использование более сложных вещей в общем случае человек получает больше денег (в общем случае, матаноебствующего в изоляции Дедфуда не рассматриваем). Закономерно, что прошарив эти "более сложные" вещи, он будет подсознательно ожидать такого же уровня понимания и от всех остальных коллег, и ловить разрыв шаблона, когда его ожидания обманываются.
У тебя гента ia32 или x86_64?
люто плюсую. Развелось быдлокодеров, не понимающих элементарных вещей. Заебись что я в 90е ебал ассемблер. Добавило понимания. И ембеддед способствует. А уже выросло поколение людей, которые не представляют, что ПАМЯТЬ И БЛОКИ В НЕЙ НЕ РЕЗИНОВЫЕ, а посему пользовать её надо правильно, и не будет тупить/cвопить. Они вообще не думают об этом, им похуй.
amd64
Ключи компиляции забыл )
Запускаешь ghci, набираешь log число, получаешь его двоичный логарифм (кстати, можно оценить разницу log_2 и log_10).
Запускаешь ghci, набираешь :m + Data.List, а потом что-то такое:
Prelude Data.List> findIndex (230543 <) $ map (10**) [0,1..]
Just 6
Это вариант а-ля lower_bound, без деления. С делением аналогично.
Кстати, надо как-то глянуть. Ато я так ни разу и не сталкивался с его бинарниками в диком виде.
> Закономерно, что за использование более сложных вещей в общем случае человек получает больше денег
не согласен. Получаемые деньги зависят от спроса — от того, насколько нужные вещи делает человек. Как он это делает — это уже вторичный вопрос, который от публики может даже намеренно скрываться, aka know-how.
Аналогично и в команде. Здесь, правда, это «как» скрыть не получится — потому что другим нужно с тобой кооперироваться.
> прошарив эти "более сложные" вещи, он будет подсознательно ожидать такого же уровня понимания и от всех остальных коллег, и ловить разрыв шаблона, когда его ожидания обманываются
о чём я и говорил — пытаться быть слишком умным в большой команде контрпродуктивно.
$ make signs
g++ signs.cpp -o signs
без нихуя.
Это бинарь с проектом для ГА. МАТРИЦЫ ДЕРЕВЬЯ ХУЕ_МОЕ
Спольски тоже ныл на эту тему http://www.joelonsoftware.com/articles/f...
А што сразу я :(
Корреляция между спросом и сложностью вещей тебе разве не очевидна?
нет. Разве что отрицательная.
1) Под "более сложными вещами" я понимал не "какую-то никому не нужную херь, для которой уже давно появились простые заменители", а именно те более сложные вещи, для которых заменителей нет и никогда в обозримом будущем не появится.
2) В умной команде быть умным совсем не контрпродуктивно. Контрпродуктивно выебываться выше среднего уровня команды; если возникает такое желание — лучше найти команду "уровнем" повыше, вот и все.
А теперь сделай -O2, а потом -O3 же, ну :(
бля, у вас что. конпеляторов под боком нет. сделайте, хуле
Это и без Спольски заметно по среднему уровню качества массового софта сегодня.
2) абсолютно верно.
Потому что 60к для москвы — зарплата продвинутого джуниора, например.
Это если фуллтайм. А я сижу, делаю что-то когда-то, параллельно с уебой и другими проектами, и ваще ништяк.
У меня здесь нет, например.
@0xd34df00d, а у тебя есть gcc?
Да, есть, но он щас объебался темплейтами и устал :(
и это проблема. Которую непонятно как решать иначе, чем через наслаивания абстракций вроде JVM, и делегирования всех сложностей и тонкостей «под» них. Точно так же как сишечка в своё время предоставила универсально прижившуюся абстракцию для ассемблеров.
При этом абстракция может давать предостаточно пространства для решения проблем с производительностью. Я имею ввиду JIT и подобные технологии того самого «умного компилирования», когда программист-клиент абстракции только высказывает свой замысел, intent — а среда поддержки абстракции (e.g. jre) самостоятельно приходит к оптимальным «деталям». Естественно, это требует ресерческих усилий, это много дизайна, кодинга и отладки, этц — но по крайней мере такой путь предоставляет решение проблемы. В то время как бесконечное вождение новичков по граблям и набивание шишек по каждой неабстрагированной детали а-ля C++ не слишком-то преуспевает как альтернативный способ решения.
ЛОЛ:
asmer@iridium ~/progging/c++ $ g++ -O2 signs.cpp -o signs
asmer@iridium ~/progging/c++ $ ./signs
0
8.25e+06
asmer@iridium ~/progging/c++ $ g++ -O3 signs.cpp -o signs
asmer@iridium ~/progging/c++ $ ./signs
0
0
бля, этому бенчмарку нужен более адекватный способ засекания времени.
не. время тут не причем. это реальное время, задержка заметна на предыдущих тестах без оптимизации. C O2 заметна задержка второго цикла. g++ соптимизировал цикл(ы) в одну итерацию, я думаю.
посмотри уже objdump -S
как попросить gcc дать объектник? а то кроме бинаря ниче нету, objdump не на что натравливать.
-c
Да. Скорее всего it в будущем будет развиваться именно в этом направлении. Хотя у меня все же теплится смутная надежда, что человечество возьмется за голову, выкинет нахуй императивное легаси и уйдет в математически строгую функциональщину. Но такого никогда не случится, увы :(
А чтобы слоить абстракции так, как ты описал, нужно дождаться скачкообразного роста ресурсов железа. Но, блин, насколько же грустно будет осознавать, как впустую проебывается 90% его потенциала.
Пойду пуэра выпью лучше для восстановления морального комфорта, да потис^W
Предлагаю устроить термоядерную войну с гарантированным полным уничтожением всего, и проблема императивщины не встанет еще долго.
А вообще, люди, блядь, указатели понять не могут, а ты их хочешь в рекурсию, фолдры, чистоту и монады. Ну не издевайся ты так.
Тян себе потискай, Ктулху! А я пойду потискаю еще эти графы да выпью реврайтов.
http://pastebin.com/aAuFUShw -O3
-g добавь же
Сучечка, мне от тебя захотелось под avr'ки поасмоебствовать.
а, не, вижу.
я когда под пики писал. охуеть, 35 команд и умри. еще и стек, сука, отдельно.
А я, на самом деле, даже под аттини на плюсцах с темплейтами писал, а __asm был в отдельных заповедниках, вокруг которых были типобезопасные обертки, няшнота.
btw, я нихуя не понимаю в этом коде. Ну т. е. не совсем нихуя, но после i86 realmode тут непонятны некоторые команды. однако условных переходов на для for я не вижу.
я помню. я педалю на pure c.
Вот графички с моего ноута:
Код здесь http://hpaste.org/65262
Явно видно, что цикл с делением заруливает — в противовес результатам на машине @asmer.
Что, собственно, и подтверждает мою тезу о бесполезности теоретического анализа здесь: YMMV, всё зависит от конкретной железки.
Кокой моднявый, с std::chrono. Завтра обязательно набросаю тестик.
а то!
Аж стандарт открыл, чтоб хотя бы прототипы видеть. А то в интернетах совсем что-то мануалов дефицит.
Попробуй, кстати, написать в районе 12-ой строки volatile. А то тупой вызов функции без сайд-эффектов кучу разз подряд меня смущает.
> void();
> C++
> сайд-эффекты
и нафига volatile в 12-й строчке? я лучше дизасм почитаю, интереснее будет.
Компилятор, по-твоему, настолько туп, чтобы не увидеть, что твои эти деления на 10 не меняют глобального состояния? Почитай уже про современные оптимизации, ну. И про значение volatile заодно.
про volatile я знаю. А про современные оптимизации — сейчас увидим.
В плюсокодотреде 200 комментов, пстач торт.
в общем, цикл там есть, функции не заинлайнены, и даже вызов их делается через регистр+смещение — типично для method call. Адреса функций используются где-то поблизости от инициализации std::function и std::bind. Алсо, std::function при инициализации вызывает operator new(unsigned int), лол.
Ещё заинлайнено дохуя темплейтов, листинг периодически РАСПИДАРАШИВАЕТ. Но энивей, твои подозрения насчёт слишком умного gcc напрасны :3
(
Вот сейчас ты запилил типичнейший абстрактный бенчмарк в вакууме, бессмысленный и беспощадный. Не вдаваясь даже в дебри того, что там сгенерирует gcc в результате использования тонн задействованных посторонних сущностей, просто посмотри на то, как работает твоя реализация ceil(). Ты будешь удивлен, скорее всего. А потом представь, что происходит с пайплайнами в результате ее работы.
Да, в некоторой степени быстродействие зависит "от конкретной железки". Но не как-то магически "ой нам не понять, просто примем как данность", а зависит от конкретных факторов. И на последних камнях этот разброс не настолько огромен, чтобы быть заметным на таких минималистичных примерах.
Потому этот бенчмарк лишь еще раз подтверждает тезис о том, что вот так сурово писать бенчмарки и смотреть на результат, как на откровение свыше — ошибка.
У меня от at&t синтаксиса брат умер :(
в дебри я вдавался. ceil (хотя там вообще-то должен быть floor, гм-гм; но особой разницы в генерируемый код это не вносит) разворачивается макросами в пачку fp инструкций. Что меня не удивляет. Смотри сам:
804860d: dd 44 24 20 fldl 0x20(%esp)
8048611: dd 1c 24 fstpl (%esp)
8048614: e8 b7 ff ff ff call 80485d0 <log10@plt>
8048619: d9 7c 24 2c fnstcw 0x2c(%esp)
804861d: 0f b7 44 24 2c movzwl 0x2c(%esp),%eax
8048622: 25 ff f3 00 00 and $0xf3ff,%eax
8048627: 0d 00 08 00 00 or $0x800,%eax
804862c: 66 89 44 24 2e mov %ax,0x2e(%esp)
8048631: d9 6c 24 2e fldcw 0x2e(%esp)
8048635: d9 fc frndint
8048637: d9 6c 24 2c fldcw 0x2c(%esp)
804863b: dd 5c 24 18 fstpl 0x18(%esp)
804863f: dd 44 24 18 fldl 0x18(%esp)
8048643: d8 05 40 88 04 08 fadds 0x8048840
это ceil. floor:
8048619: d9 7c 24 2c fnstcw 0x2c(%esp)
804861d: 0f b7 44 24 2c movzwl 0x2c(%esp),%eax
8048622: 25 ff f3 00 00 and $0xf3ff,%eax
8048627: 0d 00 04 00 00 or $0x400,%eax
804862c: 66 89 44 24 2e mov %ax,0x2e(%esp)
8048631: d9 6c 24 2e fldcw 0x2e(%esp)
8048635: d9 fc frndint
8048637: d9 6c 24 2c fldcw 0x2c(%esp)
804863b: dd 5c 24 18 fstpl 0x18(%esp)
804863f: dd 44 24 18 fldl 0x18(%esp)
8048643: d8 05 40 88 04 08 fadds 0x8048840
я вижу какие-то манипуляции с битовым представлением, затем frndint, затем fadds константы 1.0. Что здесь не так? Всё ожидаемо.
Да, конкретные повлиявшие факторы проанализировать можно, но мне лень. Я вижу, что на одной машине в два раза заруливает один метод, на другой — другой. Я также могу проинтерпретировать эти результаты, и заодно объяснить каждую фичу на графиках выше — но, опять же, лень.
Ты меня случайно не троллишь сейчас? )
Это не "какие-то манипуляции с битовым представлением". Это получение fpu control word, изменение некоторых флагов в нем (отвечающих за направление округления), и восстановление его оригинального значения после выполнения frndint.
И вот эта хрень у тебя выполняется на каждой итерации цикла. Изменение режима работы fpu, вызов еще одной его команды (не такой уж и дешевой), и изменение режима обратно.
В бенчмарке, который мы рассматривали выше, этого не было (потому что не ceil, нни floor там не вызывали).
И теперь, внимание, вопрос к знатокам. Когда ты сравниваешь результаты двух бенчмарков без учета вышеописанного фактора, и списываешь охуенную разницу на влияние железа... Как это называется?
нет, не троллю. Замечание принимается, переделаю без floor.
gcc выкинул оба цикла.
volatile int _ = nDigDiv(123456789123456789);