Pierre Terdiman

My favourite: "You cannot sort floats faster than O(N logN)! It's been PROVEN!" True story – I've heard this claim even from a CS PhD (!!). This is what happens when you forget your assumptions and muddle your terminology. I politely directed him to radix sort [0]. [0] E.g. http://www.codercorner.com/RadixSortRevisited.htm

Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to render. A few ways to solve this pop to mind. As Aeolun mentions in a parallel comment, you can just divide coordinates if your grid is regular. But it often isn’t. In that case, you can attack it in a few ways. One time Feynman was giving a lecture and said “This triangle looks a little cockeyed. Obtuse! That’s the word! I know about the triangles but not their names.” And I’m not Feynman, but I did forget the name of this: you build a tree of squares. First one is your whole grid; split it into four smaller squares, those are the children; repeat till your resolution is sufficient. Then you can attach whatever you want to the child nodes (in this case, grid squares). Since it bisects space into halves, you can do a search in O(log n). But what if you want to go faster? What if it’s absolutely crucial for speed, like a physics engine, to be able to ask “which objects occupy this region of space?” My favorite algorithm is absolutely delightful: a radix sort on floats. http://www.codercorner.com/RadixSortRevisited.htm You end up getting O(k*N) time, just like radix sort normally gives you. But the real magic is that it works with bounding boxes. There’s an article from the same author which I can no longer find, detailing it. But the idea is, you sort all your objects in one spatial dimension first, say along the X…

Another use is doing radix sort of floating point numbers. Since the exponent is in the most significant bits you can almost treat them as integers for radix sort (you just need to be a bit careful with negative values): http://www.codercorner.com/RadixSortRevisited.htm

Very exciting topics, can't wait digging into the book. If you like this, you might also enjoy reading about optimisation tips by Mike Acton (data oriented programming,https://dataorientedprogramming.wordpress.com/tag/mike-acton/ ) and Pierre Terdiman (on collision detection and physics optimizations, for example http://www.codercorner.com/blog/?p=1978) We wrote some book (and SIGGRAPH courses) a few years ago, Multithreading for Visual Effects (http://www.multithreadingandvfx.org). The audience for this kind of books turned out to be pretty small.

I have also heard about it as radix sort : http://www.codercorner.com/RadixSortRevisited.htm

> One interesting thing you'll notice about IEEE754 is that the values sort naturally if you interpret them as sign-magnitude integers With a few bit-twiddling tricks you can even make them radix-sortable, as explained by Malte Skarupke: > Michael Herf has also discovered a good way to generalize this to floating point numbers: Reinterpret cast the float to a uint32, then flip every bit if the float was negative, but flip only the sign bit if the float was positive. The same trick works for doubles and uint64s. Michael Herf explains why this works in the linked piece, but the short version of it is this: Positive floating point numbers already sort correctly if we just reinterpret cast them to a uint32. The exponent comes before the mantissa, so we would sort by the exponent first, then by the mantissa. Everything works out. Negative floating point numbers however would sort the wrong way. Flipping all the bits on them fixes that. The final remaining problem is that positive floating point numbers need to sort as bigger than negative numbers, and the easiest way to do that is to flip the sign bit since it’s the most significant bit. Up until recently in most JS engines it was faster to sort typedarrays with a custom radix sort than with the built-in sort (seems to no longer be the case, thank goodness) [0] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorith… [1] http://www.codercorner.com/RadixSortRevisited.htm [2] http://stereopsis.com/radix.html

If a variable were just a memory address and assignment were just a memory copy, this would be a valid operation. It's a valid operation regardless of whether a standards body says it's not. uint32 x = 5; uint16 y = *(uint16*)&x; The effect is to set y to the first two bytes of memory from x. Values assigned to x are serialized into memory in either big endian or little endian order. Those are the only two cases you have to account for. Quake 3 engine has a macro for the above operation which produces the same value of y on all platforms. This is useful for serializing x to disk, then loading it later (and possibly on a different architecture). One source of confusion is that int and short are essentially, for all intents and purposes, undefined -- they are of course defined by the standards, but their implementation is allowed to vary so much that no programmer can make any assumptions about their size (in bytes) at runtime. int8, int16, int32, int64 are all explicit and force the compiler (and the hardware) to obey the wishes of the programmer. This is, I think, the right approach. People make much ado about the fact that "a byte isn't necessarily 8 bits" and "the only assumption you can make about a short is that it's smaller than an int, and larger than a char", etc, which is probably unnecessary mental effort. "Bytes are 8 bits. Here are four bytes. Here's the value that the four bytes store. Copy two of the four bytes to this other spot (adjusting…

I remember being told a long time ago by our graphics programmer that the result of a floating point operation might be different depending on the state of the FPU. A quick internet search brings up things like this: http://www.codercorner.com/FPUFun.htm which talks about setting the default rounding mode of the FPU. Not sure if that's what he was talking about, but it certainly bears no reference to my issue as I'm certainly not explicitly setting anything like that. That being that case can you give a reasonable explanation why carrying out ( x * y ) then later that function / y gave a value for x that casting would keep as x, when leaving the y division until sometime much later during the run resulted in a value of x - 1? There must have been something different between the two runs apart from literal time, but if nothing is hidden, then what is the difference that made the difference?