Мелкие задачки для крупных мозгов 9

_BC_ >

Хороший вопрос, наверное там же, где и 100b для своего кода =)

(на самом деле мой код выдаёт 011b)





Black_mirror



А разве должен быть 0?

Если base = 01h, то младший индекс - это 0^й бит байта 10000000h, а старший индекс - это 31^й бит байта 10000003h

 

S_T_A_S_

Действительно не должно я почему-то думал что индекс бита со знаком

 

S_T_A_S_

_BC_

Я нашел значения при которых ваш код работает не правильно:

base=2,index_low=0FFFFFFF0h,index_high=00000000Fh

 

Final Ver?

ebp=base, edi=hiindex,esi=loindex

Код (Text):

1.     xor eax, eax
2.     dec eax
3.     cdq
4.     lea ebx, [edi+ebp*8]
5.     btr eax, ebx
6.     lea ecx, [esi+ebp*8]
7.     shr esi, 3
8.     shr edi, 3
9.     add esi, ebp
10.     add edi, ebp
11.     xor edi, esi
12.     cmp edi, 4
13.     rcl eax, 1
14.     adc eax, eax
15.     clc
16.     ror edx, cl
17.     adc eax, eax

 

xor eax, eax

dec eax

тут наверно лучше

or eax,-1

тот же размер но одна инструкция (для скорости).

 

А дубово-прозрачный вариант не подходит ?

Код (Text):

1. ;eax = ptr to data, ecx = lower index, edx = higher index
2.     lea ecx,[ecx+eax*8]
3.     lea eax,[edx+eax*8]
4.     test cl,31
5.     setnz dl       ;бит 0
6.     xor ecx,eax
7.     test ecx,-32   ;для экономии байтиков можно shr ecx,5 (но PIV будет дольше соображать)
8.     setz cl        ;бит 2
9.     inc eax
10.     test al,31
11.     setnz al       ;бит 1
12.     ;осталось собрать все в al со сдвигом - возможны варианты, для примера так:
13.     add cl,cl
14.     add al,cl
15.     add al,al
16.     add al,dl
17.     ;movzx eax,al ;если результат д.б. в r32

 

ОТК забракует

 

> "ОТК забракует "



ОТК рекомендовало избегать "тупых чрезмерных проверок". Но для получения 3 независимых бит результата требуется не менее 3-х независимых проверок. Можно сделать их в лоб в соответствии с "мат.лог.моделью", а можно соревноваться в способах их завуалированной реализации на х86.



> "построить наибыстрейшую модель при средне-ожидаемом входе"

А в чем измеряем быстроту ? Просто в количестве команд или учитываем особенности семейств P6, NetBurst, AMD ?

 

А как насчет переполнения ?

Проверь вот это:

base=2,index_low=0FFFFFFF0h,index_high=00000000Fh

 

leo >

Для экономии можно написать и and ecx,-32





All



можно ли что-то выгадать исходя из условий:



lo <= hi

A - B <= A xor B



мне кажется, что как-то можно обойтись 2мя проверками, только вот не пойму, как )

 

_BC_

> "А как насчет переполнения ?"



Не понял, кому адресован вопрос. Если мне, то отвечаю:

Если индексы - unsigned, то это или некорректные входные данные (т.к. lo > hi), или некорректная постановка задачи (если нужны int64 или int128, то это нужно указывать особо).

Если - signed, то все правильно:

lo_bit_ptr = 2*8-16 = 0

hi_bit_ptr = 2*8+15 = 31 = 1Fh

Результат:

бит 0 = 0 - младший выравнен (младшие 5 бит = 0)

бит 1 = 0 - старший является старшим битом dword (младшие 5 бит = 11111b = 31)

бит 2 = 1 - принадлежат одному dword (старшие биты с 6 по 31 совпадают)

 

leo

Ну хорошо, занавесим на все проблемы с переполнением и забудем про 35 бит в битовом адресе.

ebp=base, edi=hiindex,esi=loindex

Код (Text):

1.     or  eax, -1 ; 83 C8 FF
2.     cdq
3.     lea ebx, [edi+ebp*8]
4.     btr eax, ebx
5.     lea ecx, [esi+ebp*8]
6.     xor ebx, ecx
7.     cmp ebx, 32
8.     rcl eax, 1
9.     adc eax, eax
10.     clc
11.     ror edx, cl
12.     adc eax, eax

 

The Svin

Индексы они со знаком или без? команды bt, bts, btr считают что без знака.

 

Индексы без знака. А вот bt* считают что со знаком если обращаются к памяти.

 

Код будет работать некорректно в отношении определения младшего индекса если у абсольютного младшего (база*8+младший) окажутся единицы в младших пяти битах.



Попробуй в дебагере к примеру такой код

xor eax,eax

xor ecx,ecx

stc

ror eax,cl

Не смотря на то, что в eax не будет вообще единиц - мы с удивлением пронаблюдаем CF=1 после ror eax,cl

 

Ну ты нашел что разбирать. Это было промежуточное (временное) решение. Смотри лучше мой последний вариант.

 

Мой вопрос остался без ответа - в каких попугаях оценивать быстродействие.

Наверное, никого не удивит, что на P4 последний изящный вариант _BC_ работает почти в 3 раза медленее, чем дубовый. Avoid complex instructions - па-а-нымаешь

 

Последний правильный.

На разных начиная хоть 486. Sorry, интен кончился пишу с линии для сироток Но когда ты задал вопрос - там была цитата моя, и меня в тупик поставило соседство моей цитаты и твоего вопроса, я вобщем связать никак не мог их, и потому отложил ответ.

