C ++, используя один байт для хранения двух переменных

Question

Я работаю над представлением шахматной доски, и я планирую сохранить ее в массиве 32 байта, где каждый байт будет использоваться для хранения двух фигур. (Таким образом, требуется только 4 бита на штуку)

Выполнение этого таким образом приводит к накладным расходам на доступ к определенному индексу платы. Как вы думаете, этот код можно оптимизировать или использовать совершенно другой метод доступа к индексам?

C ++

char getPosition(unsigned char* c, int index){
    //moving pointer
    c+=(index>>1);

    //odd number
    if (index & 1){
        //taking right part
        return *c & 0xF;
    }else
    {
        //taking left part
        return *c>>4;
    }
}


void setValue(unsigned char* board, char value, int index){
    //moving pointer
    board+=(index>>1);

    //odd number
    if (index & 1){
        //replace right part
                 //save left       value only 4 bits
        *board = (*board & 0xF0) + value;
    }else
    {
        //replacing left part
        *board  = (*board & 0xF) + (value<<4);
    }
}


int main() {

    char* c = (char*)malloc(32);

    for (int i = 0; i < 64 ; i++){
        setValue((unsigned char*)c, i % 8,i);
    }

    for (int i = 0; i < 64 ; i++){
        cout<<(int)getPosition((unsigned char*)c, i)<<" ";

        if (((i+1) % 8 == 0) && (i > 0)){
            cout<<endl;
        }


    }


    return 0;
}

Меня одинаково интересуют ваши мнения относительно шахматных представлений и оптимизации описанного выше метода как отдельной проблемы.

Большое спасибо

EDIT

Спасибо за ваши ответы. Некоторое время назад я создал игру в шашки, в которой я использовал 64-байтовое представление доски. На этот раз я пробую разные методы, просто чтобы посмотреть, что мне нравится. Память не такая большая проблема. Бит-доски, безусловно, в моем списке, чтобы попробовать. Спасибо

Answer 1

В этом проблема преждевременной оптимизации. Где ваша шахматная доска заняла бы 64 байта для хранения, теперь она занимает 32. Что это действительно мешает вам? Вы действительно проанализировали ситуацию, чтобы увидеть, нужно ли вам сохранять эту память?

Предполагая, что вы использовали один из наименее оптимальных методов поиска, прямой поиск AB до глубины D без эвристики, и вы генерируете все возможные перемещения в позиции перед поиском, тогда абсолютный максимальный объем памяти, необходимый для вашей доски, будет равен sizeof. (доска) * W * D. Если мы предположим, что W = 100 и D = 30 достаточно велики, то у вас в памяти будет 3000 плат на глубине D. 64 К против 32 К ... Это действительно того стоит?

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

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

Что касается представления, которое я предпочитаю ... Мне нравятся битборды. Много серьезных измерений не проводилось, но я сравнил два сделанных мною двигателя: один битборд и один массив, и один битборд был быстрее и мог достигать гораздо больших глубин, чем другой.

Answer 2

Позвольте мне первым указать на потенциальную ошибку (в зависимости от компиляторов и настроек компилятора). И ошибки в том, что преждевременная оптимизация - это зло:

   //taking left part
    return *c>>4;

если * c отрицательно, то >> может повторить отрицательный старший бит. т.е. в двоичном виде:

0b10100000 >> 4 == 0b11111010

для некоторых компиляторов (т. Е. Стандарт C ++ оставляет за компилятором решение - как переносить старший бит, и является ли символ знаком или без знака).

Если вы хотите продолжить работу со своими упакованными битами (и позвольте мне сказать, что вам, вероятно, не стоит беспокоиться, но это зависит от вас), я бы предложил обернуть упакованные биты в класс и переопределить [] такой, что

board[x][y] 

дает вам распакованные биты. Затем вы можете легко включать и выключать упаковку, используя тот же синтаксис в любом случае. Если вы укажете на перегрузки оператора, это должно быть так же эффективно, как и код, который у вас есть сейчас.

Answer 3

Ну, 64 байта - это очень маленький объем оперативной памяти. Тебе лучше просто использовать символ [8] [8]. То есть, если вы не планируете хранить тонну шахматных досок. Использование char [8] [8] облегчает (и ускоряет) доступ к плате и выполняет более сложные операции на ней.

Если вам все еще интересно хранить доску в упакованном представлении (либо для практики, либо для хранения большого количества досок), я говорю, что вы «делаете это правильно» в отношении битовых операций. Возможно, вы захотите встроить аксессоры, если хотите набрать скорость, используя ключевое слово inline.

Answer 4

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

1. Какая сторона должна двигаться дальше?
2. Может ли белый и / или черный замок короля и / или ферзя?
3. Можно ли взять пешку пассивно?
4. Сколько ходов прошло с момента последнего хода пешки и / или захвата?

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

Answer 5

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

AFAIK, вы можете обнаружить, что хранение шахматной фигуры в 8 байтах будет более эффективным. Даже если вы вернетесь на 15 шагов глубины, размер кэша L2 вряд ли будет ограничением, но смещение ОЗУ может быть . Я предполагаю, что правильная обработка шахматной доски будет включать функции Expand () и Reduce () для преобразования между представлениями доски во время различных частей алгоритма: некоторые могут быть быстрее при компактном представлении, а некоторые наоборот. Например, кэширование и алгоритмы, включающие хеширование по составу двух соседних ячеек, могут быть полезны для компактной структуры, все остальное нет.

Я бы также подумал о разработке некоторого вспомогательного оборудования, например, платы FPGA или кода GPU, если производительность так важна.

Answer 6

Достаточно ли места для рассмотрения, когда нельзя просто использовать полный байт для представления квадрата? Это облегчило бы доступ к программе и, скорее всего, быстрее, поскольку манипуляции с битами не требуются.

В противном случае, чтобы убедиться, что все идет гладко, я бы позаботился о том, чтобы все ваши типы были без знака: getPosition возвращает беззнаковый символ и квалифицировал все ваши числовые литералы как «U» (например, 0xF0U), чтобы убедиться, что они всегда интерпретируются как беззнаковые , Скорее всего, у вас не возникнет проблем с подписью, но зачем рисковать на архитектуре, которая ведет себя неожиданно?