Решение первой задачи из 1st Tech Interview

Задача 1

Есть несколько тредов-воркеров, которые обрабатывают сообщения в бесконечном цикле. Точка входа в тред — функция PollEvents. Она получает свой уникальный instrument_id (от 0 до MAX_INSTRUMENTS_COUNT) и занимается только им. Какие проблемы производительности есть в этом коде?

/* there are a few workers (threads), each receives messages with the following scheme:
{
  "e": "string", // event_type: "price" or "announcement"
  "id": int32,   // msg id, only for e = price
  "T": int64,    // exchange time
  "s": int32,    // instrument id
  "data": string // current price (eg. "25.3519") or announcement message
}
each worker handles messages with the same symbol "s" */
 
struct PriceUpdate {
    double price;
    int64_t timestamp;
};

struct Announcement {
    std::string message;
    int64_t timestamp;
};

struct Item {
    int last_id = -1;
    double min_price = -1;
    int64_t timestamp = -1;
};

std::vector<Item> prices_info(MAX_INSTRUMENTS_COUNT); // shared between threads
 
/* worker code starts here */
 
std::variant<PriceUpdate, Announcement> GetNextMessage(int instrument_id) {
    std::string message = ReadNextMessage();
    auto parsed = ParseJson(message);
    std::string data = parsed.GetField<std::string>("data");
    int64_t ts = parsed.GetField<int64_t>("T");
    if (parsed.GetField<std::string>("e") == "announcement") {
        return Announcement{data, ts};
    } else {
        int id = parsed.GetField<int>("id");
        if (id < prices_info[instrument_id].last_id && prices_info[instrument_id].last_id != -1) {
            throw std::runtime_error("Unexpected id " + std::to_string(id));
        }
        double price = std::stod(data);
        if (prices_info[instrument_id].min_price < 0 || price < prices_info[instrument_id].min_price) {
            prices_info[instrument_id].min_price = price;
        }
        prices_info[instrument_id].last_id = id;
        prices_info[instrument_id].timestamp = ts;
        return PriceUpdate{price, ts};
    }
}

void PollEvents(int instrument_id) {
    for (;;) {
        std::variant<PriceUpdate, Announcement> next_message;
        try {
            next_message = GetNextMessage(instrument_id);
        } catch (const std::exception& e) {
            LogError(e);
            continue;
        }
        std::visit([&](auto&& event) {
            using T = std::decay_t<decltype(event)>;
            if constexpr(std::is_same<T, PriceUpdate>) {
                HandlePriceUpdate(event);
            } else {
                HandleAnnouncement(event);
            }
        }, next_message);
    }
}

Решение

Проблема 1: обратите внимание на порядок полей в структуре Item. За счет паддинга размер структуру будет больше, чем мог бы. Впрочем, здесь это неважно и ниже мы увидим, почему.

struct Item {
    int last_id = -1;
    double min_price = -1;
    int64_t timestamp = -1;
};

Следует обращать внимание на порядок следования полей во входных и выходных данных. Иногда это может помочь компилятору оптимизировать копирование (в случае, если соседние поля и их паддинги совпадают). В данном случае можно адаптировать порядок полей в структуре Item к порядку во входных данных – так, например, копирование полей id и T может быть выполнено при помощи 1 инструкции процессора (но все еще стоит обращать внимание на размеры полей и паддинги). Улучшение незначительно, но при других входных и выходных данных эффект может быть более заметным.

Проблема 2: вектор используется из нескольких тредов. Ниже по коду видно, что мы можем читать и писать одновременно в соседние элементы этого вектора, а это значит, что возможен false sharing. Поэтому нужно задать выравнивание для структуры.

struct alignas(std::hardware_destructive_interference_size) Item {
    int last_id = -1;
    double min_price = -1;
    int64_t timestamp = -1;
};

std::vector<Item> prices_info(MAX_INSTRUMENTS_COUNT); // shared between threads

Проблема 3:

    std::string message = ReadNextMessage();
    auto parsed = ParseJson(message);
    std::string data = parsed.GetField<std::string>("data");

Здесь и далее используется std::string, что приводит к аллокациям памяти и копированию. В зависимости от интерфейсов, которые предоставляют ридер и парсер, можно попробовать использовать вместо этого string_view. Например, если парсер внутри себя хранит для каждого ключа смещение и длину строки, то мы можем получить значительное улучшение:

    std::string_view data = parsed.GetField<std::string_view>("data");

Для коротких строк (например, если price = "25.3519") использование std::string все же может быть оправдано, поскольку сработает SSO и весь объект строки будет лежать на стеке.

Проблема 4:

double price = std::stod(data);

Функция stod должна понимать разные форматы записи числа с плавающей точкой. Если нам заранее известен формат, то мы можем использовать, например, from_chars или свою реализацию, вместо того, чтобы использовать "тяжелую" общую функцию.

Проблема 5:

Что, если мы можем сделать предположение о частоте типов сообщений, которые мы получаем? Например, Announcement приходит довольно редко, и в основном мы получаем PriceUpdate. Тогда можно пометить ветки как likely или unlikely.

    if (parsed.GetField<std::string>("e") == "announcement") [[unlikely]] {
        return Announcement{data, ts};
    }

Проблема 6:

        if (id < prices_info[instrument_id].last_id && prices_info[instrument_id].last_id != -1) {
            throw std::runtime_error("Unexpected id " + std::to_string(id));
        }

Хорошо ли выбрасывать исключения? Вообще говоря, это зависит от того, как часто это происходит. Если это вполне вероятная ситуация, то, возможно, лучше возвращать специальное значение или обрабатывать ошибку на месте, поскольку обработка исключения — довольно тяжелая операция. Если же это действительно исключительная ситуация, то никогда не вызываемая инструкция throw почти ничего не стоит, и лучше оставить ее. В данном случае, исключение бросается, когда приходит невалидное сообщение, что, вероятно, не должно происходить часто, поэтому исключение здесь уместно.

Проблема 7:

std::visit([&](auto&& event) {
            using T = std::decay_t<decltype(event)>;
            if constexpr(std::is_same<T, PriceUpdate>) {
                HandlePriceUpdate(event);
            } else {
                HandleAnnouncement(event);
            }
        }, next_message);

Что здесь происходит? Вероятно, после подстановки всех шаблонов, это превратится во что-то вроде этого (псевдокод):

if(next_message.type == PriceUpdate) {
    HandlePriceUpdate(next_message);
} else {
    HandleAnnouncement(next_message);
}

То есть использование std::variant приносит нам ветвление. Можно ли этого избежать? Один из способов — избавиться от std::variant вообще, и вызывать соответствующие хендлеры прямо из GetNextMessage. А если мы хотим задавать хендлеры снаружи, то будем передавать их как шаблонные параметры (таким образом они всё ещё будут инлайниться, в отличие от передачи их как коллбеков в обычных параметрах).

template<void A(const Announcement&), void U(const PriceUpdate&)>
void GetNextMessage(int instrument_id) {
    // ...
    if (parsed.GetField<std::string>("e") == "announcement") {
        A(Announcement{data, ts});
    } else {
        // ...
        U(PriceUpdate{price, ts});
    }
}

void PollEvents(int instrument_id) {
    // ...
    GetNextMessage<handleAnnouncement, handlePriceUpdate>(instrument_id);
}