Circular buffers are based on an algorithm well known by any developer who’s got past the “Hello world!” days. They offer a number of key characteristics with wide applicability such as constant and efficient memory use, efficient FIFO semantics, etc.
One feature which is not always desired, though, it the fact that circular buffers traditionally will either overwrite the last element, or raise an overflow error, since they are generally implemented as a buffer of constant size. This is an unwanted property when one is attempting to consume items from the buffer and it is not an option to blindly drop items, for instance.
This post presents an efficient (and potentially novel) algorithm for implementing circular buffers which preserves most of the key aspects of the traditional version, while also supporting dynamic expansion when the buffer would otherwise have its oldest entry overwritten. It’s not clear if the described approach is novel or not (most of my novel ideas seem to have been written down 40 years ago), so I’ll publish it below and let you decide.
When I started programming in Python long ago, one of the features which really hooked me up was the quality interactive interpreter offered with the language implementation. It was (and still is) a fantastic way to experiment with syntax, semantics, modules, and whatnot. So much so that many first-class Python practitioners will happily tell you that the interactive interpreter is used not only as a programming sandbox, but many times as the their personal calculator too. This kind of interactive interpreter is also known as a REPL, standing for Read Eval Print Loop, and many languages have pretty advanced choices in that area by now.
After much rejoice with Python’s REPL, though, and as a normal human being, I’ve started wishing for more. The problem has a few different levels, which are easy to understand.
I was just rambling randomly yesterday, in the usual microblogging platforms, about how result checking seems to be ignored or done badly. The precise wording was:
It’s really amazing how little attention error handling receives in most software development. Even *tutorials* often ignore it.
It indeed does amaze me. It sometimes feels like we write code for theoretical perfect worlds.. “If the processor executes exactly in this order, and the weather is calm, this program will work.”. There are countless examples of bad assumptions.. someday I will come with some statistics of the form “Every N seconds someone forgets to check the result of write().”.
Avi Bryant is working on MagLev, a Ruby interpreter, based on Gemstone’s Smalltalk VM, with some very amazing features, like transactioned objects distributed across several VMs:
The integrated VMs, cache, and storage conspire to create an illusion that global state is shared across all instances: no matter how many VMs you add, over however many machines, they all see and work with the same set of Ruby objects.
My geek side finds this highly exciting, and eager to see it released to see how people will deal with it in practice.
At the same time, my let’s-build-stable-and-maintainable-software side is a bit skeptic. As Joe Armstrong puts so enthusiastically, shared state is hard to manage correctly, global transactions reduce scalability, and transparent RPC is seductive, but dangerous.
I’m also curious about the speed gains pointed out. It’s well known that the Ruby VM isn’t very fast, which means that there must be opportunities for speedups. Even then, 100x faster is impressive, and history shows that sometimes the significant improvements are harder when the semantics are precisely the same. Let’s hope Avi can manage to run the Ruby tests successfully.