4 ms·
One thing that you'll notice stands out if you look at this code and compare it to what a compiler might generate is the very efficient use of registers; indeed
by userbinator 7y ago
One thing that you'll notice stands out if you look at this code and compare it to what a compiler might generate is the very efficient use of registers; indeed, a compiler that can do this level of optimisation/code generation would be a "holy grail", but there's been little effort towards that since traditional code generation and optimisation is "good enough" for most purposes. However, as this example shows, the actual limit is still very far away.
- voldacar 7y agoDo you know of any work being done in this area? I'm not that familiar with compiler design but this sounds fascinating.
- azhenley 7y agoThe Wikipedia page has some good info to start with: https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_allocation
- rwmj 7y agoIt's not quite true that no work is done in this area. https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization is an active area of research, where we try to find the optimal code sequence (for various values of "optimal" which could include small size, but more usually highest performance) using various techniques including exhaustive search, annealing and logic programming. (To be fair superoptimizing a 512 byte game is far beyond what could be done today)
- deleted 7y ago[deleted]
- acqq 7y ago> is the very efficient use of registers It's of course more than that: just reading the start, one can see that the author placed the variables immediately after the bytes of the screen, and the screen starts on the position 0. So at the start he clears both the screen and his variables up to the variables "level" and "lives" with: xor ax,ax mov cx,level/2 ; Clear screen and variables (except level/lives) xor di,di rep stosw (Note here that the whole rep stosw loop is 2 bytes only. That's the feature of the 8086 instruction set. The memory was expensive then.) At that moment he will load both the level and the lives variables with just: mov ax,[di] and then increase the level by 2 and store it back inc ax inc ax stosw The last three instructions are encoded with just 3 bytes: 40 inc ax 40 inc ax AB stosw Etc. it's more than just allocating registers, it's having the overview of what one wants and how it can organize the whole to minimize the number of instructions for all tasks together. And, of course, using the instruction set that was designed to save the memory for code. Specifically, in C, as an example, the compiler still expects that it's the programmer who plans the memory layout, it can't reorganize where you place what for you.
- sehugg 7y agoThere are a couple of other neat tricks, like drawing invaders in the pixel color of their array index, so that a complicated collision detection routine is not neccessary.