Здравствуйте, Mystic, Вы писали:

M>Здравствуйте, WolfHound, Вы писали:

WH>>Здравствуйте, Mystic, Вы писали:

M>>>Моему извращенному уму нативный код писать проще и приятнее.
WH>>А мне нет ибо нативность отбирает кучу умственных ресурсов на вопросы не связанные непосредственно с задачей.

M>>>А верифицируемость накладывает кучу ограничений, которые надо потом думать, как разрулить.
WH>>Какие конкретно ограничения?

M>Я мыслю алгоритмы большей частью как манипуляцию с байтами и битами. У меня есть память, я к ней обращаюсь как хочу. Захочу, прочитаю из нее указатель, захочу прочитаю из нее целое значение. Записи с вариантами и т. п. Попытка начать писать тот же шахматный движок под .NET быстро натолкнулась на то, что без постоянного использования unsafe крайне проблематично выделить под хэш фрагмент памяти, разбить его на блоки одинакового размера, представить его в виде списка свободных блоков. Вместо того, чтобы за пять секунд написать то, что я хочу, я вынужден тратить уйму времени на вопросы не связанные непосредственно с задачей.

Это решается кастомными аллокаторами памяти. К сожаления, тот же .NET (наколько я знаю) такой возможности пока не предоставляет. Но тут надо померять, может и со стандартным все будет пучком

M>Например, я хочу хранить некоторые данные как последовательность заканчивается нулевым символом. Так мне удобнее всего в данном случае. Но, соотвественно, код, который берет по одному символу пока не наткнется на нулевой, уже не будет безопасным.

Мммм. А зачем? Чем хранение длины хуже?

M> И т. п. Да и просто получить первый (последний) бит, установленный в единицу, оптимальным способом, уже ассемблерная вставка.

if ((x & 0x01) != 0) — я уверен — компилятор разберется. Самая элементарная оптимизация, ее умели еще компиляторы 70-ых.

P.S. Но в целом я согласен, хотелось бы иметь возможность дешево кастить сырую память к value-типам без лишних копирований (тут правда надо подумать, как себя вести если структура содержит ссылки). Или это уже можно и я чего-то не знаю?

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, Mystic, Вы писали:

G>Просто ты пытаешься программировать на уровне абстракции ниже, чем предоставляет .NET, от этого и проблемы.
Да, я пытаюсь программировать на том уровне абстракции, на котором мне удобнее

M>>Да и просто получить первый (последний) бит, установленный в единицу, оптимальным способом, уже ассемблерная вставка.
G>Оптимальность ассемблерного кода очень сильно зависит от процессора. А формула a&0x1 или a&0x80 может компилироваться хоть в AND, хоть BT, хоть еще во что-то, что является оптимальным по мнению компилятора (а он гораздо лучше знает).

На самом деле речь идет о BSR и BSF. Вряд-ли компилятор цикл for преобразует в BSR, не говоря уже о более оптимальном

static const FLD LSB_Magic[64] = 
{
   A8, B4, E1, H5, E8, B2, E2, G5,
   D8, H4, F7, G2, A7, E3, C3, F5,
   C8, C4, F1, C7, E7, A3, G6, F3,
   H8, D4, G1, E6, B6, E4, H1, E5,
   B8, A4, F8, D1, C1, G7, B7, B1,
   A2, D7, D2, H6, A1, F6, C6, H3,
   G4, G8, H7, C2, F2, A5, H2, D6,
   D3, A6, B5, B3, G3, C5, D5, F4
};

#define pop_lsb(x)  pop_lsb_inner(&x)

static inline FLD pop_lsb_inner(U64* pb)
{
   if (*pb == 0)
      return NF;

   U64 lsb = *pb ^ (*pb - 1);
   unsigned int foldedLSB = ((int) lsb) ^ ((int)(lsb>>32));
   int ind = (foldedLSB * 0x78291ACF) >> (32-6); // range is 0..63

   *pb &= ~lsb;
   return LSB_Magic[ind];
}

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Mystic, Вы писали:

M>>Я мыслю алгоритмы большей частью как манипуляцию с байтами и битами. У меня есть память, я к ней обращаюсь как хочу. Захочу, прочитаю из нее указатель, захочу прочитаю из нее целое значение.
WH>Зачем читать целое как указатель или указатель как целое?

Хотя бы для экономии.

M>>Записи с вариантами и т. п.
WH>Ты про алгебраические типы? http://en.wikipedia.org/wiki/Algebraic_data_type

