linda performance improvement

slightly improve linda performance when the producer/consumer scenario
leaves leave the key empty

3 files changed, 66 insertions, 81 deletions

diff --git a/CHANGES b/CHANGES
index d1c4913..c2b14ed 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,5 +1,8 @@
 CHANGES:
 
+CHANGE 93: BGe 20-Jan-14
+   * slightly improve linda performance when the producer/consumer scenario leaves leave the key empty
+
 CHANGE 92: BGe 20-Jan-14
    * version 3.8.1
    * new function lane:get_debug_threadname()
diff --git a/src/keeper.c b/src/keeper.c
index b0db8b4..1a696aa 100644
--- a/src/keeper.c
+++ b/src/keeper.c
@@ -127,14 +127,14 @@ static void fifo_peek( lua_State* L, keeper_fifo* fifo, int count_)
 
 // in: fifo
 // out: remove the fifo from the stack, push as many items as required on the stack (function assumes they exist in sufficient number)
-static void fifo_pop( lua_State* L, keeper_fifo* fifo, int _count)
+static void fifo_pop( lua_State* L, keeper_fifo* fifo, int count_)
 {
         int fifo_idx = lua_gettop( L);           // ... fifo
         int i;
         // each iteration pushes a value on the stack!
-        STACK_GROW( L, _count + 2);
+        STACK_GROW( L, count_ + 2);
         // skip first item, we will push it last
-        for( i = 1; i < _count; ++ i)
+        for( i = 1; i < count_; ++ i)
         {
                 int const at = fifo->first + i;
                 // push item on the stack
@@ -151,8 +151,12 @@ static void fifo_pop( lua_State* L, keeper_fifo* fifo, int _count)
                 lua_rawseti( L, fifo_idx, at);         // ... fifo vals val
                 lua_replace( L, fifo_idx);             // ... vals
         }
-        fifo->first += _count;
-        fifo->count -= _count;
+        {
+                // avoid ever-growing indexes by resetting each time we detect the fifo is empty
+                int const new_count = fifo->count - count_;
+                fifo->first = (new_count == 0) ? 1 : (fifo->first + count_);
+                fifo->count = new_count;
+        }
 }
 
 // in: linda_ud expected at *absolute* stack slot idx
diff --git a/tests/linda_perf.lua b/tests/linda_perf.lua
index 9348f71..1d92c8e 100644
--- a/tests/linda_perf.lua
+++ b/tests/linda_perf.lua
@@ -6,7 +6,9 @@ local table_unpack = unpack or table.unpack
 
 -- this lane eats items in the linda one by one
 local eater = function( l, loop)
-        local key, val = l:receive( "go")
+        -- wait for start signal
+        l:receive( "go")
+        -- eat data one by one
         for i = 1, loop do
                 local val, key = l:receive( "key")
                 --print( val)
@@ -18,7 +20,9 @@ end
 
 -- this lane eats items in the linda in batches
 local batched = function( l, loop, batch)
-        local key, val = l:receive( "go")
+        -- wait for start signal
+        l:receive( "go")
+        -- eat data in batches
         for i = 1, loop/batch do
                 l:receive( l.batched, "key", batch)
         end
@@ -30,6 +34,7 @@ end
 local lane_eater_gen = lanes.gen( "*", eater)
 local lane_batched_gen = lanes.gen( "*", batched)
 
+-- main thread writes data while a lane reads it
 local function ziva( preloop, loop, batch)
         -- prefill the linda a bit to increase fifo stress
         local top = math.max( preloop, loop)
@@ -38,8 +43,8 @@ local function ziva( preloop, loop, batch)
         for i = 1, preloop do
                 l:send( "key", i)
         end
-        print( l:count( "key"))
-        if batch then
+        print( "stored " .. l:count( "key") .. " items in the linda before starting consumer lane")
+        if batch > 0 then
                 if l.batched then
                         lane = lane_batched_gen( l, top, batch)
                 else
@@ -49,12 +54,21 @@ local function ziva( preloop, loop, batch)
         else
                 lane = lane_eater_gen( l, top)
         end
-        -- tell the lanes they can start eating data
-        l:send("go", "go")
+        -- tell the consumer lane it can start eating data
+        l:send( "go", true)
         -- send the remainder of the elements while they are consumed
+        -- create a function that can send several values in one shot
+        batch = math.max( batch, 1)
+        local batch_values = {}
+        for i = 1, batch do
+                table.insert( batch_values, i)
+        end
+        local batch_send = function()
+                l:send( "key", table_unpack( batch_values))
+        end
         if loop > preloop then
-                for i = preloop + 1, loop do
-                        l:send( "key", i)
+                for i = preloop + 1, loop, batch do
+                        batch_send()
                 end
         end
         l:send( "done" ,"are you happy?")
@@ -62,33 +76,25 @@ local function ziva( preloop, loop, batch)
         return lanes.now_secs() - t1
 end
 
