Megadługaśnie w Basicu by Kaz 2009-05-03 11:27:58
Zgodnie z obietnicą Adam "Urborg" Kaczmarek opisał metodę
uzyskiwania bardzo długich linii programu w Basicu:
Dla jasności dalszych wywodów rozróżnijmy pojęcie wiersza ekranu i linii programu. Wiersz może się składać na Atari z 32, 40 lub 42 znaków. Standardowo, po włączeniu komputera mamy 40 znaków. Z kolei linia programu, jak każdy porządny atarowiec wie, w Atari Basic czy też w Turbo Basic, ma ograniczenie długości do trzech wierszy. Łatwo policzyć, że w standardowym trybie jest to 120 znaków (jeśli zlikwidujemy margines, o czym później). Nie jest to wiele, gdy zależy nam na upchnięciu jak największej liczby komend i parametrów w jednej linii programu. A dlaczego zależy nam na tym upychaniu? Bo taki program zajmuje mniej miejsca w pamięci (oszczędność na numeracji kolejnych linii) i działa szybciej (pętla w jednej linii jest szybsza niż pętla rozbita na kilka linii, ponadto średni czas wykonania Basicowej instrukcji GOTO/GOSUB jest wprost proporcjonalny do ilości linijek w programie).
Większość wie też zapewne, że są pewne sposoby, aby upchnąć w jednej linijce nieco więcej. Po uruchomieniu edytora Basica ujrzymy ekran o szerokości 40 znaków z dwuznakowym marginesem po lewej stronie. Czyli w jednym wierszu ekranu możemy wpisać 38 znaków. Możemy jednak ustawić szerokość marginesu na zero (POKE 82,0) co pozwala uzyskać po dwa dodatkowe znaki w każdym wierszu ekranu. Mamy wtedy dostępne 120 znaków dla całej linii programu długiej na 3 wiersze ekranu. Co jeszcze? Możemy pominąć spacje po numerze linijki, czy pomiędzy instrukcją a wartością numeryczną (na przykład 10GOTO10 czy 20POKE82,0). Ostatnia rzecz to stosowanie skrótów nazw komend (np. O. zamiast OPEN daje możliwość zaoszczędzenia 2 znaków). Sumaryczny zysk nie będzie w sumie powalający, ale zawsze coś. Można w ten sposób uzyskać linijki długie na jakieś 130-150 znaków.
Tymczasem podczas prac nad "Kolony 2106" udało mi się odkryć pewien sposób na obejście wspomnianego ograniczenia. Jak już wcześniej było mówione, upychanie jak największej ilości komend w linijkach oszczędza pamięć i przyśpiesza działanie programu. Jest to więc bardzo przydatna metoda optymalizacji. Łącząc dwie krótkie linijki w jedną dłuższą oszczędzamy 3 bajty, ale to jeszcze nie wszystko. Można zaoszczędzić znacznie więcej, bo dłuższe linijki pozwalają na przebudowanie pewnych konstrukcji programistycznych. Na przykład często spotkać można w programach Basicowych instrukcje warunkowe które kończą się skokiem GOTO/GOSUB. Jest to spowodowane tym, że programista nie był w stanie zmieścić wszystkich instrukcji, które miały być wykonane po spełnieniu warunku z instrukcji warunkowej IF THEN, w jednej linijce. Gdyby linijki programu wydłużyć, wtedy wykonywania skoku możnaby uniknąć. Co prawda Turbo Basic udostępnia instrukcję warunkową IF ENDIF, która ten problem rozwiązuje, ale ta konstrukcja zajmuje trochę więcej pamięci, bo słówko ENDIF kończące instrukcję warunkową zabiera dodatkowe 3 bajty.
Podczas prac nad grą cały czas zmagaliśmy się z brakiem pamięci i siłą rzeczy łapaliśmy się wszelkich możliwych metod optymalizacji. Właśnie podczas prób upychania jak największej liczby komend w jednej linijce udało nam się dokonać pewnego odkrycia.
"Kolony 2106", jak większość obecnych projektów, powstawała na komputerze PC i emulatorze. Dodatkowo, żeby ułatwić sobie życie i przyspieszyć prace nad programem, nie korzystałem z edytora Turbo Basica, lecz z windowsowego Notatnika. Tam wpisywałem linijki które chciałem wprowadzić do programu i zapisywałem w pliku TXT. Potem Plik TXT konwertowałem za pomocą emulatora na format ATASCII (Misc/Convert/ASCII to ATASCII z opcją "EOL only"). Plik wynikowy dołączałem do pliku ATR za pomoca programiku "MakeATR". Następnie zaś plik ATR podpinałem do emulatora i wczytywałem gotowe linijki za pomocą komendy ENTER do pamięci. Jak wszystko było OK zapisywałem program komendą SAVE. No i tak się złożyło, że pewnego pięknego dnia odkryłem, że postępując w ten sposób mogę wpisać w jednej linijce sporo więcej niż normalnie. Wygląda bowiem na to, że ograniczenie długości do trzech linii jest tylko i wyłącznie ograniczeniem wymuszonym przez edytor Turbo Basica. Sam interpreter bez problemu radzi sobie z dłuższymi linijkami. Zacząłem więc testować, ile tak naprawdę da się w ten sposób maksymalnie wpisać. Okazało się, że wprowadzając dane za pomocą komendy ENTER pojedyncza linijka może mieć 254 znaki czyli ponad dwa razy więcej niż normalnie. Próba wprowadzenia większej ilości zaowocuje błędem numer 137. Mimo wszystko da się wprowadzić jeszcze więcej! Można przecież zastosować skróty nazw i pomijanie spacji.
Nie trudno sobie wyobrazić jakie oszczędności mogłoby przynieść zastosowanie tej metody do całego programu "Kolony 2106" czy też innego programu tej wielkości. Kilkaset linijek, o które dałoby się skrócić program, pomnożone przez 3 bajty za każdą linijkę to oszczędność, którą trudno byłoby przecenić. Wydawało się to wręcz zbyt piękne, by było prawdziwe. Zaczęło mi się więc rodzić w głowie podejrzenie, że to może działa tylko na emulatorze, a na prawdziwym Atari będzie kicha. Ponieważ nie dysponowałem wówczas ani stacją dysków ani interfejsem SIO2SD, poprosiłem Arka Lubaszkę, aby sprawdził na swoim sprzęcie czy taki program faktycznie zadziała. Arek, którego ta nowość bardzo zaciekawiła, szybko i fachowo porobił stosowne testy, które dały wynik pozytywny: na prawdziwym Atari to też działało! Po ostatecznych konsultacjach zdecydowaliśmy się więc na zastosowanie tej metody do całego kodu "Kolony 2106".
Podsumowując - cała metoda sprowadza sie do przygotowania gotowych linijek programu w jakimś innym edytorze niż standardowy edytor Turbo Basica czy Atari Basica, a potem wprowadzeniu ich za pomocą instrukcji ENTER. Okazuje się, że z takimi linijkami kompilator Turbo Basica też sobie radzi, choć obawiam się, że prawdopodobnie po kompilacji zysk w postaci krótszego i szybszego programu znika.
To by było na tyle. Metody nie zamierzam opatentować, ani zastrzegać, więc wszyscy zainteresowani mogą robić z niej dowolny użytek i stosować ją w swoich programach, kiedy tylko przyjdzie im na to ochota. Czego sobie i wszystkim atarowcom życzę.
Dla jasności dalszych wywodów rozróżnijmy pojęcie wiersza ekranu i linii programu. Wiersz może się składać na Atari z 32, 40 lub 42 znaków. Standardowo, po włączeniu komputera mamy 40 znaków. Z kolei linia programu, jak każdy porządny atarowiec wie, w Atari Basic czy też w Turbo Basic, ma ograniczenie długości do trzech wierszy. Łatwo policzyć, że w standardowym trybie jest to 120 znaków (jeśli zlikwidujemy margines, o czym później). Nie jest to wiele, gdy zależy nam na upchnięciu jak największej liczby komend i parametrów w jednej linii programu. A dlaczego zależy nam na tym upychaniu? Bo taki program zajmuje mniej miejsca w pamięci (oszczędność na numeracji kolejnych linii) i działa szybciej (pętla w jednej linii jest szybsza niż pętla rozbita na kilka linii, ponadto średni czas wykonania Basicowej instrukcji GOTO/GOSUB jest wprost proporcjonalny do ilości linijek w programie).
Większość wie też zapewne, że są pewne sposoby, aby upchnąć w jednej linijce nieco więcej. Po uruchomieniu edytora Basica ujrzymy ekran o szerokości 40 znaków z dwuznakowym marginesem po lewej stronie. Czyli w jednym wierszu ekranu możemy wpisać 38 znaków. Możemy jednak ustawić szerokość marginesu na zero (POKE 82,0) co pozwala uzyskać po dwa dodatkowe znaki w każdym wierszu ekranu. Mamy wtedy dostępne 120 znaków dla całej linii programu długiej na 3 wiersze ekranu. Co jeszcze? Możemy pominąć spacje po numerze linijki, czy pomiędzy instrukcją a wartością numeryczną (na przykład 10GOTO10 czy 20POKE82,0). Ostatnia rzecz to stosowanie skrótów nazw komend (np. O. zamiast OPEN daje możliwość zaoszczędzenia 2 znaków). Sumaryczny zysk nie będzie w sumie powalający, ale zawsze coś. Można w ten sposób uzyskać linijki długie na jakieś 130-150 znaków.
Tymczasem podczas prac nad "Kolony 2106" udało mi się odkryć pewien sposób na obejście wspomnianego ograniczenia. Jak już wcześniej było mówione, upychanie jak największej ilości komend w linijkach oszczędza pamięć i przyśpiesza działanie programu. Jest to więc bardzo przydatna metoda optymalizacji. Łącząc dwie krótkie linijki w jedną dłuższą oszczędzamy 3 bajty, ale to jeszcze nie wszystko. Można zaoszczędzić znacznie więcej, bo dłuższe linijki pozwalają na przebudowanie pewnych konstrukcji programistycznych. Na przykład często spotkać można w programach Basicowych instrukcje warunkowe które kończą się skokiem GOTO/GOSUB. Jest to spowodowane tym, że programista nie był w stanie zmieścić wszystkich instrukcji, które miały być wykonane po spełnieniu warunku z instrukcji warunkowej IF THEN, w jednej linijce. Gdyby linijki programu wydłużyć, wtedy wykonywania skoku możnaby uniknąć. Co prawda Turbo Basic udostępnia instrukcję warunkową IF ENDIF, która ten problem rozwiązuje, ale ta konstrukcja zajmuje trochę więcej pamięci, bo słówko ENDIF kończące instrukcję warunkową zabiera dodatkowe 3 bajty.
Podczas prac nad grą cały czas zmagaliśmy się z brakiem pamięci i siłą rzeczy łapaliśmy się wszelkich możliwych metod optymalizacji. Właśnie podczas prób upychania jak największej liczby komend w jednej linijce udało nam się dokonać pewnego odkrycia.
"Kolony 2106", jak większość obecnych projektów, powstawała na komputerze PC i emulatorze. Dodatkowo, żeby ułatwić sobie życie i przyspieszyć prace nad programem, nie korzystałem z edytora Turbo Basica, lecz z windowsowego Notatnika. Tam wpisywałem linijki które chciałem wprowadzić do programu i zapisywałem w pliku TXT. Potem Plik TXT konwertowałem za pomocą emulatora na format ATASCII (Misc/Convert/ASCII to ATASCII z opcją "EOL only"). Plik wynikowy dołączałem do pliku ATR za pomoca programiku "MakeATR". Następnie zaś plik ATR podpinałem do emulatora i wczytywałem gotowe linijki za pomocą komendy ENTER do pamięci. Jak wszystko było OK zapisywałem program komendą SAVE. No i tak się złożyło, że pewnego pięknego dnia odkryłem, że postępując w ten sposób mogę wpisać w jednej linijce sporo więcej niż normalnie. Wygląda bowiem na to, że ograniczenie długości do trzech linii jest tylko i wyłącznie ograniczeniem wymuszonym przez edytor Turbo Basica. Sam interpreter bez problemu radzi sobie z dłuższymi linijkami. Zacząłem więc testować, ile tak naprawdę da się w ten sposób maksymalnie wpisać. Okazało się, że wprowadzając dane za pomocą komendy ENTER pojedyncza linijka może mieć 254 znaki czyli ponad dwa razy więcej niż normalnie. Próba wprowadzenia większej ilości zaowocuje błędem numer 137. Mimo wszystko da się wprowadzić jeszcze więcej! Można przecież zastosować skróty nazw i pomijanie spacji.
dwie przykładowe linijki kodu "Kolony
2106"
Nie trudno sobie wyobrazić jakie oszczędności mogłoby przynieść zastosowanie tej metody do całego programu "Kolony 2106" czy też innego programu tej wielkości. Kilkaset linijek, o które dałoby się skrócić program, pomnożone przez 3 bajty za każdą linijkę to oszczędność, którą trudno byłoby przecenić. Wydawało się to wręcz zbyt piękne, by było prawdziwe. Zaczęło mi się więc rodzić w głowie podejrzenie, że to może działa tylko na emulatorze, a na prawdziwym Atari będzie kicha. Ponieważ nie dysponowałem wówczas ani stacją dysków ani interfejsem SIO2SD, poprosiłem Arka Lubaszkę, aby sprawdził na swoim sprzęcie czy taki program faktycznie zadziała. Arek, którego ta nowość bardzo zaciekawiła, szybko i fachowo porobił stosowne testy, które dały wynik pozytywny: na prawdziwym Atari to też działało! Po ostatecznych konsultacjach zdecydowaliśmy się więc na zastosowanie tej metody do całego kodu "Kolony 2106".
Podsumowując - cała metoda sprowadza sie do przygotowania gotowych linijek programu w jakimś innym edytorze niż standardowy edytor Turbo Basica czy Atari Basica, a potem wprowadzeniu ich za pomocą instrukcji ENTER. Okazuje się, że z takimi linijkami kompilator Turbo Basica też sobie radzi, choć obawiam się, że prawdopodobnie po kompilacji zysk w postaci krótszego i szybszego programu znika.
To by było na tyle. Metody nie zamierzam opatentować, ani zastrzegać, więc wszyscy zainteresowani mogą robić z niej dowolny użytek i stosować ją w swoich programach, kiedy tylko przyjdzie im na to ochota. Czego sobie i wszystkim atarowcom życzę.
Kaz 2009-05-03 11:32:32
Adam, potrafisz oszacowac, ile pamieci udalo sie uzyskac po wszystkich optymalizacjach w stosunku do oryginalnej gry?
gokparhan 2009-05-03 11:53:58
olum verin su oyunuda
urborg 2009-05-03 12:09:56
Trudno to tak dokładnie oszacować. Kolony zajmowało praktycznie cała dostępną pamięć czyli około 40 kilobajtów. Szacuję że rzeczy które dodaliśmy ważyły conajmniej z 10 kilobajtów. Ale będa to zawsze bardzo zgrubne szacunki. Wiele rzeczy udało się dodać tanim kosztem tylko dlatego, że pewne procedury używane w Kolony zostały zastąpione nowymi uniwersalnymi procedurami dzięki czemu ten sam kod jest używany często po kilka razy w róznych miejscach programu.
mono 2009-05-03 20:00:11
Bardzo fajna technika! A gdyby zrobić ENTER "E:" i wprowadzać program zakończony sekwencją CONTROL+3?
larek 2009-05-03 20:24:25
Urządzenie "E:" to systemowy edytor, więc nic z tego nie będzie. Tu właśnie chodzi o to, aby ominąć to ograniczenie.
bob_er 2009-05-03 20:28:11
z ciekawosci: procedura txt->lst byla jakos oskryptowana, czy recznie robiona?
sikor 2009-05-03 20:46:12
Ale edytor ACTION! powinien dać radę (do 240 znaków, o ile dobrze pamiętam). Lub prawie dowolny edytor tekstu dla Atari też ;)
urborg 2009-05-03 20:57:01
bob_er: ręcznie. Zmiany były jednak najczęściej wprowadzane hurtowo po kilkadziesiąt linijek naraz.
MDW 2009-05-04 11:32:27
No i wszystko się wyjaśniło. Fajnie. :) Czytelność takiego kodu na pewno się nie zwiększa ale oszczędności są znaczne, a to ma w tym przypadku wyższy priorytet. Gratuluję odkrycia.
A tak swoją drogą to szkoda, że nigdy nie powstały jakieś lepsze edytory do Basica/TurboBasica. Oczywiście żeby zostawało tyle pamięci ile Basic ma normalnie. Czy to byłoby niemożliwe na jakimś rozszerzeniu pamięci?
Jeżeli dobrze pamiętam (ostatni raz robiłem to w 1993 roku) to ? FREE(0) pokazywało 37902 bajty. :)
Rozyk 2009-05-04 22:45:11
A nie dałoby się "zpatchować" Basica lub TB aby przyjmował dłuższe linie? Powinno się dać........... Pytanie do ekspertów ASM.
tdc 2009-05-04 23:27:20
Adam nie tu uświadomił, że tu jest mowa o optymalizacji kodu dla Basic ;) No to mamy już komplet ;) (Action! itp.)
Fajny art.
Sikor: Action! ma faktyczne ograniczenie 8 bitowe, ale chyba jest ono mniejsze o kilka bajtów - nie pamiętam dokładnie (ale chyba jak się przekroczy tę magiczną wartość np. 253 znaki to się chyba action! sypie...). Ale pewny nie jestem
Pamiętam natomiast, że często robiłem takie jazdy że wczytywałem programy z Basic do Action! itp.
tdc 2009-05-04 23:28:16
oczywiście miało być: "Adam mnie tu uświadomił"
urborg 2009-05-05 07:00:10
patchować basica nie trzeba. Wystarczyłoby spaczować edytor basica, bo interpreter nie ma nic przeciwko długim linijkom. Ciekawy jestem jak długie linijki tak naprawdę może obsłużyć interpreter. Może nie ma ograniczeń? Ten błąd 137 o którym pisałem to przepełnienie bufora odczytu dla instrukcji ENTER.
Adam, potrafisz oszacowac, ile pamieci udalo sie uzyskac po wszystkich optymalizacjach w stosunku do oryginalnej gry?
gokparhan 2009-05-03 11:53:58
olum verin su oyunuda
urborg 2009-05-03 12:09:56
Trudno to tak dokładnie oszacować. Kolony zajmowało praktycznie cała dostępną pamięć czyli około 40 kilobajtów. Szacuję że rzeczy które dodaliśmy ważyły conajmniej z 10 kilobajtów. Ale będa to zawsze bardzo zgrubne szacunki. Wiele rzeczy udało się dodać tanim kosztem tylko dlatego, że pewne procedury używane w Kolony zostały zastąpione nowymi uniwersalnymi procedurami dzięki czemu ten sam kod jest używany często po kilka razy w róznych miejscach programu.
mono 2009-05-03 20:00:11
Bardzo fajna technika! A gdyby zrobić ENTER "E:" i wprowadzać program zakończony sekwencją CONTROL+3?
larek 2009-05-03 20:24:25
Urządzenie "E:" to systemowy edytor, więc nic z tego nie będzie. Tu właśnie chodzi o to, aby ominąć to ograniczenie.
bob_er 2009-05-03 20:28:11
z ciekawosci: procedura txt->lst byla jakos oskryptowana, czy recznie robiona?
sikor 2009-05-03 20:46:12
Ale edytor ACTION! powinien dać radę (do 240 znaków, o ile dobrze pamiętam). Lub prawie dowolny edytor tekstu dla Atari też ;)
urborg 2009-05-03 20:57:01
bob_er: ręcznie. Zmiany były jednak najczęściej wprowadzane hurtowo po kilkadziesiąt linijek naraz.
MDW 2009-05-04 11:32:27
No i wszystko się wyjaśniło. Fajnie. :) Czytelność takiego kodu na pewno się nie zwiększa ale oszczędności są znaczne, a to ma w tym przypadku wyższy priorytet. Gratuluję odkrycia.
A tak swoją drogą to szkoda, że nigdy nie powstały jakieś lepsze edytory do Basica/TurboBasica. Oczywiście żeby zostawało tyle pamięci ile Basic ma normalnie. Czy to byłoby niemożliwe na jakimś rozszerzeniu pamięci?
Jeżeli dobrze pamiętam (ostatni raz robiłem to w 1993 roku) to ? FREE(0) pokazywało 37902 bajty. :)
Rozyk 2009-05-04 22:45:11
A nie dałoby się "zpatchować" Basica lub TB aby przyjmował dłuższe linie? Powinno się dać........... Pytanie do ekspertów ASM.
tdc 2009-05-04 23:27:20
Adam nie tu uświadomił, że tu jest mowa o optymalizacji kodu dla Basic ;) No to mamy już komplet ;) (Action! itp.)
Fajny art.
Sikor: Action! ma faktyczne ograniczenie 8 bitowe, ale chyba jest ono mniejsze o kilka bajtów - nie pamiętam dokładnie (ale chyba jak się przekroczy tę magiczną wartość np. 253 znaki to się chyba action! sypie...). Ale pewny nie jestem
Pamiętam natomiast, że często robiłem takie jazdy że wczytywałem programy z Basic do Action! itp.
tdc 2009-05-04 23:28:16
oczywiście miało być: "Adam mnie tu uświadomił"
urborg 2009-05-05 07:00:10
patchować basica nie trzeba. Wystarczyłoby spaczować edytor basica, bo interpreter nie ma nic przeciwko długim linijkom. Ciekawy jestem jak długie linijki tak naprawdę może obsłużyć interpreter. Może nie ma ograniczeń? Ten błąd 137 o którym pisałem to przepełnienie bufora odczytu dla instrukcji ENTER.