results.txt

luamarca $ ./run_benchmark.sh bench/sort-fedin.lua 1e5

Results:

luajit -O
-------------------------------------------------------------------
                name |     rel | abs s / iter = us (1e-6 s) / iter
-------------------------------------------------------------------
 bubble_nocallback_s |  1.0000 |   0.51 /     100000 = 5.100000 us
   bubble_nocallback |  1.0000 |   0.51 /     100000 = 5.100000 us
     bubble_callback |  1.2157 |   0.62 /     100000 = 6.200000 us
   bubble_callback_s |  1.2157 |   0.62 /     100000 = 6.200000 us
bubble_idxcallback_s |  1.4314 |   0.73 /     100000 = 7.300000 us
  bubble_idxcallback |  1.5294 |   0.78 /     100000 = 7.800000 us
    tsort_nocallback |  6.0196 |   3.07 /     100000 = 30.700000 us
  tsort_nocallback_s |  6.1569 |   3.14 /     100000 = 31.400000 us
      tsort_callback | 13.1176 |   6.69 /     100000 = 66.900000 us
    tsort_callback_s | 13.1373 |   6.70 /     100000 = 67.000000 us
   tsort_idxcallback | 14.1176 |   7.20 /     100000 = 72.000000 us
 tsort_idxcallback_s | 14.2549 |   7.27 /     100000 = 72.700000 us

lua
-------------------------------------------------------------------
                name |     rel | abs s / iter = us (1e-6 s) / iter
-------------------------------------------------------------------
 bubble_nocallback_s |  1.0000 |   5.16 /     100000 = 51.600000 us
   bubble_nocallback |  1.0271 |   5.30 /     100000 = 53.000000 us
     bubble_callback |  1.2016 |   6.20 /     100000 = 62.000000 us
   bubble_callback_s |  1.2345 |   6.37 /     100000 = 63.700000 us
bubble_idxcallback_s |  1.4864 |   7.67 /     100000 = 76.700000 us
  bubble_idxcallback |  1.5019 |   7.75 /     100000 = 77.500000 us
  tsort_nocallback_s |  1.5717 |   8.11 /     100000 = 81.100000 us
    tsort_nocallback |  1.6143 |   8.33 /     100000 = 83.300000 us
    tsort_callback_s |  3.2558 |  16.80 /     100000 = 168.000000 us
      tsort_callback |  3.2888 |  16.97 /     100000 = 169.700000 us
   tsort_idxcallback |  4.1318 |  21.32 /     100000 = 213.200000 us
 tsort_idxcallback_s |  4.2442 |  21.90 /     100000 = 219.000000 us

luajit2
-------------------------------------------------------------------
                name |     rel | abs s / iter = us (1e-6 s) / iter
-------------------------------------------------------------------
     bubble_callback |  1.0000 |   0.89 /     100000 = 8.900000 us
   bubble_nocallback |  1.0562 |   0.94 /     100000 = 9.400000 us
   bubble_callback_s |  1.0674 |   0.95 /     100000 = 9.500000 us
 bubble_nocallback_s |  1.0899 |   0.97 /     100000 = 9.700000 us
  bubble_idxcallback |  1.1124 |   0.99 /     100000 = 9.900000 us
bubble_idxcallback_s |  1.2360 |   1.10 /     100000 = 11.000000 us
    tsort_nocallback |  4.1348 |   3.68 /     100000 = 36.800000 us
  tsort_nocallback_s |  4.3146 |   3.84 /     100000 = 38.400000 us
      tsort_callback |  7.5618 |   6.73 /     100000 = 67.300000 us
    tsort_callback_s |  7.7079 |   6.86 /     100000 = 68.600000 us
 tsort_idxcallback_s |  8.8202 |   7.85 /     100000 = 78.500000 us
   tsort_idxcallback |  8.9663 |   7.98 /     100000 = 79.800000 us

sort-fedin.lua

local pairs, assert, print = pairs, assert, print
local table_sort = table.sort
local math_random, math_randomseed = math.random, math.randomseed

--------------------------------------------------------------------------------

math_randomseed(12345)

--------------------------------------------------------------------------------

local generate_data = function()
  return
  {
    006.635; 009.210; 011.345; 013.277; 015.086; 016.812; 018.475; 020.090;
    021.666; 023.209; 024.725; 026.217; 027.688; 029.141; 030.578; 032.000;
    033.409; 034.805; 036.191; 037.566; 038.932; 040.289; 041.638; 042.980;
    044.314; 045.642; 046.963; 048.278; 049.588; 050.892; 052.191; 053.486;
    054.776; 056.061; 057.342; 058.619; 059.893; 061.162; 062.428; 063.691;
    064.950; 066.206; 067.459; 068.710; 069.957; 071.201; 072.443; 073.683;
    074.919; 076.154; 077.386; 078.616; 079.843; 081.069; 082.292; 083.513;
    084.733; 085.950; 087.166; 088.379; 089.591; 090.802; 092.010; 093.217;
    094.422; 095.626; 096.828; 098.028; 099.228; 100.425; 101.621; 102.816;
    104.010; 105.202; 106.393; 107.583; 108.771; 109.958; 111.144; 112.329;
    113.512; 114.695; 115.876; 117.057; 118.236; 119.414; 120.591; 121.767;
    122.942; 124.116; 125.289; 126.462; 127.633; 128.803; 129.973; 131.141;
    132.309; 133.476; 134.642;
  }
