Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пн авг 20, 2018 08:30

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 14:09 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Платформа SPF 4.20, Windows 7, CPU -- Intel U7300

В своей программе необходимо произвольное чтение байта из двумерного массива. Реализовал произвольное чтение и запись значений из памяти побайтово, через слова C@ и С!

Увеличится ли производительность программы если сделать чтение из памяти словами (т.е с использованием слова @) с последующим выделением из слова нужного байта? Не сведут ли на нет возможный выигрыш в производительности накладные расходы по выделению нужного байта из прочитанного слова?

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 14:33 
За SPF не ручаюсь, но при нормальной реализации:
1) При чтении байта - по фигу. Процессор не дебил, он сам знает, как ему удобнее прочесть байт.
2) При чтении группы байтов - конечно, выигрыш будет, если Вам удастся прочесть все слово разом и так же разом его обработать. Например, вместо цикла из 4-х байтовых операций применить четыре словные операции с разными масками. Если же придется разбивать на байты, то выигрыша не будет.
3) При записи, конечно, удобнее подождать, пока накопится слово.
4) Все это копейки. Если данная операция критична по времени, от ее переписывания на языке ассемблера ничто не спасет (кроме, возможно, очень хорошего оптимизатора, который знает язык ассемблера лучше Вас).


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 15:34 
AlexF писал(а):
Платформа SPF 4.20, Windows 7, CPU -- Intel U7300
В своей программе необходимо произвольное чтение байта из двумерного массива. Реализовал произвольное чтение и запись значений из памяти побайтово, через слова C@ и С!
.


Без знания всей последовательности дальнейшей обработки
вряд ли что можно сказать. т.к. чтение С@ - это всего
одна команда в коде MOVZX EАX, Byte Ptr 0 [EАX]
и тормоз может оказаться не в этой команде:)

P.S. Вряд ли для процессора эта команда чем то тормозней
чем другие варианты. т.к. накладываются ещё куча факторов,
например таких как скорость доступа к памяти и др.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 16:31 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Себе же и ответил. Увеличения скорости не даст, даст замедление.
Поставил опыт, заменил слова C@ на ПрочитатьБайт.
Код:
: ПрочитатьБайт ( адр -- знач )
DUP
  -4 AND \ получили адрес по границу слова
  @
SWAP
  3 AND \ адрес байта в слове
  3 LSHIFT \ специализ версия 8 * -- переводим в биты
  RSHIFT
  255 AND \ очистили старшие биты
;

замедлило скорость выполнения программы на 18%.

Если кто сможет переписать это слово на асм-е, было бы интересно опробовать такой вариант слова. :-)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 17:24 
Не в сети

Зарегистрирован: Ср май 03, 2006 11:27
Сообщения: 1394
Откуда: St.Petersburg
Благодарил (а): 2 раз.
Поблагодарили: 11 раз.
AlexF писал(а):
Если кто сможет переписать это слово на асм-е, было бы интересно опробовать такой вариант слова.

Сперва следует дизассемблерировать

Код:
REQUIRE SEE lib\ext\disasm.f


: ПрочитатьБайт ( адр -- знач )
DUP
  -4 AND \ получили адрес по границу слова
  @
SWAP
  3 AND \ адрес байта в слове
  3 LSHIFT \ специализ версия 8 * -- переводим в биты
  RSHIFT
  255 AND \ очистили старшие биты
;

SEE ПрочитатьБайт
572EC7 8945FC           MOV     FC [EBP] , EAX
572ECA 25FCFFFFFF       AND     EAX , # FFFFFFFC
572ECF 8B00             MOV     EAX , [EAX]
572ED1 8B55FC           MOV     EDX , FC [EBP]
572ED4 8945FC           MOV     FC [EBP] , EAX
572ED7 8955F8           MOV     F8 [EBP] , EDX
572EDA B803000000       MOV     EAX , # 3
572EDF 2345F8           AND     EAX , F8 [EBP]
572EE2 C1E003           SHL     EAX , 3
572EE5 8BC8             MOV     ECX , EAX
572EE7 8B45FC           MOV     EAX , FC [EBP]
572EEA D3E8             SHR     EAX , CL
572EEC 25FF000000       AND     EAX , # FF
572EF1 C3               RET     NEAR


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 17:40 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
AlexF писал(а):
Поставил опыт, заменил слова C@ на ПрочитатьБайт.

