#c #templates #chess
#c #шаблоны #шахматы
Вопрос:
Я разрабатываю шахматный движок и работаю над генерацией ходов. Например, вот моя функция для генерации ходов для черного коня:
/** Pseudolegal moves don't take check into account. */
std::vector<uint8_t>
generate_pseudolegal_bknight_moves(std::shared_ptr<Position> position,
uint8_t square) {
assert(VALID_SQUARE(square));
assert(position->mailbox[square] == B_KNIGHT);
uint8_t candidates[8] = {
NEXT_RANK(PREV_FILE(PREV_FILE(square))),
NEXT_RANK(NEXT_RANK(PREV_FILE(square))),
PREV_RANK(PREV_FILE(PREV_FILE(square))),
PREV_RANK(PREV_RANK(PREV_FILE(square))),
NEXT_RANK(NEXT_FILE(NEXT_FILE(square))),
NEXT_RANK(NEXT_RANK(NEXT_FILE(square))),
PREV_RANK(NEXT_FILE(NEXT_FILE(square))),
PREV_RANK(PREV_RANK(NEXT_FILE(square))),
};
std::vector<uint8_t> moves;
for (int i = 0; i < 8; i ) {
uint8_t candidate = candidates[i];
uint8_t piece = position->mailbox[candidate];
if (VALID_SQUARE(candidate) amp;amp; (!IS_BLACK_PIECE(piece))) {
moves.push_back(candidate);
}
}
return moves;
}
Функция для генерации ходов белого коня очень похожа, меняются только два термина (макросы):
B_KNIGHT -> W_KNIGHT , и IS_BLACK_PIECE -> IS_WHITE_PIECE .
Я бы предпочел не дублировать функцию генерации перемещения для каждой части, но до сих пор делал это таким образом, потому что у него наименьшие издержки во время выполнения. Я мог бы включить bool is_white или что-то в аргументы и переключить термины с помощью тернарного is_white ? W_KNIGHT : B_KNIGHT , но условное условие добавило бы накладные расходы во время выполнения, которых раньше не было, и это не кажется таким элегантным. Мне было интересно, есть ли какая-нибудь функция времени компиляции, которая помогла бы мне иметь одно определение функции.
Я полагаю, я также мог бы использовать встроенные функции, чтобы попытаться уменьшить количество дублируемого кода, но мне было интересно, есть ли какая-либо альтернатива лучше, чем это.
Комментарии:
1. Почему вам не нужна дополнительная функция? Или оператор if? Как вы думаете, какие накладные расходы во время выполнения это приведет?
2. Можете ли вы точно описать, каких огромных накладных расходов вы опасаетесь, с современными процессорами с несколькими Ггц? Но, в любом случае, если вы настроены на поиск способа иметь две функции, но только один экземпляр показанной логики, это именно то, для чего нужны шаблоны в C . Знаете ли вы, что такое шаблоны и как их использовать? Просто сделайте цвет элемента параметром шаблона, и вот вам: две функции по цене одной!
3. Люди, как правило, плохо угадывают, что сделает код быстрее или медленнее. Старые теории о нотации Big-O в отношении алгоритмической сложности часто развеиваются соображениями кэша и конвейерной обработки процессора. Короче говоря, вам не следует так сильно беспокоиться о производительности. Позаботьтесь о правильности, а затем периодически используйте профилировщик для измерения производительности и определения того, где сосредоточить усилия по ускорению. Например, рассмотрите возможность использования каузального профилировщика, такого как Coz , профилировщика точек доступа, такого как Intel VTune, gprof и т. Д., Или профилировщика кэша, такого как kcachegrind.
4. Каждый бит накладных расходов имеет значение, потому что эти функции будут выполняться миллионы, если не миллиарды раз. Также я должен упомянуть, что это личный проект для обучения, поэтому, конечно, некоторые микроскопические накладные расходы в конечном счете несущественны. Однако мне интересно выяснить, как это сделать, с целью применения шаблона в другом месте.
5. Вы очень сильно идете по пути «вытягивания комара, проглатывая верблюда». Оптимизация на основе профилей на целевой платформе — единственный надежный способ ускорить код. Прогнозирование ветвлений в современных процессорах довольно хорошее, и вы не должны предполагать, что знаете, что означает «быстрее» даже на уровне выполнения процессора без измерений. В противном случае вы просто догадываетесь и, вероятно, ошибаетесь.
Ответ №1:
Если вы не хотите накладных расходов, вы можете использовать параметр шаблона и if constexpr :
enum class Color { WHITE, BLACK };
template <Color C> std::vector<uint8_t>
generate_pseudolegal_knight_moves(std::shared_ptr<Position> position,
uint8_t square) {
...
if constexpr (C == Color::WHITE) {
assert(position->mailbox[square] == W_KNIGHT);
} else {
assert(position->mailbox[square] == B_KNIGHT);
}
...
}
// Call
auto moves = generate_pseudolegal_knight_moves<Color::WHITE>(...);
Стандарт гарантирует, что условие будет оценено во время компиляции, а ложная ветвь будет отброшена.
Комментарии:
1. Это именно то, что я искал, 👍👍👍
2. @vasia Откуда ты это знаешь? Вы протестировали его и сравнили со своей собственной версией? Пожалуйста, не думайте, что вы будете генерировать более быстрый код без его тестирования.
3. @cigien Это то, что я искал . Будет ли это быстрее или нет, это отдельный вопрос.