bsl_zcs

Отвык я от твоего стиля. Ну ты как начал, так я и продолжу ;)

Очень интересно. Я бы намного меньше удивился, если бы было наоборот. ;) Просто потому, что приведённый код на писюках не работает. Ему нужна big endian архитектура.

Работает. Проверка на прямое равенство (поправлено после поста Black_mirror - заплевали, ироды :()

Кстати, а чем Solaris x86 отличается от какого-нить виндовса на той же машине, для кода на С без единого системного вызова? ;)


А ты почитай SPARCV9.pdf :) Авось и с требованиями выравнивания при доступах к памяти ознакомишься ;) Все для квалификации полезнее :)

И уже по самому коду: в коде от "кросс-платформенного программиста" могло бы вместо 4 стоять sizeof(long). ;)

Размер лонга на V9 - 8 байт. Ты прав. Надо было sizeof. Не так уж трудно и поправить :)

А ещё можно было обойтись одним комплектом указателей, кастить их в первом цикле, и нахаляву получить адреса остатка. Ну это уже так, к слову... ;)

:-)>

volodya

bsl_zcs совершенно прав:

  char s1[]="AABA";
  char s2[]="AAAB";
  int z=mycmp(s1,s2,4);//-1
  z=strcmp(s1,s2);//1

Black_mirror

