Агоритмы с довесками в 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
на лету, но сути это в целом не меняет, там внутри будет по сути то же самое.