Epic Fail #4: Poor data structure implementation
In my second year of university, I took a class that involved a series of AVR assembly language programming labs. One of them required an implementation of a queue data structure. It was meant to be a simple lab, but an early design decision made it needlessly complicated. This additional complexity single-handedly turned debugging into a nightmare.
My Epic Fail Queue Implementation
My implementation required that all elements be butted up to the front of the buffer. One pointer points to the back.
+---+---+---+---+---+---+
| A | B | C | | | |
+---+---+---+---+---+---+
^
Back
Enqueueing items would add to the back of the queue, and the Back
pointer is updated in the process:
+---+---+---+---+---+---+
| A | B | C | D | | |
+---+---+---+---+---+---+
^
Back
Dequeuing would require us to take from the front and shift the remaining elements forward to fill in the space:
+---+---+---+---+---+---+
| B | C | D | | | |
+---+---+---+---+---+---+
^
Back
Hopefully it should be obvious that this makes dequeuing so expensive to accomplish (O(n)
) since you’d have to read and write across all the remaining elements in order to do the shifting.
This mistake of choosing the wrong queue implementation bloated the code up by requiring an unnecessarily complex dequeue function to be implemented, and since the function didn’t work the first time around, it took at a nightmarish night of debugging.
The program was failing in such weird ways, and there were so many other possible points of failure, with so many subsystems concurrently running and accessing data all at once. Remember, this is assembly language we’re talking about! If the dequeue function were simpler, I could’ve quickly “proved” that it works as expected, thus allowing me to focus on other places.
In the end, the dequeue function was the problem.
When I proudly presented the final working program to the lab demonstrator, while he was impressed that I got such a thing to work, he was shocked that I even attempted to implement such a thing in the first place. “You realize you could’ve implemented this with a circular buffer, right?”
The Circular Buffer
In a circular buffer, your queue contents are continguously contained somewhere within the queue, not necessarily at the front or back. Two pointers point to the beginning and end.
Front
v
+---+---+---+---+---+---+
| | | A | B | C | |
+---+---+---+---+---+---+
^
Back
Dequeuing would simply grab whatever’s at the front and update the pointer:
Front
v
+---+---+---+---+---+---+
| | | | B | C | |
+---+---+---+---+---+---+
^
Back
And enqueing would simply add to the back and update the pointer:
Front
v
+---+---+---+---+---+---+
| | | | B | C | D |
+---+---+---+---+---+---+
^
Back
If the end of the buffer is reached, we simply wrap to the end, using modular arithmetic to start reading from the beginning again:
Front
v
+---+---+---+---+---+---+
| E | | | B | C | D |
+---+---+---+---+---+---+
^
Back
Simple and fast!
The Takeaway
The really obvious takeaway here is to make sure you evaluate your data structures and implementations properly, otherwise you end up giving yourself so much pain later on.
But for me personally, I think at the time, I was a bit too dangerously relaxed about the whole topic of data structures. At that point, I never experienced just how much worse poor design decisions can make everything.
To me, this was a painful yet valuable lesson in ensuring the suitability of a design, and it highlights the importance of mastering and internalizing understanding of data structures and algorithms.