На самом деле для СПФ:
Код:
: ReadByte ( addr -- byte ) @ 0xFF AND ;
Если взять весь процесс чтения байтов, то лучше читать сразу по 8-мь байтов или по 16-ть(есть такие команды у х86).

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 17:48 
[quote="AlexF"]Себе же и ответил
замедлило скорость выполнения программы на 18%.
Код:
Предсказуемо. т.к одна asm команда заменилась
последовательностью сформированной на базе Форт слов
прошедших через оптимизатор.:).

[quote="AlexF"]
Если кто сможет переписать это слово на асм-е, было бы интересно опробовать такой вариант слова. :-)[/quote]
Например так.
Не заморачиваясь с ассемблером посмотрел
как этот код выглядел бы VFХ и перенёс в SPF4
[code]
S" lib\ext\spf-asm.f" INCLUDED
HEX
CODE b@
          MOV       EDX, EAX
          AND       EAX, # -4
          AND       EDX, # 03
          SHL       EDX, # 3
          MOV       ECX, EDX
          MOV       EDX, 0 [EAX]
          SHR       EDX, CL
          AND       EDX, # 000000FF
          MOV       EAX, EDX
          RET
END-CODE
DECIMAL


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пн мар 05, 2012 21:22 
Немного подправленный код выше
Код:
CODE b@
          MOV       ECX, EAX
          AND       EAX, # -4
          AND       ECX, # 03
          SHL       ECX, # 3
          MOV       EDX, 0 [EAX]
          SHR       EDX, CL
          AND       EDX, # 000000FF
          MOV       EAX, EDX
          RET
END-CODE


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пт мар 09, 2012 17:38 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Спасибо за ответы. Появилось немножко времени, проверил все три варианты. Итог -- использование стандартного слова C@ дает лучшую производительность.

Результаты тестирования

Вариант 1) Использование стандартного слова С!
Среднее время выполнения -- 273 ms (Скорость чтения -- 120 МБ/сек)

Вариант 2) Чтение 4-х байтными словами, реализация на примитивах Форта
Среднее время выполнения -- 583 ms (Скорость чтения -- 58 МБ/сек)

Вариант 3) Чтение 4-х байтными словами, реализация на асме (последний вариант от Kopa)
Среднее время выполнения -- 558 ms (Скорость чтения -- 56 МБ/сек)

ЗЫ. Если кому интересно, могу опубликовать текст программы которой производил замеры.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Пт мар 09, 2012 17:43 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
AlexF писал(а):
Итог -- использование стандартного слова C@ дает лучшую производительность.

Вывод по первому впечатлению - некорректный.
AlexF писал(а):
ЗЫ. Если кому интересно, могу опубликовать текст программы которой производил замеры.

Мне интересно. Давайте текст.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Сб мар 10, 2012 09:27 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Программа для тестирования -- усеченный вариант реализации игры "Жизнь", удалил из нее лишнее. Плюс снабдил словами для подсчета статистики. Синтетическую программу писать не стал, т.к хотелось иметь статистику на основе реальной программы.

Тестирование проводилось следующим образом:
* в слове Клетка.Значение раскоментировался тестируемая реализация;
* запускался в cmd полученный текст программы;
* программа после каждого цикла выводит время работы;
* всего шесть циклов, после последенего выводится общая статистика.

Если есть вопросы -- задавайте.

Код:
\ Тестирование скорости чтения

0 VALUE  Вселенная
0 VALUE  Вселенная.Размер
0 VALUE  Вселенная.Ширина
0 VALUE  Вселенная.Высота

VARIABLE Тест.ОбщееВремя_ 0 Тест.ОбщееВремя_ !
VARIABLE Тест.Кол-во_        0 Тест.Кол-во_ !

