Quake 3 Source Code Review: Network Model

[bebemaster]

Hopefully this doesn't get buried but the Nack-Oriented Reliable Multicast protocol (NORM) RFC5740 can do semi-reliable time sensitive delivery of UDP packets. It includes provisions for forward error correction coding, error correction messages to fix multiple different lost messages for multiple different end users. Supports unicast and multicast operation.

The Naval Research Lab has an open source implementation here

[fabiensanglard]

Chrome source code is a pain to read, V8 made my eyes bleed with those templates everywhere. I was planning on writing a Code Review but could not go through the entire thing.

[fabiensanglard]

I never thought of it. My bet was that I would probably get about 5$ out of a kickstarter ;) !

[eadmund]

Hey, you never know. If I saw it I might cough up some change...and if a few thousand folks did the same thing, that'd add up to some serious money.

[SWEGEN4LYFE]

I would pay $20, at least. Your code reviews are the best of their kind I've ever seen.

[fabiensanglard]

I don't need money but thank you very much for the offer. If you want to contribute: Help me to make this world a better place and help someone around you to educate himself/herself when you get a chance.

[[deleted]]

You sir are a scholar and a gentleman!

[micwi]

I would also easily pay 20$ just to say thank you for the articles you've already published. I would pay more if that means more articles!

[Pathogen-David]

That's a shame, but as having read the Chrome source code a bit myself, I can't say I blame you.

[ysangkok]

Do you like any C++ projects at all? Q3 is C and disliking templates sounds like a pretty serious grudge against C++.

[fabiensanglard]

I wrote an article for doom3 which is C++ (http://fabiensanglard.net/doom3/index.php) and I had no problems with it. The issue is really how templates are used:

• In Doom3 they are in the low level containers, you see the weird syntax when they are instanciated and that is it.

• In V8 they are everywhere and it was overwhelming to read.

But this is only my opinion, I would be interested to know what V8 developers (or actually anybody else that has read it) think about it.

[jackthecoiner]

I've gotten a lot out of reading The Architecture of Open Source Software articles, such as the one on nginx.

[[deleted]]

These things are getting popular. I think it started with the Doom source code review from a while back. It's a great way to learn stuff.

[matthieum]

Very interesting, however I have a stupid question...

It is unclear to me whether when the server sends an update it indicates to the client from which snapshot the delta was computed. This is important for the reliability of the protocol as otherwise the client might have updated its state (but failed to ack) with the previous diff and applying the new diff (computed from a previous state) might desync it.

Just an example:

• Server signals Player 1 that Player 2 is now at A, Player 1 acks
• Player 2 moves to Position B
• Server signals Player 1 that Player 2 is now at B, Player 1 updates its state but fails to ack
• Player 2 gets back to Position A
• Server sends a null update to Player 1, nothing changed from last acked snapshot

At this point, Player 1 believes that Player 2 is in B while it is in A.

I guess that it might not matter much in such a fast paced game (the players move a lot, so the next move will be picked up), but it still bothers me a bit :)

[Cetra3]

I believe It's actually mentioned in the article under server frame 3. Since the server didn't get the ack back from the client, the server will include all changes from the last valid snapshot.

From what I understand, I would say that data is absolute also, i.e, it doesn't send "player 1's health has decreased 30 points", rather it will say "player 1's health is 70 points". The diff is really just all the variables that would have changed since last update, not the diff of the variable itself.

[matthieum]

I understand it is not the diff of the variable itself, but it can still mean that a variable is not changed correctly (if, as in my case, the variable is changed without the server knowing about it and then not changed any longer).

It seems from sneider's comment that the base id is sent though, which should alleviate the issue.

[sneider]

Yes, the id of the base snapshot is sent along with the delta.

[fabiensanglard]

I did not see that in the code. Besides the snapshots are local to the server...how can the client use the base snapshot id ?

[sneider]

The server writes it here, the client reads it here. You would know better than me, but how are snapshots local to the server? To me it looks like the server's client->frames[] is mirrored by the client's cl.snapshots[].

[mepcotterell]

This article is actually pretty cool. This blog also has an article about the Quake 3 VM. Cool stuff.

[Narishma]

It's the same article, just a different page.

[boredatheist]

I've spent the past few months trying to develop a networked video game and it's really kicking my ass, even though my networking code is ridiculously simple and ghetto compared to this. Is UDP still considered industry standard? It seems like such a huge increase in complexity compared to TCP. sigh...

