The amazing design of PCI Express

The IBM PC computer architecture (like many other similar architectures) was designed with expandability in mind, meaning that the base computer (motherboard + CPU) can be expanded with external third-party modules, in the form of expansion cards that can be attached (usually directly to the motherboard). During the long history of the architecture there have been numerous and diverse expansion bus protocol standards, including ISA, AGP, PCI and, what has now become the ubiquitous (and often sole) standard, PCI Express (which shouldn't be confused with the older PCI standard. While similar, the connection slots are physically incompatible.)

The current standard, PCI Express, could arguably be called the "ultimate" expansion bus standard in its perfection. Indeed, PCI Express is an absolute marvel of computer engineering.

One of the most notable and important features of PCI Express is its incredible compatibility with different versions of itself. I like to describe PCI Express as being "compatible forwards, backwards and sideways".

What do I mean by this?

As of writing this there are now 6 different generations ("versions", if you will) of the PCI Express standard, although the vast majority of current motherboards only implement generation 4. The main difference between the different generations is data transfer speed.

However, all these versions are fully compatible with each other. You can take a generation 1 PCI Express expansion card and connect it to a motherboard supporting generation 4, and it will work (ie. the standard is backwards compatible). More prominently, however, you can take a Generation 4 PCI Express expansion card and connect it to a motherboard that has only support for the generation 1 standard, and it will work (which could be called "forwards compatibility", in other words, older generations of the standard are forwards-compatible with newer generations).

The same goes, of course, with any other combination of the six possible generations.

Moreover, and rather amazingly, the standard is also "sideways-compatible" with itself, as I like to call it. What do I mean by this?

PCI Express slots come in different widths, which directly correspond to data transfer speed. Most typical widths are x1, x2, x4, x8 and x16 (although x2 and x8 tend to be rare in motherboards). These multipliers do not indicate merely data transfer speeds, but in fact indicate directly how many physical connectors there are in the expansion slots. (In other words, the multiplier is not, for example, some kind of clock speed multiplier, but directly indicates how many physical connectors and wires there are in the expansion slot.)

Remarkably, you can take any PCI Express expansion card, of any width, and connect it to any PCI Express slot, no matter what its width may be (as long as the physical design of the slot allows it).

In other words, it's perfectly possible to take an x1 card and connect it to a full-length x16 slot, and it will work. Likewise it's possible (at least in theory) to take an x16 card and connect it to an x1 slot, and it will work correctly. (And, of course, any other combination of lengths will work.)

This is the reason why it's perfectly possible to take an x16 GPU and connect it to an x4 slot, and it will work. (The only drawback of doing this is the reduced data transfer rate between the CPU and the GPU.)

(In practice x1 slots in motherboards have a physical barrier at the end that stops a longer card from being inserted. There's no technical reason to stop this from being possible, at least from the point of view of the PCI Express standard. In fact, if you were to physically cut out that barrier, you could insert an x16 card into the x1 slot, and it will work. The main reason why manufacturers put the barrier there is to stop very large cards from being inserted, which would cause a lot of sag due to gravity, very possibly physically bending and damaging the slot, the motherboard, and possibly the card itself.)

This is what I call "sideways compatibility".

Misconceptions about card shuffling

Lots of card games rely on shuffling the deck of cards for proper randomization. Most games that use the standard 52-card deck (most famously games like poker and bridge) as well as most, if not all, collectible card games, as well as a myriad of other games that use cards (which may be completely custom to that particular game) rely on proper deck randomization.

In some games good deck randomization is not crucial, and a fair, balanced and reasonable game can still be had even with poor randomization. In other games, however, proper deck randomization is often considered absolutely crucial, even mandated by the rules of the game, and poor deck randomization could even be seen (or intentionally abused) as a form of cheating.

Putting deliberate cheating aside, the fact that so many card games require deck randomization, so much so that it's almost ubiquitous in card games, has quite naturally given rise to a lot of misconception about what "proper randomization" is, and about shuffling.

These misconceptions usually lead to two rather particular extremes when it comes to deck shuffling: The under-shufflers (people who shuffle way too little) and the over-shufflers (people who shuffle needlessly much). There are also tons of misconceptions about shuffling techniques in particular, and what is considered "proper randomization" and what isn't.

Under-shuffling

The phenomenon of under-shuffling, ie. shuffling way too little for proper randomization, is surprisingly common, and happens in all kinds of card games. Perhaps the most common and most extreme case is the people who mash-shuffle two times, and think that's enough.

Mash-shuffling is dividing the deck in two parts (of significant proportions) and then inserting one part into the other by the side, interleaving the cards in the two parts. (Randomization happens mainly because the interleaving is very rarely completely even, and the number of cards that get between the other cards is relatively random.) It's very similar to a riffle-shuffle (and usually achieves pretty much the exact same amount of randomization), except for the physical mechanism by which the cards are interleaved (riffle-shuffling is often preferred over mash shuffling because the latter wears out the edges of the cards more quickly. Note, however, that riffle-shuffling is not really possible with sleeved cards.)

It can be mathematically argued that for a deck of 52 cards (standard deck) or 60 cards (minimum MtG deck size) 7 mash shuffles are enough for full deck randomization. For a 100 card deck (MtG Commander) 8 mash shuffles are enough. It might not be immediately obvious why, but the mathematics are solid on this. (If you want to be extra sure, you can add a couple more mashes; it won't hurt.)

But what this means, and it should be quite intuitive and clear why, is that 2 mash shuffles is not even nearly enough for proper randomization.

Yet, you see this all the time. In fact, exactly 2 mash shuffles seems to be strangely common. Some people might do three or four (and a few might even do just one, although quite rarely), but among the under-shufflers exactly 2 seems to be the most common.

Sometimes this is caused by a complete misunderstanding of what "shuffling" and "randomization" mean. Many people, especially the under-shuffling kind, have this misconception that "randomization" merely means "I don't know exactly where the original cards ended up in the final deck". In other words, if they can't say with accuracy, for example, "the original top card of the deck ended 8th from the top in the resulting deck", then the deck is "randomized". In other words, as long as you don't know exactly where each card is, it's "randomized".

Of course this isn't what randomization means. While the term is actually surprisingly difficult to define clearly and unambiguously, a simple definition would be that any card in the deck has a random and equal chance of ending up anywhere in the final deck, and that the relative order of any two cards in the original deck have about a 50-50 chance of being reversed in the final deck at random. Optimally, any of the possible permutations of the cards in the deck should have an equal and random chance of appearing.

It should be quite clear why two mash shuffles are not even nearly enough to achieve this. (It's much less clear why 7 mash shuffles are enough for this in a 52 or 60 card deck, but that's another topic.)

Complete information loss on where the cards have ended in the final deck is of course a crucial part of randomization, but it's not the only part that's required for proper randomization.

Over-shuffling

In the other extreme we have the over-shufflers: The people who will go to completely needless lengths to randomize their decks, well beyond what would be necessary, to the point of it being just a waste of everybody's time.

A common phenomenon among these people, however, is not merely that they shuffle excessively, such as doing 20 mash shuffles when 7 would be enough. It's very common for them to not only use several shuffling techniques, but also have a lot of misconceptions and misinformation about these shuffling techniques. They also tend to be extraordinarily dogmatic about these beliefs, defending them to the death.

Perhaps the most common and infamous misconceptions, and the source of most flamewars and extreme dogmatism, especially among collectible card game players, relate to pile-shuffling.

Pile-shuffling is distributing the cards in the deck into a number of piles and then just collecting them into a new deck. In other words, you take the deck and start putting cards from the top onto eg. seven piles, one after another on sequence, until all the cards are on the piles. Then you just put all the piles one on top of another.

I think that any rational person should understand why this does not randomize the deck in any way. That's because there's zero randomness in this process, and it's 100% deterministic. Every card in the original deck will end up at an exact predetermined location in the final deck. Even if you collect the final piles in a "random" order, that only means that each card of the original deck will end up in one of a very limited number of positions in the final deck. In fact, if you pay attention to the order in which you pick the piles, you can tell exactly where a particular card is going.

Most particularly, quite often pile-shuffling means that the original top card of the deck will end up at the bottom of the final deck (if you think about how pile-shuffling progresses you'll see why). Or, at the very least, at one of the few predetermined places in the final deck, depending on the order in which you pick the piles.

Some people argue that pile-shuffling becomes random if you always pick a random pile to put the next card onto. For starters, people are very poor at randomization when they do it consciously, and secondly, this is still extremely poor randomization (eg. because of the reason stated above, ie. the top card of the original deck will still end up at one of the very few predetermined positions in the final deck).

When you bring up this issue, they will respond that "you don't just do pile-shuffling alone, afterwards you mash-shuffle enough to make the deck random". They seem completely unable to see that they just admitted that pile-shuffling does not randomize the deck, as it needs some actual randomization afterwards.

Yet, try to convince an over-shuffler that pile-shuffling is completely useless for deck randomization and just a waste of everybody's time. Good luck. You are not going to succeed. This is, for some reason, one of the things that over-shufflers are most dogmatic about, and will take this opinion to their graves.

The main reason why they pile-shuffle is that they have this strong instinct that mash-shuffling does not "separate the cards enough", and thus they need to be separated from each other with pile-shuffling. If some particular types of card are clumped together in the original deck, they need to be "separated out" via pile-shuffling or else they'll end up clumped together in the final deck too, if only mash shuffling was used.

You cannot convince them otherwise. They will never, ever, in a million years, believe that 7 mash shuffles are enough to fully randomize the deck, and "separate the cards" from each other enough. They might believe it from, like, 50 mash shuffles, but not from 7. You can try convincing them, but you will fail.

Of course this still doesn't explain why do many collectible card game players pile-shuffle several times.

The major problem in trying to debunk the "plane on a conveyor belt" dilemma

The "plane on a conveyor belt" dilemma (or various variants of such a name) is the question of whether a plane can take off from a conveyor belt that's running backwards matching the speed of the plane.

Quite famously the TV show Mythbusters tried to demonstrate that of course it can, there's no doubt about it. Later also Adam Savage made a YouTube video further explaining the myth and why the idea that the plane couldn't take off just doesn't work.

One of the major problems with the proposition, and the attempt at debunking it, however, is that the problem is quite often presented in an ambiguous manner, using ambiguous wording.

The ambiguous wording is that the conveyor belt "matches the speed" of the airplane. The problem with this is that the idea is very easily misunderstood.

And that's exactly what happened with the Mythbusters episode. They interpreted it to mean that if the plane, for example, sets its throttle so that the plane ought to go at, let's say 50 mph, then the conveyor belt should go backwards at 50 mph.

But that's not the idea in the dilemma. The conveyor belt is not supposed to look at what the throttle of the plane is set at, and use the same speed.

When people say that the conveyor belt should "match the speed" of the airplane, what they really mean is that the conveyor belt should always move as fast as to counteract any movement by the airplane. In other words, if the plane starts moving forward, the conveyor belt should quickly accelerate up until the plane stops. It doesn't matter if the conveyor belt needs to go at 10 thousand mph to stop the plane, that's the very idea.

In other words, the idea in the dilemma, which is usually very poorly expressed, is that if the conveyor belt always accelerates as much as necessary to keep the plane in immobile, can it take off? It doesn't matter if the conveyor belt moves at 100 mph, or a million mph, it always accelerates to a speed that keeps the plane immobile. In other words, it always "matches the speed" of the plane in the sense that it will always go as fast as necessary to keep it still.

Ostensibly this should theoretically make the airplane incapable of taking off because wheels cannot have zero friction, and the conveyor belt will always be able to take advantage of this friction to stop the plane from moving. (In practice the friction could generate so much heat that the wheels would melt and burst, but this is a hypothetical scenario anyway.)

So no, I don't think Mythbusters proved the myth as false. They merely misinterpreted and misunderstood what the myth is about (this no doubt helped by the fact that very few people can actually clearly and unambiguously express the scenario properly.)

What mathematics do you need to know for computer programming?

Computer programming has, over the last couple of decades, quite quickly become easily available and feasible for all computer users. Many a beginner programmer becomes fascinated at the prospect of creating programs of their own, especially games.

However, quite soon they encounter several hurdles along the way. Computer programming is not necessarily as simple and easy as it might sound. The fancier results you want, the more you need to know. Not only do you need to know the programming language you want to use and the various libraries available to do the necessary tasks to achieve the desired goal, but programming requires higher-level "meta-knowledge" about computing science, such as practical knowledge about algorithms data containers and... math.

Indeed, math is quite ubiquitous in most computer programming, and especially in game programming. Modern tools and game engines might make this easier and remove the burden of coming up with the math necessary for the most common actions that happen in a video game, but sooner or later the requirement of some math knowledge will be encountered.

Many a beginner programmer has found out the hard way that their dismissal of math in elementary and high school as "boring", "unnecessary" and "I will never need any of this in real life" comes to bite them in the posterior once they try their hands at computer programming. Quite soon they find themselves searching the internet for the basic math knowledge that they did not pay attention to in school.

But the question arises: What kind of math is needed and useful in programming, especially game programming? If one had to concentrate on the most useful parts of math, what would it be, and what could be skipped?

I have thought of this question quite many times, and I have come up with a list:

Rather obviously, basic arithmetic is absolutely ubiquitous in everything, including programming. However, this should not stop just at the primary school level arithmetic, as doing arithmetic in bases other than base-10 becomes surprisingly important knowledge in programming. Most importantly having a good grasp of base-2 (ie. binary) and base-16 arithmetic, and the conversions between all three bases, is of crucial importance.

Linear algebra is quintessential to game programming (and almost any programming that involves any sort of graphics). Having a good grasp of linear algebra is extremely useful. In fact, having a good grasp of elementary algebra in general helps a lot.

Very closely related is analytic geometry, which use in video game programming ought to be quite self-evident.

Likewise trigonometry will quite often turn out very useful. All of these share in common that they deal with calculations done in two and three-dimensional Cartesian space, which is what computer games (and almost any program dealing with graphics) deal with.

An example of a field of math that, in my experience, is very rarely if ever needed in practical programming is calculus. You can probably skip all of calculus completely and it's unlikely you'll find that as a hindrance in the vast majority of programming. (There may be some very specialized programs for very specialized tasks that may require calculus, but they tend to be very rare and far-removed from most common programming needs.) Of course it's good to know at least something about calculus for general knowledge, to have at least a grasp of what it's about and the generic principles, but in my experience being good at calculus is completely unnecessary in the vast, vast majority of programming tasks.

(Perhaps the closest thing you may ever need calculus for in graphical programming is if the need arises to find out a formula for the slope of a function, which may be needed for things like raytracing, but even then this tends to be very niche. At a very minimum one should know that a slope function can be calculated using calculus, even if one doesn't know the exact method for deriving it. This knowledge will at least guide you to the right direction, if the need ever arises.)

The best thing about adaptive sync (G-Sync, FreeSync)

Since the dawn of time (of computer hardware) it has always been the display monitor that is 100% in charge of how many times per second a computer program, such as a video game, can update the screen. For example, a 60-hertz display forces the computer to update 60 times per second, period, and if it misses that timeframe then tough luck, the next opportunity is the next screen refresh, which effectively means the game updates at 30 Hz. There is no in-between.

Unless, of course, the computer simply ignores the display's refresh rate by turning off its own vertical sync, and just updates the image at whatever speed it likes. This frees up the game's framerate but has the rather annoying consequence of so-called screen tearing: The picture changes in the middle of the monitor updating the display, and thus you get the upper section of the display still showing the previous frame while the lower section is showing the next frame. If the image is eg. scrolling horizontally, there will be a clear cutline, where the two pictures are offset. Since the computer rarely can hold an exactly perfect timing on this, this horizontal cutting line, this tear, tends to jump randomly, and can be quite annoying.

Some time in the beginning of the 2010's Nvidia introduced a technological solution, which they called G-Sync, that effectively reverses this relationship: Instead of the display monitor deciding the refresh rate and the computer adapting to it, we do it the other way around: Now it's the computer that decides the refresh rate and the monitor adapts to it, refreshing the display as soon as a new picture is sent to it (within certain maximum and minimum limits). AMD soon followed this by introducing their open FreeSync standard.

This offers the best of both worlds: The computer is not limited to a highly limited set of refresh rates (such as 60 Hz and fractions of it), and thus the refresh rate can vary freely (within limits), and there is no screen tearing. If the game renders at 53 Hz at one point and then at 47 Hz, and then at 71 Hz, it doesn't matter, the monitor will display every frame as soon as it becomes available.

Nvidia has always marketed this feature to professional and hard-core gamers, essentially arguing that they can get the maximum display performance out of video games without any fractional framerate limits, and without the annoyance of screen tearing. They argue that if a particular PC can run a particular game at, say, 107 frames per second, you'll get 107 frames per second, not 60, and thus your reaction times will be better and gameplay will be smoother. You'll always get the most out of your rig, rather than being limited by the display (up to the maximum refresh rate supported by the display, eg. 144 Hz.)

However, I think that for a more regular gamer (like me) there's a much better practical reason why adaptive sync technology, such as G-Sync, is especially handy and useful. It's a bit related to the above, but it's not about the efficiency of the game and how much it eg. could improve your reaction times etc.

As a more normal gamer I don't really care if a game is running at, let's say, 50 Hz, or 70 Hz, or 120 Hz. It all looks essentially the same to me. (It's only at about 40-45 Hz or thereabouts that I start noticing the slower framerate in casual gameplay.)

Much more important and practical for me is that G-Sync almost completely frees me from having to worry about optimizing the game settings to hit that golden 60 Hz threshold.

With a regular non-adaptive-syncing display, when you use vsync (which is a must if you don't want screen tearing), if your PC is not capable of running a particular game consistently at 60 Hz or above, it will drop below that at points, which with vsync means that it will immediately drop down to 30 Hz. This can be quite annoying, especially if the game keeps constantly and randomly switching between 60 and 30 Hz. This random constant switching between the two framerates causes an uneven jitter in the game, which is even more annoying than if the game just always ran at 30 Hz.

In fact, prior to getting a G-Sync monitor, if a game was really heavy to render and I didn't want to reduce the resolution any further, I would just limit it to 30 Hz. Better a constant 30 Hz than random jumping between 60 and 30. The constant 30 is less annoying.

G-Sync, however, solves this problem beautifully. It almost completely removes any need to worry about hitting that magical 60 Hz threshold. With G-Sync it doesn't matter if the game occasionally drops a bit below 60 Hz, like to 55 Hz, or even 50. It still looks good, and you don't even notice. With G-Sync you can completely forget about that magical number "60", because it doesn't mean anything anymore. There is no magical framerate number.

(As mentioned, the only situation where I start noticing some jitter is if the framerate drops to about 40 Hz and below. However, with most games with my rig that doesn't happen all that often. I have a quite hefty gaming PC. But even then, the transition is still very smooth, not jumpy like without G-Sync, and it jumping between 60 and 30 Hz, so even when the framerate drops to something like 40, it's not as annoying looking.)

This is the main reason why I enjoy G-Sync. It's not the high framerates that matter to me, but the ones below 60, which were a pain before.