WARNING 0!
WINAPI: GetTickCount KERNEL32.DLL

S" lib\ext\spf-asm.f" INCLUDED

: Клетка.Значение! ( знач номер -- )
Вселенная + C! ;

\ ---------   Чтение байта, варианты реализации

: ПрочитатьБайт ( адр -- знач )
DUP
  -4 AND \ получили адрес по границу слова
  @
SWAP
  3 AND \ адрес байта в слове
  3 LSHIFT \ специализ версия 8 * -- переводим в биты
  RSHIFT
  255 AND \ очистили старшие биты
;

\  b@ ( adr -- val )

HEX
CODE b@
          MOV       EDX, EAX
          AND       EAX, # -4
          AND       EDX, # 03
          SHL       EDX, # 3
          MOV       ECX, EDX
          MOV       EDX, 0 [EAX]
          SHR       EDX, CL
          AND       EDX, # 000000FF
          MOV       EAX, EDX
          RET
END-CODE
DECIMAL

\ --------- Здесь при проведении теста раскоментировать требуемое слово ---------
: Клетка.Значение ( номер -- знач )
\ Вселенная + b@ ;
\ Вселенная + C@ ;
Вселенная + ПрочитатьБайт ;

: Клетка.Живая? ( номер -- 0|1 )
DUP 0< IF Вселенная.Размер + THEN
DUP Вселенная.Размер > IF Вселенная.Размер - THEN

Клетка.Значение  11 =  NEGATE  ;

: Клетка.Кол-воСоседей ( номер -- кол-во )
0 ( номер кол-во )
OVER 1- Клетка.Живая? ( 0/1 ) +
OVER 1+ Клетка.Живая? +
OVER Вселенная.Ширина + Клетка.Живая? +
OVER Вселенная.Ширина + 1+ Клетка.Живая? +
OVER Вселенная.Ширина + 1- Клетка.Живая? +
OVER Вселенная.Ширина - Клетка.Живая? +
OVER Вселенная.Ширина - 1+ Клетка.Живая? +
OVER Вселенная.Ширина - 1- Клетка.Живая? +
NIP 
;

: Вселенная.Очистить
   Вселенная  Вселенная.Размер 10 FILL ;

: Вселенная.Создать ( ш в -- )
2DUP
   TO Вселенная.Высота
   TO Вселенная.Ширина
* CELL / 1+ CELLS
   DUP  TO Вселенная.Размер \ выравнивание по размеру ячейки
    ALLOCATE THROW TO Вселенная  \ выделили и очистили
Вселенная.Очистить
;

: Поколение
Вселенная.Размер 0 DO
  I Клетка.Кол-воСоседей ( номер -- ) DROP
LOOP  ;

: сменаПоколений ( кол-во -- )
   0 DO   Поколение LOOP ;

: тестРезультат
GetTickCount  - ABS 
  DUP  Тест.ОбщееВремя_ +!
  ."  Test execute time -- " . ."  ms."  CR
  Тест.Кол-во_ 1+!
;

: тестСкоростиРаботы ( кол-во -- )
GetTickCount
     10 сменаПоколений ( кол-во -- )
тестРезультат
;

: тестИтого \ Выводит усреднее время тестов
." -----------------------------------------------------" CR
." Memory size " Вселенная.Размер . ." byte" CR
."   Avg time "
      Тест.ОбщееВремя_ @ Тест.Кол-во_ @ / . ." ms" CR
."   Speed access memory "
      Тест.ОбщееВремя_ @ Тест.Кол-во_ @ / 10 /   DUP .
        ." ms" CR
."   Speed access memory "
     Вселенная.Размер 8 * SWAP / DUP .
     ." read/ms OR "  1024 / . ." MB/sec" CR
;

\ ------- запуск ----------
2048 2048 Вселенная.Создать ( ш в -- )

   тестСкоростиРаботы ( кол-во -- )
   тестСкоростиРаботы ( кол-во -- )
   тестСкоростиРаботы ( кол-во -- )
   тестСкоростиРаботы ( кол-во -- )
   тестСкоростиРаботы ( кол-во -- )
   тестСкоростиРаботы ( кол-во -- )
