Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Скорость выполнения участка кода.  (Прочитано 500 раз)
0 Пользователей и 1 Гость смотрят эту тему.
AlexLaw
Участник

ru
Offline Offline

« : 07-10-2018 14:05 » 

Здравствуйте знатоки Делфи.
Хочется посоветоваться с вами вот по какому вопросу.
Для меня важна скорость выполнения программы и поэтому я хочу задать некоторые вопросы,
но чтобы не выглядеть попрашайкой буду предлагать свои варианты решения.
Моя цель путем обсуждения получить наиболее быстрый код.
1. Что лучше использовать для оценки скорости,
Профайлер или такты https://habr.com/post/75234/ или измерять время?
Ну и первый вопрос:
Подсчитать кол-во установленных бит в UInt64.
Мои варианты
1.Вариант
(click to show)
Код:
function CountBitsInt64_(const u:UInt64):Integer;//кол уст бит
var
i,j,k:Integer;
begin
k:=0;
             for i:=63 downto 0 do  begin
             j := (u shr i) and 1;
                       case j  of
                                1:begin
                                k:=k+1;
                                end;
                       end;
             end;
result:=k;
end;
2.Вариант
(click to show)
Код:
//Подсчет количества установленных бит в integer
 function CountBits(const Value: integer): integer;
asm
mov ECX,EAX
xor EAX,EAX
test ECX,ECX
jz @@ending
@@counting:
shr ECX,1
adc EAX,0
test ECX,ECX
jnz @@counting
@@ending:
end;
//Подсчет количества установленных бит в Int64
function CountBitsInt64(const integer64:UInt64):integer;
var
high_bit,low_bit:Longword;
i,j:integer;
begin
low_bit:=integer64;
high_bit:=integer64 shr 32;
i:=CountBits(low_bit);
j:=CountBits(high_bit);
result:=i+j;
end;

Для относительнойоценки  скорости пока использую такты
Код:
function RDTSC: UInt64;
asm
 rdtsc
end;

Так вот второй вариант немного быстрей.
Какие есть еще более быстрые варианты?
Записан
AlexLaw
Участник

ru
Offline Offline

« Ответ #1 : 07-10-2018 14:39 » 

Сразу хочу поставить следующий вопрос.
Имеются два массива
  WPieceStart: array [0..5]  of  UInt64 =(1152921504606846976,576460752303423488,9295429630892703744,2594073385365405696,4755801206503243776,71776119061217280);// начальная позиция
  BPieceStart: array [0..5]  of  UInt64 = (16,8,129,36,66,65280);

Преобразовать их в (FEN строку)-нотацию Форсайта — Эдвардса

Мой вариант
(click to show)
Код:
function U64toFen_(WP,BP:array  of  UInt64;col:Integer):WideString;
var
i,ii,j,z,swth,k:Integer;
strF,strN,strK,FenString:string;
Figure:UInt64;
begin
result:='';
strF:='KQRBNPkqrbnp';
FenString:='';
Figure:=0;
ii:=64;
      for i := 0 to 5 do begin
        Figure:=Figure or WP[i] or BP[i];
      end;
        for i:=63 downto 0 do  begin // i-номер уст бита
            j := (Figure shr i) and 1;//j-флаг уст бита
                case j  of
                     1:begin
                       for z := 5 downto 0 do begin
                         if (MaskOneBit[i] and WP[z])>0 then begin swth:=z+1;break; end;
                         if (MaskOneBit[i] and BP[z])>0 then begin swth:=z+7;break; end;
                       end;//опред тип фигуры
                     k:=ii-i;
                     StrK:=IntToStr(k-1);
                     if k=1 then StrK:='';
                     strN:=copy(strF,swth,1) + StrK;
                     FenString:=strN+FenString;
                     ii:=i;
                     end;//1
                end;//case
        if (i mod 8)=0 then begin
                     k:=ii-i;
                     StrK:=IntToStr(k);
                     if k=0 then StrK:='';
                     if i>0 then begin
                       FenString:='/'+strK+FenString;
                     end else FenString:=strK+FenString;
                     ii:=ii-k;
        end;//if
        end;//for     
  case col of
     0:FenString:=FenString+' w';
     1:FenString:=FenString+' b';
  end;
result:=FenString;
end;
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #2 : 07-10-2018 17:46 » 

Подсчет: второй вариант быстрее. И быстрее уже не будет. Еще ест табличный метод, но он может дать очень разные результаты в разных условиях.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
AlexLaw
Участник

