5 ms·

Compiling Quake 3 Virtual Machines To JavaScript

100 points by mariuz 13y ago

jevinskie 13y ago
It would be cool if it compiled either LCC assembly or QVM bytecode to LLVM IR. Now you have all of LLVM's optimizations! Finally, spit out the JS using Emscripten like the rest of the project.
- ris 13y ago
  I thought that too, but remember this has to all be done at runtime, so depending on LLVM would require an Emscripten-ized version of LLVM (does such a thing exist?) to be distributed with the generated js and similarly depending on Emscripten would require a copy of Emscripten to be distributed with the generated js. And from what I hear the runtime performance of Emscripten itself ain't that great.
  - derefr 13y ago
    Why does this have to be done at runtime, exactly? How many mods (or rather, QVM files) were there? And are people still making them? If the answer is "less than 100K" and "no, of course not," then you can probably get away with: 1. compiling all the QVM files to their Javascript equivalents ahead-of-time; 2. stuffing them all on a CDN (with each JS blob named after the md5 of the relevant QVM source); and then 3. having a "compiler" in your client that just hashes the source it's about to "compile", and requests the blob with that hash from your CDN. Of course, if the amount of generated JS is small enough, you could even just serve it all with the client. I'm doubting that one, though; it's probably at least 50MB of code. (Though it might be heavily redundant code... it could compress very well!)
    - ris 13y ago
      > Why does this have to be done at runtime, exactly? Because that's how quake3 works. What you're describing would be incompatible with all other quake3 clients. And part of the point of implementing the QVM in the first place is compatibility.
- inolen1 13y ago
  I actually did that first: https://github.com/inolen/qvmc https://github.com/inolen/qvmc It worked, but the main issue was related to object file generation. Basically, you have to allocate one big i8 array to represent all of the QVM's data segments (including its bss segment). This doesn't translate well once compiled with Emscripten, as bss relocation is on a per-variable basis. For one of the Quake 3 Fortress QVMs which was only a few hundred kb it output a ~50mb .bc file and a ~70mb .js file of mostly 0s. I experimented with storing each segment as its own i8 array (which could be 0 initialized for the bss segment) in a packed struct, which significantly lowered the .bc file size. However, while I was looking into what I'd need to change in Emscripten to support this, I instead decided to go the route of writing the runtime compiler. Fun fact: Quake 3 mods didn't have access to malloc / free, so it wasn't uncommon to have large amounts of static, 0 initialized data.
cgdangelo 13y ago
Very nice. Glad to see CPMA in there. :-)
webbedhands 13y ago
What is up with that comment?
- sho_hn 13y ago
  It's the guy writing TempleOS. Google around, you're in for an interesting story.
  - itry 13y ago
    Does he have a new hn account? I love to read his stuff. But the account "losethos" has been inactive for over a month now.
    - mjn 13y ago
      He still posts but his comments are auto-killed. You can see the comments if you turn on showdead in your preferences.
    - odonnellryan 13y ago
      He has changed the name of his OS multiple times. Might have some luck with the latest name, but you'd have to dig for it.
    - uptown 13y ago
      Here's your primer: https://twitter.com/losethos https://twitter.com/losethos http://www.templeos.org/ http://www.templeos.org/
    - phpnode 13y ago
      https://news.ycombinator.com/user?id=TempleOSV2 https://news.ycombinator.com/user?id=TempleOSV2
  - TazeTSchnitzel 13y ago
    https://web.archive.org/web/20130629121009/http://qaa.ath.cx/LoseThos.html https://web.archive.org/web/20130629121009/http://qaa.ath.cx...
_random_ 13y ago
'Transpiling' since it kind of converts to a scripting language not a native code.
- jahewson 13y ago
  'Translation' would be the word of choice from PL literature. But there's such a significant transformation going on here that compiling seems quite apt.
- pacala 13y ago
  asm.js is portable assembly with a jit assembler. In that sense, it's even closer to "native code" than C, as C requires a separate compilation step.
  - Pacabel 13y ago
    That's not true at all. Asm.js is just a subset of JavaScript that is far more machine-friendly than it is human-friendly. Having a worse syntax than C or normal JavaScript doesn't mean that it's closer to native code or anything like that. And the compilation step is still there in both cases. It doesn't matter if it's just-in-time compilation or ahead-of-time compilation; it's still compilation, and it's still there.
    - CmonDev 13y ago
      Precisely. Until there are CPUs with direct asm.js support (hopefully not though).
  - eliasmacpherson 13y ago
    I am confused, there are JIT compilers for C: http://code.google.com/p/asmjit/ http://code.google.com/p/asmjit/ http://homepage1.nifty.com/herumi/soft/xbyak_e.html http://homepage1.nifty.com/herumi/soft/xbyak_e.html How is asm.js different to those?
    - Pacabel 13y ago
ItendToDisagree 13y ago
This is pretty crazy impressive! The performance gain particularly. Is that much of a gain expected?
- ori_b 13y ago
  I'm impressed, but I'm not particularly surprised. The initial code was interpreted, while the new code is JIT compiled. I have no data to back this up, but I suspect that if instead of generating javascript, he generated x86 assembly, you'd see a similar speedup. Possibly a larger one.
  - Scaevolus 13y ago
    That's exactly what Quake3 did natively, and it gave a large performance boost.
    - inolen1 13y ago
      Right. Pulling from JC's August 16, 1999 .plan (http://floodyberry.com/carmack/johnc_plan_1999.html#d19990816 http://floodyberry.com/carmack/johnc_plan_1999.html#d1999081...) when he first wrote the x86 compiler: Q3demo1 dll: 52.9 Compiled: 50.2 Interpreted: 43.9 Q3demo2 dll: 50.1 Compiled: 46.5 Interpreted: 38.7

