Game Programming Gems 6

Michael Dickheiser

Mentioned 2

Game Programming Gems 6 is the latest ALL new volume in this critically acclaimed series. Filled with insights from game industry pros, this volume provides faster, better, tools and techniques for making the best games possible. These techniques have been used in today?s most successful games and will help solve many of the challenges facing the development team. Not only do they help the team avoid redundancy and save valuable programming hours, but they push the team to approach problems from a new perspective and develop their own tools to prevent future issues. As with all previous volumes, the core areas of graphics, programming, networking, AI, physics, and audio are thoroughly covered and in this volume, new coverage of game testing, wireless gaming, and scripting has also been added. Game Programming Gems 6 is an indispensable resource that every developer must have on their shelves!

More on Amazon.com

Mentioned in questions and answers.

I've been having fun rendering charts and graphs from co-ordinates lately, and I'm fascinated by using matrices to transform co-ordinate spaces.

I've been able to successfully scale and invert 2 dimensional co-ordinate spaces, but now my appetite is whetted. :)

Where can I go for clear, informative, (free), educational material on matrices, matrix math, especially as applies to 2 and 3 dimensional space?

Thanks!

Those are the information that I found. Some of them might be valuable to You:

Theory:

(Searching for "Matrices" at Google books gives You lots of lecutures, some of which are directly connected with transformations - this is one of the first results, but I cheer You to check more.)

I also encourage (I don't know if this is the right word, I am just learning English) You, to look for this kind of information in one of those books (though they are not free, but You can find large parts of older ones on Google Books):

  1. Game programming gems 7
  2. Game programming gems 6
  3. Game programming gems 5
  4. Game programming gems 4
  5. Game programming gems 3
  6. Game programming gems 2
  7. Game programming gems

Each of those has section about math gems - and there are lots of neat tricks there. Those books are worth every cent.

There are also GPU Programming gems, so You might try them too.

Practice:

If I will find more, I will edit and add links here, but to be honest - I found those links in about 10 minutes of using google. World's most popular browser stores data about everything - and yes, "everything" means matrices too.

Cheers, Mate.

I really dont understand how you can make some data structures lock-free. For example, if you have a linked list then either you surround the operations with mutexes, OR you can end up with a race condition if another thread executes whilst you are busy re-linking new nodes together.

The concept of "lock free" (I appreciate it doesnt mean "No locks" but means threads can progress without waiting for other threads to finish) just doesnt make sense.

Could somebody please show me a simple example using a stack, queue or linked list etc which is implemented as "lock-free" because I cannot understand how you can prevent the race condition without interfering with another threads productivity? Surely these two aims contradict each other?

Lockless structure use atomic instruction to acquire ownership of resources. Atomic instruction lock the variable it's working at CPU cache level, witch assure you that another cores can't interfere with the operation.

Let's say you have these atomic instruction:

  • read(A) -> A
  • compare_and_swap(A, B, C) -> oldA = A; if (A == B) { A = C }; return oldA;

With these instruction you can simply create a stack:

template<typename T, size_t SIZE>
struct LocklessStack
{
public:
  LocklessStack() : top(0)
  {
  }
  void push(const T& a)
  {
     int slot;
     do
     {
       do
       {
         slot = read(top);
         if (slot == SIZE)
         {
           throw StackOverflow();
         }
       }while(compare_and_swap(top, slot, slot+1) == slot);
       // NOTE: If this thread stop here. Another thread pop and push
       //       a value, this thread will overwrite that value [ABA Problem].
       //       This solution is for illustrative porpoise only
       data[slot] = a;
     }while( compare_and_swap(top, slot, slot+1) == slot );
  }
  T pop()
  {
     int slot;
     T temp;
     do
     {
       slot = read(top);
       if (slot == 0)
       {
         throw StackUnderflow();
       }
       temp = data[slot-1];
     }while(compare_and_swap(top, slot, slot-1) == slot);
     return temp;
  }
private:
  volatile int top;
  T data[SIZE];
};

volatile is required so compiler don't mess the order of operation during optimization. Two concurrent push occur:

The first one enter in the while loop and read slot, then the second push arrive, read top, the compare and swap (CAS) succeed and increment top. The other thread wake up, the CAS fail and read another time top..

Two concurrent pop occur:

Really similar to the previous case. Need to read the value as well.

One pop and push occur simultaneously:

pop read the top, read temp.. push enter and modify top and push a new value. Pop CAS fail, pop() will do the cycle again and read a new value

or

push read the top and acquire a slot, pop enter and modify the top value. push CAS fail and have to cycle again pushing on a lower index.

Obviously this is not true in a concurrent environment

stack.push(A);
B = stack.pop();
assert(A == B); // may fail

cause while push is atomic and pop is atomic the combination of them is not atomic.

First chapter of Game programming gem 6 is a nice reference.

Note the code is NOT TESTED and atomic can be really nasty.