Resuscitating Lua couroutines

[vortizee]

I had an array of coroutines, which in my naïve way I created to parse database files (300,000 lines) of object information to be drawn. They ran without any attention, filling a temporary table until the parse was complete, at which time I could seamlessly replace the live table with the temp table and the process could be repeated when necessary… Or so I thought.

The first time I got them to work I was staggered by how fast and unnoticeable the process was. Boom, the objects appeared! Then I learned my second lesson on coroutines: They die. Okay, I thought after sulking for a night, Virtual Coroutines to the rescue. These functions just needed to return a value which could be passed back to itself when ‘resumed’ so that it knew where to continue from, or pass a flag of ‘parse completed; start from the beginning when called next time’. It worked. At least 150 X’s slower! And the code to call these virtuals to action is also a clunker because each must be called explicitly to pass values and check the ‘ended’ flag, whereas the original coroutines started with their own local values and ended by increasing the array number to run the next coroutine when complete. Instead of a simple: if map moved by distance d, coroutine.resume( findObjects[ kind_of_objects ] ), I needed 50 lines of code.

So, can I coerce Lua to reset the coroutine by wrapping it in a function? Would a reset coroutine use its starting locals? How would such a function pass the yield message back, and how do I resume it when it yields? I think I know how to speed up the virtual coroutines a bit, but I already have something that works fast and elegantly — just only once.

In pseudo code, the originals were like

Code: Select all

makeObjects[1] =  coroutine.create( function()
  local prev, last, counter, temp.table = get(first), get(last), 0, { }
  while not finished do
    (add objects to temp.table from database if kind=1 and location are okay)
    if item is last of its kind then
      finished = true 
    else update counter
      if counter = 100 then coroutine.yield() end
    end
  end
  if finished then
    populate live.table with temp.table
    destroy temp.table in case it will be shorter next time
    set next coroutine_sequence to 2 — another type of object from maybe another database
end end)

[Inny]

So here's one of those inconvenient truths about Lua coroutine, which again I love them so much, but they are strictly mutable. It sounds kind of like you want an immutable coroutine, so to speak, where you'd get returned an object from coroutine.resume that's the new state of the thread, so that the old state of the thread can be reused. This idea, which you called a virtual coroutine, is actually called a "Delimited Continuation" and is prominent in languages like Scala or Lisp. In Lua we don't have the kind of syntax that would make this easy.

However to get the effect you're looking for isn't that hard, if you're okay with a function that returns an object that contains functions. Or in Object-Oriented speak, a Factory that returns an Object that you'll call its Methods. This isn't too complex to make into a single function:

Code: Select all

function MakeObjectsFactory(inital_inputs)
  local function makeObjects()
    local that = {}
    that.some_inputs = initial_inputs
    function that:next()
      process(that.some_inputs)
    end
    return that
  end
  return makeObjects
end

But at this point Functional Programming is running amuck and you're better off pulling in middleclass and writing a normal class.

[airstruck]

Maybe I'm missing something here, but couldn't you just wrap most of the function body in an infinite loop?

I mean, instead of this:

Code: Select all

local coroutineThatDies = coroutine.create(function ()
    local finished = false
    while not finished do
        local result = doStuff()
        if result == something then
            finished = true
        else
            coroutine.yield(result)
        end
    end
    finishDoingStuff()
    -- I'm dying!
end)

Can't you do this?

Code: Select all

local coroutineThatLives = coroutine.create(function ()
    while true do
        local finished = false
        while not finished do
            local result = doStuff()
            if result == something then
                finished = true
            else
                coroutine.yield(result)
            end
        end
        finishDoingStuff()
        -- I'm not dying!
    end
end)

[vortizee]

What Inny says is beyond my level of understanding abstractions. But a coroutine that never dies needs to reset its starting point locals somehow. This sounds intuitively reasonable.

There’s a script-wide local keeping track of which coroutine# in the array of coroutines is active, so any coroutine could just reset its locals to the starting numbers and increment the coroutine# then yield instead of dying. When the next-next coroutine sets that coroutine# back to the first one (1), it just continues from the beginning. I’ve managed to whittle the performance penalty of just using functions to ‘almost tolerable’ but I’ll have to explore this idea to see if it can deliver the speed I need. That would also mean all four coroutines would be in a suspended state during most of the run. And why not? Anything that is not active is also in suspension.