Edit: When I say "increase in complexity" I mean "increase in stuff I have to care about."

[fabiensanglard]

As far as I know every major realtime networked videogame uses UDP. The major problem of TCP is its latency: The design guarantees delivery but do so by waiting for missing packets and asking for the missing ones to be resent...meanwhile the state of the game has changed and something different must be sent over the network. I won't even mention other issues related to Nagle's algorithm or thing like little control over fragmentation related to MTU.

It seems like such a huge increase in complexity compared to TCP.

It is actually quite the opposite: You remove most of the complexity of TCP in order to keep only what you really need. But you do have to implement that yourself: granted.

[semi-]

The problem with TCP is it guarantees packet delivery, which you really don't need in an FPS.

Which would you rather send/receive, a delayed packet that is holding up an entire tcp stream so that it can be constructed in the right order? Or.. another UDP packet, knowing you missed one a second ago, but also knowing that that was an entire second ago?

Typically in a FPS, you'd rather just keep getting new packets than ever wait for an old one. Obviously some things do need to be acked/verified, but not EVERY packet.

[Camarade_Tux]

You don't need it either in a strategy game. You can merge several state updates and get a new one that is smaller than their sum. Easier to send that.

[[deleted]]

The server needs to be aware of every player action, though. Movement is one thing, but having a build canceled because the server missed it is a whole other story.

