Forth
http://fforum.winglion.ru/

*определить количество значащих байт в числе
http://fforum.winglion.ru/viewtopic.php?f=19&t=1213		 Страница 2 из 2
Автор:  Forthware [ Пн мар 24, 2008 21:44 ]
Заголовок сообщения: 
Хм... Думаю пора открывать методы тестирования раз у наших Атлонов такое разногласие вышло. :)
Мой был довольно топорный, грубый и приблизительный. Выглядело оно где-то так:
Код:
WINAPI: GetTickCount   kernel32.dll
: TEST1 GetTickCount 100000000 0 DO 1 I 3 AND 3 LSHIFT LSHIFT SB DROP LOOP GetTickCount SWAP - CR . ;
: TEST2 GetTickCount 100000000 0 DO 1 I 3 AND 3 LSHIFT LSHIFT SB1 DROP LOOP GetTickCount SWAP - CR . ;
: TEST3 GetTickCount 100000000 0 DO 1 I 3 AND 3 LSHIFT LSHIFT SB2 DROP LOOP GetTickCount SWAP - CR . ;
Задержка на подготовку аргументов и выполнение цикла не учитывалась, но учивыя что она приблизительно одинакова для всех тестов, разница в производительности еще больше чем полученные результаты.
Обратите внимание, что аргумент генерируется таким образом, чтобы количество чисел с одним, двумя, тремя и четырьмя байтами было одинаковое. Кроме того, числа с одинаковым количеством байт никогда не идут подряд, что, вместе с одинаковой частотой, дает надежду сбить предсказания ветвлений (хотя есть сомнения насколько успешно).
Если есть желание использовать случайные числа, имея, например, слово RNDM возвращающее случайное число от 0 до 2^32 с линейным распределением, формирование аргумента надо делать следующим образом:
Код:
... 1 RNDM 0x18 AND LSHIFT SB1 ...
Или что-то в этом роде, поскольку непосредственно используя случайное число, мы получаем вероятность 4 байтного аргумента в 2^24 (~16млн) раз больше чем 1 байтного.

А как тестировали вы?
Автор:  chess [ Вт мар 25, 2008 10:28 ]
Заголовок сообщения: 
Forthware писал(а):
Хм... Думаю пора открывать методы тестирования раз у наших Атлонов такое разногласие вышло.

Вот как делал я.
Код:
REQUIRE IDN ~chess\assm\sp-assm.f

: dt1
DUP A^A CPUID        \  вызываем команду CPUID,
                     \  после выполнения которой все
                     \  предыдущие инструкции
                     \  гарантированно сошли к конвейера
                     \  и потому никак не могут повлиять
                     \  на результаты замеров

DA=TSC               \  вызываем инструкцию RDTSC, которая
                     \  возвращает в регистре EAX младшее
                     \  двойное слово текущего значения
                     \  Time Stamp Counter 'a
\ Ваш код
0xFFFFFFFF
DUP 0xFFFF0000 AND
IF 0xFF000000 AND IF 4 ELSE 3 THEN
ELSE 0xFF00 AND IF 2 ELSE 1 THEN THEN

DUP A^A CPUID        \ еще раз выполняем команду CPUID
                     \ чтобы все предыдущие инструкции
                     \ гарантированно успели покинуть
                     \ конвейер(чтобы RDTSC не начала выполняться раньше
                     \ окончания нашего фрагмента кода)

DA=TSC               \ вызываем инструкцию RDTSC для чтения
                     \ нового значение Time Stamp Count

ROT - CR .           \ вычисляем разность второго и первого
                     \ замеров, тем самым определяя реальное
                     \ время выполнения
                     \ фрагмента кода
;

К сожалению, даже этот, рекомендованный[Агнер Фог], код все равно не годится для измерения
времени выполнения фрагмента кода, поскольку полученный с его помощью результат
представляет собой полное время выполнения фрагмента, т. е. его латентность,
а не пропускную способность для фрагмента кода, впрочем при однократном использовании кода это в первом
приближении подойдет. Код еще не в кэше, поэтому это худшее время исполнения.


Код:
: dt
DUP A^A CPUID DA=TSC

\ мой код
0xFFFFFFFF
A=H\A 3 RSHIFT 1+

DUP A^A CPUID DA=TSC
ROT - CR .
;

STARTLOG
dt dt1

лог для ATHLON
Код:
71
94
Ok ( 4 4 )
Автор:  chess [ Вт мар 25, 2008 10:52 ]
Заголовок сообщения: 
ygrek писал(а):
Если вы уверены что есть такой эффект и для вас это важно, то почему бы это не исправить (если есть желание)?

