Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 18:01

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Насколько производительно чтение словами?
Автор Сообщение
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Было бы полезно ознакомится с материалом, о которым вы упоминаете. Выложите, пож-та.
Цитата:
... дошли руки до основополагающей статьи Мура (про проблемно-ориентированный язык, 1970) ...
Думаю, лучше в отдельной теме.

Обратил :-)
Сообщение Добавлено: Ср мар 14, 2012 01:06
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
AlexF писал(а):
вот из недавних обсуждений
Дело в том, что если Вы столкнулись с проблемой оптимизации стековых обменов (и загрузок), значит Вы идете по неправильному пути. И ошибка в отслеживании поколений - лишнее тому свидетельство.
У меня тут наконец дошли руки до основополагающей статьи Мура (про проблемно-ориентированный язык, 1970). И основная идея Мура - в написании языка, на котором проблема описывается без потерь и избыточности. Т.е. появление такой избыточности, как в данном случае - свидетельство неудачного конструирования.
Писать алгоритмы "про запас", мол, пример неудачен, но принцип полезен - также порицаемая Муром глупость. Когда перед Вами встанет задача действительно что-то соптимизировать, и проц будет другим, и вводная изменится...
Кстати, обратите внимание, после всех смелых экспериментов, Вы пришли к выводам, которые я в самом начале вывел чисто умозрительно...
Сообщение Добавлено: Пн мар 12, 2012 01:34
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
chess, был не в курсе.

gudleifr, вы видимо подзабыли основной пост -- интерес состоял несколько в другом. В курсе про оптимизацию, вот из недавних обсуждений -- http://habrahabr.ru/blogs/algorithm/136616/. Скажу более, в приведенном фрагменте ошибочно реализована смена поколений. Но не в этом его и цель была.

Для интересующихся сайт, посвященный этой игре -- http://beluch.ru/life/conway.htm
Сообщение Добавлено: Пн мар 12, 2012 01:13
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Удачный пример неудачной оптимизации...
А ведь задачка-то классическая!
Изображение
Сообщение Добавлено: Вс мар 11, 2012 13:26
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
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-го байтов, поэтому дополнительного времени (сверх времени на @) не потребуется.
Сообщение Добавлено: Вс мар 11, 2012 09:46
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Спасибо, что уделили время.

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

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

С вашим итоговым выводом согласен. Мое резюме -- оптимизацию нужно делать в алгоритме: 1) уменьшить кол-во операций записи; 2) уменьшить операций чтения. Как-то так.
Сообщение Добавлено: Вс мар 11, 2012 02:56
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
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 байтов. Для большего ускорения в этом плане надо соответствующим образом изменить алгоритм.
Сообщение Добавлено: Сб мар 10, 2012 21:31
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Программа для тестирования -- усеченный вариант реализации игры "Жизнь", удалил из нее лишнее. Плюс снабдил словами для подсчета статистики. Синтетическую программу писать не стал, т.к хотелось иметь статистику на основе реальной программы.

Тестирование проводилось следующим образом:
* в слове Клетка.Значение раскоментировался тестируемая реализация;
* запускался в 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
Сообщение Добавлено: Сб мар 10, 2012 09:27
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
AlexF писал(а):
Итог -- использование стандартного слова C@ дает лучшую производительность.

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

Мне интересно. Давайте текст.
Сообщение Добавлено: Пт мар 09, 2012 17:43
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Спасибо за ответы. Появилось немножко времени, проверил все три варианты. Итог -- использование стандартного слова C@ дает лучшую производительность.

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

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

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

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

ЗЫ. Если кому интересно, могу опубликовать текст программы которой производил замеры.
Сообщение Добавлено: Пт мар 09, 2012 17:38
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Немного подправленный код выше
Код:
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
Сообщение Добавлено: Пн мар 05, 2012 21:22
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
[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
Сообщение Добавлено: Пн мар 05, 2012 17:48
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
AlexF писал(а):
Поставил опыт, заменил слова C@ на ПрочитатьБайт.

На самом деле для СПФ:
Код:
: ReadByte ( addr -- byte ) @ 0xFF AND ;
Если взять весь процесс чтения байтов, то лучше читать сразу по 8-мь байтов или по 16-ть(есть такие команды у х86).
Сообщение Добавлено: Пн мар 05, 2012 17:40
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
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
Сообщение Добавлено: Пн мар 05, 2012 17:24
  Заголовок сообщения:  Re: Насколько производительно чтение словами?  Ответить с цитатой
Себе же и ответил. Увеличения скорости не даст, даст замедление.
Поставил опыт, заменил слова C@ на ПрочитатьБайт.
Код:
: ПрочитатьБайт ( адр -- знач )
DUP
  -4 AND \ получили адрес по границу слова
  @
SWAP
  3 AND \ адрес байта в слове
  3 LSHIFT \ специализ версия 8 * -- переводим в биты
  RSHIFT
  255 AND \ очистили старшие биты
;

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

Если кто сможет переписать это слово на асм-е, было бы интересно опробовать такой вариант слова. :-)
Сообщение Добавлено: Пн мар 05, 2012 16:31

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


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