Заплевали. Совсем заплевали :(((
ОК. Тогда только для сравнения АБСОЛЮТНО ИДЕНТИЧНЫХ строк.
Функция писалась для нахождения совпадений - одинаковых последовательностей в генах.

bsl_zcs

Не люблю быть голословным. Я таки "распылюсь" (как сказал Эдмонд) и сброшу кое-что через пару дней. Там будет ответ. Если одним словом - софт пайп. И такты там видны невооруженным глазом.
Я вчера записал это для двухбайтного случая, чтобы упростить сравнение. Посчитал такты. Однобайтный конечно быстрее. Сейчас прилижу и исполню на симуляторе с интерфейсом - чтоб ввести можно было.

Пока пишу кратко и попсово.


Когда-то знал про stall

Все правильно: stall - железный термин, stop - в ассемблере (пишется ;;) - регистровые зависимости в ia-64 требуют ;; иначе проц накажет программера undefined behaviour.

Теперь по поводу оптимизации. У интеловской инструкции pcmp есть некоторая специфика - вариантов маловато.

//0xff в байтах, 
//где r2[i]>r3[i], в др местах ноль, 0 <= i <= 7,
//затем ;;-стоп, тк зависимость
pcmp1.gt  r1 = r2, r3;;     // такт n

//compute zero index справа - ищет 
//первый нулевой байт
czx1.r r4 = r1              // такт n+3 

Получили первый байт, где <=. Меняем регитры местами - получаем >=. А если надо <? Отрицание результата (r1) невыгодно - лишний стоп. А инструкций только две: pcmp1.gt и pcmp1.eq. Остается сменить границы - например вместо 4...10 - 3....11 Параллельных инструкций IA-64 мало, но их скорость велика - 8 параллельных операций за 3 такта!
Если бы не цикл - да кто б сомневался пару раз что-то повернуть, с маской and сделать итд и итп - мильон вариантов. Но я намеренно ищу простейшие, идеальные для ia-64 условия - чтобы достичь ПИКОВОЙ производительности.

Цикл оформляется в wtop loop - конвейер. После каждой итерации, вызываемой командой br.wtop регистровый стек вращается и изменяются на единичку имена регистров. Поэтому пишем данный кусок так:

MyLoop:
...
pcmp1.gt  r36 = r32, r34 // такт n
czx1.r r20 = r37           // тот же такт n
...
br.wtop.sptk.few MyLoop

Отметь - ;; больше нет, так как r37 в прошлой жизни - в предыдущей итерации - звался r36. У r32, r34 тоже может быть аналогичная история. Это и есть софт пайп с хардовой поддержкой процессором. Сам софтовый конвейер хорошо и давно всем известен, но его аппаратная реализация - уникальная фича IA-64. С нагляным интерфейсом все это ты можешь увидеть в одном из моих топиков про Итаниум - вместе с exe симулятора.


Еще небольшое замечание. В некоторых случаях можно обойтись и без паралельных инструкций - например and, or, xor, add. Я так выкрутился во всех почти операциях с hex числами - там простые границы типа 0x30 - 0x39 и еще один диапазон (см мой вышеупомянутый пост с аттачем) - даже цикл не нужен!
Если не малтимидиа, то все можно за один такт, а не за 3. Но в общем случае - нет. Т.е. Эдмонд прав в конкретном примере.

PS Тег code - просто оргазм! Как я раньше его не замечал?

volodya
заплевали, ироды :(

Дык мы же не со зла. Со зла бы ты так легко не отделался... ;)

А ты почитай SPARCV9.pdf

Спасибо, конечно, за предложение. Я имел в виду немного другое: ты перечислил несколько операционных систем, а твоему коду операционка по барабану, для него важна архитектура самой машины. Насколько мне известно, тот же сорярис существует и в версии для писюков. Уверяю тебя, поведение этого кода ничем не будет различаться между писюковой виндой и писюковой соляркой.

А за сантехникой я сидел один раз в жизни. Она при этом была выключена. ;)

Не так уж трудно и поправить

В принципе, придираться к этому коду я могу ещё долго. Если будет интересно - свистни. ;)

только для сравнения АБСОЛЮТНО ИДЕНТИЧНЫХ строк

int compareAbsolutelyIdenticalStrings ( char *src, char *dst, int len )
{
    return 0;  /*  ;)  */
}

Valery

Я в архитектуре твоего иа64 не разбираюсь, поэтому, возможно, то, что я советую - не лучший вариант, заранее прошу прощения в таком случае. Тем не менее, соображения следующие: после команды czx1.r, очевидно, в той или иной форме следует сравнение полученного индекса с нулём. И по результатам сравнения предпринимаются некоторые действия. Так вот, для меня неочевидна целесообразность такого подхода. Я предлагаю не искать никаких байт в векторе, а сравнивать его целиком. Результатом pcmp1.gt (видимо, это аналог mmx-овой pcmpgtb) является двоичная маска удовлетворяющих условию байт. Соответственно, когда по условию прохдят все байты, там - -1 (0xff...ff), когда ни одного - 0.

В сравнении у тебя участвует регистр с размноженым байтом границы. Очевидно, что на скорости это отрицательно не сказывается. Не знаю, как это делается в условиях того софт пайпа, но точно так же, скорее всего, можно получить регистр с желаемым результатом сравнения. И сравнивать результат pcmp1.gt сразу с ним.

Значение этого регистра заносится на этапе инициализации, там же, где принимается решение об обмене границ сравнения.

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

bsl_zcs

Я наверное твою идею не понял. Сначала сравниваю с нижней границей, затем с верхней, потом and и далее дюбая инструкция, способная решить, есть ли хоть один 0 (пусть обычный cmp, можно czx после вылета из цикла). Если у тебя есть mmx идея с более простой маской/границей сравнения - пожалуйста, скажи. Я чувствую, что не вижу какого-то умного трюка. Как вообще можно упростить это:

0. Загрузка; stop
1. 2 сравнения (зависимостей нет); stop
2. and или еще что-нибудь - результаты сравнений надо снова сравнить; stop
3. Проверить, отличается ли результат от 0xfff..ff
[Здесь стоп необязателен, тк инструкция перехода обозревает предикат - результат сравнения сразу].

После вылета из цикла уже можно проверить - макс длина строки исчерпана или плохой символ. Здесь можно czx сделать. Последний адрес и код вылета вернуть.

Без пайпа это вот что:

ploop:
        ld8   r20 = [r4], 8;;  //загрузка с инкрементом адреса
        add r5 = -1, r5          //декремент счетчика   
        pcmp1.gt  r10 = r20, r6     // r6 = lower-1
        pcmp1.gt  r11 = r7, r20;;     // r7 = upper+1
        and r12 = r10, r11;;     
        p10, p0 = cmp.eq.and -1, r12 //особое параллельное 
        p10, p0 = cmp.ne.and r0, r5  //сравнение - сразу неск-ко условий
  (p10) br.cond.sptk.few    ploop   //=x86 jcc, если установлен предикат p10

можно получить регистр с желаемым результатом сравнения

Если мы скажем вычитать параллельно а не сравнивать будем - сколь это ускорит код?

Возможно, как последний вариант мы оба все-же имели именно это? Наверно мне надо было не вокруг да около, а сразу говорить полностью.

Скоро сюда повешу что обещал.

Так, давай по порядку с самого начала:

Ты пожаловался, что знаковые сравнения не подходят для случая, когда границы диапазона получаются с разным знаком.

Я рассказал, что в таком случае можно поменять границы местами и трактовать результат сравнения в обратную сторону.

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

В свою очередь, я предложил модификацию алгоритма, решающую обе эти проблемы.

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

Да, чуть не забыл, ещё нужно заменить and результатов двух векторных сравнений на xor. Это, пожалуй, единственное неочевидное место. Тут эксплуатируется факт того, что характер сравнений гарантирует исполнение как минимум одного из них. То есть, не выполниться оба они не могут, поэтому, ноль может означать только то, что оба выполнились и значение входит в диапазон.

Вот в общем-то и всё. Никаких умных трюков нет, и способа упростить это я тоже не вижу. А способ заставить это делать немного больше - есть.

compareAbsolutelyIdenticalStrings - хи-хи. Теперь с помощью своей абсолютно гениальной программы :))) найди мне одинаковые последовательности вот в этом гене, а еще вот в том :)))

