Предсказание ветвлений - путь к высокопроизводи­тельному C++

if (data > threshold) {
    // Обработка A
} else {
    // Обработка B
}

// Циклы обычно хорошо предсказываются
for (int i = 0; i < size; ++i) {
    total += data[i];
}

// Этот код будет хорошо предсказуем, если value обычно больше 100
if (value > 100) {
    processHighValue();
} else {
    processLowValue();
}

// Классическая реализация быстрой сортировки с плохой предсказуемостью
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) { // Непредсказуемое условие!
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Такой код часто лучше предсказывается на AMD
for (int i = 0; i < size; ++i) {
    if (i % 3 == 0) { // периодический паттерн
        doSomething();
    }
}

// Псевдокод, иллюстрирующий предикатное выполнение в ARM
r1 = (condition) ? thenValue : elseValue; // может быть выполнено без ветвления

// Такой код создаёт определённый паттерн ветвлений
bool condition = false;
for (int i = 0; i < 100; ++i) {
    condition = !condition;
    if (condition) { // Чередующееся условие: true, false, true, false...
        doA();
    } else {
        doB();
    }
}

int binarySearch(const std::vector<int>& array, int target) {
    int left = 0;
    int right = array.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (array[mid] == target)
            return mid;
            
        if (array[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return -1;
}

int branchlessBinarySearch(const std::vector<int>& array, int target) {
    int n = array.size();
    int left = 0;
    int right = n;
    
    while (right > left) {
        int mid = left + ((right - left) >> 1);
        // Используем арифметику вместо условных переходов
        left += (array[mid] < target) * (mid - left + 1);
        right -= (array[mid] >= target) * (right - mid);
    }
    
    int result = (left < n && array[left] == target) ? left : -1;
    return result;
}

std::vector<Customer> customers = loadFromDatabase();
for (const auto& customer : customers) {
    if (customer.hasOverduePayment()) {  // Непредсказуемо, если распределение случайное
        notifyCustomer(customer);
    }
}

while (dataStream.hasNext()) {
    Packet packet = dataStream.readNext();
    if (packet.type == PacketType::CONTROL) {  // Непредсказуемо для сетевого трафика
        handleControlPacket(packet);
    } else {
        processDataPacket(packet);
    }
}

int recursiveFunction(TreeNode* node) {
    if (node == nullptr) {  // Ошибка предсказания на листовых узлах
        return 0;
    }
    
    return node->value + 
           recursiveFunction(node->left) + 
           recursiveFunction(node->right);
}

std::unordered_map<int, int> sparseMap;
// Заполнение с большим количеством пустых ячеек
 
for (int key = 0; key < maxKey; ++key) {
    if (sparseMap.find(key) != sparseMap.end()) {  // Непредсказуемо!
        process(sparseMap[key]);
    }
}

std::vector<int> data = loadData();
std::vector<int> indices = generateRandomIndices(data.size());
 
for (int idx : indices) {
    if (data[idx] > threshold) {  // Крайне непредсказуемо при случайных индексах
        processElement(data[idx]);
    }
}

std::vector<std::unique_ptr<Shape>> shapes;
// Заполнение разными типами: Circle, Square, Triangle...
 
for (const auto& shape : shapes) {
    if (shape->type() == ShapeType::CIRCLE) {  // Непредсказуемо при разнородных данных
        processCircle(static_cast<Circle*>(shape.get()));
    } else if (shape->type() == ShapeType::SQUARE) {
        processSquare(static_cast<Square*>(shape.get()));
    } else {
        processOtherShape(shape.get());
    }
}

std::vector<std::shared_ptr<Animal>> animals;
// Заполнение разными животными: Dog, Cat, Bird...
 
// Каждый вызов makeSound() - это непрямое ветвление
for (const auto& animal : animals) {
    animal->makeSound();  // Трудно предсказать, какая реализация будет вызвана
}

// Базовый шаблонный класс
template <typename Derived>
class Animal {
public:
    void makeSound() {
        // Вызов реализации из производного класса
        static_cast<Derived*>(this)->makeSoundImpl();
    }
};
 
// Конкретная реализация
class Dog : public Animal<Dog> {
public:
    void makeSoundImpl() { std::cout << "Bark!" << std::endl; }
};
 
// Использование без виртуальных вызовов
Dog dog;
dog.makeSound();  // Прямой вызов, нет виртуальных функций

try {
    processBankTransaction(account, amount);
} catch (InsufficientFundsException& e) {
    notifyUserAboutInsufficientFunds(account);
} catch (DatabaseException& e) {
    logError("Database error during transaction: " + e.getMessage());
} catch (std::exception& e) {
    logUnexpectedError(e);
}

// Вместо исключений — явные коды ошибок
enum class TransactionResult {
    SUCCESS,
    INSUFFICIENT_FUNDS,
    DATABASE_ERROR,
    OTHER_ERROR
};
 
TransactionResult processBankTransaction(Account& account, Money amount) {
    if (account.balance < amount) {
        return TransactionResult::INSUFFICIENT_FUNDS;
    }
    
    if (!database.isConnected()) {
        return TransactionResult::DATABASE_ERROR;
    }
    
    // Выполнение транзакции...
    return TransactionResult::SUCCESS;
}
 
// Использование
TransactionResult result = processBankTransaction(account, amount);
switch (result) {
    case TransactionResult::SUCCESS:
        confirmTransaction();
        break;
    case TransactionResult::INSUFFICIENT_FUNDS:
        notifyUserAboutInsufficientFunds(account);
        break;
    // Обработка других случаев...
}

bool isValidTradePrice(double price) {
    return price > 0.0 && price < 1000000.0;
}
 
void processTrades(const std::vector<Trade>& trades) {
    for (const auto& trade : trades) {
        if (isValidTradePrice(trade.price)) {  // Вызов функции в горячем цикле
            executeTrade(trade);
        }
    }
}

// Общая версия для любого случая
template <typename T>
T processValue(T value) {
    // Сложная логика с множеством ветвлений
}
 
// Специализированная версия для наиболее частого случая
template <>
int processValue<int>(int value) {
    // Оптимизированная версия без лишних ветвлений
}

// Непредсказуемый вариант: данные случайно распределены
for (const auto& element : collection) {
    if (element.value > threshold) {  // Случайный результат
        processHighValue(element);
    } else {
        processLowValue(element);
    }
}

// Сортируем данные по значению
std::sort(collection.begin(), collection.end(), 
          [](const auto& a, const auto& b) { return a.value < b.value; });
 
// Находим первый элемент, превышающий пороговое значение
auto split_point = std::partition_point(collection.begin(), collection.end(),
                                       [threshold](const auto& e) { return e.value <= threshold; });
 
// Обрабатываем отдельно "малые" значения
for (auto it = collection.begin(); it != split_point; ++it) {
    processLowValue(*it);
}
 
// Обрабатываем отдельно "большие" значения
for (auto it = split_point; it != collection.end(); ++it) {
    processHighValue(*it);
}

// С ветвлением
int max_branchy(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}
 
// Без ветвления (но с плавающей точкой - будьте осторожны!)
int max_branchless_float(int a, int b) {
    return a * (a > b) + b * (b >= a);
}
 
// Без ветвления, целочисленный вариант
int max_branchless_int(int a, int b) {
    int diff = a - b;
    int mask = diff >> 31;  // Если a < b, все биты равны 1, иначе 0
    return a + (mask & (b - a));
}

// Стандартный подход с ветвлением
int abs_branchy(int x) {
    if (x < 0) {
        return -x;
    } else {
        return x;
    }
}
 
// Бесветвленный вариант для целых чисел
int abs_branchless(int x) {
    int mask = x >> 31;  // Создаёт маску: все 1 если x < 0, все 0 иначе
    return (x + mask) ^ mask;  // Трюк для получения абс. значения
}

// С ветвлением
int clamp_branchy(int x, int min_val, int max_val) {
    if (x < min_val) return min_val;
    if (x > max_val) return max_val;
    return x;
}
 
// Без ветвлений
int clamp_branchless(int x, int min_val, int max_val) {
    // Сначала ограничиваем снизу, затем сверху
    return (x > min_val ? x : min_val) < max_val ? 
           (x > min_val ? x : min_val) : max_val;
}

// С ветвлением
void process_branchy(int value, int* result) {
    if (value > 10) {
        *result = value * 2;
    } else {
        *result = value / 2;
    }
}
 
// Без ветвлений, используя побитовые операции
void process_branchless(int value, int* result) {
    // Создаём маску: все биты = 1, если value > 10, иначе все биты = 0
    int mask = !!(value > 10) * 0xFFFFFFFF;
    
    // Вычисляем оба возможных результата
    int value_doubled = value * 2;
    int value_halved = value / 2;
    
    // Используем маску для выбора нужного результата
    *result = (mask & value_doubled) | (~mask & value_halved);
}

// С ветвлением
int categorize_branchy(int value) {
    if (value < 0) return 0;
    if (value < 10) return 1;
    if (value < 100) return 2;
    return 3;
}
 
// Без ветвлений с таблицей
int categorize_branchless(int value) {
    // Создаём биты сравнения
    int bit0 = (value >= 0);
    int bit1 = (value >= 10);
    int bit2 = (value >= 100);
    
    // Комбинируем биты для получения индекса таблицы
    int index = bit0 | (bit1 << 1) | (bit2 << 2);
    
    // Таблица результатов для всех возможных комбинаций
    static const int lookup_table[] = {
        0,  // 000: value < 0
        1,  // 001: 0 <= value < 10
        2,  // 011: 10 <= value < 100
        3   // 111: value >= 100
    };
    
    return lookup_table[index];
}

// Традиционный подход с ветвлением
int count_greater_branchy(const std::vector<int>& data, int threshold) {
    int count = 0;
    for (int value : data) {
        if (value > threshold) {
            count++;
        }
    }
    return count;
}

#include <immintrin.h> // AVX2 интринсики
 
int count_greater_simd(const std::vector<int>& data, int threshold) {
    int count = 0;
    size_t size = data.size();
    size_t i = 0;
    
    // Обработка блоками по 8 элементов (AVX2 работает с 256-битными регистрами)
    if (size >= 8) {
        __m256i thresh_vec = _mm256_set1_epi32(threshold);
        __m256i count_vec = _mm256_setzero_si256();
        
        for (; i + 7 < size; i += 8) {
            __m256i data_vec = _mm256_loadu_si256((__m256i*)&data[i]);
            __m256i mask = _mm256_cmpgt_epi32(data_vec, thresh_vec);
            count_vec = _mm256_add_epi32(count_vec, 
                         _mm256_and_si256(mask, _mm256_set1_epi32(1)));
        }
        
        // Суммируем результаты из всех элементов SIMD-вектора
        int counts[8];
        _mm256_storeu_si256((__m256i*)counts, count_vec);
        for (int j = 0; j < 8; j++) {
            count += counts[j];
        }
    }
    
    // Обработка оставшихся элементов
    for (; i < size; i++) {
        count += (data[i] > threshold);
    }
    
    return count;
}

struct Particle {
    float x, y, z;
    float velocity;
    uint32_t flags;
};
 
// SIMD-версия для фильтрации частиц по нескольким критериям
int count_active_particles_simd(const std::vector<Particle>& particles) {
    // Код использует AVX для параллельной проверки нескольких частиц
    // и избегает ветвлений внутри цикла
    
    // ... (реализация опущена для краткости)
    
    return active_count;
}

// Выполнение во время выполнения (обычный рекурсивный вариант)
int factorial_runtime(int n) {
    if (n <= 1) return 1;
    return n * factorial_runtime(n - 1);
}
 
// Выполнение во время компиляции (шаблонный метапрограммный вариант)
template <int N>
struct Factorial {
    static constexpr int value = N * Factorial<N - 1>::value;
};
 
template <>
struct Factorial<0> {
    static constexpr int value = 1;
};
 
// Использование: factorial = Factorial<5>::value;

// Обобщённая версия для произвольного типа
template <typename T>
void process(const T& value) {
    // Сложная обработка с множеством условий
}
 
// Специализация для наиболее частого случая
template <>
void process<int>(const int& value) {
    // Оптимизированная обработка без ветвлений
}
 
// Специфичная версия для конкретного диапазона
template <typename T>
std::enable_if_t<std::is_floating_point_v<T>> 
processFast(const T& value) {
    // Оптимизированная версия для чисел с плавающей точкой
}

template <typename T>
auto processValue(T value) {
    // Разные ветки выполнения выбираются на этапе компиляции
    if constexpr (std::is_integral_v<T>) {
        return optimizedIntegralProcess(value);
    } else if constexpr (std::is_floating_point_v<T>) {
        return optimizedFloatProcess(value);
    } else {
        return genericProcess(value);
    }
}

__attribute__((hot)) void criticalFunction() {
    // Горячая функция - компилятор размещает её для оптимального доступа
}
 
__attribute__((cold)) void rarelyCalledFunction() {
    // Холодная функция - может быть размещена отдельно от горячего кода
}

#pragma optimize("g", on)  // Оптимизировать для скорости
void hotPath() { /* ... */ }
#pragma optimize("g", off)

// GCC/Clang
if (__builtin_expect(condition, 1)) {  // Ожидаем, что условие обычно истинно
    commonPath();
} else {
    rarePath();
}
 
// Упрощённая макро-версия
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), The condition is false.0)
 
if (likely(condition)) {
    // Чаще всего выполняется этот блок
} else {
    // Редко выполняемый код
}

#ifdef DEBUG
    void validate(int value) {
        // Подробная проверка с многими ветвлениями
    }
#else
    void validate(int value) {
        // Минимальная проверка или отсутствие проверок в релизе
    }
#endif

void processData(const Data& data) {
    #ifdef ENABLE_VALIDATION
        if (!validateData(data)) {
            handleInvalidData(data);
            return;
        }
    #endif
    
    // Основная обработка
}

template <bool ValidateInput = true>
void processData(const Data& data) {
    if constexpr (ValidateInput) {
        // Код валидации, который будет полностью 
        // исключён компилятором, если ValidateInput = false
        if (!validateData(data)) {
            handleInvalidData(data);
            return;
        }
    }
    
    // Основная обработка
}
 
// Использование:
processData<true>(data);  // С проверкой
processData<false>(data); // Без проверки

void processPacket(const Packet& packet) {
    if (packet.isCorrupt()) [[unlikely]] {
        handleCorruptPacket(packet);
        return;
    }
    
    if (packet.isControl()) [[likely]] {
        processControlPacket(packet);
    } else {
        processDataPacket(packet);
    }
}

switch (messageType) {
    case MessageType::DATA: [[likely]]
        processData(message);
        break;
    case MessageType::CONTROL:
        processControl(message);
        break;
    case MessageType::ALERT: [[unlikely]]
        processAlert(message);
        break;
}

using PacketHandler = void (*)(const Packet&);
 
// Таблица обработчиков, индексируемая типом пакета
PacketHandler handlers[MAX_PACKET_TYPE] = {
    &handleDataPacket,
    &handleControlPacket,
    &handleHeartbeatPacket,
    // ...
};
 
// Использование: единственное ветвление для проверки правильности индекса
void dispatchPacket(const Packet& packet) {
    PacketType type = packet.getType();
    if (type < MAX_PACKET_TYPE) {
        handlers[type](packet);
    }
}

// Базовый шаблонный класс (CRTP)
template <typename Derived>
class Processor {
public:
    void process(const Data& data) {
        // Предварительная обработка
        static_cast<Derived*>(this)->processImpl(data);
        // Пост-обработка
    }
};
 
// Конкретные реализации
class FastProcessor : public Processor<FastProcessor> {
public:
    void processImpl(const Data& data) {
        // Быстрая реализация без лишних ветвлений
    }
};
 
class FlexibleProcessor : public Processor<FlexibleProcessor> {
public:
    void processImpl(const Data& data) {
        // Более гибкая реализация
    }
};

// Общая функция для любого случая
template <typename T>
void process(const T& data, ProcessingMode mode) {
    // Полная реализация с проверками и ветвлениями
}
 
// Специализированная функция для наиболее частого случая
template <>
void process<int>(const int& data, ProcessingMode mode) {
    if (mode == ProcessingMode::FAST) {
        // Сверхбыстрая обработка без дополнительных проверок
        process_int_fast(data);
        return;
    }
    // Запасной вариант для других режимов
    process_int_general(data, mode);
}

void processOrder(const Order& order) {
    if (order.type == OrderType::LIMIT) {
        if (order.side == OrderSide::BUY) {
            if (order.quantity > largeOrderThreshold) {
                processLargeLimitBuy(order);
            } else {
                processSmallLimitBuy(order);
            }
        } else {
            if (order.quantity > largeOrderThreshold) {
                processLargeLimitSell(order);
            } else {
                processSmallLimitSell(order);
            }
        }
    } else if (order.type == OrderType::MARKET) {
        // Аналогичная вложенная логика...
    } else if (order.type == OrderType::STOP) {
        // Ещё больше вложенных условий...
    }
}

void processOrder(const Order& order) {
    // Используем атрибут likely для наиболее вероятного пути
    if (order.type == OrderType::LIMIT) [[likely]] {
        // Сначала проверяем самый распространенный случай
        if (order.side == OrderSide::BUY) [[likely]] {
            // Редкий случай помечаем как unlikely
            if (order.quantity > largeOrderThreshold) [[unlikely]] {
                processLargeLimitBuy(order);
            } else {
                processSmallLimitBuy(order);
            }
        } else {
            // Аналогичная структура...
        }
    } else {
        // Вынесли редкие типы в отдельный метод
        processNonLimitOrder(order);
    }
}

void renderScene(const Scene& scene) {
    for (const auto& object : scene.objects) {
        if (object.isVisible()) {
            if (object.hasTexture()) {
                if (object.isTransparent()) {
                    renderTransparentTextured(object);
                } else {
                    renderOpaqueTextured(object);
                }
            } else {
                if (object.isTransparent()) {
                    renderTransparentUntextured(object);
                } else {
                    renderOpaqueUntextured(object);
                }
            }
        }
    }
}

void renderScene(Scene& scene) {
    // Сортируем объекты по их свойствам
    scene.sortObjectsByRenderProperties();
    
    // Теперь у нас есть отдельные контейнеры для разных типов
    
    // Рендерим сначала все непрозрачные объекты с текстурами
    for (const auto& object : scene.opaqueTexturedObjects) {
        renderOpaqueTextured(object);
    }
    
    // Затем непрозрачные объекты без текстур
    for (const auto& object : scene.opaqueUntexturedObjects) {
        renderOpaqueUntextured(object);
    }
    
    // И т.д. для других категорий...
}

// Неоптимальный полиморфный подход
class RenderableObject {
public:
    virtual void render() = 0;
};
 
class TexturedObject : public RenderableObject {
public:
    void render() override { renderWithTexture(); }
};
 
// Использование
for (const auto& object : scene.objects) {
    if (object->isVisible()) {
        object->render(); // Виртуальный вызов
    }
}

Message parseMessage(const char* buffer, size_t length) {
    Message msg;
    
    // Определяем тип сообщения
    char messageType = buffer[0];
    if (messageType == 'A') {
        parseAddOrderMessage(buffer, length, msg);
    } else if (messageType == 'D') {
        parseDeleteOrderMessage(buffer, length, msg);
    } else if (messageType == 'E') {
        parseExecuteOrderMessage(buffer, length, msg);
    } else if (messageType == 'U') {
        parseUpdateOrderMessage(buffer, length, msg);
    }
    // ... и так далее для десятка типов сообщений
    
    return msg;
}

using MessageParser = void (*)(const char*, size_t, Message&);
 
// Таблица функций, индексируемая по ASCII-коду типа сообщения
MessageParser parsers[256] = {nullptr};
 
// Инициализация таблицы
parsers['A'] = parseAddOrderMessage;
parsers['D'] = parseDeleteOrderMessage;
parsers['E'] = parseExecuteOrderMessage;
// ... и т.д.
 
// Парсинг с использованием таблицы
Message parseMessage(const char* buffer, size_t length) {
    Message msg;
    char messageType = buffer[0];
    
    // Единственное ветвление — проверка валидности типа
    if (parsers[messageType] != nullptr) {
        parsers[messageType](buffer, length, msg);
    }
    
    return msg;
}