python - Why list append and pop(0) faster than incrementing and decrementing front rear counters in queue?

Question

I have implemented push and pop functions in queue using following methods.

1. Initialise list as [], push:list.append(), pop:list.pop(0)
2. Initialise list as [None]*100,front=rear=0, push: list[rear]=item, rear++, pop: front++ (while incrementing front or rear, it is doing x = (x+1)%100).

I was expecting, the second approach will be faster, because pop in second approach just increments the front counter, and pop in first approach has to shift all list items to an index lower, e.g. from list1 to list[0], from list[2] to list1 etc.

But my experiment with timeit() shows the 1st approach is faster. Can anyone explain why?

code:

def initialiseQueue():
    global L,Ld,front,rear,size
    L=[None]*100
    Ld=[]
    front=0
    rear=0
    size = 100

def enqueue(x):
    global L, rear, size
    if (rear+1)%size==front: # full
        print("Queue is full. Can't add new item.")
        return 1
    else:
        L[rear] = x
        rear = (rear +1)%size
        return 0

def dequeue():
    global L, front,rear, size
    if front==rear:   #empty
        print("Queue is empty")
    else:
        x = L[front]
        front = (front + 1)%size
        return x

from random import *
def qDQ(m,n,way='default'):
    for _ in range(m):
        for i in range(n):
            x = randint(1,10)
            addToQueue(x,way)
        for i in range(n):
            removefromQueue(way)

def addToQueue(x,way):
    global L,Ld
    if way == 'default':
        Ld.append(x)
    else:
        enqueue(x)

def removefromQueue(way):
    global L,Ld
    if way == 'default':
        return Ld.pop(0)
    else:
        return dequeue()

from time import *
from timeit import *

m,n=input("Enter two integers separated with spaces:").split(" ")
m=int(m)
n=int(n)

a = timeit(stmt="qDQ(m,n,'default')",setup='initialiseQueue()',timer=process_time,number=10000, globals=globals())
b = timeit(stmt="qDQ(m,n,'special')",setup='initialiseQueue()',timer=process_time,number=10000, globals=globals())
print("Process time for add/remove from queue using list built-in functions:",a)
print("Process time for add/remove from queue using approach 2:",b)
print("Hence","approach 1" if a<b else "approach 2","is faster!")

Answer 1

Python is an interpreted language. It translates function execution into bytecodes for its "virtual machine".

Your enqueue function translates to the following operations:

>>> import dis #Python disassembler from std lib
>>> dis.dis(enqueue)
  3           0 LOAD_GLOBAL              0 (rear)
              2 LOAD_CONST               1 (1)
              4 BINARY_ADD
              6 LOAD_GLOBAL              1 (size)
              8 BINARY_MODULO
             10 LOAD_GLOBAL              2 (front)
             12 COMPARE_OP               2 (==)
             14 POP_JUMP_IF_FALSE       28

  4          16 LOAD_GLOBAL              3 (print)
             18 LOAD_CONST               2 ("Queue is full. Can't add new item.")
             20 CALL_FUNCTION            1
             22 POP_TOP

  5          24 LOAD_CONST               1 (1)
             26 RETURN_VALUE

  7     >>   28 LOAD_FAST                0 (x)
             30 LOAD_GLOBAL              4 (L)
             32 LOAD_GLOBAL              0 (rear)
             34 STORE_SUBSCR

  8          36 LOAD_GLOBAL              0 (rear)
             38 LOAD_CONST               1 (1)
             40 BINARY_ADD
             42 LOAD_GLOBAL              1 (size)
             44 BINARY_MODULO
             46 STORE_GLOBAL             0 (rear)

  9          48 LOAD_CONST               3 (0)
             50 RETURN_VALUE
             52 LOAD_CONST               0 (None)
             54 RETURN_VALUE

whereas append is a builtin operation, highly optimized and coded in C (for CPython).

The same goes for pop.

I think this explains at least one reason why your code is much slower.

Optimisation is a difficult business, efficiency depends on many factors and there can be surprises at all levels so it is better to resist to premature optimization: only start looking at those details if you have a problem.

For comparison, here is the same disassembling for a function calling builtin append on a list:

>>> import dis
>>> def append(l, x):
...   l.append(x)
... 
>>> dis.dis(append)
  2           0 LOAD_FAST                0 (l)
              2 LOAD_METHOD              0 (append)
              4 LOAD_FAST                1 (x)
              6 CALL_METHOD              1
              8 POP_TOP
             10 LOAD_CONST               0 (None)
             12 RETURN_VALUE
>>> 

In fact it is just doing LOAD_METHOD and CALL_METHOD.