czwartek, 22 kwietnia 2021

Przełomowe Atarowe odkrycie w Action!;)

Wczoraj dokonałem przełomowego odkrycia, coś czego się kompletnie nikt nie spodziewał.

Odkrycie dotyczy rewelacyjnego języka programowania Action! z 1983 roku(!) ACS, który był prawdopodobnie pierwszym językiem, który był stworzony z myślą o tworzeniu profesjonalnych gier i dem. Do dziś nie poznałem języka szybszego i lepiej przemyślanego - naprawdę niezwykłe!

Wrato zaznaczyć, że do dziś wszyscy pamiętają, że Action! to znaczy szybkość i że nie ma możliwości odnalezienia innego języka, który byłby prawie tak szybki jak asembler.

Wyjaśnię czego dotyczy odkrycie: gdy pracowałem kiedyś w Mirage Software z Jaśkiem, to rozgryźliśmy w tym języku bardzo ciekawą rzecz, mianowicie język zezwala na to, aby utworzyć tablicę o adresie 0. Kiedyś na party podszedł do mnie koder z innego komputera, czyli Sqward i zapytał co to za potworek? Tablica bez wartości tylko z jakimś zerem??
Genialność tego rozwiązania jest niesamowita, bo skraca i upraszcza dostęp do pamięci. We wszystkich innych językach programowania mamy dwa rozkazy (+ inne wariacje tak jak w Action!), czyli POKE i PEEK. Natomiast ta tablica powoduje, że nie potrzeba już żadnych procedur, a dostęp do tablicy posiada funkcjonalność ich obu!;)
Dodatkowo każdy kompilator wykonuje skok do procedury, a następnie powrót - czym traci masę czasu CPU. Jednak przy dostępie do tablicy nie ma żadnego skoku (szczególnie czasochłonny jest na pecetach x86) i nie ma żadnego powrotu!;)

Korzystaliśmy z tego rozwiązania latami, będąc przekonanymi, że nie ma w żadnym języku czegoś szybszego i bardziej sprytnego;)

No i tak było do wczoraj:P

Odkryłem coś co powoduje, że przenosimy się o kilka poziomów wyżej w programowaniu zaawansowanych animacji (w grach/demach) na Atari w Action!
Trudno w to uwierzyć, no ale po dziesięcioleciach od 1983 roku - dziś udało mi się coś w tak stareńkim języku odkryć!;)

Udało mi się opracować bardzo podobny mechanizm tablicy, z którego korzysta się w prawie identyczny sposób, jednak jego wydajność jest naprawdę imponująca!

W przykładzie:
    ; Zapisanie 21 bajtów w graphics 15 za pomocą tablicy P:
    [173 $D40B 201 40 208 249]
    GG=6
    QQ=$9000
    FOR Q=0 TO 20 DO
    P(QQ)=255 QQ==+1
    OD
    GG=0
trwa 22 linie rastra...
Do wczoraj każdy by powiedział, że jest to bardzo szybko jak na język tak stary i język który nie jest asemblerem, ale kompilatorem.

Jednak jak wykorzystamy mój nowy pomysł np. tak:
    [173 $D40B 201 80 208 249]
    GG=6
    FOR Q=0 TO 20 DO
    FastP(Q)=255
    OD
    GG=0
Zajmuje to 10 linii rastra!
Czyli ponad dwukrotnie szybciej!;)


Widzimy wykresy wydajności rastra, dla zaprezentowanych tu przykładów kodu wykorzystujących oba rozwiązania.

(oczywiście obie wersje programu da się napisać wydajniej - ale to takie proste obrazowe przykłady)

Rewolucyjne jest również to, że o kilka poziomów zmniejsza to też rozmiar kodu!;)

Do tej pory w moich grach były liczne procedury, które animowały przeciwników w najszybszy możliwy sposób, czyli za pomocą tablicy P. Niestety procedury te były bardzo duże, zajmowały wiele kilobajtów, więc nie byłem z tego zadowolony.

