Ring buffer in Ruby

Question

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
 end
 def full?
 (@end + 1) % @size == @start
 end
 def empty?
 @end == @start
 end
 def write(element)
 return if full?
 @ring[@end] = element
 @end = (@end + 1) % @size
 end
 def read
 return if empty?
 element = @ring[@start]
 @start = (@start + 1) % @size
 element
 end
 def clear
 @ring = Array.new(@size)
 @start, @end = 0, 0
 end
end

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|
 rb.read
}
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Î1⁄4s\n", t_avg_w)
printf("Avg. read: %.02fÎ1⁄4s\n", t_avg_r)

• Matjaz Muhic: There's a link to github repository.

Answer 1

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.

This:

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:

RingBuffer#write
 0.560000 0.000000 0.560000 ( 0.563023)
RingBuffer#read
 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.

• Matjaz Muhic: This is just some excellent input. Thank you very much! :)
• Matjaz Muhic: 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?
• Flambino: @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.
• Matjaz Muhic: 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
• Flambino: @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.

Answer 2

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.

• Matjaz Muhic: But, fixed size queue doesn't actually wrap around does it? I'm a bit confused.
• ChrisWue: @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).
• Matjaz Muhic: 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?
• nijave: A fixed size queue generally blocks or raises an error when full instead of simply overwriting old elements like a ring buffer would
• nijave: @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