end

local f_bubble_sort = function(t, b)
  for i = 2, #t do
    local b_switched = false
    for j = #t, i, -1 do
      if
        b ~= nil
      then
        if
          b(t[j], t[j - 1])
        then
          t[j], t[j - 1] = t[j - 1], t[j]
          b_switched = true
        end
      else
        if
          t[j] < t[j - 1]
        then
          t[j], t[j - 1] = t[j - 1], t[j]
          b_switched = true
        end
      end
    end
    if b_switched == false then
      return
    end
  end
  return
end

local process = function(t)
  local r = { }
  for i = 1, #t do
    r[i] = { "string", t[i] }
  end
  return r
end

local permute = function(tab, n, count)
  n = n or #tab
  count = count or n

  for i = 1, count do
    local j = math_random(i, n)
    tab[i], tab[j] = tab[j], tab[i]
  end

  return tab
end

local less = function(lhs, rhs)
  return lhs < rhs
end

local less_idx = function(lhs, rhs)
  return lhs[2] < rhs[2]
end

local tequals = function(lhs, rhs)
  for k, v in pairs(lhs) do
    if v ~= rhs[k] then
      return false
    end
  end

  for k, v in pairs(rhs) do
    if lhs[k] == nil then
      return false
    end
  end

  return true
end

local tequals_idx = function(lhs, rhs)
  for k, v in pairs(lhs) do
    if v[2] ~= rhs[k][2] then
      return false
    end
  end

  for k, v in pairs(rhs) do
    if lhs[k] == nil then
      return false
    end
  end

  return true
end

--------------------------------------------------------------------------------

local sorted = generate_data()
local sorted_processed = process(generate_data())

--------------------------------------------------------------------------------

local bench = { }

--------------------------------------------------------------------------------

do
  local t_hi_critical_l = generate_data()
  bench.tsort_nocallback = function()
    table_sort(t_hi_critical_l)
    assert(tequals(t_hi_critical_l, sorted))
  end
end

do
  local t_hi_critical_l = generate_data()
  bench.tsort_callback = function()
    table_sort(t_hi_critical_l, less)
    assert(tequals(t_hi_critical_l, sorted))
  end
end

do
  local t_hi_critical_i = process(generate_data())
  bench.tsort_idxcallback = function()
    table_sort(t_hi_critical_i, less_idx)
    assert(tequals_idx(t_hi_critical_i, sorted_processed))
  end
end

--[[
    for i = 1, #sorted do
      print(i, t_hi_critical_i[i], sorted[i])
    end
--]]
--------------------------------------------------------------------------------

do
  local t_hi_critical_l = generate_data()
  bench.bubble_nocallback = function()
    f_bubble_sort(t_hi_critical_l)
    assert(tequals(t_hi_critical_l, sorted))
  end
end

do
  local t_hi_critical_l = generate_data()
  bench.bubble_callback = function()
    f_bubble_sort(t_hi_critical_l, less)
    assert(tequals(t_hi_critical_l, sorted))
  end
end

do
  local t_hi_critical_i = process(generate_data())
  bench.bubble_idxcallback = function()
    f_bubble_sort(t_hi_critical_i, less_idx)
    assert(tequals_idx(t_hi_critical_i, sorted_processed))
  end
end

--------------------------------------------------------------------------------

do
  local t_hi_critical_l_shuffled = permute(generate_data())
  bench.tsort_nocallback_s = function()
    table_sort(t_hi_critical_l_shuffled)
    assert(tequals(t_hi_critical_l_shuffled, sorted))
  end
end

do
  local t_hi_critical_l_shuffled = permute(generate_data())
  bench.tsort_callback_s = function()
    table_sort(t_hi_critical_l_shuffled, less)
    assert(tequals(t_hi_critical_l_shuffled, sorted))
  end
end

do
  local t_hi_critical_i_shuffled = process(permute(generate_data()))
  bench.tsort_idxcallback_s = function()
    table_sort(t_hi_critical_i_shuffled, less_idx)
    assert(tequals_idx(t_hi_critical_i_shuffled, sorted_processed))
  end
end

--------------------------------------------------------------------------------

do
  local t_hi_critical_l_shuffled = permute(generate_data())
  bench.bubble_nocallback_s = function()
    f_bubble_sort(t_hi_critical_l_shuffled)
    assert(tequals(t_hi_critical_l_shuffled, sorted))
  end
end

do
  local t_hi_critical_l_shuffled = permute(generate_data())
  bench.bubble_callback_s = function()
    f_bubble_sort(t_hi_critical_l_shuffled, less)
    assert(tequals(t_hi_critical_l_shuffled, sorted))
  end
end

do
  local t_hi_critical_i_shuffled = process(permute(generate_data()))
  bench.bubble_idxcallback_s = function()
    f_bubble_sort(t_hi_critical_i_shuffled, less_idx)
    assert(tequals_idx(t_hi_critical_i_shuffled, sorted_processed))
  end
end

--------------------------------------------------------------------------------

return bench