Записки дилетанта: Навіщо розуміти комп'ютер, якщо сучасні мови та їх бібліотеки такі потужні?

середа, 12 серпня 2020 р.

Навіщо розуміти комп'ютер, якщо сучасні мови та їх бібліотеки такі потужні?

Працюю із дуже розумними та працьовитими студентами. Тому основне обмеження -- рівень їх мотивації. Важливо показати їм -- навіщо все це. Звісно, власний похід по граблях дає глибший і стабільніший результат, але це довга дорога, хотілося б її спростити. Тому -- очевидні для них приклади плюс практика.

Байка - 1

Типовий "мотиваційний" приклад -- історії про вирішення задачі підрахунку слів у текстових файлах. Фабула наступна, пропонуєш цю задачу новій аудиторії, наступного разу:

Сильний студент: "дуже складна задача, на 1Мб файлі майже півгодини рахує!".
Слабкий: "Та ні, кілька секунд всього".

Як так? Слабші слухали рекомендації уважно. Сильні слухати такий дріб'язок не стали, глянули мануали, побачили метод count() чи аналогічний. Вирішили, що треба унікальний список слів -- зробили копію контейнер із вхідними даними, посортували (знаючи, що таке в стандартній бібліотеці є), видалили дублікати (і таке знайшли), тоді пройшлися по отриманому, кожен раз викликаючи count() для вихідного контейнера. Результат отримано. Разом із, мінімум, квадратичною складність по кількості слів та немалою константою. (Формально -- N*M, де N -- кількість слів, M -- кількість унікальних слів, але на практиці, якщо не відкидати розділові знаки, не приводити до одного регістру, відношення N до M потрапляло десь між 3 і 10). Якщо результат додавали не в std::unordere_map а до std::map, ("бо map вимагав викладач") -- N*M*ln M. Замість менше, ніж N*ln N.

Варіацій подібного виконання бувало багато. Вище -- історія про людей, які прийшли в Python чи С++ з С. Хто із мов з розвиненішою стандартною бібліотекою -- візьме std::set чи іншу реалізацію множини для створення унікального списку. Хтось зразу вектор пар стрічка-кількість створить, з нього вже в std::map копіюючи і т.д. і т.п. Але суті це не змінює.

В результаті -- легкодоступність інструментів разом із нерозумінням, як вони функціонують, народжує монстрів. Якби автори мусили реалізовувати count() на, скажімо, С -- вони б точно задумалися. А так -- чорна скринька і все.

Ця історія про нерозуміння функціонування готових засобів. Про важливість розуміти будову CPU чи CUDA-сумісного GPU можна показати на прикладі матричних операцій -- як результат змінюється між тривіальною та все більш оптимальними (читай -- важкозрозумілими) реалізаціями. Порядок-другий різниці -- достатньо переконливо. Однак, для таких задач, через складність, часто, розумним рішенням є скористатися готовим кодом, який нюанси "заліза" враховує -- бібліотекою матриць, перетворень Фур'є, нейромереж тощо.

Чи є щось між тими полюсами? Студенти вкотре показали -- є.

"Біти-байти, навіщо це все?.. Я хочу думати про алгоритм!"

Весна 2020-го. Наближається сесія. Студенти здають практичні. Перевіряю одну із них -- про маніпуляцію із double/float стандарту IEEE 754 вручну. Зроблена досить якісно і з розумінням. Але, коли вчитуюся в подробиці реалізації, натрапляю на epic fail. Потрібно було авторам перевіряти, чи нульовий біт у байті рівний нулю. Реалізували вони це так (С++17):

std::string to_bin(std::byte current_byte) noexcept
{
  return std::bitset<8>(std::to_integer<size_t>(current_byte)).to_string();
}

bool check0_1(std::byte cb) noexcept
{
    auto byte_bin = to_bin(cb);
    return byte_bin[0] == '0';
}

Замість:

bool check0_2(std::byte cb)
{
    return std::to_integer<size_t>(cb) & 1;
}

Розумію, поспіх. Розумію -- втома, немає часу шукати хороші рішення -- але ж замість очевидної арифметики (яку вони точно знали! -- суджу за попереднім їх "профайлом", та й саму практичну важко зробити, не розуміючи маніпуляцій бітами) -- купа коду. Його ж ще написати треба було. Коду, який перетворює число на стрічку -- із потенційним динамічним виділенням та звільненням пам'яті (якщо small string optimization не було), щоб потім символ в отриманій стрічці порівняти із символом '0' чи '1', а стрічку викинути. Я навіть розгубився -- сходу не зміг придумати, як зробити це ще гірше. (Потім придумав).

Що їм за це було -- хай залишиться за кадром. А я хотів би показати, як, за допомогою виключно онлайн інструментів, перевірити, наскільки все погано із таким кодом.

Перший інструмент -- "Compiler explorer", https://godbolt.org. Скомпілюємо ним цей код. Посилання: https://godbolt.org/z/v7Mncr. Якщо компілювати gcc 10.1 із -O3 та -std=c++17, то check0_2() виглядатиме так:

check0_2(std::byte): mov eax, edi and eax, 1 ret

