The Weekend Apelsin Got Lost All The Time

So on thursday morning my friend apelsin mentioned a hackathon at his college, San Jose University. I expressed interest but pointed out that I live 800 miles away. So he bought me a ticket on the last plane flying to San Francisco that night. 10 hours after he had mentioned this hackathon with me, I was riding on a train to San Jose University (after missing one train and getting off on the wrong stop).

The hackathon had prizes - $3100, $1500, and $600 for 1^st, 2^nd, and 3^rd, respectively. The goal was to build, in 24 hours, a AI for a game. The game was a 7x7 board with empty tiles on it. To win a round, you must construct a continuous path from one side to the other. Player 1 must construct a path connecting the left and right sides, while player 2 must construct a path from top to bottom. The squares are grouped into randomized sets, which are then run through over and over, and each time a set is made available, each bot places a bid on the set. The highest bid gets to pick any square from that set and claim it. You had 98 credits to bid with (7*7*2 = 98) and there was no way to get more.

I was able to build an atemporal pathfinding algorithm that constructed a 7-turn path by figuring out in advance which squares would be available which turn. To prevent difficult edge cases I simplified it so it would always try to do it in 7 turns and simply bid 14 credits each time. My friend helped with debugging and brainstorming ideas, as well as setting everything up, and we had to keep correcting each other on how the game actually worked, but the entire time I was also learning how to use a mac, since my only laptop was a piece of shit and he only had macs.

We were also trying to use Codelite in the hopes that it would be better than Xcode, but that ended up being a disaster with constant crashes and failed debuggers. As a result, I learned two things from this hackathon: I fucking hate macs, and Codelite is a horrible, unstable IDE you should never use.

I was only able to stabilize our algorithm with 40 minute left in the competition. I attempted to implement an aggressive analysis algorithm that would detect a potential win condition for the opponent and block it, but it never worked. Had I instead extended the algorithm to simply look for alternative paths longer than 7 turns, we probably would have won, but I didn't realize that until after the competition. Even though we only had a very basic algorithm, our pathfinding was extremely strong and as a result we got all the way to 4th place. Unfortunately, that wasn't enough for a cash prize, so we weren't able to recoup the plane ticket cost.

So then we took a train back up to his house in San Francisco, went out for dinner, and did more music stuff with his crazy studio monitor setup. The next day involved fisherman's wharf, candy, being lost, and getting to play around on a hardware synth. Then I went to bed and today I got flown back to Seattle.

All because my friend looked at a hackathon advertisement on Thursday morning.

Today I Was Mistaken For A 17-Year-Old Girl

This is what they had to say about me:

This was in response to an article I posted on reddit about a 17-year-old american girl who put on a hijab and went to a mall for 2 hours. She describes being completely ignored by everyone, save for a 4 year old girl who asked if she was a terrorist. All because she wore a scarf on her head.

I have read about hundreds of horrifying accounts of sexism and seen thousands of sickening displays of misogynistic hatred (just dig around youtube for 5 seconds). But, as they say, it's never quite the same until it happens to you.

It was just funny at first - some dumbass thought I wrote the article just because I submitted it? No wonder he was so full of impulsive hatred. Perhaps he was trolling, or thought it was funny to brutally attack a woman for committing the crime of being born. But as I read the message a few more times, it dawned on me that this was simply an errant fool mistaking me for the opposite gender, yet the champions of feminism must get these kinds of messages all the time.

Of course, I am no stranger to controversy, having spent hours defending my bountiful collection of unpopular opinions about programming languages that no one should really care about. Hundreds of people have felt it necessary to inform me how horribly wrong all my opinions are, and how I'm so bad at programming the world would be a better place if I never wrote another line of code. So why did this message pierce my internet-hate-machine defenses - a message that wasn't even directed at me? Why did it make me think about what it would be like to be a woman and have my inbox full of this vitriolic misogyny every day just because I had an opinion?

In every technical argument, every hateful comment directed at me, they were all due to choices I made. If my opinions were, in fact, so terribly wrong, it was not because I was a horrible human being, it was simply because I made the wrong choices. When somebody calls you a bitch and tells you to bend over, they are not saying this because of choices you made, they are saying this because you are female. As if the fact that you lack a Y-chromosome gives them an innate right to belittle you and strip away your humanity. There is a difference between being told that you are a stupid idiot, and being considered subhuman. It is this subtle, yet infinitely important difference that many people seem to miss.

While I was still young and in primary school, I thought the only difference between boys and girls was that one had a penis and one didn't. It seems that society has failed to manage a level of maturity greater than that of a 9-year-old boy. In fact, when I was in kindergarten, we were playing a game, and the teams were girls vs boys, as usual. I noticed, however, that the girls were significantly outnumbered. In a bid that surprised even myself, I declared that I would join the girls team in order to make things fair.

