Агоритмы с довесками в compile-time

Сейчас делал простой класс для кэширования кусков больших данных, полученных из какого-нибудь абстрактного источника данных большого размера. Класс хранит в себе std::map, отображающий смещения в источнике данных в куски закэшированных данных.

Хочется, чтобы в классе была функция, которая по смещению и размеру возвращает вектор из регионов, в каждом из которых указан размер и кусок данных, если в этом регионе данные загружены. Что-нибудь типа такого (эффективность из-за копий данных пока оставим в стороне):

struct region {
    size_t size;
    std::vector<char> data;
}

std::vector<region> read(uint64_t offset, size_t size) {
    // тут довольно громоздский алгоритм поиска и итерации по `std::map`
    // и копирования нужных кусков данных
}

И, как обычно бывает в таких случаях, настает момент, когда хочется получить не данные, а просто список регионов с информацией о том, загружены ли данные в кэш. Что-то вроде этого:

struct region_info {
    size_t size;
    bool is_fetched;
}

std::vector<region_info> read_info(uint64_t offset, size_t size);

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

Что делали обычно раньше в таких случаях? Просто делали одну функцию read, в которую параметром передавали флаг, сообщающий о том, нужно ли возвращать данные или только информацию о регионе, а в структуру region добавляли флаг is_fetched. И если данные возвращать не надо, то во всех элементах возвращаемого вектора переменные data возвращались пустые.

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

В современном C++ можно делать правильное решение очень просто:

template <bool fetch_data>
auto read_info(uint64_t offset, size_t size) {
    using region_t = std::conditional_t<fetch_data, region, region_info>;
    using ret_type = std::vector<region_t>;

    ret_type res;

    // цикл прохода по элементам внутри std::map
    for (...) {
        region_t reg;

        // где-то внутри цикла при добавлении очередного элемента
        if constexpr (fetch_data) {
            reg.data = ...;
        }

        res.push_back(reg);
    }

    return res;
}

Никакого дублирования кода алгоритма или шаблонной магии, всё просто и понятно. Результат получается практически идеальный: невозможно словить баг, передав неверный флаг в функцию read, или попытавшись использовать переменную data структуры region там, где не предполагается, что она будет валидная.

Сейчас задумался в каких ещё языках такое можно легко делать? Насколько я помню, в Haskell вроде бы должно получиться, но там и весь алгоритм будет рекурсивный, как и в старом C++. Какие ещё? Rust?

P.S. Вообще говоря, если делать правильно в современном C++, то вместо возврата вектора надо возвращать range, который будет конструировать элементы типа region на лету, но сути это в целом не меняет, там внутри будет по сути то же самое.

comments powered by Disqus