Więc co daje nowe rozwiązanie?

W zależności od sytuacji mamy tu: od ~2,9 do 4,2 razy krótszy kod! Oczywiście względem zwykłej tablicy P!

To naprawdę duża oszczędność.
Naprawdę zawadzały mi te procedury, gdy będą mogły być 3 - 4 krotnie krótsze to jest coś!;)

Okazało się, że myk jaki wymyśliłem - Action! kompiluje do 5 bajtów kodu dla stałej i do 8 bajtów przy zmiennym adresie (animacji). Jest to najmniejszy rozmiar kodu jaki da się wygenerować, więc krócej i szybciej na Atari się już nie da;))

Coś niesamowitego, naprawdę sądziłem przez kilkadziesiąt lat, że szybciej się już nie da... A jednak!;)

Tu zaprezentowany jest najszybszy powszechnie znany sposób, dzięki któremu można najszybciej zmodyfikować w Action! komórkę pamięci - wydajność 100% asemblera (tu modyfikacja adresu $9000 w trybie 15). Niżej znajduje się mój nowo odkryty trick FastP, który nie dotyczy tylko jednego adresu jak w pierwszym przypadku, ale nadaje się do robienia animacji - jednak jak widać czas wykonania obydwu jest ten sam!

Ten zaawansowany i niebezpieczny trick jaki zastosowałem spowoduje, że moje gry, które do tej pory grały na nosie wszystkim np. strzelankom, ze wszystkich możliwych komputerów 8-bitowych, teraz będą od 70% do 80% szybsze!;) a miejscami i 100% szybsze;)
...i to bez grama asemblera! Bo trzeba podkreślić, że na innych komputerach nie było tak zaawansowanego i profesjonalnego języka programowania, więc nie dało się zrobić profesjonalnej strzelanki w żadnym kompilatorze - takie gry robiło się wyłącznie w asemblerach.

W mojej ocenie Atari i Action! pokazały tutaj pazur!;)


A wszystko dzięki temu, że właśnie pracuję nad grą na konkurs Sikora tzw. 16 Kb Cart 2021;) Natomiast to odkrycie Sikor! pewnie nie zostałoby odkryte, gdyby nie Twój konkurs;)
Dzięki Sikor!;)

Jakbym komuś powiedział w latach 80. że uda mi się dziś coś podobnego odkryć - to pewnie nikt by mi nie uwierzył!:))) Ja wtedy bym zareagował: to daj mi maszynę czasu bo chcę wiedzieć jak to zrobić!;)


Update: 9 VI 2022:
Tak... mój blog przeszedł kolejny najazd rządnych krwi trolli (26 komentarzy! nie licząc licznych wątków na forach - obłęd!), jednak leci obecnie już 14 miesiąc od czasu tego postu i nikt (ABSOLUTNIE NIKT!) nie wpadł na to co konkretnie odkryłem.

(w czasie najazdu obleśnych szyderców to posiłkowano się kodem, który został kiedyś opublikowany, jednak gdy wyjaśniłem że nie o to mi chodzi, to jakoś wszyscy zamilkli - nawet nikt nie próbował dojść o co chodzi...
Choć jak mniemam, podstawy obsługi wyszukiwarek internetowych mają wszyscy w małym palcu, więc założyć można że w internecie rozwiązana znaleźć nie można...)

Przypominam, że umiejętność znalezienia cudzego kodu w internecie, nie jest przesłanką do tego żeby siebie uważać za wielkiego programistę, bo jak mniemam wszyscy trolle w komentarzach pod tym postem - za takich siebie mają...


