Hogyan lehet legyorsabban meghatározni, hogy '\0' tartalmaz -e egy szó

Egyéb: Assembly, Ada...

String műveletknél (pl. másolás, összehasonlítás,hossz) '\0' végű stringeknél (C -string) lehetne nagyobb (4/8 byte) lépésekben haladni (mostani 1 byte helyett), ha olcsón megállapíthatnám, hogy lehet -e string vég az adott (4/8 byte) elem.

(Az alapértelmezett memóriakezelésnél 8 byte -al osztható területek mallocálódnak.)

Az összes Architektura érdekelne.

Röviden az Accumlátor/Work regiszter (Vagy neki megfelelő :)) tartalmaz -e '\0' byteot, (8 osztható bitindextöl kezdve.)

  • 7210 megtekintés

( egmont | 2007. 07. 04., sze – 20:30 )

Végre egy izgi kérdés :-))
Az a baj, hogy most nem látok annál hatékonyabb megoldást, mint hogy minden egyes byte-jára megnézed, hogy az nulla-e. Ezt persze lehet variálni (pl. a szót maszkolod különféle fix maszkokkal és nulla jön-e ki), de sajnos N byte-os szó esetén ez még mindig N teszt.
Pillanatnyilag nem látom, hogy lehetne ennél hatékonyabbat csinálni, de nem kizárt. Asszem a ma esti House alatt ezen fogok gondolkozni :)
De azt hiszem, már az is jelentős gyorsítás, ha 4 v. 8 byte-ot (persze alignolt pozícióból) egybe olvasol be a memóriából valami regiszterbe, aztán azt ott állsz neki elemezni.

( hud | 2007. 07. 04., sze – 22:25 )

Hát szóval találtam valamit. Persze most jó lenne, ha tudnám, hogy mi mennyi ideig tart egy prociban, és nem is sokat gyorsít, de szerintem működik. Eltolást, AND műveletet és 1 byte ellenőrzését vettem 1 lépésnek.

Nézzük 8 byte-ra, innen biztos általánosítani tudod. Számolni fogok valószínűségeket, két dolgot teszek fel:
- a következő 8 byte nem tartalmaz \0-t. Úgy is az az érdekes, amikor hosszú a string, akkor akarunk gyorsak lenni. Ha hamar megtaláljuk a \0-t, akkor örülönk.
- a bitek véletlenszerűek. Nyílván nem, de így tudunk számolni.

Az algoritmus:
Fogod a 8 byte-ot, eggyel ciklikusan eltolod (a bal részre a jobbról távozó byte jön be). Ezután AND-del összehasonlítod az eredeti 8 byte-tal (ha külön művelet lemásolni, akkor nem lesz jó a módszerem). Ezután megnézed a 0., 2., 4., 6. pozíciókat, hogy ott \0 áll-e. Ha végig nem, akkor ebben nem lesz \0. Ha igen, akkor ellenőrzöd a megfelelő két byte-ot.

P( a 4 vizsgálat során valahol \0-t látsz | nincs \0 bennük ) =
1 - P( a 4 vizsgálat során sehol sem látsz \0-t | nincs \0 bennük ) =
1 - P( 1 bytenál nem \0-t látsz | nem \0 )^4 =
1 - (1 - P(két véletlen bit AND műveletnél 0-t látsz)^8)^4 =
1 - (1-(3/4)^8)^4, ami kb. 0.344

Tehát az esetek harmadában lesz csak vak risztás. Egy vak riasztás 2 plusz vizsgálattal jár (nade lehet több vakriasztás is, úgyhogy vissza a matekhoz), nézzük pontosan a várható értéket:

6 művelet: egy eltolás, egy AND, plusz 4 vizsgálat.
plusz: 4*2* P( két véletlen bit AND műveletnél 0-t látsz) = 4*2*(3/4)^8 (magyaráznám a 2-es szorzót: két összehasonlítást kell néznünk)
Összesen: 6.8009

Ez várhatóan még mindig jobb, mint a 8 vizsgálat.

Számoltam több eltolással, de 8-nál több jött ki. Nincs még 16 byte-os rendszer? Ott repesztene.

Egy kis magyarázat. Használtam:
- feltételes valószínűséget
- várható érték linearitást
- elemi kombinatorikát
Bármelyikben szívesen segítek.

Még valami: Lehet, hogy az AND művelet után kapott 8 byte-os számot még egyszer el kellene tolni, most már 2 byte-tal, majd összehasonlítani (vagyis AND-elni) magával. Így csak 2 byte-ot kellene ellenőrizni, hogy \0-ák-e. Ez így még nem lenne gyors, mivel marad a 6 művelet + nagyobb szám várható értékben = kb. 8.773, mivel minden egyes vakriasztás esetén 4 byte-ot kell végig nézni. Javítási javaslat: vakriasztás esetén az első AND művelet után kapott számot lehetne vizsgálni, és nagy valószínűséggel (ez is feltételes lesz, na ezt nem volt kedvem számolni) 2 vizsgálattal meg lehet úszni a dolgot. Ez még gyors lehet, de 6 alá semmiképp sem tud menni.