Thanks for the idea and keeping the discussion down to my level. I’m going to read Inny’s idea a number of times until something sticks too. It makes more sense every time, but there’s a wall of understanding to be breached.

[vortizee]

Eternal is not as trivial as I thought, so I paused to think it over and came up with the below after abandoning hasty thoughts of multiple yields or potential resume dead ends.

Code: Select all

local coroutineThatLives[coNum] = coroutine.create( function ( )
	local count, start, prev, last = 0, 1, 1, dbase_last

	while true do
		local finished = false
		while not finished do

			local v = { get_data(prev) }
			prev = prev + 1				-- set for next resume
			cnt = cnt + 1				  -- yield counter
			if not v or prev > last then	
				finished = 2			   -- no more data or beyond last (a known ref)
			else
				if v[n] validates then
					table.insert ( temp, { v } )
				end
			end
            
			if cnt == 150 then			-- time to yield
				finished = true
			end
            
			if finished then				  -- time to yield or exit
				if finished == 2 then		-- should release data and die
					live = { }			     -- forget old data
					populate live table with temp table values in a loop of paranoia
					temp = { }			     -- ready to rebuild from scratch
					prev = start		      -- we start from here again
					coNum = coNum + 1	    -- next coroutine to call by controller
				end
				count = 0				      -- zero for next resume
				finished = false			  -- IS THIS THE MAGIC ??
				coroutine.yield()		    -- thread resumes after this
			end
		end
	end
end)

If so, the temp table need only live (be a local) in the coroutine, a minor bonus. If it works, it will be interesting to see the speed of execution. I’m not sure now what the while true does.

[zorg]

Technically, having more than one yield in a coroutine is not anything bad.

<code>

Okay so, let me try to edit your code a bit... also fill it up with questions in comments to things that aren't clear to me.

Code: Select all

local coroutineThatLives[coNum] = coroutine.create( function ( ) -- just an offhand question, but why do you need multiple coroutines? can't you load the data in with one?
	local count = 0
	local start = 1
	local prev = 1
	local last = dbase_last -- is this a global? why? just pass it in as a parameter.

	while true do -- coroutines "die" two ways, either they finish executing by return-ing, or error-ing. This would ensure than, with you yielding at least once inside, without return statements or errors (unless caught with pcall or xpcall), it will never end.
		local finished = false --the local declaration for this could be moved out of the infinite loop, less constant allocation, though it might not be that big of an issue.
		while not finished do -- This is what actually grinds your data; after this is done, since you wanted the coro to live, it will still run, it just won't do anything.

			local v = get_data(prev)
			prev = prev + 1				-- set for next resume <- what's exactly the purpose of this?
			cnt = cnt + 1				  -- yield counter <- this i can understand
			if not v or prev > last then	
				finished = 2			   -- no more data or beyond last (a known ref) <- why not true?
			else
				if v validates then
					table.insert ( temp, { v } ) -- why are you using a temp table?
				end
			end
            
			if cnt == 150 then			-- time to yield
				finished = true                   -- why not just call coroutine.yield() here (too) ?
			end
            
			if finished then				  -- time to yield or exit
				if finished == 2 then		-- should release data and die <- why not true?
					live = { }			     -- forget old data
					populate live table with temp table values in a loop of paranoia -- wat. why. :|
					temp = { }			     -- ready to rebuild from scratch
					prev = start		      -- we start from here again
					coNum = coNum + 1	    -- next coroutine to call by controller <- again, why more than one coro?
				end
				count = 0				      -- zero for next resume
				finished = false			  -- IS THIS THE MAGIC ?? <- you're already setting finished to false at the start of the infinite loop, that's kinda the point.
				coroutine.yield()		    -- thread resumes after this
			end
		end
	end
end)

If so, the temp table need only live (be a local) in the coroutine, a minor bonus. If it works, it will be interesting to see the speed of execution. I’m not sure now what the while true does.[/quote]

Now, you can pass parameters to and get results from the coroutine with the coroutine.resume call; that works in tandem with coroutine.yield inside a coroutine, just exactly the opposite way. Except for the first resume call that starts it, those will be passed as arguments to the function you define as a coroutine.