Update:
Ciekawe! Dziś jest już 1 IX 2022 a ja nadal nie otrzymałem ŻADNEGO rozwiązania tego zadania! Jak pokrzyczeć w komentarzach i na forach to jest wielu chętnych, ale jak napisać parę linijek kodu samodzielnie (a nie wkleić z google'a) to jakoś nikogo nie ma...

To bardzo ciekawe, że jak można dowalić mi to w ciągu kilku minut, pojawiają się komentarze, ale jak trzeba coś napisać z sensem - to nikogo nie ma... ABSOLUTNIE NIKOGO!

To istotne, bo ktoś mógłby napisać, że nie ma ze mną kontaktu, a próbował się ze mną skontaktować i podesłać rozwiązanie - ale jak tu w coś takiego wierzyć, gdy zestawia się ze sobą tollowanie w szybkim czasie (jakoś znaleźć mnie wszyscy mogą?!?) z tym jak upłynęło blisko 1,5 roku!!!

Naprawdę znaleźć mnie nie możecie? A może paluszki się połamały lub klawiatura gdzieś się zapodziała??

Jesteście mali i żałośni!

28 komentarzy:

AdamK pisze...

TDCu, proszę nie kompromituj się. Instrukcje skoków na x86 kosztują w większości przypadków dokładnie 0 cykli procesora (bezwarunkowe takie jak tu by były to zawsze 0 cykli).
Kompilatory zaś już od dawien dawna potrafią optymalizować takie rzeczy jak operację typu PEEK/POKE i ładnie ją wciskać w kod tam gdzie trzeba.

Tdc pisze...

Ja się kompromituję??
A Ty porównujesz dzisiejszego Intela z tym z dawnych czasów... i z językiem programowania z 1983 roku...
No to cytując Ciebie "proszę nie kompromituj się.".

W ramach lekcji historii zobacz jak działały skoki w dowolnym Intelu x86 z czasów Action!

Ijon Tichy pisze...

nie rozumiem o co chodz z tym przyśpieszeniem. może więcej przykładów?

Anonimowy pisze...

Zero cykli? Serio? A czytałeś kiedyś dokumentację Intela albo jakiegokolwiek innego procesora? No to przeczytaj, to się dowiesz, że jmp na Intelu zajmuje 11 do 24 cykli w zależności od modelu procesora i trybu adresowania. Nie ma czegoś takiego jak instrukcje, które mają zero cykli, inaczej procesor nie potrzebowałby w ogóle zegara i wykonywał każdą pracę w zero czasu. Są co najwyżej instrukcje, które zajmują jeden cykl i procesory o architekturze simd potrafią wykonać kilka takich instrukcji jednocześnie. Co nadal nie oznacza, że jeśli procesor wykonuje w jednym cyklu 10 takich instrukcji, to znaczy, że każda z nich zajmuje 1/10 cyklu :)

kklis pisze...

@Ijon Tichy

Jeśli dobrze zrozumiałem Tomka to normalnie deklarujesz sobie P jako BYTE ARRAY P=0 i wtedy chcąc zapisywać coś w pamięci od adresu $9000 piszesz coś takiego:

QQ=$9000
FOR Q=0 TO 20 DO
P(QQ)=255
QQ==+1
OD

Trcik polega na tym żeby sobie zdefiniować FastP jako BYTE ARRAY FastP=$9000 i wtedy pętla skraca się do postaci:

FOR Q=0 TO 20 DO
P(Q)=255
OD

bo nie trzeba za każdym razem inkrementować adresu, robi to za ciebie licznik pętli.

Anonimowy pisze...

No tyle, że to nie żadne odkrycie a oczywista oczywistość.
Jeśli tak sobie zadeklarujesz tablicę bajtów w pamięci, że ogarniesz jej obsługę licznikiem pętli, to zawsze będzie szybciej niż dodatkowo inkrementować wskaźnik.
To podstawy optymalizacji programu.

Nazywanie tego odkryciem, wynika raczej z braku wiedzy "odkrywcy".

Ijon Tichy pisze...

@kklis dzięki... po takiej ścianie tekstu spodziewałem się jakiejś magicznej autoinkrementacji przy STA czy czegoś takiego :]]]]]]]

Anonimowy pisze...

Istnieją nieudokumentowane rozkazy procesora 6502 i być może używając któregoś z ich da się uzyskać zachowanie podobne do instrukcji LDIR z procesora Z80 (która ogarnia jednocześnie transfer danych i aktualizację liczników). Jednak szczerze wątpię, żeby Action! umiał generować kod wykorzystujący takie instrukcje.