ez jo. de meg gyorsabb lenne, ha osszeANDolnad a 8 byteot, es akkor csak egy ellenorzes hogy 0 kaptal-e, nem kell kulon megnezni a 0.,2.,4.6. byteot. egyebkent szerintem csak par szazalekot gyorsulna ilyen trukokkel, mert pl. osszeANDolni ket byte-ot, vagy ellenorizni, hogy egy byte 0-e kb. ugyanannyi ido, annyival lassabb az utobbi, hogy ott lehet (bar szerintem nem valoszinu) egy rosszul megjosolt ugras, ami viszont rengeteg ido.

- Use the Source Luke ! -

Ha össze AND-eled a 8 byte-ot, akkor az 8 művelet kapásból, nem? Ráadásul ha 8 véletlen byte-ot összeAND-elsz (milyen mókás, hogy az AND szóból származtatunk igét, és az össze, mint igekötő egybeírandó vele), akkor csak akkor nem lesz hibás detektálás, ha van olyan közös bit, ami végéig 1-es, erre pedig 1-(255/256)^8, ami kb. 0,03 , ami nagyon kicsi. Vagyis szinte mindig végig kell nézni a byte-okat egyesével.

És igen, ilyen trükkökkel biztos csak pár százalákot lehet kihozni, ha egyátalán valamit kilehet.

( zamboriz v | 2007. 07. 04., sze – 22:42 )

Ha 8 bájtonként dolgoznád fel a sztringeket, akkor 8 bájt felel meg egy szimbólumnak, feldolgozási egységnek. Ha záró szimbólumot, végjelet szeretnél használni, akkor ez is 8 bájtos kell legyen.

Az üres sztring tehát 8 bájtnyi '\0' lenne. Az 1 karakteres sztring az 1 karakter, amit 7 bájtnyi '\0' kitöltés (padding), és egy 8 bájtos végjel követ.

Szerintem.

( denes | 2007. 07. 04., sze – 22:54 )

MMX-szel meg SSE-vel lehet. lasd PCMPEQB assembly utasitas. hogy innen hogyan, az legyen hazi feladat :]

- Use the Source Luke ! -

vegulis lassuk be ez az utasitas pont az ilyen jellegu feladatok gyorsitasara kerult be az utasitaskeszletbe :)

szerk: jo ertem a poent, ez milyen nyelvu oldal? de amugy ha mar rajottel mit csinal ez az utasitas (na ezt a google tenyleg megmondja) meg tudod mi az a regiszter (az am nagyon bonyolult) akkor jozan paraszti esz, es fel perc alatt kesz az algoritmus.

- Use the Source Luke ! -

( turul16 v | 2007. 07. 04., sze – 23:15 )


0000000000075380 <strcmp>:
   75380:       8a 07                   mov    (%rdi),%al
   75382:       3a 06                   cmp    (%rsi),%al
   75384:       75 0d                   jne    75393 <strcmp+0x13>
   75386:       48 ff c7                inc    %rdi
   75389:       48 ff c6                inc    %rsi
   7538c:       84 c0                   test   %al,%al
   7538e:       75 f0                   jne    75380 <strcmp>
   75390:       31 c0                   xor    %eax,%eax
   75392:       c3                      retq   
   75393:       b8 01 00 00 00          mov    $0x1,%eax
   75398:       b9 ff ff ff ff          mov    $0xffffffff,%ecx
   7539d:       0f 42 c1                cmovb  %ecx,%eax
   753a0:       c3                      retq

glibc -ben igy nez ki amd64 en.

ki mondja, hogy nem jo masolasra az mmx?
a prefetch utasitas mindenkepp jo, hogy mar cachebol vegye a masolandot
az meg miert nem jo ha egyszerre 128 bitet mozgat (SSE-vel)?

szerk: mert nyilvan mmx-et amd64-gyel osszevetni nincs ertelme masolas eseten, amd64-en mar csak
az SSE-nek lehet ertelme

- Use the Source Luke ! -

mmx ele nem lehet rep-et rakni.

hol van ez leirva, ez a zlib-es dolog? szerintem az mplayer-ben ezt benchmarkolta az iroja. eleve nyilvan mindig megmeri az ember optimalizacio elott meg utan a programjat, hogy mennyivel lett gyorsabb, mar csak kivancsisagbol is. ugyhogy ezt nem nagyon ertem, ezt a zlib dolgot.

