Truth tables to simplify logic

[Thalassicus]

If anyone's ever had a long, complicated chain of if-statements checking several boolean variables to figure out what actions to take, this might be helpful for you. I did something like this to solve a bug with the game's display of yield and growth modifiers in the city window (it incorrectly grouped them together and stated base yield was the surplus).

This method comes in three parts:

1. Truth table
2. Function to read the truth table
3. Usage

showYieldString = {
showYieldString = {
--             output      if           input 
--   show { base, surplus} if Consumed YieldMod SurplusMod
          { false, false}, --    -        -         -    
          {  true, false}, --    -        -     SurplusMod
          {  true, false}, --    -     YieldMod     -    
          {  true,  true}, --    -     YieldMod SurplusMod
          { false,  true}, -- Consumed    -         -    
          { false,  true}, -- Consumed    -     SurplusMod
          {  true,  true}, -- Consumed YieldMod     -    
          {  true,  true}  -- Consumed YieldMod SurplusMod
}

function GetTruthTableResult(inputs, truthTable)
  local index = 0
  for k,v in pairs(inputs) do
    if v then
      index = index + math.pow(2, #inputs-k))
    end
  end
  return truthTable[index + 1]
end

...
local truthiness = GetTruthTableResult({isConsumed, hasYieldMod, hasSurplusMod}, showYieldString)
local showBaseYield,showSurplusYield = truthiness[1],truthiness[2]
...

The truth table indicates what outputs should be produced with given inputs.

In this example, if a yield is consumed (input) it always shows the surplus yield (output) on the tooltip. This corresponds with the four rows with "Consumed" in the truth table and four matching "true" statements for surplus. The order of items in the truth table is important: the result function expects each decimal index to correspond to its binary representation (index 0 is 000, then 001, 010, 011, etc).

The reasons I chose this method of implementation are:

• Easy for me to visually understand the logic.
• Separates data from the algorithm.
• Linear execution time: no matter how complex the combinations of input and output, there's only as many conditional checks (if-statements) as there are variables.
• Changing output doesn't require rewriting any if-then conditional statements.
• The output can be anything. In this case I return two table values, but it could be strings, function calls, etc... even different output types for each row in the truth table.

The restrictions to using truth tables are:

• Only works for simple boolean checks as input.
• Table size is exponential to the number of inputs, so it's only feasible with four or less input variables (though output variables are not constrained).

 

[alpaca]

Interesting. I always liked truth tables in my maths lectures

However, it's a lot faster to resolve the logic in your head. But that, admittedly, requires more brainpower and is more error-prone. Your truth table is equivalent to

showBaseYield = (not isConsumed or hasYieldMod) and (hasYieldMod or hasSurplusMod)
showSurplusYield = isConsumed or (hasYieldMod and hasSurplusMod)

 

[Thalassicus]

Completely true about the equivalency. The reason I chose this method is faster execution time, and a series of boolean expressions can be more difficult to change a single 'true' to a 'false' and re-optimize the whole thing.

 

[alpaca]

Completely true about the equivalency. The reason I chose this method is faster execution time, and a series of boolean expressions can be more difficult to change a single 'true' to a 'false' and re-optimize the whole thing.

It may be more comfortable but it sure as hell isn't faster. Creating tables and iterating takes a lot of time.

I ran some tests, one with your code and one with an equivalent series of unoptimized ifs and elseifs (see code below) including the time needed to create function, tables and everything once and execution time with a variable number of times. Benchmark was done using os.clock()

# executions	truth table	ifs
1000	0.0149	0
10000	0.0159	0
100000	0.1411	0.0161
1000000	1.5	0.2029

Your implementation:

local num = 1000
local clockStart = os.clock();
local showYieldString = {
--             output      if           input 
--   show { base, surplus} if Consumed YieldMod SurplusMod
          { false, false}, --    -        -         -    
          {  true, false}, --    -        -     SurplusMod
          {  true, false}, --    -     YieldMod     -    
          {  true,  true}, --    -     YieldMod SurplusMod
          { false,  true}, -- Consumed    -         -    
          { false,  true}, -- Consumed    -     SurplusMod
          {  true,  true}, -- Consumed YieldMod     -    
          {  true,  true}  -- Consumed YieldMod SurplusMod
}

function GetTruthTableResult(inputs, truthTable)
  local index = 0
  for k,v in ipairs(inputs) do
    if v then
      index = index + math.pow(2, #inputs - k)
    end
  end
  return truthTable[index + 1]
end
		
for i = 1,num do
	GetTruthTableResult({false, true, false}, showYieldString)
end
print(os.clock() - clockStart);

Equivalent set of ifs:

local num = 1000
local startClock = os.clock()

function GetTruthiness(a, b, c)
	if not a and not b and not c then
		return false, false
	elseif a and not b and not c then
		return false, true
	elseif not a and b and not c then
		return true, false
	elseif not a and not b and c then
		return true, false
	elseif a and b and not c then
		return true, true
	elseif a and not b and c then
		return false, true
	elseif not a and b and c then
		return true, true
	elseif a and b and c then
		return true, true
	end
end

for i=1,num do
	showBaseYield, showSurplusYield = 	GetTruthiness(false, true, false)
end

print(os.clock() - startClock)

As you can see, your code is at least 7.5 times slower even for very large numbers of executions we're never going to see in the game. For small numbers of executions, table construction time is important (1/100 of a second is quite a lot) and the behaviour is much worse there.


Edit: For reference, here are the number of my "optimized" if statement, which did surprise me a bit at first.

# executions	time
1000	0
10000	0
100000	0.0310
1000000	0.3278

So applying boolean logic is actually a bit slower than just checking the ifs brute-force unless you save a lot of ifs by doing it. If you think about it a bit, it stops being surprising, though: The computer atomizes the statements anyways, so the already atomized version is a little more efficient.


----------------------------------------

Edit 2: On a more personal tip, I would recommend using ipairs instead of pairs if you need order preserved. Pairs is not guaranteed to preserve order. Try executing the following code snippets in fire tuner:

for k,v in pairs({[1]=1,[2]=2,[3]=3,[4]=4,[5]=5,[6]=6,[7]=7,[8]=8,[9]=9,[10]=10}) do print(v) end
for k,v in ipairs({[1]=1,[2]=2,[3]=3,[4]=4,[5]=5,[6]=6,[7]=7,[8]=8,[9]=9,[10]=10}) do print(v) end

 

[Thalassicus]

That's puzzling... looking values up in an array (arithmetic) is generally faster than branches (interrupting the pipe). Creating lua tables must be a very inefficient process...

I don't think having it in the "atomized" form is what makes a difference, if the lua reference manual is accurate in stating lua is compiled... converting the statements to the simplest assembly representation would be done beforehand.

Either way though the execution time is so fast it's not a concern. As you pointed out, it'd take a million executions to even reach the 1-second mark and this code is probably run only a few thousand times throughout an entire game of CiV. Unless doing embedded programming or core game engine tasks, execution time and memory usage are usually secondary priorities to the time/cost of programmers to write code. That's the primary point of this method: takes less time and is easier to create, understand, and modify.

I know about ipairs and use it earlier in the file for the building autotips. Order is not important for this task... and I suspect pairs() is faster or it'd be pointless to have in the language.

 

[alpaca]

That's puzzling... looking values up in an array (arithmetic) is generally faster than branches (interrupting the pipe). Creating lua tables must be a very inefficient process...

I don't think having it in the "atomized" form is what makes a difference, if the lua reference manual is accurate in stating lua is compiled... converting the statements to the simplest assembly representation would be done beforehand.

Either way though the execution time is so fast it's not a concern. As you pointed out, it'd take a million executions to even reach the 1-second mark and this code is probably run only a few thousand times throughout an entire game of CiV. Unless doing embedded programming or core game engine tasks, execution time and memory usage are usually secondary priorities to the time/cost of programmers to write code. That's the primary point of this method: takes less time and is easier to create, understand, and modify.

I know about ipairs and use it earlier in the file for the building autotips. Order is not important for this task... and I suspect pairs() is faster or it'd be pointless to have in the language.

Actually ipairs is almost guaranteed faster. The difference is that ipairs only iterates over the array part of a table while pairs iterates over the whole table, including all hashed entries. Lua is not exactly compiled, I think. It's turned into a set of virtual machine statements pretty much as you write without optimization afaik.

Before I continue talking, I feel like I should mention I'm not actually meaning to criticize what you're doing. I'm trying to get a feeling for how fast Lua code executes, and I'm using this as a learning example.

It actually looks like using os.clock() for benchmarking is not such a hot idea, except if you use a very large number of cycles. Representation of small times seems erratic because it has a resolution of about 0.015 seconds, which you can also see in Lua.log - I'm not sure there's anything better, though.

Just the function call part is still at least five times slower using truth tables as tables rather than truth tables wrapped in if statements (your implementation has constant time no matter the truth values while the ifs use lazy evaluation, so I checked for the true, true, true case) at 18.7 vs 3.3 vs 5.3 seconds @ 10M executions. Another interesting point is that using local variables instead of global saves almost 10% execution time for the last two cases

Setting up the table a million times takes 4.5 seconds, so 4.5 microseconds for even a fairly small table. This is negligible if you only do it once when the file is executed but we should keep it in mind if we set up tables for each plot for example, where you will end up doing it a couple of thousand times. Funnily enough, although not really relevant here, I remembered what I read in a guide about optimizing Lua code and tested setting up the table like this (without creating new tables at every point in the loop), which only takes 0.7 seconds:

local showYieldString = {0,0,0,0,0,0,0,0}
local tTable = {false, false}
for i = 1,num do
	tTable[1] = false
	tTable[2] = false
	showYieldString[1] = tTable
	tTable[1] = true
	tTable[2] = false
	showYieldString[2] = tTable
	tTable[1] = true
	tTable[2] = false
	showYieldString[3] = tTable
	tTable[1] = true
	tTable[2] = true
	showYieldString[4] = tTable
	tTable[1] = false
	tTable[2] = true
	showYieldString[5] = tTable
	tTable[1] = false
	tTable[2] = true
	showYieldString[6] = tTable
	tTable[1] = true
	tTable[2] = true
	showYieldString[7] = tTable
	tTable[1] = true
	tTable[2] = true
	showYieldString[8] = tTable
end

So just the act of creating the new tables every time takes about 6.5 times as long as changing the values.



On a more general note, while it's true that we're only talking microseconds in all cases for single executions, I think that following some general patterns that save these microseconds does add up in the long term. If I can execute code in 0.3 rather than 1.5 milliseconds, this might mean a large difference if looping over all plots, for instance.

 

[SamBC]

Setting up the table a million times takes 4.5 seconds, so 4.5 microseconds for even a fairly small table. This is negligible if you only do it once when the file is executed but we should keep it in mind if we set up tables for each plot for example, where you will end up doing it a couple of thousand times. Funnily enough, although not really relevant here, I remembered what I read in a guide about optimizing Lua code and tested setting up the table like this (without creating new tables at every point in the loop), which only takes 0.7 seconds:

local showYieldString = {0,0,0,0,0,0,0,0}
local tTable = {false, false}
for i = 1,num do
	tTable[1] = false
	tTable[2] = false
	showYieldString[1] = tTable
	tTable[1] = true
	tTable[2] = false
	showYieldString[2] = tTable
	tTable[1] = true
	tTable[2] = false
	showYieldString[3] = tTable
	tTable[1] = true
	tTable[2] = true
	showYieldString[4] = tTable
	tTable[1] = false
	tTable[2] = true
	showYieldString[5] = tTable
	tTable[1] = false
	tTable[2] = true
	showYieldString[6] = tTable
	tTable[1] = true
	tTable[2] = true
	showYieldString[7] = tTable
	tTable[1] = true
	tTable[2] = true
	showYieldString[8] = tTable
end

So just the act of creating the new tables every time takes about 6.5 times as long as changing the values.

I believe that tables are handled entirely as references, to in the above case all 8 entries of showYieldString will be {true,true}, and if anyone ever changes one of them they will all change, because all 8 entries are pointing at one table... this is what I get from PiL, anyway...

 

[alpaca]

I believe that tables are handled entirely as references, to in the above case all 8 entries of showYieldString will be {true,true}, and if anyone ever changes one of them they will all change, because all 8 entries are pointing at one table... this is what I get from PiL, anyway...

Ah, yes, I think you're right. Forgot about that. So you'd have to create 8 different tables. Anyhow that was just to test how slow creating tables really is.