Да, об этом. На также и об эффективной их реализации

M>>Попытка начать писать тот же шахматный движок под .NET быстро натолкнулась на то, что без постоянного использования unsafe крайне проблематично выделить под хэш фрагмент памяти, разбить его на блоки одинакового размера, представить его в виде списка свободных блоков. Вместо того, чтобы за пять секунд написать то, что я хочу, я вынужден тратить уйму времени на вопросы не связанные непосредственно с задачей.
WH>Чем System.Collection.Generic.Dictionary<Key, Value> не подошол?

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

M>>И т. п. Да и просто получить первый (последний) бит, установленный в единицу, оптимальным способом, уже ассемблерная вставка.
WH>А чем не подходит x & ~(x — 1)?

Точнее номер первого установленного бита.

Здравствуйте, jedi, Вы писали:

J>Это решается кастомными аллокаторами памяти. К сожаления, тот же .NET (наколько я знаю) такой возможности пока не предоставляет. Но тут надо померять, может и со стандартным все будет пучком
Кастомный аллокатор небезопасно...

M>>Например, я хочу хранить некоторые данные как последовательность заканчивается нулевым символом. Так мне удобнее всего в данном случае. Но, соотвественно, код, который берет по одному символу пока не наткнется на нулевой, уже не будет безопасным.
J>Мммм. А зачем? Чем хранение длины хуже?
Небольшая оптимизация. Но даже хранение длины не сделает код безопасным.

M>> И т. п. Да и просто получить первый (последний) бит, установленный в единицу, оптимальным способом, уже ассемблерная вставка.
J>if ((x & 0x01) != 0) — я уверен — компилятор разберется. Самая элементарная оптимизация, ее умели еще компиляторы 70-ых.
Я имел в виду индекс бита. Желательно с одновременным установлением его в нуль. Типа получаем номер бита из битборда, как во всех генераторах ходов.

J>P.S. Но в целом я согласен, хотелось бы иметь возможность дешево кастить сырую память к value-типам без лишних копирований (тут правда надо подумать, как себя вести если структура содержит ссылки). Или это уже можно и я чего-то не знаю?

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, Mystic, Вы писали:
M>>Я мыслю алгоритмы большей частью как манипуляцию с байтами и битами.
MC>Ну будет у тебя верифицированная работа с битовым массивом (матрицей, кубом?). Делов-то.
А если он содержит ссылки внутри себя? Плюс потеря производительность на дополнительных проверках...

Здравствуйте, Mystic, Вы писали:

M>Точнее номер первого установленного бита.
Наверное проще создать аналог BitArray над массивом Uint64

Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, Mystic, Вы писали:

M>>Точнее номер первого установленного бита.
S>Наверное проще создать аналог BitArray над массивом Uint64

BitArray не нужен. Шахматная доска содержит 64 клетки. Таким образом UInt64 мне вполне достаточно, обобщать шахматы на доски других размеров я не собираюсь. Просто, во-первых, их много (на шахматную позицию надо битовая маска пешек, коней, слонов, ладей, ферзей и всех фигур и все за белых и черных + заполняемость хеша позиций на современных машинах порядка нескольких миллионов позиций в секунду). Во-вторых, эта операция при генерации ходов на вес золота.

Здравствуйте, Mystic, Вы писали:

M>Здравствуйте, gandjustas, Вы писали:

G>>Здравствуйте, Mystic, Вы писали:

G>>Просто ты пытаешься программировать на уровне абстракции ниже, чем предоставляет .NET, от этого и проблемы.
M>Да, я пытаюсь программировать на том уровне абстракции, на котором мне удобнее
ты демонстрируешь парадокс блаба. Тебе кажется что удобнее, потому что ты не имеешь опыта написания на высоком уровне абстракции.

M>>>Да и просто получить первый (последний) бит, установленный в единицу, оптимальным способом, уже ассемблерная вставка.
G>>Оптимальность ассемблерного кода очень сильно зависит от процессора. А формула a&0x1 или a&0x80 может компилироваться хоть в AND, хоть BT, хоть еще во что-то, что является оптимальным по мнению компилятора (а он гораздо лучше знает).
M>На самом деле речь идет о BSR и BSF. Вряд-ли компилятор цикл for преобразует в BSR, не говоря уже о более оптимальном


M>

M>//код скипнут

Так напиши тоже самое без указательной магии на C#, в чем проблема?

