6
\$\begingroup\$

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μs\n", t_avg_w)
printf("Avg. read: %.02fμs\n", t_avg_r)
\$\endgroup\$

migrated from programmers.stackexchange.com Mar 24 '14 at 21:53

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • \$\begingroup\$ There's a link to github repository. \$\endgroup\$ – Matjaz Muhic Mar 24 '14 at 21:46
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is just some excellent input. Thank you very much! :) \$\endgroup\$ – Matjaz Muhic 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\$ – Matjaz Muhic 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\$ – Matjaz Muhic 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
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ But, fixed size queue doesn't actually wrap around does it? I'm a bit confused. \$\endgroup\$ – Matjaz Muhic 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\$ – Matjaz Muhic Mar 25 '14 at 7:02

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.