lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]



On Thursday, June 12, 2014, Paige DePol <lual@serfnet.org> wrote:

On Jun 12, 2014, at 4:15 PM, Tim Hill <drtimhill@gmail.com> wrote:

> On Jun 12, 2014, at 11:14 AM, Coda Highland <chighland@gmail.com> wrote:
>
>> On Thu, Jun 12, 2014 at 11:10 AM, Tim Hill <drtimhill@gmail.com> wrote:
>>> For the second case, you place each “case” in its own function, and then put these functions into a table indexed by the “switch” _expression_. Voila! Constant time switch, with no new syntax needed.
>>
>> Constant time with a painful amount of overhead, thus prompting the
>> requests for a "proper" switch statement. :P
>>
>> /s/ Adam
>>
>
> If by painful overhead you mean all the typing, I’m not sure there is that much difference .. a few “function() .. end” brackets around code instead of “case …” statements.
>
> If you mean the run-time overhead of setting up the table, this depends entirely on how often the table is used. If its only used once then yes, the overhead is probably greater than the constant time function lookup and call. But jump table style switch statements and lookup tables are inherently a performance optimization that is only really of benefit if the switch/table is used multiple times (e.g. in a loop), so in that more typical case the setup time for the table is easily amortized over the multiple invocations.
>
> And a switch style jump table isn’t free either; it still has to be compiled. The compiler logic to inspect all the switch cases and optimize them as a jump table is non-trivial, thus making compiles slower and the compiler bigger. Given that many Lua apps are compiled once and then run once, all you are doing is moving “painful overhead” from run-time to compile-time.
>
> Further, compilers can generally only create jump tables for switch statements when the domain is very restricted. Say, for constant integer cases over a limited range that is densely populated. Whereas using a Lua table works for any domain and range of values.
>
> —Tim

My switch patch uses a Lua table to store the case values, it is a fairly trivial process, add a key to the table and set the value to the program counter offset of the jumpto point. I also check each jumpto point against each jumpto statement, however, I do not need to analyse the case values in any way, just add them to the table. I will note that each switch statement does require the use of a table, so there is extra resource usage there.

The advantage of the switch statement is twofold, nicer syntax than a table full of functions plus the ability to utilise fall-through. If you look through the Lua source you will see that fall-through is actually used a fair amount of times.

Compare the two code samples (first sample by Coda Highland):


local t
t = {
    'one' = function() stuff() t.two() end,
    'two' = function() otherstuff() end,
    'three' = function() morestuff() end,
    'four'  = function() yetmore() t.five() end,
    'five'  = function() otherthings() end,
}
t[var]()


switch var
    case one
      stuff()
    case two
      otherstuff()
      break
    case three
      morestuff()
      break
    case four
      yetmore()
    case five
      otherthings()
end


Which would you rather maintain? Personally, I find the syntax of the switch statement considerably easier to look at and mentally parse. Plus with the switch statement you also have the ability to use the `else` (aka `default`) block in case `var` is not in your switch. That would require additional code in the first example to handle.

Another detriment to using the table-of-functions method is that you are essentially creating a closure for each case value, should you be using this form of switch in a tight loop you have now added a closure call (or more to implement fall-through) to each iteration of the loop, whereas with a proper switch statement you only do a single table lookup for each iteration.

Here is the results of running the above code[1] in a tight loop a million times each, averaged over 5 runs:

>>>>> switch.lunia: 0.4462178s
>>>>> table.lunia: 0.9022026s

As you can see the switch is more efficient than the table-of-functions method. Granted, we are talking less than a second for a million iterations of a loop, however, when running Lua code in time-criticial situations[2] you typically want every performance gain you can get! ;)

~pmd

[1] Code was run on vanilla Lua codebase with only my switch patch[3] applied.

[2] For example, video games, or the person on this list who is running Lua code between individual video frames!

[3] https://github.com/FizzyPop/lua-patches/tree/master/joint-patches/jump-table%2Bif-shct%2Bcont-loop



Is it easy for you to compare this to plain old if-else?