Оптимизация без шаблонов

Question

Я пишу шахматный движок, и у меня есть функция, которая выглядит следующим образом:

U64 find_moves(Piece type, Team side, uint8_t square, U64 occupied) {
    switch (type) {
        case PAWN: {
            U64 result = 0;
            result |= occupied & bb_normal_moves::pawn_caps[side][square];
            if (!(occupied & bb_normal_moves::pawn_moves_x1[side][square])) {
                result |= bb_normal_moves::pawn_moves_x1[side][square];
                if (!(occupied & bb_normal_moves::pawn_moves_x2[side][square])) {
                    result |= bb_normal_moves::pawn_moves_x2[side][square];
                }
            }
            return result;
        }
        case KNIGHT:
            return bb_normal_moves::knight_moves[square];
        case BISHOP:
            return bb_magics::bishop_moves(square, occupied);
        case ROOK:
            return bb_magics::rook_moves(square, occupied);
        case QUEEN:
            return bb_magics::bishop_moves(square, occupied) | bb_magics::rook_moves(square, occupied);
        case KING:
            return bb_normal_moves::king_moves[square];
    }

    return 0; // Can't happen
}

По сути, она делегирует вызов другой функции в зависимости от параметра type.Во многих местах вокруг программы эта функция вызывается после циклического перебора различных значений Piece, которые, как представляется, равны enum.

К сожалению, это означает, что эта функция вызывается каждый раз в этом цикле,так что много времени ЦП тратится впустую на эту ветвление функции.

Я хотел бы изменить эту функцию, чтобы компилятор оптимизировал вызовы:

template <Piece type> U64 find_moves(Team side, uint8_t square, U64 occupied)

, но затеммои циклы не будут компилироваться, поскольку цель вызова функции не может быть решена во время компиляции.

Есть ли способ оптимизировать эту функцию без ручного развертывания всех моих циклов?

РЕДАКТИРОВАТЬ: Здесьпример одного из циклов, который вызывает find_moves:

for (uint8_t piece = 1; piece < 6; piece++) {
    move.info.piece = piece;
    U64 bb_piece = board.bb_pieces[team][piece];

    while (bb_piece) {
        uint8_t from = pop_bit(team, bb_piece);
        move.info.from = from;

        U64 bb_targets = find_moves((Piece) piece, team, from, board.bb_all) & mask;

        while (bb_targets) {
            uint8_t to = pop_bit(x_team, bb_targets);
            move.info.to = to;

            buf[buf_size++] = move;
        }
    }
}

Answer 1

Учитывая, что значения вашего перечисления Piece от 1 до 6, вы можете использовать шаблоны, std::make_index_sequence, std::index_sequence, чтобы развернуть.

Извините, но я могу подготовить только минимальный пример (нет move, нет board и т. д.).

Если вы вызываете что-то как

foo(std::make_index_sequence<6U>{});

в foo(), вы можете вызвать другую функцию с одиночными значениями (вы пометили C ++17, чтобы вы могли использовать свертывание шаблонов)

template <std::size_t ... Ps>
void foo (std::index_sequence<Ps...> const &)
 { (bar<Ps>(), ...); }

Моя идея заключается в том, что в bar() вы можете поместить содержимое тела цикла for (uint8_t piece = 1; piece < 6; piece++) вашего примера;Я размещаю только вызов тривиальной (без других аргументов) функции find_moves().

template <std::size_t Ps>
void bar ()
 { find_moves<pieces(1+Ps)>(); }

Теперь вы можете разработать шесть шаблонных функций find_moves(), используя полную специализацию (я пишу только std::cout сообщения; вы, используя другие аргументы, может поместить содержимое case s в ваш switch.

template <pieces P>
void find_moves ();

template <>
void find_moves<Pawn> ()
 { std::cout << "Case Pawn" << std::endl; }

template <>
void find_moves<Knight> ()
 { std::cout << "Case Knight" << std::endl; }

template <>
void find_moves<Bishop> ()
 { std::cout << "Case Bishop" << std::endl; }

template <>
void find_moves<Rook> ()
 { std::cout << "Case Rook" << std::endl; }

template <>
void find_moves<Queen> ()
 { std::cout << "Case Queen" << std::endl; }

template <>
void find_moves<King> ()
 { std::cout << "Case King" << std::endl; }

Ниже приведен полный пример компиляции

#include <iostream>
#include <utility>
#include <type_traits>

enum pieces { Pawn = 1, Knight, Bishop, Rook, Queen, King };

template <pieces P>
void find_moves ();

template <>
void find_moves<Pawn> ()
 { std::cout << "Case Pawn" << std::endl; }

template <>
void find_moves<Knight> ()
 { std::cout << "Case Knight" << std::endl; }

template <>
void find_moves<Bishop> ()
 { std::cout << "Case Bishop" << std::endl; }

template <>
void find_moves<Rook> ()
 { std::cout << "Case Rook" << std::endl; }

template <>
void find_moves<Queen> ()
 { std::cout << "Case Queen" << std::endl; }

template <>
void find_moves<King> ()
 { std::cout << "Case King" << std::endl; }

template <std::size_t Ps>
void bar ()
 { find_moves<pieces(1+Ps)>(); }

template <std::size_t ... Ps>
void foo (std::index_sequence<Ps...> const &)
 { (bar<Ps>(), ...); }

int main ()
 {
   foo(std::make_index_sequence<6U>{});
 }