Anonimowy pisze...

11-24 cykle to skoki na 8086, Pentium już skakał w jednym cyklu: jmp short (w obrębie segmentu) to 1 cykl, a rozkaz jmp można było skalować w kanale PV. 486 w takiej konfiguracji to 3 cykle. Motorola 68000 jmp wykonywała w zależności od trybu adresowania od 8-14 cykli, a Z80 od 4 do 8 (ale tego to już nie pamiętam).

Anonimowy pisze...

Ale samozaoranie, epickie!

Pecuś pisze...

Tdc dokonał przełomowego odkrycia!

Odkrył optymalizację kodu :)

zbyti pisze...

Jakbyś Tomek robił tak jak ja, często sprawdzał pod emulatorem lub monitorem jako kod Action! generuje dla danej konstrukcji językowej to byś nie dokonywał tego typu odkryć po 30 latach :]

Pecuś pisze...

zbytu zauważ, że w tym przypadku nie ma potrzeby sprawdzania jaki kod jest generowany. Pozbycie się dowolnej operacji z wnętrza pętli w dowolnym języku programowania przyspieszy działanie programu. To podstawy optymalizacji kodu!
Przyznam, że ja pisząc daaawno temu jakieś programiki w Action! nigdy nie traktowałem całej pamięci jako tablicy zaczynającej się od komórki zerowej. Zawsze deklarowałem sobie taką tablice od miejsca w pamięci w którym była mi potrzebna. Zakładam, że większość ludzi tak robiła bo czemu nie, skoro tak jest szybciej.
Czyli stosowałem "odkrycie" Tomka wiele lat prze jego dokonaniem. Jak wielu innych programistów.

zbyti pisze...

@Pecuś tak w tym przypadku masz racje, nie trzeba sprawdzać co jednoprzebiegowy kompilator na to. Po prostu podpowiadam jak na przyszlość uniknąć podobnych kopromitacji bo nie wiadomo ile jeszcze przełomowych odkryć przed nami które są oczywiste przy poważnym podejściu do programowania i poznawania możliwości kompilatora.

Jege rewelacja nie jest dla mnie nowością bo optymalizując swoje programy w Action! jego odykrycie stosowałem "z automatu" prawie na samym początku nauki.

Irytuje mnie gdanie o szybkości Action! gdy jedna z najczęstysz operacji czyli np. X==+1 na typie BYTE nie jest kompilowane do INC X.

W swoich programach gdy ze względu na szybkość używałem zmiennych na ZP to nie mogłem się z tym pogodzić i zdefiniowałem sobie w Action! coś takiego: INC x CNI gdzie INC otwierało blok kodu z odpowiednim opcodem a CNI zamykało blok kodu za pomocą ]

Pętle for nie są optymalizowane, tak jak w Mad Pascalu. Poke/Peek, przesunięcia bitowe to funkcje itd. itp.

Do tego nauczyłem się pisać w Action! bez jego bibliotek także kod kompilowany w Action! można napisać całkowicie przenośnie na dowolny 6502. Z resztą Action! miał się pojawić na C64, były takie plany ale coś nie pykło.

Także głowne tezt o szybkości i dedykowaniu Action! Atari to nonsens. Dedykowany to jest tylko runtime i pozostałe biblioteki ale to chyba oczywiste.

Pecuś pisze...

Ale statystyki bloga skoczyły :)

Może w tym szaleństwie jest metoda! ;)

Tdc pisze...

Ci którzy mnie tutaj atakują i niekompetentnie podważają moje odkrycie... szkoda słów...

Moja odpowiedź do żałosnych szyderców.

Pecuś pisze...

Tomek, nikt Cię nie atakuje. I nie podważa tego "odkrycia".