-local tests =
+local tests1 =
 {
-        --[[{ 2000000, 0},
-        { 3000000, 0},
-        { 4000000, 0},
-        { 5000000, 0},
-        { 6000000, 0},]]
-        --[[{ 1000000, 2000000},
-        { 2000000, 3000000},
-        { 3000000, 4000000},
-        { 4000000, 5000000},
-        { 5000000, 6000000},]]
-        --[[{ 4000000, 0},
-        { 4000000, 0, 1},
-        { 4000000, 0, 2},
-        { 4000000, 0, 3},
-        { 4000000, 0, 5},
-        { 4000000, 0, 8},
-        { 4000000, 0, 13},
-        { 4000000, 0, 21},
-        { 4000000, 0, 44},]]
+        --[[
+        { 10000, 2000000, 0},
+        { 10000, 2000000, 1},
+        { 10000, 2000000, 2},
+        { 10000, 2000000, 3},
+        { 10000, 2000000, 5},
+        { 10000, 2000000, 8},
+        { 10000, 2000000, 13},
+        { 10000, 2000000, 21},
+        { 10000, 2000000, 44},
+        --]]
 }
-print "tests #1"
-for k, v in pairs( tests) do
+print "############################################\ntests #1"
+for k, v in pairs( tests1) do
         local pre, loop, batch = v[1], v[2], v[3]
         print( "testing", pre, loop, batch)
-        print( pre, loop, batch, "duration = " .. ziva( pre, loop, batch))
+        print( pre, loop, batch, "duration = " .. ziva( pre, loop, batch) .. "\n")
 end
 
 --[[
@@ -124,6 +130,7 @@ end
         ziva( 4000000, 0, 44) -> 2s
 ]]
 
+-- sequential write/read (no parallelization involved)
 local function ziva2( preloop, loop, batch)
         local l = lanes.linda()
         -- prefill the linda a bit to increase fifo stress
@@ -154,6 +161,7 @@ local function ziva2( preloop, loop, batch)
         for i = 1, preloop, step do
                 batch_send()
         end
+        print( "stored " .. (l:count( "key") or 0) .. " items in the linda before starting consumer lane")
         -- loop that alternatively sends and reads data off the linda
         if loop > preloop then
                 for i = preloop + 1, loop, step do
@@ -170,16 +178,8 @@ end
 
 local tests2 =
 {
-        --[[{ 2000000, 0},
-        { 3000000, 0},
-        { 4000000, 0},
-        { 5000000, 0},
-        { 6000000, 0},
-        { 1000000, 2000000},
-        { 2000000, 3000000},
-        { 3000000, 4000000},
-        { 4000000, 5000000},
-        { 5000000, 6000000},]]
+        -- prefill, then consume everything
+        --[[
         { 4000000, 0},
         { 4000000, 0, 1},
         { 4000000, 0, 2},
@@ -189,44 +189,22 @@ local tests2 =
         { 4000000, 0, 13},
         { 4000000, 0, 21},
         { 4000000, 0, 44},
+        --]]
+        -- alternatively fill and consume
+        { 0, 4000000},
+        { 0, 4000000, 1},
+        { 0, 4000000, 2},
+        { 0, 4000000, 3},
+        { 0, 4000000, 5},
+        { 0, 4000000, 8},
+        { 0, 4000000, 13},
+        { 0, 4000000, 21},
+        { 0, 4000000, 44},
 }
 
-print "tests #2"
+print "\n############################################\ntests #2"
 for k, v in pairs( tests2) do
         local pre, loop, batch = v[1], v[2], v[3]
         print( "testing", pre, loop, batch)
-        print( pre, loop, batch, "duration = " .. ziva2( pre, loop, batch))
+        print( pre, loop, batch, "duration = " .. ziva2( pre, loop, batch) .. "\n")
 end
-
---[[
-        V 2.1.0:
-        ziva( 20000, 0) -> 3s           ziva( 10000, 20000) -> 3s
-        ziva( 30000, 0) -> 8s     ziva( 20000, 30000) -> 7s
-        ziva( 40000, 0) -> 15s    ziva( 30000, 40000) -> 14s
-        ziva( 50000, 0) -> 24s    ziva( 40000, 50000) -> 22s
-        ziva( 60000, 0) -> 34s    ziva( 50000, 60000) -> 33s
-
-        SIMPLIFIED:
-        ziva( 20000, 0) -> 4s           ziva( 10000, 20000) -> 3s
-        ziva( 30000, 0) -> 8s     ziva( 20000, 30000) -> 7s
-        ziva( 40000, 0) -> 14s    ziva( 30000, 40000) -> 14s
-        ziva( 50000, 0) -> 23s    ziva( 40000, 50000) -> 22s
-        ziva( 60000, 0) -> 33s    ziva( 50000, 60000) -> 32s
-
-        FIFO:
-        ziva( 2000000, 0) -> 9s   ziva( 1000000, 2000000) -> 14s
-        ziva( 3000000, 0) -> 14s  ziva( 2000000, 3000000) -> 23s
-        ziva( 4000000, 0) -> 19s  ziva( 3000000, 4000000) -> 23s
-        ziva( 5000000, 0) -> 24s  ziva( 4000000, 5000000) -> 32s
-        ziva( 6000000, 0) -> 29s  ziva( 5000000, 6000000) -> 33s
-
-        FIFO BATCHED:
-        ziva( 4000000, 0, 1)  -> 19s
-        ziva( 4000000, 0, 2)  -> 11s
-        ziva( 4000000, 0, 3)  -> s
-        ziva( 4000000, 0, 5)  -> s
-        ziva( 4000000, 0, 8)  -> s
-        ziva( 4000000, 0, 13) -> s
-        ziva( 4000000, 0, 21) -> s
-        ziva( 4000000, 0, 44) -> s
-]]