Box3D fizikas dzinī sadursmju pārbaude ar SSE2 instrukcijām aizņem 17 337 milisekundes tur, kur agrākais skalārais kods prasīja 40 706. Runa ir par 500 simulācijas soļiem uz viena procesora kodola. Ar astoņiem pavedieniem tas pats tests nokrīt no 5292 līdz 2410 milisekundēm.
Skaitļus 18. jūlijā publicēja Erins Kato (Erin Catto), Box2D autors, kurš no maija strādā pie trīsdimensiju atzara. Rakstā par SIMD lietošanu sadursmju kodā viņš izklāsta, kur laiks aizķērās un ko deva datu pārkārtošana atmiņā.
Kvadrātiskā problēma ar šķautnēm
Box3D sadursmes nosaka ar dalošo asu testu, angliski separating axis test jeb SAT. Diviem izliektiem korpusiem tas pārbauda katru šķautņu pāri. Kastei ir 8 virsotnes, 6 skaldnes un 12 šķautnes, tāpēc kaste pret kasti izrēķinās lēti. Kato etalona aina ar nosaukumu convex pile nomet 5120 korpusu, katram no tiem 32 punkti. Tādam akmenim ir 59 skaldnes un 89 šķautnes. Divi šādi korpusi vienai sadursmei dod 7921 šķautņu pāri.
Skaits aug kvadrātiski. Kad ainā krīt tūkstošiem tādu akmeņu, šķautņu tests apēd lielāko daļu kadra laika. Box3D korpusiem ir uzlikti 128 šķautņu griesti, lai indeksus varētu glabāt astoņu bitu skaitļos.
Plata SIMD un masīvu struktūra
Fizikas kodā SIMD instrukcijas var lietot divos veidos. Šaurajā variantā trīs komponentu vektoru ieliek SIMD reģistrā un parasto vektoru matemātiku izsaka ar instrukciju izsaukumiem. Ceturtā josla tad stāv tukša un daļa laika aiziet komponentu savākšanai atpakaļ kopā. Kato izvēlējās plato variantu, kas vienlaikus apstrādā vairākas darba vienības. Viena korpusa A šķautne tiek pārbaudīta pret četrām korpusa B šķautnēm reizē.
Tas prasa datus glabāt masīvu struktūrā: vispirms visas x koordinātas blakus, tad visas y koordinātas un tad visas z. Pārkārtošanai ir sava cena. Tā ir ieskaitīta zemāk redzamajos skaitļos, jo mērījumi rāda visas simulācijas kopējo laiku ar visu pārējo darbu, kas kadrā notiek. Kato secinājums par savu tabulu ir īss:
SSE2 ir vairāk nekā divreiz ātrāks par skalāro kodu.
Skaitļi pa pavedieniem
Kato tabulā ir trīs kolonnas: skalārs, SSE2 un AVX2-Lite. Visi mērījumi ir milisekundēs par 500 soļiem.
- 1 pavediens: 40 706, 17 337 un 15 762
- 2 pavedieni: 20 799, 8857 un 8131
- 4 pavedieni: 10 324, 4509 un 4084
- 6 pavedieni: 6958, 3106 un 2843
- 8 pavedieni: 5292, 2410 un 2277
Ieguvums saglabājas arī tad, kad pavedienu kļūst vairāk. Ar vienu pavedienu SSE2 kods ir 2,35 reizes ātrāks par skalāro, ar astoņiem 2,20 reizes. Trešā kolonna Box3D vēl nav pabeigta. Kato kompilatorā ieslēdza AVX2 arhitektūru, bet pašā kodā palika SSE2 instrukciju izsaukumi, tāpēc viņš to sauc par AVX2-Lite. Divdimensiju Box2D jau lieto īstus AVX2 izsaukumus. Papildu ieguvums no arhitektūras karodziņa vien ir 9 % ar vienu pavedienu un 5,5 % ar astoņiem.
Kato piebilst, ka pārrakstīšana palīdz tikai sarežģītiem korpusiem. Kastēm un citām vienkāršām formām šķautņu pāru ir tik maz, ka SIMD kods tur neko nepaspēj nopelnīt.
Ko tas nozīmē kadra budžetā
Etalona skaitļus var dalīt ar 500, lai iegūtu vienu soli. Skalārais kods ar astoņiem pavedieniem 5120 akmeņu kaudzei tērē 10,6 milisekundes uz soli. SSE2 to nokārto 4,8 milisekundēs. Ja spēle mērķē uz 60 kadriem sekundē, viss kadrs ir 16,6 milisekundes un fizikai parasti atvēl tikai daļu no tā. Starpība starp 10,6 un 4,8 izšķir, vai tāda aina vispār ir izpildāma.
Uz viena kodola aina paliek smaga arī pēc pārrakstīšanas: 34,7 milisekundes uz soli pret skalārā koda 81,4. Daudzpavedienu sadalījums Box3D balstās uz grafa krāsošanu lielām salām, tāpēc astoņi pavedieni dod aptuveni septiņkārtīgu paātrinājumu.
Kas Box3D jau lieto
Box3D repozitorijs GitHub atvērts 10. maijā un tam šobrīd ir 5571 zvaigzne. Kods ir C17 ar C saskarni, licence MIT, tāda pati kā Box2D 10 182 zvaigžņu projektam. Pēdējās izmaiņas repozitorijā ievietotas 26. jūlijā.
Kato 30. jūnija paziņojumā dzini sauc par alfa programmatūru un raksta, ka drīz iezīmēs v0.1 versiju. Tur uzskaitīts arī tas, ar ko Box3D atšķiras no divdimensiju priekšteča:
- trīsstūru tīklu un augstuma lauku sadursmes
- iepriekš sagatavotas saliktas formas
- nepārtraukta sadursmju noteikšana
- vienāds rezultāts uz visām platformām, ar ierakstīšanu un atkārtotu atskaņošanu
- lielas pasaules ar divkāršas precizitātes pozīcijām
Algoritmi nāk gan no Box2D, gan no Valve dziņa Rubikon. Alfa statuss projektus nav atturējis. Kintsugiyama Studios spēlē The Legend of California cietokšņos var būt ap 50 000 atsevišķu sadursmju tīklu, bet servera pusē tā uztur simtiem tūkstošu vienību. Dzini izmanto arī Facepunch Studios s&box, Esoterica dzinis un izstrādātāja Glena Fīdlera (Glenn Fiedler) kosmosa spēle ar tūkstoš spēlētājiem. Fīdlers par bibliotēku publiski rakstīja īsi: Yeah this library is great. Use it!!!
Nākamais Kato uzdevums pēc raksta ir tas pats šķautņu tests uz ARM. NEON instrukciju kopa Box3D kodā vēl nav ielikta.
Komentāri
Šim rakstam vēl nav komentāru. Esi pirmais, kurš dalās ar savu viedokli.