Zwracamy Ci uwagę, że to, co być może dla Ciebie jest odkryciem jest dla nas czymś oczywistym i znanym od lat. Bo to podstawa optymalizaci kodu pod kątem szybkości w każdym jezyku, a nie tylko Action!

To, że Ty wpadłeś na to teraz.... cóż .... bywa i tak :P

Tdc pisze...

@Ijon Tichy pisze..
nie rozumiem o co chodz z tym przyśpieszeniem. może więcej przykładów?

Może wyjaśnię tyle, że zaprezentowałem tu mechanizm oraz osiągnięte rezultaty, ale nie pokazałem jak to zrobiłem.

kklis, podał przykłady, które opisują podstawę zagadnienia.
Problem tylko w tym, że oba podane przez niego przykłady mają tę samą prędkość (różni się paroma cyklami CPU co jest prawie nieodczuwalne).

A moje odkrycie - tak wyszydzane tutaj przez kilka osób (w tym niektóre znam lub kojarzę) - jest od tego rozwiązania ponad dwa razy szybsze - tak jak to widać na zaprezentowanym screenie - który powinien rozwiać wszelkie wątpliwości wydajnościowe.

Nie może tego cały czas ogarnąć Pecuś, który właśnie na forum napisał, że wszystko wie i rozumie. Tyle że gdyby zaprezentował wydajność tego o czym pisze to dopiero przekonałby się jak nie ma zielonego pojęcia o czym mówi i jedynie uparcie troluje tutaj...

Pecuś... naprawdę na forum już dałem Tobie do rozumienia co myślę o Twoich wywodach, tu ponawiam: nie trać mojego czasu...

Pecuś pisze...

Podaj przykładowy - działający - kod. Każdy będzie mógł to ocenić.
Bo z przykłądów, które podałeś wyżej wynika tylko to, co wszyscy logicznie myślący i programujący troszkę ludze już Ci napisali.

A jeśli te przykłady nie pokazują idei tego "odkrycia", to po zo je umieszczasz, sam prosząc się o krytykę.

zbyti pisze...

@TDC przeciez ja to opisałem rok temu na AOL w watku o pisaniu gry SCRAMBLE w Action! jak i uzywam tego w kodzie tej nieskonczonej gry.

Mozna zadeklarowac tablice o wielkosci bajta wtedy for chodzi po niej wydajnie, tablica jest wskaznikiem wiec mozna jej przypisac nowy adres i wydajnie po niej biegac.

cala magia...

kod jest na atari area.

Pecuś pisze...

@zbyti Śledziłem ten wątek, był na prawdę świetny. Z resztą pokazał wiele ułomności kompilatora Action!

Jeśli dobrze pamiętam, ten zasugerował zadeklarowanie tablicy BYTE o rozmiarze mniejszym niż 256b, bo być może poruszanie się po niej będzie szybsze (oczywista sugestia - sam bym tu szukał miejsca na optymalizację).

W sumie fajny myk, bo przy traktowaniu odwołania do tablicy BYTE jak wskaNika (bo tek traktuje to w zasadzie każdy język) można spokojnie chodzić po pamięci poza tablica (ta o długości 1 bajta.

Jak widać tekst Tomka jest więc w stylu "wiem ale nie powiem" ;p

AdamK pisze...

W architekturze x86, w 1989 w procesorze 486 wprowadzono branch prediction (w motkach jest to od 68040). Pozwala one próbować przewidywać dokąd zaprowadzi skok i wyeliminować (lub w starszych procesorach, drastycznie zmniejszyć) jego koszt. Już w 486 działało to średnio z 90% skutecznością, w nowoczesnych procesorach przekracza 99%. W skrócie polega to na tym, że procesor próbuje przewidzieć dokąd zaprowadzi skok, i jeśli mu się to uda - wykonanie instrukcji skoku będzie kosztować 0 cykli procesora. Tak, 0 cykli, bo przewidywanie jest wykonywane podczas (i równolegle) wykonywania wcześniejszych instrukcji procesora. Jeśli się to nie uda, to wówczas dopiero instrukcja skoku ma jakiś koszt. Jest to podstawowa funkcjonalność, krytyczna dla wydajności procesorów, bez której byłyby one spokojnie o połowę wolniejsze (licząc średnie IPC), jeśli nawet nie wolniejsze.
Z tego też wynika że instrukcja skoku bezwarunkowego zajmuje zawsze 0 cykli procesora, bo zawsze wykonuje skok i 'przewidzianie' tego jest banalne.

Misiek z Nadarzyna pisze...

Przeczytałem sobie ten artykuł i zdaje mi się, że rzeczywiście TeDeC odkrył koło na nowo! Gratulację.

AdamK pisze...

Przepraszam, nieprecyzyjnie się wyraziłem - instrukcja skoku bezwarunkowego zajmie 0 cykli procesora jeśli uda się też przewidzieć cel skoku, co w większości przypadków (stały cel skoku) jest banalne. W bardziej skomplikowanych przypadkach - nadal może to być 0, jeśli tylko cel skoku da się wyliczyć odpowiednio wcześnie.

DAK pisze...

Ale dawno mnie tu nie było :) Czołem TDC, czołem innym tu zebranym.

