Appendix A

Implementing the circular buffer turned out to be very difficult. It was also very difficult to test; there were many boundary cases. A resizeable, doubly-linked, circular list was an alternative I considered. Here is a side by side comparison.

Circular Buffer Circular List
  • Almost never need to allocate memory
  • Difficult to overflow buffer
  • No extra processing
  • Expected to be efficient*
  • Hard to implement
  • May need to search through messages unnessecarily
  • Messages never have to be processed more than once
  • Probably easier to implement
  • Easy to remove a message from anywhere
  • Need to allocate memory frequently and copy messages around

The major advantages of the buffer are that it requires no memory allocations, and for a buffer with only one to three messages, it should be very fast because there's no unnecessary processing of the data. The major advantages of the list are that it should be easier to implement (and hence less buggy) and, unlike the buffer, it's easy to remove a message from anywhere. The list method will also perform well when messages are repeatedly revisited. This is because messages can be processed and read into a structure the first time. Then it is easy to read without further work on subsequent accesses. However, it's unlikely a message would be read more than once or twice; so, this may just be extra work.

*There's no way to compare without implementing both methods.


home