Не могу полностью согласиться что никакого секрета. Есть дилетантское мнение (возможно неправильное но пока не опровергнутое) что если из известной "ОС" убрать виртуальную машину то она перестанет кушать аккумуляторы в конских количествах и станет пошустрее. Т.е. рынок уже протоптан, на нем доминирует некачественный продукт, который даже понятно как улучшить. Но... мегакорпорация, попытавшаяся откусить кусок, сбежала. Конкурент - да, Петя имеется. С предпринимательской чуйкой, качественным продуктом и т.п. Только лидером на собственном рынке он не является. Остальные померли, несмотря на множество лояльных клиентов. Весьма ресурсные конторы вместо попыток подмять под себя рынок платят линенцзионные платежи за даунгрейд своего железа, или делают форк того-же но в профиль. И это в общем нормальный ход дел именно для софта. Возможно действительно дело в том что все заливают железом, но производители железа получается платят два раза (за код который его тормозит и за разработку чтобы все таки не слишком тормозило) и довольны.
Два автозавода одновременно начали делать один и тот-же продукт. Один начал выпускать дешманские тарантайки через месяц, другой - хорошие машины через два года. Вторая модель видимо выгоднее при наличии ресурсов, по крайней мере автозаводы обычно строят без подсобных хозяйств по ручному выпуску бюджетных малолитражек до старта основного конвейера.
Две фабрики начали выпускать микроволновки. Одна выпустила глючное воняющее пластиком поделие через месяц, другая через год качественный продукт. Те же соображения.
Вася пустил постояльцев жить в курятнике и к концу сезона был с прибылью, Петя построил микроотель с кондишками к следующему. Если он этот год переживет - в следующем все будет неплохо.
Почему-то везде есть граница качества, ниже которой продукт не нужен, и везде есть кореляция качество-деньги. И только в софте это не работает. Ну или не везде работает, все же в играх есть какая-то связь между ценой и качеством, и в некоторых других сегментах тоже.
Проблема же не в том что Петя выпустил свой продукт позже, и даже не в том что Вася нанял двух прогеров (ему кстати повезло что их через пять месяцев осталось двое а не восемь и они даже что-то там доделали нужное а не переписали всё на свежем фреймворке. У Пети этот риск намного меньше просто в силу его подхода). И далеко не факт что у Пети нет ресурсов на раскрутку. Скорее в том что именно ресурсы на раскрутку и решат какая поделка выживет, а их качество не решает примерно ничего и потому может быть соптимизировано. При "низком" старте Вася просто поделил свои ресурсы на два направления а Петя направил на одно.
кстати да, тоже было такое, хотя и не так проявлялось (в плане что встроенный массив не панацея). Но здесь Вы работаете с абстракцией как с другой абстракцией (чуть ниже как с памятью и это уже прокатывает, хотя тоже смешивание) - дело сознательное. В начальном примере и этого нет, а константы размера/цикла могут быть обфусцированы, преднамеренно или нет.
"All natural laws end here". Мне кажется, к UB она подходит замечательно)
Если в плане что здесь природные законы заканчиваются и начинаются человеческие со всеми их особенностями - то полностью согласен. Список UB это что-то вроде перечня триггеров, включающих фантазии компилятора на тему оптимизации, которые правильно работают только на определенном подмножестве случаев, причем точно его границы компилятор сам определить не может. Если романтичное undefined behaviour заменить на прозаичное known issues - мысленный путь до workaround становится значительно короче.
справедливости ради, в вашем же блоге была статья, в которой std::array не только не ловит выход за массив, а генерит код с безусловно бесконечным циклом, который вываливает все содержимое стека (подозреваю что из-за constexpr const_reference operator[], что дает компилятору повод пооптимизировать обращения к несуществующим элементам). В комментах победило мнение что это не баг а фича, пути UB непостижимы. Но как-то таких фич не хочется.
while (key != s->key && (s = s->next));
if (!s) return -1;
хотя что именно возвращает функция неважно для иллюстрации, но так что-то более осмысленное. Туманная ремарка про потерю и возврат CPU, потому что это про RCU, и мы под грейс-периодом, который в случае разных процессов а не тредов злое ядро может неограниченно продлить.
Похоже фразой про нюансы я случайно задел чьи то чувства. Может все таки поясните свою позицию? Какое из следующих утверждений является неверным?
макроассемблер ЯВУ Си не имеет встроенных средств отличия "распределенной" памяти от "нераспределенной".
Он полагается в различении этих категорий в масштабах страниц на железо и ОС
В масштабах байт статус "распределенности" не играет никакой роли, важно "назначение". Использование памяти "не по назначению" приведет к UB, даже если она перед этим была "распределена" маллоком, на стеке или еще как-то. За "назначение" отвечают компилятор, линковщик, загрузчик процесса, процессор - за свои конечные подмножества случаев, программист - за все остальное.
Если ОС говорит, что страница данного адреса была выделена процессу, и адрес либо назначен в конечные подмножества пункта 3, но его использование не противоречит определенным правилам, установленным языком (вызов функции, разыменование переменной, чтение данных), либо не назначен в них и правила использования памяти, произвольно установленные программистом, не противоречат сами себе и правилам выше, то с точки зрения языка адрес "распределен", даже если явно никогда не выделялся. При этом способы, которыми ОС и программист выполняют свою часть работы, никак языком не регулируются, кроме нескольких частных случаев, об одном из которых дискуссия выше.
Из пунктов 2-4 следует что чтение данных по произвольному адресу не является UB пока ОС и железо не против, чего можно добиться способами, к языку не относящимися.
Не претендую на истину в последней инстанции, но хотелось бы серьезных возражений.
C точки зрения компилятора вообще нет причин беспокоиться. Упрощенно как-то так выглядит:
typedef struct someStructTg {
struct someStructTg *next;
int key;
int value;
} someStruct;
extern jmp_buf recover;
int get_data(volatile someStruct *s, int key)
{
if (!s) return -1;
int wcnt = get_writes_counter();
volatile someStruct *p;
// Тут где-то cpu мы потеряли, кто-то поломал цепочку, cpu нам вернули.
// Блокировку от этого события мы сознательно пропустили
if (setjmp(recover))
return -1; // Сегфолтнулись ниже
while (key != s->key && (p = s->next))
s = p;
int rv = s->value;
// Тут барьер чтобы rv не выпилили но допустим он в get_writes_counter
if (get_writes_counter() != wcnt)
return -1; //проверяет что никто ничего не писал пока читали
return rv;
}
трейс-кеш это что-то ужасно старое. заменили на микроопс кеш и он делится ровно пополам на интеле, что описано в статье про уязвимость (https://ieeexplore.ieee.org/document/9499837). Мне кажется, проблема smt в том что его серьезно никто за 20 лет не стал воспринимать. ("Мы запустили программу name и она быстрее/медленнее на x% с включенным/выключенным SMT"). Это как эффективность SSE оценивать по фпс в doom. Кооперативные потоки это отлично (например про умножение матриц я специально выяснял), но как гарантировать их кооперативность я не нашел. Как заставить компилятор конкретные функции оптимизировать под порезанное ядро тоже не нашел (да и всю прогу целиком). Не исключаю что плохо искал, но как минимум хорошо спрятано. При этом всякие бигдаты с рандомным доступом на вид должны разгоняться очень хорошо (пример кстати хороший)
Теоретически это UB. Практически для ситуации описанной выше (там не код а данные, которые мы не пишем а читаем), не такое уж оно и undefined.
Мы можем прочитать мусор, позже это опознаем и выкинем.
Мы можем зациклиться если это "преследование указателя". Вариант теоретический, но надо иногда проверять а не читаем ли мы мусор до того как указатель догоним.
Мы можем упасть в сегфолт. Самое неприятное. Можно проверить, действительно ли эту память выделяли. Дорого, ситуация редкая а проверять придется постоянно. Можем перехватить сегфолт, проверить а не в определенной ли точке кода он случился, и если там то longjmp на выход, а если нет то валимся дальше. Ну или в свежем линуксе сделать тоже самое более цивилизованным способом (я кстати все не соберусь попробовать).
Британскую королеву код славить точно не начнет. В результате получается усточивость к манипуляциям ядра с процессом и реализуемость некоторых локфри алгоритмов в юзерспейс. Обычно такой трюк для подкачки используется и возможные адреса обращений там все таки резервируются, тут извращенное применение но работает.
За что минус то. Два треда. Один начал что-то читать но подвис. Второй тем временем все переписал. Первый очнулся, прочитал до конца, в том числе ссылку, которая уже не ссылка. Если хочется локфри - а его хочется, то можно или как-то руками проверить - а ссылка ли это, или перехватить сигсегв или вот эту штуку использовать. Вполне себе такой штатный сигсегв получается.
Я до сегодня думал, что типы кастуются слева направо
та же беда.
На хабре же была отличная статья с тестами про чтение за границами массива
Статью прочитал но прямой связи не увидел. Если я объявил что-то как char [16 (константа)] и потом полез к 17му байту (константа) то да, разворот цикла поломается. Наверное. По крайней мере приводится случай когда он поломался. Если я объявил что-то как char *, присвоил этому адрес из середины другого куска (важно что не выделял) и начал прыгать по нему как по массиву (так более читаемо, и выше много примеров что так думаю не я один) - то, возможно, компилятор который на этом сломается я не встречу пока сам не напишу, т.к. массовым ему не стать.
Первая часть не понятна. a[b] это *(a+b), не *(b+a). Что тут void*, что int и почему они должны местами поменяться? Вобще похоже приводится к void* оба, но это странно:
void *a = malloc(20);
int b = 10;
size_t c = b + a, d = a + b;
check.c:8:20: warning: initialization of ‘size_t’ {aka ‘long unsigned int’} from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
8 | size_t c = b + a, d = a+b;
| ^
check.c:8:31: warning: initialization of ‘size_t’ {aka ‘long unsigned int’} from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
8 | size_t c = b + a, d = a+b;
| ^
Только void* не слишком удобно. Но похоже Вы еще один пункт для статьи нашли:
int a[4] = {0,1,2,3};
int b = 2;
printf("%d %d",*(a+b),*(b+a));
"2 2", никаких ворнингов. Никогда бы не подумал.
Про индекс массива: https://wiki.sei.cmu.edu/confluence/display/c/ARR30-C.+Do+not+form+or+use+out-of-bounds+pointers+or+array+subscripts - про это? Напоминает "Нельзя курить во время тренировки но можно тренироваться во время курения". А если массив без размера? А если массив не был объявлен как массив? А если по каким то соображениям было удобно B определить как &A[n], то B[-1] уже нельзя, но A[n-1] можно? А если...? Так то проблема серьезная, но формализация метода решения странная и все игнорят (и я тоже, увы).
Как посмотрю, напишу. Пока Штрассен интереснее. Да и в целом BLIS/openBLAS интереснее. В двупоточном что-то в любом случае теряется, 100% не получить из за стохастичности процесса.
Да надо бы по хорошему, коли уж занялся этим. Хотя кмк именно для этого старого проца врядли что-то изменилось с той картинки (MKL там есть). Так то меня не столько интересовала производительность, сколько понять где она пропадает и еще есть такой "стереотип" чтоли, что одновременная многопоточность не подходит для вычислений, вот разобраться почему
Skylake без X (без AVX-512) не считают достойным отдельной ветки ядра (что логично). Тут есть для Haswell 3.5 Ггц, на моем 3.8. Вполне корелирует с локальными прогонами. У меня получилось BLIS ~104, OpenBLAS ~102. Это не совсем корректно сравнивать, в либах там обработка краев, которую пока неохота делать от слова совсем. Я в блисе выкидывал "лишние" проверки, получились вот те самые 106.7 что в статье, но за прям равенство условий не поручусь.
Ну и да, если уж соревноваться по честному, то надо брать ассемблер, смотреть что там с фронтендом в двунитковой версии, подгонять под кеш микроинструкций. Так то и так норм, сишный код, 97% утилизации.
В теории да, в деталях реализации по крайней мере сейчас - кмк нет. Основное возражение - он рекурсивный, раскладка данных в памяти Гото, которая тут и везде, ему не понравится. Можно подумать, как их для него раскладывать, почему бы и нет. Там еще скрытый линейный коэффициент на современных железках - ему надо много записей в память, а этого добра традиционно в два раза меньше чем чтения. Т.е. теоретический выигрыш на заданном размере надо делить на два.
Не могу полностью согласиться что никакого секрета. Есть дилетантское мнение (возможно неправильное но пока не опровергнутое) что если из известной "ОС" убрать виртуальную машину то она перестанет кушать аккумуляторы в конских количествах и станет пошустрее. Т.е. рынок уже протоптан, на нем доминирует некачественный продукт, который даже понятно как улучшить. Но... мегакорпорация, попытавшаяся откусить кусок, сбежала. Конкурент - да, Петя имеется. С предпринимательской чуйкой, качественным продуктом и т.п. Только лидером на собственном рынке он не является. Остальные померли, несмотря на множество лояльных клиентов. Весьма ресурсные конторы вместо попыток подмять под себя рынок платят линенцзионные платежи за даунгрейд своего железа, или делают форк того-же но в профиль. И это в общем нормальный ход дел именно для софта. Возможно действительно дело в том что все заливают железом, но производители железа получается платят два раза (за код который его тормозит и за разработку чтобы все таки не слишком тормозило) и довольны.
Кстати да, почему так?
Два автозавода одновременно начали делать один и тот-же продукт. Один начал выпускать дешманские тарантайки через месяц, другой - хорошие машины через два года. Вторая модель видимо выгоднее при наличии ресурсов, по крайней мере автозаводы обычно строят без подсобных хозяйств по ручному выпуску бюджетных малолитражек до старта основного конвейера.
Две фабрики начали выпускать микроволновки. Одна выпустила глючное воняющее пластиком поделие через месяц, другая через год качественный продукт. Те же соображения.
Вася пустил постояльцев жить в курятнике и к концу сезона был с прибылью, Петя построил микроотель с кондишками к следующему. Если он этот год переживет - в следующем все будет неплохо.
Почему-то везде есть граница качества, ниже которой продукт не нужен, и везде есть кореляция качество-деньги. И только в софте это не работает. Ну или не везде работает, все же в играх есть какая-то связь между ценой и качеством, и в некоторых других сегментах тоже.
Проблема же не в том что Петя выпустил свой продукт позже, и даже не в том что Вася нанял двух прогеров (ему кстати повезло что их через пять месяцев осталось двое а не восемь и они даже что-то там доделали нужное а не переписали всё на свежем фреймворке. У Пети этот риск намного меньше просто в силу его подхода). И далеко не факт что у Пети нет ресурсов на раскрутку. Скорее в том что именно ресурсы на раскрутку и решат какая поделка выживет, а их качество не решает примерно ничего и потому может быть соптимизировано. При "низком" старте Вася просто поделил свои ресурсы на два направления а Петя направил на одно.
кстати да, тоже было такое, хотя и не так проявлялось (в плане что встроенный массив не панацея). Но здесь Вы работаете с абстракцией как с другой абстракцией (чуть ниже как с памятью и это уже прокатывает, хотя тоже смешивание) - дело сознательное. В начальном примере и этого нет, а константы размера/цикла могут быть обфусцированы, преднамеренно или нет.
Если в плане что здесь природные законы заканчиваются и начинаются человеческие со всеми их особенностями - то полностью согласен.
Список UB это что-то вроде перечня триггеров, включающих фантазии компилятора на тему оптимизации, которые правильно работают только на определенном подмножестве случаев, причем точно его границы компилятор сам определить не может. Если романтичное undefined behaviour заменить на прозаичное known issues - мысленный путь до workaround становится значительно короче.
справедливости ради, в вашем же блоге была статья, в которой std::array не только не ловит выход за массив, а генерит код с безусловно бесконечным циклом, который вываливает все содержимое стека (подозреваю что из-за constexpr const_reference operator[], что дает компилятору повод пооптимизировать обращения к несуществующим элементам). В комментах победило мнение что это не баг а фича, пути UB непостижимы. Но как-то таких фич не хочется.
Что-то как-то сумбурно получилось
можно читать как
хотя что именно возвращает функция неважно для иллюстрации, но так что-то более осмысленное. Туманная ремарка про потерю и возврат CPU, потому что это про RCU, и мы под грейс-периодом, который в случае разных процессов а не тредов злое ядро может неограниченно продлить.
https://github.com/runityru/rc-singularity/blob/9d1789fdf8754615195a111f2279f71972334e04/allocator.c#L92 тут есть рабочая реализация старой версии без темной магии с сегфолтами, с проверкой. Которую приходится при каждом разыменовании в цепочке выполнять, а можно оптом через сегфолт или userfaultfd. Но идея та же.
Похоже фразой про нюансы я случайно задел чьи то чувства. Может все таки поясните свою позицию? Какое из следующих утверждений является неверным?
макроассемблерЯВУ Си не имеет встроенных средств отличия "распределенной" памяти от "нераспределенной".Он полагается в различении этих категорий в масштабах страниц на железо и ОС
В масштабах байт статус "распределенности" не играет никакой роли, важно "назначение". Использование памяти "не по назначению" приведет к UB, даже если она перед этим была "распределена" маллоком, на стеке или еще как-то. За "назначение" отвечают компилятор, линковщик, загрузчик процесса, процессор - за свои конечные подмножества случаев, программист - за все остальное.
Если ОС говорит, что страница данного адреса была выделена процессу, и адрес либо назначен в конечные подмножества пункта 3, но его использование не противоречит определенным правилам, установленным языком (вызов функции, разыменование переменной, чтение данных), либо не назначен в них и правила использования памяти, произвольно установленные программистом, не противоречат сами себе и правилам выше, то с точки зрения языка адрес "распределен", даже если явно никогда не выделялся. При этом способы, которыми ОС и программист выполняют свою часть работы, никак языком не регулируются, кроме нескольких частных случаев, об одном из которых дискуссия выше.
Из пунктов 2-4 следует что чтение данных по произвольному адресу не является UB пока ОС и железо не против, чего можно добиться способами, к языку не относящимися.
Не претендую на истину в последней инстанции, но хотелось бы серьезных возражений.
C точки зрения компилятора вообще нет причин беспокоиться. Упрощенно как-то так выглядит:
трейс-кеш это что-то ужасно старое. заменили на микроопс кеш и он делится ровно пополам на интеле, что описано в статье про уязвимость (https://ieeexplore.ieee.org/document/9499837).
Мне кажется, проблема smt в том что его серьезно никто за 20 лет не стал воспринимать. ("Мы запустили программу name и она быстрее/медленнее на x% с включенным/выключенным SMT"). Это как эффективность SSE оценивать по фпс в doom. Кооперативные потоки это отлично (например про умножение матриц я специально выяснял), но как гарантировать их кооперативность я не нашел. Как заставить компилятор конкретные функции оптимизировать под порезанное ядро тоже не нашел (да и всю прогу целиком). Не исключаю что плохо искал, но как минимум хорошо спрятано. При этом всякие бигдаты с рандомным доступом на вид должны разгоняться очень хорошо (пример кстати хороший)
Теоретически это UB. Практически для ситуации описанной выше (там не код а данные, которые мы не пишем а читаем), не такое уж оно и undefined.
Мы можем прочитать мусор, позже это опознаем и выкинем.
Мы можем зациклиться если это "преследование указателя". Вариант теоретический, но надо иногда проверять а не читаем ли мы мусор до того как указатель догоним.
Мы можем упасть в сегфолт. Самое неприятное. Можно проверить, действительно ли эту память выделяли. Дорого, ситуация редкая а проверять придется постоянно. Можем перехватить сегфолт, проверить а не в определенной ли точке кода он случился, и если там то longjmp на выход, а если нет то валимся дальше. Ну или в свежем линуксе сделать тоже самое более цивилизованным способом (я кстати все не соберусь попробовать).
Британскую королеву код славить точно не начнет. В результате получается усточивость к манипуляциям ядра с процессом и реализуемость некоторых локфри алгоритмов в юзерспейс. Обычно такой трюк для подкачки используется и возможные адреса обращений там все таки резервируются, тут извращенное применение но работает.
как бы да, но есть нюансы :)
https://man7.org/linux/man-pages/man2/userfaultfd.2.html
За что минус то. Два треда. Один начал что-то читать но подвис. Второй тем временем все переписал. Первый очнулся, прочитал до конца, в том числе ссылку, которая уже не ссылка. Если хочется локфри - а его хочется, то можно или как-то руками проверить - а ссылка ли это, или перехватить сигсегв или вот эту штуку использовать. Вполне себе такой штатный сигсегв получается.
та же беда.
Статью прочитал но прямой связи не увидел. Если я объявил что-то как char [16 (константа)] и потом полез к 17му байту (константа) то да, разворот цикла поломается. Наверное. По крайней мере приводится случай когда он поломался. Если я объявил что-то как char *, присвоил этому адрес из середины другого куска (важно что не выделял) и начал прыгать по нему как по массиву (так более читаемо, и выше много примеров что так думаю не я один) - то, возможно, компилятор который на этом сломается я не встречу пока сам не напишу, т.к. массовым ему не стать.
Это ж не я предложил так сконвертить. Но с интом тоже странно выглядит.
А вобще gcc считает размер void за 1, но ругается.
https://gcc.gnu.org/onlinedocs/gcc/Pointer-Arith.html
Первая часть не понятна. a[b] это *(a+b), не *(b+a). Что тут void*, что int и почему они должны местами поменяться?
Вобще похоже приводится к void* оба, но это странно:
Только void* не слишком удобно. Но похоже Вы еще один пункт для статьи нашли:
"2 2", никаких ворнингов. Никогда бы не подумал.
Про индекс массива: https://wiki.sei.cmu.edu/confluence/display/c/ARR30-C.+Do+not+form+or+use+out-of-bounds+pointers+or+array+subscripts - про это? Напоминает "Нельзя курить во время тренировки но можно тренироваться во время курения". А если массив без размера? А если массив не был объявлен как массив? А если по каким то соображениям было удобно B определить как &A[n], то B[-1] уже нельзя, но A[n-1] можно? А если...? Так то проблема серьезная, но формализация метода решения странная и все игнорят (и я тоже, увы).
Как посмотрю, напишу. Пока Штрассен интереснее. Да и в целом BLIS/openBLAS интереснее.
В двупоточном что-то в любом случае теряется, 100% не получить из за стохастичности процесса.
Да надо бы по хорошему, коли уж занялся этим. Хотя кмк именно для этого старого проца врядли что-то изменилось с той картинки (MKL там есть). Так то меня не столько интересовала производительность, сколько понять где она пропадает и еще есть такой "стереотип" чтоли, что одновременная многопоточность не подходит для вычислений, вот разобраться почему
del
i5-8265U
https://github.com/flame/blis/blob/master/docs/Performance.md#haswell
Skylake без X (без AVX-512) не считают достойным отдельной ветки ядра (что логично). Тут есть для Haswell 3.5 Ггц, на моем 3.8. Вполне корелирует с локальными прогонами. У меня получилось BLIS ~104, OpenBLAS ~102. Это не совсем корректно сравнивать, в либах там обработка краев, которую пока неохота делать от слова совсем. Я в блисе выкидывал "лишние" проверки, получились вот те самые 106.7 что в статье, но за прям равенство условий не поручусь.
Ну и да, если уж соревноваться по честному, то надо брать ассемблер, смотреть что там с фронтендом в двунитковой версии, подгонять под кеш микроинструкций. Так то и так норм, сишный код, 97% утилизации.
не линейный а логарифмический, не на два а сильно меньше, но не выигрыш а результат. А так почти всё верно )
А есть опенсорс пример использования? Вот что нашел: https://dl.acm.org/doi/10.5555/3014904.3014983, почитаю на досуге )
В теории да, в деталях реализации по крайней мере сейчас - кмк нет. Основное возражение - он рекурсивный, раскладка данных в памяти Гото, которая тут и везде, ему не понравится. Можно подумать, как их для него раскладывать, почему бы и нет. Там еще скрытый линейный коэффициент на современных железках - ему надо много записей в память, а этого добра традиционно в два раза меньше чем чтения. Т.е. теоретический выигрыш на заданном размере надо делить на два.