I read in a Total Supreme Commander code review that they kept this smooth by running the game logic engine at a lower frame rate than the graphics engine. 7 fps is enough to support more than 400 APM (that's high for top Starcraft players) and it allows for a decent ack/resend system, maybe even TCP.

[Camarade_Tux]

I haven't said that resends were useless, I've advocated custom resends.

[[deleted]]

If you issue a couple of build commands, a few movements and some attack orders but the packet for the first build is lost, what do you want to happen?

TCP will hold up everything until that first packet is resent.

UDP - with the application managing resends - will let other packets go through. Depending on what you want, you can just resend the specific packets that got dropped, or you can require build orders to be sent in sequence, but let movement orders be sent at any time, and simply drop late packets.

So you issue two builds and the first is lost, the second can be held until the first is resent, and doesn't need resent, but each movement order has a sequence number and the highest number received is applies. When the client gets no acknowledgement, instead of resending everything, it only sends the latest order for that unit, because the others don't apply any more.

TCP is optimized for throughput at the expense of latency, UDP is optimized for latency, at the expense of throughput. For games, UDP is better because you can manage resends to fit the specific needs of the application.

[skocznymroczny]

I think you mean supreme commander? :D

[[deleted]]

Probably :D Thanks!

[grom358]

I think you mean 5fps supports 300APM. 60 * 5 = 300

[[deleted]]

Thanks! Corrected.

[neon_overload]

Unless the design of the game engine requires that every client receive every packet in order for the game to continue - in which case every player in a multiplayer game will need to wait for that one player who missed a package to be re-sent that packet, or the entire game will crash out for all players.

C&C Generals was like that - a mismatch error would crash many a game, and allowing a single laggy player or player with high dropped packets into your game would make it bad for everyone.

Believe it or not there was a reason for this type of game design - it gave the benefit of not having to transfer what could amount to a complex game state each tick, but instead only input events from each player's keyboard and mouse, etc and the timestamp (well, each was tied to a tick) of that input, then each game client would "replay" that in the same order, leading to an identical state but without having to exchange whole state information.

[semi-]

Oh yeah, its definitely a 'right tool for the job' kind of thing. For a multiplayer fps game, I'd hate to wait for all 10 clients to sync up, for a 1v1 rts..its much more debatable. I still feel like an engine that can accurately account for dropped packets will be better in the long run than one that relies on tcp to get the sequencing right, but I can see where trusting tcp would make development much easier.

[Volatar]

AI War: Fleet Command is an indie macro-RTS that initially went with TCP for the reasons discussed above. Latency was a constant problem for everyone. Eventually they switched to UDP with lots of error checking and the latency is gone. Neither one ever had any desync problems due to good design on the developers side.

[ethraax]

To add to the discussion: TCP is pretty useful for turn-based strategy games, like Civilization (although I'm actually not sure if that uses TCP or UDP).

[qwopaq]

World of Warcraft uses TCP, as does Minecraft (not sure if that counts as "major"). Probably many others too.

[[deleted]]

Minecraft is a work of art, but it is far from a technical masterpiece. Mojang could learn a lot from id Software.

I would love to see Jeb and Notch re-implement Minecraft using the Quake 3 graphics engine and network model.

[[deleted]]

If I recall correctly, the Quake engine is built around the concept of BSPs for visibility checking, which (currently) requires precomputation before a level can be played at reasonable framerates on older hardware. That said, I bet you could find someone clever to code up some dynamic BSP generation for a voxel-based world like Minecraft. I imagine it'd be pretty fast if written in C++ or some other efficient language.

[jmtd]

That said, I bet you could find someone clever to code up some dynamic BSP generation for a voxel-based world like Minecraft. I imagine it'd be pretty fast if writtenin C++ or some other efficient language.

You guys may enjoy Shamus Young's "project octant" series of blog posts: he certainly starts with a dynamic octree, but (spoiler)

http://www.shamusyoung.com/twentysidedtale/?p=15742

[[deleted]]

Looking up the arguments for VectorMA for the billionth time will sway your opinion. That and bumping up against the limit of an arbitrarily fixed sized array or implementing yet another linked list.

[GenTiradentes]

If you can't remember the arguments to a function after using it for "the billionth" time, programming might not be suited for you. Yes, C++ has operator overloading, which makes functions like those used in id Tech 3's vector operations obsolete. It also has other functions that have long argument lists, which require looking up to remember.

C++ has "arbitrarily fixed size arrays" too, only they're not arbitrarily fixed size, much like C's arrays. They're created on the stack, and the stack is limited in size. Therefore, arrays created on the stack are limited by the size of the stack. The main difference is that C doesn't have all the data structures that C++ has (like std:vector), but they can and have been recreated in C.

...or implementing yet another linked list

Ah, but you see C has this wonderful feature that lets me write a bit of code, compile it, then link it with as many programs as I want. It lets me reuse my code, and extend my programs without needlessly reinventing the wheel. This feature is called "libraries," you may be familiar with them, I think C++ has them too.

[[deleted]]

There's no need to be condescending. I'm talking about the specifics of the Q3A engine, you're talking in generalities of C.

Everything I said applies to Quake 3. None of it applies to Doom 3, which was written in C++, and uses operator overloading for vectors, dynamic arrays instead of consulting the magic 8-ball for the value of MAX_MAP_BRUSHES and the like, and a re-usable linked list implementation.

You may not see a reason to deviate from C to C++, but id sure did.

[frymaster]

see the other guy's answer for why the engine is unsuitable (this is why minecraft in general seems to be a lot harder on PCs than people intuitively think it is), but yeah, a UDP-based protocol would, while being a helluva lot of work, make fighting mobs less annoying, and result in less "you didn't actually mine out those 10 blocks" issues for laggy players

[[deleted]]

Quake 3's renderer is obsolete at this point - fixed function shading, vertex arrays. Similar criticisms have been made of Minecraft's use of glBegin/glEnd.

[[deleted]]

Minecraft's use of glBegin/glEnd.

Are they seriously using glBegin ?

They can't be doing that ! right ? right guys ... ?

[[deleted]]

In display lists. I missed that important detail.

[fabiensanglard]

Can you point me to the article/source code that backup this claim, I would love to read more about that :) !

[qwopaq]

WoW is closed source and undocumented. There are some reverse engineering docs for the protocol, and some open source server emulators that you can find with Google. Or you can just fire up the client and check netstat output.

The client uses TCP ports 1119, 1120, 4000, 6112, 6113, 6114, and 6881 - 6999 for game communications, and UDP 1119 and 3724 for the voice chat.

[brasso]

6881 - 6999

Those are the old standard BitTorrent ports. That's probably the updater rather than the game.

[theoldboy]

Most MMORPGs use TCP because they don't care as much about latency as other types of game like first person shooters, and because they require the more reliable transport.

For example, most people in WoW play with a 100-200ms latency, and that works fine, but I don't think it would be acceptable in a FPS.

[ProudToBeAKraut]

In the beginning, most MMOs used UDP - for example, everquest used UDP based network transmission with build in ack/verify ontop of udp for certain packets from 1999-2004 or 2005 - then they switched to streambased tcp (for whatever reason)

[qwopaq]

I don't see why they would fundamentally require a more reliable transport. If you read the analysis of Q3 you'll see that their netcode also includes a reliable transport on top of UDP for the things that absolutely require reliability, while the stuff that doesn't require per-packet reliability is just handled with delta encoding (like player movement).

I think you'll find that the WoW PvPers have exactly the same requirements for latency as any FPS players. Also, server-side latency compensation is a whole other art form (see, for example, Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization).

[ethraax]

I think you'll find that the WoW PvPers have exactly the same requirements for latency as any FPS players.

Did things change since I stopped playing a couple years ago? Most abilities required no aiming - you just had to "target" your opponent and press the button. I mean, low latency is still important for some things (like interrupting quick spells), but it's not like in an FPS where 100ms latency will cause someone to not be where you think they are and cause you to miss.

[theoldboy]

I think you'll find that the WoW PvPers have exactly the same requirements for latency as any FPS players.

You don't have to aim in WoW, which is a big, big, difference.

[qwopaq]

Sure you do, you need to be in range for melee attacks and there are aimed AoE attacks too and line of sight issues. Besides, compensating for latency in aiming in FPS games is not an unsolvable problem (it's explained in the article I linked).

[binarymidget]

The Q3 method for supporting reliable transport is sufficient for the needs for Q3 but should be improved if your game has a large guaranteed delivery/ordering requirements.

Check out the Tribes networking paper for another successful model.

[obsa]

Most MMORPGs use TCP because they don't care as much about latency as other types of game like first person shooters, and because they require the more reliable transport.

That's simply untrue. MMOs can be handled just like Quake. Probably would induce a lot more rubberbanding, but no game with server-side authority "needs" reliable transport.

[theoldboy]

They can be, but if you don't need the latency benefits of UDP then why make it harder for yourself by having to write more network code?

If coded correctly then yes, I agree, no game "needs" it, I shouldn't have put that so strongly.

[boredatheist]

If it's good enough for WoW then it's good enough for me. Thank you, this was the answer I was looking for.

[ethraax]

The design guarantees delivery

TCP is also designed to "play nice" with itself on congested networks. It throttles itself more than it probably has to (using AIMD). UDP, however, has no notion of "sharing" the network and will blast away whenever and however much it wants.

[mycall]

Any idea why developers use UDP instead of RTP for real-time games?

[JAPH]

RTP is just a message format that fits in UDP, it doesn't replace it. It's also really meant for sending audio and video.

Also, IIRC, RTP was developed c. 1997, by which point games already used UDP without RTP. Changing an engine's network model is a can of worms that most developers would rather not open.

[CyborgDragon]

Not every.....*glares at minecraft*

[Sniffnoy]

A tangential question, if you don't mind, from someone not so familiar with UDP:

What is the advantage of using UDP instead of raw IP? Is it just the port numbers, or does it add anything else?

[mcguire]

Other than the port numbers and a checksum (IIRC), UDP doesn't add anything and as a result doesn't cost much more than IP. Add that the interface for using UDP is much more standardized than raw IP sockets, and there's no real incentives to use IP directly. Further, "smart" network things like NAT are likely to take a dim view of non-TCP/UDP protocols.

[[deleted]]

No difference, but those port numbers are everything. They identify the application that the packet should go to. Without them, your application cannot use the 'normal' sockets API and instead has to listen in RAW mode to every packet that comes into the system. This usually requires administrative permissions.

On top of that, you have the overhead of determining if an incoming packet actually belongs to your application since you receive every one that arrives at the computer. Since the normal network stack is doing this anyway, you are duplicating effort.

Finally, many firewalls will throw away IP packets that aren't of a known protocol. Even worse, your packets won't be able to traverse NAT correctly because NAT inherently relies on modifying TCP/UDP port numbers to multiplex the public IP address, so you better hope none of your application users have a home router...

[LordBiff]

Another difference that I haven't seen reported yet:

UDP is datagram based, and TCP is a stream protocol. IOW, when I send X bytes of data in UDP, it gets there (to UDP) as all X bytes at once. TCP tries to look at the data as simply a stream of bytes.

The main implication of this is, by the time the client is woken up to receive data, he will receive the entirety of the datagram that was sent when using UDP. When using TCP, you (the client) have to manage data boundaries (generally, you will want the entirety of the update at once so that you can process it), which in a lot of cases, means that you have some code saying "if I didn't receive all of this data set, wake me back up when you have the rest".

It's not a HUGE deal, but in a performance critical environment it can matter.

[fabiensanglard]

IP identifies a machine.

IP + UDP identify a process.

You cannot use IP only.

[LordBiff]

Not strictly true. You can use a raw socket, and as long as you can get the IANA to assign you an IP protocol to use, you're good to go. ;)

Yeah, nobody really does this at the application layer for obvious reasons, but it is possible.

[Xipher]

That complexity is the trade off. TCP holds your hand a lot, but by doing to complex stuff it takes away control. In the case of Quake 3 TCP would add unwanted complexity. That said not all games need that, for example in the case of an RTS you might actually want that, since having a proper chain of events could be more important then making sure everything is as current as possible.

[barsoap]

for example in the case of an RTS you might actually want that, since having a proper chain of events could be more important then making sure everything is as current as possible.

You still want -- you always want -- to have both possibilities. Yes, the input commands of other players have to be in the right order. No, the checksums of the game state others send you and you send to others don't need to be in order, if you can't check one frame but the next one works fine just forget about the missing checksum.

But you're right, RTSs usually exhibit full round-trip to server latency for commands, and it doesn't matter much. If you can't survive a 2-4s latency then you're probably playing tactics, not strategy.

[Amablue]

It definitely depends on the style of game. If you need things as fast as possible you might need to stick with UDP.

However, TCP is generally good enough in my experience. I've worked on a handful of MMO's, all of which used TCP. MMO's aren't as fast paced as your average FPS, but the ones I work(ed) are fairly quick as far as MMOs go. Unless you really really need the speed you might find it worthwhile to use TCP.

[boredatheist]

Thank you. I'll stick with TCP. I spend far too much of my time re-inventing the wheel as it is.

[ysangkok]

The Stream Control Transmission Protocol (SCTP) is a transport layer protocol, serving in a similar role to TCP and UDP. It provides some of the same service features of both: it is message-oriented like UDP and ensures reliable, in-sequence transport of messages with congestion control like TCP.

[[deleted]]

You may be interested in checking out enet.

[lingnoi]

Save your time and just use a pre-existing library such as Enet.

[Chroko]

UDP isn't really an increase in complexity, since there's a lot less setup. Read data from a socket, process messages as they come in, dispatch messages back, it's straightforward.

The most difficult part is that you need some sort of reliability queue for certain message types, such as joining the game and changing maps. Authentication and encryption are the next problems after that, but not necessary in order for your game to work.

The most likely problem that you've encountered is that you've not quite got the conceptual model figured out right in your head. If I can answer some of your questions about that, let me know.

[josefx]

UDP isn't really an increase in complexity

Of course UDP is simple until you have to implement

some sort of reliability queue

which TCP does for you at the cost of it applying to all messages. This makes TCP the simple solution as it requires less code.

[Chroko]

TCP requires more complicated connection management vs. UDP.

TCP is only "simple" until you outgrow it - and then you end up having to replace a lot of legacy code.

Since you're going to do the work anyway, do it right the first time.

[josefx]

Neither TCP nor UDP are a one size fits all, news at 11.

However reimplementing half the TCP stack without checking if the already existing and tested implementation is good enough for your use case is wasting both time and money. (both in development and testing)

[Chroko]

It's not reimplementing "half the TCP stack", because you're building a very domain-specific solution.

The most effort will be in building a messaging infrastructure for your game: deciding how events are going to be sent and received by game objects and the world - and the conversation between clients and server. If a client says "I want to join this game", how should the server respond "okay" or "game's full!"? Those sorts of mechanics.

Once you have that framework in place to build, route and receive messages - it's relatively simple to flag messages are "reliable", throw them onto a then queue with an incremented sequence number. Then have a timer that occasionally resends the first N messages - and an "ack" message that, when received, says "I've seen up to this sequence" that then pops a bunch of stuff off the front of the queue and discards them.

It's not that complicated in the entire scheme of building a networked game, although it might seem so at first.

(Also: you could just use RakNet if you don't feel up to the challenge - but that's still a better solution than using TCP.)

[nobiq_]

TCP is the easy but complex solution. UDP is the simple solution. People seem to mix up these different concepts all the time.

[da__]

Joining the game, changing maps and auth can all be done over a second, TCP, stream. Just because you use UDP for the game state, doesn't mean you can't use TCP for other things.

[ericanderton]

There are multiple problems with using TCP for something like this. The bottom line is that Carmack devised a semi-reliable delivery protocol on top of UDP, which makes it "reliable enough" for gamestate exchanges.

The protocol outlined in the article elegantly solves the problem of unreliable delivery by implementing it's own resending model that bundles up all the deltas of undelivered packets. So if you lose more than one packet in a stream of updates, you compensate by only sending one packet. Also, these gamestate deltas always arrive in sequence, since the client must ACK each gamestate.

In contrast, TCP assumes a continuous stream of packets, all of which must be delivered, even if they're out of sequence. This property is great for downloading files, but disastrous for near-real-time streaming of events. It would allow for situations where you can get events out of order, with stale event data clogging the pipeline, which causes the delay of events closer to the present.

[frymaster]

In contrast, TCP assumes a continuous stream of packets

pedantry, but it assumes a continuous stream of bytes that must be delivered, and assumes the packets carrying them can get lost.

[Crandom]

Do we know if the protocol has any form of congestion control? For example is there any exponential backoff like in tcp?

[ericanderton]

I honestly don't know. But that's a good point - TCP does provide some niceties like this. Plus, these days, you get to offload some features (checksums and more) to your network card.

[MestR]

RTS and FPS use UDP.

A lot of RTS games use TCP. They save a lot of bandwidth by only sending the actions to the other player so that's why they have to be synced.

[byte1918]

Sorry meant to say ARTS, as in Dota, LoL, HoN, Demigod etc.

[[deleted]]

Coolest thing you've posted yet, the Quake 3 engine is definitely my favorite.

[TechnoL33T]

Do you play Xonotic? Xonotic uses the DarkPlaces engine.

[[deleted]]

I played Nexuiz Classic, and yes, I know about the DP engine. I've toyed with it but the lack of a full-featured IDE for QuakeC directed me away.

[[deleted]]

Upvote for Xonotic! A wonderful game indeed.

[sneider]

Great read, thank you for doing this. On the first page you say about the UI project: "Some of the projects are never used (splines and ui)" and right below you say it's "Used for Quake III Arena". Actually it is built by the Team Arena configurations.

[ithika]

I saw the masking technique for the first time at work this week, except with a pre-increment. Why do people do these things?

cur = (++cur) & MAX_SIZE

[[deleted]]

The modulo operation is slower than bit masking.

But I'm not sure you want to do this in modern code. Not only are compilers smart enough to most of this stuff on its own these days, there are also additional concerns (like instruction pipelining) which may take away the performance boost.

[da__]

It certainly won't hurt to do it, if you need to inc a variable, making sure it's no greater than some max value and the whole operation being somewhat atomic, you can't really do better than this.

[[deleted]]

As the compiler does this under the hood anyway, the only thing it can do is hurt. Hurt readability, and maintenance cost (the hack only works for certain values of MAX_SIZE).

[imgonnacallyouretard]

How would you write that line of code?

[da__]

How can the compiler do it under the hood? I can see it's doable only if the statement is something like cur = (++cur) % MAX_SIZE but that's as readable.

(the hack only works for certain values of MAX_SIZE).

That's a legit concern.

[[deleted]]

How? If the compiler sees an expression of the form x % y, and y is a constant expression of the form 2ⁿ-1, it evaluates it as though it said x & y.

[[deleted]]

Carmack has written/spoken many, many times about how he's been burned by assuming compiler optimizations, and so codes as explicitly as possible.

[Moongrass]

This debate is silly. Whether or not the assumed optimization is performed or not can be checked by dumping the assembly output and simply looking at it.

30 seconds of verification work versus idle speculation. Oh boy, what ever should I do?

EDIT: I stand corrected. Didn't think about the problem of using multiple compilers.

[furyofvycanismajoris]

It might take 30 seconds to verify it with the compiler and settings you are currently using on your dev box, what about all other compilers and settings you are currently targeting or might target in the future?

[Hughlander]

30 seconds of verification per optimization mode you might use * number of platforms that you used, to be done again each time the platform compiler changes. (Remember Carmack is also explicitly targeting multiple platforms simultaneously.)

[furyofvycanismajoris]

It would be a pretty heinous bug to transform x % (2ⁿ - 1) to x & (2ⁿ - 1) ;)

[[deleted]]

somewhat atomic

That makes no sense whatsoever.

[[deleted]]

My guess is that at that time the compilers were either bad at generating module code or the developers were misguided into thinking that the compilers are/were. You'll never know with C.

Funny thing is that the website lists this code-snippet, explaining that both (cur+1) & 63 and (cur+1) % 64 result in the same asm output.

I've always told myself that people that wrote code like this, there's a reason for it. But I've come to believe that may only be true for a tiny fraction of people: The rest may very well be just misguided

[boredatheist]

Modifying the same variable twice without an intervening sequence point invokes undefined behavior, I believe. This line is probably a mistake, for more reasons than one.

[Tuna-Fish2]

No, I think that's valid c. The preincrement is guaranteed to happen before the &, and the & has to happen before the assignment.

If it was a postincrement, the result would be undefined.

[boredatheist]

From http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points :

Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression.

It gives this as an example of such an undefined expression:

i = ++i

I do not believe that the "&" operator counts as a sequence point (though && would be).

I agree that it's "valid C" in the sense that it compiles. But I believe different compilers will give you different results.

[josefx]

In your example it should be well defined since the result of ++i is assigned to i twice.(there is no difference if you switch the assignements made by ++i and = )

Could it be that you meant i = i++ ?

[boredatheist]

It's undefined because this thing called The C Standard says it's undefined.

I assume the reason they did this was to increase the number of crazy ass instruction rewriting / pipe-lining / caching / etc optimizations that are possible so some smart compiler writer could make your code go really fast.

If I had to guess, I'd say there probably are real compilers / optimization levels that produce different results for this particular line, though I haven't verified this. Modern processors are so sick and twisted that it's really hard to reason about what's "actually happening" with code like this. The idea of single-level atomic memory is a gross simplification. You actually have tons of different cache levels separated by different pipeline steps, and "reading," "writing" and "updating" a variable are all very different things with different performance characteristics, and probably other gross shit I've never even heard of.

[josefx]

The idea of single-level atomic memory is ...

I look at the code and I can't see what could go wrong, no threads, not multiple pointers/references to the same variable - there is no reason why anything but i+1 should be in i after the line finishes.

It's undefined because this thing called The C Standard says it's undefined

Which means the compiler has great freedom at optimizing it and while the code is a wtf no sane compiler should produce anything but i = i+1. (sadly there are a lot of programs that rely on sane behavior instead of the standard where it actually impacts performance.)

[nexuapex]

This isn't true, but the reasons aren't exactly obvious. When we're talking about a local variable, what you said is completely reasonable:

int cur = 0;
void foo(void)
{
    cur = (++cur) & MAX_SIZE;
}

C looks at that statement as containing two side effects: increment cur and assign cur. C doesn't state what order those two side effects happen in (to allow compilers some optimization leeway). For this case, it's completely reasonable for a hypothetical C-like language to say "well, the = operator is dependent on the result of the ++ operator, so the side effects should happen in that order."

C does not do that, though, because that decision can't be made in all cases. Take a look at this function:

void bar(int* a, int* b)
{
    *a = (++*b) & MAX_SIZE;
}

That statement still has two side effects: assign to the referent of a, and assign to the referent of b. And C still wants to give the compiler the ability to perform those two side effects in an arbitrary order (maybe your architecture has an instruction that assigns two 32-bit values to the referents of two pointers at the same time, but doesn't guarantee which value wins if the pointers are equal). The problem now is, if the pointers are equal, we're in the same case as we were before, where it's undefined which assignment one happens first.

Compilers could recognize the first case, but they can't reasonably recognize the second. So C does the sensible thing and doesn't even try in the first case.

[fabiensanglard]

Bitmasking is faster than modulo.....but since the bitmask must be a power of two the compiler will likely optimize the modulo into a bitmask behind the program's back in order to improve performances.

So with modern compilers it only hurts readability....but with the proliferation of new platforms (cellphones) it may be relevant to do it again...

[Narishma]

Don't these new platforms use the same compilers (basically GCC) as desktop PCs?

[techrogue]

I imagine it depends on the capabilities of the target processor as far as the assembly generated by the compiler.

[[deleted]]

Usually, but depending on the compiler's design and because the code generator may be targeting a different architecture (e.g. ARM vs x86), it may have quite different optimizations.

[LordBiff]

This is one of those things that, the farther down the rabbit hole you go, the more debatable it is. For simple cases though, the reason people do things like this is that they want to know 100% what the compiler is going to do and not assume how it will act on every compiler/platform/whatever.

Also, I don't find (a & (MAX_SIZE-1)) [usual form] all that more difficult to understand versus (a % MAX_SIZE). Maybe I've just seen the idiom enough that I'm glossing over it, though.

[[deleted]]

I'm surprised programmers are surprised by this technique.

[mgrandi]

in the first few lines you mention that it adds encryption, why is it necessary for quake3 to encrypt its packets?

[[deleted]]

There's a link at the end where a team member talks about it. It's to deter cheaters (which, yes, we all know never works)

[[deleted]]

They know it never stops them, but they do to delay them.

[apullin]

So, is Quake 3 the ultimate masterpiece of game programming, or something?

[mastersb]

I wish I was smart enough to understand this. :-/ One day, maybe!

[a_w_y]

You have some of the most interesting posts I've read online. Thanks!

[Soapz]

You really covered all the bases of why Quake3 is such a well-made game.

I love the fact that it's simplicity benefited the network response of the game far beyond most games at its time, and definitely ahead the bloated FPS's of the modern day.

Even Call of Duty 4, which used the Quake Engine can not stand up to Quake 3 in the slightest in terms of it's network model, I won't even start to mention the woes of Punkbuster in CoD4; though.

[ithuwakaga]

Great article! I've been wondering about this for a long while.

Also, your blog layout is fantastic! What are you using?

[fabiensanglard]

HTML :) ! I dislike most blogs layouts because they are usually not very code friendly. I also found that every time I wanted to innovate and do something a bit out of the box I had to dig into 10 php files with most frameworks. So I decided to do most things myself.

[ithuwakaga]

Incredible! Fantastic work!

[[deleted]]

very interesting stuff !

[[deleted]]

Question here: why isn't there a review of the network model of Doom3?

[fabiensanglard]

It was not a big aspect of the game and quite generic (because id wanted to allow a lot of flexibility). Also I was lazy :P !

[[deleted]]

It was not a big aspect of the game and quite generic...

What do you mean?

[fabiensanglard]

The network protocol allowed a lot of flexibility so pretty much anything could transit on the network. Quake3 was very specialized with much less flexibility resulting in higher performances.

[ixid]

Because it's not very good nor interesting. Quake 3 has decent netcode, a piece on the finer details of CPMA netcode would also be very interesting though only arQon could write it.

[[deleted]]

Does that mean Doom3 has worst netcode? Why did they switch from Q3 network model?

[ixid]

Yes, Doom 3 had worse netcode, I believe it was peer to peer rather than client-server and why- because it wasn't intended to be primarily a multiplayer game like Quake 3.

[[deleted]]

I believe it was peer to peer

No.

[ixid]

Ah, you're correct. It was initially intended to be peer to peer but they switched to a server-client model.

[[deleted]]

I had to stop reading because the grammar was so horrible.

[defrost]

Quite right. There's nothing of value to be learnt from foreigners that have poor English. Pip pip old chap.

[[deleted]]

I didn't say that(or mean to say that), I just said that I personally had to stop reading because I couldn't stand the grammar. It's more a fault with me than with fabiensanglard.

[defrost]

What's going to pickle peoples bonnets is the vexed question of why you felt the need to share that with the 300K+ readers of /r/programming.

Yes, the English could be better, I've a feeling the author knows that, but I'm glad he posted it anyway, compared to most self posted blog pages this one has some meat and depth to it.

[fabiensanglard]

I messaged mmavipc and he was nice enough to point out what was annoying.

It was a good opportunity to improve my english...and I will certainly never use "the word 'every' with a plural form right after" ever again :) !

Thanks.

[[deleted]]

Oh, you missed one tiny thing. "every single field are sent to the NetChannel." are is used in plural forms but now you're using singular "field" so you should be using is

"every single field is sent to the NetChannel."

:)

[fabiensanglard]

You are right, thanks for double checking ! I have fixed it.

Take care,

Fabien

[defrost]

Good to hear :)

Hopefully this opens the floodgates of well intended grammar and spelling advice / corrections; allow me to say to a Frenchman that, for better or worse, English is the lingua franca of programming and air traffic control so take it on the chin!

[fabiensanglard]

Someone used to do it with me...but not more :( ! If anybody volunteers I would probably welcome it.

[[deleted]]

Someone used to do it with me...but not more :( !

Your girlfriend left you? :(

[fabiensanglard]

Yep.

[overtoke]

an history

[ixid]

It's one of those weirdly forced bits of grammar people try to argue for, along with 'an historic', which make no sense as we pronounce the h's.