[SnowOne 2025] Константин Владимиров: Странные ограничения статических компиляторов

Рассмотрим, чем статически компилируемые языки отличаются от динамически компилируемых, что такое трансляционная семантика, чем трансляция отличается от исполнения и какие странные ограничения статических компиляторов это порождает.

Видео: https://youtu.be/fAZSIAsKarc

Transcript

1. СТРАННЫЕ ОГРАНИЧЕНИЯ Странные ограничения статических компиляторов и суть трансляционной модели. К. Владимиров, Syntacore, 2025 mail-to: konstantin.vladimirov@gmail.com
2. Динамические языки • A dynamic programming language is a type of programming language that allows various operations to be determined and executed at runtime. • Интуитивно: • Python, Ruby, Javascript – динамически типизированные динамические языки. • Java, C# – статически типизированные динамические языки. • C, C++ – статические языки. • Когда я говорю "динамический" относительно языка я имею в виду существенный объём рантайм-поддержки: • интерпретацию внутри виртуальной машины, JIT-компиляцию, сборку мусора... 2 Dynamic_programming_language
3. Статические языки • В случае статического компилятора, мы говорим, что он производит трансляцию, а потом исполнение программы. • Это выглядит просто, но это обманчивая простота. 3 Execution Translation
4. Статические языки • В случае статического компилятора, мы говорим, что он производит трансляцию, а потом исполнение программы. • Фаза трансляции включает в себя много независимых фаз, включая препроцессирование, синтаксическую и семантическую обработку и оптимизации. 4 Execution Language Frontend Optimizing Compiler
5. Динамические языки • В случае динамических языков трансляция и исполнение в классическом смысле разорваны на разные части и перемешаны. • Трансляция включает в себя классический фронтенд (трансляция в байт-код) и JIT-оптимизации во время работы приложения. • Исполнение делится на интерпретацию и классическое исполнение оптимизированного кода. 5 Interpreter Execution GC JIT Interpreter Interpreter Language Frontend
6. Обсуждение • Разделение этапа трансляции и этапа исполнения в статических языках это хорошо или плохо? • Сегодня мы посмотрим на ряд примеров: к чему приводит это разделение и какие у него подводные камни. 6
7. Ассемблер может сильно отличаться int sum(int n) { if (n == 1) return 1; return n + sum(n - 1); } • Мы видим, что слева происходит нечто не слишком похожее на то, что справа. sum(int): li a3,1 li a5,0 beq a0,a3,.L7 .L2: mv a4,a0 addiw a0,a0,-1 addw a5,a5,a4 bne a0,a3,.L2 addiw a0,a5,1 .L7: ret 7 https://godbolt.org/z/qP5qMTGfn
8. Ассемблер может сильно отличаться int sum(int n) { if (n == 1) return 1; return n + sum(n - 1); } • Иногда результат может драматически отличаться. sum(int): addiw a1, a0, -1 beqz a1, .LBB0_2 addi a2, a0, -2 mul a1, a1, a2 addi a3, a0, -3 slli a3, a3, 32 slli a2, a2, 32 mulhu a2, a2, a3 srli a2, a2, 1 add a0, a0, a1 subw a0, a0, a2 addiw a0, a0, 1 ret .LBB0_2: li a0, 1 ret 8 https://godbolt.org/z/qP5qMTGfn
9. Абстрактная машина • В статически транслируемых языках компилятор обязан учитывать особенности абстрактной машины языка, не порождая при этом кода для неё. int zero() // external linkage { int i = 0; int j = i * i + i * 3 + 42; // no side effects return i; } • Есть простое и важное правило, согласно которому действует оптимизатор. 9
10. As-if rule [intro.abstract] [...] conforming implementations are required to emulate (only) the observable behavior of the abstract machine. • Что представляет собой observable behavior? • Accesses through volatile glvalues • Data written into files • The input and output dynamics of interactive devices • Компилятор имеет право делать с программой почти что угодно пока наблюдаемое поведение гарантированно то же. • Это даёт некоторую свободу оптимизаторам. 10
11. Мы должны быть консервативными int nonzero(int i) // external linkage { return i * i + i * 3 + 42; // no side effects, but... } • Cтатический компилятор не может тут ничего убрать при раздельной трансляции: он не знает будет ли это выражение использовано далее для произведения побочного эффекта. • Тот объём внутри которого статический компилятор способен отследить все связи называется единицей трансляции. Для языка C это файл. 11
12. Трансляционная семантика • В языке C++ абстрактная машина является: • Параметризованной. • Это допускает наличие implementation-defined и locale-specific behavior. • Не детерминированной. • Это допускает наличие unspecified behavior. • Не везде определённой. • Это допускает наличие undefined behavior. 12
13. Implementation defined • Определяемое реализацией поведение должно быть задокументировано для вашей реализации. • Определяемое локалью поведение должно быть документировано для вашей локали. std::println("{}", sizeof(char16_t)); // 2? std::println("{:L}", 1234); // 1234? • Здесь в обоих случаях допустим широкий набор разнообразных побочных эффектов. • Туда же падают conditionally supported вещи (вроде inline asm). 13
14. Unspecified • Корректная ситуация в которой может быть несколько равноправных вариантов выполнения (зависящих от реализации). • То есть у нас есть два вполне корректных поведения. if (+"{}" == +"{}") { // сравнение указателей, не строк! std::println("{}", "option 1"); } else { std::println("{}", "option 2"); } • Зачем оставлено это поведение? • Внезапно: чтобы дать возможность оптимизации. 14 https://godbolt.org/z/8T6ndKrqv
15. Вернёмся к сумме int sum(int n) { if (n == 1) return 1; return n + sum(n - 1); } • Вообще-то в этом коде что-то вроде довольно большого (?) цикла если вход отрицательный. sum(int): addiw a1, a0, -1 beqz a1, .LBB0_2 addi a2, a0, -2 mul a1, a1, a2 addi a3, a0, -3 slli a3, a3, 32 slli a2, a2, 32 mulhu a2, a2, a3 srli a2, a2, 1 add a0, a0, a1 subw a0, a0, a2 addiw a0, a0, 1 ret .LBB0_2: li a0, 1 ret 15
16. Undefined behavior • Компилятор имеет право не моделировать не определённые в абстрактной машине действия. int sum(int n) { // если n <= 0 if (n == 1) return 1; return n + sum(n - 1); // то тут signed int underflow // но при этом его нет // в абстрактной машине } 16 https://godbolt.org/z/9EboaPoE6
17. Undefined behavior • [intro.abstract] A conforming implementation executing a well-formed program shall produce the same observable behavior [...]. However, if any such execution contains an undefined operation, this document places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation) int k, satd = 0, dd, d[16]; /* .... more code here .... */ for (dd = d[k = 0]; k < 16; dd = d[++k]) // бесконечный цикл satd += (dd < 0 ? -dd : dd); 17
18. А что с динамическими языками? for (dd = d[k = 0]; k < 16; dd = d[++k]) satd += (dd < 0 ? -dd : dd); 18 Interpreter Execution JIT Bounds check Interpreter Bounds check
19. Слепота относительно UB • Компилятор всегда ведёт себя так, как будто UB не существует. int f() { int i; int j = 0; for (i = 1; i > 0; i += i) ++j; return j; } • Законная оптимизация этого кода это опять бесконечный цикл. f(): .L2: jmp .L2 19
20. Можем ли мы обуздать UB в signed int? • Оба варианта с такого рода опциями (fwrapv и ftrapv) ограничены только целочисленным переполнением. • Можем ли мы убрать UB в принципе? 20 int f() { int i; int j = 0; for (i = 1; i > 0; i += i) ++j; return j; } f(): mov eax, 31 ret f(): ud1 eax, dword ptr [eax] ftrapv fwrapv https://godbolt.org/z/soM6c8dvY
21. Убираем UB более общим способом • Разновидностью корректной реализации абстрактной машины языка является явная проверка UB. int mult (int a, int b) { return a * b; // UB if integer overflow } • Одним из способов является подключение UB sanitizer. mult(int, int): mov eax, edi imul eax, esi jo .LBB0_1 // jump if overflow ret .LBB0_1: // вызов __ubsan_handle_mul_overflow 21
22. UB ради производительности: память int foo(int *a, double *d, int n) { for (int i = 1; i < n; ++i) { d[2] = 1.0; a[i] += i * i; } return d[a[0]]; } 22 https://godbolt.org/z/W5b1vMboz
23. Строгий алиасинг и его отмена int foo(int *a, double *d, int n) { [basic.lval] If a program attempts to access the stored value of an object through a glvalue whose type is not similar to one of the following types the behavior is undefined: A. the dynamic type of the object B. a type that is the signed or unsigned type corresponding to the dynamic type of the object C. a char, unsigned char, or std::byte type • Есть опция -fno-strict-aliasing которая блокирует компилятору оптимизации, основанные на strict aliasing. 23
24. Стоит ли овчинка выделки? unsigned i, j; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) C[i * N + j] = foo(); • Тут дело в том, что указатели 64- битные, но по стандарту unsigned overflow определено. • В итоге вычисление 𝑖 ∗ 𝑁 + 𝑗 делается в 32-битных типах, а далее расширяется до 64 бит. .LBB0_2: mv s0, s4 mv s1, s3 .LBB0_3: call foo() slli a1, s1, 32 srli a1, a1, 30 add a1, a1, s6 sw a0, 0(a1) addi s0, s0, -1 addi s1, s1, 1 bnez s0, .LBB0_3 addiw s5, s5, 1 add s3, s3, s2 bne s5, s2, .LBB0_2 24 https://godbolt.org/z/cYnjnYTGh
25. Стоит ли овчинка выделки? int i, j; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) C[i * N + j] = foo(); • В то же время для целых чисел переполнение не определено. • Мы выкинули довольно много из очень горячего цикла. • Но автоматически это сделать сложно. .LBB1_2: mul a0, s4, s6 add a0, a0, s4 add s0, s2, a0 mv s1, s5 .LBB1_3: call foo() sw a0, 0(s1) addi s1, s1, 4 bne s1, s0, .LBB1_3 addi s6, s6, 1 add s5, s5, s4 bne s6, s3, .LBB1_2 25 https://godbolt.org/z/cYnjnYTGh
26. Intwrap predication • Можно добавить проверку на переполнение и сделать арифметику в 64 бит. • Ускорение до 18% на coremark для RISC-V. 26 https://reviews.llvm.org/D132208 unsigned i, j; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) C[i * N + j] = f(); unsigned i, j; unsigned long long v, w; if (overflow(N * N)) { for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) C[i * N + j] = f(); } else { for (v = 0; v < N; ++v) for (w = 0; w < N; ++w) C[v * N + w] = f(); }
27. Что мог бы сделать JIT? • Поскольку переполнение не самый вероятный сценарий, JIT мог бы просто вставить возврат в интерпретатор. 27 unsigned i, j; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) C[i * N + j] = f(); unsigned long long i, j; if (overflow(N * N)) __back_to_interpreter(); for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) C[i * N + j] = f();
28. Непредсказуемая производительность • Мы позволяем некоему процессу, например JIT-компилятору или сборщику мусора вклиниваться посередине исполнения. • Очевидная проблема: производительность приложения перестаёт быть предсказуемой. • Это не значит, что она будет плохой. "Непредсказуемый" и "плохой" это разные слова. 28 Interpreter Execution GC JIT Interpreter Interpreter
29. UB и трансляционная семантика • Есть мнение, что в Java нет UB. • Но и в C++ есть такие места, в которых нет и по стандарту не может быть UB. 29 Execution Translation Constexpr execution
30. Constexpr is perfect ubsan constexpr int f() { int i; int j = 0; for (i = 1; i > 0; i += i) ++j; return j; } constexpr int x = f(); <source>:3:24: note: value 2147483648 is outside the range of representable values of type 'int' 3 | for (i = 1; i > 0; i += i) 30 https://godbolt.org/z/vfW5qqM5z
31. Constexpr is perfect ubsan constexpr int f() { int k, satd = 0, dd, d[16] = {1, 2, 3}; for (dd = d[k = 0]; k < 16; dd = d[++k]) satd += (dd < 0 ? -dd : dd); return satd; } constexpr int x = f(); <source>:3:36: note: read of dereferenced one-past-the-end pointer is not allowed in a constant expression 3 | for (dd = d[k = 0]; k < 16; dd = d[++k]) 31 https://godbolt.org/z/397P656PW
32. Constexpr и проблема останова constexpr int f() { unsigned u, v = 0; for (u = 2; u > 1; ++u) ++v; return v; } constexpr unsigned x = f(); <source>:4:5: note: constexpr evaluation hit maximum step limit; possible infinite loop? 4 | ++v; 32 https://godbolt.org/z/1fjxoKdjn
33. Проблемы constexpr: fp evaluation constexpr float f(float x, float y) { return x / y; } constexpr float x = f(1.0, 3.0); int v; v = std::bit_cast<int>(x); std::println("{:#x}", v); std::fesetround(FE_DOWNWARD); v = std::bit_cast<int>(f(1.0, 3.0)); std::println("{:#x}", v); 33 0x3eaaaaab 0x3eaaaaaa https://godbolt.org/z/eTM9Y6cc4
34. Обсуждение • Работа floating-point вычислений зависит от меняющегося во время выполнения глобального состояния. • Хуже того, результатом любого floating-point вычисления могут быть: • Специальные значения: sNaN, qNaN • Бесконечности ±INF • Денормализованные числа. • И далее они распространяются на дальнейшие вычисления. 34
35. Нарушим IEEE? float f(float x) { return x*x*x*x*x*x*x*x; } • Как мы выше показали, компилятор тут не может сделать тривиальную оптимизацию. x *= x; x *= x; x *= x; • Это может изменить результат очень существенно. f: vmovaps xmm1, xmm0 vmulss xmm0, xmm0, xmm0 vmulss xmm0, xmm0, xmm1 vmulss xmm0, xmm0, xmm1 vmulss xmm0, xmm0, xmm1 vmulss xmm0, xmm0, xmm1 vmulss xmm0, xmm0, xmm1 vmulss xmm0, xmm0, xmm1 ret 35
36. Нарушим IEEE! Assume ffast-math float f(float x) { return x*x*x*x*x*x*x*x; } • Теперь эта оптимизация возможна. x *= x; x *= x; x *= x; • Чем мы за это заплатили? f: vmulss xmm0, xmm0, xmm0 vmulss xmm0, xmm0, xmm0 vmulss xmm0, xmm0, xmm0 ret 36 https://godbolt.org/z/WsbjGnrWG
37. Плохо предсказуемая корректность • Статические компиляторы должны догадываться о большом количестве разнообразных вещей. • После того, как эти догадки сделаны, их нельзя изменить во время выполнения. • Если какая-то из этих догадок некорректна, это приводит к последствиям в виде непредсказуемой корректности вычислений. • Мы можем от этого заблокироваться, но тогда мы теряем производительность. Гораздо чаще мы делаем наоборот: проектируем языки так, чтобы легче давать подсказки. 37
38. qsort vs std::sort • Сравним C подход когда компаратор передаётся через указатель. void qsort (void* base, size_t num, size_t size, int (*compar)(const void*, const void*)); • Против C++ подхода, когда сравнение завёрнуто в тип. template <typename It, typename Comp = std::less<>> void sort (It start, It fin, Comp compare); • Что будет работать быстрее? 38
39. Разница очевидна: полтора раза 39 quick-bench result
40. Как мог бы выйти из этого JIT? • JIT компилятор не требует такого рода догадок void qsort (void* base, size_t num, size_t size, int (*compar)(const void*, const void*)) { // горячий случай: сравнение с конкретным компаратором // строим код который оптимизирован для него // если что-то не угадали – просто уходим в интерпретатор } 40
41. Именно тут кроется трюк • На этом трюке очень часто строятся многочисленные "примеры когда Java быстрее C". • По сути это ловкость рук: мы делаем достаточно горячий цикл, относительно которого статический компилятор делает неправильное предсказание. • Понятно, что JIT прав всегда и в данном случае затраты на него окупаются. • Разумеется это имеет мало общего с производительностью настоящих приложений, где профиль обычно плоский и тонкие места обрабатываются с учётом профиля статически. 41
42. Обсуждение • Для JIT гораздо легче делать оптимизации, включая очень сложные. • Увы, делают это они гораздо реже. • Но почему? 42
43. JIT должен быть быстр 43 Execution Language Frontend Optimizing Compiler Interpreter Execution JIT Language Frontend
44. Люди ищут выходы: falcon JIT и друзья 44 Optimizing cloud-native compiler Interpreter Execution IR builder Language Frontend Caching
45. Резюме • Статические компиляторы должны догадываться о контексте исполнения. • Undefined behavior даёт оптимизатору достаточное пространство для догадок. • Везде где трансляция смешана с исполнением нет нужды в пространстве догадок и в особой трансляционной семантике. • Например в constexpr в C++ • За совмещённость с исполнением JIT платит более простыми оптимизациями, зато появляются дополнительные опции вроде возможности всегда вернуться в интерпретатор. • Люди постоянно ищут возможности получить лучшее из двух миров. 45
46. ВСЕМ СПАСИБО А теперь ваши вопросы
47. БЭКАП Если останется время 47
48. Что насчёт векторизации? • Допустим мы хотим векторизовать strlen. • Тут рантайм динамического языка может по получению исключения обработать его. Но что делать в статических языках? 48 Non-committed memory String vector size vector size vector size
49. Fault only first strlen: mv a3, a0 # Save start loop: vsetvli a1, x0, e8, m8, ta, ma # Vector of max length vle8ff.v v8, (a3) # Load bytes csrr a1, vl # Get bytes read vmseq.vi v0, v8, 0 # Set v0[i] vfirst.m a2, v0 # Find first set bit add a3, a3, a1 # Bump pointer bltz a2, loop # Not found? add a0, a0, a1 # Sum start + bump add a3, a3, a2 # Add index sub a0, a3, a0 # Subtract sum ret 49 strlen.s
50. Обсуждение: польза сборщика мусора • Может ли сборка мусора быть полезной для производительности? • Подумайте вот о таком сценарии. В вашей программе вам очень важно избежать утечек памяти. • При наличии сборщика мусора это гарантирует сборщик мусора. • Что мы за это заплатим при попытке решить эту проблему без него? 50
51. Умные указатели • Следующая идея интрузивных умных указателей для C++ не работает template<typename T> void intrusive_ptr_add_ref(T* ptr) { ptr->add_ref(); } template<typename T> void intrusive_ptr_release(T* ptr) { if(!ptr->release()) delete ptr; } 51
52. Настоящая картинка вызывает ужас • Отдельно живущий контрольный блок плох с точки зрения многопоточной синхронизации. • Наличие слабых указателей является очень неудобной концепцией. • Как итог shared pointers в мире C++ пользуются дурной репутацией. 52