Understanding the instruction limit

I’m curious about what sort of thing causes a program to hit the instruction limit. In my utf8 code, I have an iterator function so that one can write:

for c in utf8_char(s) do
   -- something on the characters in s
end

to work through a string which is assumed to be encoded as utf8. The problem that I run into is that if the source string, s, has more than about 20 characters then I hit the instruction limit. Everything works fine if I split that string into pieces, so long as each piece is not more than about 20 characters. So something in the iterator seems to hit the limit. I’m curious as to what that could be.

The actual iterator code is quite simple:

function utf8_char(s)
    local i = 1
    if not s then
        s = ""
    end
    return function ()
        local a,l,d
        while true do
            c = string.sub(s,i,i)
            if c == "" then
                return nil
            end
            i = i + 1
            a = string.byte(c)
            if a < 127 then
                return a
            elseif a > 191 then
                -- first byte
                l = 1
                a = a - 192
                if a > 31 then
                    l = l + 1
                    a = a - 32
                    if a > 15 then
                        l = l + 1
                        a = a - 16
                    end
                end
                d = a
            else
                l = l - 1
                d = d * 64 + (a - 128)
                if l == 0 then
                    return d
                end
            end
        end
    end
end

It would be nice to be able to deal with strings of arbitrary length. If it can’t be done using an iterator, then I can think of a few ways to get round it, but this does have a certain elegance about it that it would be a shame to lose.

I tried doing a bit of pre-processing on the string in case it was the string.sub part. But that didn’t help at all.

I’m intellectually curious as well (knowing how the insides of things work is a good thing) - but as a practical matter, is there a problem with doing setInstructionLimit(0) and moving on? Or, alternatively, setting it then resetting it when you’re done?

Here’s what setInstructionLimit() does internally:

lua_sethook(L, &ExceedInstructionCountFunc, LUA_MASKCOUNT, kMaxInstructionCount);

This sets a hook on the Lua interpreter to call “ExceedInstructionCountFunc” after kMaxInstructionCount is reached.

Simeon: That translates to “This sets a hook on the Lua interpreter to call “Bandersnatch” after “Snark Island” is reached.”. Is this something that I can read about in the Lua documentation? I want to know what counts as an “Instruction” and how the fact that I split a string (and thus do the same operations but organised differently) affects the count.

Bortels: I don’t know if that would be okay - which is part of my problem; I assume that this is here for some reason and figure that if I’m hitting it and can refactor my code so as not to hit it then the refactored code will probably be better suited to Codea. It may be that the instruction count is computed on a per-cycle basis and that (roughly) the more instructions there are then the slower the cycle will take to compute. In that case, lowering the instruction count would be a good thing.

I imagine whenever the interpreter is about to execute an op-code. But the documentation is a bit vague on what counts as an instruction, see here:

http://pgl.yoyo.org/luai/i/lua_sethook

The count hook: is called after the interpreter executes every count instructions. (This event only happens while Lua is executing a Lua function.)

I had a look at the Lua source. It seems that the program counter’s value is used as the “instruction count” for the purposes of that hook. So the hook limits the number of op-codes.

It’s hard to say why it hits the limit when the string is not split.

I can see how this can be an issue for library code, where you generally don’t want to call setInstructionLimit(0). I wonder if a stack of instruction limits could be used, so the library could call pushInstructionLimit(0) → execute code that is known to work → popInstructionLimit().

Or perhaps, as Bortels says, we can drop the instruction limit from the run-time viewer and only enforce it during compile time (to ensure there are no massive loops in global scope).

Pardon my extreme ignorance, but what is an “op-code” in this context? (Searching gives me some general idea, but to understand what is really going on here then I need to know a bit more precisely.)

They are the low-level instructions that Lua uses to address its virtual machine. These are higher level than you would find on typical hardware (such as x86 or ARM) but a lot lower level than Lua code.

There’s an overview of the instructions here:
http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf

Generally these are thinks like MUL, SUB, ADD for arithmetic operations. LOAD* and MOVE to move values into registers. A virtual machine simulates a CPU in software. It provides a set of registers and operations that can be performed on those registers.

Lua translates high level Lua code into Lua op-codes then executes the code by running the ‘virtual machine.’

I haven’t implemented a virtual machine or compiler in a long time, but there is a paper on the implementation of Lua which goes into detail on its register-based virtual machine: http://www.lua.org/doc/jucs05.pdf

Hmm, I might find another way of implementing this. Maybe a utf8string class is called for that does tricky stuff internally to avoid iterators. I just tried:

function getstuff()
   local t = {"a","b","c", ... you get the idea }
   local i = 0
   local j = 0
   return function()
      if i == 26 then
          i = 0
          j = j + 1
          return j
      end
      i = i + 1
      return t[i]
   end
end

The idea being to see how many iterations I can do before hitting the instruction limit. My iPad is now refusing to talk to me.

What’s really bizarre is that I tried redoing the utf8 iterator basically as this. The outer function splits the string into a table and then the iterator simply returns the next value of the table. That still hit the instruction limit. The only real difference is that the utf8 iterator uses something like string.sub or string.gmatch. Are these “op-codes”?

Not exactly, string.sub and string.gmatch are implemented as C-functions that are called by the Lua interpreter. They probably get compiled into a sequence like OP_GETTABLE, OP_LOADK, OP_CALL. Their complexity wouldn’t count against the instruction limit, but there would be some small number of instructions used in order to call them, depending how you call them (i.e., whether you use the dot . operator or the colon : operator).

Anyway: I have now removed the instruction limit from run-time execution of the code. I have left it in for the initial code parsing, but that won’t effect your string manipulation. It will be changed in the update after 1.2.7, whenever Apple decides to let that out.

I’m not sure that I agree with removing the limit. I’d rather understand what it is in my code that is reaching that limit and figure out whether or not there is a better way to do it. What would be useful would be a way to get the current instruction number so that I can monitor it before it goes critical.

This doesn’t hit the limit for me with 200 chars. I’m on ipad2.

function utf8_char(s)
    local i = 1
    if not s then
        s = ""
    end
    return function ()
        local a,l,d
        while true do
            c = string.sub(s,i,i)
            if c == "" then
                return nil
            end
            i = i + 1
            a = string.byte(c)
            if a < 127 then
                return a
            elseif a > 191 then
                -- first byte
                l = 1
                a = a - 192
                if a > 31 then
                    l = l + 1
                    a = a - 32
                    if a > 15 then
                        l = l + 1
                        a = a - 16
                    end
                end
                d = a
            else
                l = l - 1
                d = d * 64 + (a - 128)
                if l == 0 then
                    return d
                end
            end
        end
    end
end

function setup()
    local aa = ""
    for i = 1,200 do aa = aa.."a" end
    for c in utf8_char(aa) do print(c) end
end

Looking at my code a bit more closely, I realised that although this was where the error was appearing, it was being called from another routine that was doing something quite complicated itself (line wrapping) and so the fact that it was this routine that threw the error is probably not significant.

However, I felt that that didn’t really matter to the main discussion which was about figuring out what contributes to the instruction limit and figuring out how to avoid it in general.

To see it “not work”, as it were, take a look at my cube project. See all those lines of instructions in the setup function? Try concatentating them.

The limit is there so “pathological” code (the classic example being an unintended endless loop) doesn’t hang Codea entirely. If you know your code is free of such issues - setting the value to 0 (which is “unlimited”) is not unreasonable.

I SUSPECT (this is all vague spine-hunch kinda stuff, but my spine is right more often than my brain) that the issue lies with Lua’s string handling. Strings are immutable, which means when you manipulate one, you end up creating new ones, and string manipulation that’s cheap in other languages can end up quite expensive - the classic case being appending to a string with ‘…’ (in your setup). I suspect in this case, the string manipulation in your function is being compounded by being called each time thru the iterator, and that something like string.sub is far more expensive than you’d reasonably suspect.

