Re: [PATCH] Jump Tables for Switch/Case and Computed Goto

[Paige DePol <lual@...>]

On May 5, 2014, at 9:11 PM, Hisham <h@hisham.hm> wrote:

> On 5 May 2014 22:26, Paige DePol <lual@serfnet.org> wrote:
>> I appreciate any and all feedback, I hope anyone using a custom Lua will try out this patch and let me know what they think of it! :)
> 
> Hi! Here's some feedback:
> 
> First, it took me a bit to realize that inside switch you're using
> `continue` to mean what is usually called fallthrough.

Yes, I do use `continue` to mean "jump to the next case block", but `continue` is not required by default and will either be used to explicitly jump to the next case, or to fallthrough when the `and break` modifier is used.


> Also, this seemed strange to me: "is also the default in most
> implementations of the switch/case expression" ← Is it really? I've
> only seen this behavior in C and languages that copy its switch
> construct verbatim (ie, languages with a syntax directly derived from
> C). In every other language with a switch/case/match
> statement/expression, fallthrough is not the default (and most often
> it's not even available).
> 
> https://en.wikipedia.org/wiki/Switch_statement#Fallthrough

I have revised the wording of that statement to be more in line with the facts, thank you! :)


>> "With this patch the if statement now has a new shortcut style:
>> 
>> if {cond} (goto {label}|jumpto {point}|break|continue|return [...])
>> 
>> With this form of the if statement no end statement is required, nor
>> are the else or elseif statements valid. The shorcut if statement was
>> developed for the jumpto statement, which can only reference jump
>> points within the same lexical block as the jumpto itself, however, I
>> quickly realised it was usable for other forms of flow control."
> 
> Interestingly, this instantly reminded me of AppleSoft BASIC for the
> Apple II. It also had two forms of IF: `IF exp THEN stmt` and `IF exp
> GOTO stmt`. I haven't thought about this structure in many, many...
> many years! :)

The main reason for this new form of `if` was to support `if {cond} jumpto {label}` as the jumpto statement can't be in a block by itself. However, I thought it would be very useful for other flow-control statements as well. Most of my formative years of coding were on Atari 8-bit systems, with the occasional Apple or Commodore 64 experience. How I loved my Atari computers! <3


> A curiosity: could you share with us what was your motivation for this
> jump-tables patch? Was it primarily to support switch-case? And also,
> what was the motivation for switch-case: syntax clarity or
> performance? (if the latter, some numbers would be nice). In my Lua
> years, I actually learned not to miss switch/case much (certainly not
> as much as I (still) miss continue (even with goto available)). I've
> never used computed goto's much so my brain is not even trained to
> think up algorithms using them. Some examples of use would be fun (I
> assume the tests don't make it justice).

When I first started hacking Lua I set a goal for myself to implement switch/case without just being syntactic sugar for chained if/else statements. I am working on creating my own variant of Lua, named Lunia, for a game engine I am also writing. I have always wanted to "create" a language, but never really had the time. Hacking Lua may not be creating my own language from scratch, but it sure is a lot of fun, and is teaching me a lot in the process!

As I worked on learning the internals of Lua I had a number of ideas for implementing switch/case, I even posted a patch a while ago here on the list which did not quite achieve the goal. However, eventually I realised that I could use a Table to store the constant values as keys with the jump point offsets as values. Once I had that working I quickly realised that essentially I had also created computed gotos, and added jump labels and the `jumpto` statement to support that.

If you check GitHub you will see a section titled Benchmarks, which shows the difference between chained `if/else` and `switch/case' statements. I will give you a summary: the switch command is faster than if/else, even when only 3 items are being chained in the if/else! A single if statement is obviously faster, however, a 2 item if/else vs switch/case is a photo finish!

I honestly do not have any direct code examples I can give you for computed goto, though an area they seem to be used is in VM engines... so I guess if someone wanted to write a VM engine, that runs on another VM engine, I have at least given them a performance boost over using if/else. ;)

Thank you very much for your feedback, it is very appreciated! :)

~pmd~