Три команди. Врахуйте, що у випадку, коли ця функція викликатиметься в коді, ймовірно її буде заінлайнено і вона зведеться до однієї машинної команди and.

Для функції check0_1(), разом із to_bin() -- все настільки жахливо, що я її сховав. Асемблерний лістинг на 155 рядків.

Показати

to_bin[abi:cxx11](std::byte):
        push    r12
        mov     r8d, 48
        mov     ecx, 8
        xor     edx, edx
        push    rbp
        lea     rbp, [rdi+16]
        mov     r12, rdi
        push    rbx
        mov     ebx, esi
        xor     esi, esi
        mov     QWORD PTR [rdi], rbp
        mov     QWORD PTR [rdi+8], 0
        mov     BYTE PTR [rdi+16], 0
        call    std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_replace_aux(unsigned long, unsigned long, unsigned long, char)
        test    bl, bl
        jns     .L2
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax], 49
.L2:
        test    bl, 64
        je      .L3
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+1], 49
.L3:
        test    bl, 32
        je      .L4
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+2], 49
.L4:
        test    bl, 16
        je      .L5
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+3], 49
.L5:
        test    bl, 8
        je      .L6
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+4], 49
.L6:
        test    bl, 4
        je      .L7
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+5], 49
.L7:
        test    bl, 2
        je      .L8
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+6], 49
.L8:
        and     ebx, 1
        je      .L1
        mov     rax, QWORD PTR [r12]
        mov     BYTE PTR [rax+7], 49
.L1:
        mov     rax, r12
        pop     rbx
        pop     rbp
        pop     r12
        ret
        jmp     .L11
to_bin[abi:cxx11](std::byte) [clone .cold]:
.L11:
        mov     rdi, QWORD PTR [r12]
        cmp     rbp, rdi
        je      .L12
        mov     rsi, QWORD PTR [r12+16]
        add     rsi, 1
        call    operator delete(void*, unsigned long)
.L12:
        call    std::terminate()
check0_1(std::byte):
        push    r12
        mov     r8d, 48
        mov     ecx, 8
        xor     edx, edx
        push    rbp
        xor     esi, esi
        push    rbx
        mov     ebx, edi
        sub     rsp, 32
        lea     rbp, [rsp+16]
        mov     rdi, rsp
        mov     BYTE PTR [rsp+16], 0
        mov     QWORD PTR [rsp], rbp
        mov     QWORD PTR [rsp+8], 0
        call    std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_replace_aux(unsigned long, unsigned long, unsigned long, char)
        mov     rdi, QWORD PTR [rsp]
        test    bl, bl
        jns     .L35
        mov     BYTE PTR [rdi], 49
        mov     rdi, QWORD PTR [rsp]
.L35:
        test    bl, 64
        je      .L36
        mov     BYTE PTR [rdi+1], 49
        mov     rdi, QWORD PTR [rsp]
.L36:
        test    bl, 32
        je      .L37
        mov     BYTE PTR [rdi+2], 49
        mov     rdi, QWORD PTR [rsp]
.L37:
        test    bl, 16
        je      .L38
        mov     BYTE PTR [rdi+3], 49
        mov     rdi, QWORD PTR [rsp]
.L38:
        test    bl, 8
        je      .L39
        mov     BYTE PTR [rdi+4], 49
        mov     rdi, QWORD PTR [rsp]
.L39:
        test    bl, 4
        je      .L40
        mov     BYTE PTR [rdi+5], 49
        mov     rdi, QWORD PTR [rsp]
.L40:
        test    bl, 2
        je      .L41
        mov     BYTE PTR [rdi+6], 49
        mov     rdi, QWORD PTR [rsp]
.L41:
        and     ebx, 1
        jne     .L42
.L45:
        cmp     BYTE PTR [rdi], 48
        sete    r12b
        cmp     rdi, rbp
        je      .L34
        mov     rax, QWORD PTR [rsp+16]
        lea     rsi, [rax+1]
        call    operator delete(void*, unsigned long)
.L34:
        add     rsp, 32
        mov     eax, r12d
        pop     rbx
        pop     rbp
        pop     r12
        ret
.L42:
        mov     BYTE PTR [rdi+7], 49
        mov     rdi, QWORD PTR [rsp]
        jmp     .L45
        jmp     .L46
check0_1(std::byte) [clone .cold]:
.L46:
        mov     rdi, QWORD PTR [rsp]
        cmp     rdi, rbp
        je      .L47
        mov     rax, QWORD PTR [rsp+16]
        lea     rsi, [rax+1]
        call    operator delete(void*, unsigned long)
.L47:
        call    std::terminate()

Трішки "зоології" -- варіюємо параметри:

Якщо заборонити виключення, ключем -fno-exceptions, залишиться 133 рядків. Але для check0_2() компілятор і без того побачив, що турбуватися про виключення не потрібно.
З -O1 пара check0_1()/to_bin() вкладатиметься в 66 рядків асемблерного лістингу, а з -O1 -fno-exceptions -- взагалі 61. Правда, при цьому, викликає зовнішні функції:
call std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_replace_aux(unsigned long, unsigned long, unsigned long, char)
і
call operator delete(void*, unsigned long).

