Lists vs Queues for Stack Representation

Preamble

From the last post we recognized that deques offer a modicum of better performance when it came to appending (deques being 3 milliseconds faster than lists, for 100,000 appends). We’re exploring this further to see if deques offer any noticeably drastic increase in performance in comparison to lists, when it comes to representing a stack.

The typical analogy of a stack is thinking of the Pringles can. We can only add elements to the top of it and remove the most recently added element (we only have access to the top of the can).

Stacks are leveraged in every aspect of computer systems (stacks and stack pointers handle program flow and aid in controlling variable scopes and managing function calls in operating systems). When developing higher-level programs, stacks can be found useful in backtracking algorithms acting as a buffer to keep track of each step (especially as we goes deeper recursively).

One common beginner-level use case for leveraging the stack data structure is finding unbalanced braces (where an opening brace doesn’t have a closing brace, or closing brace doesn’t have an opening brace). Let’s assume we’re given some input where the brackets are either ‘'(’' or ‘')'’.

Some pseudo-code for the simplified brackets problem being:

Read input into a string
instantiate empty stack
[start loop]
For character in string:
	if character is an open brace (
		append character to stack
	else if character is a closing brace such as )
		if stack is empty
			return "unbalanced brackets"
		else
			pop/remove character from stack
[end of loop]
if stack is empty:
	return "balanced"
else (stack still has some open brackets in it)
	return "unbalanced"

Typically queues are used in a fashion where the first element entered in is the first element put out (FIFO). Dequeues are double ended and allow us access to the other end of the queue (so we can access the last element entered - LIFO).

Performance Benchmarking Test Cases

We will observe the space usage and time usage of performing consecutive appends and consecutive pops. We will consider building our stack up to varying sizes (1,000 10,000 100,000 1,000,000).

We will utilize 3 underlying data structures to implement the “stack” data structure behavior. These 3 were also observed in this post describing how to implement a stack.

1. Lists
2. Deques
3. LifoQueue

Code Used for Test Case

No third party libraries were installed. A new VPS instance (Nanode from Linode) was spun up and the default Python 3.7.3 interpreter was used.

import functools
import time
from random import shuffle
from collections import deque
from queue import LifoQueue


# Code to get memory size accurately/deeply ---------
import sys
import gc
def get_obj_size(obj):
    marked = {id(obj)}
    obj_q = [obj]
    sz = 0

    while obj_q:
        sz += sum(map(sys.getsizeof, obj_q))
        all_refr = ((id(o), o) for o in gc.get_referents(*obj_q))
        new_refr = {o_id: o for o_id, o in all_refr if o_id not in marked and not isinstance(o, type)}
        obj_q = new_refr.values()
        marked.update(new_refr.keys())
    return sz
#----------------------------------------------------

def time_this(func):
    @functools.wraps(func)  # preserves metadata of original func
    def wrapper_timer(*args, **kwargs):
        start_time = time.perf_counter()
        value = func(*args, **kwargs)
        end_time = time.perf_counter()
        func_run_time = end_time - start_time
        print(f"Finished {func.__name__!r} in {func_run_time:.5f} secs")
        return value
    return wrapper_timer
    
test_iterations = [1_000, 10_000, 100_000, 1_000_000]
for test_case in test_iterations:
    int_list = [x for x in range(test_case)]
    shuffle(int_list)
    print("Test Case: ", test_case)
    
    list_stack = []
    deq_stack = deque()
    lifo_q_stack = LifoQueue()
    
    @time_this
    def list_append():
        for num in int_list:
            list_stack.append(num)
            
    @time_this
    def list_pop():
        for _ in range(test_case):
            list_stack.pop()
    
    @time_this
    def deq_append():
        for num in int_list:
            deq_stack.append(num)
            
    @time_this
    def deq_pop():
        for _ in range(test_case):
            deq_stack.pop()
    
    @time_this
    def lifo_append():
        for num in int_list:
            lifo_q_stack.put(num)
    
    @time_this
    def lifo_pop():
        for _ in range(test_case):
            lifo_q_stack.get_nowait()
    
    
    print("------------- LIST --------------")
    list_append()
    print("list memory size: ", get_obj_size(list_stack))
    list_pop()
    print("---------------------------------\n\n")

    print("------------- DEQUE -------------")
    deq_append()
    print("deque memory size: ", get_obj_size(deq_stack))
    deq_pop()
    print("---------------------------------\n\n")
    
    print("------------- LIFO Q ------------")
    lifo_append()
    print("LifoQueue memory size: ", get_obj_size(lifo_q_stack))
    lifo_pop()
    print("---------------------------------\n\n")

Results

All time is taken in seconds (s)

Section 1 : Time taken to append an Element onto the Stack

Lists and Deques performed very similarly however it could be found that Lists are approximate 0.1 times slower than Deques, making Deques the best performer but not by an extravagant margin, in comparison to what was observed with LifoQueues.

LifoQueues performed the worst being 23.5 times slower than Lists. This might be due to overhead associated with the fact that these were meant to be used in multi-threaded or multi-processing environments, enforcing synchronized queues (where information must be exchanged safely between threads). The exact reasoning is beyond the scope of this post which is just to establish performance benchmarks on ways stacks can be implemented.

Section 2 : Time taken to Remove an Element off the Stack

The results appear to be similar to Section 1 of the results. However it is noticeable that on average, to remove an element off a stack takes more time than appending an element to the stack.

Section 3 : Space Usage of the Stack

Size measured in bytes

Arguably, while we can see that Lists and Deques varied in its size (due to compiler resizing Lists and Deques bigger than needed to accommodate faster appends - reducing need to interweave resizes into every operation), Deques had consistently showed to be a smaller amount to Lists in the largest case of 1,000,000 elements appended.

LifoQueue, once again consistently performing worse but not by an extravagant amount this time (in this case being only 0.1 times more memory usage than Lists typically).

Conclusion

We observed that Lists are approximate 0.1 times slower than Deques. Under circumstances where multi-processing or multi-threading is not involved, LifoQueues should definitely be avoided, due to it being 23.5 times slower when applying operations involving appending and removing.