Андрей Викторович Столяров: сайт автора

☞ From Андрей (unverified) Fri Apr 12 00:59:47 2024

"Компилятор всё оптимизирует"

Я посмотрел статью, прикреплённую в письме, и хочу сказать что достаточно удивился тому, что gcc не может по-нормальному оптимизировать даже вот такой простой пример(взятый из статьи):

bool isWhitespace(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '\t'; }

Вот этот простой код, который, казалось бы, можно реализовать простейшими логическими операциями, создаёт ВЕТВЛЕНИЕ при включенных оптимизациях.

Я скомпилировал код сам, и действительно, в выводе появляются инструкции для ветвления. Не сказал бы что я имею глубокие познания в ассемблере, но я точно знаю, что ветвление очень сильно понижает производительность на x86 системах из-за некоторых оптимизаций на уровне процессора. Из программ даже специально убирают ветвление чтобы они работали быстрее(это называется "branchless optimization"), а тут его компилятор создаёт буквально на ровном месте, причём когда никто не просит

clang кстати не сделал ветвление в этом конкретном примере и его ассемблерный вывод выглядит гораздо чище, так что есть с чем сравнивать и скорее всего это не "все компиляторы такие плохие", а если и плохие, то gcc, похоже, просто особенно плохой

ответить

From Andrey V. Stolyarov Fri Apr 12 09:58:17 2024

Re: "Компилятор всё оптимизирует"

В таких случаях лично меня крайне настораживают слова вроде "Я скомпилировал код сам, и действительно" при отсутствии упоминания того, какой был включён уровень оптимизации (-O2? -O3? или вообще про -O забыли?)

ответить

From Андрей (unverified) Fri Apr 12 11:59:28 2024

Re: Re: "Компилятор всё оптимизирует"

Действительно, забыл упомянуть про это. Я проверял с обоими уровнями оптимизаций. На -O2 и на -O3 результат получается полностью идентичный с этим примером

Стоит отметить, что без оптимизаций тоже появляются инструкции ветвления, причём у обоих компиляторов, так что, возможно, такая плохая оптимизация как-то связанна с временной репрезентацией. Возможный вариант: компилятор строит излишне низкоуровневую временную репрезентацию, к которой потом для него "самой логичной" оказывается не самая эффективная оптимизация. Не знаю как оно на самом деле, но однозначно придётся долго копаться в коде и документациях gcc чтобы это выяснить

ответить

From Дмитрий (unverified) Tue Apr 16 11:56:53 2024

Re: Re: "Компилятор всё оптимизирует"

0) gcc -v (Debian 12.2)

1) gcc -m32 -fno-asynchronous-unwind-tables -S -masm=intel main.c

#…

cmp DWORD PTR 8[ebp], 32

je .L2

cmp DWORD PTR 8[ebp], 10

je .L2

cmp DWORD PTR 8[ebp], 9

jne .L3

.L2:

mov eax, 1

jmp .L5

.L3:

mov eax, 0

.L5:

pop ebp

ret

#…

2) gcc -m32 -fno-asynchronous-unwind-tables -S -masm=intel -O2 main.c

#…

mov edx, DWORD PTR 4[esp]

lea eax, -9[edx]

cmp eax, 1

setbe al

cmp edx, 32

sete dl

or eax, edx

movzx eax, al

ret

#…

ответить

From Алексей О. (unverified) Thu Apr 18 11:10:31 2024

Re: "Компилятор всё оптимизирует"

Я не держу за привычку участвовать в “интернет-дискуссиях”, но чувствую что в этой дискуссии явно не хватает, как вы выразились, “глубоких познаний”. Так что, из личного уважения к Андрею Викторовичу и его труду, да и, будем честны, просто для себя, вброшу немного информации с позиции человека, который мало-мальски разбирается в вопросах производительности.

Начнем с того, что современные “большие” компиляторы (gcc, llvm, msvc), действительно регулярно генерируют неоптимальный, а иногда и просто очень плохой код. По этой причине, любой, кто задался целью написать производительную программу, вынужден проводить в дизассемблере немало времени. Хорошо ли это? Конечно нет. Правда ли это? Да. Можно ли сделать лучше? Наверное, да, но тут не всё так просто..

Давайте рассмотрим ваш пример из приложенной странички: isWhitespace.

Во-первых, говорить про “оптимальную” или “неоптимальную”, или даже “хорошую” или “плохую” кодогенерацию не имеет никакого смысла в отвязке от конкретной платформы. Я не вижу упоминания ключей -march в вашем комментарии, а в исходной статье они упоминаются только в одном месте (Case 31), где автор ругается на две ненужные инструкции вида xor eax, eax (которые, кстати, на современных x86_64 платформах вообще считаются за “zeroing idiom” и не приводят к генерации никаких вычислительных операций). Что на одной платформе будет медленнее, то на другой может быть быстрее, и наоборот.