- Use the Source Luke ! -

itt egyszer már előkerült.
"gentoo miert nem hasznal mmx -et orba szájba, pl. zlib-nél" felkultás

Meg nézegettem zlibet -hogy vajon miért nem, és benne le volt írva (forrás megjegyzés), hogy mmx nem volt süti P4 en.
Ujabban futás közben dönti el, hogy mmx vagy mmx nélküli változat fusson (by processor detektálás).
Régi, de mmx tudó procikon mmx, ujakon no-mmx.

Ezért nem kapott mmx USE flaget zlib gentooban :)

4K mozgatása (ugyanaz):
0xFFFFFF szer:

movsb 1 byte - 8 bit
time ./test

real 0m39.566s
user 0m38.868s
sys 0m0.147s

movsw 2 byte -16bit

time ./test

real 0m19.911s
user 0m19.610s
sys 0m0.050s

movsl 4byte - 32 bit

time ./test

real 0m14.878s
user 0m14.621s
sys 0m0.047s

movsq 8byte - 64bit
time ./test

real 0m5.170s
user 0m5.062s
sys 0m0.024s

memcpy
4 regiszterrel masolosdi technikat hasznal, a maradekot movsb -zi. (fentiek nem kezelnek maradekot)
time ./test

real 0m7.887s
user 0m7.741s
sys 0m0.012s

mplayer fast_memcpy -DHAVE_SSE2 -DHAVE_MMX -DHAVE_SSE -DHAVE_3DNOW -DHAVE_MMX2 aclib_template.c nyomán BLOCK_SIZE=4k
time ./test

real 0m34.033s
user 0m33.406s
sys 0m0.099s

SSE2 joval lassabb memoria masolásra, nem igazan tudja párhuzamositani őket a processor, és lassab a feldolgázsuk is, mint egy General porpuse utasitasnak. Ezen a prefetchnta sem segít, amit más forumokon sem javalottak memoria masolásra.

szerk: még pár mérés:
SSE2
movntps ->movaps change
time ./test

real 0m12.991s
user 0m12.784s
sys 0m0.048s

MMX2 movntq
real 0m28.636s
user 0m28.215s
sys 0m0.100s

MMX1 movq
real 0m18.659s
user 0m18.397s
sys 0m0.052s

C-lang for 32bitt -O0
time ./test

real 1m57.940s
user 1m55.829s
sys 0m0.439s

C-lang for 32bit -O2
time ./test

real 0m39.237s
user 0m38.613s
sys 0m0.145s

C-lang for 32bit -O2 4 ertekadas /ciklus. (Csak egy regisztert hasznal (eax))
time ./test

real 0m14.763s
user 0m14.535s
sys 0m0.049s

Hasonló asm 32 bit 4 reg :
time ./test

real 0m12.527s
user 0m12.302s
sys 0m0.052s

( egmont | 2007. 07. 05., cs – 15:28 )

Ezt találtam ki otthon: (C-jellegű szintaxissal, mert Intel assemblyhez nem értek):

long long foo = [a 8 vagy akárhány byte-os cucc];
foo |= (foo >> 1);
foo |= (foo >> 2);
foo |= (foo >> 4);
end_of_string akkor és csak akkor, ha ((foo & 0x0101010101010101) != 0x0101010101010101);

Az első shiftelősdi-vagyolósdi után minden bit azt tartalmazza, hogy az eredeti regiszterben az adott pozíció, és az attól balra lévő pozíció legalább egyikén 1-es bit volt-e.
A második shiftelősdi után immár minden bit 4 kezdeti bitet vagyol össze.
A harmadik shift után pedig minden bit azt mutatja, hogy az ott végződő egymást követő 8 bit között volt-e 1-es kezdetben.
Jelen esetben ebből minden byte-nak a jobb szélső bitje érdekes, a többi szemét. Ha volt 0-s byte (end of string), akkor itt lesz köztük 0-s bit, ellenkező esetben ezek mind 1-es bitek.

Bónusz: C-ben 0x0101... helyett (((unsigned [típus])(-1))/255) fordítási időben épp a megfelelő szóhosszúságban produkálja a szükséges konstanst.