Важно-неважно, причем здесь это, эффект то есть. Зачем писать оптимизатор, зачем выравнивать код - вот в чем
вопрос.
Можно конечно разделить словарь на область для данных и кода и компилировать с учетом этого. Но я думаю можно это и много чего учесть при переходе к СПФ-64.
Доделывать СПФ-32, точнее переделывать - гораздо затратнее. Это только мое мнение.
Автор:  Forthware [ Вт мар 25, 2008 12:59 ]
Заголовок сообщения: 
Подтверждаю. У меня вышло 72 и 85 соответственно. Таким образом осталось решить какой метод тестирования более обьективен. :)
chess писал(а):
полученный с его помощью результат представляет собой полное время выполнения фрагмента, т. е. его латентность,
а не пропускную способность для фрагмента кода, впрочем при однократном использовании кода это в первом приближении подойдет.
В реальных приложениях нас конечно же волнует именно пропускная способность. А вот насчет достаточности "первого приближения" есть сомнения. Во первых, какое возможно отклонение при таком "приближении"? Во вторых, результаты получились достаточны близкими, а на CoreDuo одинаковы, поэтому при последующих итерациях результат может стать противоположным.
Поэтому, мне кажется, что лучше все-таки считать время, а не такты, и не однократного исполнения одной последовательности с одним аргументом и выпорожненными конвейерами, декодерами и кешем, а в реальном коде, при многократных повторениях. Ведь если в реальности вы сможете ощутить разницу в времени выполнения программы из за того что применен тот или инной алгоритм определения количества байт в числе, то только потому, что данное слово будет исполнено огромное количество раз, и при этом на его выполнение потратится не менее 5-10% от общего времени исполнения программы. Подобный сценарий, мне кажется, более адекватно представлен в моем варианте тестирования. Если же исполнение нашего слова будет составлять меньше 1% от общего времени выполнения кода, то разницу определить будет совершенно невозможно. Как считаете?

ЗЫ Вы мои эксперементы у себя повторить пробовали?
Автор:  Forthware [ Вт мар 25, 2008 13:24 ]
Заголовок сообщения: 
chess писал(а):
ygrek писал(а):
Если вы уверены что есть такой эффект и для вас это важно, то почему бы это не исправить (если есть желание)?
Важно-неважно, причем здесь это, эффект то есть. Зачем писать оптимизатор, зачем выравнивать код - вот в чем
вопрос.
Не ссорьтесь! Вы оба правы. Изменение распределения памяти однозначно не повредило бы SPF. Но с другой стороны, от того что память распределена не оптимально, оптимизатор и выравнивание кода не теряют своей актуальности. Почему? Самое простое - потому что они реально повышаеют производительность при таком распределении памяти какое есть сейчас. Больше того, тормоза от перемешивания данных и кода возникают довольно редко, поэтому носят характер риска а не перманентной деградации производительности. С другой стороны, разработка оптимизатора и эффективных алгоритмов очень важные вещи, поскольку в случае перехода на архитектуру с раздельной памятью, они останутся актуальными, мы сможем использовать тот-же, отработаный оптимизатор. Поэтому мысль что "оптимизация не нужна раз есть риск потерять гораздо больше прозводительности" аналогична мысли: "раз у меня не McLaren F1, то нет смысла переключаться с первой передачи". :D
Автор:  chess [ Вт мар 25, 2008 13:31 ]
Заголовок сообщения: 
Forthware писал(а):
ЗЫ Вы мои эксперементы у себя повторить пробовали?

Попробовал:
Код:
WINAPI: GetTickCount   kernel32.dll
: TEST1 GetTickCount 100000000 0 DO 1 I 3 AND 3 LSHIFT LSHIFT SB DROP LOOP GetTickCount SWAP - CR . ;
: TEST2 GetTickCount 100000000 0 DO 1 I 3 AND 3 LSHIFT LSHIFT SB1 DROP LOOP GetTickCount SWAP - CR . ;
TEST1
TEST2
Результат:
Код:
1766
937
Думаю истина где-то посредине. :) Не факт, что код всегда будет циклиться и не факт, что в цикле кэш при этом не будет переписываться. Кроме того для Intel-процессоров есть кэш трассы, он тоже скажется на замедлении кода.
В общем все по ситуации, если код не циклится, то моя оценка верней, если циклится то ваша.
Автор:  Forthware [ Вт мар 25, 2008 14:04 ]
Заголовок сообщения: 
Все, разобрался! :D Выходит Атлон, гад, умеет предсказывать и повторяющиеся последовательности разных ветвлений с одинаковой частотой. Поэтому, мой предыдущий тест прошел слишком удачно, что я и подозревал. Дошли таки руки попробовать со случайными числами, вот:
Код:
: TEST1 GetTickCount SWAP 0 DO 1 rndm 0x1F AND LSHIFT SB DROP LOOP GetTickCount SWAP - CR . ;

