Fast queue module

Resources Community Resources
#1

I made this simple queue module:

local Queue = {}
Queue.__index = Queue

function Queue.new()
	return setmetatable({ _a = 1, _b = 1 }, Queue)
end

function Queue:size()
	return self._b - self._a
end

function Queue:push(val)
	self[self._b] = val
	self._b += 1
end

function Queue:pop()
	local val = self[self._a]
	self[self._a] = nil
	self._a += 1
	return val
end

return Queue

To test it out I made a simple script that performs 100000 push and 100000 pop operations. Here are the results:
Using table: 1.2s
Using queue: 9ms

1 Like
#2

Interesting results, I would like to see the code for the benchmarks.

#4

Yes, of course:

local x = 100000

local s = tick()
local t = {}
for i = 1, x do
	table.insert(t, i)
end
for i = 1, x do
	table.remove(t, 1)
end
print("Using table", tick() - s)

s = tick()
local q = Queue.new()
for i = 1, x do
	q:push(i)
end
for i = 1, x do
	q:pop()
end
print("Using Queue", tick() - s)
#5

I mean it is a very simple utility module and it is faster than table.insert/remove queue implementation.

#6

Your benchmark code is not correct, table.remove(t, 1) will shift every element in the array down by 1 to fill the gap of the removed element this does not match the behavior of the :pop() method which just leaves holes in the array. You should also use os.clock() instead of tick() for any benchmarks.

Here are the results once you correct for this issue:

image
image1632Ă—841 70.9 KB

Source code 
--[[
This file is for use by Benchmarker (https://boatbomber.itch.io/benchmarker)

|WARNING| THIS RUNS IN YOUR REAL ENVIRONMENT. |WARNING|
--]]

local Queue = {}
Queue.__index = Queue

function Queue.new()
	return setmetatable({ _a = 1, _b = 1 }, Queue)
end

function Queue:size()
	return self._b - self._a
end

function Queue:push(val)
	self[self._b] = val
	self._b += 1
end

function Queue:pop()
	local val = self[self._a]
	self[self._a] = nil
	self._a += 1
	return val
end

local Samples = 10_000
local Array = {}
local Object = Queue.new()

return {
	ParameterGenerator = function()
		return
	end,

	Functions = {
		["table.insert"] = function(Profiler) 
			for Index = 1, Samples do
				table.insert(Array, Index)
			end
		end,

		["table.remove"] = function(Profiler) 
			for Index = 1, Samples do
				local Element = Array[Index]
				Array[Index] = nil
			end
		end,
		
		["Queue Push"] = function(Profiler) 
			for Index = 1, Samples do
				Object:push(Index)
			end
		end,

		["Queue Pop"] = function(Profiler) 
			for Index = 1, Samples do
				local Element = Object:pop()
			end
		end,
	},
}
5 Likes
#7

Thank you for your response. Yes, it looks like my “fast” queue module isn’t fast XD.
But can you please explain why is OOP slower than just using the same code without wrapping it in a method?

#8

Because metatables, you’re simply doing extra work trying to find the method being called.

2 Likes
#9

Well, makes sense why tables took so long. Try with table.remove(q) only (which is identical to pop!), it went from being ~135 times slower to being 4 times faster :).

@Ax3nx I just saw your response, said exactly what I wanted! Just read the slight edit I have here.