I wish it were that easy, but supporting women's rights isn't necessarily about standing up for women - it's about letting women stand up for themselves. It's about treating them like normal human beings and giving them the opportunity to solve their own problems. It's about respecting them because of who they are, not simply due to their gender.

Perhaps one day, society can rise to a 9-year-old kid's level of sophistication.

C# to C++ Tutorial - Part 4: Operator Overload

[ 1 · 2 · 3 · 4 · 5 · 6 · 7 ]

If you are familiar with C#, you should be familiar with the difference between C#'s struct and class declarations. Namely, a struct is a value type and a class is a reference type, meaning that if you pass a struct to a function, its default behavior is for the entire struct to be copied into the function's parameter, so any modifications made to it won't affect whatever was passed in. On the flip side, a class is a reference value, so a reference is passed into the function, and any changes made to that reference will be reflected in the object that was originally passed into the function.

// Takes an integer, or a basic value type
public static int add(int v)
{
  v+=3;
  return 4+v;
}

public struct Oppa
{
  public string gangnam;
}

// Takes a struct, or a complex value type
public static Oppa style(Oppa g)
{
  g.gangnam="notstyle";
  return g;
}

public class Psy
{
  public int style;
}

// Takes a class, or a reference type
public static void change(Psy psy)
{
  psy.style=5;
}

// Takes an integer, but forces it to be passed by reference instead of by value.
public static int addref(ref int v)
{
  v+=3;
  return 4+v;
}

int a = 0;
int b = add(a);
// a is still 0
// b is now 7

int c = addref(a);
// a is now 3, because it was passed by reference
// c is now 7

Oppa s1;
s1.gangnam="style";
Oppa s2 = style(s1);
//s1.gangnam is still "style"
//s2.gangnam is now "notstyle"

Psy psy = new Psy();
psy.style=0;
change(psy);
// psy.style is now 5, because it was passed by reference

C++ also lets you pass in parameters by reference and by value, however it is more explicit about what is happening, so there is no default behavior to know about. If you simply declare the type itself, for example (myclass C, int B), then it will be passed by value and copied. If, however, you use the reference symbol that we've used before in variable declarations, it will be passed by reference. This happens no matter what. If a reference is passed into a function that takes a value, it will still have a copy made.

// Integer passed by value
int add(int v)
{
  v+=3;
  return 4+v;
}

class Psy
{
public:
  int style;
};

// Class passed by value
Psy change(Psy psy)
{
  psy.style=5;
  return psy;
}

// Integer passed by reference
int addref(int& v)
{
  v+=3;
  return 4+v;
}

// Class passed by reference
Psy changeref(Psy& psy)
{
  psy.style=5;
  return psy;
}

int horse = 2;
int korea = add(horse);
// horse is still 2
// korea is now 9

int horse2 = 2;
int korea2 = addref(horse2);
// horse2 is now 5
// korea2 is now 9

Psy psy;
psy.style = 0;
Psy ysp = change(psy);
// psy.style is still 0
// ysp.style is now 5

Psy psy2;
psy2.style = 0;
Psy ysp2 = changeref(psy2);
// psy2.style is now 5
// ysp2.style is also 5

However, in order to copy something, C++ needs to know how to properly copy your class. This gives rise to the copy constructor. By default, the compiler will automatically generate a copy constructor for your class that simply invokes all the default copy constructors of whatever member variables you have, just like C#. If, however, your class is holding on to a pointer, then this is going to cause a giant mess when two classes are pointing to the same thing and one of the deletes what it's pointing to! By specifying a copy constructor, we can deal with the pointer properly:

class myString
{
public:
  // The copy constructor, which copies the string over instead of copying the pointer
  myString(const myString& copy)
  {
    size_t len = strlen(copy._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,copy._str,sizeof(char)*len);
  }
  // Normal constructor
  myString(const char* str)
  {
    size_t len = strlen(str);
    _str=new char[len];
    memcpy(_str,str,sizeof(char)*len);
  }
  // Destructor that deallocates our string
  ~myString()
  {
    delete [] _str;
  }

private:
  char* _str;
};

This copy constructor can be invoked manually, but it will simply be implicitly called whenever its needed. Of course, that isn't the only time we need to deal with our rogue pointer that screws things up. What happens when we set our class equal to another class? Remember, a reference cannot be changed after it is created. Observe the following behavior:

int a = 3;
int b = 2;
int& ra = a;
int* pa = &a;