100 points by mariuz 13y ago

It would be cool if it compiled either LCC assembly or QVM bytecode to LLVM IR. Now you have all of LLVM's optimizations! Finally, spit out the JS using Emscripten like the rest of the project.

ris 13y ago
I thought that too, but remember this has to all be done at runtime, so depending on LLVM would require an Emscripten-ized version of LLVM (does such a thing exist?) to be distributed with the generated js and similarly depending on Emscripten would require a copy of Emscripten to be distributed with the generated js. And from what I hear the runtime performance of Emscripten itself ain't that great.
- derefr 13y ago
  Why does this have to be done at runtime, exactly? How many mods (or rather, QVM files) were there? And are people still making them? If the answer is "less than 100K" and "no, of course not," then you can probably get away with: 1. compiling all the QVM files to their Javascript equivalents ahead-of-time; 2. stuffing them all on a CDN (with each JS blob named after the md5 of the relevant QVM source); and then 3. having a "compiler" in your client that just hashes the source it's about to "compile", and requests the blob with that hash from your CDN. Of course, if the amount of generated JS is small enough, you could even just serve it all with the client. I'm doubting that one, though; it's probably at least 50MB of code. (Though it might be heavily redundant code... it could compress very well!)
  - ris 13y ago
    > Why does this have to be done at runtime, exactly? Because that's how quake3 works. What you're describing would be incompatible with all other quake3 clients. And part of the point of implementing the QVM in the first place is compatibility.
inolen1 13y ago
I actually did that first: https://github.com/inolen/qvmc https://github.com/inolen/qvmc It worked, but the main issue was related to object file generation. Basically, you have to allocate one big i8 array to represent all of the QVM's data segments (including its bss segment). This doesn't translate well once compiled with Emscripten, as bss relocation is on a per-variable basis. For one of the Quake 3 Fortress QVMs which was only a few hundred kb it output a ~50mb .bc file and a ~70mb .js file of mostly 0s. I experimented with storing each segment as its own i8 array (which could be 0 initialized for the bss segment) in a packed struct, which significantly lowered the .bc file size. However, while I was looking into what I'd need to change in Emscripten to support this, I instead decided to go the route of writing the runtime compiler. Fun fact: Quake 3 mods didn't have access to malloc / free, so it wasn't uncommon to have large amounts of static, 0 initialized data.

cgdangelo 13y ago

Very nice. Glad to see CPMA in there. :-)

webbedhands 13y ago

What is up with that comment?

sho_hn 13y ago
It's the guy writing TempleOS. Google around, you're in for an interesting story.
- itry 13y ago
  Does he have a new hn account? I love to read his stuff. But the account "losethos" has been inactive for over a month now.
  - mjn 13y ago
    He still posts but his comments are auto-killed. You can see the comments if you turn on showdead in your preferences.
  - odonnellryan 13y ago
    He has changed the name of his OS multiple times. Might have some luck with the latest name, but you'd have to dig for it.
  - uptown 13y ago
    Here's your primer: https://twitter.com/losethos https://twitter.com/losethos http://www.templeos.org/ http://www.templeos.org/
  - phpnode 13y ago
    https://news.ycombinator.com/user?id=TempleOSV2 https://news.ycombinator.com/user?id=TempleOSV2
- TazeTSchnitzel 13y ago
  https://web.archive.org/web/20130629121009/http://qaa.ath.cx/LoseThos.html https://web.archive.org/web/20130629121009/http://qaa.ath.cx...

_random_ 13y ago

'Transpiling' since it kind of converts to a scripting language not a native code.

jahewson 13y ago
'Translation' would be the word of choice from PL literature. But there's such a significant transformation going on here that compiling seems quite apt.
pacala 13y ago
asm.js is portable assembly with a jit assembler. In that sense, it's even closer to "native code" than C, as C requires a separate compilation step.
- Pacabel 13y ago
  That's not true at all. Asm.js is just a subset of JavaScript that is far more machine-friendly than it is human-friendly. Having a worse syntax than C or normal JavaScript doesn't mean that it's closer to native code or anything like that. And the compilation step is still there in both cases. It doesn't matter if it's just-in-time compilation or ahead-of-time compilation; it's still compilation, and it's still there.
  - CmonDev 13y ago
    Precisely. Until there are CPUs with direct asm.js support (hopefully not though).
- eliasmacpherson 13y ago
  I am confused, there are JIT compilers for C: http://code.google.com/p/asmjit/ http://code.google.com/p/asmjit/ http://homepage1.nifty.com/herumi/soft/xbyak_e.html http://homepage1.nifty.com/herumi/soft/xbyak_e.html How is asm.js different to those?
  - Pacabel 13y ago

ItendToDisagree 13y ago

This is pretty crazy impressive! The performance gain particularly. Is that much of a gain expected?

ori_b 13y ago
I'm impressed, but I'm not particularly surprised. The initial code was interpreted, while the new code is JIT compiled. I have no data to back this up, but I suspect that if instead of generating javascript, he generated x86 assembly, you'd see a similar speedup. Possibly a larger one.
- Scaevolus 13y ago
  That's exactly what Quake3 did natively, and it gave a large performance boost.
  - inolen1 13y ago
    Right. Pulling from JC's August 16, 1999 .plan (http://floodyberry.com/carmack/johnc_plan_1999.html#d19990816 http://floodyberry.com/carmack/johnc_plan_1999.html#d1999081...) when he first wrote the x86 compiler: Q3demo1 dll: 52.9 Compiled: 50.2 Interpreted: 43.9 Q3demo2 dll: 50.1 Compiled: 46.5 Interpreted: 38.7