ru
Offline Offline

« Ответ #3 : 07-10-2018 17:57 » 

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

* test1.zip (325.12 Кб - загружено 8 раз.)
* dll16092018.zip (840.07 Кб - загружено 8 раз.)
Записан
darkelf
Молодой специалист

ua
Offline Offline

« Ответ #4 : 08-10-2018 06:48 » 

Для относительнойоценки  скорости пока использую такты
Код:
function RDTSC: UInt64;
asm
 rdtsc
end;

Так вот второй вариант немного быстрей.
Какие есть еще более быстрые варианты?
Имхо, rdtsc можно использовать так явно только на одноядерных процессорах. На многоядерных или в многопроцессорных конфигурациях можно получить проблемы. В данном случае лучше пользоваться API предоставляемые ОС, что будет более портабельно (на ARM-ах команды rdtsc, например, нет) и надёжно. Если в Вашем случае подразумевается Windows, то можно воспользоваться QueryPerformanceFrequency()/QueryPerformanceCounter(), если Linux, то clock_gettime(CLOCK_MONOTONIC, ...).
« Последнее редактирование: 08-10-2018 06:50 от darkelf » Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 08-10-2018 06:52 » 

Конечно, второй вариант быстрее, но с таким же успехом можно и все переписать на асме.

Это обосновано в режиме realtime, но не в условиях ИИ, если уж так свербит скорость, то нужно рассматривать параллельные вычисления.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 09-10-2018 06:02 » 

AlexLaw, не знаю, как в дельфи, но, например, в c++ 64 раза сдвинуть переменную и посчитать сумму младших битов каждого результата сдвига - это вообще никак не отразиться на скорости. Можно в цикле.
Можно (если прямо так уж критична скорость) без цикла - 64 повторных команды: сдвиг и подсчёт переносов (код попухлее чутка). С табличным способом это сделается за 16 переходов и 8 сложений, если сделать 8 свичей по 256 значений каждый (код ещё более пухлый, хотя кто на это смотрит сейчас).
« Последнее редактирование: 09-10-2018 06:04 от Алексей++ » Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 09-10-2018 07:24 » 

Свичи — плохо, 100% вероятности промаха предсказания перехода. Это хуже, чем обращение к памяти в табличном способе.
64 повторных блока команд не быстрее цикла: удлинение кода — лишнее обращение к памяти.
Табличный способ будет быстрее цикла при условии предзагрузки таблицы в кеш.
« Последнее редактирование: 09-10-2018 07:30 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #8 : 09-10-2018 07:37 » 

RXL, если не поленюсь - проверю )
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 09-10-2018 07:56 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 09-10-2018 08:06 » 

ну лично мне цикл тоже больше по душе. Компактненько

Добавлено через 19 минут и 11 секунд:
накидал пабысраму.

В дебаге, 20 миллионов итераций
цикл     - 7 секунд
64 шага  - 7 секунд
свичи    - 2 секунды


В релизе, 10 миллиардов итераций
цикл     - 10 секунд
64 шага  - 10 секунд
свичи    - 10 секунд


число, где считались биты, везде одно и то же == 0x123456789abcdef0

Время измерял ударами пальца об стол, точность плюс-минус секунда  Краснею

короче говоря, можно использовать цикл, так как в релизе разница незаметна
« Последнее редактирование: 09-10-2018 08:26 от Алексей++ » Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #11 : 09-10-2018 08:35 » 

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

darkelf
Молодой специалист

ua
Offline Offline

« Ответ #12 : 09-10-2018 10:42 » 

Для подсчёта бит, если поддерживает процессор, можно воспользоваться командой popcnt. Для gcc/icc есть builtin-ы/instinsic-и.
Записан
AlexLaw
Участник

ru
Offline Offline

« Ответ #13 : 13-10-2018 06:04 » 

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

Она имеет вид:
(MSB) 0010…010001 (LSB)
LSB – least significant bit младший бит - a8
MSB – most significant bit старший бит -h1

Для отображения всей шахматной позиции будем использовать набор из 12 BitBoard.
Фигуры представим двумя массивами:
WPiece-для белых,
BPiece-для черных, где индекс соответствует следуещему
0-KING-Король
1-QUEEN-Ферзи
2-ROOK-Ладьи
3-BISHOP-Слоны
4-KNIGHT-Кони
5-PAWN-Пешки

Давайте начнем с ладьи.



* BaseVisible13102018.zip (153.32 Кб - загружено 4 раз.)
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #14 : 13-10-2018 12:03 » 

