Комментарии 300
Массив размером 256*(sizeof int)=1Kb? Можно и без массива и без ветвлений, например:
char c ; // input
char t ; // temp
int res = 0;
...
t = c ^ 's'; res += (int)((~t &(t-1)) >> 7) & 1;
t = c ^ 'p'; res -= (int)((~t &(t-1)) >> 7) & 1;
на ассеблере будет еще компактнее (можно задвигать знаковый бит в флаг переноса);
или так:
t = c ^ 's'; res -= (int)((~t & (t-1)) >> 7);
t = c ^ 'p'; res += (int)((~t & (t-1)) >> 7);
я ради любви к науке, протестировал оба ваших варианта, и все они значительно медленнее варианта с табличкой (2-3 раза). Приемы из "мира z80", редко на современных процессорах работают так же прямолинейно.
Если я правильно понял, то исходный код на СИ на основе switch ,
а в ручной оптимизации фактически switch заменили на if.
Полагаю, что это некорректно, так как оптимизируется совершенно иной алгоритм, чем изначально оптимизировали компиляторы .
switch и if эквивалентны, и компиляторы имеют полное право это делать.
Вы не поняли, о чем я написал. Право компиляторов никто не умоляет.
Речь идет о ручной оптимизации автором статьи.
Switch и набор if по-разному преобразуются в машинный код. Обычно switch более громоздкая в машинном коде, но более компактная в C.
В статье автор исходный код на СИ написал с переключателем
а потом оптимизирует алгоритм на ассемблере с использованием условных операторов. А это аналог программ на С c использованием if.
Если бы он написал на СИ два варианта со switch и на основе if и оба варианта оптимизировал компиляторами а потом руками, тогда все было корректно.
Всё и так вполне корректно. switch - это синтаксический сахар для if. С точки зрения компилятора языка разницы между switch и if-elseif-else нет. Код на C, который считается языком высокого уровня, должен писаться так, как его легче читать (т.е. в данном случае через switch), а задача компилятора сгенерировать эффективное представление в инструкциях проца вне зависимости от стиля записи кода. Статья анализирует насколько хорошо компилятор с этой задачей справляется, и в этом контексте использование switch вполне уместно.
Некорректным было бы, например, сравнивать разные алгоритмы.
switch - это синтаксический сахар для if
Duff's device с вами не согласен.
вот нашел такое объяснение :
Если какой-либо зависимости в значениях value нет, то switch вполне может быть лучшим вариантом. Если же значение a или b встречаются значительно чаще (например в 95% и 4% случаев соответственно), то if может существенно превосходить в скорости switch.Это связано с особенностью блока предсказания ветвлений процессора. Последовательные if позволяют ему «обучаться» на входных данных и лучше предсказывать нужную ветку программы. В то же время switch, если компилятор сделал из него таблицу и косвенный переход, будет справляться с этой задачей значительно хуже.Например, для архитектур x86 и x86-64 подробнее об switch-против-if можно прочитать в «Intel® 64 and IA-32 Architectures Optimization Reference Manual».Ну и вообще, в таких случаях может быть эффективна гибридная схема:
void f ()
{
if (value == a) // отдельно обрабатываем вероятное значение
...
else if (value == b) // отдельно обрабатываем вероятное значение
...
else switch (value) { // обрабатываем всё остальное
case c: ...
case d: ...
}
}Для уверенности, что компилятор нас правильно понял, ещё бывает полезно обернуть условие (value == a) во что-то подобное __builtin_expect(value == a, 1) или __assume(value == a). Где __builtin_expect и __assume — соответствующие подсказки оптимизатору.
Всё и так вполне корректно. switch - это синтаксический сахар для if. С точки зрения компилятора языка разницы между switch и if-elseif-else нет.
Удачи вам попробовать в case вместо константы засунуть переменную. Тогда узнаете насколько "switch - это синтаксический сахар для if". switch и if не эквивалентны.
Меня всегда удивляло непонимание многими инструкции switch. Это не синтаксический сахар, и эквивалентность с if-м существует только при малом (вроде бы до 4-х) количестве вариантов. Как только их больше, проявляется истинная сущность этой конструкции - переход к требуемой ветке за одно сравнение. Если же у вас 10-ть if-в то переход займёт девять операций сравнения в худшем случае. Где же здесь сахар? Принципиально разный подход!
Вы тут полагаетесь на конкретное поведение компилятора, которое может поменяться в любой момент. Сегодня switch по разному может обработать, завтра цепочку однотипных if-ов распознает и сведёт к таблице...
эквивалентность с if-м существует только при малом (вроде бы до 4-х) количестве вариантов
в себя слышите? Вы конструкции языка дали определение через реализацию конкретного компилятора.
В целом switch выражает какую то семантику и делает проще что-то для компилятора, но это не значит, что компилятору запрещено переписать его как кучу ифов
Меня всегда удивляло непонимание многими инструкции switch. Это не синтаксический сахар, и эквивалентность с if-м существует только при малом (вроде бы до 4-х gcc) количестве вариантов. Как только их больше, проявляется истинная сущность этой конструкции - переход к требуемой ветке за одно сравнение. Если же у вас 10-ть if-в то переход займёт девять операций сравнения в худшем случае. Ну что, эквивалентно перейти за одно сравнение или за девять? Принципиально разный подход!
просто напомню, что вообще то С не напрямую в ассемблер транслируется и то что там в коде написано неособо то и важно
Компилятор может переставлять инструкции как ему вздумается, пока поведение программы от этого не меняется
Без попытки включить pgo тема сишки не до конца раскрыта. Плюс векторные инструкции скорее всего позволили бы значительно улучшить результат, на riscv во всяком случае, этот пример хорошо ложится.
https://news.ycombinator.com/item?id=36618344 — тут были решения, которые векторизируются компилятором, и все становится сильно быстрее
Никакие pgo(как и "кэши") здесь не помогут.
Плюс векторные инструкции скорее всего позволили бы значительно улучшить результат, на riscv во всяком случае, этот пример хорошо ложится.
Оно хорошо ложится на любой камень с возможностью параллельного исполнения.
А если немножко подумать головой, то и ассемблер не нужен.
static short weight [256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-1,0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int run_switches(char *input) {
int res = 0;
char c;
while ((c = *input++)) {
res += weight [c];
}
return res;
}
Условных инструкций внутри глубоких циклов в целях оптимизации лучше вообще избегать, это мешает векторизации.
Собственно, основная уважительная причина для появления условных операторов внутри цикла – это конечный автомат, но его, как правило, не стоит задача ускорять.
Вариант с to_add из поста, на моих замерах в два раза быстрее. И он без ассемблера, если перевести в попугаи из статьи дает 3.4 GiB/s
На моих замерах вариант с to_add из поста в два раза медленнее приведённого мной выше, благодаря использованию излишней памяти в массиве типа int. Но их конкретная сравнительная эффективность, конечно, зависит от размера кеша L1.
Странно, размер L1, уже давно со времен PIII, перевалил за десятки килобайт, но да ладно.
У Intel Core размер L1 Data Cache может составлять 32 килобайта, при этом он поделен на 64 блока по 512 байт. Поэтому 512 байт - важный размер для структуры данных.
Насколько я понимаю, это влияет только на ассоциативность в какой-то мере https://coffeebeforearch.github.io/2020/01/12/cache-associativity.html я бы еще понял если речь шла про кэш линии(64 байта).
Практика – критерий истины. На моём Core i3 сокращение размера таблицы с 1024 до 512 байт ускоряет программу вдвое, дальнейшее сокращение до 256 байт (char[]) не меняет время работы.
У меня ровно противоположный результат char и short, в два раза медленнее int, zen 3.
Вы все молодцы! :) Вы только что личным примером продемонстрировали, почему такими ручными оптимизациями нет смысла заниматься. У компилятора ещё есть шансы учесть такие нюансы при генерации кода для -march=native, а вот ручками хоть на уровне C хоть на уровне ассемблера этим заниматься практически никогда смысла нет, потому что этот код будет работать на разном железе и оптимизация под одно железо нередко даёт противоположный эффект для другого железа.
P.S. А оптимизация на уровне C плюс к этому может давать противоположный эффект на разных компиляторах или версиях одного компилятора.
Смотря в чём состоит цель. Если расчёт длится, например, одну либо две недели, то есть за что бороться. Мы же не обсуждаем, почему автор статьи решил ускорить свой цикл.
Недавно мне пришлось консультировать людей по поводу подходов к оптимизации их программы (фортрановской), где в коде, между прочим, была функция, на всякий случай сохраняющая достигнутое состояние вычислительного процесса для возможности перезапуска, и эта функция вызывалась с периодичностью раз в 30 дней. Я был несколько удивлён флегматичностью программиста, но тем не менее.
Если расчёт длится неделю-две, то обычно один из подходов "просто подождать, потому что ручная оптимизация кода займёт больше времени чем мы выиграем" или "реализовать возможность распараллелить вычисления на несколько серверов" оказывается предпочтительнее ручной оптимизации под конкретный проц на одном конкретном сервере. При этом параллельный запуск на нескольких серверах резко уменьшает пользу оптимизаций под конкретный CPU, потому что высоки шансы, что на этих серверах процы будут отличаться.
Обычно оптимизировать код становится выгодно тогда, когда финансовые затраты на его выполнение заметно превышают финансовые затраты на его ручную оптимизацию (исход которой к тому же заранее предсказать невозможно). Поэтому по факту оптимизацией кода занимаются тогда, когда финансовые затраты на выполнение кода начинают превышать "допустимые" с точки зрения бизнеса.
А временные затраты обычно оптимизируют горизонтальным масштабированием, что хоть и увеличивает финансовые затраты, но зато масштабируется с одной стороны и сводит вопрос необходимости оптимизаций к ранее решённому (когда финансовые затраты превысят "допустимые").
Всё-таки обычно массивные вычисления распараллеливают на одинаковые серверы, потому что иначе увеличение производительности таким образом - вообще малоподъёмная задача. Наиболее широко используемая модель MPI подразумевает (хотя не требует) однородность узлов.
Ну и модель с финансовыми затратами на выполнение несколько наивна, так как обычно в современности не столько стоит денег само машинное время, сколько важно уложиться в сроки работ. Можно, конечно, сказать, что срыв сроков имеет определённую цену, но это применение неподходящего инструмента анализа, так как назначение этой цены неизбежно будет произвольным. Это верно как в макро-, так и в микромасштабе. Каково влияние на стоимость быстродействия программы управления впрыском в автомобильный двигатель, если она не укладывается с расчётами в один такт двигателя? Да нет никакого влияния, такая программа лишена смысла.
А что ещё делать программисту, пока компьютер считает его могучую программу? Как раз и заняться оптимизацией кода.
Если же не стоит задача оптимизировать код, то и нет всех этих вопросов.
При использовании облаков (что наиболее типичный кейс для таких вычислений) гарантировать идентичные CPU крайне проблематично.
Бизнес всегда оперирует только деньгами. Сроки важны, но только потому, что срыв сроков стоит денег. Если уложиться в срок обойдётся в разы дороже, чем срыв сроков - обычно бизнес предпочтёт срыв сроков.
Каково влияние на стоимость быстродействия программы управления впрыском в автомобильный двигатель, если она не укладывается с расчётами в один такт двигателя?
Давайте не будем тянуть сюда довольно редкие кейсы Embedded/RTOS, потому что с ними и так всё ясно: там код должен работать и не "как можно быстрее", и не "как получится", а не медленнее минимально приемлемой границы. Это действительно "другое" и в контекст обсуждаемой статьи не вписывается.
А что ещё делать программисту, пока компьютер считает его могучую программу? Как раз и заняться оптимизацией кода.
Нет. Взять следующую бизнес-таску из бэклога.
Если же не стоит задача оптимизировать код, то и нет всех этих вопросов.
Перед бизнесом? Не стоит, как правило. Бизнес хочет заработать денег. Задача оптимизировать код появляется только тогда, когда бизнес видит возможность на этом заработать ещё больше денег.
Эти монетаристские мантры крайне ограниченно описывают реальность. Код пишется живыми людьми, как каждому из которых в отдельности, так и их объединениям совокупно, вообще наплевать на прибыль собственника. Я уж лично вырос из того возраста и статуса, чтобы делать вид, что меня интересует ход бизнеса, а не мой личный доход и эстетическое чувство. Хотя могу втирать такие темы про "потребности бизнеса" (как будто это у бизнеса имеются потребности) не хуже.
Чем старее и циничнее вы становитесь, тем больше вещей называется своими именами.
Но можно отметить, что стоимость программного продукта создаётся в том числе и метриками кода, одной из которых является его производительность.
Давайте не будем тянуть сюда довольно редкие кейсы Embedded/RTOS
Это не "довольно редкие кейсы", это одно из направлений моей работы, с одной стороны, и вещь, делающая предметно осмысленной обсуждаемую тему - с другой.
В чём цель вашего участия в дискуссии? Доказать, что обсуждаемый предмет вообще не важен? Тогда, может быть, просто вы находитесь вне контекста обсуждения?
Я, кстати, не слышал ни об одном случае, когда вычислительные задачи выносили бы в облако. По логике вещей, оплачивать стопроцентную загрузку чужого железа банально невыгодно, даже если не вспоминать о безопасности.
Код пишется живыми людьми, как каждому из которых в отдельности, так и их объединениям совокупно, вообще наплевать на прибыль собственника.
Безусловно. Но есть нюанс. Если этот код пишется в свободное от работы время - можно делать что угодно. Но в рабочее, т.е. оплаченного тем самым никого не волнующим бизнесом, нужно делать то, что просит бизнес. Потому что иначе получается очень некрасивая ситуация: сотруднику платят за одно, а делает он совсем другое, причём осознанно. Если называть вещи своими именами, то эта вещь называется обман (или саботаж, в зависимости от цели и нанесённого ущерба).
Эти монетаристские мантры крайне ограниченно описывают реальность.
А вот с этим я соглашусь. Я тоже не фанат того, что все и всё пытаются выражать в деньгах. Но и обманывать тех, кто платит мне зарплату, я тоже не считаю приемлемым. Поэтому оптимизациями я лично с удовольствием занимаюсь либо в своё свободное время, либо тогда, когда удаётся убедить бизнес в необходимости данных оптимизаций.
В чём цель вашего участия в дискуссии? Доказать, что обсуждаемый предмет вообще не важен?
Он важен, просто в очень ограниченном наборе кейсов. Из которых на мой взгляд самый распространённый - это разработка оптимизаций для компиляторов. А применение этого подхода для ручной оптимизации кода конкретного приложения для запуска на конкретном CPU - на мой взгляд практически не применимо в реальных бизнес-задачах. Буду только рад, если окажется что я не прав, и кто-то приведёт примеры таких реальных бизнес-задач и окажется, что они встречаются намного чаще, чем мне кажется. Цель моего участия в дискуссии - сделать более очевидным этот набор кейсов.
По логике вещей, оплачивать стопроцентную загрузку чужого железа банально невыгодно, даже если не вспоминать о безопасности.
Так она же не стопроцентная. Такого рода тяжёлые вычислительные задачи обычно либо разовые/периодические, либо сильно зависят от заливаемых юзерами данных. В первом случае сервер чаще простаивает чем работает, во втором количество необходимых для обработки данных серверов сильно плавает в зависимости от текущей нагрузки - и в обоих облако обойдётся намного дешевле собственных серверов.
Но в рабочее, т.е. оплаченного тем самым никого не волнующим бизнесом, нужно делать то, что просит бизнес.
Не то, что просит бизнес, а то, что приказывает непосредственный начальник.
И, раскручивая по индукции, эта цепочка технических указаний никогда не доходит до собственника при сколько-нибудь значительном размере компании. Хотя каждый провозглашает, что действует в интересах бизнеса.
Буду только рад, если окажется что я не прав, и кто-то приведёт примеры таких реальных бизнес-задач и окажется, что они встречаются намного чаще, чем мне кажется.
Ну вот мы в реальной бизнес-задаче укладывали несколько лет назад умножение векторов в шаг дискретизации сигнала АЦП/ЦАП. Там, помню, были и библиотечные ассемблерные процедуры умножения, и эквивалентные преобразования системы уравнений, чтобы привести данные к используемому библиотекой виду, и распараллеливание руками, и всё такое. Между прочим, единственное, что никак не помогло в достижении цели – это приобретённая платная оптимизирующая версия микроконтроллерного компилятора Си вместо бесплатной не оптимизирующей. Эффект от автоматических оптимизаций был близок к нулю.
Такого рода тяжёлые вычислительные задачи обычно либо разовые/периодические, либо сильно зависят от заливаемых юзерами данных
Обычно, если люди считают скажем, прочность методом конечных элементов, то они постоянно её и считают, для чуть разных условий. В какой-то момент останавливаются в уточнении результата, так как упираются в предел производительности. Если высвобождается дополнительное машинное время – считают задачу более точно, это им позволит с конструкции убрать лишний запас.
Вот за одну такую ступенечку и надо было успеть выполнить ввод-вывод и все вычисления по всем каналам.
Если не ошибаюсь, тут синий – выходной сигнал прямо на выходе ЦАП, а жёлтый – он же после выходного фильтра.
Порой можно добиться 6-кратного ускорения путём ручной правки сжатого цикла Си в ассемблере и оптимизации с помощью техник, которые в компиляторы, похоже, ещё не встроили.
Хм.. То есть если вместо исходного кода вы сразу напишите
while (true)
{
char c = *input
if (c == '\0')
return
input++
n = 0
if (c == 'p')
n = -1
if (c == 's')
n = 1
res += n
}то результат тоже будет получен в 6.73 раз быстрее?
Ну так это получается, как будто вы написали алгоритм сортировки пузырьком и хотите чтобы компилятор его оптимизировал в какой-нибудь quicksort.
Вот Вы построили код на С на основе if, о чем я и пытался сказать.
Именно так и оптимизировал автор статьи но на асме, подменив case в С, if-ом в ассме.
Не очень понятно в чем разница? Компилятор в праве трансформировать семантически эквивалентные конструкции пока это не нарушает стандарт.
До сих пор можно встретить компилятор, в которых
i = i + 2 + 2;
i = i + 4;
i += 4;Компилируются по разному. Вы считаете, что это разные вещи?
каким образом сравниваете?
Если по числу символов в строке , то разные ,
если по результату , то разные ( во второй строке I это не i)
если по области хранения и исполнения, то разные.
первая строка может быть исполнена в памяти, а последняя в регистре. Зависит от описания и от компилятора
В первой строке константа 2, а во второй и третьей константа 4. разное.
На самом деле много неопределенного в этих трех строках, поэтому будет зависеть от описания переменных и способа хранения которые здесь не указаны.
Поэтому ответ неопределенный.
I/i это опечатка, телефон правит за меня.
Так вот, оптимизирующие компиляторы сделают все три одинаково. Потому что итог - и на 4 больше чем до. Побочных эффектов нет.
И компилятор может вообще заменить на константу, выбросив все и пересчитав в процессе.
А тупые компиляторы сделают вычисление 2+2 как отдельно в рантайме и только потом добавят...
Вы просто рассуждаете из собственного предположения.
Но Вы ошибаетесь. Ранее я написал, что все зависит от определений и зададаемых параметров компилятору. Можно указать в одном варианте, что переменная в регистре, а в другом что в памяти и компилятор сделает разные вырианты. Можно указать что переменная изменяется из вне, а можно и не указывать. Если дальше переменная не используется, то во втором случае компилятор вообще выкинет это выражение из кода.
Можно указать что 2 и 4 этот константы, в нестираемой памяти и компилятор не заменет 2+2 на 4.
Ну и т д
Поэтому результирующий машинный код непредсказуемый в общем случае.
А попытка обобщить примитивные примеры на все случаи жизни всегда ошибочна, хотя и заманчива.
Расскажите, пожалуйста, как литерал "2" превращается в "константы, в нестираемой памяти"
проще вам почитать загрузку исполняемых приложений,например, у Рихтера. Если упрощенно, то в бинарнике (exe) файле есть несколько блоков данных, в том числе и для констант. В мобильных устройствах (тоже Си) , я гружу константы во flash,чтобы экономить RAM.
Расскажите, пожалуйста, как литералу стать константой.
Для какого процессора пишите?
Мы тут про язык Си. Это НЕ машино-зависимая особенность.
"2" в тексте кода это литерал. "i+2" выражение оперирует идентификатором i, оператором + и литералом 2. Вы понимаете разницу между константой и литералом?
понятна Ваша мысль.
Но можете привести результат оптимизации Ваших примеров компиляторами, c интересом прочитаю.
Остальное лишь Ваше или мое суждение.
Я подозреваю, вы серьёзно так троллите... Но для читателей приведу пример: https://godbolt.org/z/E9ssr1n1c
Пять вариантов:
num = num + 2 + 2;
num = 2 + num + 2;
num = num + 4;
num += 4;
num += 2 + 2;Если с -O0 разница есть (по понятным причинам), на -O1 уже все компиляторы выдают одинаковый код для всех 5 выражений.
ну и, чтоб два раза не вставать, еще пример: https://godbolt.org/z/YPve5vK45
Опять же, уже на -O1 -- найдите, пожалуйста, разницу, между сгенерированным кодом, хотя на входе -- свич, иф, иф-елзе.
вот такой пример, разница на -O2 и -O1, а на -O0 -разницы нет:
volatile int num1;
int s0() {
num1 = num1 + 2 + 2;
return num1;
}
int num;
int s1() {
num = 2 + num + 2;
return num;
}
результат:
s0():
mov eax, DWORD PTR num1[rip]
add eax, 4
mov DWORD PTR num1[rip], eax
mov eax, DWORD PTR num1[rip]
ret
s1():
mov eax, DWORD PTR num[rip]
add eax, 4
mov DWORD PTR num[rip], eax
ret
num:
.zero 4
num1:
.zero 4
Повторю еще раз, результат работы компилятора непредсказуемый, чем больше код, тем больше будет чудес.
И что вы хотите мне тут сказать?
Оба случая две двойки схлопнулись в одну четвёрку.
Хочу сказать, размер кода асм разный, а оператор С один и тот же.
А чтобы двойки не схлопывались для процессора SOC можно указать,что они во флеш.
Но пусть будет по-вашему, мне все равно.
вот пример, в котором код результата изменяется, хотя начальный код функций одинаковый.
попробуйте с разными ключами будет интересно особенно с -O1 или -O2.
int const x=2;
int s0(int num) {
num = num + x + x;
return num;
}
volatile int const y=2;
int s1(int num) {
num = num + y + y;
return num;
}
и не надо кругом видеть заговор.
Я не знаю о каком заговоре идёт речь.
Компилятор имеет право на оптимизации в рамках, заданными стандартом -- где находятся чекпоинты, какие побочные эффекты прописаны и так далее.
Форма (if / switch / и так далее) не является четким определением того, как будет выглядеть итоговый машинный код до тех пор, пока все эффекты эквивалентны исходному коду.
Вы привели пример когда два НЕ эквивалентных исходных кода генерируют различный машинный код. Спасибо, кэп?
Мой аргумент был о том, что два различных исходных кода, использующих разную запись исходника (с if и switch) но выполняющих одну и ту же работу с одними и теми же данными -- являющиеся эквивалентами друг друга -- приводят к эквивалентному машинному коду, что еще раз доказывает, что if и switch эквивалентны (до тех пор, пока они использованы эквивалентно! это не означает, что они эквивалентны всегда).
Исключительно синтаксическое изменение исходного кода не должно приводить к изменениям производительности -- оптимизирующие компиляторы для того и существуют, чтобы это делать.
Вот примеры для сравнения switch и if then else
вариант 1:
int run_switches(char *input) {
int res = 0;
while (true) {
char c = *input++;
switch (c) {
case 's': res ++; break;
case 'p': res --; break;
case '\0': return res;
default: break;
}
}
}
------------------------------
Вариант 2:
int run_switche(char *input) {
int res = 0; char c;
while(true){
c=*input++;
if (c=='s') res ++; else if (c=='p') res --; else if (c==0) return res;
}
}
компилировал на pocc.exe под Windows
тест на строке в 23835 символов
вариант 1: 1.16 GiB/s; ( в статье на GCC 0.25 GiB/s)
вариант 2: 1.26 GiB/s;
вариант с массивом из статьи pocc.exe 2.0 GiB/s (в статье GCC 1.98 GiB/s)
Для integer, наверное, одинаковые, для double необязательно (из-за потерь в точности):
double i = 9007199254740991;
i = i + 2 + 2; //9007199254740994
i = i + 4; //9007199254740996
Сложно как-то! Можно в две строчки(не считая скобочек) уместить :)
while(c = *input++)
{
res += (c == 'p') ? -1 : ((c == 's') ? 1 : 0);
}Хотя, конечно, писать такой код неправильно.
Интересно было бы сравнить с этим... На современном С++ так сказать
https://godbolt.org/z/fv7GxeYsq
#include <algorithm>
#include <string>
int run_switches(std::string_view input) {
return std::count(begin(input), end(input), 's') -
std::count(begin(input), end(input), 'p');
}Там есть существенное отличие, что известен конец строки. Eсли его передавать, то и "вариант на Си", раскочегаривается на векторизацию и simd/sse.
ну посчитайте strlen, может так выйти что всё равно будет быстрее
У меня получилось где-то на 30% хуже, варианта с табличкой, но вообще неожиданно хорошо, несмотря на 3 прохода по памяти (2 count + 1 strlen).
#include <algorithm>
#include <string>
#include <string.h>
int run_switches(const char* input) {
const char* begin_it = input;
const char* end_it = input + strlen(input);
return std::count(begin_it, end_it, 's') -
std::count(begin_it, end_it, 'p');
}
PS: а на clang, оказалась в 1.5 раза быстрее
Автоматически? Нет даже банальный "while (*it != '\0') ++it;" не векторизуется.
По большому счёту да, автоматически. Нужно только немного помочь компилятору. while(*it) - здесь сказано "до нуля и не далее". Там нечего параллелить.
Речь шла о команде sse через, которую можно потенциально векторизовать данный цикл, эквивалентный strlen. (там в конце вычитание из начального указателя очевидно)
Ничего не понял, честно говоря. Во первых, sse/не sse - здесь никакой роли не играет. Любая возможность железа параллельно исполнять код здесь так же будет работать.
Во вторых, я отвечал на вот это:
Автоматически? Нет даже банальный "while (*it != '\0') ++it;" не векторизуется.
Я указал на то, что это векторизуется "автоматически", будь оно не так топорно записано. О причинах не-векторизации я также сообщил. Команда sse никакого отношения к делу не имеет и просто является частным случаем, не более.
Вариант с двумя std::count плох тем, что требует двукратного чтения строки, что может быть накладно для хоть сколько нибудь длинных строк (не вмещающихся в кеш-линию). Такой вариант наверняка кратно медленнее оригинала.
В C++20 завезли [[likely]] и [[unlikely]]. Так то buildin были и в GCC, и в Clang, например __builtin_expect. Если я знаю заранее, что у меня тут happy-path, или как-то заранее знаю, что чаще всего случится, то пишу likely, и даже в ASM не заглядываю. Другое дело, сможет ли компилятор векторизовать. Вот тут, желательно глянуть в ASM, и разными конструкциями, заставить компилятор сделать как надо.
Префы здесь ничем не помогут. Пока есть return в цикле уровень параллельности околонулевой.
Никогда не говорит нет. Проверяй свой код на https://godbolt.org с trunk компилятором, они всегда работают над улучшением.
Интересно кто-нибудь уже ваяет компилятор на нейронных сетях чтобы получать оптимальную оптимизацию словно сделана вручную...
Не то, но ai сам лезет в ассемблер https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
Не увидел ни в статье, ни в комментариях хотя бы намёка на производительность. Написал вам минимально адекватный бенч.
#define step_size 128
#define auto __auto_type
#define proc(v) ({ auto _v = (v); (_v == 's') - (_v == 'p'); })
#define aligned(ptr, align) ({ \
auto _ptr = (ptr); \
auto _align = (align); \
auto _r = (long long)_ptr & _align - 1; \
_r ? _ptr + (_align - _r) : _ptr; \
})
int run_switches(const unsigned char* i) {
auto r = 0;
for (auto head_end = aligned(i, step_size); i != head_end && *i; ++i) r += proc(*i);
while (1) {
signed char step_r = 0;
unsigned char rs[step_size];
for (auto n = 0; n != sizeof(rs); ++n) {
rs[n] = i[n] ? 0 : ~0;
step_r += proc(i[n]);
}
long long* _ = rs;
if (_[0] | _[1] | _[2] | _[3] | _[4] | _[5] | _[6] | _[7] | _[8] | _[9] | _[10] | _[11] | _[12] | _[13] | _[14] | _[15]) {
while (*i) r += proc(*i++);
break;
}
r += step_r;
i += sizeof(rs);
}
return r;
}Собирать так: gcc -std=gnu2x -Ofast -march=native -fwhole-program -obench bench.c. Код автора с to_add выдаёт на моём мк(целерон какой-то) ~4.5 Gib/s. Моя версия выдаёт 26.6 Gib/s. Это овер 5 раз. Заморачиваться на каких-то крополях мне лень.
Зато с читабельностью этого варианта просто беда…
Для чего вообще нужен rs? Почему не заменить rs[n] = i[n] ? 0 : ~0 на if !i[n] { return r + step_r }?
Читабельность здесь мимо по большому счёту, поскольку целью заявлялось "быстрее". А так, это борьба с компилятором(и отчасти с C). clang нормально работает на таком:
while (1) {
signed char step_r = 0;
unsigned char zero = 0;
for (auto n = 0; n != step_size; ++n) {
zero |= !i[n];
step_r += proc(i[n]);
}
if (zero) {
while (*i) r += proc(*i++);
break;
}
r += step_r;
i += step_size;
}Но gcc не смогает и там всего 20Gib/s. Поэтому приходится хаками "расслаблять" некоторые правила языка.
return в цикле очевидно всё сломает и выдаст пару Gib/s, как в начале статьи.
А за счёт чего выигрыш? Цикл по 128 байт внутри которого ничего кроме арифметики нет позволяет компилятору использовать AVX?
Отличные замечания. Идея, как я понял, в том, что мы гарантируем выполнение основного цикла ровно 128 раз, и за счёт этого можем использовать векторную операцию?
Идея в повышении уровня параллельности кода насколько это возможно. "скалярный"(с уровнем параллельности ~0) код всегда будет медленным. И компилятор ничего с этим сделать не сможет. Вот нормальный код ни компилятору, ни железу не мешает. Не имеет лишних зависимостей по данным/интсрукциям.
128 или нет - это не важно. Если проще - нужно более одного. Даже сильно более. На самом деле я там забыл вернуть обратно на 64 и именно со 128 там будет переполнение на "sssss...". Но сути это не меняет.
Тут критика из Тви подъехала, что скажете?
Так и есть, внутренний цикл, ожидает кратность массива step_size, и эта строчка легко вылетает за границы:
for (auto n = 0; n != sizeof(rs); ++n) {
rs[n] = i[n] ? 0 : ~0;
step_r += proc(i[n]);
}Для чистоты эксперимента я туда трассировку индекса добавил, и да при размере входного массива 1000000, идет доступ к диапазонам индекса 1000000 - 1000047. Собственно в этом и вся соль задачи, без векторизации strlen это все бесполезно, а сделать ее автоматически довольно сложно, так как нет гарантии за выход за границы null terminated string, если шагать по размерности simd регистра. @0xd34df00d предложил вариант со специальной инструкцией SSE4, но компилятор самостоятельно так вряд ли умеют.
Я вам уже выше отвечал на ваши заблуждения про "векторизация"/"strlen"/"автоматически"/"команда sse" и прочее.
А так, вопросы для вас ниже. Расскажете мне про чтение за '\0' и что мне помешает это делать.
Чтение за \0 это UB, очевидно, если вы выделили память ptr = malloc(1000000), то последний указатель это ptr + 1000000, а не ptr + 1 000 047. Не помешает, как и с любым UB, все будет работать чисто случайно на некоторых входных данных и условиях.
Вы упомянули strlen выходящий за пределы массива из glibc, может быть покажете, а то я в его коде этого не увидел?
В общем, мне эти споры на "кому раньше надоест" мало интересны. Рассказываете про "падает" - показывете. Вы это говорили прямым текстом, эксперт из "тви" также это заявлял. До тех пор пока нет падения - в сотый раз слушать "это же ub, как ты можешь отрицать!!!" - это всё мимо.
Изучите хотя бы базовые принципы работы памяти. Там про страницы и прочее(что вы успели нагуглить чуть ранее). Далее уже будете рассуждать.
Конечно, я нагуглил, вы лучше сами погуглите, что такое UB, а то видимо еще нет. Ваш код - UB, и то что он не падает, лишь счастливая случайность страничной организации системы памяти.
Ну что можно сказать. Фиксируем. Персонаж действует по обозначенной мной схеме - надеется что мне просто надоест отвечать.
Опять пошли заходы про "счастливая случайность", хотя я уже отвечал на это и оказалось вероятность "счастья" - 100%. Никакого ответа на это не последовало и не последует. Также фиксируем.
Про "нагуглил" - это очевидный факт, потому как зная хотя бы базовые принципы организации памяти рассуждать вот таким образом:
Собственно в этом и вся соль задачи, без векторизации strlen это все бесполезно, а сделать ее автоматически довольно сложно, так как нет гарантии за выход за границы null terminated string, если шагать по размерности simd регистра.
просто невозможно. Поэтому данный персонаж ничего не знал, а теперь погуглил, осознал свою неправоту и сейчас пытается съехать с темы на различные абстрактные понятия типа ub и стандарта.
Так давайте по простому. Ваш код это UB, Да или Нет?
А то эти детские наезды, уже немного поднадоели.
Давайте по простому. Мой код падает, Да или Нет?
А то эти детские наезды, уже немного поднадоели.
Код не падает, на некотором распространенном конечном наборе платформ и компиляторов. Но при этом он очевидно является UB, так как вы признали, что происходит выход за пределы массива.
И вот, что нам говорит стандарт по этому поводу:
Accessing outside the array bounds is undefined behavior, from the c99 draft standard section Annex J.2 J.2 Undefined behavior includes the follow point: An array subscript is out of range, even if an object is apparently accessible with the given subscript (as in the lvalue expression a[1][7] given the declaration int a[4][5]) (6.5.6).
Отсутствие UB, не возможно доказать работоспособностью, на любом конечном наборе платформ и компиляторов.
Так что да: ваш код не падает, но является явным UB.
Код не падает
Утверждалось обратное - показывайте, либо признавайте что врали. До этого момента все заявления мимо.
на некотором распространенном конечном наборе платформ и компиляторов.
В студию набор на котором падает.
Так что да: ваш код не падает, но является явным UB.
Персонаж расписался в своей(и того твиттер-эксперта) лжи. Молодец. Теперь ваша задача показать, что следует из этого ub. Ведь если оно никак не влияет на поведение, да и вообще никак не наблюдается - оно ничего не значит и его нет. Там чайник какой-то модный одно время на орбите летал - вот это то самый случай.
Таких обнаглевших спамеров нечасто встретишь. Опять же, радостные вести для подобных персонажей - любой "перегиб" с моей стороны - и я теряю возможность отвечать(бан/минуса). Удобно.
Как такое вообще может быть? Источник байки не подкинете, а то я уже 10 минут гугл насилую безрезультатно.
Такое может быть по одной причине - это оправдания и к реальности отношения не имеет. Эксперт протирает штаны уже кучу лет, а тут бам - кто-то показывает новый трюк.
Далее у эксперта два пути: либо признать своё непонимание(и похоронить себя как эксперта), либо начинать придумывать разные отмазки.
Особенно мне нравятся оправдания, которые никак не проверяются - там что-нибудь про будущее(кстати, насколько далёкое?), про новые версии компиляторов(о которых эксперт ничего не знает), квантовые вычисления и прочее. Не нужно на это ловится.
Не нужно на это ловится
Да я не ловлюсь, у меня восприятие таких штук эмм феноменологическое. Пример Дэдфуд кстати привёл занятный.
Я, к счастью, на сях пишу может раз-два в год ради домашних экспериментов, всё тут же при мне компилится/исполняется, и, в общем, я бы стал делать как вы – но не 128, конечно, а 8 – потому что мне это сразу без объяснений понятно.
Что, в общем, вполне соответствует условиям задачи: вот прямо здесь и сейчас выдавить всё что можно – при имеющихся текущих вводных, без всякой ерунды типа «а вдруг через год не заработает».
Но такой код, абьюзающий ub, распространять я бы стал только в качестве примера-демонстрашки.
У меня эта позиция, в общем, только сейчас чётко сформулировалась, спасибо вам за это )
Да я не ловлюсь, у меня восприятие таких штук эмм феноменологическое.
Я, к счастью, на сях пишу может раз-два в год
к счастью
Ну вот, видите - вас уже убедили в некой сложности C. UB пропаганда - это меинлайн подобной методички.
Причём в целом, да - писать на C(нормальный код, а не хелворды) действительно сложнее. Но в случае не-хелворда - выбора-то и нет. Никакой иной язык не позволяет настолько же эффективное исполнение. Остальное просто пыль и мы все сидели бы сейчас на калькуляторах, если бы не C и решения из C-мира.
я бы стал делать как вы – но не 128, конечно, а 8 – потому что мне это сразу без объяснений понятно.
Ну 8 там мало будет. 32/64 - это уже нормально. На 16 авось оно что-то сможет.
Но такой код, абьюзающий ub, распространять я бы стал только в качестве примера-демонстрашки.
Опять же, нет. Оно не абузит ub, оно абузит матчасть, с которой у многих дела обстоят неважно. UB - понятие стандарта и появилось оно там из-за того, что:
стандарт не может оперировать конкретными условиями - это абстрактное описание
всегда легче написать "вот за это мы никак не отвечаем" чем пытаться как-либо описывать реальность
А в реальности конкретно здесь есть только железо/память, котороя работает так, как работает. Никакие стандарты и прочее железо не волнуют.
А в реальности конкретно здесь есть только железо/память, котороя работает так, как работает
В этой конкретной задачке в этой конкретной постановке – ну да.
Но в моей например реальности если я компилю какой-то сторонний (не мной написанный) код на сях, таргетом скорее всего будет wasm. И оно почти наверняка не заработает с произвольной длиной строки ни с каким степ-сайзом больше 4. Потому что wasm просто не даст читать за границами строки, он проверки за вас сделает по-любому, а буферы он выделяет кратно 32 битам. Проверю на досуге.
Ну вот, видите - вас уже убедили в некой сложности C.
Да бросьте, я в нынешней терминологии дед, меня поздно убеждать. В моей вселенной уже давно если надо быстро – то С, если прямо совсем распределёнщина – Erlang, всё остальное – JS норм. Ну сейчас вот Питон ещё добавился для всякого с ML.
царь
В школу слёту.
Ровно все эти вопросы можно было бы задать лет пять назад
Не, отсылки на что-то иное - сразу мимо. Были заданы конкретные вопросы, в том числе главный из них ниже.
Попытки в ответ на это проехаться демагогией про «а насколько далёкое будущее?» — это не более чем демагогия.
Классика - сектант всегда попытается приписать оппоненту свои свойства. Ведь демагогией является именно необозначение сроков - и тогда всегда можно сказать "ну просто время ещё не пришло" и так до бесконечности. Но наш герой получил плохую подготовку(или просто охренел, что более вероятно) и назвал "демагогией" обратное.
В целом, спорить с данным персонажем смысла никакого. Его мотивация очевидна - он спутал меня с царём и далее просто побежал мстить и гадить. А так как сам персонаж нигде и никак не состоялся - мы имеем то, что имеем: максимум болтовни и ноль кода. А болтовня меня не интересует.
Да ладно, версия компилятора вышла лет 5 назад, а про стрикт алиасинг разговры уже больше 10 лет назад. Так что какой-то внезапности не наблюдаю.
Это основное. Ваша задача показать, каким образом приведённый код можно "оптимизировать" и вызвать этим проблемы. Без этого подобные рассуждения ничего не стоят.
Да, код падает.
char c[8128];
int main() {
char* p = & c[8100];
memset(p, 'p', 20);
*(p + 21) = 0;
run_switches(p);
}Выдаёт segmentation fault на вашей реализации и не выдаёт на простых без UB.
gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04.1)
Собирал вот так:
rm a.out; gcc -std=gnu2x -Ofast -march=native -fwhole-program a.c; ./a.outВы бы хоть посмотрели, из-за чего именно он падает. Ну да, ладно, допустим вы далеки от C.
Я там после for head_end забыл вписать if (!*i) return r; - это не то, о чём говорили ub-персонажи.
А я посмотрел. Однако же просьба была вызвать падение в коде, вызванное UB от обращения позади нуля. Я вызвал? Вызвал. Оно упало из-за обращения к следующему после выравнивания. Да, на современных архитектурах, вызвать падение "на пальцах" можно только в этом месте.
Остальной код лезет в лишние места, но только в пределах выровненных 128 байт. То есть вызвать проблему всё еще можно -- напрмер, в случае обращения к какому-либо устройству через MMIO если дёргать не поддержанные адреса.
Еще можно получить шар с волосами на архитектурах где размер страницы меньше 128 байт.
Еще можно напороться на параноидальный гипервизор, контролирующий доступ в пределах субстраниц.
Исправленный код допустим даже в продакшен (и даже я бы принял его с подавлением санитайзера в этом случае) но только при условии комментария и инит-теста что размер страницы больше 128.
Однако же просьба была вызвать падение в коде, вызванное UB от обращения позади нуля.
Неверно. Задача была вызвать падение из-за широкого чтения позади нуля. Вы показали пропущенный return, который не имеет отношения к делу. Вам следует изучить тему для начала, а далее уже отвечать. Какие-то ассоциации из подкорки вроде "и там после 0, и там после 0 - значит это одно и то же" - сразу мимо.
То есть вызвать проблему всё еще можно -- напрмер, в случае обращения к какому-либо устройству через MMIO если дёргать не поддержанные адреса.
Ну фантазии меня мало интересуют. Это нужно показать.
Еще можно получить шар с волосами на архитектурах где размер страницы меньше 128 байт.
Куллстори. Архитектуру в студию. Ну кстати, я верно задетектил абсолютное непонимание, ведь это 128 - от него ничего не зависит и это можно менять.
Еще можно напороться на параноидальный гипервизор, контролирующий доступ в пределах субстраниц.
Ога.
Исправленный код допустим даже в продакшен
Боже, эти откровения. Рассказывали про кучу проблем, а теперь бам - оказывается можно тест бахнуть и всё сразу же становиться нормально.
А в целом да - код работает, а все перечисленные "проблемы" - просто фантазии, даже тест не нужен.
это всё мимо
А вдруг у вас найдётся час-другой написать про это материал? Было бы круто, иллюзии по этому поводу прямо массовое явление, там в тви чёрте-что творится.
предложил вариант со специальной инструкцией SSE4
и как же она будет работать не выходя за границу? =)
Тут нечего особенно говорить - обычный "ньюфаг", который где-то услышал про санитайзеры и ub. Только вот ему не рассказали про ложные срабатывания этих санитайзеров. Схема типичная - где-то что-то увидел, ничего не понял и побежал срывать покровы.
А по поводу ub, открою секрет, но ничего не мешает читать далее '\0'. Поэтому данный эксперт идёт сначала смотреть код strlen/memchr/прочих функций из glibc, а далее начинает отрывать себе руки и всё остальное(ну это его желание, что поделать).
В общем, условия просты - для обоснования ub эксперту нужно сообщить что мне помешает читать память далее '\0'. А также что мешает делать тоже самое glibc. Всё просто.
Ах да, я как-то даже не сомневался. Если кому-то интересно, мотивация данного эксперта:
Это очередной адепт того самого языка программирования(который убийца c/++, да). Ладно, я не буду рассказывать здесь, что это за адепты и в чём их суть, а то меня забанят за пару минут.
Что значит не мешает? У вас индексы вылетают за пределы массива, это все не падает только по счастливой случайности, так не влезает на границу страницы.
Да, и код ваш мягко говоря "переусложнен", если знать размер массива, или иметь гарантии, что он кратен размеру simd регистра. То прекрасно векторизуется самый очевидный вариант:
#include <string.h>
int run_switches(const char* input)
{
size_t n = strlen(input);
int res = 0;
for (size_t i = 0; i < n; ++i)
{
res += (input[i] == 's') ? +1 : 0;
res += (input[i] == 'p') ? -1 : 0;
}
return res;
}https://godbolt.org/z/qx8zGG6do
К слову несмотря на strlen, он у меня вышел в два раза быстрее варианта с табличкой, потому что strlen из стандартной библиотеки раскочегарен по полной.
У вас индексы вылетают за пределы массива, это все не падает только по счастливой случайности, так не влезает на границу страницы.
Ога.
не влезает на границу страницы.
Суть. И да - "случайно" - покажете мне падение?
Да, и код ваш мягко говоря "переусложнен"
Это оправдания. Ваш не переусложнённый код выдаёт выдаёт перф - внимание - 5 Gib/s. Это сильно.
потому что strlen из стандартной библиотеки раскочегарен по полной.
Потому что написан знающими людьми, а не вчерашними студентами, которые узнали вчера про -fsanitize из гугла.
Ну и да, ответ за glibc strlen и прочее - где он? Почему проигнорировали? Это другое? )
Суть. И да - "случайно" - покажете мне падение?
Отлично, если вы скажите, что ваш код работает только по одной причине: потому что не происходит пересечения границы страницы, хотя с точки зрения стандарта это очевидное UB. На этом мы договоримся.
Что значит договоримся? Вы рассказывали про "падает" - показать не смогли, оказалось ничего и никогда не падает. Теперь начали рассказывать про какой-то стандарт и в целом пытаться съехать с темы.
С болтунами договориться невозможно по определению, поскольку договор основывается на том, что слова соответствуют реальности. Ваши не соответствуют. Какие ещё "договоримся", боже.
Вы вообще в курсе, что отсутствие UB, в общем случаи невозможно доказать, конечным количеством тестов, на конечном наборе конфигураций? Пока, что на наиболее распространенных платформах, и версиях компиляторов "не падает".
Но в данном случаи вы даже не отрицаете, что происходит выход за пределы массива, это очевидно. Выход за пределы массива, по стандарту это UB.
На этом можно разговор заканчивать, потому что вы видимо из тех, кто начинает верить в UB. Только когда начинает падать, на какой-то следующей версии компилятора или другой аппаратной платформе.
Так, заспам про "ub" будет продолжаться до последнего. Но тут интересно другое:
Вы вообще в курсе, что отсутствие UB, в общем случаи невозможно доказать, конечным количеством тестов, на конечном наборе конфигураций?
И вот данный персонаж(а также твиттер-эксперт) пытаются требовать с меня именно эти доказательства. Это совсем нелепое позорище. Т. е. именно они должны доказывать наличие этого ub/падает/прочее. Но пока не получилось(и далее также не получится).
Но в данном случаи вы даже не отрицаете, что происходит выход за пределы массива, это очевидно
Совсем заврался. Выход я нигде не отрицал, я отрицал негативные(да и вообще хоть какие-либо наблюдаемые) эффекты этого выхода. Ой, персонаж запутался в элементарной логике. Ну ничего, бывает.
В общем, хотите поиграть в дурачка - это не ко мне. Ко мне приходите вместе с коркой от упавшей функции.
Т. е. именно они должны доказывать наличие этого ub/падает/прочее. Но пока не получилось(и далее также не получится).
Так это вы и пытаетесь доказать отсутствие UB, предоставляя конечный набор тестов. Любой конечный набор тестов не является доказательством отсутствия UB. В данном случаи, корректная работа конечного набора тестов, и является частным случаем UB.
Наличие UB, можно доказать основываясь на аналитические построения стандарта. В данном случаи мы очевидно имеем выход за пределы массива, выход за пределы массива - является UB. Так что совсем не понятно с чем вы спорите.
Адекватный подход: это признать, что код является UB, но при этом работает на некотором распространенном наборе компиляторов и платформ. Это так и есть, и с этим спорить бессмысленно.
Так это вы и пытаетесь доказать отсутствие UB, предоставляя конечный набор тестов.
Неверно. Вы говорите есть ub - показываете его и последствия этого ub. Нет последствий ub - нет и самого ub. Всё просто.
Вы видимо довольно плохо знаете историю. Негативные проявления UB, появлялись и просто с выходом следующих поколений, более умных компиляторов. Не падает - это не аргумент, против UB, по крайней мере в приличном обществе. UB очевидно есть, то что вам не могут предъявить падения при некоторых конфигурациях абсолютно ничего не доказывает. Добавьте по меньшей мере -fsanitize, упадет. Но для вас это тоже не аргумент. )
Сам даже забыл уже - где корка от падения? Снова не смоглось?
Тут надо бы начать с того, что, ни из чего не следует, что UB само по себе – это что-то плохое. Плохо, когда от него ожидается какое-то конкретное поведение. А в данном случае нас устраивает любое поведение с точки зрения семантики языка Си.
Довольно известная шутка, что UB может запустить форматирование диска. В случаи UB никакой семантики нет, есть только везение, или очень большое невезение. В данном случаи мы опираемся на простой факт, что доступ будет происходить в границах валидной страницы. При этом очевидно происходит доступ за границы массива. В самом плохом и неудачном случаи, компилятор может просто сломать код основываяась на том, что UB теоретически возможна, и будет абсолютно прав.
Это неправильная шутка. UB с точки зрения стандарта языка Си означает только то, что конкретный результат выполнения операции не выводим из требований стандарта. Когда мы обращаемся с чтением к элементу массива за его границами, то не можем исходя из стандарта предсказать, какое в точности значение получим. Именно этот факт и обозначается термином UB.
То, что результат операции представляет собой UB, само по себе не означает, что эта операция запрещена или не имеет определённого результата вообще.
А страницы и всякие сегфолты – это понятия машинного языка, а не Си. И с точки зрения машинного языка поведение программы в данном случае вполне определено.
У нас очевидно разные стандарты:
The definition of undefined behavior:
C11(ISO/IEC 9899:201x) §3.4.3
1 undefined behavior
behavior, upon use of a non portable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements
2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).
3 EXAMPLE An example of undefined behavior is the behavior on integer overflow.
There is also a list of undefined behaviors in C11 §J.2 Undefined behavior
По-моему, тут написано именно то, что я написал.
... поведение, в результате использования непортабельного или ошибочного кода или ошибочных данных, в отношении которого данный стандарт не предъявляет требований...
Нет, я конечно могу и перевести:
2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).
Возможные UB, относятся к диапазону возможностей: от полного игнорирования ситуации с непредсказуемыми результатами, до поведения в процессе трансляции или выполнения программы в соответствии с документированными характеристиками среды (с выдачей или нет, диагностического сообщения), а так же завершения трансляции или исполнения программы. (с выводом диагностического сообщения).
Так что любое UB, может привести как минимум к завершению программы в лучшем случаи, а в худшем нарушение констинстентности внутреннего состояния с произвольными последствиями.
Не любое UB может привести ко всем этим бедам, а возможны UB, приводящие к каким-то из них. Но стандарт, как написано выше, не предъявляет требований, поэтому это просто примеры.
А откуда вы знаете, какие UB приведут к каким бедам?
Со временем компиляторы становятся умнее, и там где раньше UB код работал "предсказуемо", появляются оптимизации, способные привести к "произвольному" поведению.
Ну всё правильно, результат операции не определён в стандарте. Это и есть UB. Он, тем не менее, вполне конкретный в каждой реализации.
Между прочим, современный компилятор не содержит таких странностей.
Самая большая проблема с UB, что с ними как в математике, из ложного утверждения можно вывести, что угодно. Так же и компилятор может исходя из утверждений отсутствия UB, вывести что угодно. К примеру, просто удалить ненужный по его мнению код, как к примеру здесь:
https://eyalitkin.wordpress.com/2016/10/12/integer-overflow-undefined-bahavior/
Первой операции проверки просто нет, она оптимизирована.
результат операции не определён в стандарте. Это и есть UB. Он, тем не менее, вполне конкретный в каждой реализации.
В стандарте есть три уровня неопределённости: undefined, unspecified, implementation-defined. (Это то, почему я предпочитаю писать UdB, а не UB - потому что есть ещё UsB.)
Формулировка, которую вы дали - "вполне конкретный в каждой реализации" - это implementation-defined. Это очень хороший случай, если так.
А вот UdB хуже - действительно, формально компилятор имеет право сделать в этом случае всё что угодно, даже воткнуть совершенно другую функциональность, которая там и не предполагалась. Увы.
Реально такие возможности у компилятора достаточно локальны, и код наобум он не генерирует, но и в них могут быть ой неожиданности.
Что запрещает компилятору доопредeлить UdB до implementation defined и обозначить это в документации?
Что запрещает компилятору доопредeлить UdB до implementation defined
Запрета собственно нет, но есть следующие предпосылки к этому:
1. Много случаев, где при нарушении может проявляться UdB, без нарушения дают возможности оптимизаций. Например, с strict aliasing резко расширяются возможности кэширования элементов массивов или структур в регистрах. Предположение о непереполнении в арифметике позволяет перегруппировку операций или избавление от лишних проверок, по типу x+1>x ==> true. Я не собирал ссылки и сейчас быстро не нашёл, но видел утверждение, что в достаточно реальных примерах на этом можно получить 20-30% производительности.
2. Компиляторы, даже свободного софта как GCC или Clang, участвуют в гонке (частично коммерческой) за скоростью выходного кода: сильно отстанут - их не будут финансировать авторы целевого софта, дистрибутивов, производители железа... Поэтому потеря >=20% производительности для них недопустима. Заметим, что Microsoft тут больше нуждается в совместимости, чем команды этих двух (!), и по отношению ко многим типовым UdB у него сильно более расслабленное отношение - не пытается выдавить проценты.
В идеале тут хотелось бы стандартизованного межвендорского средства со списком всех возможных UdB и стандартных контекстных опций "вот тут такое мы допускаем". Но, похоже, никого пока настолько не припекло, чтобы вводить в стандарт. Для тех кому нужно - есть опции компиляции (я видел -O0 на крупные проекты целиком чтобы не думать о проблеме вообще), есть `#pragma GCC optimize` или атрибуты функции, которые позволяет задавать другой уровень для функции. С этим всем важность пробивания в стандарт как-то снизилась.
Есть и обратные примеры, type punning через union. А выигрыш в 20% не нужен если это сломает большую часть кодовых баз.
Есть и обратные примеры, type punning через union
Обратные чему, собственно?
Type punning через union, насколько я знаю, гарантируется более-менее для C, но не C++. Обсуждение (результаты вроде актуальны). Вообще это одна из самых сомнительных тут вещей. Я предпочитаю код, где такое происходит, выносить в отдельные исходные файлы и выключать strict aliasing в них.
Для C++20 есть bit_cast. Для предшествующих версий и компиляторов GCC, Clang работает memcpy (memmove), у них есть спец. оптимизация для этого. Но на MS это так не переносится.
Ещё есть грубоватый хак с барьером памяти компилятора, типа asm volatile("":::"memory") или, начиная с C11, atomic_signal_fence(memory_order_seq_cst). Но при нём весь доступ к нелокальным переменным рубится на "до" и "после" с запретом кэширования в регистрах. Может быть слишком жёстко. И снова для MS так не работает.
У меня 100% Unix, а GCC или Clang - вопрос рельефа местности (GCC заметно чаще). Тут я наполовину в безопасности. Но всё равно надо наблюдать за выходками новых версий.
А выигрыш в 20% не нужен если это сломает большую часть кодовых баз.
Так они варят эту лягушку мееедленно. Но в то же время именно у авторов GCC и Clang тут позиция "кто не укрылся - сам виноват", и целостность кодовых баз для них не в приоритете. Уже сколько скандалов было, лично Линус факами кидался.
В некоторых языках, кстати, выход за границы массива можно явным образом разрешать (PL/I, Ада, новый Паскаль, старый Фортран).
У меня в работе однажды была программа, содержащая некую заимствованную процедуру кодирования данных для передачи в канал связи, написанную в древнейшие времена на Фортране и позже переведённую её автором на Паскаль. Эту процедуру в целом совершенно невозможно было понять, так как она представляла собой лапшу из goto и односимвольных имён переменных. Факт, однако же был в том, что, если разрешить контроль за границами массива, то она падала, а если запретить, то работала нормально. Я проследил её алгоритм и выяснил, что там в определённых условиях перед окончанием работы берётся лишний элемент массива, но никак потом не используется в результате. Так эта процедура до сих пор и работает, уже лет 40 или 50, наверное.
Всё ядро операционной системы, например, построено на разыменовании указателей, сконструированных из целых чисел, и других подобных вещах, являющихся несомненным UB. Просто потому, что в абстрактных категориях с аппаратурой работать невозможно.
Компилятор вправе не компилировать машиннозависимый код?
Всё ядро операционной системы, например, построено на разыменовании указателей, сконструированных из целых чисел, и других подобных вещах, являющихся несомненным UB.
Если вы про Linux, то он по факту и не на C написан.
Вот так новость, а на чём же? Самый что ни на есть Си. Только стандартная библиотека не используется, что вполне нормальный ход.
На C с нестандартными расширениями от GCC
Это и есть язык Си. Стандарт существует только в сферическом виде в вакууме, любой компилятор несколько отличается от него.
Мы сейчас с вами общаемся на русском языке, тоже отличающемся от стандартов. Тем не менее, именно это и есть настоящий живой язык.
Если компилятор (старый или новый) не компилирует мой код (соответствующий или не соответствующий стандарту) не так, как я ожидал, то мне будет абсолютно по барабану, какой там будет резолюшн.
Мне приходилось находить случаи, когда компилятор неправильно компилировал вполне соответствующий стандарту код. И что из этого? Да ничего, в программе появляется #ifdef или просто обходной путь.
Немного вещей менее осмысленны для прикладного программиста, чем открытие багрепорта компилятору.
Мне-то какая польза от того, что починят? Я ж не знаю, какой версией компилятора жизнь заставит людей компилить мой код. Может, у них окажется старая.
Это как-то работает только если со своего рабочего места распространять лишь бинарники. Но чаще у программистов в трудовых обязанностях - создание исходного кода.
Вообще, я хочу заметить, что C/C++ комьюнити довольно уникально в смысле отношения к стандартам языка. Комитет по стандартизации выковыривает у себя из носа разные новые фичи, включает в стандарты, а народ потом на эти стандарты... э... возбуждается и носится с ними, как со священными текстами. Ни в одном другом языке я не припомню такой практики, когда первичен был бы стандарт, а вторичен компилятор. В лингвистике это называется прескриптивным подходом.
Обычно путь обратный, хотя проходится по-разному.
В других языках (rust, c#, go, ...) — компилятор часто ровно один. Поэтому он главнее стандарта. А когда компиляторов десяток, какой из них "правильнее" — холиварный вопрос.
В Фортране, например, компиляторов много, но ни один из них не реализует действующий стандарт, а стандарт, в свою очередь, потихоньку впитывает некоторые полезные фичи из компиляторов (при этом гипотетический компилятор, написанный по стандарту, не смог бы откомпилировать подавляющее большинство фактически использующихся программ). В Паскале и PL/I всем разработчикам компиляторов всю жизнь вообще было пофиг, что написано в стандарте, комитет ISO жил своей параллельной жизнью. В Лиспе стандартизировали в глубоком прошлом поведение одной реализации и договорились никогда его не менять (ну это язык специфический, там при развитии синтаксис менять не нужно).
В Фортране, например, компиляторов много, но ни один из них не реализует действующий стандарт, а стандарт, в свою очередь, потихоньку впитывает некоторые полезные фичи из компиляторов.
Это ровно как в C++ ))
В Паскале и PL/I
Случай, когда 1 платформа — 1 компилятор. Миграции на другой компилятор быть не может.
Ну нет, там и на разных платформах, и на одинаковых были разные компиляторы. Просто в разной степени популярные, но это и для Си точно так же.
Я думаю, на тех платформах, где ситуация с си-компиляторами такая же, как с другими языками, там поклоняются не Стандарту, а документации на Компилятор. Но тут-то публика больше с развитых платформ, где независимых компиляторов как минимум три.
Например? В основном используется в Unix-совместимых системах gcc и совместимый с ним llvm, а в Windows - msvc. Я тут вижу по одному независимому компилятору на платформу.
На Windows (особенно в open-source) можно нередко увидеть проекты, заточенные под MinGW, а на обоих платформах также есть clang (построенный поверх llvm).
gcc и совместимый с ним llvm
Это непримиримые конкуренты, с разной историей, разной кодовой базой, разными языковыми расширениями. Поэтому clang (как и msvc) никогда не скомпилирует ядро linux, там слишком много завязано на compiler-specific.
Когда я говорю о применении llvm к языку Си, то, естественно, имею в виду clang. Clang – это фронтенд C/C++ к универсальному компилятору llvm.
Это непримиримые конкуренты, с разной историей и кодовой базой.
Может, они и конкуренты, но clang написан так, чтобы максимально соответствовать реализации C/C++ в gcc. Именно в gcc, а не в стандарте языка.
То же самое minigw – это порт gcc в Windows, основанный на реализации gcc. Он существует именно потому, что опенсоурсные программы обычно написаны на входном языке gcc, а не на сферическом стандартном C/C++.
Независимых компилятора в данном случае два – gcc и msvc.
Дальше среди независимых компиляторов для PC идёт, наверное, Intel C, ну и сами прикиньте, насколько он популярен.
Как минимум, у разработчиков совсем разный подход к UB.
Если gcc старается выдать что-то разумное, угадать что имел ввиду программист, то clang наоборот, увидев UB, старается максимально жёстко дать по рукам: если цикл с переполнением int, сделаем его бесконечным. Если callback не инициализирован, но вызывается, сделаем вызов любой функции, подходящей под сигнатуру.
Про переполнение int – это городская легенда, связанная с багом в какой-то версии llvm.
А что касается случая с вызовом функции, то это просто следствие более глубокой оптимизации в llvm. Компилятор рассуждает так: если по тексту программы переменной присваивается одно-единственное валидное значение, то давайте просто его запишем в статическую секцию и уберём лишний оператор присваивания.
Вот она, легенда...
Так даже интереснее:
Не видел этот пример. Очевидно, что это просто ошибка в gcc. Как видите, clang её компилирует в пустое тело.
Здесь, видимо, уважаемый @0xd34df00d посоветовал бы отрепортить баг в gcc и приостановить работу над программой (до получения NOTABUG, так как он сочтёт это ub).
Очевидно, что это просто ошибка в gcc
Это не ошибка. Заменить int на unsigned, и получите результат, идентичный MSVC. Просто авторы компиляторов захотели "дать по рукам".
Вы совершенно неправильно себе представляете побудительные мотивы разработчиков компиляторов. “Дать по рукам” совершенно точно к ним не относится.
А замена int на unsigned ничего в смысле семантики языка не меняет в данном примере. Просто баг в компиляторе перестаёт проявляться.
Во многом, впрочем, все эти примеры иллюстрируют скорее проблемы плохо построенных синтетических тестов, чем самого компилятора.
А замена int на unsigned ничего в смысле семантики языка не меняет в данном примере. Просто баг в компиляторе перестаёт проявляться
Насколько я помню, это всё много лет назад обсуждалось, и было закрыто разработчиками компилятора с резолюцией NOTABUG, потому что UB.
Ну вот народ и свалил на clang с таким отношением :)
Если более серьёзно, то gcc – уже очень старый компилятор, в котором перемешаны между собой разные уровни оптимизации для огромного количества платформ, и его уже очень трудно сопровождать. Неудивительно, что авторы дали отмазку вместо того, чтобы очень много париться ради не имеющего практического применения синтетического теста.
Во многом, впрочем, все эти примеры иллюстрируют скорее проблемы плохо построенных синтетических тестов, чем самого компилятора
В старом сишном мире частенько работали с переполнением int как с модулярной арифметикой, подразумевая, что семантика переполнения такая же, как на процессоре.
Вот это надёжно работало, независимо от любых переполнений:
int tick1 = GetTickCount();
RunFunc();
int tick2 = GetTickCount();
if (tick2 - tick1 > 50) { // прошло более 50мс }На этом можно было строить циклы. И вдруг, с каким-то релизом clang, эти циклы превратились в тыкву, потому что нефиг использовать int там, где требуется unsigned
Из-за этого (получив большую фобию к типу int как потенциальному UB-генератору) я себя не очень комфортно чувствую в C#, потому что там все индексные типы (которые в C++ size_t) — знаковые (например, результат string.IndexOf). И официальный гайд по проектированию API от MS рекомендует использовать int в случаях, где в C++ уместен size_t.
Просто FYI: баг открывать не надо, если поставить gcc опцию -fwrapv то результат будет соответствовать clang.
clang (как и msvc) никогда не скомпилирует ядро linux
Clang уже 2 года как на это способен.
Не, это ни на что не повлияет. Там нет какого-то непонимания, что такое ub, и прочего. Т. е. это не ошибочное мнение, а просто попытки как-то оправдать свой положение. Эксперты сидят с 4-5 Gib/s, да и даже это они также спастили, а не написали сами. И тут вдруг кто-то показывает нормальный перф - далее всё просто: либо все понимают, что за гуру оптимизации здесь обитают, либо эксперты придумывают тысячи оправданий своей некомпетентности.
А поскольку стандарт - максимально абстрактная байда, легче всего рулить именно туда, ведь никак это проверить нельзя. Там вон выше(или ниже) дошли до размера страницы памяти < 128 байт, а вот где-то там(квак) что-то поломалось спустя долгое время, ну и конечно же, агитка про "отформатировать диск"(это совсем позор, ведь никакого форматирования не было зафиксировано ни разу).
это совсем позор, ведь никакого форматирования не было зафиксировано ни разу
Синтетический пример наделал много шуму, и теперь все его вспоминают со словами "а ещё ваш UB форматирует диски".
http://kristerw.blogspot.com/2017/09/why-undefined-behavior-may-call-never.html
Честно говоря, не понимаю удивления этих людей. Чего конкретно они ожидали, передавая управление по неизвестно чем заполненному адресу? Даже если, допустим, они рассчитывали получить jmp 0, то почему бы по адресу 0 не находиться как раз коду EraseAll? (Хотя механизм в данном случае другой, но тем не менее).
В целом работает (более того я бы наверное "с ходу" написал бы с +/- такими же константами);
Но всё-таки с одним уточнением: step_size 128 - многовато.
На архитектурах, где malloc выравнивает пользовательский адрес по 8 байт (64 бита) - теоретически можно словить выход за пределы brk() и чтение из PROT_READ страницы.
ПС
Другие примеры - вроде бы тоже привели в комментариях.
Взял произвольную строку в 23800 байт и компилятор pocc.exe OC Windows
Получил скорость для первого кода 1160 MiB/s, в статье 295 MiB/s
а для кода с таблицей 2.0 GiB/s, в статье GCC: 1.98 GiB/s
Смотрю минуса уже начинают подъезжать. Видимо группа поддержки набигает. Поэтому отмечу ещё один момент и пойду. В чём суть "аргументации" твиттер- и прочих экспертов, - UB. Но что характерно, именно то ub, которое имеет последствия и искажает результат работы функции эксперты не нашли. Это переполнение при step_size = 128, которое я не убрал. Я сообщал здесь об этом ранее.
А вот "false-positive UB" они нашли. Ну как нашли - путили санитайзер и оно им нашло. Сами они не нашли бы даже этого. Я ожидал подобных заходов почти мгновенно, но почему-то их не последовало, я даже удивился немного. Только спустя полдня адепт известно какого ЯП что-то там нагуглил. Удивительные эксперты.
Ладно, резюмируя(для неофитов в первую очередь, но не только для них) - код дан, любой может взять и проверить - это одна из фишек программирования по сравнению с большинством остального - всё довольно просто проверяется. Берём мой код - перф на уровне, берём код из glibc - перф на уровне, берём код экспертных экспертов - ой, сливает раз в несколько раз. Рассказывали про падения - не нашли, начали рассказывать про ub - оказалось это "ложное" ub и ни на что оно не влияет. Далее совсем поломались и начали просто заспамливать меня как боты "это ub", "это ub", "это ub" - надо же как-то оправдаться в глазах общественности. Ну так бывает, когда ты эксперт из твиттера/адепт некого ЯП/ещё какой-то 25 эшелон.
Если вы любите прыгать в стог сена с вилами в нём и ни разу не напоролись на них -- не повод рассказывать что опасность вил забытых в сене преувеличена.
Похоже вы решили со мной поиграть в эксперта. Хорошо. Падение из-за того UB, о котором говорили из твиттера и здесь - в студию. Обоснование за попытки манипулировать, предоставив падение, которое к делу не относится - так же в студию.
Такой код падает:
исходник
#include <stdlib.h>
#include <stdio.h>
#define step_size 128
#define auto __auto_type
#define proc(v) ({ auto _v = (v); (_v == 's') - (_v == 'p'); })
#define aligned(ptr, align) ({ \
auto _ptr = (ptr); \
auto _align = (align); \
auto _r = (long long)_ptr & _align - 1; \
_r ? _ptr + (_align - _r) : _ptr; \
})
int run_switches(const unsigned char* i) {
auto r = 0;
for (auto head_end = aligned(i, step_size); i != head_end && *i; ++i) r += proc(*i);
while (1) {
signed char step_r = 0;
unsigned char rs[step_size];
for (auto n = 0; n != sizeof(rs); ++n) {
rs[n] = i[n] ? 0 : ~0;
step_r += proc(i[n]);
}
long long* _ = rs;
if (_[0] | _[1] | _[2] | _[3] | _[4] | _[5] | _[6] | _[7] | _[8] | _[9] | _[10] | _[11] | _[12] | _[13] | _[14] | _[15]) {
while (*i) r += proc(*i++);
break;
}
r += step_r;
i += sizeof(rs);
}
return r;
}
int main(int argc, char **argv) {
if (argc < 2) {
printf("Usage: %s <iterations>\n", argv[0]);
return 1;
}
const int n = atoi(argv[1]);
char *commands = "ssssss";
int res = 0;
for (int i = 0; i < n; i++) {
res += run_switches(commands);
}
printf("%s: %d\n", commands, res);
commands[3]='\0';
res = 0;
for (int i = 0; i < n; i++) {
res += run_switches(commands);
}
printf("%s: %d\n", commands, res);
return 0;
}
Cборка и запуск:
[dixaba@srv ~]$ gcc -std=gnu2x -Ofast -march=native -fwhole-program -obench bench.c
bench.c: In function ‘run_switches’:
bench.c:24:20: warning: initialization of ‘long long int *’ from incompatible pointer type ‘unsigned char *’ [-Wincompatible-pointer-types]
24 | long long* _ = rs;
| ^~
[dixaba@srv ~]$ ./bench 1
ssssss: 6
Segmentation fault (core dumped)Для начала нужно почитать тему, а уже потом бежать срывать покровы. Где if, про который я говорил? К тому же он очевиден, если пытаться читать код, а не просто пустить, получить левое падение, ничего не понять и бежать рассказывать истории.
Для начала нужно вспомнить, что безопасно кастовать указатели можно только между чемто*, void* и char*, а кастование между чемто* и чемтодругим* (как у вас - long long int* и unsigned char*) - UB. Заметьте, gcc ругнулся даже без включения дополнительных проверок.
Кстати, вы уверены, что ваш long long int и мой long long int будут одного и того же размера? Стандарты C очень интересны, они определяют только нижний размер типов.
Новые откровения подъехали. А чего проигнорировали всё и свичнулись на новую тему? Рассказывали про падает, а оказалось не падает. Чего так?
Что-то эксперт так уверенно рассказывал и так быстро куда-то пропал. Ну это типично.
Просто для протокола:
безопасно кастовать указатели можно только между чемто*, void* и char*
а кастование между чемто* и чемтодругим* (как у вас - long long int* и unsigned char*) - UB
Даже здесь засыпался, даже в области стандарта(который эксерт не читал и знает о нём из историй в интернете). Сообщу новость - signed/unsigned варианты одного и того же базового типа алиастся без ub.
Здравствуйте, примите глубочайшие сожаления в связи с невозможностью написания ответа в течение 1 (одной) минуты после того как Вы написали свой.
signed/unsigned варианты одного и того же базового типа алиастся без ub.
Хочу напомнить, что char'ов в стандарте есть аж три, и безопасно кастить только в обычный char, без указания знаковости. То есть если бы у вас был char rs[step_size]; - было бы стандарто-допустимо.
Для начала нужно вспомнить, что безопасно кастовать указатели можно только между чемто, void и char, а кастование между чемто и чемтодругим (как у вас — long long int и unsigned char*) — UB
Вы чего-то недоговариваете, потому что в такой формулировке из стандарта надо убрать reinterpret_cast
Не припомню чтоб в C был reinterpret_cast , это же C++ное. Но и в C++ нельзя разыменовывать указатели после reinterpret_cast (кроме очень отдельных случаев).
Если вы хотите сделать не-UB-шно, то в C надо использовать union, а в C++ - std::bit_cast
std::bit_cast
Ох, с этими новыми стандартами опять старый код переписывать ))
Ну кстати, если MyStruct* нельзя в AnotherStruct* но можно в char* и обратно, то выходит так можно?
MyStruct* myStruct = (MyStruct*)(char*)otherStruct;
Выглядит, как заставить программиста писать лишний код на ровном месте...
Нельзя. С точки зрения стандарта по адресу лежит какой-то обьект, не так важно через какие касты указателей в к нему добираетесь важно чтобы читался тот же обьект что и был записан изначально. Есть исключения для signed в unsigned, based в derived и испектирование репрезентации через std::byte. На самом деле по стандарту даже malloc либо до недавнего времени, либо до сих пор использовать нельзя. Поэтому полезность такого стандарта близка к нулю.
Как раз unsigned char на ровне с std::byte может быть использован для доступа к репрезентации обьекта.
Я минусую твои посты с надменным тоном. Вообще не в курсе кто тут "эксперт", но читать тебя противно.
Справедливости ради, dllmain триггернулся после комментария с совершенно хамским и не менее надменным скриншотом из твиттера: https://habr.com/en/companies/ruvds/articles/747826/comments/#comment_25755608
Точно такое же UB есть в Qt в qustrlen, и оно там просто подавлено для asan через __attribute__((__no_sanitize_address__)).
Не "просто подавлено". Эта оптимизация включена (и подавлена) только для __SSE2__ и используют гарантированно пакетные выровненные загрузки через _mm_load_si128 и добавлены комментарии почему это безопасно :)
Все верно, но проблема слегка ортогональна sse, при загрузке int64 или int32 принципиально все то же самое - главное на другую страницу не обратиться, затем и выравнивание. То есть это для целого набора архитектур безопасно, не безопасные еще поискать надо.
Выравнивание требуется по разным причинам. x86 в целом довольно вольно к выравниванию относится -- ну упадёт производительность "немного" если читать не выровненное, но и только. Но прямо сейчас в миру тонны процессоров которые невыровненные читать откажутся с SIGBUS'ом даже внутри страницы.
В данном же случае они полагаются на всё сразу -- выравнивание и для инструкции (_mm_load_si128 грузит только выровненные адреса) и для производительности. (кстати, совсем не факт что интрисинк сгенерит обязательно выровненную инструкцию -- см например https://stackoverflow.com/questions/73912363/mm-load-si128-is-not-throwing-on-unaligned-access) и дополнительно приведен комментарий объясняющий (как тот математик) безопасность этого действия.
Я сварщик не настоящий, но ради интереса решил на расте попробовать
pub fn run_switches(input: &str) -> i64 {
let chunked_bytes = input.as_bytes().chunks_exact(64);
let rest = chunked_bytes.remainder();
let mut result = chunked_bytes
.map(|chunk| chunk.iter().map(sp_to_int).sum::<i8>() as i64)
.sum::<i64>();
result += rest.iter().map(sp_to_int).sum::<i8>() as i64;
return result;
}
fn sp_to_int(b: &u8) -> i8 {
match b {
b's' => 1,
b'p' => -1,
_ => 0,
}
}У меня выдаёт около 22 GiB/s. Но если суммировать чанки во что-то больше i8 и увеличить размер чанков, то производительность падает на порядок. Может знающие люди подскажут, с чем это связано и как можно оптимизировать.
https://godbolt.org/z/je76jG1aW, там 8 и 16
Фишка в том, что
а) c i8 оно грузит регистры из памяти чохом по 4*128 бит (размер кэш-линии), а с i16 – вразброс, и по 64 бита
б) с i8 оно счётчики по каждой позиции ведёт прямо внутри xmm в тех же позициях, где были символы (они же тоже по 8 бит), а потом результат по 16 символам суммирует одной инструкцией psadbw. Сравните с крошевом с i16.
Заметим, что код делает почти то же самое, что Сишный от dllamin-а – читает за границами – и ничего.
Заметим, что код делает почти то же самое, что Сишный от dllmain-а – читает за границами – и ничего.
Нет, rust безопасный язык и не может себе позволить ничего такого.
Заметьте, там строка разбивается на часть, кратную 64, и остаток. Обе части обрабатываются отдельно.
Заметьте, там строка разбивается на часть, кратную 64, и остаток
Остаток, кратный восьми.
Не соображу, где это написано
result += rest.iter().map(sp_to_int).sum::<i8>() as i64;Замечу, кстати, что код ваш считает после \0, если скормить "ppss\0ppp", будет -3.
Этот код решает совершенно другую, гораздо более простую, задачу. Он работает с растовским типом str, в котором длина строки содержится в отдельном счётчике. А серьёзные проблемы сишного кода с производительностью связаны с поиском завершающего нуля в сишной строке.
Конечно, можно справедливо сказать, что в реальной жизни никто не заставляет выбирать нуль-терминированную структуру данных. Но тем не менее, такой подход несколько лишает смысла сам предмет обсуждения.
Даже если считать длину строки отдельно, скорость упадёт не более, чем в 2 раза. Это покрывается преимуществами этой реализации. Там выше был код от thevlad на чистом C, который сначала считал strlen, потом векторизовывался, и был быстрее любого (из представленных здесь) однопроходного подхода (понятно, что в общем случае можно сделать и однопроходный, и векторизованный).
strlen сам векторизован внутри себя.
Наиболее дискутируемая здесь проблема состоит именно в том, как обходиться с невыровненными строками.
strlen сам векторизован внутри себя
Как-то он внутри себя решает эту проблему ))
Вероятно, итог дискуссии в том, что векторизованный strlen, написанный на асме, невозможно переписать на C, обязательно наткнёмся на UB. Даже если архитектура позволяет читать внутри страницы за пределами терминатора строки, компилятор может подложить свинью из-за UB.
Он точно так же решает эту проблему, как dllmain, просто авторы stdlib проще относятся к ub, чем некоторые подписчики Хабра.
В большинстве случаев код очень жёстко завязан на компилятор.
Вы издеваетесь? Случай, когда люди хотя бы даже просто тестируют свой код с несколькими компиляторами - редкое исключение. Обеспечивать кросс-компиляторную совместимость - очень большая работа, и мало кому нужная. Если говорить про Си, то 99% кода не подразумевает компиляции за пределами штатного компилятора своей изначальной платформы.
Хотя б даже кодировка исходных файлов - где-то UTF-8, а где-то UCS-2. Ну и дальше разный объём реализации возможностей языка, разные нюансы стандартной библиотеки, разные ошибки компиляторов и т.д.
Например, я, когда пишу под винду, использую MSVC, и не стесняюсь пользоваться его __declspec-ами и #pragma-ми вне стандарта. Я мог бы, конечно, каждое такое использование заворачивать в #ifdef, но считаю это бессмысленной тратой времени, потому что этот компилятор меня полностью устраивает и переходить с него куда-то не вижу смысла.
Ну так
В большинстве случаев код очень жёстко завязан на компилятор.
Это как раз про специфицированные штуки. А если при этом UB-код почему-то работает корректно, то и переписывать его не будут.
Обычно в больших проектах компилятор не обновляют без крайней нужды. Поэтому в целом пофиг, что там через пару релизов - вряд ли эти новые релизы когда то соприкоснутся с кодом проекта
Новые версии стандартов — это крайняя нужда или нет?
Нет конечно. Крайняя нужда диктуется требованиями бизнеса - например возникает требование поддержки платформы под которую использовавшегося до этого момента компилятора нет. Или интеграция чужого продукта/библиотеки который не поддерживает старый компилятор.
Бизнес обычно вообще не интересует, какая там версия стандарта.
Почему обязательно неспецифицированное? У приличных людей в документации на компилятор есть раздел Implementation-defined behavior.
Например, IBM в документации на компилятор C пишет, что операция [] полностью эквивалентна сложению, а сложение указателя допустимо в любом случае, когда результат даёт валидный адрес. А что такое валидный адрес, можно прочитать в “Принципах работы”. Ни одного указания на то, что индекс массива обязан иметь значение в пределах массива, IBM не даёт – да оно и понятно, учитывая что у них во многих системных интерфейсах используется трюк с выходом за границу массива неизвестной заранее длины.
Единственное, что запрещает IBM – конструировать указатель битовыми операциями (так как некоторые его биты могут быть частью системных масок).
Даже сравнение на равенство?
По-моему, это вы путаете кванторы существования и всеобщности, когда пишете про “совершенно неспецифицированное UB”.
Компилятор IBM я привёл просто потому, что люблю пользоваться IBMовскими описаниями языков, так как они очень подробные и, в частности, обычно подробнее и конкретнее стандартов.
С. 157: By definition, the expression a[b] is equivalent to the expression *((a) + (b)), and, because addition is associative, it is also equivalent to b[a].
С. 143: Do not apply the indirection operator to any pointer that contains an address that is not valid, such as NULL. The result is not defined.
С. 92: Any bitwise manipulation of a pointer can result in undefined behavior.
Это как искать не там, где потерял, а под фонарём, потому что удобнее.
С чего бы компилятору, которым вы пользуетесь, следовать документации IBM, а не Стандарту?
А что запрещает? Это валидное выражение, только его значение непредсказуемо, потому что мы не знаем, что находился после a.
Мы вроде про Си.
Стандарт C++ запрещает формировать указатели
Это максимально логично. Вдруг на какой-то архитектуре адресные регистры отличаются от регистров данных и невалидный адрес в них, или переполнение при формировании адреса, автоматически приведёт к генерации исключения.
А вдруг на какой-то архитектуре вообще нельзя формировать указатели? В отличие от вашего предположения, такая архитектура существует и достаточно широко используется, это IBM i (AS/400). Память для программ на C/C++ там, как я понимаю, просто эмулируется с точки зрения аппаратуры одним массивом.
Язык Си уже в своей основе содержит не универсально переносимую концепцию адресной арифметики.
Ничего себе. А где об этом можно почитать? Так выходит, на такой архитектуре невозможен классический компилятор, потому что ему нужно сформировать бинарный файл, некоторые байты которого при выполнении станут указателями.
Есть прекрасная увлекательно написанная книга Солтиса “Основы AS/400”, очень рекомендую для общего развития, даже не имея практического интереса к этой платформе. Ну и просто по “AS/400” можно поискать.
Компилятор (и вообще любую программу, генерирующую исполняемый код) написать невозможно силами пользователя. Собственно, это так в любой ОС, реализующей уровень безопасности защищённой программной среды. Тут просто ключ к программной среде находится только у IBM и вообще вынесен из пользовательского API в микрокод. При этом писать пользовательские программы на входных языках входящих в состав ОС компиляторов можно (в классической ЗПС на базе какого-нибудь Linux можно писать интерпретируемые скрипты на каком-нибудь питоне, разница тут не имеет принципиального характера).
Нашёл материалы по этой штуке. Получается, там виртуальная машина, а пользовательская программа — это p-код для неё, к native-коду доступа у пользователя нет.
Но не понимаю ваше возражение. Массивы-то в этой вирт. машине есть. То есть, любой указатель можно представить как пару (объект-массив, индекс). И адресная арифметика прекрасно делается через арифметику над индексной частью, а действия с указателями из разных массивов — UB. Туда же "странные" запреты кастить указатели разных типов друг в друга, вирт. машина не поймёт, если нижележащие под указателями массивы разного типа. То есть, Стандарт как будто писался под такую архитекуру и идеально к ней подходит.
А всё-таки, полноценный C тут невозможен.
Не можем получить указатель на функцию, не можем сохранить указатель в integral тип достаточной длины и восстановить его обратно.
Нижележащая виртуальная машина не имеет таких инструкций.
https://www.ibm.com/docs/en/ssw_ibm_i_73/rbam6/rbam6pdf.pdf
Как если бы мы компилировали в аппаратную lisp-машину, в которой нет способа кастануть целое число в лямбду, которую можно выполнить.
Я как-то фантазировал, если бы писал лисп-машину, и лисп-ос, как бы я построил безопасность.
И решение мне виделось таким, что приложение получает список функций API. Если на месте какой-то функции стоит nil, то и доступа к функции нет. С другой стороны, родительское приложение (отладчик) может поставить фильтр на любую функцию, и передать блок API в дочернее приложение. Тем самым, разрешить приложению доступ только к некоторым файлам, или виртуализировать доступ к системным часам.
В вышеупомянутой книге Солтиса, которую я пролистал по диагонали, как раз упоминается сходное решение: нет указателя на объект — нет доступа. Если бы указатели кастились из int-ов, можно было бы брутфорсить.
Хм, то есть, не запускать программы, опасность которых доказана? Но это же неразрешимая в общем случае задача, особенно если программа кастит int-ы в указатели на функции ))
Заворачивание в монады – дело полезное, но само по себе не даст пентагоновский класс B, как у AS/400. Тут работа программиста – небольшая часть усилий. Тем более, что именно программист в может быть угрозой безопасности.
Фундаментально это реализация защиты информации. Невозможно адресоваться к посторонней памяти, так как невозможно получить указатель на неё.
Чтобы как раз-таки не страницами авторизовать доступ, а на уровне отдельных объектов.
Память тегирована, любой элемент данных аппаратно имеет тип. Элемент типа указатель может быть создан только ядром операционной системы. Программа может только его передать дальше в неизменном виде или разыменовать.
Возражение заключается в том, что наэмулировать (как вы предлагаете пару массив-индекс) мы в принципе можем любую концепцию на любой вычислительно полной архитектуре. Но тогда не надо особенностями машинной архитектуры аргументировать возможности языка, потому что он реализуется не на машинной архитектуре, а на эмуляторе.
А если предметно, то у вас всё сломается на void*.
Пары указатель-смещение известны в "защищённых" архитектурах (тот же Эльбрус). Каст в void* сам по себе ничего не ломает, получаем под капотом такую же пару (объект/смещение), как у оригинала. Обратный каст пройдёт без проблем.
А вот каст void* в size_t уже проблема. А без него не сделаешь хеш-таблицу, например.
Обновлять - не значит не быть на него завязанным.
Тот же strict-aliasing он не пришёл внезапно, поэтому не вижу большой проблемы следить за такого рода breaking change в компиляторах. Тем более что strlen так просто не пропадёт, и он должен остаться производительный, а значит и этот подход будет работать.
Тем не менее пример на Расте тоже хорош – с таким вот на первый взгляд странным поведением при замене i8 на i16 пока не столкнёшься, не предугадаешь.
Я вот когда асм читал, прямо удивлён был. То-есть образовательный момент у этого примера, да вообще у всего треда с dllmain, изумительный. Может, только для меня.
Название про ускорение С, а на самом деле возня с ассемблером.
В {n} раз быстрее Си