Also, i'm still not really sure what the purpose of all the parts is, to me, it looks horribly overengineered, and unless there are intricacies i'm not seeing/getting, i feel like a much simpler solution may exist. Elephant from a flea, really.

[vortizee]

Let me try to answer in sequence as I’m struggling with the limited size of the forum pages.
No, there are multiple databases to poll sequentially so it’s efficient to call any of them in one coroutine statement by index. As in coroutine.resume(getPieces)

dbase_last is a global localized to a table of firsts and lasts for each database at the start of the script, yes, and some of the databases continue beyond the ‘last’ ref to define other object types, so it’s a convenient way to find the end of the area of interest.

Yes, I see where the local finished = false could go outside that block. The get is actually pseudo code for calling some unknown c function that returns database values in a sequence. On resume, that’s the reference that gets me the next item values of the database.

finished = 2 tells me the coroutine ended: there is no more data of interest. I can now replace the live table with the temp table and “reset” the coroutine. finished = true tells me the coroutine needs to yield but not end nor update the live table nor reset the coNum to the next coroutine.

The temp table means I can draw stuff with the live table continuously while the temp table collects data in the background after a map has moved. So, it’s a way of disposing of old elements outside the map and adding new elements as the map origin changes.

I could call coroutine yield when finished = true but was afraid of multiple yields at the start. When finished = 2, the coroutine’s parse is complete. This is where the original coroutines died after passing their data to the live tables. The parsing will restart when called by a map move.

‘finished = false’ at that point resets the flag ‘finished’ for the resume after the yield else I fear the ‘while not finished’ will fail. It might be redundant. I’m using the same flag to tell me when to yield to the controller (after 150 polls = true), and when to pass the temp table to the live table, reset the coroutine index to the next coroutine, and yield (=2).

I pass the temp values to the live values in a loop of paranoia because if I set table.live = table.temp, then immediately table.temp = { }, I wonder if I have passed a reference that might cease to exist, rather than values that I expect to endure. Hence the paranoia. As in, if I have passed a reference and the garbageman empties the reference bin, have I lost the values? I’d rather write table.live = table.temp then table.temp = { } if you tell me table.live’s values are safe. Is that like some sort of deep copy?

The whole purpose is to update tables that draw various pieces every frame. The piece collection process parses large databases in the background as to their location, type and number (amongst much other stuff of no interest) using a reference number ‘prev’ that can be reset to a known ‘first’ ref and checked if beyond the ‘last’ known ref. It really should be called ‘next’. The only reason for its existence is to reset it to ‘first’ after it has completed ‘last’, otherwise it requires added complication. When each temp table has finished collecting values, its live table parent gets those values, losing all pieces that are now outside the map range and acquiring new ones that just appeared within map range. Testing the location of any piece with respect to a map that moves and rotates is expensive, and I hoped to keep things simple. I’m sure there are better methods.

The main controller function is the simplest possible. When coNum is not zero, coroutine.resume(getPieces[coNum]) else if the map has moved by some distance, coNum = 1. The last coroutine resets coNum to zero.

Now, you can pass parameters to and get results from the coroutine with the coroutine.resume call; that works in tandem with coroutine.yield inside a coroutine, just exactly the opposite way. Except for the first resume call that starts it, those will be passed as arguments to the function you define as a coroutine.

With that you’ve fried my brain and it’s two hours past bedtime. A big thanks for taking the time to respond and understand.

[vortizee]

After minor refinements and typo safaris, the coroutines are now immortal !! Speed is not much better than the virtual coroutines, but the controller is back to a few lines of code. Caching a function that is part of a local table of functions failed, as did caching a similar from an include/require utils script but I should be able to work those out and refine further.

Some issues were due to faulty understanding of how data was stored. The inputs from the hash table needed to be like w = splitSpaces( pcs.A ) but the inputs from the other methods required getting a table w = { getData ( prev ) }. From the latter, the comparison failed if w[1] == “25” but worked with if w[1] == 25, and I thought that Lua would’ve automatically handled those. At least I can skip a few tonumber() operations.

@airstruck, you nailed it! @zorg, thanks for clarifications and questions that helped.