Битовые флаги

Недавно наткнулся в одной библиотеке на интересный способ объявления и использования битовых флагов которым хочу поделиться. Но перед тем как перейти к нему хотел бы показать как я бы лично их реализовал и чем мой метод хуже.

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

struct File {
     int permissions;
     enum class ACLs {
         read = 1,
         write = 2,
         remove = 4,
         rename = 8
     };
};


int main() {
    File file;
    file.permissions = (int)File::ACLs::read | (int)File::ACLs::write; // Файл в который можно читать и писать но не переименовывать или удалять


    if (file.permissions & (int)File::ACLs::remove) { // Удалить файл если есть права на удаление
        // removeFile(file);
    }
}

https://godbolt.org/z/c9fevjEYG

Как видно из примера такие флаги очень удобно комбинировать, проверять на наличие свойства и т.д. Ну впрочем вы и сами явно в курсе. Давайте лучше сфокусируемся на недостатках этого кода. А их много:

1. Необходимо кастовать значение enum к int перед каждой битовой операцией: (int)File::ACLs::read | (int)...
2. Необходимо корректно инициализировать значения enum степенями двойки.
3. Битовые выражение для проверки наличия свойства которые сложно читать

А теперь собственно глянем как подобное может быть реализовано удобнее:

struct File {
    union {
        int permissions;
        struct { int read:1, write:1, remove:1, rename:1; };
    };
};


int main() {
    File file;
    file.permissions = 0b11; // Установить биты отвечающие за read и write


    if (file.remove) { // Удалить файл если есть права на удаление
        // removeFile(file);
    }
}

https://godbolt.org/z/TxxEs71hP

На всякий если кто-то не понял что произошло объясню. Union позволяет объявить несколько альтернативных способов доступа к одному и тому же куску памяти. В данном случае первое свойство структуры File будет иметь размер Int (самый большой тип под Union), но при этом эту же область памяти можно будет в коде интерпретировать как второй заданный тип юниона. При этом второй тип в свою очередь состоит из 4 значений каждое из которых занимает ровно 1 бит памяти.
Таким образом мы можем одновременно использовать кусок памяти выделенный под свойство permissions и как целочисленное число (что позволит нам проводить битовые операции) и как набор битовых полей, что упростит нам проверку на наличие какого-то свойства.

Конечно этот пример не во всех случаях лучше исходного решения. Как минимум вопрос инициализации как видно тут решен не очень красиво, однако это еще один инструмент в копилке возможностей языка.

Перегрузка операторов (часть 1)

Все вы в курсе, что создатели С++ посчитав свой язык слишком простым к освоению, решили добавить в него парочку, так сказать, интересных возможностей. Одной из таких возможностей является перегрузка операторов. Все мы знаем, что в отличи от той же Java, эта фича дает возможность C++ разработчикам писать свои удобные к использованию коллекции, умные указатели и многое другое. Но есть парочка операторов, которые в здравом уме, скорее всего, вы бы даже использовать не стали, но оказывается их вполне себе можно перегрузить. Давайте глянем на пару из них.

