Tabla de clasificación - JIT compilado (más bajo es mejor)
- es1024 - 81.2 puntos (¡incluido un compilador que funciona!)
- Kieth Randall - 116 puntos
- Ell - 121 puntos
Tabla de clasificación - Interpretada (más bajo es mejor)
- Martin Büttner - 706654 puntos (alrededor de 2 horas).
- críptico - 30379 puntos (97 segundos)
Su misión, si elige aceptarla, es escribir el intérprete / VM de bytecode más pequeño posible. El VM / intérprete utiliza una pequeña arquitectura CISC (las operaciones pueden variar en tamaño), con el lenguaje que se especifica a continuación. Al finalizar, debe imprimir el valor de los 3 registros de la CPU para demostrar que se imprime la salida correcta (3,126,900,366).
Compilador
Si desea hacer sus propias pruebas, a continuación se publica un compilador. Siéntase libre de publicar sus exámenes con su respuesta.
Especificaciones "VM"
La VM tiene 3 registros integrales sin signo de 32 bits: R0, R1, R2. Se representan en hexadecimal como 0x00, 0x01 y 0x02.
Se deben admitir las siguientes operaciones:
El formato es [nombre] [... operandos ...], [código de operación hexadecimal] [... operandos repetidos ...]
- LOAD [registro] [valor de 4 bytes], 0x00 [registro] [valor de 4 bytes]
- PUSH [registro], 0x02 [registro]
- POP [registro], 0x03 [registro]
- ADD [registro, 1 byte] [registro, 1 byte], 0x04 [registro] [registro]
- SUB [registro, 1 byte] [registro, 1 byte], 0x05 [registro] [registro]
- MUL [registro, 1 byte] [registro, 1 byte], 0x06 [registro] [registro]
- DIV [registro, 1 byte] [registro, 1 byte], 0x07 [registro] [registro]
- JMP [línea de código, 4 bytes], 0x08 [número de línea de código de 4 bytes]
- CMP [registro, 1 byte] [registro, 1 byte], 0x09 [registro] [registro]
- BRANCHLT [línea de código, 4 bytes], 0x0a [número de línea de código de 4 bytes]
Algunas notas:
- Las operaciones matemáticas anteriores suman los valores de 2 registros, colocando la salida en el primer registro.
- CMP, el operador de comparación, debe comparar los valores de 2 registros y almacenar la salida en algún indicador interno (esto puede ser específico de la implementación) para uso futuro en instrucciones de bifurcación.
- Si se llama BRANCH antes que CMP, a menos que se llame BRANCHEQ, la "VM" no debe bifurcarse.
- PUSH / POP, como era de esperar, empuja o saca números de la pila.
- Los operadores Jump y Branch saltan a una operación específica (línea de código), no a una dirección binaria.
- Las operaciones de sucursal no hacen la comparación. Por el contrario, toman la salida de la última comparación para ejecutar.
- Los operadores Branch y Jump utilizan un sistema de indexación de número de línea basado en cero. (Por ejemplo, JMP 0 salta a la primera línea)
- Todas las operaciones deben realizarse en números sin signo que se desbordan a cero y no arrojan una excepción en un desbordamiento de enteros.
- La división por cero no está permitida y, como tal, el comportamiento del programa no está definido. Puedes (por ejemplo) ...
- Bloquea el programa.
- Finalice la ejecución de la VM y devuelva su estado actual.
- Mostrar un mensaje "ERR: División por 0".
- La terminación del programa se define como cuando el puntero de instrucción llega al final del programa (se puede suponer un programa no vacío).
Salida La salida debe ser exactamente esto (nuevas líneas incluidas)
R0 3126900366
R1 0
R2 10000
Puntos Los
puntos se calculan según la siguiente fórmula:Number Of Characters * (Seconds Needed To Run / 2)
Para evitar diferencias de hardware que causen tiempos diferentes, cada prueba se ejecutará en mi computadora (i5-4210u, 8GB ram) en el servidor ubuntu o Windows 8, así que trate de no usar un tiempo de ejecución increíblemente exótico que solo se compila en un Dual G5 Mac Pro con exactamente 762.66 mb de RAM libre.
Si está utilizando un lenguaje / tiempo de ejecución especializado, publique un enlace a él.
- Para las partes interesadas, he publicado el código de prueba (escrito en C #) aquí: http://pastebin.com/WYCG5Uqu
Programa de prueba
La idea surgió de aquí , por lo que utilizaremos una versión algo modificada de su programa.
La salida correcta para el programa es: 3,126,900,366
Cía:
int s, i, j;
for (s = 0, i = 0; i < 10000; i++) {
for (j = 0; j < 10000; j++)
s += (i * j) / 3;
}
En el código: [R0 es representativo de s, R1 de j, R2 de 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
En binario / hexadecimal:
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
Puntos de bonificación (los efectos se aplican multiplicativamente) Por ejemplo, si califica para los tres, sería ((caracteres * 0.50) * 0.75) * 0.90
- Disminución del 50% si el intérprete es realmente un compilador JIT
- Disminución del 25% si aplica algún tipo de desenrollamiento de bucle / optimización significativa.
- 10% de disminución si extiende la VM con
- BRANCHEQ [línea de código, 4 bytes] (Rama si es igual - código de operación 0x0b)
- BRANCHGT [línea de código, 4 bytes] (Rama si es mayor que - opcode 0x0c)
- BRANCHNE [línea de código, 4 bytes] (Rama si no es igual - código de operación 0x0d)
- RLOAD [registro 1] [registro 2] (mueve el valor del registro 2 al registro 1 - código de operación 0x01).
No permitido
- Precompilar el caso de prueba en el programa está prohibido. Debe aceptar el código de bytes de STDIN o de un archivo (no importa cuál).
- Devolver la salida sin ejecutar el programa.
- Cualquier otra forma que se te ocurra para engañar al requisito de VM.
fuente
CMP
Verifica por menos que o igualdad? ¿Y qué pasa con su resultado?MUL
yDIV
también están subespecificados. ¿Deben estar firmados o sin firmar? ¿Qué sucede en el desbordamiento de multiplicación?Respuestas:
C, 752 (589 + 163 para definir banderas) * 0.5 (JIT) * 0.9 (extensiones) * (optimización 0.75) * (0.64 segundos / 2) = 81.216
Toma código (
LOAD R0
, etc.), sin caracteres finales, espacio simple, sin líneas en blanco en el medio, sin comentarios, etc. Se requiere una nueva línea final.Esto se convierte a 80386 bytecode y se ejecuta.
Carga
0
en un registro se sustituye porxor
ing el registro con ella misma en lugar demov
ing0
en el registro, que es de tres bytes más corto en el código de bytes generada, y puede ser muy marginalmente más rápido.Compilar con:
Se requiere un sistema operativo compatible con POSIX.
La entrada se lee desde STDIN (use
./bytecode < file
para canalizar desde un archivo).Código de bytes resultante para el programa de prueba:
Sin golf:
fuente
C, Puntuación = 854 bytes × (~ 0.8 segundos / 2) × 0.5 [JIT] × 0.9 [Extensiones] = ~ 154 bytes segundos
Compile con
gcc vm.c -ovm -m32 -w
un SO compatible con POSIX x86.Ejecutar con
./vm < program
, dondeprogram
es un archivo de programa binario.A por la velocidad. El programa realiza una traducción bastante directa del programa de entrada al código de máquina x86 y permite que la CPU haga el resto.
Por ejemplo, aquí está la traducción del programa de prueba.
ecx
,esi
yedi
corresponden aR0
,R1
yR2
, respectivamente;bh
sostiene las banderas de estado;eax
yedx
son registros de cero; la pila de llamadas corresponde a la pila de la VM:Sin golf
Mostrar fragmento de código
fuente
CJAM,
222187185 bytes * (demasiado lento / 2)Solo quería ver qué tan corto puedo obtener un bytecode VM escribiéndolo en CJam. Menos de 200 bytes parece bastante decente. Sin embargo, es muy lento, porque CJam en sí mismo se interpreta. Lleva años ejecutar el programa de prueba.
Para ejecutarlo, descargue el intérprete de Java en este enlace de sourceforge , guarde el código
vm.cjam
y ejecútelo conEl programa espera el bytecode en STDIN. No he encontrado una manera todavía datos binarios tubo en un programa, sin PowerShell añadir un salto de línea de arrastre y convertir
0x0a
a0x0d 0x0a
, que es realmente molesto. El código incluye 4 bytes para arreglar eso (D-);
), que no he incluido en el recuento total, porque no es algo que el programa deba hacer si realmente recibió el bytecode en STDIN, en lugar de alguna versión extrañamente codificada de este. . Si alguien conoce una solución para eso, hágamelo saber.Ligeramente incólume:
Agregaré una explicación adecuada mañana.
En resumen, estoy almacenando todos los registros, el puntero de instrucciones y el indicador de comparación en variables, para que pueda mantener la pila de CJam libre para usar como pila de VM.
fuente
python / c ++, puntaje = 56.66
1435 caracteres * .234 / 2 segundos * .5 [JIT] * .75 [Optimización] * .90 [Instrucciones adicionales]
Compila el programa de entrada en c ++, ejecuta gcc en él y luego ejecuta el resultado. La mayor parte del tiempo se gasta dentro de gcc.
La optimización que hago es reducir las operaciones de pila a variables explícitas si se permite semánticamente. Ayuda mucho, aproximadamente 10 veces mejor tiempo de ejecución del código compilado (aproximadamente 0,056 segundos para ejecutar realmente el binario resultante). No estoy seguro de lo que está haciendo gcc que te da esa mejora, pero es bueno.
Ciertamente se podría jugar un poco más.
fuente
Lua 5.2 (o LuaJIT), 740 bytes
Primer intento, solo mínimamente golf. Esta versión funciona (al menos en el programa de prueba) e implementa los códigos de operación adicionales, pero no cumple con el requisito matemático sin firmar y no es particularmente rápido. Sin embargo, como beneficio adicional, es una máquina virtual que se ejecuta en una máquina virtual, y está escrita de tal manera que se puede interpretar (ejecutar con PUC-Lua) o una especie de JIT (ejecutar con LuaJIT; aún se interpreta, pero el intérprete ahora es JITADO).
EDITAR: Golf mejor, aún grande.
EDITAR: se corrigió un error importante y ahora restringe la aritmética al
unsigned long
rango. Sin embargo, de alguna manera logró evitar que el tamaño se saliera de control, pero aún así da la respuesta incorrecta.EDITAR: Resulta que el resultado fue correcto pero la salida no. Cambió a imprimir con en
%u
lugar de%d
y todo está bien. También cambió los registros basados en tablas para variables para mejorar el tamaño y la velocidad.EDITAR: Utilizando la
goto
declaración de Lua 5.2 (también disponible en LuaJIT), he reemplazado el intérprete con "JIT-to-Lua", generando código que es ejecutado directamente por la propia máquina virtual de Lua. No estoy seguro de si esto realmente cuenta como JIT, pero mejora la velocidad.Aquí está la versión original y legible.
fuente
<
mis bucles en lugar de<=
, por lo que se dejó la instrucción de ramificación final. Todavía recibe la respuesta incorrecta, pero ahora tarda unos minutos en hacerlo. :)C#
15051475 bytesEsta es mi versión del intérprete, escrito en C # podría optimizarse / jugar más, creo, pero realmente no sé dónde;)
versión de golf:
editar
eliminado algunos innecesarios
public
yprivate
modificadores:llámalo con
executable.exe filename
dóndefilename
está el archivo que contiene el código a interpretarMi "programa de prueba":
Intérprete sin golfista con nombres más largos variables, clases, ...
fuente