Valszeg elég gyors a fenti algoritmus, mivel nincs benne elágazás, kevés regiszter is elég, és a kód nem lesz hosszabb ahogy nő hogy hány bites architektúrán dolgozol (32 -> 64 -> ki tudja mit hoz a jövő). 


  400510:       48 89 f8                mov    %rdi,%rax
  400513:       48 d1 e8                shr    %rax
  400516:       48 09 f8                or     %rdi,%rax
  400519:       48 89 c2                mov    %rax,%rdx
  40051c:       48 c1 ea 02             shr    $0x2,%rdx
  400520:       48 09 c2                or     %rax,%rdx
  400523:       48 89 d0                mov    %rdx,%rax
  400526:       48 c1 e8 04             shr    $0x4,%rax
  40052a:       48 09 d0                or     %rdx,%rax
  40052d:       48 ba 01 01 01 01 01    mov    $0x101010101010101,%rdx
  400534:       01 01 01 
  400537:       48 21 d0                and    %rdx,%rax
  40053a:       48 39 d0                cmp    %rdx,%rax

  40053d:       0f 95 c0                setne  %al
  400540:       0f b6 c0                movzbl %al,%eax

gcc igy forditja.

Nem tudom be hozza -e az árát, ez még mindig drágának tűnik.
De tetszik :)

( asch v | 2007. 07. 05., cs – 10:15 )

Szerintem érdekesebb kérdés, hogy mihez kell?

( egmont | 2008. 02. 28., cs – 08:38 )

Megnéztem, hogy a glibc hogyan csinálja a strlen() vagy strchr() implementációjában. Nagyon durva! Eltartott jódarabig, mire megértettem, a baromi hosszú megjegyzés ellenére. (Egyébként az egyik "left" szó helyett "right"-ot akartak írni, ez tovább nehezített a megértésen.) Mondjuk az alap ötlet tök egyszerű: az összeadás vagy kivonás műveletet kell okosan úgy használni, hogy ha egy byte csupa nulla bitből áll, akkor a carry bit a végén másképp alakul, mint ha nem csupa nullából. Konkrétan hozzáadja a bináris 01111110 11111110 11111110 11111111 számot, és azzal játszik, hogy ha valamelyik byte nullás volt, akkor ott a carry bit elakad és ezáltal a következő byte LSB-je nem változik, míg ha bármelyik bit 1-es volt, akkor az végigszalad egészen a következő byte LSB-jéig és ott ellenkezőjére változtatja azt a bitet és ott megáll.

Kivonat a glibc-2.7/string/strchr.c fájlból:

unsigned long int magic_bits = 0x7efefeffL;
unsigned long int longword = (((amit tesztelni akarsz)));

/* We tentatively exit the loop if adding MAGIC_BITS to
LONGWORD fails to change any of the hole bits of LONGWORD. */

if ((((longword + magic_bits) ^ ~longword) & ~magic_bits) != 0) {

/* vagy van 0-s byte, vagy false pozitívként elképzelhető, hogy az első byte 128-as, de mivel itt úgyis elkezdesz egyenként lépni, így ez kiszűrhető */

} else {

/* tuti nincs nullás byte, száguldhatsz tovább */

}

Assemblyben hozzáférsz a kieső carry bithez, így valszeg a false positive is elkerülhető.

Na szóval az előző is túl bonyolult volt. Az 5807-es glibc hibabejelentés alapján íme Az Ultime Megoldás A Problémára: 


int haszerobyte(unsigned32 x) {
  return ((x - 0x01010101) & (~x) & 0x80808080) != 0;
}

és 64 bitesre is hasonlóan, csak hosszabban folytatva a mintát a konstansokban.

Szóljon, aki talál ennél is egyszerűbbet. :-)

Megérteni, helyességét ellenőrizni mindenkinek legyen házi feladat. Nekem kábé 5 percbe tellett.

( tovis v | 2011. 03. 12., szo – 13:49 )

Szép ha valaki még vissza nyúl ilyen dolgokhoz.
Szerintem, vissza kellene nyúlni a probléma gyökeréhez - valaki ezeket a sztringeket odapakolja/generálja. Itt kellene eleve a hosszát is odatenni (mint azt más nyelvekben mint a C csinálják is), azaz nem C stringet használni.
A mai memória bőségben nem kellene a másolásnál a hosszal bíbelődni - fix hosszakat használni, másolni és csak akkor foglalkozni a záró zéróval ha annak van jelentősége - nyomtatás/megjelenítés. Ha 256 bájton tárolsz egy névelőt (egy értékes karaktert), az zavaró vagy sem?

* Én egy indián vagyok. Minden indián hazudik.

( asch v | 2011. 03. 25., p – 16:58 )

A legtöbb esetben a memória sávszélessége sokkal kisebb lesz, mint a processzoré, ezért akármilyen algoritmust is használunk, arra kell főleg ügyelni, hogy a memória olvasás optimális legyen.

Lehet, hogy mindegy is, hogy belül bájtonként izélünk-e?

Persze ez csak akkor igaz, ha kicsúszunk a cache-ből, de az egész hosszmérés úgyis csak akkor lesz érdekes, ha annyi string van, hogy kicsússzunk.