А цель какая? Цель всегда первична.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
AlexLaw
Участник

ru
Offline Offline

« Ответ #15 : 13-10-2018 12:50 » 

А цель какая? Цель всегда первична.
Недавно мне на глаза попалась вот такая прога https://zipproth.de/jetchess/index.html
Так вот меня поразила огромная скорость ее работы

Как видно из рисунка на глубину depth=8 она тратит всего 1,5 минуты.
Я не профессиональный программист, а любитель самоучка.
Поэтому и предложил всем миром попробовать хоть немного приблизиться к такому достижению.
К тому же у меня "замылилися" глаз.
Ну и может кому интересно поработать в команде.
как-то так.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #16 : 13-10-2018 13:47 » 

AlexLaw,

- что такое генератор шахматных ходов, что он должен делать ?

- насчёт скорости работы вообще - попробуй писать на c++ (на Qt, например, там с графикой попроще возюкаться, если что. И ассемблерные вставки не нужны будут

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

- почему нужно изобретать движок, когда их наверняка уже много. Разве что для тренировки навыков )
Записан

AlexLaw
Участник

ru
Offline Offline

« Ответ #17 : 13-10-2018 14:09 » 

AlexLaw,
- что такое генератор шахматных ходов, что он должен делать ?
он должен генерировать все легальные ходы в соответствии с шахматными правилами.
это может быть список ходов или как у меня число IUnt64 - где каждый бит - это допустимый ход
AlexLaw,

- насчёт скорости работы вообще - попробуй писать на c++ (на Qt, например, там с графикой попроще возюкаться, если что. И ассемблерные вставки не нужны будут

с++ не знаю, не изучал.
С графикой нет проблем
Визуализация доски представлена ниже.
AlexLaw,
 Как в одном бите сохранить всю информацию о фигуре ?
Выше написал, как это выглядит
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #18 : 13-10-2018 14:59 » new

AlexLaw, то есть, результат работы такого генератора для одного конкретного расположения фигур - это тридцать два 64-битных значения ?

для каждого типа фигуры можно заранее сгенерировать (один раз в начале работы программы) маску его всех его ходов из каждой клетки (это массив uint64[64] для каждого типа фигур) . Тогда генерация его текущих ходов сводится к взятию нужной маски из этого массива и вычитанию позиций всех текущих фигур. Это будет работать очень быстро

кстати, используешь ли многопоточность? Данная задача легко распараллеливается
« Последнее редактирование: 13-10-2018 15:02 от Алексей++ » Записан

AlexLaw
Участник

ru
Offline Offline

« Ответ #19 : 13-10-2018 15:10 » 

AlexLaw, то есть, результат работы такого генератора для одного конкретного расположения фигур - это тридцать два 64-битных значения ?
Да
AlexLaw,
кстати, используешь ли многопоточность? Данная задача легко распараллеливается
Нет
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #20 : 13-10-2018 15:11 » 

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

AlexLaw
Участник

ru
Offline Offline

« Ответ #21 : 13-10-2018 16:57 » 

AlexLaw,
для каждого типа фигуры можно заранее сгенерировать (один раз в начале работы программы) маску его всех его ходов из каждой клетки (это массив uint64[64] для каждого типа фигур) . Тогда генерация его текущих ходов сводится к взятию нужной маски из этого массива и вычитанию позиций всех текущих фигур.
Пока не вижу, как это может работать.

Например в начальной позиции у ферзя на d1 нет ходов, а после пешкой e2-e4, появляется ход по диагонали e2-h5.

Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #22 : 13-10-2018 17:11 » 

AlexLaw, да, я не учёл загораживание пути. Это тоже дополнительная обработка - проверЯть преграды на путях. Тем не менее, вычитание маски всё равно будет отсеивать очень много мусора. Опять же, для каждой маски можно (при её генерации) сохранить путь в приращениях, чтобы не генерировать каждый раз этот путь при проверке препятствий (это я уже в преждевременную оптимизацию ударился)

Другой путь - хранить не 64 бита, а 64 байта (к ним адресоваться проще в плане скорости, ну и 7 дополнительных битов можно использовать для чего-нибудь), тогда от фигур можно будет шагать во всех направлениях по нужным правилам, прерываясь, если там есть фигура или удар (для короля)

я вот так с ходу даже и не могу сказать, какой путь будет быстрее. Разве что всё это попробовать реализовать и сравнить
« Последнее редактирование: 13-10-2018 17:15 от Алексей++ » Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines