10 ms·

Yes. By the way this feature of Doom was allowing nice and symmetric multiplayer over slow modem or network lines. Only small client-side packets were send thro

Yes. By the way this feature of Doom was allowing nice and symmetric multiplayer over slow modem or network lines. Only small client-side packets were send through the network (think keystrokes/mouse movement updates). As a different example Quake was designed using a client/server model with hugely asymmetric packet sizes (~40 bytes for client->server packet and ~800 bytes for the opposite direction). As a teenager at around 1996-1997 I once tried to re-factor Quake to use the same model as Doom - run server/client combo on both machines with servers synchronized using exact same random generator seeds / etc. Spend about two months on that, but it had proved to be very difficult - the sync between the servers was inevitably lost due to some indeterminism in the code that I couldn't uncover. Maximum that I was able to achieve was around two seconds running in sync. And I still don't know where the sync was getting lost ;) Learned a lot from that experience, big thank you to John Carmack (and the Id Software team) for writing that code as good and clean as he/(they) did...

TheLoneWolfling 11y ago
Probably floating-point oddities. The bane of deterministic programming everywhere.
- tobinfricke 11y ago
  Floating point is deterministic.
  - dilmuff 11y ago
    For distributed scenarios where the architecture, language and library are unspecified and effectively random, it is not. Not so long ago x87 80-bit precision was common while non x87 systems typically used single and double precision. Finally, IEEE-754 does not specify transcendental functions, so once you use those your results vary all over the place as approximations vary. The fact that Go does not use the the CRT for FP will demonstrate this in the real world.
  - munificent 11y ago
    On a single chip, yes. But different chips handle some corner cases differently, leading to divergence between machines.
    - TheLoneWolfling 11y ago
      Actually with C / C++, it can be different even with the same chip. It can actually be different using the same binary and still be compliant. Something like this: if( a == x/y ) assert( a == x/y ); Is allowed to assert (!). It's also allowed to not assert. Worse, the following is a legal "optimization" of the above code: if( a == x/y ) if ( getRandomBooleanFromSomewhere() ) assert( a == x/y ); (I'd use rand, but I don't want to get into matters of state here. Just assume that getRandomBooleanFromSomewhere, well, pulls a random boolean from somewhere. No side effects.) Why, you might ask? It's allowed to use extra precision, but not required to. And it's not required to even be consistent about it. So: if it uses extra precision, and it decides to lose the extra precision (say, by spilling x/y to stack) between the first and second uses, the assert could potentially fire. If it doesn't do both of those, the assert cannot fire. So it's legal to remove the assert, but also legal to keep it. And also legal to randomly decide which to do at runtime. Now, this is a stupid thing for it to do in this case. But nonetheless, it is allowed. And there are cases where analogous optimizations actually make a plausible amount of sense. You can work around it to an extent with FPU flags. But that way lies madness. To put it mildly. ("It desyncs when I print a document.")
      - lmm 11y ago
        AIUI the C standard mostly regards floating-point as out of scope / platform-specific. Your vendor should (hopefully) provide stricter specs for how it works on your particular machine.
        TheLoneWolfling 11y ago
        The particular machine tends to be deterministic. It's the compiler that's mainly the problem here. Or rather, the language standard.
  - dandelany 11y ago
    Technically, maybe, sort of. http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo...
  - DougMerritt 11y ago
    So is rand() and similar. The point is that Heisenbugs and such at the app level are hard to debug because behavior is not absolutely repeatable under what seem to humans to be identical circumstances. That most certainly gives the appearance of non-determinism. And floating point is frequently infamously tricky to deal with, I think is the obvious point without arguing terminology.
  - TheLoneWolfling 11y ago
    If only. Even something as simple as this, where x and y and a are floating-point values: if( a == x/y ) assert( a == x/y ); Is legally allowed to trigger (!). Worse, it's also legally allowed to not trigger. That's right. The above can be legally compiled to always trigger, or never trigger, or even to sometimes trigger (although this is rare in practice). Why? C / C++ allow floats to be stored with excess precision. And they lose that excess precision when spilled to RAM. And GCC isn't deterministic. So x/y may be pulled out as a common subexpression and spilled to a register after the first usage, and it triggers. And then the next time it isn't, and it doesn't. (Effectively, the difference between this: temp = x/y if( a == temp) { spill(temp); assert( a == temp ); } and this: temp = x/y if( a == temp) { assert( a == temp ); } Yes, it'll (generally - though the standard doesn't dictate that it will be!) be deterministic in terms of always with a given example in an single binary triggering or not triggering, but that is irrelevant, as binaries aren't cross-platform and you aren't always loading exactly the same binaries of the dynamic libraries you've linked to. You can (most of the time) work around this by manually setting FPU precision (note that you need to change the precision of both the mantissa and exponent, as otherwise you can still end up with issues). (Except that you, in C++ at least, have to work deep magic - you have to set it before main even runs, because you can end up with problems with static initialization otherwise.) And in the process losing compatibility. And finding that random code you call occasionally resets things. Or random code you don't call (a classic example: the printer driver!). And using exactly one of float or double throughout. And hoping that none of the libraries you use ever resets FPU precision for anything, or uses the other of float or double itself. (And hope that your OS properly saves / restores the FPU everywhere, though this has largely become a non-issue). And, worst of all, you've got to hope that the compiler performs constant folding with the same level of care as you've just taken. Look at these: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845 http://yosefk.com/blog/consistency-how-to-defeat-the-purpose-of-ieee-floating-point.html http://yosefk.com/blog/consistency-how-to-defeat-the-purpose... http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo... http://www.yosoygames.com.ar/wp/2013/07/on-floating-point-determinism/ http://www.yosoygames.com.ar/wp/2013/07/on-floating-point-de...
  - limaoscarjuliet 11y ago
    I am one of the authors of Fire Fight game, which had the same multi-player model as Doom. Main source of multi-player sync loss was a different number of rand() calls between machines e.g. a different animation sequence for own character vs enemy. If own animation calls one rand() too many, the next common rand will return diff values on own vs enemy machines. And you essentially start playing two different games together ;-) That being said, we fixed all bugs. There were no additional checks to synchronize state other than keyboards. It was way easier than we anticipated! Good times!
    - TheLoneWolfling 11y ago
      That was what, 1996? Unfortunately, many of the edge cases that cause non-deterministic behavior have gotten substantially more exploited by compilers since then.
      - limaoscarjuliet 11y ago
        I really want to disagree. Assuming the code is correct: - proper handling of system calls and EINTR, - do not call illegal functions in signal handlers, - proper synchronization to avoid race conditions, - etc. it will work just fine. The problems with today's systems does not lie in compilers. It lies in vastly increased complexity of the code itself. Back in 96 we had a few sprites, with some animation sequence, sound effects. State of an object was kept in a few integers. Collisions were done using really stupid algorithm that would probe special mask in level builder with a circle consisting of 16 points, so we can get a vector pointing away from the wall. Etc. Today, collisions, physics, presentation - all this is thousands of times more complex. More code, more bugs, more issues. For that reason, it would be very difficult to write keyboard-state driven multiplayer today.
        TheLoneWolfling 11y ago
        Ah, you weren't using floating-point. That makes things substantially easier. W.r.t. floating-point, good luck. See https://news.ycombinator.com/item?id=9430958 https://news.ycombinator.com/item?id=9430958
  - cbd1984 11y ago
    Deterministic but too hard to predict is a form of non-determinism, as far as humans are concerned.
    - TheLoneWolfling 11y ago
      It's not even deterministic. At least for anything that ever passes through C or C++, or uses code that does. (I.e. everything, close enough.) See: https://news.ycombinator.com/item?id=9431372 https://news.ycombinator.com/item?id=9431372
  - willvarfar 11y ago
    Different machines have different internal precision. See http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo... Games I've worked on have used libraries e.g. http://nicolas.brodu.net/programmation/streflop/index.html http://nicolas.brodu.net/programmation/streflop/index.html
  - fancyketchup 11y ago
    Not necessarily. The x87 implementation (which is relevant to everything PC, prior to SSE) of IEEE 754 internally uses an 80-bit extended precision representation for floating point numbers. Numbers are rounded to 64 bits for loads and stores of course... Now, what do you suppose happens during a context switch, when a second process wants to use floating point math?
    - zurn 11y ago
      You can save/load 80-bit values to memory with the regular x87 instructions, it's just called "extended precision". And the accelerated "save FPU state" instructions save the full 80-bit state. Otherwise it would be pretty nutty. Where you can get unpredictable (though still repeatable) behaviour is when your compiler spills into 64-bit memory slots, and does it a little differently with each little modification to the code.
  - shultays 11y ago
    May not be same on different machines
    - TheLoneWolfling 11y ago
      May not even be the same on the same machine. At least if you're using C or C++ (or anything that ever passes through C or C++, i.e. almost everything.)
- tachyonbeam 11y ago
  Quake 1 & 2 largely used fixed point arithmetic, for speed, AFAIK.
  - clarry 11y ago
    They've got fixed point code in a few spots (especially where it makes sense if you're e.g. indexing into a texture), but the original Quake source really says float all over the place.
elwell 11y ago
Cool. Do you have blog that talks about old game hacks?
bananaboy 11y ago
The Quake and QuakeWorld source weren't released until 1999.
- dchichkov 11y ago
  Yes. It was that leaked version, not the officially released code. Fortunately Id Software was very cool about the leak, looks like they've even accepted patches :) """ wikipedia John Carmack ... and the Doom source code in 1997. When the source code to Quake was leaked and circulated among the Quake community underground in 1996, a programmer unaffiliated with Id Software used it to port Quake to Linux, and subsequently sent the patches to Carmack. Instead of pursuing legal action, Id Software, at Carmack's behest, used the patches as the foundation for a company-sanctioned Linux port.[citation needed] Id Software has since publicly released the source code to Quake, Quake 2....

TheLoneWolfling 11y ago

Probably floating-point oddities. The bane of deterministic programming everywhere.

tobinfricke 11y ago
Floating point is deterministic.
- dilmuff 11y ago
  For distributed scenarios where the architecture, language and library are unspecified and effectively random, it is not. Not so long ago x87 80-bit precision was common while non x87 systems typically used single and double precision. Finally, IEEE-754 does not specify transcendental functions, so once you use those your results vary all over the place as approximations vary. The fact that Go does not use the the CRT for FP will demonstrate this in the real world.
- munificent 11y ago
  On a single chip, yes. But different chips handle some corner cases differently, leading to divergence between machines.
  - TheLoneWolfling 11y ago
    Actually with C / C++, it can be different even with the same chip. It can actually be different using the same binary and still be compliant. Something like this: if( a == x/y ) assert( a == x/y ); Is allowed to assert (!). It's also allowed to not assert. Worse, the following is a legal "optimization" of the above code: if( a == x/y ) if ( getRandomBooleanFromSomewhere() ) assert( a == x/y ); (I'd use rand, but I don't want to get into matters of state here. Just assume that getRandomBooleanFromSomewhere, well, pulls a random boolean from somewhere. No side effects.) Why, you might ask? It's allowed to use extra precision, but not required to. And it's not required to even be consistent about it. So: if it uses extra precision, and it decides to lose the extra precision (say, by spilling x/y to stack) between the first and second uses, the assert could potentially fire. If it doesn't do both of those, the assert cannot fire. So it's legal to remove the assert, but also legal to keep it. And also legal to randomly decide which to do at runtime. Now, this is a stupid thing for it to do in this case. But nonetheless, it is allowed. And there are cases where analogous optimizations actually make a plausible amount of sense. You can work around it to an extent with FPU flags. But that way lies madness. To put it mildly. ("It desyncs when I print a document.")
    - lmm 11y ago
      AIUI the C standard mostly regards floating-point as out of scope / platform-specific. Your vendor should (hopefully) provide stricter specs for how it works on your particular machine.
      - TheLoneWolfling 11y ago
        The particular machine tends to be deterministic. It's the compiler that's mainly the problem here. Or rather, the language standard.
- dandelany 11y ago
  Technically, maybe, sort of. http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo...
- DougMerritt 11y ago
  So is rand() and similar. The point is that Heisenbugs and such at the app level are hard to debug because behavior is not absolutely repeatable under what seem to humans to be identical circumstances. That most certainly gives the appearance of non-determinism. And floating point is frequently infamously tricky to deal with, I think is the obvious point without arguing terminology.
- TheLoneWolfling 11y ago
  If only. Even something as simple as this, where x and y and a are floating-point values: if( a == x/y ) assert( a == x/y ); Is legally allowed to trigger (!). Worse, it's also legally allowed to not trigger. That's right. The above can be legally compiled to always trigger, or never trigger, or even to sometimes trigger (although this is rare in practice). Why? C / C++ allow floats to be stored with excess precision. And they lose that excess precision when spilled to RAM. And GCC isn't deterministic. So x/y may be pulled out as a common subexpression and spilled to a register after the first usage, and it triggers. And then the next time it isn't, and it doesn't. (Effectively, the difference between this: temp = x/y if( a == temp) { spill(temp); assert( a == temp ); } and this: temp = x/y if( a == temp) { assert( a == temp ); } Yes, it'll (generally - though the standard doesn't dictate that it will be!) be deterministic in terms of always with a given example in an single binary triggering or not triggering, but that is irrelevant, as binaries aren't cross-platform and you aren't always loading exactly the same binaries of the dynamic libraries you've linked to. You can (most of the time) work around this by manually setting FPU precision (note that you need to change the precision of both the mantissa and exponent, as otherwise you can still end up with issues). (Except that you, in C++ at least, have to work deep magic - you have to set it before main even runs, because you can end up with problems with static initialization otherwise.) And in the process losing compatibility. And finding that random code you call occasionally resets things. Or random code you don't call (a classic example: the printer driver!). And using exactly one of float or double throughout. And hoping that none of the libraries you use ever resets FPU precision for anything, or uses the other of float or double itself. (And hope that your OS properly saves / restores the FPU everywhere, though this has largely become a non-issue). And, worst of all, you've got to hope that the compiler performs constant folding with the same level of care as you've just taken. Look at these: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845 http://yosefk.com/blog/consistency-how-to-defeat-the-purpose-of-ieee-floating-point.html http://yosefk.com/blog/consistency-how-to-defeat-the-purpose... http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo... http://www.yosoygames.com.ar/wp/2013/07/on-floating-point-determinism/ http://www.yosoygames.com.ar/wp/2013/07/on-floating-point-de...
- limaoscarjuliet 11y ago
  I am one of the authors of Fire Fight game, which had the same multi-player model as Doom. Main source of multi-player sync loss was a different number of rand() calls between machines e.g. a different animation sequence for own character vs enemy. If own animation calls one rand() too many, the next common rand will return diff values on own vs enemy machines. And you essentially start playing two different games together ;-) That being said, we fixed all bugs. There were no additional checks to synchronize state other than keyboards. It was way easier than we anticipated! Good times!
  - TheLoneWolfling 11y ago
    That was what, 1996? Unfortunately, many of the edge cases that cause non-deterministic behavior have gotten substantially more exploited by compilers since then.
    - limaoscarjuliet 11y ago
      I really want to disagree. Assuming the code is correct: - proper handling of system calls and EINTR, - do not call illegal functions in signal handlers, - proper synchronization to avoid race conditions, - etc. it will work just fine. The problems with today's systems does not lie in compilers. It lies in vastly increased complexity of the code itself. Back in 96 we had a few sprites, with some animation sequence, sound effects. State of an object was kept in a few integers. Collisions were done using really stupid algorithm that would probe special mask in level builder with a circle consisting of 16 points, so we can get a vector pointing away from the wall. Etc. Today, collisions, physics, presentation - all this is thousands of times more complex. More code, more bugs, more issues. For that reason, it would be very difficult to write keyboard-state driven multiplayer today.
      - TheLoneWolfling 11y ago
        Ah, you weren't using floating-point. That makes things substantially easier. W.r.t. floating-point, good luck. See https://news.ycombinator.com/item?id=9430958 https://news.ycombinator.com/item?id=9430958
- cbd1984 11y ago
  Deterministic but too hard to predict is a form of non-determinism, as far as humans are concerned.
  - TheLoneWolfling 11y ago
    It's not even deterministic. At least for anything that ever passes through C or C++, or uses code that does. (I.e. everything, close enough.) See: https://news.ycombinator.com/item?id=9431372 https://news.ycombinator.com/item?id=9431372
- willvarfar 11y ago
  Different machines have different internal precision. See http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/ http://gafferongames.com/networking-for-game-programmers/flo... Games I've worked on have used libraries e.g. http://nicolas.brodu.net/programmation/streflop/index.html http://nicolas.brodu.net/programmation/streflop/index.html
- fancyketchup 11y ago
  Not necessarily. The x87 implementation (which is relevant to everything PC, prior to SSE) of IEEE 754 internally uses an 80-bit extended precision representation for floating point numbers. Numbers are rounded to 64 bits for loads and stores of course... Now, what do you suppose happens during a context switch, when a second process wants to use floating point math?
  - zurn 11y ago
    You can save/load 80-bit values to memory with the regular x87 instructions, it's just called "extended precision". And the accelerated "save FPU state" instructions save the full 80-bit state. Otherwise it would be pretty nutty. Where you can get unpredictable (though still repeatable) behaviour is when your compiler spills into 64-bit memory slots, and does it a little differently with each little modification to the code.
- shultays 11y ago
  May not be same on different machines
  - TheLoneWolfling 11y ago
    May not even be the same on the same machine. At least if you're using C or C++ (or anything that ever passes through C or C++, i.e. almost everything.)
tachyonbeam 11y ago
Quake 1 & 2 largely used fixed point arithmetic, for speed, AFAIK.
- clarry 11y ago
  They've got fixed point code in a few spots (especially where it makes sense if you're e.g. indexing into a texture), but the original Quake source really says float all over the place.

elwell 11y ago

Cool. Do you have blog that talks about old game hacks?

bananaboy 11y ago

The Quake and QuakeWorld source weren't released until 1999.

dchichkov 11y ago
Yes. It was that leaked version, not the officially released code. Fortunately Id Software was very cool about the leak, looks like they've even accepted patches :) """ wikipedia John Carmack ... and the Doom source code in 1997. When the source code to Quake was leaked and circulated among the Quake community underground in 1996, a programmer unaffiliated with Id Software used it to port Quake to Linux, and subsequently sent the patches to Carmack. Instead of pursuing legal action, Id Software, at Carmack's behest, used the patches as the foundation for a company-sanctioned Linux port.[citation needed] Id Software has since publicly released the source code to Quake, Quake 2....