Для начала давайте глянем на операторы доступа к свойствам объекта. К таким операторам относятся оператор разыменования (*), взятие ссылки на (&), или доступа к свойству по адресу (->). Вы скорее всего знаете что эти операторы перегружаемые, что дает возможность реализовывать простые к использованию умные указатели. Однако один оператор меня тут удивил – оператор разыменования свойства класса (->*). Согластно cppref (https://en.cppreference.com/w/cpp/language/operator_member_access) В обычной жизни (без перегрузки) этот оператор равносилен конструкции (*object).*field_ptr. Тут лично у меня возник логичный вопрос, а зачем собственно разыменовывать свойство объекта?
Казалось бы, если у нас есть некоторое свойство класса которое является указателем в память, то его разыменование должно происходить так: *object->field_ptr. И я был абсолютно прав, однако оказалось что в С++ существует такая концепция как указатели на свойства класса. Давайте рассмотрим что это такое на следующем коде:

class A {
public:
   A() { field = 0; }
   int field;
};


int main() {
   A a;
   A *a_ptr = &a;


   int (A::*field_ptr); // Вот это собственно указатель на свойство 
   field_ptr = &A::field; // А теперь оно указывет на свойство field
}

Вот собственно что бы пользоваться такими указателями и существует оператор ->* который можно использовать как:

return a_ptr->*field_ptr;

Потрясающе. И зачем мне перегружать этот оператор? Честно говоря я без понятия. На просторах интернета я нашел только этот вразумительный случай использования: https://stackoverflow.com/questions/2696864/are-free-operator-overloads-evil. Для простоты статьи я не буду вдаваться в объяснение, если вам интересно, почитайте первый же ответ описывающий библиотеку Boost.Phoenix. А мы двинемся дальше.

Операторы сравнения. Опять же, очевидно что можно перегрузить операторы <, >, =, но какого было мое удивление узнать, что начиная с С++20 существует оператор трехстороннего сравнения <=>. Давайте для начала поймем что он делает без перегрузок:

https://godbolt.org/z/1qs14eeoz

  auto comp = 1 <=> 2;
  std::cout << typeid(comp).name() << std::endl;
  std::cout << "Is lower: " << (comp < 0) << std::endl;
  std::cout << "Is bigger: " << (comp > 0) << std::endl;
  std::cout << "Is equal: " << (comp == 0) << std::endl;

Результат этого кода следующий:

std::strong_ordering
Is lower: 1
Is bigger: 0
Is equal: 0

Итак оператор <=> возвращает объект некого типа std::strong_ordering либо std::weak_ordering который можно сравнить с 0 операторами <, >, ‘==’ и который по сути реализует метод int compare. По сути перегрузка данного оператора позволяет нам одним методом реализовать целых 5 операторов: ==, !=, <=, >, >=.

Вот так может выглядеть класс двухмерных координат с использованием данного оператора:

https://godbolt.org/z/6W9fzKxcE

#include <compare>
#include <iostream>


struct Point {
   int x, y;

   friend constexpr std::strong_ordering operator<=>(Point lhs, Point rhs)
   {
       if (lhs.x < rhs.x or (lhs.x == rhs.x and lhs.y < rhs.y))
           return std::strong_ordering::less;
       if (lhs.x > rhs.x or (lhs.x == rhs.x and lhs.y > rhs.y))
           return std::strong_ordering::greater;
       return std::strong_ordering::equivalent;
   }
};


int main() {
   Point p1{0,0};
   Point p2{0,-1};
   Point p3{1,0};


   std::cout << (p1 < p2) << " " << (p2 <= p3) << " " << (p3 > p1) << std::endl;
}

Перегрузка операторов (часть 2)

Ладно, вы еще не устали? Тогда вот вам на десерт самый абсурдный оператор. Оператор перечисления ,. Да, да, его можно перегрузить. Давайте для начала вспомним когда он может использоваться. Ну например в следующих строчках:

int main() {
    int a = 0;
    int b = 0;
    for (a = 0, b = 0; a < 2 && b < 2; a++, b++);
    return a, b;
}

Что тут делает этот оператор? Правильно, вычисляет по цепочке все выражения и возвращает самое правое. Давайте попробуем его перегрузить:

struct Crazy {
   int a;


   int operator,(Crazy &ob2)
   {
       return a;
   }
};


int main() {
   Crazy a{1};
   Crazy b{2};


   return a, b;
}

Результатом данной программы будет 1, то есть мы заставили вернуть левый объект вместо правого. Отлично, а нафига это нужно? Ну есть парочка интересных примеров (которые можно глянуть тут: https://stackoverflow.com/questions/5602112/when-to-overload-the-comma-operator). Вот один из них: Boost.assign умеет делать так:

vector<int> v;
v += 1,2,3,4,5,6,7,8,9;

Перегрузив запятую позволяет создавать цепочки на добавление элементов в коллекцию.

Ну что же, теперь вы знаете на 3 бессмысленных фичи С++ больше. Поздравляю вас, еще пару тысяч таких и мы с вами научимся проходить самые душные C++ интервью!

Оптимизация с использованием данных профилятора. Часть 1

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

Как вы знаете clang является оптимизирующим компилятором. То есть он пытается перепаковать исходный код в нечто наиболее эффективное для конкретной архитектуры процессора. И для большей части оптимизаций знания самого кода вполне достаточно. Однако существует ряд оптимизаций, которые могут работать эффективнее в случае если на этапе компиляции известно как код используется во время исполнения. К таким оптимизациям относятся к примеру: девиртуализация вызовов виртуальных методов (devitualization of virtual methods), порядок расположения блоков кода в исполняемом файле (instructions memory layout) и подстановка функций (functions inling). Для простоты статьи я остановлюсь подробнее на последней оптимизации, про первые две есть неплохое видео на ютуб, ссылку на которое я оставлю в конце статьи.

Для начала коротко про подстановку функций. Допустим у нас есть следующий код:

int foo(int arg) {
   return arg + 1;
}


int main(int argc, char*argv[]) {
   return foo(argc); // Место вызова функции
}

При прямолинейной компиляции этого кода мы получим что-то типа:

foo(int):
       lea     eax, [rdi + 1] // Логика функции
       ret


main:
       ... // Инициализация аргументов
       call    foo(int) // Прыжок в область кода с реализацией функции
       ret

Недостаток этого кода в том, что прыжок (call) является накладной операцией, так как переходы по сегментам исполняемого файла влияют на эффективность исполнение и компиляторы стараются сводить их к минимуму.

Если мы соберем этот пример с флагом -O2 мы увидим следующий код:

main:
       lea     eax, [rdi + 1]
       ret

То есть компилятор подставил код самой функции вместо ее вызовы.

У вас скорее всего возник вопрос “а почему бы тогда не подставлять вообще все функции в программе?”. Хороший вопрос, однако большинство функций в реальном коде достаточно большие и вызываются во многих местах кода, если подставлять их всех везде размер исполняемого файла очень быстро станет слишком большим. Компиляторы стараются соблюдать некий компромисс между скоростью исполнения и размером бинарного файла. Для этого есть понятие квоты подстановок и при обычных условиях компилятор руководствуется рядом эвристик для того чтобы решить какой из методов подставить. Допустим в следующем примере:

int foo(int arg) {
  return arg + 1;
}

int bar(int arg) {
  int c = arg * 2;
  int d = c + arg * 3;
  return c + d;
}

int main(int argc, char*argv[]) {
   int result;
   for (int i = 0; i < 1000000000; i++) {
       if (argc > 2) {
           result += foo((int)argv[2][0]);
       } else {
           result += bar((int)argv[1][0]);
       }
   }


   return result;
}

При прочих равных если у компилятора осталась одна квота на подстановку, то он выберет функцию foo так как она короче (я сейчас игнорирую остальные оптимизации).
Однако что если в реальной жизни пользователь намного чаще вызывает эту программу с одним аргументом? Проще говоря, если функция bar вызывается намного чаще, чем функция foo то ее подстановка становится более выгодной. Но что бы понять это компилятору нужна информация о том как программа используется пользователем.

Способов получения этой информации несколько, один из них – использование стороннего профилятора во время выполнения для сбора семплирования. В линуксе таким профилятором для CPU служит утилита perf.

Оптимизация с использованием данных профилятора. Часть 2

Давайте посмотрим как это может работать.

Шаг 1: Компилируем программу с несколькими флагами позволяющими сопоставить собранные метрики с исходным кодом:

clang++ -O2 -gline-tables-only -fdebug-info-for-profiling -funique-internal-linkage-names sample.cc -o sample

Шаг 2: Исполняем собранную программу с профилятором:

sudo perf record -b -e BR_INST_RETIRED.NEAR_TAKEN:uppp ./sample 1

Шаг 3: Так как perf это внешняя для llvm утилита, нам нужно сконвертировать результат ее работы в формат понятный для компилятора. Для этого в llvm есть утилита llvm-profgen:

llvm-profgen --binary=./sample --output=sample.prof --perfdata=perf.data

Шаг 4: Перекомпилируем исходную программу с собранной статистикой:

clang++ -O2 -fprofile-sample-use=sample.prof sample.cc -o sample_pgo

Давайте глянем на собранную статистику профилятора. Для этого в llvm есть другая утилита llvm-profdata которая позволяет объединять статистики, смотреть их содержимое и многое другое:

llvm-profdata show --sample sample.prof

Команда выше покажет нам следующее:

Function: main: 1965000, 0, 7 sampled lines
Samples collected in the function's body {
  …
  6: 82500, calls: _Z3bari:82500 
  …
}

Имея эту информацию на руках компилятор может понять что функция bar вызывается намного чаще чем функция foo и проработать эффективнее. Важное замечание: Если сценарий использования программы в реальной жизни резко меняется, то результат сбора PGO данных может повлиять негативно на производительность программы, так что чаще всего в реальной жизни PGO данные пере-собираются в реальном времени.

В следующей части я попробую собрать сам clang вместе и без PGO и сравню производительность сборки какого нибудь примера.

На последок видео о котором я говорил в начале: https://www.youtube.com/watch?v=3RtMMHkVsDg