At some point I required a simple data structure that would server as a first-in-first-out queue. I could use the usual queue.Queue, but I didn’t need the threading locks it has. Not to mention that they decrease the performance quite significantly.

Enter deque

My best bet was deque from collections module. It does what I want and it’s presumably much faster than queue.Queue. There are some problems though, for me, at least; that made me write my own class.

Getting used to it.

I am used to get() and put() methods on queues and push() and pop() on stacks. Here, I want to use deque as a FIFO queue, but it uses append() and popleft() for the purposes I need. Not very intuitive, I may forget about it during intensive programming.

Overriding the names

Maybe I will not need that in practice, but since I want it to be a FIFO queue, I want getting from the left of the data structure to be more intuitive than getting from the right. So I started off by overriding the method names.

class simple_fifo_queue(deque):

	popright = deque.pop
	pop = deque.popleft

Now, getting the leftmost element is just pop(), which is convenient; and if I ever need to get an element from the right (which I won’t since I use it as a queue; but simply for the sake of leaving the original pop() intact), I can do it via popright().

I could do the same to assign get() as well. But I’ve decided to make it a bit move verbose and expanded, because I needed to solve yet another problem.

Empty behaviour

The queue module conveniently provides a queue.Empty exception, which is raised when you try to get() from a non-blocking Queue which has no elements in it. What does deque do in this situation? It raises IndexError! Neither intuitive nor verbose, to me. So I added my own to the class. For the sake of simplicity, my queue is non-blocking and always raises the exception when it is empty.

class simple_fifo_queue(deque):

	popright = deque.pop
	pop = deque.popleft

	class Empty(Exception):
		pass

	def get(self, *args, **kwargs):
		try:
			result = self.pop(*args, **kwargs)
		except IndexError:
			raise simple_fifo_queue.Empty
		return result

Simple enough. I could make it raise queue.Empty, but I felt like making my own exception specific to this very class.

Ok. One final problem.

Careful, don’t lose data!

The queue.Queue has maxsize argument that allows you to specify the maximum size of the queue, obviously; and if you add a message when the queue is full, the queue.Full exception will be raised.

Yet, deque behaves differently. It was maxlen, but when you add messages to a full queue, it does not raise any exceptions; it drops messages from the opposite side silently instead! This could be dangerous, because it can be easily forgotten during your workflow. We’ll do two things to circumvent that:

  • block maxlen entirely and show a warning if we provide it.
  • provide a max_length instead that will make the queue raise an exception when it is full.

So here’s the final code.

class simple_fifo_queue(deque):

	popright = deque.pop
	pop = deque.popleft

	class Empty(Exception):
		pass

	class Full(Exception):
		pass

	def __init__(self, *args, max_length=None, maxlen=None, **kwargs):
		self.max_length = max_length
		if maxlen is not None:
			logging.warning("Do not set `maxlen` in `simple_fifo_queue`, please! Use max_length instead!")
		super(simple_fifo_queue, self).__init__(*args, **kwargs)

	def get(self, *args, **kwargs):
		try:
			result = self.pop(*args, **kwargs)
		except IndexError:
			raise simple_fifo_queue.Empty
		return result

	def put(self, *args, **kwargs):
		if not self.max_length or len(self) < self.max_length:
			self.append(*args, **kwargs)
		else:
			raise simple_fifo_queue.Full

I can access queue size simply using the built-in len() function; I can check the overflow this way. Again, I made my own Full exception.

Performance benchmarks

The class is not complex at all. But let’s see how fast it can go. Let’s create two benchmark functions: one for our class, another for queue.Queue. All they do is put a million integers into queue and then get them all.

For queue.Queue:

from queue import Queue, Empty

def queue_adder():
    q = Queue()
    for _ in range(10**6):
        q.put(42)
    while True:
        try:
            a = q.get(block=False)
        except Empty:
            break

For simple_fifo_queue:

def simple_queue_adder():
    q = simple_fifo_queue()
    for _ in range(10**6):
        q.put(42)
    while True:
        try:
            a = q.get()
        except simple_fifo_queue.Empty:
            break

Result for queue.Queue:

6.7 s ± 408 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Result for simple_fifo_queue:

827 ms ± 106 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Eight times faster! Guess it was worth it. I didn’t try other types of data, but even being able to do it with elementary types is pretty cool already, if you ask me.

In conclusion.

It was just a simple recipe for a FIFO queue that you can tweak to your own needs. Python is a flexible language, it’s fun to customize stuff.

Thanks for tuning in! I’ll see you eventually.