Уверяю тебя, поведение этого кода ничем не будет различаться между писюковой виндой и писюковой соляркой.

Так уж повелось, что на писюках ставят бздю или линукс. Солярка - для солярки. Не хватало еще закрытую ось держать на PC. Одна винда чего стоит... С ее WFP... :(((

В принципе, придираться к этому коду я могу ещё долго. Если будет интересно - свистни. ;)


А давай. А то ля-ля, тополя. Давай, кажи, как можно лучше. Только func(){return 0;} мне не надо, я так сам умею :)

esi -- начало потока (адрес)
edi -- конец потока

eax -- нижняя
edx -- верхняя границы

mov ebx, [esi]
;нижняя граница:
mov ecx, eax
sub ecx, ebx
;; если AL < 128: то 7-е биты байтов будут 1, если хоть один из них = 0 - нашли
;; если AL > 127: то 7-е биты байтов будут 0, если хоть один из них = 1 - нашли
xor ecx, eax ;; теперь 7-е биты байтов будут 1, если хоть один из них = 0 - нашли

;верхняя граница:
sub ebx, edx
;; если DL < 128: то 7-е биты байтов будут 1, если хоть один из них = 0 - нашли
;; если DL > 127: то 7-е биты байтов будут 0, если хоть один из них = 1 - нашли
xor ebx, edx ;; теперь 7-е биты байтов будут 1, если хоть один из них = 0 - нашли

xor edx, ecx ;; 7-е биты байтов могут быть одинаковыми, только если не нашли, значит обнулим их
and edx, 80808080h ;; проверяем 7-е биты, если хоть один результат = 1 - нашли

bsl_zcs


А способ заставить это делать немного больше - есть.

Вот этого раньше в упор не видел. Спасибо тебе!

S_T_A_S_


Так, я может до чего-то не допер..

пусть нижняя граница 0x25252525, ищем попадание.
Числа 0x25302930. Разность в старшем байте отрицательна.
Проблема может быть только в старшем байте? Если попадутся большие числа, то не только в старшем: 0x29257f7f. Но в любом случае - только если что-то лежит на границе.
Если как-то обойти - все супер, в жопу малтимидию!

Valery
Мда.. похоже рано я написал. Проблема не там, где вы пишите.

В зависимости от строгости условия, к нижней границе возможно надо прибавить 01010100h. Подобным образом надо корректировать и верхнюю. У меня всегда плохо с границами

Идея такая: необходимо чтобы произошел ЗАЕМ из более старшего байта. Тогда 7й бит будет =1. Если где-то заема нет, то значит 7й бит будет 0 - признак выхода за диапозон. Если нижний диапазон >80h, то так:

00401000 > $  B8 85868686   mov     eax, 86868685
00401005   .  BA C7C7C7C7   mov     edx, C7C7C7C7
0040100A   .  BB EF8F8589   mov     ebx, 89858FEF
0040100F   .  8BC8            mov     ecx, eax  ;;  86868685
00401011   .  2BCB            sub     ecx, ebx  ;;  FD00F696
00401013   .  2BDA            sub     ebx, edx  ;;  C1BDC828
00401015   .  33D9            xor     ebx, ecx  ;;  3CBD3EBE
00401017   .  81E3 80808080 and     ebx, 80808080  ;;  00800080  нашли !!

Для другого случая придется менять границы..
Что-то Edmond придумал с XOR, но молчит :)

S_T_A_S_

Вроде мы на "ты" были..