I was just reading about ring buffer the other day and I was fascinated by how simple yet efficient it is.

I've implemented a ring (circular) buffer in Ruby and I'm just wondering if there's anything I can improve, and also how to properly measure its performance.

Ring buffer:

class RingBuffer

  attr_accessor :ring, :size, :start, :end

  def initialize(size)
    @ring = Array.new(size)
    @size = size
    @start, @end = 0, 0

  def full?
    (@end + 1) % @size == @start

  def empty?
    @end == @start

  def write(element)
    return if full?

    @ring[@end] = element
    @end = (@end + 1) % @size

  def read
    return if empty?

    element = @ring[@start]
    @start = (@start + 1) % @size

  def clear
    @ring = Array.new(@size)
    @start, @end = 0, 0


Speed test:

require_relative 'ring_buffer.rb'

buffer_size = 1024*1024
rb = RingBuffer.new(buffer_size)

t0 = Time.now
(buffer_size-1).times {|idx|
  rb.write idx
t1 = Time.now
(buffer_size-1).times {|idx|
t2 = Time.now

t_all = (t2-t0) * 1000.0
t_avg_w = (t1 - t0) * 1000.0 * 1000.0 / buffer_size
t_avg_r = (t2 - t1) * 1000.0 * 1000.0 / buffer_size

printf("All: %.02fms\n", t_all)
printf("Avg. write: %.02fμs\n", t_avg_w)
printf("Avg. read: %.02fμs\n", t_avg_r)
  • \$\begingroup\$ There's a link to github repository. \$\endgroup\$
    – Matjaz Muhic
    Mar 24 '14 at 21:46

A few things:

  • You declare accessors: Use them yourself. Don't access instance variables directly if you can help it; you'll keep you code more flexible if your object uses its own accessor methods. In other words: Drop most of those @ chars (though you'll have to use self.end to distinguish it from the end keyword)

  • However, for the most part, you'll only want public reader methods. Otherwise anyone can just mess with the internal ring array from the outside (sure, you can always mess with stuff in Ruby objects, but making it part of your object's declared interface makes it too easy).
    In fact, I'd probably pare it allll the way down to just read, write, empty? and full? with no public accessors and keep the rest private.

  • You could consider adding a method to do the oft-duplicated (x + 1) % size trick for you.

As for performance: Using a normal array with push and shift is much faster I'm afraid. And there's no fixed size. So if you want a fast FIFO buffer/queue in plain Ruby, use an array.


buffer_size = 1024**2
buffer = RingBuffer.new(buffer_size)

puts "RingBuffer#write"
puts Benchmark.measure {
  buffer_size.times { |i| buffer.write(i) }

puts "RingBuffer#read"
puts Benchmark.measure {
  buffer_size.times { buffer.read }

puts "----------------------------------"

array = []

puts "Plain Array#push"
puts Benchmark.measure {
  buffer_size.times { |i| array << i }

puts "Plain Array#shift"
puts Benchmark.measure {
  buffer_size.times { array.shift }

gets me:

  0.560000   0.000000   0.560000 (  0.563023)
  0.400000   0.000000   0.400000 (  0.400563)
Plain Array#push
  0.120000   0.000000   0.120000 (  0.139201)
Plain Array#shift
  0.170000   0.000000   0.170000 (  0.164827)

So writing/pushing is ~4.7 times faster, and reading/shifting is ~2.4 times faster with a regular ol' Array.

  • \$\begingroup\$ This is just some excellent input. Thank you very much! :) \$\endgroup\$ Jun 12 '14 at 9:59
  • \$\begingroup\$ I'm not sure though, how Array is faster. I've tried benchmarking this scenario: I fill both up (array and ring buffer) then I read/shift, and then a write/push. Shouldn't in this case ring buffer be faster since it's wrapping around and not shifting? \$\endgroup\$ Jun 12 '14 at 16:23
  • \$\begingroup\$ @MatjazMuhic Array will likely always be faster because it's compiled C code. It exposes a Ruby API, so it feels like it's just Ruby, but its guts are C. Your implementation, when written in Ruby, is basically an extra layer (interpreted, not compiled) on top of that. So nothing you write in Ruby will be as close to metal as built-in, compiled code. You might be able to make a fast circular buffer in C, though, with bindings for Ruby. But that's a very different topic, of course. \$\endgroup\$
    – Flambino
    Jun 12 '14 at 21:16
  • \$\begingroup\$ But I'm not doing anything cpu expensive since underneath it's using the array, but without shifting. This implementation for example should be faster than normal array: github.com/bbcrd/CBuffer \$\endgroup\$ Jun 13 '14 at 12:28
  • 1
    \$\begingroup\$ @MatjazMuhic Array, being compiled, isn't even on the same playing field as your code, regardless of what you're doing. I'll also add that there's something fishy with that library you linked. I tried running its rake benchmark task, and with no modifications, Array looks slower. But they've wrapped Array in a class, and (for whatever reason), it murders performance. I upped the iterations from 10,000 to 100,000, and it took so long I just pulled the plug. But skip the (unneccessary) wrapper, and Array again handily beats all-comers - by an order of magnitude. \$\endgroup\$
    – Flambino
    Jun 13 '14 at 13:06

I'm no ruby guy but just from a general point of view I try to see data structures from an abstract interface point of view. And your interface looks like a fixed size FIFO queue. The fact that you implemented it as a ring buffer is just an implementation detail really. So I'd be inclined to rename it to FixedSizeQueue, write to enqueue and read to dequeue which seems more natural names for the operations as you have implemented them.

  • \$\begingroup\$ But, fixed size queue doesn't actually wrap around does it? I'm a bit confused. \$\endgroup\$ Mar 25 '14 at 6:55
  • \$\begingroup\$ @MatjazMuhic: Well, what does it matter to the user? As a user you can write N items into the structure until it's full. And you can read from it until it's empty. And you will get the items out of it in the same order as they were put in. To me that's a fixed sized queue. What underlying implementation you use is not really relevant for the user (in most cases). \$\endgroup\$
    – ChrisWue
    Mar 25 '14 at 6:59
  • \$\begingroup\$ Well I guess someone would/could choose a ring buffer over a normal queue when the performance is critical? Because there's no overhead of shifting items? \$\endgroup\$ Mar 25 '14 at 7:02
  • \$\begingroup\$ A fixed size queue generally blocks or raises an error when full instead of simply overwriting old elements like a ring buffer would \$\endgroup\$
    – nijave
    Apr 19 at 16:32
  • 1
    \$\begingroup\$ @ChrisWue I guess more accurately the question is calling a FixedQueue a ring buffer so I guess there's so ambiguity in regards to what problem the original question was trying to solve. It seems ring buffer more commonly refers to a data structure that overwrites data automatically en.wikipedia.org/wiki/Circular_buffer \$\endgroup\$
    – nijave
    Apr 19 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.