Во-вторых, говорить про производительность функции такого вида также не имеет никакого смысла в отвязке от того, когда и с какими аргументами она вызывается. Грубо говоря, если вы будете отдавать этой функции значения по адресам в диапазоне сильно больше размера L3, то почти любая версия этой функции будет отрабатывать приблизительно за столько, сколько занимает чтение этого “char c” из памяти. Вот эти вот +-2 такта меркнут на фоне латентности памяти в 300-500 тактов. Если вы хотите оценить производительность такого вот кода, то стоит рассматривать какие-то реальные сценарии, где этот код реально много вызывается. Например, в цикле по какой-нибудь большой строке. Тут всё становится гораздо интереснее: начинают играть роль внеочередность исполнения инструкций, суперскалярность, спекулятивное исполнение. Такой код, кроме прочего, тривиально векторизуется.

Вот про такой цикл, на конкретной платформе, уже можно что-то пытаться говорить о производительности. Тут много инструментов, но главные: это профилировщики и статические анализаторы. Первые (например linux-perf, Intel VTune, AMD uProf) покажут вам, какие инструкции отрабатывают дольше остальных *на самом деле*, а также могут вывести значения т.н. PMC (Performance Monitoring Counters), то есть таких специальных регистров внутри процессора, которые подсчитывают интересные для нас события: количество исполненных инструкций, количество тактов, количество ветвлений с удачным и неудачный предсказанием, количество кэш-промахов разного уровня и тд. Вторые (например uiCA), используют достаточно точную модель процессора конкретного поколения, чтобы прогнать на ней ваш цикл и попытаться предсказать производительность, загруженность конвейера и конкретных функциональных устройств, показать узкие места в микроархитектуре и тд. Компилятор, если передать ему лишь одну такую функцию, этим контекстом не обладает, а значит вынужден генерировать “что-то”, согласно каким-то там эвристикам, которые в него заложены. Судить об оптимальности кодогенерации по такому примеру имеет смысла примерно столько же, сколько судить о скорости автомобиля по размеру его колес.

TL;DR: если вы вынесете хоть что-то из этого моего потока сознания, так пусть это будет то, что *не надо* смотреть на кусок ассемблера в полной отвязке от контекста (программного и аппаратного), видеть в нем одну инструкцию ветвления, и делать вывод “gcc bad”.

Оптимизация кода - интереснейшая область программирования, которой, к сожалению, уделяется очень мало внимания. Написание реально быстрых программ требует большого количества знаний, начиная с микроархитектуры процессоров и подсистем памяти, и заканчивая математической статистикой и теорией вероятности (производительность кода еще нужно уметь правильно измерить!).

Если вас эта тема реально интересует, то вот ресурсы (или наводки на них), которые я могу посоветовать (некоторые из них могут не работать без javascript. А.В., не убивайте насмерть, пожалуйста!):

1. https://en.algorithmica.org/hpc/

2. https://github.com/dendibakh/perf-book/releases/download/Q1.2024/Performance.Analysis.and.Tuning.on.Modern.CPUs.Q1.2024.pdf

3. https://www.agner.org/optimize/#manuals

ответить

☞ From Anonymous (unverified) Sun Mar 31 11:05:57 2024

xz

На это сайте в списке рассылки кое-что повеселее было про xz 5.6.0 и .1

ответить

☞ From Eduard (unverified) Tue Mar 26 10:53:52 2024

Новость про gcc

Ничему нельзя верить, даже gcc. Что же, не хотелось мне читать главу про ассемблер, но видимо придется. Хотя, всё равно переходить некуда. Из компиляторов Си кроме gcc и clang и выбирать то нечего. Под винду есть Pelles C и MSVC, но они ж под винду.

Столлман молчит, а те парни кидают оскорбительные письма. Уж тоже помолчали бы.

ответить

From Andrey V. Stolyarov Tue Mar 26 11:03:00 2024

Re: Новость про gcc

> Уж тоже помолчали бы.

Они не могут помолчать. Их пытаются носом ткнуть в тот простой факт, что их деятельность в последние лет пятнадцать сугубо вредоносна и уж точно совершенно бесполезна, а им, естественно, никак не хочется слезать с того потока спонсорских грантов, на котором они гордо восседают и весьма неплохо себя чувствуют.

ответить

From Anonymous (unverified) Wed Mar 27 16:11:05 2024