G>>>А подход с компиляцией при установке, как драйверы в Singularity, такие проблемы не решает?
T>>На 99%.
T>>Один процент на то, что потребуется ассемблер. А он потребуется.
G>Ну создателям singularity пока не потребовался. Есть вероятность что и в дальнейшем не потребуется.

Создатели сингулярности пока запустили её только на десятке машин с одной системой команд.

Есть практически 100% вероятность, что когда они запустят на нескольких разных архитектурах, да ещё и с разными требованиями (от микроконтроллера до суперкомпьютера, как на Линуксе), им понадобится ассемблер.

Что-то у меня двойственное впечатление складывается от твоих вопросов. Похоже, тебя интересует не чьё-то мнение, а исключительно своё.

Вот этот вопрос, вопрос про типы

Автор: gandjustas
Дата: 19.06.09

в ветке про TDD. Везде сценарий один и тот же: "x?", мой "y." и твой "а нифига, всё равно x." Без каких-либо признаков даже поверхностных размышлений.

Здравствуйте, gandjustas, Вы писали:

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

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

G>Так напиши тоже самое без указательной магии на C#, в чем проблема?

Проблема в том, что я хочу видеть в машинном коде BSR и BSF.

Здравствуйте, thesz, Вы писали:

G>>>>А подход с компиляцией при установке, как драйверы в Singularity, такие проблемы не решает?
T>>>На 99%.
T>>>Один процент на то, что потребуется ассемблер. А он потребуется.
G>>Ну создателям singularity пока не потребовался. Есть вероятность что и в дальнейшем не потребуется.

T>Создатели сингулярности пока запустили её только на десятке машин с одной системой команд.
T>Есть практически 100% вероятность, что когда они запустят на нескольких разных архитектурах, да ещё и с разными требованиями (от микроконтроллера до суперкомпьютера, как на Линуксе), им понадобится ассемблер.
А для чего может понадобиться ассемблер, кроме установки служебных регистров, работы с портами и прерываниями?
В Singularity они необходимость ассемблера обошли таким образом: коду драйвера передается экземпляр класса, который отвечает за всю низкооуровневую работу (обращения к этому классу вполне могут компилиться в нужный нативный код).
Почему нельзя будет для других архитектур процессоров сделать другие классы, наследники какого-либо базового?

T>Что-то у меня двойственное впечатление складывается от твоих вопросов. Похоже, тебя интересует не чьё-то мнение, а исключительно своё.
T>Вот этот вопрос, вопрос про типы

Автор: gandjustas
Дата: 19.06.09

в ветке про TDD. Везде сценарий один и тот же: "x?", мой "y." и твой "а нифига, всё равно x." Без каких-либо признаков даже поверхностных размышлений.
Я вроде написал что "есть вероятность", а не то что я "стопудово уверен, а кто не согласен идут в жопу"

Здравствуйте, Mystic, Вы писали:

M>Здравствуйте, gandjustas, Вы писали:

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

M>Писать программы для работы с базами данных на более высоком уровне абстракции---пожалуйста. Шахматный движок---увольте, мне удобнее его писать на чистом С. Нет, я допускаю, что я не умею пользоваться высокими абстракциями. Для меня это в случае разработки шахматного движка это программирование шиворот навыворот: я знаю как должен выглядеть код на самом низком уровне, и начинаю мыслить о том, как бы мне написать высокоуровневую абстрактную конструкцию, чтобы она скомпилировалась во что-то очень близкое к тому, что я ожидаю...
Ну тогда пиши код на низкоуровневом языке, и инвокай его из высокоуровневого, раз тебе так тяжело работать с абстракциями.

G>>Так напиши тоже самое без указательной магии на C#, в чем проблема?
M>Проблема в том, что я хочу видеть в машинном коде BSR и BSF.
Это действительно проблема. Только это проблема в тебе, а не в .NET или еще чем-то.

Здравствуйте, gandjustas, Вы писали:

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

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

Моему извращенному уму нативный код писать проще и приятнее.

G>>>Так напиши тоже самое без указательной магии на C#, в чем проблема?
M>>Проблема в том, что я хочу видеть в машинном коде BSR и BSF.
G>Это действительно проблема. Только это проблема в тебе, а не в .NET или еще чем-то.

Может быть и во мне, но сильных шахматных движков, написанных на .NET, я не знаю...

Здравствуйте, Mystic, Вы писали:

WH>>Зачем читать целое как указатель или указатель как целое?
M>Хотя бы для экономии.
Экономии чего?