В таком варианте, результаты тестирования, практически совпали с результатами вашего теста! И так, мой вариант, проигрывает по скорости в среднем около 20%. :)

ЗЫ В реальной жизни, однако, большинство строк имеют длину счетчика в 1 байт, поэтому опять же, предсказание ветвлений может сделать свое дело. ;)
Автор:  WingLion [ Вт мар 25, 2008 21:11 ]
Заголовок сообщения: 
Самое смешное, как мне кажется, заключается в том, что считать количество значащих байт при множественной работе со строками придется на много меньше времени, нежели что-то делать с этими строками, а по сему, стремление к минимальному времени исполнения подобного кусочка кода выглядит как подтирание следа от капли воды на капоте машины только что врезавшейся в столб.
Автор:  Forthware [ Вт мар 25, 2008 21:51 ]
Заголовок сообщения: 
WingLion писал(а):
Самое смешное, как мне кажется, заключается в том, что считать количество значащих байт при множественной работе со строками придется на много меньше времени, нежели что-то делать с этими строками, а по сему, стремление к минимальному времени исполнения подобного кусочка кода выглядит как подтирание следа от капли воды на капоте машины только что врезавшейся в столб.
Так точно! :lol: Обычный спортивный интерес, не более. :D
Автор:  Alexander [ Чт мар 27, 2008 15:01 ]
Заголовок сообщения: 
Если честно, то вопрос заданный в теме не совсем ясен, 1-2-3-4 - это число Одна тысяча двести тридцать четыре или порядок хранения числа в памяти, и где значащий байт хранится по младшим или по старшим адресам???
Автор:  Forthware [ Чт мар 27, 2008 16:49 ]
Заголовок сообщения: 
Alexander писал(а):
Если честно, то вопрос заданный в теме не совсем ясен, 1-2-3-4 - это число Одна тысяча двести тридцать четыре или порядок хранения числа в памяти, и где значащий байт хранится по младшим или по старшим адресам
Под количеством "значащих байтов" подразумевается максимальная разрадность данных (в байтах, или кратная 8 битам), достаточная для хранения данного числа. Вот собственно. :shuffle; И только вы не поняли... :roll: :lol:
Автор:  Alexander [ Пт мар 28, 2008 08:57 ]
Заголовок сообщения: 
Forthware писал(а):
Под количеством "значащих байтов" подразумевается максимальная разрадность данных (в байтах, или кратная 8 битам), достаточная для хранения данного числа. Вот собственно. И только вы не поняли...

Тут вопрос очень интересен, в плане представления отрицательных чисел, в которых как известно
старшие биты (байты) кодируются 1 (-1),так сказать знаковое расширение чисел, и сказать что они ничего не значат???
Серьезно вопрос то
mOleg писал(а):
определить наиболее быстрым образом текущую разрядность числа

А мне всегда казалось что в Форте разрядность чисел измеряется ячейками и размерами ячеек.
:lol: А без двоичного логарифма не обойтись?
Автор:  Forthware [ Пт мар 28, 2008 13:15 ]
Заголовок сообщения: 
Alexander писал(а):
Тут вопрос очень интересен, в плане представления отрицательных чисел, в которых как известно старшие биты (байты) кодируются 1 (-1),так сказать знаковое расширение чисел, и сказать что они ничего не значат???
Изначально речь шла о счетчиках строки, которые, как вы понимаете, являются числами без знака (u). Так что нет никакого "знакового расширения". :)
Alexander писал(а):
А мне всегда казалось что в Форте разрядность чисел измеряется ячейками и размерами ячеек.
То о чем вы говорите есть разрядность области памяти, и равна она максимальной разрядности числа которое в ней можно сохранить. Разрядность конкретного числа никак от этого не зависит. Например, 1, в любом представлении, будь то 64 битный дабл, или 8 битный символ, имеет разраядность 1 бит. Будете возражать? :twisted:
Alexander писал(а):
А без двоичного логарифма не обойтись?
Дык обошлись вроде. :roll: :lol:
Автор:  Alexander [ Пт мар 28, 2008 14:00 ]
Заголовок сообщения: 
Возражать я не буду напротив теперь мне ясен вопрос
КАК ПОСЧИТАТЬ ЧИСЛО БИТ, ДЛЯ КОДИРОВАНИЯ КОНКРЕТНОГО ЧИСЛА.
Поправьте меня, если я опять не понял.
Автор:  Forthware [ Пт мар 28, 2008 19:06 ]
Заголовок сообщения: 
Alexander писал(а):
Поправьте меня, если я опять не понял.
Гдето так:
КАК ПОСЧИТАТЬ ЧИСЛО БИТ достаточное, ДЛЯ представления КОНКРЕТНОГО ЧИСЛА
Страница 2 из 2 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/