Strides Interactive

Conditionless ProgrammingFiled Under: Weekly Tuesday Dose of goodness

Hi all, since I’ll be away tomorrow, this week’s post comes early!

Therefore, today I’m going to talk about Condition-less Programming. As you might already figured out, it’s as straightforward as programming software without conditions.

Is that really possible?

After all, conditions are part and parcel of almost any programming language out there. What does it take to be conditionless and why must it be done that way?

Let’s find out…

First of all, I’m not going to go in circles to explain this form of programming. The first thing you have to know is that “Conditionless Programming” is actually an optimization technique to reduce conditional bottlenecks.

Many a time have we been acustomed to use conditionals such as if-else and switch-case. Noticed that I didn’t cover the loop conditions because those conditions are necessary for a loop to function. Removing them is not an option.

However, there’re several cases where if-else can be removed. While switch-case usually deals with numbers, enumerations and constants, it’s also a potential source of code maintenance mayhem.

So, why is conditionless programming an optimization technique?

In if-else statements, other than integers, floats and boolean, it can also evaluate string equality by using the ancient C function strcmp or operator == for C++ strings.

Like it or not, these functions are bound to cause performance issues when used in a large scale. String comparison requires a match byte for byte. Both functions oes comparison lexicographically - meaning that ALL characters on both sides will be checked and the differences will be returned as an integer.

In application orchestration, such comparisons, especially done in real-time frequency, (ie, done per render factor frame or per execution frame) will have significant performance impact on the application itself.

To alleviate this performance bottleneck, a few techniques are devised to counter the effects of string comparison - that is, eliminate string comparison altogether. While some of these techniques are natural to some script languages such as Strides Octopus’s ScriptIDE, it may require more work for others who writes the codes for application orchestration.

Here’re the few things required for conditionless programming optimizations:

1) Reflection - ability to call a function by string name rather than by code. GetProcAddress() is one of them.

2) Naming Convention - That is, the name of the function must be consistent and can be built upon.

Now, we know that Reflection is not an official facility or mechanism of C or C++, but it can still be done as long as you overcome the 2 major obstacles.

1 - Parameter differences
2 - Scope and ownership
3 - Hashing and storing these functions

It’ll probably end up becoming pure C functions rather than C++ methods belonging to a class. Your parameter(s) will then be a standard complex object (also known as an envelope).

Let’s say if you have the following functions stored in a hash map:

Key, Value

“Create Jet Fighter Craft”, CREATE_JET_FIGHTER_CRAFT()
“Create Shuttle Craft”, CREATE_SHUTTLE_CRAFT()
“Create Parachute Craft”, CREATE_PARACHUTE()

Let’s say, I have a function that receives a string. This string will contain either “Jet Fighter”, “Shuttle”, or “Parachute”. How can I call the right creation methods for each of these crafts?

Method #1

In code, this is probably how people will normally do it:

void createCraft(cString& parmCraftName)
{
    if(parmCraftName == "Jet Fighter")
        CREATE_JET_FIGHTER_CRAFT();
    else if(parmCraftName == "Shuttle")
        CREATE_SHUTTLE_CRAFT();
    else if(parmCraftName == "Parachute")
        CREATE_PARACHUTE();
}

* note that cString::operator == does the same thing as strcmp() but returns only a true or false.

In any case, if there’s 1000 parachutes being created, the code would have to compare the parameter against “Jet Fighter” and “Shuttle” 1000 times as well, slowing things down when they don’t have to.

Method #2

With conditionless programming, the same thing can be achieved with lesser comparisons:

typedef void (_cdecl * FUNCTION)();

void createCraft(cString& parmCraftName)
{
    cString finalFuncName = "Create ";
    finalFuncName += parmCraftName;
    finalFuncName += " Craft";

    FUNCTION func = funcHashMap.get(finalFuncName); //hash map, worst-case O(log 2 (n))
    if(func)
        func(); //run the function

}

You may think, what’s the big deal? I might have saved myself only at most 1-2 comparisons max since the Big-O-notation of hash map still requires some comparison internally even though not all the strings are compared.

Actually, it IS a big deal when the deal gets bigger. Now we have 3 crafts, string comparison has little or minimal effect. If you have 300 crafts or even 30,000 crafts, the amount of string comparison done will certainly matter.

An algorithm like that has a Big-O-Notation of O(n)(m) - where n is the number of crafts, and m is the variable string length of a craft name. We can set a minimum size to m, say, 5 bytes per m. So, for 30,000 crafts, the total iterations required to execute the right creation fucntion is 30,000 x 5 = 150,000 and that’s considered an optimistic estimation!

Why is m considered to be a set of iterations? That’s because, string comparisons are done byte with byte. So go figure.

Let’s say if we use the second method to work on things, what’ll be the Big O notation?

O(log 2 (n) ) (m)

2^15 = 32768, therefore worst case would be 15 iterations in the hash map. Let’s consider a more conservative number for m. Say, m=50 bytes.

Total iterations required: 15*50 = 750 iterations.

That means, assuming that there’re 30,000 crafts and the string length of each craft is estimated to be at 50 bytes long (or 25 unicode bytes)

Let’s do the same for the first method:

Total iterations required: 30,000 * 50 = 150,000 iterations.

750 iterations compared to 150,000 iterations. That’s a BIG BIG difference if you ask me and that difference gets larger as you add more crafts into the list.

Conclusion

Conditionless programming works best if there’s a relatively large data set and with the right underlying tools such as a hash map and common function names, you’ll find that your application performs better than simple bulldoze comparison in any case.

It’s not always applicable for very small data sets, ie, no more than 10 comparisons. In that case, method #1 might work just as well and might not worth the hassle to setup the entire scheme just to optimize that small part of the code.

In Strides Octopus, this very method is used to immediately call scripts without having to perform condition checks. This is essential since Strides Script as mentioned in a post I did a long time ago, performs poorly in comparisons and its design discourages nested or sequenced comparisons.

You can still do so, but that’ll involve calling a lot more scripts, which since the respective instructions are stored in memory during runtime, will not be worth doing. Moreover, naming each script to perform a single comparison on each different craft is extremely tedious and repetitive; defeating the purpose of using Strides Octopus altogether.

Therefore in Strides Octopus, when there’s a need to create a ship with a variable name, the following is done:

Run Script Immediate,
Executes all instructions of script [scriptName] of group [scriptGroup] immediately.

[scriptName] = "Create +$global[chosen_ship]+ Fighter"
[scriptGroup] = "Constructors" - you'll need to fill this in yourself since
Strides IDE will not be able to figure out the group only until runtime.

Hope these insights can help you in your own projects!

Signing off,
Jeremy