Try:

  1. replacing your setup loop with aa=“aaaaaaaaaaaaaaaaaaaaaaaa…” (ie. just assign it)
  2. converting the string to a table of characters (strings, really, but short), do the work with those.

@TLL: it would be kinda neat to expose the value of whatever internal variable is keeping count of instructions.

Could also do away with the instruction limit business altogether if you make the triple tap emergency exit interrupt running lua code (not sure if internally codea could do that but avoiding instruction limits altogether would simplify life for us)

Bortels, i’d have guessed that string manipulation is slow too, and probably it is, but it doesn’t seem to eat many instructions. In the code below the instruction limit needs to only increase linearly with the number of a’s (5 instructions per a to be precise)

function setup()
    setInstructionLimit(509)
    a = ""
    for i = 1,100 do a = a.."a" end
end

See other thread - I suspect that chunks of Codea itself are written in Lua, so an extra-Lua escape hatch may be more difficult than it seems. I’m sure if it’s easy TLL will see this and say “yep” and add that soon. :slight_smile:

re. string manipulation - not slow, and not expensive in opcodes - but actual work may not match # of opcodes represented.

The classic example is “a = a … ‘a’”. This doesn’t modify the “a” string. it makes a new string, and points a to it (and the old string is garbage collected at some point). if you do that in a big loop. you get memory filled with an “a” string, an “aa” string, an “aaa” string, and so on. All that memory has to be allocated, tracked, and garbage collected. So - 2 opcodes could mean copying megabytes of memory in a bad case, and tons of garbage collection, and be computationally expensive even if the opcode count is small.

See http://lua-users.org/wiki/ImmutableObjects - notably, “Lua strings are immutable and interned. This has some implications [4]. To create a string that differs in only one-character from an existing 100 MB string requires creating an entirely new 100 MB string since the original string cannot be modified.”

To that I would add that even if you work with small strings, a constant churn can create many, many objects that need garbage collection. If you want to work with things that will change a lot - tables are your friend.

If any one is still interested to know what opcodes are, there is an article on http://howto.oz-apps.com/2012/04/lua-riff-source-code-and-bytecode.html and the other best way is to write the lua code in a text file (on the desktop) run luac which will compile this text file into bytecode, this file now contains the opcodes. Strangely there are only about 35-37 opcodes in Lua 5.1 and with these, it can provide such a rich experience.

String handling in lua can be tricky, I wrote about that in another thread, but that has nothing to do with the number of instructions executed. That is really the amount of instructions the VM executes, so even if it means copying around tons of megabytes, one VM instruction only counts as one instruction towards the limit.

If you have a standalone lua installation of some “real” PC, you can see the generated opcodes by putting your script through “luac -l”. Basically, sth like

a=a.."a"

translates to four opcodes, regardless of how long the strings are. The problem at hand is more likely caused, as @Andrew_Stacey wrote, by some surrounding code that does a lot of stuff.

Regarding string concatenation, there are a few tricks. For one, the internal implementation of the concat operator can handle an arbitrary number of arguments. This means that if you concatenate a lot of strings in one statement, like so:

a="a".."b".."c".."d".."e" -- ... and so on

it is still translated to only one call to the internal concat operator! Together with the implementation of this operator, this makes for a lot more speed and a lot less garbage when concatenating strings that stitching them together one by one. The other thing to do, especially when building large strings from pieces, is to use tables as string buffers, meaning adding the strings to be concatenated to a table and then calling table.concat on this table. Also, for some cases string.format may be the tool of choice.

Luas strings are not really that much slower than in languages with mutable strings. you just need to know how to handle them. Btw. one thing you get from the immutability of luas strings and from the fact that they are interned is that each string, seen as an individual sequence of bytes, is stored exactly once in the interpreter. The upshot of this being that a string compare, regardless of how long the strings are, boils down to a comparison of the pointers to the strings. Which obviously is as fast as it gets :slight_smile:

Btw I am also in favor of leaving the limit in by default.