b = a; //b is now 3
a = 0; //b is still 3, but a is now 0
b = ra; // b is now 0
a = 5; // b is still 0 but now a is 5
b = *pa; // b is now 5
b = 8; // b is now 8 but a is still 5

ra = b; //a is now 8! This assigns b's values to ra, it does NOT change the reference!
ra = 9; //a is now 9, and b is still 8! ra STILL refers to a, and NOTHING can change that.

pa = &b; // Now pa points to to b
a = *pa; // a is now 8, because pointers CAN be changed.
*pa = 7; // Now b is 7, but a is still 8

int*& rpa = pa; //Now we have a reference to a pointer (C++11)
//rpa = 5; // COMPILER ERROR, rpa is a reference to a POINTER
int** ppa = &pa;
//rpa = ppa; // COMPILER ERROR, rpa is a REFERENCE to a pointer, not a pointer to a pointer!
rpa = &a; //now pa points to a again. This does NOT change the reference!
b = *pa; // Now b is 8, the same as a.

So somehow, we have to overload the assignment operator! This brings us to Operator Overloading. C# operator overloading works by defining global operator overloads, ones that take a left and a right argument, and are static functions. By default, C++ operator overloading only take the right argument. The left side of the equation is implied to be the class itself. Consequently, C++ operators are not static. C++ does have global operators, but they are defined outside the class, and the assignment operator isn't allowed as a global operator; you have to define it inside the class. All the overload-able operators are shown below with appropriate declarations:

class someClass
{
someClass operator =(anything b); // me=other
someClass operator +(anything b); // me+other
someClass operator -(anything b); // me-other
someClass operator +(); // +me
someClass operator -(); // -me (negation)
someClass operator *(anything b); // me*other
someClass operator /(anything b); // me/other
someClass operator %(anything b); // me%other
someClass& operator ++(); // ++me
someClass& operator ++(int); // me++
someClass& operator --(); // --me
someClass& operator --(int); // me--
// All operators can TECHNICALLY return any value whatsoever, but for many of them only certain values make sense.
bool operator ==(anything b); 
bool operator !=(anything b);
bool operator >(anything b);
bool operator <(anything b);
bool operator >=(anything b);
bool operator <=(anything b);
bool operator !(); // !me
// These operators do not usually return someClass, but rather a type specific to what the class does.
anything operator &&(anything b); 
anything operator ||(anything b);

anything operator ~();
anything operator &(anything b);
anything operator |(anything b);
anything operator ^(anything b);
anything operator <<(anything b);
anything operator >>(anything b);
someClass& operator +=(anything b); // Should always return *this;
someClass& operator -=(anything b);
someClass& operator *=(anything b);
someClass& operator /=(anything b);
someClass& operator %=(anything b);
someClass& operator &=(anything b);
someClass& operator |=(anything b);
someClass& operator ^=(anything b);
someClass& operator <<=(anything b);
someClass& operator >>=(anything b);
anything operator [](anything b); // This will almost always return a reference to some internal array type, like myElement&
anything operator *();
anything operator &();
anything* operator ->(); // This has to return a pointer or some other type that has the -> operator defined.

anything operator ->*(anything a);
anything operator ()(anything a1, U a2, ...);
anything operator ,(anything b);
operator otherThing(); // Allows this class to have an implicit conversion to type otherThing
void* operator new(size_t x); // These are called when you write new someClass()
void* operator new[](size_tx); // new someClass[num]
void operator delete(void*x); // delete pointer_to_someClass
void operator delete[](void*x); // delete [] pointer_to_someClass

};

// These are global operators that behave more like C# operators, but must be defined outside of classes, and a few operators do not have global overloads, which is why they are missing from this list. Again, operators can technically take or return any value, but normally you only override these so you can handle some other type being on the left side.
someClass operator +(anything a, someClass b);
someClass operator -(anything a, someClass b);
someClass operator +(someClass a);
someClass operator -(someClass a);
someClass operator *(anything a, someClass b);
someClass operator /(anything a, someClass b);
someClass operator %(anything a, someClass b);
someClass operator ++(someClass a);
someClass operator ++(someClass a, int); // Note the unnamed dummy-parameter int - this differentiates between prefix and suffix increment operators.
someClass operator --(someClass a);
someClass operator --(someClass a, int); // Note the unnamed dummy-parameter int - this differentiates between prefix and suffix decrement operators.

bool operator ==(anything a, someClass b);
bool operator !=(anything a, someClass b);
bool operator >(anything a, someClass b);
bool operator <(anything a, someClass b);
bool operator >=(anything a, someClass b);
bool operator <=(anything a, someClass b);
bool operator !(someClass a);
bool operator &&(anything a, someClass b);
bool operator ||(anything a, someClass b);

someClass operator ~(someClass a);
someClass operator &(anything a, someClass b);
someClass operator |(anything a, someClass b);
someClass operator ^(anything a, someClass b);
someClass operator <<(anything a, someClass b);
someClass operator >>(anything a, someClass b);
someClass operator +=(anything a, someClass b);
someClass operator -=(anything a, someClass b);
someClass operator *=(anything a, someClass b);
someClass operator /=(anything a, someClass b);
someClass operator %=(anything a, someClass b);
someClass operator &=(anything a, someClass b);
someClass operator |=(anything a, someClass b);
someClass operator ^=(anything a, someClass b);
someClass operator <<=(anything a, someClass b);
someClass operator >>=(anything a, someClass b);
someClass operator *(someClass a);
someClass operator &(someClass a);

someClass operator ->*(anything a, someClass b);
someClass operator ,(anything a, someClass b);
void* operator new(size_t x);
void* operator new[](size_t x);
void operator delete(void* x);
void operator delete[](void*x);

We can see that the assignment operator mimics the arguments of our copy constructor. For the most part, it does the exact same thing; the only difference is that existing values must be destroyed, an operation that should mostly mimic the destructor. We extend our previous class to have an assignment operator accordingly:

class myString
{
public:
  // The copy constructor, which copies the string over instead of copying the pointer
  myString(const myString& copy)
  {
    size_t len = strlen(copy._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,copy._str,sizeof(char)*len);
  }
  // Normal constructor
  myString(const char* str)
  {
    size_t len = strlen(str);
    _str=new char[len];
    memcpy(_str,str,sizeof(char)*len);
  }
  // Destructor that deallocates our string
  ~myString()
  {
    delete [] _str;
  }

  // Assignment operator, does the same thing the copy constructor does, but also mimics the destructor by deleting _str. NOTE: It is considered bad practice to call the destructor directly. Use a Clear() method or something equivalent instead.
  myString& operator=(const myString& right)
  {
    delete [] _str;
    size_t len = strlen(right._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,right._str,sizeof(char)*len);
  }

private:
  char* _str;
};

These operations take an instance of the class and copy it's values to our instance. Consequently, these are known as copy semantics. If this was 1998, we'd stop here, because for a long time, C++ only had copy semantics. Either you passed around references to objects, or you copied them. You could also pass around pointers to objects, but remember that pointers are value types just like integers and floats, so you are really just copying them around too. In fact, until recently, you were not allowed to have references to pointers. Pointers were the one data type that had to be passed by value. Provided you are using a C++0x-compliant compiler, this is no longer true, as you may remember from our first examples. The new standard released in 2011 allows references to pointers, and introduces move semantics.

Move semantics are designed to solve the following problem. If we have a series of dynamic string objects being concatenated, with normal copy constructors we run into a serious problem:

std::string result = std::string("Oppa") + std::string(" Gangnam") + std::string(" Style") + std::string(" by") + std::string(" Psy");
// This is evaluated by first creating a new string object with its own memory allocation, then deallocating both " by" and " Psy" after copying their contents into the new one
//std::string result = std::string("Oppa") + std::string(" Gangnam") + std::string(" Style") + std::string(" by Psy");
// Then another new object is made and " by Psy" and " Style" are deallocated
//std::string result = std::string("Oppa") + std::string(" Gangnam") + std::string(" Style by Psy");
// And so on and so forth
//std::string result = std::string("Oppa") + std::string(" Gangnam Style by Psy");
//std::string result = std::string("Oppa Gangnam Style by Psy");
// So just to add 5 strings together, we've had to allocate room for 5 additional strings in the middle of it, 4 of which are then simply deallocated!

This is terribly inefficient; it would be much more efficient if we could utilize the temporary objects that are going to be destroyed anyway instead of reallocating a bunch of memory over and over again only to delete it immediately afterwards. This is where move semantics come in to play. First, we need to define a "temporary" object as one whose scope is entirely contained on the right side of an expression. That is to say, given a single assignment statement a=b, if an object is both created and destroyed inside b, then it is considered temporary. Because of this, these temporary values are also called rvalues, short for "right values". C++0x introduces the syntax variable&& to designate an rvalue. This is how you declare a move constructor:

class myString
{
public:
  // The copy constructor, which copies the string over instead of copying the pointer
  myString(const myString& copy)
  {
    size_t len = strlen(copy._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,copy._str,sizeof(char)*len);
  }
  // Move Constructor
  myString(myString&& mov)
  {
    _str = mov._str;
    mov._str=NULL;
  }
  // Normal constructor
  myString(const char* str)
  {
    size_t len = strlen(str);
    _str=new char[len];
    memcpy(_str,str,sizeof(char)*len);
  }
  // Destructor that deallocates our string
  ~myString()
  {
    if(_str!=NULL) // Make sure we only delete _str if it isn't NULL!
      delete [] _str;
  }

  // Assignment operator, does the same thing the copy constructor does, but also mimics the destructor by deleting _str. NOTE: It is considered bad practice to call the destructor directly. Use a Clear() method or something equivalent instead.
  myString& operator=(const myString& right)
  {
    delete [] _str;
    size_t len = strlen(right._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,right._str,sizeof(char)*len);
    return *this;
  }

private:
  char* _str;
};

NOTE: Observe that our destructor functionality was changed! Now that _str can be NULL, we have to check for that before deleting the object.

The idea behind a move constructor is that, instead of copying the values into our object, we move them into our object, setting the source to some NULL value. Notice that this can only work for pointers, or objects containing pointers. Integers, floats, and other similar types can't really be "moved", so instead their values are simply copied over. Consequently, move semantics is only beneficial for types like strings that involve dynamic memory allocation. However, because we must set the source pointers to 0, that means we can't use const myString&&, because then we wouldn't be able to modify the source pointers! This is why a move constructor is declared without a const modifier, which makes sense, since we intend to modify the object.

But wait, just like a copy constructor has an assignment copy operator, a move constructor has an equivalent assignment move operator. Just like the copy assignment, the move operator behaves exactly like the move constructor, but must destroy the existing object beforehand. The assignment move operator is declared like this:

myString& operator=(myString&& right)
  {
    delete [] _str;
    _str=right._str;
    right._str=0;
    return *this;
  }

Move semantics can be used for some interesting things, like unique pointers, that only have move semantics - by disabling the copy constructor, you can create an object that is impossible to copy, and can therefore only be moved, which guarantees that there will only be one copy of its contents in existence. std::unique_ptr is an implementation of this provided in C++0x. Note that if a data structure requires copy semantics, std::unique_ptr will throw a compiler error, instead of simply mysteriously failing like the deprecated std::autoptr.

There is an important detail when you are using inheritance or objects with move semantics:

class Substring : myString
{
  Substring(Substring&& mov) : myString(std::move(mov))
  {
    _sub = std::move(mov._sub);
  }

  Substring& operator=(Substring&& right)
  {
    myString::operator=(std::move(right));
    _sub = std::move(mov._sub);
    return *this;
  }

  myString _sub;
};

Here we are using std::move(), which takes a variable (that is either an rvalue or a normal reference) and returns an rvalue for that variable. This is because rvalues stop being rvalues the instant they are passed into a different function, which makes sense, since they are no longer on the right-hand side anymore. Consequently, if we were to pass mov above into our base class, it would trigger the copy constructor, because mov would be treated as const Substring&, instead of Substring&&. Using std::move lets us pass it in as Substring&& and properly trigger the move semantics. As you can see in the example, you must use std::move when moving any complex object, using base class constructors, or base class assignment operators. Note that std::move allows you to force an object to be moved to another object regardless of whether or not its actually an rvalue. This would be particularly useful for moving around std::unique_ptr objects.

There's some other weird things you can do with move semantics. This most interesting part is the strange behavior of && when it is appended to existing references.

• A& & becomes A&
• A& && becomes A&
• A&& & becomes A&
• A&& && becomes A&&

By taking advantage of the second and fourth lines, we can perform perfect forwarding. Perfect forwarding allows us to pass an argument as either a normal reference (A&) or an rvalue (A&&) and then forward it into another function, preserving its status as an rvalue or a normal reference, including whether or not it's const A& or const A&&. Perfect forwarding can be implemented like so:

template<typename U>
void Set(U && other)
{
  _str=std::forward<U>(other);
}

Notice that this allows us to assign our data object using either the copy assignment, or the move assignment operator, by using std::forward<U>(), which transforms our reference into either an rvalue if it was an rvalue, or a normal reference if it was a normal reference, much like std::move() transforms everything into an rvalue. However, this requires a template, which may not always be correctly inferred. A more robust implementation uses two separate functions forwarding their parameters into a helper function:

class myString
{
public:
  // The copy constructor, which copies the string over instead of copying the pointer
  myString(const myString& copy)
  {
    size_t len = strlen(copy._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,copy._str,sizeof(char)*len);
  }
  // Move Constructor
  myString(myString&& mov)
  {
    _str = mov._str;
    mov._str=NULL;
  }
  // Normal constructor
  myString(const char* str)
  {
    size_t len = strlen(str);
    _str=new char[len];
    memcpy(_str,str,sizeof(char)*len);
  }
  // Destructor that deallocates our string
  ~myString()
  {
    if(_str!=NULL) // Make sure we only delete _str if it isn't NULL!
      delete [] _str;
  }
  void Set(myString&& str)
  {
    _set<myString&&>(std::move(str));
  }
  void Set(const myString& str)
  {
    _set<const myString&>(str);
  }


  // Assignment operator, does the same thing the copy constructor does, but also mimics the destructor by deleting _str. NOTE: It is considered bad practice to call the destructor directly. Use a Clear() method or something equivalent instead.
  myString& operator=(const myString& right)
  {
    delete [] _str;
    size_t len = strlen(right._str)+1; //+1 for null terminator
    _str=new char[len];
    memcpy(_str,right._str,sizeof(char)*len);
    return *this;
  }

private:
  template<typename U>
  void _set(U && other)
  {
    _str=std::forward<U>(other);
  }

  char* _str;
};

Notice the use of std::move() to transfer the rvalue correctly, followed by std::forward<U>() to forward the parameter. By using this, we avoid redundant code, but can still build move-aware data structures that efficiently assign values with relative ease. Now, its on to Part 5: Delegated Llamas! Or, well, delegates, function pointers, and lambdas. Possibly involving llamas. Maybe.

Lockless Lattice-Based Computing

The Flow Programming Language was introduced as a form of lattice-based computing¹. This method of thinking about code structure was motivated by the need to make implicit parallelization of code possible at compile-time. Despite this, it has fascinated me for a number of reasons that extend well beyond simple multithreading applications. Most intriguing is its complete elimination of memory management². A lattice-based programming language doesn't have manual memory allocation or garbage collection, because it knows when and where memory is needed throughout the entire program. This is particularly exciting to me, because for the longest time I've had to use C or C++ simply because they are the only high-performance languages in existence that don't have garbage collection, which can be catastrophic in real-time scenarios, like games.

Naturally, this new methodology is not without its flaws. In particular, it currently has no way of addressing the issue of what to do when one variable depends on the values of multiple other variables, which can give rise to race conditions.



In the above diagram, both e and f depend on multiple previous results. This is a potential race condition, and the only current proposed solution is using traditional locks, which would incur contention issues³. This, however, is not actually necessary.

Instead of using an ugly lock, we can instead pair each variable up with a parameter counter. This counter keeps track of the number of dependent variables that have yet to be calculated. When a variable is resolved, it atomically decrements the parameter counter for all variables that are immediately dependent on it. If this atomic decrement results in a value of exactly 0, the thread can take one of 3 options:

1. Queue a task to the thread manager to execute the variable's code path at some point in the future.
2. Add the variable to its own execution queue and evaluate it later.
3. Evaluate the variable and its execution path immediately (only valid if there are no other possible paths of execution)

If a thread reaches the a situation where all variables dependent on the last value it evaluated have nonzero parameter counts, then the thread simply "dies" and is put back into the thread scheduler to take on another task. This solution takes advantage of the fact that any implicit parallelization solution will require a robust method of rapidly creating and destroying threads (most likely through some kind of task system). Consequently, by concentrating all potential race conditions and contention inside the thread scheduler itself, we can simply implement it with a lockless algorithm and eliminate every single race condition in the entire program.

It's important to note that while the thread scheduler may be implemented with a lock-free (or preferably wait-free) algorithm, the program itself does not magically become lock-free, simply because it can always end up being reduced to a value that everything else depends on which then locks up and freezes everything. Despite this, using parameter counters provides an elegant way of resolving race-conditions in lattice-based programming languages.

This same method can be used to construct various intriguing multi-threading scenarios, such as attempting to access a GPU. Calling a GPU DrawPrimitive method cannot be done from multiple threads simultaneously. Once again, we could solve this in a lattice-based programming language by simply introducing locks, but I hate locks. Surely there is a more elegant approach? One method would be to simply construct an algorithm that builds a queue of processed primitives that is then pumped into the GPU through a single thread. This hints at the idea that so long as a non-thread-safe function is isolated to one single thread of execution inside a program, we can guarantee it will never be called at the same time at compile time. In other words, it can only appear once per-level in the DAG.

Of course, what if we wanted to render everything in a specific order? We introduce a secondary dependency in the draw call, such that it is dependent both on the primitive processing results, and a dummy variable that is resolved only when the drawing call directly before it is completed. If the primitive processing finishes before the previous drawing call is completed, the thread simply dies. When the previous drawing call is finished, that thread decrements the variable's parameter count to 0 and, because there are no other avenues of execution, simply carries on finishing the drawing call for the now dead thread. If, however, the previous drawing call is completed before the next primitive can be processed, the previous thread now dies, and when the primitive drawing is completed, that thread now carries on the drawing calls.



What is interesting is that this very closely mirrors my current implementation in C++ for achieving the exact same task in a real-world scenario, except it is potentially even more efficient due to its ability to entirely avoid dynamic memory allocation. This is very exciting news for high performance programmers, and supports the idea of Lattice-Based Programming becoming a valuable tool in the near future.


¹ I'd much rather call it "Lattice-Based Programming", since it's a way of thinking about code and not just computing.
² I would link to this if the original post had anchors to link to.
³ Also, I happen to have a deep-seated, irrational hatred of locks.

7 Problems Raytracing Doesn't Solve

I see a lot of people get excited about extreme concurrency in modern hardware bringing us closer to the magical holy grail of raytracing. It seems that everyone thinks that once we have raytracing, we can fully simulate entire digital worlds, everything will be photorealistic, and graphics will become a "solved problem". This simply isn't true, and in fact highlights several fundamental misconceptions about the problems faced by modern games and other interactive media.

For those unfamiliar with the term, raytracing is the process of rendering a 3D scene by tracing the path of a beam of light after it is emitted from a light source, calculating its properties as it bounces off various objects in the world until it finally hits the virtual camera. At least, you hope it hits the camera. You see, to be perfectly accurate, you have to cast a bajillion rays of light out from the light sources and then see which ones end up hitting the camera at some point. This is obviously a problem, because most of the rays don't actually hit the camera, and are simply wasted. Because this brute force method is so incredibly inefficient, many complex algorithms (such as photon-mapping and Metropolis light transport) have been developed to yield approximations that are thousands of times more efficient. These techniques are almost always focused on attempting to find paths from the light source to the camera, so rays can be cast in the reverse direction. Some early approximations actually cast rays out from the camera until they hit an object, then calculated the lighting information from the distance and angle, disregarding other objects in the scene. While highly efficient, this method produced extremely inaccurate results.

It is with a certain irony that raytracing is touted as being a precise, super-accurate rendering method when all raytracing is actually done via approximations in the first place. Pixar uses photon-mapping for its movies. Most raytracers operate on stochastic sampling approximations. We can already do raytracing in realtime, if we get approximate enough, it just looks boring and is extremely limited. Graphics development doesn't just stop when someone develops realtime raytracing, because there will always be room for a better approximation.

1. Photorealism

The meaning of photorealism is difficult to pin down, in part because the term is inherently subjective. If you define photorealism as being able to render a virtual scene such that it precisely matches a photo, then it is almost impossible to achieve in any sort of natural environment where the slightest wind can push a tree branch out of alignment.

This quickly gives rise to defining photorealism as rendering a virtual scene such that it is indistinguishable from a photograph of a similar scene, even if they aren't exactly the same. This, however, raises the issue of just how indistinguishable it needs to be. This seems like a bizarre concept, but there are different degrees of "indistinguishable" due to the differences between people's observational capacities. Many people will never notice a slightly misaligned shadow or a reflection that's a tad too bright. For others, they will stand out like sore thumbs and completely destroy their suspension of disbelief.

We have yet another problem in that the entire concept of "photorealism" has nothing to do with how humans see the world in the first place. Photos are inherently linear, while human experience a much more dynamic, log-based lighting scale. This gives rise to HDR photography, which actually has almost nothing to do with the HDR implemented in games. Games simply change the brightness of the entire scene, instead of combining the brightness of multiple exposures to brighten some areas and darken others in the same photo. If all photos are not created equal, then exactly which photo are we talking about when we say "photorealistic"?

2. Complexity

Raytracing is often cited as allowing an order of magnitude more detail in models by being able to efficiently process many more polygons. This is only sort of true in that raytracing is not subject to the same computational constraints that rasterization is. Rasterization must render every single triangle in the scene, whereas raytracing is only interested in whether or not a ray hits a triangle. Unfortunately, it still has to navigate through the scene representation. Even if a raytracer could handle a scene with a billion polygons efficiently, this raises completely unrelated problems involving RAM access times and cache pollution that suddenly become actual performance bottlenecks instead of micro-optimizations.

In addition, raytracing approximation algorithms almost always take advantage of rays that degrade quickly, such that they can only bounce 10-15 times before becoming irrelevant. This is fine and dandy for walking around in a city or a forest, but what about a kitchen? Even though raytracing is much better at handling reflections accurately, highly reflective materials cripple the raytracer, because now rays are bouncing hundreds of times off a myriad of surfaces instead of just 10. If not handled properly, it can absolutely devastate performance, which is catastrophic for game engines that must maintain constant render times.

3. Scale

How do you raytrace stars? Do you simply wrap a sphere around the sky and give it a "star" material? Do you make them all point sources infinitely far away? How does this work in a space game, where half the stars you see can actually be visited, and the other half are entire galaxies? How do you accurately simulate an entire solar system down to the surface of a planet, as the Kerbal Space Program developers had to? Trying to figure out how to represent that kind of information in a meaningful form with only 64 bits of precision, if you are lucky, is a problem completely separate from raytracing, yet of increasingly relevant concern as games continue to expand their horizons more and more. How do we simulate an entire galaxy? How can we maintain meaningful precision when faced with astronomical scales, and how does this factor in to our rendering pipeline? These are problems that arise in any rendering pipeline, regardless of what techniques it uses, due to fundamental limitations in our representations of numbers.

4. Materials

Do you know what methane clouds look like? What about writing an aerogel shader? Raytracing, by itself, doesn't simply figure out how a given material works, you have to tell it how each material behaves, and its accuracy is wholly dependent on how accurate your description of the material is. This isn't easy, either, it requires advanced mathematical models and heaps of data collection. In many places we're actually still trying to figure out how to build physically correct material equations in the first place. Did you know that Dreamworks had to rewrite part of their cloud shader¹ for How To Train Your Dragon? It turns out that getting clouds to look good when your character is flying directly beneath them with a hand raised is really hard.

This is just for common lighting phenomena! How are you going to write shaders for things like pools of magic water and birefringent calcite crystals? How about trying to accurately simulate circular polarizers when most raytracers don't even know what polarization is? Does being photorealistic require you to simulate the Tyndall Effect for caustics in crystals and particulate matter? There are so many tiny little details all around us that affect everything from the color of our iris to the creation of rainbows. Just how much does our raytracer need to simulate in order to be photorealistic?

5. Physics

What if we ignored the first four problems and simply assumed we had managed to make a perfect, magical photorealistic raytracer. Congratulations, you've managed to co-opt the entirety of your CPU for the task of rendering a static 3D scene, leaving nothing left for the physics. All we've managed to accomplish is taking the "interactive" out of "interactive media". Being able to influence the world around us is a key ingredient to immersion in games, and this requires more and more accurate physics, which are arguably just as difficult to calculate as raytracing is. The most advanced real-time physics engine to-date is the Lagoa Multiphysics, and it can only just barely simulate a tiny scene in a well-controlled environment before it completely decimates a modern CPU. This is without any complex rendering at all. Now try doing that for a scene with a radius of several miles. Oh, and remember our issue with scaling? This applies to physics too! Except with physics, its an order of magnitude even more difficult.

6. Content

As many developers have been discovering, procedural generation is not magic pixie dust you can sprinkle on problems to make them go away. Yet, without advances in content generation, we are forced to hire armies of artists to create the absurd amounts of detail required by modern games. Raytracing doesn't solve this problem, it makes it worse. In any given square mile of a human settlement, there are billions of individual objects, ranging from pine cones, to rocks, to TV sets, to crumbs, all of which technically have physics, and must be kept track of, and rendered, and even more importantly, modeled.

Despite multiple attempts at leveraging procedural generation, the content problem has simply refused to go away. Until we can effectively harness the power of procedural generation, augmented artistic tools, and automatic design morphing, the advent of fully photorealistic raytracing will be useless. The best graphics engine in the world is nothing without art.

7. AI

<Patrician|Away> what does your robot do, sam
<bovril> it collects data about the surrounding environment, then discards it and drives into walls
— Bash.org quote #240849

Of course, while we're busy desperately trying to raytrace supercomplex scenes with advanced physics, we haven't even left any CPU time to calculate the AI! The AI in games is so consistently terrible its turned into its own trope. The game industry spends all its computational time trying to render a scene, leaving almost nothing left for the AI routines, forcing them to rely on techniques from 1968. Think about that - we are approaching the point where AI in games comes down to a 50-year old technique that was considered hopelessly outdated before I was even born. Oh, and I should also point out that Graphics, Physics, Art, and AI are all completely separate fields with fundamentally different requirements that all have to work together in a coherent manner just so you can shoot headshots in Call of Duty 22.

I know that raytracing is exciting, sometimes simply as a demonstration of raw computational power. But it always disheartens me when people fantasize about playing amazingly detailed games indistinguishable from real life when that simply isn't going to happen, even with the inevitable development² of realtime raytracing. By the time it becomes commercially viable, it will simply be yet another incremental step in our eternal quest for infinite realism. It is an important step, and one we should strive for, but it alone is not sufficient to spark a revolution.

¹ Found on the special features section of the How To Train Your Dragon DVD.
² Disclaimer: I've been trying to develop an efficient raytracing algorithm for ages and haven't had much luck. These guys are faring much better.