тестИтого
\ BYE


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Сб мар 10, 2012 21:31 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
AlexF писал(а):
Если есть вопросы -- задавайте.

1. Тупо прогнал ваш тест на моем компьютере и получил:

Вариант 1) Использование стандартного слова С@
Среднее время выполнения -- 199 ms (Скорость чтения -- 164 MB/sec)

Вариант 2) Чтение 4-х байтными словами, реализация на примитивах Форта
Среднее время выполнения -- 199 ms (Скорость чтения -- 164 MB/sec)

Только b@ определил без ваших излишеств. Дело в том, что в СПФ в младшем адресе памяти находится младший байт 32-разрядного числа, поэтому:
Код:
: b@ ( adr -- val ) @ 255 AND ;


2. Чтобы ускорить выполнение программы нужно попытаться использовать естественный паралеллизм инструкций целевого процессора. В игре Жизнь для этого можно читать сразу из нескольких ячеек памяти имеющих соседние адреса используя инструкции чтения из памяти по 8 или 16 байтов. Для большего ускорения в этом плане надо соответствующим образом изменить алгоритм.

_________________
С уважением, chess



За это сообщение автора chess поблагодарил: AlexF
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Вс мар 11, 2012 02:56 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Спасибо, что уделили время.

п.1 Возможно, вы правы. В ваших условиях (модель процессора, ОС) разницы не показало. Но основной вывод сохранился -- замена стандартного слова С@ преимуществ никаких не дает. Но результат интересный. Прежде чем опубликовать результаты несколько раз прогнал тесты. Что у вас за процессор?

п.2 Если правильно вас понял, то упрощая слово b@ вы упустили один фактор -- чтение 32-х битн слов выровненных по 32-х битному адресу. Т.е слово читается по адресу 0, 4, 8, 16 и т.д. а уже байт выделяется внутри этого слово (как бы по смещению внутри этого слова).

С вашим итоговым выводом согласен. Мое резюме -- оптимизацию нужно делать в алгоритме: 1) уменьшить кол-во операций записи; 2) уменьшить операций чтения. Как-то так.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Вс мар 11, 2012 09:46 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
AlexF писал(а):
Что у вас за процессор?

IntelCore2 4300 @ 1,80GHz
AlexF писал(а):
п.2 Если правильно вас понял, то упрощая слово b@ вы упустили один фактор -- чтение 32-х битн слов выровненных по 32-х битному адресу. Т.е слово читается по адресу 0, 4, 8, 16 и т.д. а уже байт выделяется внутри этого слово (как бы по смещению внутри этого слова).

Не понял Вас.
Большинство инструкций процессора x86(работа с памятью) работают с невыровненными адресами. К ним относится и инструкция mov reg, [reg], которая используется в слове @:

SEE @
Код:
CODE @
5525EC 8B00             MOV     EAX , [EAX]
5525EE C3               RET     NEAR
END-CODE
Поэтому для addr(см. ниже) не имеет значения выровненный он или невыровненный:

Код:
CREATE addr  1 C, 2 C, 3 C, 4 C, 5 C, 6 C, 7 C, 8 C,

addr     @ 255 AND .
addr 1+  @ 255 AND .
addr 2+  @ 255 AND .
addr 3 + @ 255 AND .
addr 4 + @ 255 AND .
addr 5 + @ 255 AND .
addr 6 + @ 255 AND .
addr 7 + @ 255 AND .
( 1 2 3 4 5 6 7 8 )

Что касается : b@ @ 255 AND; , то 255 AND может выполняться параллельно с @ в части обнуления разрядов регистра 1-го, 2-го, 3-го байтов, поэтому дополнительного времени (сверх времени на @) не потребуется.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Насколько производительно чтение словами?
СообщениеДобавлено: Вс мар 11, 2012 13:26 
Удачный пример неудачной оптимизации...
А ведь задачка-то классическая!
Изображение


Вернуться к началу
  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB