Tabela liderów - Kompilacja JIT (Im niższa, tym lepiej)
- es1024 - 81,2 punktów (w tym działający kompilator!)
- Kieth Randall - 116 punktów
- Ell - 121 punktów
Tabela liderów - interpretowana (im niższa, tym lepiej)
- Martin Büttner - 706654 punktów (około 2 godzin).
- criptych - 30379 punktów (97 sekund)
Twoim zadaniem, jeśli zdecydujesz się to zaakceptować, jest napisanie możliwie najmniejszego interpretera kodu wirtualnego / VM. VM / interpreter używa małej architektury CISC (operacje mogą różnić się rozmiarem), z językiem określonym poniżej. Po zakończeniu należy wydrukować wartość 3 rejestrów procesora, aby udowodnić, że wydrukowano prawidłowe dane wyjściowe (3 126 900 366).
Kompilator
Jeśli chcesz wykonać własne testy, poniżej znajduje się kompilator. Możesz opublikować swoje testy wraz z odpowiedzią.
Specyfikacje „VM”
Maszyna wirtualna ma 3 32-bitowe rejestry integralne bez znaku: R0, R1, R2. Są one reprezentowane w postaci szesnastkowej jako 0x00, 0x01 i 0x02.
Obsługiwane są następujące operacje:
Format to [nazwa] [... operandy ...], [szesnastkowy kod operacji] [... operandy powtórzone ...]
- LOAD [rejestr] [wartość 4 bajtów], 0x00 [rejestr] [wartość 4 bajtów]
- PUSH [rejestr], 0x02 [rejestr]
- POP [rejestr], 0x03 [rejestr]
- ADD [rejestr, 1 bajt] [rejestr, 1 bajt], 0x04 [rejestr] [rejestr]
- SUB [rejestr, 1 bajt] [rejestr, 1 bajt], 0x05 [rejestr] [rejestr]
- MUL [rejestr, 1 bajt] [rejestr, 1 bajt], 0x06 [rejestr] [rejestr]
- DIV [rejestr, 1 bajt] [rejestr, 1 bajt], 0x07 [rejestr] [rejestr]
- JMP [linia kodu, 4 bajty], 0x08 [4 bajtowy numer linii kodu]
- CMP [rejestr, 1 bajt] [rejestr, 1 bajt], 0x09 [rejestr] [rejestr]
- BRANCHLT [linia kodu, 4 bajty], 0x0a [4 bajtowy numer linii kodu]
Niektóre uwagi:
- Powyższe operacje matematyczne sumują wartości 2 rejestrów, umieszczając dane wyjściowe w pierwszym rejestrze.
- CMP, operator porównania, powinien porównywać wartości 2 rejestrów i przechowywać dane wyjściowe w jakiejś wewnętrznej fladze (może to być specyficzne dla implementacji) do przyszłego wykorzystania w instrukcjach oddziału.
- Jeśli BRANCH zostanie wywołany przed CMP, chyba że BRANCHEQ zostanie wywołany, „VM” nie powinno się rozgałęziać.
- PUSH / POP nie zaskakuje push i pop numery ze stosu.
- Operatory skoku i rozgałęzienia skaczą do określonej operacji (wiersza kodu), a nie do adresu binarnego.
- Oddziały nie wykonują porównania. Zamiast tego wykonują dane wyjściowe z ostatniego porównania.
- Operatorzy rozgałęzień i skoków korzystają z systemu indeksowania numerów linii opartego na zerach. (Np. JMP 0 przeskakuje do pierwszej linii)
- Wszystkie operacje należy wykonywać na liczbach bez znaku, które przepełniają się do zera i nie zgłaszają wyjątku w przypadku przepełnienia liczb całkowitych.
- Dzielenie przez zero jest niedozwolone i jako takie zachowanie programu nie jest zdefiniowane. Możesz (na przykład) ...
- Awaria programu.
- Zakończ wykonywanie maszyny wirtualnej i zwróć jej bieżący stan.
- Pokaż komunikat „ERR: Dzielenie przez 0”.
- Zakończenie programu definiuje się, gdy wskaźnik instrukcji osiąga koniec programu (można założyć, że program nie jest pusty).
Dane wyjściowe Dane wyjściowe muszą być dokładnie takie (łącznie z nowymi wierszami)
R0 3126900366
R1 0
R2 10000
Punkty
Punkty są obliczane na podstawie następującego wzoru:Number Of Characters * (Seconds Needed To Run / 2)
Aby uniknąć różnic sprzętowych powodujących różne czasy, każdy test będzie uruchamiany na moim komputerze (i5-4210u, 8 GB pamięci RAM) na serwerze Ubuntu lub w systemie Windows 8, więc staraj się nie używać szalonego, egzotycznego środowiska wykonawczego, które kompiluje się tylko na Dual G5 Mac Pro z dokładnie 762,66 MB wolnej pamięci RAM.
Jeśli używasz specjalistycznego środowiska wykonawczego / języka, opublikuj link do niego.
- Dla zainteresowanych stron opublikowałem kod testowy (napisany w C #) tutaj: http://pastebin.com/WYCG5Uqu
Program testowy
Pomysł przyszedł stąd , więc użyjemy nieco zmodyfikowanej wersji ich programu.
Prawidłowe wyjście dla programu to: 3 126 900 366
W C:
int s, i, j;
for (s = 0, i = 0; i < 10000; i++) {
for (j = 0; j < 10000; j++)
s += (i * j) / 3;
}
W kodzie: [R0 jest reprezentatywne dla s, R1 dla j, R2 dla i]
LOAD R0 0
LOAD R2 0 <--outer loop value
LOAD R1 0 <--inner loop value
--Begin inner loop--
PUSH R1 <--push inner loop value to the stack
MUL R1 R2 <--(i*j)
PUSH R2
LOAD R2 3
DIV R1 R2 <-- / 3
POP R2
ADD R0 R1 <-- s+=
POP R1
PUSH R2
LOAD R2 1
ADD R1 R2 <--j++
POP R2
PUSH R2
LOAD R2 10000
CMP R1 R2 <-- j < 10000
POP R2
BRANCHLT 3 <--Go back to beginning inner loop
--Drop To outer loop--
LOAD R1 1
ADD R2 R1 <--i++
LOAD R1 10000
CMP R2 R1 <-- i < 10000
LOAD R1 0 <--Reset inner loop
BRANCHLT 2
W systemie binarnym / szesnastkowym:
0x00 0x00 0x00 0x00 0x00 0x00
0x00 0x02 0x00 0x00 0x00 0x00
0x00 0x01 0x00 0x00 0x00 0x00
0x02 0x01
0x06 0x01 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x03
0x07 0x01 0x02
0x03 0x02
0x04 0x00 0x01
0x03 0x01
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x01
0x04 0x01 0x02
0x03 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x27 0x10
0x09 0x01 0x02
0x03 0x02
0x0a 0x00 0x00 0x00 0x03
0x00 0x01 0x00 0x00 0x00 0x01
0x04 0x02 0x01
0x00 0x01 0x00 0x00 0x27 0x10
0x09 0x02 0x01
0x00 0x01 0x00 0x00 0x00 0x00
0x0a 0x00 0x00 0x00 0x02
Punkty bonusowe (Efekty są stosowane multiplikacyjnie) Np. Jeśli zakwalifikujesz się do wszystkich trzech, będzie to ((znaki * 0,50) * 0,75) * 0,90
- 50% mniej, jeśli interpreter jest w rzeczywistości kompilatorem JIT
- Zmniejszenie o 25%, jeśli zastosuje jakiekolwiek rozwinięcie pętli / znaczącą optymalizację.
- 10% mniej, jeśli rozszerzysz maszynę wirtualną o
- BRANCHEQ [linia kodu, 4 bajty] (rozgałęzienie, jeśli jest równe - kod operacji 0x0b)
- BRANCHGT [linia kodu, 4 bajty] (rozgałęzienie, jeśli jest większe niż - kod operacji 0x0c)
- BRANCHNE [linia kodu, 4 bajty] (Rozgałęzienie, jeśli nie jest równe - kod operacji 0x0d)
- RLOAD [rejestr 1] [rejestr 2] (przenieś wartość rejestru 2 do rejestru 1 - kod operacji 0x01).
Niedozwolone
- Kompilowanie przypadku testowego w programie jest zabronione. Musisz zaakceptować kod bajtowy ze STDIN lub z pliku (nie ważne które).
- Zwracanie wyniku bez uruchamiania programu.
- W inny sposób możesz oszukać wymaganie maszyny wirtualnej.
źródło
CMP
sprawdza mniej niż lub równość? A co dzieje się z jego wynikiem?MUL
iDIV
są również nieokreślone. Czy powinny być podpisane czy niepodpisane? Co dzieje się w przypadku przepełnienia mnożenia?Odpowiedzi:
C, 752 (589 + 163 dla definicji flag) * 0,5 (JIT) * 0,9 (rozszerzenia) * (optymalizacja 0,75) * (0,64 sekundy / 2) = 81,216
Pobiera kod (
LOAD R0
itp.), Bez znaków końcowych, pojedynczej spacji, bez pustych linii na środku, bez komentarzy itp. Wymagany jest znak nowej linii.Jest to następnie konwertowane na kod bajtowy 80386 i wykonywane.
Ładowanie
0
do rejestru otrzymujexor
ing rejestr ze sobą zamiastmov
ing0
do rejestru, który jest trzy bajty krótszy w wygenerowanego kodu bajtowego, a może być bardzo nieznacznie szybciej.Połącz z:
Wymagany system operacyjny zgodny z POSIX.
Dane wejściowe są odczytywane ze STDIN (użyj
./bytecode < file
do potokowania z pliku).Wynikowy kod bajtowy dla programu testowego:
Nie golfowany:
źródło
C, wynik = 854 bajtów × (~ 0,8 s / 2) × 0,5 [JIT] × 0,9 [Rozszerzenia] = ~ 154 bajtów s
Kompiluj z
gcc vm.c -ovm -m32 -w
systemem operacyjnym zgodnym z POSIX x86.Uruchom z
./vm < program
, gdzieprogram
jest binarny plik programu.Idę po prędkość. Program wykonuje dość proste tłumaczenie programu wejściowego na kod maszynowy x86 i pozwala procesorowi wykonać resztę.
Na przykład oto tłumaczenie programu testowego.
ecx
,esi
Iedi
odpowiadająR0
,R1
iR2
, odpowiednio;bh
posiada flagi stanu;eax
iedx
są rejestrami typu scratch; stos wywołań odpowiada stosowi maszyny wirtualnej:Bez golfa
Pokaż fragment kodu
źródło
CJam,
222187185 bajtów * (za wolny / 2)Chciałem tylko zobaczyć, jak krótko mogę uzyskać maszynę wirtualną z kodem bajtowym, pisząc ją w CJam. Mniej niż 200 bajtów wydaje się całkiem przyzwoite. Ale to cholernie powolne, ponieważ sam CJam jest interpretowany. Uruchomienie programu testowego trwa wieki.
Aby go uruchomić, pobierz interpreter Java pod tym linkiem sourceforge , zapisz kod
vm.cjam
i uruchom goProgram oczekuje kodu bajtowego na STDIN. Nie znalazłem jeszcze sposobu na przesłanie danych binarnych do programu, bez dodania przez PowerShell łamania linii końcowej i konwersji
0x0a
do0x0d 0x0a
, co jest naprawdę denerwujące. Kod zawiera 4 bajty do naprawienia tego (D-);
), którego nie uwzględniłem w całkowitej liczbie, ponieważ nie jest to coś, co program powinien zrobić, jeśli faktycznie otrzymał kod bajtowy na STDIN, zamiast jakiejś dziwnie zakodowanej jego wersji . Jeśli ktoś zna rozwiązanie tego problemu, daj mi znać.Nieznacznie nie golfista:
Dodam jutro właściwe wyjaśnienie.
Krótko mówiąc, przechowuję wszystkie rejestry, wskaźnik instrukcji i flagę porównania w zmiennych, dzięki czemu mogę zachować stos CJam jako stos maszyny wirtualnej.
źródło
python / c ++, wynik = 56,66
1435 znaków *. 234/2 sekundy * .5 [JIT] * .75 [Optymalizacja] * .90 [Dodatkowe instrukcje]
Kompiluje program wejściowy do c ++, uruchamia na nim gcc, a następnie uruchamia wynik. Większość czasu spędza się w gcc.
Jedyną optymalizacją, którą wykonuję, jest zredukowanie operacji stosu do zmiennych jawnych, jeśli jest to dozwolone semantycznie. To bardzo pomaga, około 10-krotnie lepszy czas działania skompilowanego kodu (około 0,056 s, aby uruchomić wynikowy plik binarny). Nie jestem pewien, co robi gcc, co daje ci taką poprawę, ale to dobrze.
Z pewnością można by jeszcze zagrać w golfa.
źródło
Lua 5.2 (lub LuaJIT), 740 bajtów
Pierwsza próba, tylko minimalnie golfa. Ta wersja działa (przynajmniej w programie testowym) i implementuje dodatkowe kody operacyjne, ale nie spełnia wymogu matematycznego niepodpisanego i nie jest szczególnie szybka. Jako bonus jest to jednak maszyna wirtualna działająca na maszynie wirtualnej i jest napisana w taki sposób, że może być interpretowana (uruchamiana za pomocą PUC-Lua) lub w rodzaju JIT (uruchamiana za pomocą LuaJIT; nadal interpretowana, ale interpreter jest teraz JITted).
EDYCJA: Lepsza gra w golfa, wciąż duża.
EDYCJA: Naprawiono poważny błąd, a teraz ogranicza arytmetykę do
unsigned long
zasięgu. Jednak jakoś udało się uchronić rozmiar przed wymknięciem się spod kontroli, ale nadal daje złą odpowiedź.EDYCJA: Okazuje się, wynik był poprawny, ale wynik nie. Przełączono na drukowanie z
%u
zamiast%d
i wszystko jest w porządku. Wyłączyłem również rejestry tabel dla zmiennych, aby nieco poprawić rozmiar i prędkość.EDYCJA: Używając
goto
instrukcji Lua 5.2 (dostępnej również w LuaJIT) zastąpiłem interpreter „JIT-to-Lua”, generując kod, który jest uruchamiany bezpośrednio przez samą maszynę wirtualną Lua. Nie jestem pewien, czy to naprawdę liczy się jako JIT, ale poprawia prędkość.Oto oryginalna, czytelna wersja.
źródło
<
zamiast tego użyłem pętli<=
, więc ostatnia instrukcja rozgałęzienia została pominięta. Nadal otrzymuje złą odpowiedź, ale teraz zajmuje to kilka minut. :)DO#
15051475 bajtówTo jest moja wersja interpretera, napisana w C # może być zoptymalizowana / gra w golfa, myślę, ale tak naprawdę nie wiem gdzie;)
wersja golfowa:
edytować
usunięto niektóre niepotrzebne
public
iprivate
modyfikatory:nazwij go,
executable.exe filename
gdziefilename
jest plik zawierający kod do interpretacjiMój „program testowy”:
Interpreter niepolity z długimi nazwami zmiennych, klas, ...
źródło