Иногда человек может обнаружить такие возможности оптимизации, которые не видит компилятор. В этой статье мы начнём с цикла, сгенерированного из кода Си с помощью clang, и скорректируем его разными способами, попутно измеряя прирост в скорости.
Эта статья публиковалась на главной странице HackerNews, и к её обсуждению вы можете присоединиться здесь.
Дисклеймер: я не эксперт по оптимизациям. По факту мой опыт касается высокоуровневых, чисто функциональных языков, где программист обычно не думает о том, как программа выполняется.
Листинги кода из этой статьи можно найти на GitHub.
Часть I
▍ Функция
Мы начнём с функции, которая перебирает строку и в зависимости от встречаемых символов инкрементирует либо декрементирует число.
int run_switches(char *input) {
int res = 0;
while (true) {
char c = *input++;
switch (c) {
case '\0':
return res;
case 's':
res += 1;
break;
case 'p':
res -= 1;
break;
default:
break;
}
}
}Инкрементирование происходит при встрече
s (successor, следующий элемент), а декрементирование при встрече p (predecessor, предыдущий элемент).Это достаточно небольшая функция, которую gcc и clang должны неплохо оптимизировать. Может, даже оптимально? Изначально я написал её, чтобы увидеть, создаст gcc таблицу переходов или же поиск.
Вот, что выдал clang (заполняющие no-op удалены и комментарии добавлены вручную):
# llvm-objdump -d --symbolize-operands --no-addresses --x86-asm-syntax=intel --no-show-raw-insn loop-1-clang.c.o
run_switches:
xor eax, eax # res = 0
loop: # while (true) {
movsx ecx, byte ptr [rdi] # c = *input
test ecx, ecx # if (c == '\0')
je ret # return
add rdi, 1 # input++
cmp ecx, 'p' # if (c == 'p')
je p # goto p
cmp ecx, 's' # if (c == 's')
jne loop # continue
add eax, 1 # res++
jmp loop # continue
p: add eax, -1 # res--
jmp loop # }
ret: ret# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-1-clang.c.o
run_switches:
xor eax, eax
loop:
╭────➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─── je ret
│ │ add rdi, 1
│ │ cmp ecx, 'p'
│ │ ╭─ je p
│ │ │ cmp ecx, 's'
├─│─│─ jne loop
│ │ │ add eax, 1
├─│─│─ jmp loop
p: │ │ ╰➤ add eax, -1
╰─│─── jmp loop
ret: ╰──➤ ret- Время выполнения: 3.23 s
- Скорость: 295.26 MiB/s
Gcc выдал немного больше кода, который выполнился чуть быстрее.
Этот код довольно прост – в нём есть три условных инструкции ветвления (
je, je, jne), ведущие к четырём возможным блокам: \0, s, p, а также блок для всех других символов.▍ Перестройка ветвлений
Тем не менее об этом цикле мы кое-что знаем. Нам известно, что выход из него происходит только при достижении нуль-терминатора (
\0). Генерируемый clang код сначала выполняет проверку наличия нуль-терминатора, но в этом нет смысла. Максимальное число нуль-терминированных строк, с которыми встретится эта функция, равно 1. Поэтому нам следует оптимизировать функцию так, чтобы сначала выполнялась проверка присутствия p или s и других символов, а не нуль-терминатора.Немного перестроим наш цикл.
run_switches:
xor eax, eax
loop: ╭─────➤ movsx ecx, byte ptr [rdi]
│ inc rdi
│ cmp ecx, 'p'
│ ╭──── je p
│ │ cmp ecx, 's'
│ │ ╭── je s
│ │ │ test ecx, ecx
├─│─│── jne loop
│ │ │ ret
p: │ ╰─│─➤ dec eax
├───│── jmp loop
s: │ ╰─➤ inc eax
╰────── jmp looprun_switches:
xor eax, eax
loop: movsx ecx, byte ptr [rdi]
inc rdi
cmp ecx, 'p'
je p
cmp ecx, 's'
je s
test ecx, ecx
jne loop
ret
p: dec eax
jmp loop
s: inc eax
jmp loopОтлично! Теперь мы выполняем ветвление раньше — при встрече
p или s, а не редкого \0.- Время выполнения: 3.10 s
- Прирост скорости:: 1.04x
- Скорость: 307.64 MiB/s
▍ Перестановка блоков
Итак, оба типичных случая (
p и s) переместились в начало цикла, так почему бы нам не удалить одну из этих ветвей, поместив её целевой блок (или BasicBlock™, для специалистов по компиляторам) в начало цикла?run_switches:
xor eax, eax
╭───── jmp loop
s: │ ╭──➤ inc eax
loop: ├─│──➤ movsx ecx, byte ptr [rdi]
│ │ inc rdi
│ │ cmp ecx, 'p'
│ │ ╭─ je p
│ │ │ cmp ecx, 's'
│ ╰─│─ je s
│ │ test ecx, ecx
├───│─ jne loop
│ │ ret
p: │ ╰➤ dec eax
╰───── jmp looprun_switches:
xor eax, eax
jmp loop # This is new
s: inc eax # This is up here now
loop: movsx ecx, byte ptr [rdi]
inc rdi
cmp ecx, 'p'
je p
cmp ecx, 's'
je s
test ecx, ecx
jne loop
ret
p: dec eax
jmp loopПрекрасно! Теперь наш блок
s перескакивает (fall through) в цикл без ветвления. Неплохо.Вы заметите, что теперь нам нужно переходить в цикл из начала функции, чтобы избежать выполнения блока
s. Хотя это довольно хороший компромисс – переход в цикл из функции происходит один раз в то время, как символов s мы встречаем множество.Но насколько быстрым окажется этот вариант?
- Время выполнения: 2.98 s
- Общее ускорение: 1.08x
- Скорость: 320.02 MiB/s
▍ Замена переходов арифметикой
Условные переходы нежелательны, но как насчёт стандартного безусловного
jmp? Что, если попробовать убрать возвращение в цикл p:?Декремент равнозначен двум декрементам и одному инкременту, правильно? Значит, давайте используем его для перескакивания в
s:.run_switches:
xor eax, eax
╭────── jmp loop
p: │ ╭─➤ sub eax, 2
s: │ ╭─│─➤ inc eax
loop: ├─│─│─➤ movsx ecx, byte ptr [rdi]
│ │ │ inc rdi
│ │ │ cmp ecx, 'p'
│ │ ╰── je p
│ │ cmp ecx, 's'
│ ╰──── je s
│ test ecx, ecx
╰────── jne loop
retrun_switches:
xor eax, eax
jmp loop
p: sub eax, 2
s: inc eax
loop: movsx ecx, byte ptr [rdi]
inc rdi
cmp ecx, 'p'
je p
cmp ecx, 's'
je s
test ecx, ecx
jne loop
retВот мы и избавились от ещё одной инструкции ветвления, используя простую арифметику. Хорошо. Но будет ли этот код быстрее?
- Время выполнения: 2.87 s
- Общее ускорение: 1.12x
- Скорость: 332.29 MiB/s
Забавный факт. Всё это время мы сравнивали производительность с выводом clang 16, но gcc 12 на деле выдавал более быстрый (хотя и более громоздкий) код. Его версия выполняется также за 2,87 с, так что мы только её догнали. Но при этом наша программа состоит из 13 инструкций, а программа gcc – из 19.
Похоже, что код gcc развернул цикл и до определённой степени повторно использует блоки кейсов.
▍ Без ветвления
Хорошо, но эти условные ветви являются реальной проблемой, не так ли? Как ускорить их прогнозирование? Я не знаю, поэтому давайте просто не будем его использовать.
# rdi: char *input
# eax: output
# r8: 1
# edx: -1
# ecx: char c
# esi: n
run_switches:
xor eax, eax
mov r8d, 1
mov edx, -1
loop:
╭──➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─ je ret
│ │ inc rdi
│ │ mov esi, 0
│ │ cmp ecx, 'p'
│ │ cmove esi, edx
│ │ cmp ecx, 's'
│ │ cmove esi, r8d
│ │ add eax, esi
╰─│─ jmp loop
ret: ╰➤ ret# rdi: char *input
# eax: ouput
# r8: 1
# edx: -1
# ecx: char c
# esi: n
run_switches:
xor eax, eax # res = 0
mov r8d, 1 # need 1 in a register later
mov edx, -1 # need -1 in a register later
loop: # while (true) {
movsx ecx, byte ptr [rdi] # char c = *input
test ecx, ecx # if (c == '\0')
je ret # return
inc rdi # input++
mov esi, 0 # n = 0
cmp ecx, 'p' # if (c == 'p')
cmove esi, edx # n = -1
cmp ecx, 's' # if (c == 's')
cmove esi, r8d # n = 1
add eax, esi # res += n
jmp loop # }
ret: retВау, мы удалили из графа потока управления множество стрелок…
Вместо условного ветвления/переходов мы, в зависимости от текущего символа, используем для сложения разные значения. Это мы делаем с помощью
cmove или «условного перехода согласно равенству».Правила таковы: по умолчанию использовать ноль, при встрече
s использовать 1, а при встрече p использовать -1. При этом всегда выполнять сложение. Неплохой поворот, но будет ли так быстрее?
- Время выполнения: 0.48 s
- Общее ускорение: 6.73x
- Скорость: 1.94 GiB/s
Да уж, получилось чертовски быстро.
▍ Освобождение регистра
В x86_64 есть ещё один способ условной установки регистра (1 байта) на 0 или 1. Он называется
sete. Давайте используем его и избавимся от нашего r8d.run_switches:
xor eax, eax
mov edx, -1
loop:
╭──➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─ je ret
│ │ inc rdi
│ │ mov esi, 0
│ │ cmp ecx, 's'
│ │ sete sil
│ │ cmp ecx, 'p'
│ │ cmove esi, edx
│ │ add eax, esi
╰─│─ jmp loop
ret: ╰➤ retrun_switches:
xor eax, eax # res = 0
mov edx, -1 # need -1 in a register later
loop: # while (true) {
movsx ecx, byte ptr [rdi] # char c = *input
test ecx, ecx # if (c == '\0')
je ret # return
inc rdi # input++
mov esi, 0 # n = 0
cmp ecx, 's' # c == 's'?
sete sil # n = 0|1
cmp ecx, 'p' # if (c == 'p')
cmove esi, edx # n = -1
add eax, esi # res += n
jmp loop # }
ret: retНо обеспечит ли это ускорение?
- Время выполнения: 0.51 s
- Общее ускорение: 6.33x
- Скорость: 1.83 GiB/s
Что ж, получилось медленнее, чем при использовании
cmov. Думаю, нет смысла задействовать меньше регистров или использовать 8-битные операции вместо 32-битных.▍ Другие попытки
Я попытался развернуть цикл нашей лучшей версии кода. В результате код замедлился.
Тогда я решил выровнять начало цикла по 16-байтовой границе (профессиональный совет: вы можете добавить
.align <bytes> перед меткой, и GNU Assembler вставит инструкции nop за вас). Это тоже замедлило код.▍ Настройка бенчмарка
$ uname -sr
Linux 6.1.33
$ lscpu
...
Model name: AMD Ryzen 5 5625U with Radeon Graphics
CPU family: 25
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
$ clang --version
clang version 16.0.1
$ gcc --version
gcc (GCC) 12.2.0Версии Си были скомпилированы с использованием
-march=native, сообщая компилятору, что нужно создать код, который будет выполняться быстро на конкретно моём процессоре, а не каком-то среднем x86_64.Этот бенчмарк тысячу раз прогоняет функцию для списка из миллиона символов (со случайными вхождениями
p и s).Для каждой версии я выполнил этот тест несколько раз, выбрав лучшие результаты.
▍ Выводы
Порой можно добиться 6-кратного ускорения путём ручной правки сжатого цикла Си в ассемблере и оптимизации с помощью техник, которые в компиляторы, похоже, ещё не встроили.
Но это ещё не конец, и далее вас ждёт вторая часть моего эксперимента.
Часть II
В первой части мы написали небольшую программу на Си, скомпилировали её, дизассемблировали, а затем скорректировали, добившись шестикратного ускорения. Теперь же мы этот результат улучшим.
Листинги из этой части также лежат на GitHub.
Первая версия нашей программы могла обрабатывать 295.26 MiB/s, а её лучший вариант – 1.94 GiB/s.
Итак, начнём с первой версии:
int run_switches(char *input) {
int res = 0;
while (true) {
char c = *input++;
switch (c) {
case '\0':
return res;
case 's':
res += 1;
break;
case 'p':
res -= 1;
break;
default:
break;
}
}
}# llvm-objdump -d --symbolize-operands --no-addresses --x86-asm-syntax=intel --no-show-raw-insn loop-1-gcc.c.o
run_switches:
xor eax, eax # res = 0
loop: # while (true) {
movsx ecx, byte ptr [rdi] # c = *input
test ecx, ecx # if (c == '\0')
je ret # return
add rdi, 1 # input++
cmp ecx, 'p' # if (c == 'p')
je p # goto p
cmp ecx, 's' # if (c == 's')
jne loop # continue
add eax, 1 # res++
jmp loop # continue
p: add eax, -1 # res--
jmp loop # }
ret: ret# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-2-gcc.c.o
run_switches:
xor eax, eax
loop:
╭────➤ movsx ecx, byte ptr [rdi]
│ test ecx, ecx
│ ╭─── je ret
│ │ add rdi, 1
│ │ cmp ecx, 'p'
│ │ ╭─ je p
│ │ │ cmp ecx, 's'
├─│─│─ jne loop
│ │ │ add eax, 1
├─│─│─ jmp loop
p: │ │ ╰➤ add eax, -1
╰─│─── jmp loop
ret: ╰──➤ ret- Время выполнения: 3.23 s
- Скорость: 295.26 MiB/s
▍ Отбрасывание кейсов
Мы выразили задачу логическим образом сверху вниз. В ней мы перебираем входные данные по одному символу и выполняем анализ кейсов для возможных вариантов (иными словами, переключаем символы).
В зависимости от результатов анализа кейсов мы выполняем разный код.
Чтобы этого избежать, мы объединим пути кода, имеющие общую структуру. Оба кейса –
p и s – добавляют в аккумулятор число. Может, тогда вместо выполнения анализа кейсов для перехода к следующему пути кода, мы будем с помощью того же анализа получать число для прибавления?Это число можно искать в массиве:
#include <stdbool.h>
static
int to_add[256] = {
['s'] = 1,
['p'] = -1,
};
int run_switches(const char *input) {
int res = 0;
while (true) {
char c = *input++;
if (c == '\0') {
return res;
} else {
res += to_add[(int) c];
}
}
}# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-2-gcc.c.o
run_switches:
movsx rax, byte ptr [rdi]
lea rdx, [rdi+1]
xor ecx, ecx
lea rsi, [rip+0] # <run_switches+0x11>
test al, al
╭─── je ret
│ nop dword ptr [rax]
loop: │ ╭➤ add rdx, 0x1
│ │ add ecx, dword ptr [rsi+rax*4]
│ │ movsx rax, byte ptr [rdx-1]
│ │ test al, al
│ ╰─ jne loop
ret: ╰──➤ mov eax, ecx
ret# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-2-clang.c.o
run_switches:
mov cl, byte ptr [rdi]
test cl, cl
╭─── je ret
│ add rdi, 0x1
│ xor eax, eax
│ lea rdx, [rip+0x0] # <run_switches+0x13>
│ cs nop word ptr [rax+rax*1+0x0]
│ nop dword ptr [rax]
loop: │ ╭➤ movsx rcx, cl
│ │ add eax, dword ptr [rdx+rcx*4]
│ │ movzx ecx, byte ptr [rdi]
│ │ add rdi, 0x1
│ │ test cl, cl
│ ╰─ jne loop
│ ret
ret: ╰──➤ xor eax, eax
ret- Время выполнения GCC: 0.47 s
- Скорость GCC: 1.98 GiB/s
- Время выполнения Clang: 0.25 s
- Скорость Clang: 3.72 GiB/s
Неплохо. В случае gcc мы достигли скорости нашей лучшей (
cmov) версии из предыдущей части, но вывод clang почти вдвое её опередил.Между gcc и clang присутствует какое-то реально странное отличие. Насколько сильной может быть разница в быстродействии между этими строками:
movzx ecx, byte ptr [rdi]
movsx rax, byte ptr [rdx-1]Думаю, что смогу заставить gcc cгенерировать версию с
movzx (перемещение и дополнение нулями) вместо movsx (перемещение и дополнение символами), используя в качестве инструкции беззнаковый целочисленный тип, то есть uint8_t или unsigned char вместо char. Попробуем:
#include <stdbool.h>
#include <stdint.h>
static
int to_add[256] = {
['s'] = 1,
['p'] = -1,
};
int run_switches(const uint8_t *input) {
int res = 0;
while (true) {
uint8_t c = *input++;
if (c == '\0') {
return res;
} else {
res += to_add[(int) c];
}
}
}# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-3-gcc.c.o
run_switches:
movzx eax, byte ptr [rdi]
lea rdx, [rdi+0x1]
xor ecx, ecx
lea rsi, [rip+0x0]
test al, al
╭───── je ret
│ nop dword ptr [rax+0x0]
loop: │ ╭─➤ movzx eax, al
│ │ add rdx, 1
│ │ add ecx, dword ptr [rsi+rax*4]
│ │ movzx eax, byte ptr [rdx-1]
│ │ test al, al
│ ╰── jne loop
ret: ╰────➤ mov eax,ecx
ret# objdump -Mintel -d --no-addresses --no-show-raw-insn --visualize-jumps loop-3-clang.c.o
run_switches:
mov cl, byte ptr [rdi]
test cl, cl
╭───── je ret
│ add rdi, 1
│ xor eax, eax
│ lea rdx, [rip+0x0]
│ cs nop word ptr [rax+rax*1+0x0]
│ nop dword ptr [rax]
loop: │ ╭─➤ movzx ecx, cl
│ │ add eax, dword ptr [rdx+rcx*4]
│ │ movzx ecx, byte ptr [rdi]
│ │ add rdi, 1
│ │ test cl, cl
│ ╰── jne loop
│ ret
ret: ╰────➤ xor eax,eax
retСработало, но окажется ли этот код быстрее?
- Время выполнения GCC: 0.47 s
- Скорость GCC: 1.98 GiB/s
- Время выполнения Clang: 0.25 s
- Скорость Clang: 3.72 GiB/s
Нет. Всё в точности, как и прежде. Хорошо, тогда в чём отличие между этими вариантами:
loop: ╭─➤ movzx eax, al
│ add rdx, 1
│ add ecx, dword ptr [rsi+rax*4]
│ movzx eax, byte ptr [rdx-1]
│ test al, al
╰── jne looploop: ╭─➤ movzx ecx, cl
│ add eax, dword ptr [rdx+rcx*4]
│ movzx ecx, byte ptr [rdi]
│ add rdi, 1
│ test cl, cl
╰── jne loopОтличия три:
- порядок;
-
[rdi]вместо[rdx - 1]; - выбор регистров.
▍ Пропуск дополнения
Оба компилятора выдали инструкцию
movzx для преобразования входного символа в целое число.Я не думаю, что эта инструкция необходима в каком-либо из этих компиляторов, поскольку 32-битные операции на x86_64 внутренне выполняют дополнение нулями, и я не вижу ни одного пути кода, где старшие биты были бы установлены.
Тем не менее некоторое чутьё подсказывает мне, что можно избавиться от этих инструкций на стороне Си, заменив:
uint8_t c = *input++;На
uint64_t c = *input++;Таким образом мы удаляем всю идентификацию этого значения как 8-битного, требующего дополнения нулями.
loop: /-> add rdx, 1
| add ecx, dword ptr [rsi+rax*4]
| movzx eax, byte ptr [rdx-1]
| test rax, rax
\-- jne looploop: /-> movzx ecx,cl
| add eax,dword ptr [rdx+rcx*4]
| movzx ecx,byte ptr [rdi]
| add rdi,0x1
| test cl,cl
\-- jne <run_switches+0x20>Что ж, для gcc сработало.
На одну инструкцию меньше без разбирания кода до уровня ассемблера. Весьма неплохо.
- Время выполнения gcc 0.47 s
- Скорость gcc: 1.98 GiB/s
Но…никакого эффекта.
▍ Переписывание asm
Давайте перепишем этот код в ассемблере – это позволит понять, что именно происходит.
Нет, нельзя надёжно пересобрать дизассемблированный код… Потребуется по меньшей мере скорректировать вывод. В данном случае я написал массив, из которого выполняется считывание посредством директив ассемблера gcc, и добавил метки перехода, чтобы сделать его читаемым.
.text
run_switches:
xor eax, eax # res = 0
loop: # while (true) {
/----> movsx rcx, byte ptr [rdi] # char c = *input
| test rcx, rcx # if (c == '\0')
| /-- je ret # return
| | add eax, dword ptr [arr+rcx*4] # res += arr[c]
| | inc rdi # input++
\--|-- jmp loop # }
ret: \-> ret
.data
arr:
.fill 'p', 4, 0
.long -1, 0, 0, 1
.fill (256 - 's'), 4, 0Это моё первое выполнение, и тут мы видим буквальный перевод версии Си. Здесь у нас на критическом пути даже два перехода (один дополнительный безусловный) в сравнении с выводом gcc и clang. Как же это скажется на скорости?
- Время выполнения: 0.24 s
- Скорость: 3.88 GiB/s
Что ж, этот вариант с первой попытки превзошёл gcc и clang. Я ожидал, что будет труднее написать более быстрый код, чем создают современные компиляторы со множеством оптимизаций…
▍ Разбираем кодирование
Вывод gcc загружает адрес массива в регистр и использует его для обращения к этому массиву на критическом пути:
lea rsi, [add_arr]
...
add ecx, dword ptr [rsi+rax*4]Это кажется излишним, так что мы наверняка можем избавиться от лишней инструкции
lea, используя адрес массива напрямую.add ecx, dword ptr [arr+rax*4]Мы удалили одну инструкцию (
lea) из не критического пути, так? Да, но если сопоставить кодировки инструкций, то мы увидим, что увеличили количество байтов, требуемых для кодирования add, а add является инструкцией на критическом пути. 48 8d 34 25 00 00 00 lea rsi,ds:0x0
...
03 0c 86 add ecx,DWORD PTR [rsi+rax*4]...
03 0c 85 00 00 00 00 add ecx,DWORD PTR [rax*4+0]Думаю, что загрузка адреса первого элемента массива в
rsi является хорошей оптимизацией, если у вас есть свободные регистры. Пока проигнорируем этот момент.▍ Исправление кода gcc
В действительности мы хотим знать, почему внутренний цикл gcc почти вдвое медленнее clang несмотря на то, что они так похожи. Чтобы это выяснить, я скопировал код gcc в программу ассемблера здесь и внёс изменения, необходимые для того, чтобы он заработал.
Если мы выполним бенчмарк для дизассемблированной версии, то он должен занять столько же времени, что и версия gcc, то есть 0,47 секунды.
Ноооо, он занял 0,26 с, оказавшись почти вдвое быстрее. Думаю, я допустил ошибку? Давайте поищем отличия в выводе.
9: 48 8d 35 00 00 00 00 lea rsi,[rip+0]
10: 48 85 c0 test rax,rax
13: 74 13 je 28 ret 9: 48 8d 34 25 00 00 00 lea rsi,ds:0
10: 00
11: 48 85 c0 test rax,rax
14: 74 13 je 29 retАга! Здесь у нас несколько иная кодировка
lea.Я не совсем уверен, что послужило причиной, так как в обеих версиях массив, похоже, сохраняется в разделе
.rodata бинарника. Если кто-то понимает разницу между этими двумя кодировками, отпишите в комментариях или мне на почту.Итак, поскольку единственное ощутимое отличие находится перед критическим путём, я предполагаю, что на производительность влияет разница в выравнивании.
Безусловно, если добавить перед нашим сжатым циклом пять невинных no-op, то мы вернёмся к быстродействию gcc.
Но мы сделаем лучше и построим график, который отразит связь добавления заполняющих no-op и времени выполнения.
Итак, начиная с пяти no-op (по одному байту каждая), мы получаем 2-кратное замедление, которое сохраняется вплоть до 20 no-op, после чего происходит ускорение. Это повторяющийся паттерн?
Да, он определённо повторяется. С какой периодичностью? Надеюсь, что это удобная степень двойки…
… Это 64 – очень хорошо.
В течение 15 байт заполнения выполнение происходит медленно, после чего в течение 49 оно происходит быстро.
Мой внутренний цикл измеряет ровно 16 байт. Значит, этот повторяющийся паттерн из 15 медленных версий должен быть связан с моментом, когда внутренний цикл gcc распределяется вдоль границы двух кэш-линий. А каков размер кэш-линии на моем процессоре? 64 байта.
Хорошие новости! Мы выяснили причину отличия в скорости.
Итак, как нам убедить gcc выровнять цикл более удачно?
Я попробовал
CFLAGS=-falign-jumps= <n> make bench-c-4-gcc при различных значениях n, но ничего не произошло.
Причина, похоже, в том, что верхний сегмент нашего цикла, являясь целью ветвления, также выступает местом, куда происходит переход из кода выше.
Фрагмент из документации gcc:
Цели ветвления, которые могут быть достигнуты только путём перехода, следует выравнивать по величине, равной степени двойки.
К счастью,
CFLAGS=-falign-loops=16 работает!В документации сказано, что
-falign-loops активна по умолчанию с оптимизациями, установленными на >= -O2. Но в ней также говорится: «Если n не указано или равно нулю, используйте значение по умолчанию, определяемое машиной». Думаю, что на моей машине это значение меньше 16 :/Также кажется излишним применять эту опцию для всей компилируемой единицы. В идеале это выравнивание желательно устанавливать вручную только для внутреннего цикла. Gcc предоставляет атрибуты выравнивания, например,
__attribute__((aligned(16))), но они не применимы к меткам/инструкциям – только к функциям.Вся наша функция фактически вписывается в одну кэш-линию и, действительно, установка
__attribute__((aligned(64))) для run_switches работает. Думаю, что это самый тонкий контроль, который вы можете получить, не разбирая код до уровня ассемблера. Хотя, возможно, кто-то знает способ получше?Заключение
- Пожалуй, нет смысла оптимизировать не критические пути.
- Сжатые, выровненные циклы, вписывающиеся в кэш-линию, выполняются молниеносно.
- Сжатые циклы, распределённые по двум кэш-линиям, могут выполняться в 2 раза медленнее своих выровненных альтернатив.
- Похоже, gcc по умолчанию выравнивает код не слишком строго.
- При написании кода GNU Assembler вашим другом окажется
.align <bytes>.
Выиграй телескоп и другие призы в космическом квизе от RUVDS. Поехали? ????
Комментарии (172)
nikolz
14.07.2023 14:03+1Если я правильно понял, то исходный код на СИ на основе switch ,
а в ручной оптимизации фактически switch заменили на if.
Полагаю, что это некорректно, так как оптимизируется совершенно иной алгоритм, чем изначально оптимизировали компиляторы .
datacompboy
14.07.2023 14:03+10switch и if эквивалентны, и компиляторы имеют полное право это делать.
nikolz
14.07.2023 14:03+1Вы не поняли, о чем я написал. Право компиляторов никто не умоляет.
Речь идет о ручной оптимизации автором статьи.
Switch и набор if по-разному преобразуются в машинный код. Обычно switch более громоздкая в машинном коде, но более компактная в C.
В статье автор исходный код на СИ написал с переключателем
а потом оптимизирует алгоритм на ассемблере с использованием условных операторов. А это аналог программ на С c использованием if.
Если бы он написал на СИ два варианта со switch и на основе if и оба варианта оптимизировал компиляторами а потом руками, тогда все было корректно.
powerman
14.07.2023 14:03+5Всё и так вполне корректно. switch - это синтаксический сахар для if. С точки зрения компилятора языка разницы между switch и if-elseif-else нет. Код на C, который считается языком высокого уровня, должен писаться так, как его легче читать (т.е. в данном случае через switch), а задача компилятора сгенерировать эффективное представление в инструкциях проца вне зависимости от стиля записи кода. Статья анализирует насколько хорошо компилятор с этой задачей справляется, и в этом контексте использование switch вполне уместно.
Некорректным было бы, например, сравнивать разные алгоритмы.
slonopotamus
14.07.2023 14:03+4switch - это синтаксический сахар для if
Duff's device с вами не согласен.
powerman
14.07.2023 14:03Кстати, да. "Проваливание" кейсов switch в C по умолчанию - очень не интуитивная фича. Так что правильнее уточнить утверждение "switch в котором все case заканчиваются break - это синтаксический сахар для if". Но по сути же это ничего не меняет, в контексте данного обсуждения, верно?
slonopotamus
14.07.2023 14:03+1В данном случае да. Вообще, на мой взгляд автор слишком рано скатился в ассемблер, явно часть проделанных им манипуляций можно было и в сишном коде провернуть.
nikolz
14.07.2023 14:03+1вот нашел такое объяснение :
Если какой-либо зависимости в значениях 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 — соответствующие подсказки оптимизатору.
Nick_Shl
14.07.2023 14:03+3Всё и так вполне корректно. switch - это синтаксический сахар для if. С точки зрения компилятора языка разницы между switch и if-elseif-else нет.
Удачи вам попробовать в case вместо константы засунуть переменную. Тогда узнаете насколько "switch - это синтаксический сахар для if". switch и if не эквивалентны.
JackKatch
14.07.2023 14:03Меня всегда удивляло непонимание многими инструкции switch. Это не синтаксический сахар, и эквивалентность с if-м существует только при малом (вроде бы до 4-х) количестве вариантов. Как только их больше, проявляется истинная сущность этой конструкции - переход к требуемой ветке за одно сравнение. Если же у вас 10-ть if-в то переход займёт девять операций сравнения в худшем случае. Где же здесь сахар? Принципиально разный подход!
aamonster
14.07.2023 14:03+2Вы тут полагаетесь на конкретное поведение компилятора, которое может поменяться в любой момент. Сегодня switch по разному может обработать, завтра цепочку однотипных if-ов распознает и сведёт к таблице...
Kelbon
14.07.2023 14:03+1эквивалентность с if-м существует только при малом (вроде бы до 4-х) количестве вариантов
в себя слышите? Вы конструкции языка дали определение через реализацию конкретного компилятора.
В целом switch выражает какую то семантику и делает проще что-то для компилятора, но это не значит, что компилятору запрещено переписать его как кучу ифов
JackKatch
14.07.2023 14:03Меня всегда удивляло непонимание многими инструкции switch. Это не синтаксический сахар, и эквивалентность с if-м существует только при малом (вроде бы до 4-х gcc) количестве вариантов. Как только их больше, проявляется истинная сущность этой конструкции - переход к требуемой ветке за одно сравнение. Если же у вас 10-ть if-в то переход займёт девять операций сравнения в худшем случае. Ну что, эквивалентно перейти за одно сравнение или за девять? Принципиально разный подход!
Kelbon
14.07.2023 14:03+2просто напомню, что вообще то С не напрямую в ассемблер транслируется и то что там в коде написано неособо то и важно
Компилятор может переставлять инструкции как ему вздумается, пока поведение программы от этого не меняется
yarston
14.07.2023 14:03+4Без попытки включить pgo тема сишки не до конца раскрыта. Плюс векторные инструкции скорее всего позволили бы значительно улучшить результат, на riscv во всяком случае, этот пример хорошо ложится.
Hixon10
14.07.2023 14:03https://news.ycombinator.com/item?id=36618344 — тут были решения, которые векторизируются компилятором, и все становится сильно быстрее
dllmain
14.07.2023 14:03Никакие pgo(как и "кэши") здесь не помогут.
Плюс векторные инструкции скорее всего позволили бы значительно улучшить результат, на riscv во всяком случае, этот пример хорошо ложится.
Оно хорошо ложится на любой камень с возможностью параллельного исполнения.
vadimr
14.07.2023 14:03+2А если немножко подумать головой, то и ассемблер не нужен.
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; }Условных инструкций внутри глубоких циклов в целях оптимизации лучше вообще избегать, это мешает векторизации.
Собственно, основная уважительная причина для появления условных операторов внутри цикла – это конечный автомат, но его, как правило, не стоит задача ускорять.
thevlad
14.07.2023 14:03+2Вариант с to_add из поста, на моих замерах в два раза быстрее. И он без ассемблера, если перевести в попугаи из статьи дает 3.4 GiB/s
vadimr
14.07.2023 14:03+1На моих замерах вариант с to_add из поста в два раза медленнее приведённого мной выше, благодаря использованию излишней памяти в массиве типа int. Но их конкретная сравнительная эффективность, конечно, зависит от размера кеша L1.
thevlad
14.07.2023 14:03+1Странно, размер L1, уже давно со времен PIII, перевалил за десятки килобайт, но да ладно.
vadimr
14.07.2023 14:03+1У Intel Core размер L1 Data Cache может составлять 32 килобайта, при этом он поделен на 64 блока по 512 байт. Поэтому 512 байт - важный размер для структуры данных.
thevlad
14.07.2023 14:03Насколько я понимаю, это влияет только на ассоциативность в какой-то мере https://coffeebeforearch.github.io/2020/01/12/cache-associativity.html я бы еще понял если речь шла про кэш линии(64 байта).
vadimr
14.07.2023 14:03Практика – критерий истины. На моём Core i3 сокращение размера таблицы с 1024 до 512 байт ускоряет программу вдвое, дальнейшее сокращение до 256 байт (char[]) не меняет время работы.
thevlad
14.07.2023 14:03У меня ровно противоположный результат char и short, в два раза медленнее int, zen 3.
powerman
14.07.2023 14:03+4Вы все молодцы! :) Вы только что личным примером продемонстрировали, почему такими ручными оптимизациями нет смысла заниматься. У компилятора ещё есть шансы учесть такие нюансы при генерации кода для
-march=native, а вот ручками хоть на уровне C хоть на уровне ассемблера этим заниматься практически никогда смысла нет, потому что этот код будет работать на разном железе и оптимизация под одно железо нередко даёт противоположный эффект для другого железа.P.S. А оптимизация на уровне C плюс к этому может давать противоположный эффект на разных компиляторах или версиях одного компилятора.
vadimr
14.07.2023 14:03+1Смотря в чём состоит цель. Если расчёт длится, например, одну либо две недели, то есть за что бороться. Мы же не обсуждаем, почему автор статьи решил ускорить свой цикл.
Недавно мне пришлось консультировать людей по поводу подходов к оптимизации их программы (фортрановской), где в коде, между прочим, была функция, на всякий случай сохраняющая достигнутое состояние вычислительного процесса для возможности перезапуска, и эта функция вызывалась с периодичностью раз в 30 дней. Я был несколько удивлён флегматичностью программиста, но тем не менее.
powerman
14.07.2023 14:03Если расчёт длится неделю-две, то обычно один из подходов "просто подождать, потому что ручная оптимизация кода займёт больше времени чем мы выиграем" или "реализовать возможность распараллелить вычисления на несколько серверов" оказывается предпочтительнее ручной оптимизации под конкретный проц на одном конкретном сервере. При этом параллельный запуск на нескольких серверах резко уменьшает пользу оптимизаций под конкретный CPU, потому что высоки шансы, что на этих серверах процы будут отличаться.
Обычно оптимизировать код становится выгодно тогда, когда финансовые затраты на его выполнение заметно превышают финансовые затраты на его ручную оптимизацию (исход которой к тому же заранее предсказать невозможно). Поэтому по факту оптимизацией кода занимаются тогда, когда финансовые затраты на выполнение кода начинают превышать "допустимые" с точки зрения бизнеса.
А временные затраты обычно оптимизируют горизонтальным масштабированием, что хоть и увеличивает финансовые затраты, но зато масштабируется с одной стороны и сводит вопрос необходимости оптимизаций к ранее решённому (когда финансовые затраты превысят "допустимые").
vadimr
14.07.2023 14:03+2Всё-таки обычно массивные вычисления распараллеливают на одинаковые серверы, потому что иначе увеличение производительности таким образом - вообще малоподъёмная задача. Наиболее широко используемая модель MPI подразумевает (хотя не требует) однородность узлов.
Ну и модель с финансовыми затратами на выполнение несколько наивна, так как обычно в современности не столько стоит денег само машинное время, сколько важно уложиться в сроки работ. Можно, конечно, сказать, что срыв сроков имеет определённую цену, но это применение неподходящего инструмента анализа, так как назначение этой цены неизбежно будет произвольным. Это верно как в макро-, так и в микромасштабе. Каково влияние на стоимость быстродействия программы управления впрыском в автомобильный двигатель, если она не укладывается с расчётами в один такт двигателя? Да нет никакого влияния, такая программа лишена смысла.
А что ещё делать программисту, пока компьютер считает его могучую программу? Как раз и заняться оптимизацией кода.
Если же не стоит задача оптимизировать код, то и нет всех этих вопросов.
powerman
14.07.2023 14:03При использовании облаков (что наиболее типичный кейс для таких вычислений) гарантировать идентичные CPU крайне проблематично.
Бизнес всегда оперирует только деньгами. Сроки важны, но только потому, что срыв сроков стоит денег. Если уложиться в срок обойдётся в разы дороже, чем срыв сроков - обычно бизнес предпочтёт срыв сроков.
Каково влияние на стоимость быстродействия программы управления впрыском в автомобильный двигатель, если она не укладывается с расчётами в один такт двигателя?
Давайте не будем тянуть сюда довольно редкие кейсы Embedded/RTOS, потому что с ними и так всё ясно: там код должен работать и не "как можно быстрее", и не "как получится", а не медленнее минимально приемлемой границы. Это действительно "другое" и в контекст обсуждаемой статьи не вписывается.
А что ещё делать программисту, пока компьютер считает его могучую программу? Как раз и заняться оптимизацией кода.
Нет. Взять следующую бизнес-таску из бэклога.
Если же не стоит задача оптимизировать код, то и нет всех этих вопросов.
Перед бизнесом? Не стоит, как правило. Бизнес хочет заработать денег. Задача оптимизировать код появляется только тогда, когда бизнес видит возможность на этом заработать ещё больше денег.
vadimr
14.07.2023 14:03+3Эти монетаристские мантры крайне ограниченно описывают реальность. Код пишется живыми людьми, как каждому из которых в отдельности, так и их объединениям совокупно, вообще наплевать на прибыль собственника. Я уж лично вырос из того возраста и статуса, чтобы делать вид, что меня интересует ход бизнеса, а не мой личный доход и эстетическое чувство. Хотя могу втирать такие темы про "потребности бизнеса" (как будто это у бизнеса имеются потребности) не хуже.
Чем старее и циничнее вы становитесь, тем больше вещей называется своими именами.
Но можно отметить, что стоимость программного продукта создаётся в том числе и метриками кода, одной из которых является его производительность.
Давайте не будем тянуть сюда довольно редкие кейсы Embedded/RTOS
Это не "довольно редкие кейсы", это одно из направлений моей работы, с одной стороны, и вещь, делающая предметно осмысленной обсуждаемую тему - с другой.
В чём цель вашего участия в дискуссии? Доказать, что обсуждаемый предмет вообще не важен? Тогда, может быть, просто вы находитесь вне контекста обсуждения?
Я, кстати, не слышал ни об одном случае, когда вычислительные задачи выносили бы в облако. По логике вещей, оплачивать стопроцентную загрузку чужого железа банально невыгодно, даже если не вспоминать о безопасности.
powerman
14.07.2023 14:03+1Код пишется живыми людьми, как каждому из которых в отдельности, так и их объединениям совокупно, вообще наплевать на прибыль собственника.
Безусловно. Но есть нюанс. Если этот код пишется в свободное от работы время - можно делать что угодно. Но в рабочее, т.е. оплаченного тем самым никого не волнующим бизнесом, нужно делать то, что просит бизнес. Потому что иначе получается очень некрасивая ситуация: сотруднику платят за одно, а делает он совсем другое, причём осознанно. Если называть вещи своими именами, то эта вещь называется обман (или саботаж, в зависимости от цели и нанесённого ущерба).
Эти монетаристские мантры крайне ограниченно описывают реальность.
А вот с этим я соглашусь. Я тоже не фанат того, что все и всё пытаются выражать в деньгах. Но и обманывать тех, кто платит мне зарплату, я тоже не считаю приемлемым. Поэтому оптимизациями я лично с удовольствием занимаюсь либо в своё свободное время, либо тогда, когда удаётся убедить бизнес в необходимости данных оптимизаций.
В чём цель вашего участия в дискуссии? Доказать, что обсуждаемый предмет вообще не важен?
Он важен, просто в очень ограниченном наборе кейсов. Из которых на мой взгляд самый распространённый - это разработка оптимизаций для компиляторов. А применение этого подхода для ручной оптимизации кода конкретного приложения для запуска на конкретном CPU - на мой взгляд практически не применимо в реальных бизнес-задачах. Буду только рад, если окажется что я не прав, и кто-то приведёт примеры таких реальных бизнес-задач и окажется, что они встречаются намного чаще, чем мне кажется. Цель моего участия в дискуссии - сделать более очевидным этот набор кейсов.
По логике вещей, оплачивать стопроцентную загрузку чужого железа банально невыгодно, даже если не вспоминать о безопасности.
Так она же не стопроцентная. Такого рода тяжёлые вычислительные задачи обычно либо разовые/периодические, либо сильно зависят от заливаемых юзерами данных. В первом случае сервер чаще простаивает чем работает, во втором количество необходимых для обработки данных серверов сильно плавает в зависимости от текущей нагрузки - и в обоих облако обойдётся намного дешевле собственных серверов.
vadimr
14.07.2023 14:03+1Но в рабочее, т.е. оплаченного тем самым никого не волнующим бизнесом, нужно делать то, что просит бизнес.
Не то, что просит бизнес, а то, что приказывает непосредственный начальник.
И, раскручивая по индукции, эта цепочка технических указаний никогда не доходит до собственника при сколько-нибудь значительном размере компании. Хотя каждый провозглашает, что действует в интересах бизнеса.
Буду только рад, если окажется что я не прав, и кто-то приведёт примеры таких реальных бизнес-задач и окажется, что они встречаются намного чаще, чем мне кажется.
Ну вот мы в реальной бизнес-задаче укладывали несколько лет назад умножение векторов в шаг дискретизации сигнала АЦП/ЦАП. Там, помню, были и библиотечные ассемблерные процедуры умножения, и эквивалентные преобразования системы уравнений, чтобы привести данные к используемому библиотекой виду, и распараллеливание руками, и всё такое. Между прочим, единственное, что никак не помогло в достижении цели – это приобретённая платная оптимизирующая версия микроконтроллерного компилятора Си вместо бесплатной не оптимизирующей. Эффект от автоматических оптимизаций был близок к нулю.
Такого рода тяжёлые вычислительные задачи обычно либо разовые/периодические, либо сильно зависят от заливаемых юзерами данных
Обычно, если люди считают скажем, прочность методом конечных элементов, то они постоянно её и считают, для чуть разных условий. В какой-то момент останавливаются в уточнении результата, так как упираются в предел производительности. Если высвобождается дополнительное машинное время – считают задачу более точно, это им позволит с конструкции убрать лишний запас.
vadimr
14.07.2023 14:03
Вот за одну такую ступенечку и надо было успеть выполнить ввод-вывод и все вычисления по всем каналам.
Если не ошибаюсь, тут синий – выходной сигнал прямо на выходе ЦАП, а жёлтый – он же после выходного фильтра.
diakin
14.07.2023 14:03+1Порой можно добиться 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.nikolz
14.07.2023 14:03+1Вот Вы построили код на С на основе if, о чем я и пытался сказать.
Именно так и оптимизировал автор статьи но на асме, подменив case в С, if-ом в ассме.
thevlad
14.07.2023 14:03+2Не очень понятно в чем разница? Компилятор в праве трансформировать семантически эквивалентные конструкции пока это не нарушает стандарт.
datacompboy
14.07.2023 14:03+2До сих пор можно встретить компилятор, в которых
i = i + 2 + 2; i = i + 4; i += 4;Компилируются по разному. Вы считаете, что это разные вещи?
nikolz
14.07.2023 14:03-5каким образом сравниваете?
Если по числу символов в строке , то разные ,
если по результату , то разные ( во второй строке I это не i)
если по области хранения и исполнения, то разные.
первая строка может быть исполнена в памяти, а последняя в регистре. Зависит от описания и от компилятора
В первой строке константа 2, а во второй и третьей константа 4. разное.
На самом деле много неопределенного в этих трех строках, поэтому будет зависеть от описания переменных и способа хранения которые здесь не указаны.
Поэтому ответ неопределенный.
datacompboy
14.07.2023 14:03+4I/i это опечатка, телефон правит за меня.
Так вот, оптимизирующие компиляторы сделают все три одинаково. Потому что итог - и на 4 больше чем до. Побочных эффектов нет.
И компилятор может вообще заменить на константу, выбросив все и пересчитав в процессе.
А тупые компиляторы сделают вычисление 2+2 как отдельно в рантайме и только потом добавят...
nikolz
14.07.2023 14:03-2Вы просто рассуждаете из собственного предположения.
Но Вы ошибаетесь. Ранее я написал, что все зависит от определений и зададаемых параметров компилятору. Можно указать в одном варианте, что переменная в регистре, а в другом что в памяти и компилятор сделает разные вырианты. Можно указать что переменная изменяется из вне, а можно и не указывать. Если дальше переменная не используется, то во втором случае компилятор вообще выкинет это выражение из кода.
Можно указать что 2 и 4 этот константы, в нестираемой памяти и компилятор не заменет 2+2 на 4.
Ну и т д
Поэтому результирующий машинный код непредсказуемый в общем случае.
А попытка обобщить примитивные примеры на все случаи жизни всегда ошибочна, хотя и заманчива.
datacompboy
14.07.2023 14:03+1Расскажите, пожалуйста, как литерал "2" превращается в "константы, в нестираемой памяти"
nikolz
14.07.2023 14:03-3проще вам почитать загрузку исполняемых приложений,например, у Рихтера. Если упрощенно, то в бинарнике (exe) файле есть несколько блоков данных, в том числе и для констант. В мобильных устройствах (тоже Си) , я гружу константы во flash,чтобы экономить RAM.
datacompboy
14.07.2023 14:03+1Расскажите, пожалуйста, как литералу стать константой.
nikolz
14.07.2023 14:03-2Для какого процессора пишите?
datacompboy
14.07.2023 14:03+2Мы тут про язык Си. Это НЕ машино-зависимая особенность.
"2" в тексте кода это литерал. "i+2" выражение оперирует идентификатором i, оператором + и литералом 2. Вы понимаете разницу между константой и литералом?
nikolz
14.07.2023 14:03-3понятна Ваша мысль.
Но можете привести результат оптимизации Ваших примеров компиляторами, c интересом прочитаю.
Остальное лишь Ваше или мое суждение.
datacompboy
14.07.2023 14:03+3Я подозреваю, вы серьёзно так троллите... Но для читателей приведу пример: 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 -- найдите, пожалуйста, разницу, между сгенерированным кодом, хотя на входе -- свич, иф, иф-елзе.
nikolz
14.07.2023 14:03-1вот такой пример, разница на -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
Повторю еще раз, результат работы компилятора непредсказуемый, чем больше код, тем больше будет чудес.
datacompboy
14.07.2023 14:03И что вы хотите мне тут сказать?
Оба случая две двойки схлопнулись в одну четвёрку.
nikolz
14.07.2023 14:03-3Хочу сказать, размер кода асм разный, а оператор С один и тот же.
А чтобы двойки не схлопывались для процессора SOC можно указать,что они во флеш.
Но пусть будет по-вашему, мне все равно.
nikolz
14.07.2023 14:03-2вот пример, в котором код результата изменяется, хотя начальный код функций одинаковый.
попробуйте с разными ключами будет интересно особенно с -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;
}
и не надо кругом видеть заговор.
datacompboy
14.07.2023 14:03+1Я не знаю о каком заговоре идёт речь.
Компилятор имеет право на оптимизации в рамках, заданными стандартом -- где находятся чекпоинты, какие побочные эффекты прописаны и так далее.
Форма (if / switch / и так далее) не является четким определением того, как будет выглядеть итоговый машинный код до тех пор, пока все эффекты эквивалентны исходному коду.
Вы привели пример когда два НЕ эквивалентных исходных кода генерируют различный машинный код. Спасибо, кэп?
Мой аргумент был о том, что два различных исходных кода, использующих разную запись исходника (с if и switch) но выполняющих одну и ту же работу с одними и теми же данными -- являющиеся эквивалентами друг друга -- приводят к эквивалентному машинному коду, что еще раз доказывает, что if и switch эквивалентны (до тех пор, пока они использованы эквивалентно! это не означает, что они эквивалентны всегда).
Исключительно синтаксическое изменение исходного кода не должно приводить к изменениям производительности -- оптимизирующие компиляторы для того и существуют, чтобы это делать.
nikolz
14.07.2023 14:03Вот примеры для сравнения 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)
vitaliy2
14.07.2023 14:03+3Для integer, наверное, одинаковые, для double необязательно (из-за потерь в точности):
double i = 9007199254740991; i = i + 2 + 2; //9007199254740994 i = i + 4; //9007199254740996datacompboy
14.07.2023 14:03+2Подозреваю, что тут зависит от
-funsafe-math-optimizationsименно из-за вопросов точности и допустимости фолдинга
Nick_Shl
14.07.2023 14:03Сложно как-то! Можно в две строчки(не считая скобочек) уместить :)
while(c = *input++) { res += (c == 'p') ? -1 : ((c == 's') ? 1 : 0); }Хотя, конечно, писать такой код неправильно.
Kelbon
14.07.2023 14:03+4Интересно было бы сравнить с этим... На современном С++ так сказать
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'); }thevlad
14.07.2023 14:03+3Там есть существенное отличие, что известен конец строки. Eсли его передавать, то и "вариант на Си", раскочегаривается на векторизацию и simd/sse.
Kelbon
14.07.2023 14:03+1ну посчитайте strlen, может так выйти что всё равно будет быстрее
thevlad
14.07.2023 14:03+1У меня получилось где-то на 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 раза быстрее
0xd34df00d
14.07.2023 14:03+1Неизвестный конец строки отлично векторизуется в таких задачах с SSE 4.2 и pcmpistr.
thevlad
14.07.2023 14:03Автоматически? Нет даже банальный "while (*it != '\0') ++it;" не векторизуется.
dllmain
14.07.2023 14:03По большому счёту да, автоматически. Нужно только немного помочь компилятору. while(*it) - здесь сказано "до нуля и не далее". Там нечего параллелить.
thevlad
14.07.2023 14:03Речь шла о команде sse через, которую можно потенциально векторизовать данный цикл, эквивалентный strlen. (там в конце вычитание из начального указателя очевидно)
dllmain
14.07.2023 14:03Ничего не понял, честно говоря. Во первых, sse/не sse - здесь никакой роли не играет. Любая возможность железа параллельно исполнять код здесь так же будет работать.
Во вторых, я отвечал на вот это:
Автоматически? Нет даже банальный "while (*it != '\0') ++it;" не векторизуется.
Я указал на то, что это векторизуется "автоматически", будь оно не так топорно записано. О причинах не-векторизации я также сообщил. Команда sse никакого отношения к делу не имеет и просто является частным случаем, не более.
Panzerschrek
14.07.2023 14:03Вариант с двумя std::count плох тем, что требует двукратного чтения строки, что может быть накладно для хоть сколько нибудь длинных строк (не вмещающихся в кеш-линию). Такой вариант наверняка кратно медленнее оригинала.
Kelbon
14.07.2023 14:03не наверняка, даже замеры сделали и это быстрее. Потому что каждый проход будет в разы быстрее
Tuxman
14.07.2023 14:03+2В C++20 завезли
[[likely]]и[[unlikely]]. Так то buildin были и в GCC, и в Clang, например__builtin_expect. Если я знаю заранее, что у меня тут happy-path, или как-то заранее знаю, что чаще всего случится, то пишу likely, и даже в ASM не заглядываю. Другое дело, сможет ли компилятор векторизовать. Вот тут, желательно глянуть в ASM, и разными конструкциями, заставить компилятор сделать как надо.dllmain
14.07.2023 14:03+1Префы здесь ничем не помогут. Пока есть return в цикле уровень параллельности околонулевой.
Tuxman
14.07.2023 14:03+1Никогда не говорит нет. Проверяй свой код на https://godbolt.org с trunk компилятором, они всегда работают над улучшением.
mir546
14.07.2023 14:03+1Интересно кто-нибудь уже ваяет компилятор на нейронных сетях чтобы получать оптимальную оптимизацию словно сделана вручную...
iliazeus
14.07.2023 14:03
vasapap
14.07.2023 14:03Не то, но ai сам лезет в ассемблер https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
dllmain
14.07.2023 14:03+8Не увидел ни в статье, ни в комментариях хотя бы намёка на производительность. Написал вам минимально адекватный бенч.
#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 раз. Заморачиваться на каких-то крополях мне лень.
powerman
14.07.2023 14:03-3Зато с читабельностью этого варианта просто беда…
Для чего вообще нужен
rs? Почему не заменитьrs[n] = i[n] ? 0 : ~0наif !i[n] { return r + step_r }?dllmain
14.07.2023 14:03+3Читабельность здесь мимо по большому счёту, поскольку целью заявлялось "быстрее". А так, это борьба с компилятором(и отчасти с 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, как в начале статьи.
powerman
14.07.2023 14:03А за счёт чего выигрыш? Цикл по 128 байт внутри которого ничего кроме арифметики нет позволяет компилятору использовать AVX?
dllmain
14.07.2023 14:03+1Ответил на подобный вопрос чуть ниже. В целом, да - нужно дать компилятору/железу возможность генерировать/исполнять параллельный код. if/return/ещё какие-то ветвления - в общем случае этому препятствуют.
vadimr
14.07.2023 14:03+2Отличные замечания. Идея, как я понял, в том, что мы гарантируем выполнение основного цикла ровно 128 раз, и за счёт этого можем использовать векторную операцию?
dllmain
14.07.2023 14:03+2Идея в повышении уровня параллельности кода насколько это возможно. "скалярный"(с уровнем параллельности ~0) код всегда будет медленным. И компилятор ничего с этим сделать не сможет. Вот нормальный код ни компилятору, ни железу не мешает. Не имеет лишних зависимостей по данным/интсрукциям.
128 или нет - это не важно. Если проще - нужно более одного. Даже сильно более. На самом деле я там забыл вернуть обратно на 64 и именно со 128 там будет переполнение на "sssss...". Но сути это не меняет.
ermouth
14.07.2023 14:03+1Тут критика из Тви подъехала, что скажете?
thevlad
14.07.2023 14:03+2Так и есть, внутренний цикл, ожидает кратность массива 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, но компилятор самостоятельно так вряд ли умеют.
dllmain
14.07.2023 14:03+1Я вам уже выше отвечал на ваши заблуждения про "векторизация"/"strlen"/"автоматически"/"команда sse" и прочее.
А так, вопросы для вас ниже. Расскажете мне про чтение за '\0' и что мне помешает это делать.
thevlad
14.07.2023 14:03Чтение за \0 это UB, очевидно, если вы выделили память ptr = malloc(1000000), то последний указатель это ptr + 1000000, а не ptr + 1 000 047. Не помешает, как и с любым UB, все будет работать чисто случайно на некоторых входных данных и условиях.
Вы упомянули strlen выходящий за пределы массива из glibc, может быть покажете, а то я в его коде этого не увидел?
dllmain
14.07.2023 14:03+1В общем, мне эти споры на "кому раньше надоест" мало интересны. Рассказываете про "падает" - показывете. Вы это говорили прямым текстом, эксперт из "тви" также это заявлял. До тех пор пока нет падения - в сотый раз слушать "это же ub, как ты можешь отрицать!!!" - это всё мимо.
Изучите хотя бы базовые принципы работы памяти. Там про страницы и прочее(что вы успели нагуглить чуть ранее). Далее уже будете рассуждать.
thevlad
14.07.2023 14:03+2Конечно, я нагуглил, вы лучше сами погуглите, что такое UB, а то видимо еще нет. Ваш код - UB, и то что он не падает, лишь счастливая случайность страничной организации системы памяти.
dllmain
14.07.2023 14:03-3Ну что можно сказать. Фиксируем. Персонаж действует по обозначенной мной схеме - надеется что мне просто надоест отвечать.
Опять пошли заходы про "счастливая случайность", хотя я уже отвечал на это и оказалось вероятность "счастья" - 100%. Никакого ответа на это не последовало и не последует. Также фиксируем.
Про "нагуглил" - это очевидный факт, потому как зная хотя бы базовые принципы организации памяти рассуждать вот таким образом:
Собственно в этом и вся соль задачи, без векторизации strlen это все бесполезно, а сделать ее автоматически довольно сложно, так как нет гарантии за выход за границы null terminated string, если шагать по размерности simd регистра.
просто невозможно. Поэтому данный персонаж ничего не знал, а теперь погуглил, осознал свою неправоту и сейчас пытается съехать с темы на различные абстрактные понятия типа ub и стандарта.
thevlad
14.07.2023 14:03Так давайте по простому. Ваш код это UB, Да или Нет?
А то эти детские наезды, уже немного поднадоели.
dllmain
14.07.2023 14:03-3Давайте по простому. Мой код падает, Да или Нет?
А то эти детские наезды, уже немного поднадоели.
thevlad
14.07.2023 14:03Код не падает, на некотором распространенном конечном наборе платформ и компиляторов. Но при этом он очевидно является 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.
dllmain
14.07.2023 14:03-3Код не падает
Утверждалось обратное - показывайте, либо признавайте что врали. До этого момента все заявления мимо.
на некотором распространенном конечном наборе платформ и компиляторов.
В студию набор на котором падает.
Так что да: ваш код не падает, но является явным UB.
Персонаж расписался в своей(и того твиттер-эксперта) лжи. Молодец. Теперь ваша задача показать, что следует из этого ub. Ведь если оно никак не влияет на поведение, да и вообще никак не наблюдается - оно ничего не значит и его нет. Там чайник какой-то модный одно время на орбите летал - вот это то самый случай.
Таких обнаглевших спамеров нечасто встретишь. Опять же, радостные вести для подобных персонажей - любой "перегиб" с моей стороны - и я теряю возможность отвечать(бан/минуса). Удобно.
0xd34df00d
14.07.2023 14:03+1Быстрый квадратный корень из кваки тоже до поры до времени работал, а потом clang стал его оптимизировать в noop.
ermouth
14.07.2023 14:03+1Как такое вообще может быть? Источник байки не подкинете, а то я уже 10 минут гугл насилую безрезультатно.
0xd34df00d
14.07.2023 14:03+1Так как я даю ссылку на старую версию хабра, если у вас не проскроллится к нужному комментарию, то просто поищите по странице по
0x5f3759df.
ermouth
14.07.2023 14:03Ох, попробовал даже на сях, оно и правда с clang 14 генерит рабочий код только с -O0, причём в отличие от более ранних версий код совсем плохой, из xmm в eax пересылки низачем, всё вот это.
Красотец, спасибо!
dllmain
14.07.2023 14:03Такое может быть по одной причине - это оправдания и к реальности отношения не имеет. Эксперт протирает штаны уже кучу лет, а тут бам - кто-то показывает новый трюк.
Далее у эксперта два пути: либо признать своё непонимание(и похоронить себя как эксперта), либо начинать придумывать разные отмазки.
Особенно мне нравятся оправдания, которые никак не проверяются - там что-нибудь про будущее(кстати, насколько далёкое?), про новые версии компиляторов(о которых эксперт ничего не знает), квантовые вычисления и прочее. Не нужно на это ловится.
ermouth
14.07.2023 14:03Не нужно на это ловится
Да я не ловлюсь, у меня восприятие таких штук эмм феноменологическое. Пример Дэдфуд кстати привёл занятный.
Я, к счастью, на сях пишу может раз-два в год ради домашних экспериментов, всё тут же при мне компилится/исполняется, и, в общем, я бы стал делать как вы – но не 128, конечно, а 8 – потому что мне это сразу без объяснений понятно.
Что, в общем, вполне соответствует условиям задачи: вот прямо здесь и сейчас выдавить всё что можно – при имеющихся текущих вводных, без всякой ерунды типа «а вдруг через год не заработает».
Но такой код, абьюзающий ub, распространять я бы стал только в качестве примера-демонстрашки.
У меня эта позиция, в общем, только сейчас чётко сформулировалась, спасибо вам за это )
dllmain
14.07.2023 14:03Да я не ловлюсь, у меня восприятие таких штук эмм феноменологическое.
Я, к счастью, на сях пишу может раз-два в год
к счастью
Ну вот, видите - вас уже убедили в некой сложности C. UB пропаганда - это меинлайн подобной методички.
Причём в целом, да - писать на C(нормальный код, а не хелворды) действительно сложнее. Но в случае не-хелворда - выбора-то и нет. Никакой иной язык не позволяет настолько же эффективное исполнение. Остальное просто пыль и мы все сидели бы сейчас на калькуляторах, если бы не C и решения из C-мира.
я бы стал делать как вы – но не 128, конечно, а 8 – потому что мне это сразу без объяснений понятно.
Ну 8 там мало будет. 32/64 - это уже нормально. На 16 авось оно что-то сможет.
Но такой код, абьюзающий ub, распространять я бы стал только в качестве примера-демонстрашки.
Опять же, нет. Оно не абузит ub, оно абузит матчасть, с которой у многих дела обстоят неважно. UB - понятие стандарта и появилось оно там из-за того, что:
стандарт не может оперировать конкретными условиями - это абстрактное описание
всегда легче написать "вот за это мы никак не отвечаем" чем пытаться как-либо описывать реальность
А в реальности конкретно здесь есть только железо/память, котороя работает так, как работает. Никакие стандарты и прочее железо не волнуют.
ermouth
14.07.2023 14:03А в реальности конкретно здесь есть только железо/память, котороя работает так, как работает
В этой конкретной задачке в этой конкретной постановке – ну да.
Но в моей например реальности если я компилю какой-то сторонний (не мной написанный) код на сях, таргетом скорее всего будет wasm. И оно почти наверняка не заработает с произвольной длиной строки ни с каким степ-сайзом больше 4. Потому что wasm просто не даст читать за границами строки, он проверки за вас сделает по-любому, а буферы он выделяет кратно 32 битам. Проверю на досуге.
Ну вот, видите - вас уже убедили в некой сложности C.
Да бросьте, я в нынешней терминологии дед, меня поздно убеждать. В моей вселенной уже давно если надо быстро – то С, если прямо совсем распределёнщина – Erlang, всё остальное – JS норм. Ну сейчас вот Питон ещё добавился для всякого с ML.
0xd34df00d
14.07.2023 14:03+1О, реально царь, явление десятое.
там что-нибудь про будущее(кстати, насколько далёкое?), про новые версии компиляторов(о которых эксперт ничего не знает)
Ровно все эти вопросы можно было бы задать лет пять назад про быстрый корень, когда не существовало компиляторов, «неправильно» его обрабатывающих. А потом вышла версия clang, которая его ломает, и код таки стал неправильно работать.
Мне не нужно указывать конкретную дату и время релиза компилятора, ломающего конкретное ub. Мне достаточно показать, что это будущее на самом деле наступает для некоторого (и неизвестного заранее) подмножества ub. Попытки в ответ на это проехаться демагогией про «а насколько далёкое будущее?» — это не более чем демагогия.
Хотите получить максимальную производительность без привязки к поведению конкретного компилятора? Пишите на ассемблере.
dllmain
14.07.2023 14:03-2царь
В школу слёту.
Ровно все эти вопросы можно было бы задать лет пять назад
Не, отсылки на что-то иное - сразу мимо. Были заданы конкретные вопросы, в том числе главный из них ниже.
Попытки в ответ на это проехаться демагогией про «а насколько далёкое будущее?» — это не более чем демагогия.
Классика - сектант всегда попытается приписать оппоненту свои свойства. Ведь демагогией является именно необозначение сроков - и тогда всегда можно сказать "ну просто время ещё не пришло" и так до бесконечности. Но наш герой получил плохую подготовку(или просто охренел, что более вероятно) и назвал "демагогией" обратное.
В целом, спорить с данным персонажем смысла никакого. Его мотивация очевидна - он спутал меня с царём и далее просто побежал мстить и гадить. А так как сам персонаж нигде и никак не состоялся - мы имеем то, что имеем: максимум болтовни и ноль кода. А болтовня меня не интересует.
dllmain
14.07.2023 14:03Это основное. Ваша задача показать, каким образом приведённый код можно "оптимизировать" и вызвать этим проблемы. Без этого подобные рассуждения ничего не стоят.
datacompboy
14.07.2023 14:03+3Да, код падает.
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
dllmain
14.07.2023 14:03Вы бы хоть посмотрели, из-за чего именно он падает. Ну да, ладно, допустим вы далеки от C.
Я там после for head_end забыл вписать if (!*i) return r; - это не то, о чём говорили ub-персонажи.
datacompboy
14.07.2023 14:03+1А я посмотрел. Однако же просьба была вызвать падение в коде, вызванное UB от обращения позади нуля. Я вызвал? Вызвал. Оно упало из-за обращения к следующему после выравнивания. Да, на современных архитектурах, вызвать падение "на пальцах" можно только в этом месте.
Остальной код лезет в лишние места, но только в пределах выровненных 128 байт. То есть вызвать проблему всё еще можно -- напрмер, в случае обращения к какому-либо устройству через MMIO если дёргать не поддержанные адреса.
Еще можно получить шар с волосами на архитектурах где размер страницы меньше 128 байт.
Еще можно напороться на параноидальный гипервизор, контролирующий доступ в пределах субстраниц.
Исправленный код допустим даже в продакшен (и даже я бы принял его с подавлением санитайзера в этом случае) но только при условии комментария и инит-теста что размер страницы больше 128.
dllmain
14.07.2023 14:03Однако же просьба была вызвать падение в коде, вызванное UB от обращения позади нуля.
Неверно. Задача была вызвать падение из-за широкого чтения позади нуля. Вы показали пропущенный return, который не имеет отношения к делу. Вам следует изучить тему для начала, а далее уже отвечать. Какие-то ассоциации из подкорки вроде "и там после 0, и там после 0 - значит это одно и то же" - сразу мимо.
То есть вызвать проблему всё еще можно -- напрмер, в случае обращения к какому-либо устройству через MMIO если дёргать не поддержанные адреса.
Ну фантазии меня мало интересуют. Это нужно показать.
Еще можно получить шар с волосами на архитектурах где размер страницы меньше 128 байт.
Куллстори. Архитектуру в студию. Ну кстати, я верно задетектил абсолютное непонимание, ведь это 128 - от него ничего не зависит и это можно менять.
Еще можно напороться на параноидальный гипервизор, контролирующий доступ в пределах субстраниц.
Ога.
Исправленный код допустим даже в продакшен
Боже, эти откровения. Рассказывали про кучу проблем, а теперь бам - оказывается можно тест бахнуть и всё сразу же становиться нормально.
А в целом да - код работает, а все перечисленные "проблемы" - просто фантазии, даже тест не нужен.
ermouth
14.07.2023 14:03+1это всё мимо
А вдруг у вас найдётся час-другой написать про это материал? Было бы круто, иллюзии по этому поводу прямо массовое явление, там в тви чёрте-что творится.
dllmain
14.07.2023 14:03Я не особо писатель - так, в свободное время в коменты заглянуть. А если интересует почитать - можно сходить в телегу царя(proriv_zaparti) - там про это уже куча всего написана. Да и не только про это. Один момент - немного специфично написано, не нужно пугаться.
0xd34df00d
14.07.2023 14:03+3Чтение за \0 это UB
Средствами языка (например, напрямую, или кастуя указатель на char к указателю на uint64_t и читая сразу 8 байт) и за границами массива — да. Средствами интринсика — нет.
Если бегать по массиву выровненно по 16 байт (размер xmm-регистра), то вы даже на потенциально неаллоцированную страницу не попадёте, и ничего страшного не будет ни с точки зрения стандарта языка, ни на практике.
Разбираться, впрочем, к какому из подмножеств относится код вашего собеседника, мне лень, я сишки наелся на обозримое будущее.
dllmain
14.07.2023 14:03+2Тут нечего особенно говорить - обычный "ньюфаг", который где-то услышал про санитайзеры и ub. Только вот ему не рассказали про ложные срабатывания этих санитайзеров. Схема типичная - где-то что-то увидел, ничего не понял и побежал срывать покровы.
А по поводу ub, открою секрет, но ничего не мешает читать далее '\0'. Поэтому данный эксперт идёт сначала смотреть код strlen/memchr/прочих функций из glibc, а далее начинает отрывать себе руки и всё остальное(ну это его желание, что поделать).
В общем, условия просты - для обоснования ub эксперту нужно сообщить что мне помешает читать память далее '\0'. А также что мешает делать тоже самое glibc. Всё просто.
Ах да, я как-то даже не сомневался. Если кому-то интересно, мотивация данного эксперта:
Это очередной адепт того самого языка программирования(который убийца c/++, да). Ладно, я не буду рассказывать здесь, что это за адепты и в чём их суть, а то меня забанят за пару минут.
thevlad
14.07.2023 14:03+2Что значит не мешает? У вас индексы вылетают за пределы массива, это все не падает только по счастливой случайности, так не влезает на границу страницы.
Да, и код ваш мягко говоря "переусложнен", если знать размер массива, или иметь гарантии, что он кратен размеру 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 из стандартной библиотеки раскочегарен по полной.
dllmain
14.07.2023 14:03+2У вас индексы вылетают за пределы массива, это все не падает только по счастливой случайности, так не влезает на границу страницы.
Ога.
не влезает на границу страницы.
Суть. И да - "случайно" - покажете мне падение?
Да, и код ваш мягко говоря "переусложнен"
Это оправдания. Ваш не переусложнённый код выдаёт выдаёт перф - внимание - 5 Gib/s. Это сильно.
потому что strlen из стандартной библиотеки раскочегарен по полной.
Потому что написан знающими людьми, а не вчерашними студентами, которые узнали вчера про -fsanitize из гугла.
dllmain
14.07.2023 14:03+1Ну и да, ответ за glibc strlen и прочее - где он? Почему проигнорировали? Это другое? )
thevlad
14.07.2023 14:03Суть. И да - "случайно" - покажете мне падение?
Отлично, если вы скажите, что ваш код работает только по одной причине: потому что не происходит пересечения границы страницы, хотя с точки зрения стандарта это очевидное UB. На этом мы договоримся.
dllmain
14.07.2023 14:03+1Что значит договоримся? Вы рассказывали про "падает" - показать не смогли, оказалось ничего и никогда не падает. Теперь начали рассказывать про какой-то стандарт и в целом пытаться съехать с темы.
С болтунами договориться невозможно по определению, поскольку договор основывается на том, что слова соответствуют реальности. Ваши не соответствуют. Какие ещё "договоримся", боже.
thevlad
14.07.2023 14:03Вы вообще в курсе, что отсутствие UB, в общем случаи невозможно доказать, конечным количеством тестов, на конечном наборе конфигураций? Пока, что на наиболее распространенных платформах, и версиях компиляторов "не падает".
Но в данном случаи вы даже не отрицаете, что происходит выход за пределы массива, это очевидно. Выход за пределы массива, по стандарту это UB.
На этом можно разговор заканчивать, потому что вы видимо из тех, кто начинает верить в UB. Только когда начинает падать, на какой-то следующей версии компилятора или другой аппаратной платформе.
dllmain
14.07.2023 14:03+1Так, заспам про "ub" будет продолжаться до последнего. Но тут интересно другое:
Вы вообще в курсе, что отсутствие UB, в общем случаи невозможно доказать, конечным количеством тестов, на конечном наборе конфигураций?
И вот данный персонаж(а также твиттер-эксперт) пытаются требовать с меня именно эти доказательства. Это совсем нелепое позорище. Т. е. именно они должны доказывать наличие этого ub/падает/прочее. Но пока не получилось(и далее также не получится).
Но в данном случаи вы даже не отрицаете, что происходит выход за пределы массива, это очевидно
Совсем заврался. Выход я нигде не отрицал, я отрицал негативные(да и вообще хоть какие-либо наблюдаемые) эффекты этого выхода. Ой, персонаж запутался в элементарной логике. Ну ничего, бывает.
В общем, хотите поиграть в дурачка - это не ко мне. Ко мне приходите вместе с коркой от упавшей функции.
thevlad
14.07.2023 14:03-1Т. е. именно они должны доказывать наличие этого ub/падает/прочее. Но пока не получилось(и далее также не получится).
Так это вы и пытаетесь доказать отсутствие UB, предоставляя конечный набор тестов. Любой конечный набор тестов не является доказательством отсутствия UB. В данном случаи, корректная работа конечного набора тестов, и является частным случаем UB.
Наличие UB, можно доказать основываясь на аналитические построения стандарта. В данном случаи мы очевидно имеем выход за пределы массива, выход за пределы массива - является UB. Так что совсем не понятно с чем вы спорите.
Адекватный подход: это признать, что код является UB, но при этом работает на некотором распространенном наборе компиляторов и платформ. Это так и есть, и с этим спорить бессмысленно.
dllmain
14.07.2023 14:03Так это вы и пытаетесь доказать отсутствие UB, предоставляя конечный набор тестов.
Неверно. Вы говорите есть ub - показываете его и последствия этого ub. Нет последствий ub - нет и самого ub. Всё просто.
thevlad
14.07.2023 14:03-1Вы видимо довольно плохо знаете историю. Негативные проявления UB, появлялись и просто с выходом следующих поколений, более умных компиляторов. Не падает - это не аргумент, против UB, по крайней мере в приличном обществе. UB очевидно есть, то что вам не могут предъявить падения при некоторых конфигурациях абсолютно ничего не доказывает. Добавьте по меньшей мере -fsanitize, упадет. Но для вас это тоже не аргумент. )
datacompboy
14.07.2023 14:03Program received signal SIGSEGV, Segmentation fault. 0x0000555555555097 in _run_switches (i=0x555555559ff8 <c+8120> "") at a.c:24 24 rs[n] = i[n] ? 0 : ~0;Могу и корку прислать если интересно, но вы легко можете и повторить падение.
dllmain
14.07.2023 14:03Как уже отписался - это мимо. Не то падение. Я там отписал, как это правится.
vadimr
14.07.2023 14:03Тут надо бы начать с того, что, ни из чего не следует, что UB само по себе – это что-то плохое. Плохо, когда от него ожидается какое-то конкретное поведение. А в данном случае нас устраивает любое поведение с точки зрения семантики языка Си.
thevlad
14.07.2023 14:03-1Довольно известная шутка, что UB может запустить форматирование диска. В случаи UB никакой семантики нет, есть только везение, или очень большое невезение. В данном случаи мы опираемся на простой факт, что доступ будет происходить в границах валидной страницы. При этом очевидно происходит доступ за границы массива. В самом плохом и неудачном случаи, компилятор может просто сломать код основываяась на том, что UB теоретически возможна, и будет абсолютно прав.
vadimr
14.07.2023 14:03Это неправильная шутка. UB с точки зрения стандарта языка Си означает только то, что конкретный результат выполнения операции не выводим из требований стандарта. Когда мы обращаемся с чтением к элементу массива за его границами, то не можем исходя из стандарта предсказать, какое в точности значение получим. Именно этот факт и обозначается термином UB.
То, что результат операции представляет собой UB, само по себе не означает, что эта операция запрещена или не имеет определённого результата вообще.
А страницы и всякие сегфолты – это понятия машинного языка, а не Си. И с точки зрения машинного языка поведение программы в данном случае вполне определено.
thevlad
14.07.2023 14:03У нас очевидно разные стандарты:
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
vadimr
14.07.2023 14:03По-моему, тут написано именно то, что я написал.
... поведение, в результате использования непортабельного или ошибочного кода или ошибочных данных, в отношении которого данный стандарт не предъявляет требований...
thevlad
14.07.2023 14:03Нет, я конечно могу и перевести:
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, может привести как минимум к завершению программы в лучшем случаи, а в худшем нарушение констинстентности внутреннего состояния с произвольными последствиями.
vadimr
14.07.2023 14:03Не любое UB может привести ко всем этим бедам, а возможны UB, приводящие к каким-то из них. Но стандарт, как написано выше, не предъявляет требований, поэтому это просто примеры.
thevlad
14.07.2023 14:03А откуда вы знаете, какие UB приведут к каким бедам?
Со временем компиляторы становятся умнее, и там где раньше UB код работал "предсказуемо", появляются оптимизации, способные привести к "произвольному" поведению.
vadimr
14.07.2023 14:03Ну всё правильно, результат операции не определён в стандарте. Это и есть UB. Он, тем не менее, вполне конкретный в каждой реализации.
Между прочим, современный компилятор не содержит таких странностей.
thevlad
14.07.2023 14:03Самая большая проблема с UB, что с ними как в математике, из ложного утверждения можно вывести, что угодно. Так же и компилятор может исходя из утверждений отсутствия UB, вывести что угодно. К примеру, просто удалить ненужный по его мнению код, как к примеру здесь:
https://eyalitkin.wordpress.com/2016/10/12/integer-overflow-undefined-bahavior/
Первой операции проверки просто нет, она оптимизирована.
vadimr
14.07.2023 14:03В некоторых языках, кстати, выход за границы массива можно явным образом разрешать (PL/I, Ада, новый Паскаль, старый Фортран).
У меня в работе однажды была программа, содержащая некую заимствованную процедуру кодирования данных для передачи в канал связи, написанную в древнейшие времена на Фортране и позже переведённую её автором на Паскаль. Эту процедуру в целом совершенно невозможно было понять, так как она представляла собой лапшу из goto и односимвольных имён переменных. Факт, однако же был в том, что, если разрешить контроль за границами массива, то она падала, а если запретить, то работала нормально. Я проследил её алгоритм и выяснил, что там в определённых условиях перед окончанием работы берётся лишний элемент массива, но никак потом не используется в результате. Так эта процедура до сих пор и работает, уже лет 40 или 50, наверное.
thevlad
14.07.2023 14:03Самая большая проблема с UB, это то что компиляторы становятся умнее, и даже на той же платформе, код скомпилированный значительно более новым компилятором перестает работать из-за UB. Это я сам наблюдал и не раз.
0xd34df00d
14.07.2023 14:03+2означает, что эта операция запрещена или не имеет определённого результата вообще.
Именно что означает. Компилятор вправе вообще вырезать функцию (и все вызывающие её функции транзитивно), если докажет, что все пути выполнения через неё вызывают UB.
vadimr
14.07.2023 14:03+1Всё ядро операционной системы, например, построено на разыменовании указателей, сконструированных из целых чисел, и других подобных вещах, являющихся несомненным UB. Просто потому, что в абстрактных категориях с аппаратурой работать невозможно.
Компилятор вправе не компилировать машиннозависимый код?
dllmain
14.07.2023 14:03Не, это ни на что не повлияет. Там нет какого-то непонимания, что такое ub, и прочего. Т. е. это не ошибочное мнение, а просто попытки как-то оправдать свой положение. Эксперты сидят с 4-5 Gib/s, да и даже это они также спастили, а не написали сами. И тут вдруг кто-то показывает нормальный перф - далее всё просто: либо все понимают, что за гуру оптимизации здесь обитают, либо эксперты придумывают тысячи оправданий своей некомпетентности.
А поскольку стандарт - максимально абстрактная байда, легче всего рулить именно туда, ведь никак это проверить нельзя. Там вон выше(или ниже) дошли до размера страницы памяти < 128 байт, а вот где-то там(квак) что-то поломалось спустя долгое время, ну и конечно же, агитка про "отформатировать диск"(это совсем позор, ведь никакого форматирования не было зафиксировано ни разу).
qw1
14.07.2023 14:03это совсем позор, ведь никакого форматирования не было зафиксировано ни разу
Синтетический пример наделал много шуму, и теперь все его вспоминают со словами "а ещё ваш UB форматирует диски".
http://kristerw.blogspot.com/2017/09/why-undefined-behavior-may-call-never.html
vadimr
14.07.2023 14:03Честно говоря, не понимаю удивления этих людей. Чего конкретно они ожидали, передавая управление по неизвестно чем заполненному адресу? Даже если, допустим, они рассчитывали получить jmp 0, то почему бы по адресу 0 не находиться как раз коду EraseAll? (Хотя механизм в данном случае другой, но тем не менее).
qw1
14.07.2023 14:03+1Они ожидали, что segfault будет защитой от случая, когда callback не инициализирован, и видимо, это их устраивало.
nikolz
14.07.2023 14:03-2Взял произвольную строку в 23800 байт и компилятор pocc.exe OC Windows
Получил скорость для первого кода 1160 MiB/s, в статье 295 MiB/s
а для кода с таблицей 2.0 GiB/s, в статье GCC: 1.98 GiB/s
dllmain
14.07.2023 14:03-3Смотрю минуса уже начинают подъезжать. Видимо группа поддержки набигает. Поэтому отмечу ещё один момент и пойду. В чём суть "аргументации" твиттер- и прочих экспертов, - UB. Но что характерно, именно то ub, которое имеет последствия и искажает результат работы функции эксперты не нашли. Это переполнение при step_size = 128, которое я не убрал. Я сообщал здесь об этом ранее.
А вот "false-positive UB" они нашли. Ну как нашли - путили санитайзер и оно им нашло. Сами они не нашли бы даже этого. Я ожидал подобных заходов почти мгновенно, но почему-то их не последовало, я даже удивился немного. Только спустя полдня адепт известно какого ЯП что-то там нагуглил. Удивительные эксперты.
Ладно, резюмируя(для неофитов в первую очередь, но не только для них) - код дан, любой может взять и проверить - это одна из фишек программирования по сравнению с большинством остального - всё довольно просто проверяется. Берём мой код - перф на уровне, берём код из glibc - перф на уровне, берём код экспертных экспертов - ой, сливает раз в несколько раз. Рассказывали про падения - не нашли, начали рассказывать про ub - оказалось это "ложное" ub и ни на что оно не влияет. Далее совсем поломались и начали просто заспамливать меня как боты "это ub", "это ub", "это ub" - надо же как-то оправдаться в глазах общественности. Ну так бывает, когда ты эксперт из твиттера/адепт некого ЯП/ещё какой-то 25 эшелон.
datacompboy
14.07.2023 14:03+1Если вы любите прыгать в стог сена с вилами в нём и ни разу не напоролись на них -- не повод рассказывать что опасность вил забытых в сене преувеличена.
dllmain
14.07.2023 14:03-1Похоже вы решили со мной поиграть в эксперта. Хорошо. Падение из-за того UB, о котором говорили из твиттера и здесь - в студию. Обоснование за попытки манипулировать, предоставив падение, которое к делу не относится - так же в студию.
DirectoriX
14.07.2023 14:03Такой код падает:
исходник
#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)dllmain
14.07.2023 14:03Для начала нужно почитать тему, а уже потом бежать срывать покровы. Где if, про который я говорил? К тому же он очевиден, если пытаться читать код, а не просто пустить, получить левое падение, ничего не понять и бежать рассказывать истории.
DirectoriX
14.07.2023 14:03-1Для начала нужно вспомнить, что безопасно кастовать указатели можно только между чемто*, void* и char*, а кастование между чемто* и чемтодругим* (как у вас - long long int* и unsigned char*) - UB. Заметьте, gcc ругнулся даже без включения дополнительных проверок.
Кстати, вы уверены, что ваш long long int и мой long long int будут одного и того же размера? Стандарты C очень интересны, они определяют только нижний размер типов.
dllmain
14.07.2023 14:03Новые откровения подъехали. А чего проигнорировали всё и свичнулись на новую тему? Рассказывали про падает, а оказалось не падает. Чего так?
dllmain
14.07.2023 14:03-1Что-то эксперт так уверенно рассказывал и так быстро куда-то пропал. Ну это типично.
Просто для протокола:
безопасно кастовать указатели можно только между чемто*, void* и char*
а кастование между чемто* и чемтодругим* (как у вас - long long int* и unsigned char*) - UB
Даже здесь засыпался, даже в области стандарта(который эксерт не читал и знает о нём из историй в интернете). Сообщу новость - signed/unsigned варианты одного и того же базового типа алиастся без ub.
DirectoriX
14.07.2023 14:03Здравствуйте, примите глубочайшие сожаления в связи с невозможностью написания ответа в течение 1 (одной) минуты после того как Вы написали свой.
signed/unsigned варианты одного и того же базового типа алиастся без ub.
Хочу напомнить, что char'ов в стандарте есть аж три, и безопасно кастить только в обычный char, без указания знаковости. То есть если бы у вас был
char rs[step_size];- было бы стандарто-допустимо.dllmain
14.07.2023 14:03-4Попытался рассказывать про что-то, не смог - начал играть в большого дядю - подобные персонажи очень любят строить из себя кого-то. Но да ладно.
Хочу напомнить
Как там с падением, уже получилось? Нет? Ну идите погуглите. Или уже погуглили?
В общем, похоже это очередной бот.
qw1
14.07.2023 14:03Для начала нужно вспомнить, что безопасно кастовать указатели можно только между чемто, void и char, а кастование между чемто и чемтодругим (как у вас — long long int и unsigned char*) — UB
Вы чего-то недоговариваете, потому что в такой формулировке из стандарта надо убрать
reinterpret_castDirectoriX
14.07.2023 14:03+1Не припомню чтоб в C был
reinterpret_cast, это же C++ное. Но и в C++ нельзя разыменовывать указатели послеreinterpret_cast(кроме очень отдельных случаев).Если вы хотите сделать не-UB-шно, то в C надо использовать
union, а в C++ -std::bit_castqw1
14.07.2023 14:03std::bit_cast
Ох, с этими новыми стандартами опять старый код переписывать ))
Ну кстати, если
MyStruct*нельзя вAnotherStruct*но можно вchar*и обратно, то выходит так можно?MyStruct* myStruct = (MyStruct*)(char*)otherStruct;Выглядит, как заставить программиста писать лишний код на ровном месте...
Szer
14.07.2023 14:03+4Я минусую твои посты с надменным тоном. Вообще не в курсе кто тут "эксперт", но читать тебя противно.
DimPal
Массив размером 256*(sizeof int)=1Kb? Можно и без массива и без ветвлений, например:
char c ; // inputchar t ; // tempint res = 0;...t = c ^ 's'; res += (int)((~t &(t-1)) >> 7) & 1;t = c ^ 'p'; res -= (int)((~t &(t-1)) >> 7) & 1;на ассеблере будет еще компактнее (можно задвигать знаковый бит в флаг переноса);
DimPal
или так:
t = c ^ 's'; res -= (int)((~t & (t-1)) >> 7);t = c ^ 'p'; res += (int)((~t & (t-1)) >> 7);lorc
Что-то я не думаю что это будет компактнее и/или быстрее. Тут дофига битовых операций на каждую итерацию цикла.
Didimus
К коллайдеру! (с)
То есть, эксперимент рассудит вас
DimPal
Зато нет 1Кб массива. Вот еще вариант на вскидку:
t = (c & ~3) ^ 'p'; // is p|q|r|sres += (((0x94 >> ((c&3)<< 1)) & 3) - 1) & ((~t & (t - 1))>> 7);//const as array[4]thevlad
я ради любви к науке, протестировал оба ваших варианта, и все они значительно медленнее варианта с табличкой (2-3 раза). Приемы из "мира z80", редко на современных процессорах работают так же прямолинейно.