WH>>Ты про алгебраические типы? http://en.wikipedia.org/wiki/Algebraic_data_type
M>Да, об этом. На также и об эффективной их реализации
Если они поддержаны виртуальной машиной напрямую то эффективность может быть такой что упаришься руками догонять.

M>Основная проблема производительность.
А конкретно?

M>Выделение/освобождения памяти для объектов фиксированного размера сводится к нескольким ассемблерным командам.
Так с ГЦ та же фигня

M>Вторая проблема в том, что дерево позиций представляет собой более взаимосвязанную структуру. Когда хэш позиций заполняется больше определенного значения, его нужно чистить.
А что метод Clear уже отменили?

M>Ну и проще удалить объект из двусвязного списка, чем искать, в каких списках он присутсвует, и оттуда удалять.
Чё? Как связано удаление из одного списка и из нескольких?

M>Плюс заботится о том, чтобы все ссылки на этот объект обнулились, а то он, не освободится...
ГЦ работает не так. Обнулять все ссылки не нужно. Достаточно чтобы объект не был достижим.
В любом случае и в нативе нужно заботиться о том чтобы на мертвый объект не было ссылок иначе

Здравствуйте, Mystic, Вы писали:

G>>>>Так напиши тоже самое без указательной магии на C#, в чем проблема?
M>>>Проблема в том, что я хочу видеть в машинном коде BSR и BSF.
G>>Это действительно проблема. Только это проблема в тебе, а не в .NET или еще чем-то.

M>Может быть и во мне, но сильных шахматных движков, написанных на .NET, я не знаю...
Наверное потому что их никто не делает.

"сила" шахматного алгоритма зависит от реализации оценки позиции и алгоритма перебора вариантов ходов, ковыряние с битами в таких алгоритмах противопоказано. Наносекундные вычисления с битами вероятнее всего незаметны будет.

Здравствуйте, Mystic, Вы писали:

MC>>Ну будет у тебя верифицированная работа с битовым массивом (матрицей, кубом?). Делов-то.
M>А если он содержит ссылки внутри себя?

Битовый массив?

M>Плюс потеря производительность на дополнительных проверках...

Она зависит от системы типов и вообще информации о семантике, доступной для компилятора.
Какие нужны дополнительные проверки, чтобы получить индекс первой единицы в битовом массиве?

Здравствуйте, WolfHound, Вы писали:

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

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

Еще преимущество одного вызова VirtualAlloc состоит в том, что я могу легко сделать дамп всего хэша, а потом проанализировать его какой-нить внешней своей тулзовиной (писанной на С#, с использованием высоких идей абстракции), которая бы вместо битбордов рисовала диаграммы и т. п.

Где у меня неправильные представления?

Здравствуйте, gandjustas, Вы писали:

G>"сила" шахматного алгоритма зависит от реализации оценки позиции и алгоритма перебора вариантов ходов, ковыряние с битами в таких алгоритмах противопоказано. Наносекундные вычисления с битами вероятнее всего незаметны будет.

Насколько я знаю, во всех сильнейших движках используется генератор ходов на основе bitboard. Васик, когда начал писать свою рыбу, первым делом переписал фруктовский движок на битборды. Разве только Fritz их не использует. Сравни по производительности:

1) Берем битовый маску пешек.
2) Делаем AND с битовой маской всех полей, кроме вертикали "а"
3) Сдвигаем битовую маску на 7
4) Делаем AND с битой маской фигур соперника

И мы получили сразу половину взятий пешками.

Аналогично

1) Берем битовую маску ладей
2) Получаем номер поля idx первой ладьи
3) Сдвигаем битовую маску всех фигур на 1 + idx & 0x38, и берем младшие шесть бит результата. Получаем mask
4) По таблице получаем все возможные ходы ладьи по горизонтали.

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

G>"сила" шахматного алгоритма зависит от реализации оценки позиции и алгоритма перебора вариантов ходов, ковыряние с битами в таких алгоритмах противопоказано. Наносекундные вычисления с битами вероятнее всего незаметны будет.

Спасибо, рассмешил.
Меня вот удивляет откуда такие знатоки всего беруися?

На всякий случай. Товарища Мистика я знаю лично и знаком с его реальными результатами в написании движков (в частности, очень неплохого шашечного).
А Вы, товавищ gandjustas, чем прославились на этом поприще?

Здравствуйте, Klapaucius, Вы писали:

K>Какие нужны дополнительные проверки, чтобы получить индекс первой единицы в битовом массиве?

Да никаких не надо, надо выполнить одну ассемблерную команду.