Gratuluję wygrzebania nowego w starym języku.

[173 $D40B 201 40 208 249]
GG=6
QQ=$9000
FOR Q=0 TO 20 DO
P(QQ)=255 QQ==+1
OD
GG=0

[173 $D40B 201 80 208 249]
GG=6
FOR Q=0 TO 20 DO
FastP(Q)=255
OD
GG=0

Znaczy, tak na chłopski rozum, w pierwszym kodzie odwołujesz się (wykonujesz skok) do konkretnego adresu pamięci, który później za pomocą pętli jest wypełniany.
W drugim zaś ten sam skok wykonujesz za pomocą tablicy zero wymiarowej, która podczas deklaracji automatycznie ma już swój adres do pamięci (nie trzeba go deklarować wcześniej).

dobrze to rozumuję?

Pozdrawiam
dak

Tdc pisze...

O! Cześć DAK!;)
Faktycznie dawno Ciebie tu nie było;)
Zastanawiam się od lat co u Ciebie;)) Kiedyś starałem się zadzwonić, ale nie udało mi się...
Skontaktuj się ze mną - to pogadamy!;)

ps. W naszej książce jest screen, który dobrze znasz!;)))

Tdc pisze...

CIEKAWE!

Tylu anonimowych (oraz co dziwne również nieanonimowych) ekspertów i ujadaczy, a obecnie mamy już prawie 1,5 roku do tego ataku trolli... a ja nie otrzymałem nawet jednego zgłoszenia rozwiązania tego problemu!

Jak to możliwe? Tylu ekspertów od Action! tylu ekspertów od google'a i co?? Nie ma w goolge, czy co???

Czyli wszystko tak jak zwykle...

Anonimowy pisze...

Nie ma żadnej odpowiedzi, bo po prostu nikogo to już nie obchodzi.
Każdy, kto chce mieć szybki kod pisze go sobie w assemblerze. I kod ten (jako całość) będzie zawsze szybszy od generowanego przez biedny - jednoprzebiegowy - kompilator Atcion!

I to niezależnie od tego ile i jakie triki zostaną w nim zastosowane.



Jeśli nie jest zaznaczone inaczej (lub nie jest zaznaczone wcale) zamieszczone ilustracje pochodzą z Wikimedia Commons lub są mojego autorstwa.


Ta strona używa cookies oraz innych technologii Google (i innych firm w specjalnych dodatkach po prawej stronie) w celu prawidłowego działania tej stronki (jej elementów jak np. ankiety, reklamy itp.) oraz zbierania statystyk. Korzystanie z tego bloga powoduje zapisywanie typowych plików na Twoje urządzenie (np. komputer, tablet itp.) o ile w ustawieniach przeglądarki nie zmienisz tego.

W UE się ludziom w głowach przewraca, więc dla świętego spokoju zamieściłem to absurdalne ostrzeżenie...