check0_2() не змінилася.
Якщо оптимізацію вимкнути повністю, check0_2(), разом із to_integer(), яка буде присутньою в коді явно, міститиме 14+8 = 22 рядки лістингу, а check0_1() із всіма службовими функціями -- 248, плюс зовнішні виклики.

Звичайно, кількість рядків, навіть не машинних команд, не дуже переконлива метрика ефективності, але співвідношення розмірів, разом із звертаннями до рантайму, мають насторожити.

Безпосереднім критерієм ефективності є час роботи коду. Замість того, щоб організовувати виміри часу локально, в коді, чи за допомогою perf/VTune/<ваш улюблений profiler>, скористаємося іншим онлайн сервісом -- Quick C++ Benchmark.

Увага! Benchmarking -- річ складна та нетривіальна. Будьте уважні та недовірливі. Зокрема -- звіряйтеся, що саме ви міряєте. Для того варто в Quick C++ Benchmark ставити галочку біля "Record disassembly" і уважно аналізувати -- а що за (машинний) код ви досліджували. Google benchmark ніби турбується, щоб компілятор зайве не наоптимізував, але на телепатію та чудеса він не здатен.

Код для тестування

#include <string>
#include <bitset>
#include <cstddef>

std::string to_bin(std::byte current_byte) noexcept
{
  return std::bitset<8>(std::to_integer<size_t>(current_byte)).to_string();
}

bool check0_1(std::byte cb) noexcept
{
    auto byte_bin = to_bin(cb);
    return byte_bin[0] == '0';
}

bool check0_2(std::byte cb)
{
    return std::to_integer<size_t>(cb) & 1;
}

static void bench_check0_1(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    bool r = false;
    for(int i = 0; i<2560; ++i)
      r |= check0_1(static_cast<std::byte>(i));
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(r);
  }
}
// Register the function as a benchmark
BENCHMARK(bench_check0_1);

static void bench_check0_2(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    bool r = false;
    for(int i = 0; i<2560; ++i)
      r |= check0_2(static_cast<std::byte>(i));
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(r);
  }
}
// Register the function as a benchmark
BENCHMARK(bench_check0_2);

Що ж показують тести? Що, для -O3, код із check0_2 швидший в 22-28 раз.

Час виконання кожного із тестів, gcc 10.1, C++17, -O3.

Враховуючи, що вона справді інлайниться, і на одну її команду and, в асемблерному коді буде ще 5-6 рядків коду циклу, можемо множити цю величину ще на 3-5 -- бо інструкції циклу складають мізерну відносну частку від коду check0_1().

Час виконання різних команд для check0_2(), обведено заінлайнений "залишок" цієї функції.
(Похибка цих величин доволі велика, іноді час атрибутується не тій інструкції, але це проблема будь-яких профайлерів).

Час виконання частини команд для check0_1() -- видно, що він між ними "розмазаний" менш-більш рівномірно, тому тих же 5 інструкцій циклу вносять помітно менший відносний вклад.

У цьому коді, щоб не дати компілятору викинути виклик нашої функції, на додачу до benchmark::DoNotOptimize(r), я протягую значення r із використанням OR -- "r |= <...>". Можна також оголосити r як volatile -- результат буде приблизно тим же. Якщо ж написати так:

static void bench_check0_2(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    for(int i = 0; i<2560; ++i)
      benchmark::DoNotOptimize( check0_2(static_cast<std::byte>(i)) );
    
  }
}

То розрив буде близько 34 і доволі відтворюваним. Якщо глянути на асемблерний код -- зникла одна інструкція, or, тому величина прискорення check0_2() виглядає природною, а check0_1() вже нічого не допоможе.

Для виконання повторного заміру поставте галочку "Clear cached results", але майте повагу до чужого волонтерського проекту -- не "покладіть" його DDoS-ом.

Час виконання кожного із тестів, варіант із
benchmark::DoNotOptimize( check0_?(static_cast<std::byte>(i)) ).
gcc 10.1, C++17, -O3.

Цикл по різним значенням аргументу використано, оскільки час роботи to_string() може залежати від кількості не нульових біт (без ретельних тестів, різниця в 23 рази для check0_1(0x00), 27 для check0_1(0xFF)).

На завершення, обіцяне застереження. Запускаючи вперше, я використав такий відверто невдалий для бенчмаркінгу код:

static void bench_check0_2(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    bool r;
    for(int i = 0; i<2560; ++i)
      r = check0_2(static_cast<std::byte>(i));
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(r);
  }
}

Отримав різницю в 87 тисяч раз. Причина проста -- компілятор викинув зайве з його точки зору.

До чого можна домірятися.

Знову ж -- інструменти потрібно розуміти, будь-які абстракції течуть.

Підсумок

Якщо зовсім не розуміти свою машину, буде весело -- і постійно чудеса та сюрпризи.
Сучасні онлайн-інструменти -- класна штука.

1 коментар:

toll18 лютого 2021 р. о 15:03
Дякую за статтю. Особливо цікаво було дізнатись про використання онлайн інструментів для оптимізації.
ВідповістиВидалити
Відповіді