bench 4 facepunch/garrysmod pr #2032

sortedpairs-bench.lua

local function getKeys( tbl )

	local keys = {}

	for k in pairs( tbl ) do
		table.insert( keys, k )
	end

	return keys

end

-- brandonsturgeon's 
function SortedPairs2( pTable, Desc )

	local keys = getKeys( pTable )

	if ( Desc ) then
		table.sort( keys, function( a, b )
			return a > b
		end )
	else
		table.sort( keys, function( a, b )
			return a < b
		end )
	end

	local i, key
	return function()
		i, key = next( keys, i )
		return key, pTable[key]
	end

end

-- without next
function SortedPairs3( pTable, Desc )

	local keys = getKeys( pTable )

	if ( Desc ) then
		table.sort( keys, function( a, b )
			return a > b
		end )
	else
		table.sort( keys, function( a, b )
			return a < b
		end )
	end

	local i, key = 1
	return function()
		key, i = keys[ i ], i + 1
		return key, pTable[ key ]
	end

end

-- without next & table.insert
local function getKeys2( tbl )

	local keys = {}

	for k in pairs( tbl ) do
		keys[ #keys + 1 ] = k
	end

	return keys

end

function SortedPairs4( pTable, Desc )

	local keys = getKeys2( pTable )

	if ( Desc ) then
		table.sort( keys, function( a, b )
			return a > b
		end )
	else
		table.sort( keys, function( a, b )
			return a < b
		end )
	end

	local i, key = 1
	return function()
		key, i = keys[ i ], i + 1
		return key, pTable[ key ]
	end

end



local newBenchmark

do
	local function sum(tbl)
		local out = 0

		for i = 1, #tbl do
			out = out + tbl[i]
		end

		return out
	end

	local function avg(tbl)
		return sum(tbl) / #tbl
	end

	local function median(tbl)
		table.sort(tbl)
		return #tbl % 2 == 0 && (tbl[#tbl * .5] + tbl[(#tbl * .5) + 1]) * .5 || tbl[math.ceil(#tbl * .5)]
	end

	local clock = os.clock
	local function bench(func, times)
		local start = clock()

		for i = 1, times do
			func(i)
		end

		return clock() - start
	end

	local function diff(a, b)
		return math.Round(math.abs(a - b) / b * 100, 2)
	end

	local print_result = "\n\n%s:\n\tsum = %s\n\tavg = %s\n\tmedian = %s"
	local spacer = string.rep(" ", 4)
	local print_diff = "- compare with %q:\n".. spacer .."sum = %s%%\n".. spacer .."avg = %s%%\n".. spacer .."median = %s%%\n".. spacer

	function newBenchmark(times, rep, compare)
		local results = {}

		return function(name, run)
			-- w8 4 one tick, if you benchmarking in singleplayer - process may freeze forever without it
			-- also collect garbage to make results cleaner
			local co = coroutine.running()
			timer.Simple(0, function()
				collectgarbage()
				coroutine.resume(co)
			end)
			coroutine.yield()

			local bench_time = {}

			for i = 1, rep do
				bench_time[i] = bench(run, times)
			end

			local result = {sum = sum(bench_time), avg = avg(bench_time), median = median(bench_time)}
			print(print_result:format(name, result.sum, result.avg, result.median))

			if compare then
				for _, info in pairs(results) do
					print(print_diff:format(info.name, diff(result.sum, info.time.sum), diff(result.avg, info.time.avg), diff(result.median, info.time.median)))
				end

				results[#results + 1] = {name = name, time = result}
			end
		end
	end
end



local tbl = {
    f   =  6,
    i   =  2,
    kpz = 10,
    mb  =  5,
    nzg =  3,
    tn  =  9,
    u   =  4,
    wqg =  8,
    x   =  7,
    zbd =  1
}

coroutine.wrap(function()
	print(string.rep(" \n", 100))
	local bench = newBenchmark(1500, 300, true)

	bench("SortedPairs old", function()
		for k, v in SortedPairs(tbl, true) do

		end
	end)

	bench("SortedPairs new", function()
		for k, v in SortedPairs2(tbl, true) do

		end
	end)

	bench("SortedPairs new without next", function()
		for k, v in SortedPairs3(tbl, true) do

		end
	end)

	bench("SortedPairs new without next & table.insert", function()
		for k, v in SortedPairs4(tbl, true) do

		end
	end)
end)()