В цитате говорится об определении наиболее вероятного варианта. Т.е. для начала - математике, апроксимации и тут уж непричём никакая модель. Но определить трудно без дополнительных вводных. Пусть размер массива не превышает 16 мб. Индексы могут быть любые в этом диапозоне от 0 до 16*1024*1024-1

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

Поэтому я никак не мог понять причём тут модели процессоров и вероятность входных данных.

Но маленький код тоже интересно.

 

leo



Прямо таки в 3 раза медленнее ?

И вообще... The smaller -- the better

 

Сравним продвинутый вариант _BC_ с дубовым вариантом leo по размеру и быстродействию.



Размер:

a) Вариант _BC_

В оригинале 27 байт, но это с мусорными старшими битами в al\eax. Если нужен чистый вариант,

то +3 байта на and r,7 - итого 30.

б) Вариант leo

Учтем замечания и заменим test eax,-32 на and и сэкономим 3 байта. В тоже время inc eax заменим на двухбайтную not eax или add al,1 (т.к. inc это мелочная экономия в обмен на ложную зависимость по флагам). Тогда, если результат может быть в al (или с мусором в eax), то получаем 35 байт. Если результат должен быть в eax, то можно заменть 2 байта test al,31 на 3 байта and eax,31, т.е. итого 36 байт.



Теперь посмотрим, как сказывается экономия 5-6 байт на быстродействии.

Для начала лирическое ИМХО. Во-первых, экономия байтов достигается за счет использования комплексных инструкций, т.е. мы перекладываем часть своего кода на microcode-ROM процессора и таким образом меняем байты на такты (достаточно посмотреть, сколько тактов поедает "волшебная" инструкция BTR). Во вторых, экономия байтов достигается за счет отказа от хранения промежуточных результатов - результаты сравнений крутятся во флагах и передается по цепочке инструкций. Отсюда зависимость по данным и флагам, и ограничение возможностей параллельного исполнения.



Посмотрим цифирьки для интеловских камешков:

Код (Text):

1.  
2. ----------------------------------------------------------------------      ---------
3.                 i486     --- P\PMMX ---     PPro\P2\P3     ------- P4 (F2x) --------
4.                такты     такты pairable     мопы порты     latency throghput  мопы
5. ----------------------------------------------------------------------      ---------
6. lea r,[r+r*i]    2         1     uv           1   p0         ?(4)     1       (2)
7. lea r,[r+r*i]    2         1     uv           1   p0         ?(4)     1       (2)
8. cdq              3         2     No           1   p0         1       0.5      (2)
9. btr r,r          6         7     No           1   p0/1       8(6)     1       (2)
10. rcl r,1          3         1     u            2   p0         4        1       (1)
11. adc r,r          1         1     u            2   p0/1       8(6)     3       (4+4ROM)
12. clc              2         2     No           1   p0/1       ?(10)    2       (3)
13. ror r,cl         3         4     No           1   p0         4        1       (2)
14. adc r,r          1         1     u            2   p0/1       8(6)     3       (4+4ROM)
15. ----------------------------------------------------------------------      ---------
16. setcc           3-4        1     No           1   p0/1       5       1.5      (3)
17. ----------------------------------------------------------------------      ---------
18. (Для P4 две цифры - первая по IA-32, вторая в скобках - по А.Фогу).

P4 Northwood (CPUID = 0F2x)

Измерения rdtsc (wintest.exe) показывают:

a) 36 тиков (40 с завершающим and), b) 12 тиков (16 c завершающим movzx)

(на Northwood'e rdtsc выдает результаты с дискретом в 4 тика).

Если нарисовать диаграммки с учетом возможного перекрытия и распараллеливания, то результат примерно согласуется с табличкой:

a) 4(lea)+6(btr)+4(rcl)+6(adc)+10(clc)+6(adc) = 36

b) 4(lea)+5(setcc)+2*1.5(setcc)+1.5(add-ы) < 14

!!! На P4 серьезным тормозом для варианта _BC_ является команда CLC, хотя сохранять флаги перед ror edx,cl совершенно не нужно. Если пожертвовать один байт и заменить clc на xor ebx,ebx, то сразу получаем ~20 тиков вместо 36 (последующим ror и adc нечего ждать и они перекрываются с предыдущим adc -> выигрыш 16 тиков !!!).



P6 family (PPro\P2\P3)

Измерения на P3 (с выравниванием на 16) показывают:

a) 16 тиков, b) 8 тиков.

(реально м.б. на 1 больше из-за погрешности измерения - распараллеливания последней инструкции со служебной командой xor eax,eax).

Также примерно совпадает с табличными данными:

a) практически ничего не распараллеливается, поэтому получаем просто сумму тактов по таблице = 15 (плюс 1-2 такта на хитрости декодирования).

б) 10 инструкций (со второй lea до add cl,cl) распараллеливаются и выполняются за 5 тиков, в итоге имеем 1(lea)+5+3(add'ы) = 9 тиков.



Для P1\PMMx результатов измерений у меня нет, но по табличке видно, что в варианте а) много медленных и неспариваемых инструкций, поэтому в первом приближении можно взять сумму тактов по таблице. Получается порядка 20-24. В варианте б) все команды однотактные и спариваемые (кроме setcc и test cl,31), поэтому будем иметь < 14 тиков.



Ну для i486 только оценки по таблице:

a) 23+(3..4) = 26..27

b) 4(lea)+3*(3..4)(setcc)+9 = 22..25

Получаем примерно одинаковые результаты. Значит на i486 экономия байтиков обошлась без заментых потерь и вариант a) является бесспорным лидером: The smaller -- the better



Выводы (имхо)

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

2. Для P6 family и старше дубовый вариант выполняется за время < задержки непредсказанного перехода (~ длины конвейера), поэтому привлекать статистику входных данных и использовать переходы по условию по-видимому нецелесообразно.