Комментарии 36
Наименования параметров в С:
1) Книга "Язык программирования Си": void swap (int *px, int *py).
2) В примере на сайте:int levenshtein(const char* s1, const char* s2) {
Понятнее наименования параметров в варианте 2. Можно писать int* px и int *px?
Разницы нет, это имеет отношение только к представлению кода для лучшего понимания
Если гнаться за непротиворечивостью, то char const * s1 , чтобы тип легко читался (указатель на... const... char).
Но непротиворечивость - это не про Си и у неё есть цена.
double[6][3] matrix = 0;
matrix[2][5] = 3.14;Цена непротиворечивости в D, наглядно (размерность читается справа налево, а индексы слева направо).
Статья интересная, но адрес функции это не секретная информация
Нет, это
«dma bypass» (программный метод обхода защитных механизмов).
Лучше часть убрать, она заменяется на printf("%p\n", bar); (или printf("0x%"PRIxPTR"\n", (uintptr_t)bar);) и пропадают ошибки (лишний volatile, sizeof считает размер указателя на буфер, а не буфера, указатель на функцию с такой-то сигнатурой где нужен просто указатель, разбор на отдельные байты сталкивает нас с endianness'ом железа, а так как повсюду little-endian, то выводится неправильно).
Потому, что в x86 архитектуре память, принадлежащая процессу, всегда доступна для чтения. Секция кода защищена только от записи. А читать можно спокойно не только адрес функции, но и ее машинный код.
в последнем примере вычисляется бит чётности, а не чётность числа.
Я так и не понял, что автор хотел сделать с адресом функции. Указатель как указатель. Если хочется, всегда можно кастануть к uint64_t.
Как-то много ваш левенштейн аллоцирует. Можно обойтись одной строкой, а то и вовсе перейти на VLA если С99 поддерживается.
gcc-12 levenstein.c -o levenstein && ./levenstein
int levenstein(const char* s1, const char* s2) {
int n = strlen(s1);
int m = strlen(s2);
if (n == 0) return m;
if (m == 0) return n;
if (n > m) {
const char* tmp = s1;
s1 = s2;
s2 = tmp;
int t = n;
n = m;
m = t;
}
int row[n + 1];
for (int i = 0; i <= n; i++) {
row[i] = i;
}
for (int j = 1; j <= m; j++) {
int prev = row[0];
row[0] = j;
for (int i = 1; i <= n; i++) {
int temp = row[i];
int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
row[i] = min3(
row[i] + 1, // deletion
row[i - 1] + 1, // insertion
prev + cost // substitution/match
);
prev = temp;
}
}
return row[n];
}
Параллельное вычисление четности числа
Очень быстро и невероятно бесполезно.
Оно вообще не быстро, т.к. достаточно было всего лишь сделать &1 с числом как по итогу и сделано в последней строчке.
Там просто ерунда написана. Эта функция не число на чётность проверяет (тогда действительно младший бит посмотреть достаточно), а вычисляет бит чётности (который зависит от количества выставленных битов в слове). И, в отличие от заявленного, это часто бывает невероятно полезно )
то бишь popcnt()&1 считает?
Типа того. Вернёт 1, если количество выставленных в слове битов нечётное, иначе 0.
Вообще, это один из известных алгоритмов (Compute parity in parallel), взятых с эпичной старинной странички с подборкой всякого такого разного прикольного: Bit Twiddling Hacks https://graphics.stanford.edu/~seander/bithacks.html
перейти на VLA если С99 поддерживается.
Вот так как раз лучше не делать, если не хотите в какой-то момент переполнение стека словить. В таких случаях очень удобна арена как раз, если она есть в проекте
Ну, вощемта если хочется нормальных безопасных функций, то так-то ещё и указатели после аллокации надо проверять. И сдаётся мне, а для сравнений каких-нибудь ДНК там определённо нужна дополнительная буфферизация и алгоритм будет заметно сложнее. Можно какой-нибудь фолбэк бахнуть после проверки размеров, если уж действительно окажется, что в стек не влезло.
Ну так а к чему вы это? То, что надо использовать аллокаторы, а не VLA или alloca, - это факт, потому что стек может переполниться и программа рухнет. То, что надо проверять указатели - тоже факт, хотя в своей программе вполне можно сделать, если это допустимо, обёртку/свой аллокатор, который в случае неудачи будет падать с сообщением об ошибке
В некоторых случаях лучше ограничить сверху максимальный размер строк и использовать VLA или alloca. malloc может довольно долго отрабатывать
Если это критично, то лучше использовать арену. Пишется арена строк в 10, она не переполняет стек, она не требует ручной очистки памяти также, как и VLA.
Арену в 10 строк я бы глянул
В случае нехватки памяти я тут вызываю abort, но легко, например, добавить флаг, который будет указывать, что вместо abort надо возвращать NULL. Также легко сделать longjmp в функцию обработчик вместо abort, или что-то ещё на ваше усмотрение, сильно сложнее код арены от этого вряд ли станет.
#include <stdint.h>
#include <stdlib.h>
#define ROUND_POW2(value, pow) \
((((value) + (pow) - 1)) & ~((pow) - 1))
struct arena {
uint8_t *cur;
uint8_t *end;
};
static inline void* arena_alloc(struct arena *a, size_t size)
{
size = ROUND_POW2(size, sizeof(long));
if(a->cur + size > a->end)
abort();
uint8_t *res = a->cur;
a->cur += size;
return res;
}Определённо не хватает методов инициализации самой арены и как выглядит освобождение арены, то бишь минимальный пример.
Конкретно освобождение памяти нужно не всегда. В нашем случае, например, достаточно передать в функцию копию арены, а не указатель. Тогда после вызова функции все выделенные в арене данные будут автоматически освобождены, прямо как в стеке. Инициализация проста донельзя, в cur кладём указатель на начало буфера, в end - на конец. Буфер либо выделяем с помощью malloc/mmap/etc, либо заводим статический.
То бишь как-то так. Главное в многопотоке потом не поссориться.
К биту чётности (и, наверное, много где ещё) не хватает предупреждения, что не надо пытаться быть умнее компилятора - он имеет __builtin_parity...__builtin_parityll и знает про Parity-Flag-для-младшего-байта в вашем процессоре и с какой микроархитектуры доступна popcnt. https://godbolt.org/z/qdo7x435f
К ошибке в макросах - что о них всё рассказывают правила SEI CERT C. Что опасно нарушать, что нет, как исправлять - 13 правил.
Компилятор-то может имеет, но не каждый компилятор и не на каждой архитектуре. Это расширение, а не часть стандарта языка, так что есть случаи, когда использовать такое — не комильфо. А ещё бывает, что компилятор вроде и умеет в __builtin_parity, но реализовано оно медленнее, потому что готовой инструкции под это дело в целевом процессоре нет. Попробуйте в этом godbolt-сниппете выбрать, скажем, 32-х битную архитектуру PPC (power gcc 15.0.2). Там компилятор вообще сгенерит немаленький такой код, да ещё и вызывающий встроенную функцию (__paritysi2); это не будет быстро.
А ещё бывает, что компилятор вроде и умеет в __builtin_parity, но реализовано оно медленнее, потому что готовой инструкции под это дело в целевом процессоре нет. Попробуйте в этом godbolt-сниппете выбрать, скажем, 32-х битную архитектуру PPC (power gcc 15.0.2). Там компилятор вообще сгенерит немаленький такой код, да ещё и вызывающий встроенную функцию (__paritysi2); это не будет быстро.
Он генерирует вызов функции из поста. Пока что разница в том, что на godbolt он не инлайнится и надо смотреть дальше у себя, если нужна производительность на той платформе. Это же и в других местах повторится, пользы от решения проблем с (?) LTO будет больше, чем велосипедостроения.
Это расширение, а не часть стандарта языка, так что есть случаи, когда использовать такое — не комильфо
Лучше на него сначала наткнуться, GCC и LLVM - это тоже стандарты, которые зачастую важнее бумажного. Хотел сказать, что к тому времени стандарт могут и поправить, но это уже сделали в C23 (__builtin_popcount→stdc_count_ones_ui).
Основная идея — использование битовых масок вместо условных переходов, что теоретически может ускорить выполнение за счёт устранения предсказания переходов процессором.
Судя по godbolt - так и есть, хотя я предполагал, что современные компиляторы знают этот трюк.
Серия обзоров местами занятная.
А вот пример с "Безусловным вычисление минимума/максимума" - прям сборник на тему "как делать не надо". Чему вы учите нейросети?)))
-(x < y) дает 0xFFFFFFFF (все биты 1) если x < y, и 0 если нет
Не факт. Зависит от реализации. Может любое ненулевое число дать.
И тем более не факт, что выражение будет подсчитано без ассемблерных инструкций перехода.
Знаковый бит diff сдвигается вправо
Тоже зависит от реализации. Заменять сдвиг на деление не посоветую - там своё ub есть.
Не факт. Зависит от реализации. Может любое ненулевое число дать.
Эту скрепу отняли у сишников в C23 (предложения N2218&N2330 родом из C++ (P0907R4&P1236R1)).
The sign representation defined in this document is called two’s complement. Previous editions of this document (specifically ISO/IEC 9899:2018 and prior editions) additionally allowed other sign representations.
Тоже зависит от реализации
Эту (отсутствие гарантии sign extension) любовно оставили, обрезав предложение при портировании из C++. Это значит, что у комитета была на уме некая архитектура без arithmetic shift right, где будет поддерживаться C23 (вместе с его плюсово-шаблонными _BitInt'ами), но не будет поддерживаться C++20. Достаточно важная архитектура, чтобы избегать там медленной эмуляции инструкции. Достаточно заметная, потому что в компиляторах под неё задокументировано поведение (Implementation-Defined обязует), необычное. Но называть архитектуру они не станут. А может и не было её... но сама идея, что такую архитектуру можно придумать (черновое название - ds9k) и периодически про неё напоминать, сама идея прекрасна.
Милорд, они уже бегут на Rust, Zig и GNU C? Не надо бояться, все не убегут!..
The sign representation defined in this document is called two’s complement
Не, я про операцию перед минусом, (x < y). В такие дебри, как разное представление знаковых чисел, я даже не влезаю. А вот с представлением bool - ну хз.
Да даже если bool компилятор точно преобразует в int 1 или 0, то какими средствами архитектуры проца? И чем скомпилированный код будет отличаться от if (x<y) ... или от стандартного min=(x<y)?x:y; хз?. Считаю, что вообще ничем.
Не, я про операцию перед минусом, (x < y).
Она таки всегда вела себя одинаково:
Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false. The result has type int.
И чем скомпилированный код будет отличаться
По задумке: будет отличаться отсутствием ветвления (jump'а) => нет работы для предсказателя переходов => не может быть ошибки предсказания перехода => результат быстрее, чем при ошибке предсказания (и стабильный по скорости, если нас волнует утечка информации).
В реальности: GCC на -O0 (!!) распознаёт за этими 5 операциями x < y ? x : y, которое тоже компилируется без ветвления в cmov (ветвление vs. предикация).
https://godbolt.org/z/51YWe7c1s
Чтобы код из статьи "заработал", нужно оружие сильнее, чем -O0:
GNU extended asm с подобранным ограничением
int tmp, tmp2;
// y ^ ((x ^ y) & -(x < y));
tmp = (x < y); asm("" : "+r"(tmp));
tmp = -tmp; asm("" : "+r"(tmp));
tmp2 = x ^ y; asm("" : "+r"(tmp2));
tmp = tmp & tmp2; asm("" : "+r"(tmp));
return y ^ tmp;Весь код и asm - на godbolt.
Пища для ума от цикла статей: что иногда можно найти под капотом компилятора и почему так нельзя делать вручную.
В соседней ветке разговор ушёл куда-то в сторону "стандартный Си местами даёт меньше, чем LLVM (если другой язык завяжется на возможности LLVM, он автоматически окажется впереди)".
Здесь пришли к тому, что стандарту языка нет дела до низкоуровневых возможностей и надо завязываться на расширения компилятора, чтобы попытаться получить желаемое.
Вариант с diff и расширением знака на все биты:
поиск максимума:
Clang распутывает в
cmovна -O1.GCC на любых уровнях не справляется и сохраняет алгоритм.
поиск минимума: оба не распутывают
Очень показательные примеры! Запустил ещё на ARM64 - ровно то же самое: одинаковые по выхлопу куски кода компилируются одинаково. И если компилятор может обойтись условно выполняемыми инструкциями вместо прыжков - он это сделает.
А непотребствами мы только рискуем запутать и себя, и компилятор.
Чему вы учите нейросети?
Плохому!
ГПСЧ на основе MurMur3 перестает проходить многие статистические тесты, если на входе поменять seed и counter местами. Это означает, что если разным потокам дать разные сиды, то между ними возможны скрытые корреляции. 128-битный линейный конгруэнтный генератор в таком виде неплох, но проваливает два теста - TMFn из PractRand >= 0.94 и Birthday Spacings with Decimation из SmokeRand.
Ненормальные непотребства, трюки, хаки и алгоритмы на C