It’s been a while, but we’re back for week 8. This week’s challenge is to write a Circular Buffer. It’s basically a first in, first out data structure with the limitation that there’s only $n$ slots for data.

It took me a while to get around to this because of having to do a bunch more elixir learning track exercises, and also because I’ve been on holiday. The selection of languages available for this exercise were kind of limited, so I’ve had to branch out into using web assembly for this one. I also did a few easier web assembly exercises to get the hang of it.

JavaScript

Let’s start with the most straightforward solutions, but also the least interesting, and probably the least efficient.

class CircularBuffer {
  constructor(maxLen) {
    this.items = []
    this.maxLen = maxLen
  }

  bufferFull(){
    return this.items.length == this.maxLen
  }

  bufferEmpty(){
    return this.items.length == 0
  }

  write(x) {
    if (this.bufferFull()) {throw new BufferFullError}
    this.items.unshift(x)
  }

  read() {
    if (this.bufferEmpty()) {throw new BufferEmptyError}
    return this.items.pop()
  }

  forceWrite(x) {
    if (this.bufferFull()){this.read()}
    this.write(x)
  }

  clear() {
    this.items = []
  }
}

export default CircularBuffer;

export class BufferFullError extends Error {
  constructor(errMsg = "Buffer is Full") {
   super(errMsg);
  }
}

export class BufferEmptyError extends Error {
  constructor(errMsg = "Buffer is Empty") {
    super(errMsg);
  }
}

There’s not much to report about this solution really. We’ve got two helper functions to figure out if the buffer is empty or if the buffer is full. The underlying data structure is just a JavaScript array which we write to with unshift and read from with pop. So you read from the right-hand end, and you put new items in at the left-hand end.

This is probably not a very efficient implementation of a circular buffer, because every write and every read requires us to check the length of the array, and we also need regular access to both ends of the array. I don’t know how javascript implements its array, but this could be quite inefficient. If the javascript array is a linked list, then measuring the length and accessing the end of the array are slow (because both operations require us to walk through the whole list). On the other hand, if the array is a fixed contiguous array in memory, then the problem with such an implementation of a list data structure is normally that if the list grows longer than the allocated memory the interpreter has to go and allocate a larger chunk of memory and copy the contents over before it can do anything. In the case of a circular array there’s a fixed maximum size, but I don’t think that’s going to help here. Consider successive writes and reads: write “A”, write “B”, write “C”, read “A”, read “B”. At this stage, the “C” is in the third position in the array, and adding new writes will add them to the right of where “C” is. So even if the circular buffer had a maximum length of 3, we would need potentially unlimited scope to grow the array (even as we shrink it from the other side by noting that we have removed the elements to the left of “C”).

Elixir

My Elixir solution to the circular buffer problem is largely the same, with the proviso that a circular buffer is a container for some state, and functional languages like elixir don’t really “do” state. So elixir has this system of processes and links that basically permits you to store your state as a separate service. This isn’t really the place to go into detail on GenServer and the like, but essentially there’s two parts to the solution. Here’s the first half:

defmodule CircularBuffer do
  @moduledoc """
  An API to a stateful process that fills and empties a circular buffer
  """
  use GenServer

  @doc """
  Create a new buffer of a given capacity
  """
  @spec new(capacity :: integer) :: {:ok, pid}
  def new(capacity) do
    GenServer.start_link(__MODULE__,capacity)
  end

  @doc """
  Read the oldest entry in the buffer, fail if it is empty
  """
  @spec read(buffer :: pid) :: {:ok, any} | {:error, atom}
  def read(buffer) do
    GenServer.call(buffer, :pop)
  end

  @doc """
  Write a new item in the buffer, fail if is full
  """
  @spec write(buffer :: pid, item :: any) :: :ok | {:error, atom}
  def write(buffer, item) do
    GenServer.call(buffer, {:push, item})
  end

  @doc """
  Write an item in the buffer, overwrite the oldest entry if it is full
  """
  @spec overwrite(buffer :: pid, item :: any) :: :ok
  def overwrite(buffer, item) do
    outcome =  write(buffer,item)
    if outcome != :ok do
      read(buffer)
      write(buffer, item)
    end
  end

  @doc """
  Clear the buffer
  """
  @spec clear(buffer :: pid) :: :ok
  def clear(buffer) do
    GenServer.cast(buffer, :clear)
  end

The first part is, effectively the API: the functions a user would call (new, read, write, overwrite and clear). The new() function creates a genserver process and returns a pid which you can use to communicate with it. The remaining API functions effectively, make a call to the GenServer with a message – either an atom such as :pop or a list such as {:push, item} – and expect a reply from the genserver.

  # List helpers

  defp push(list, item) do
    [ item | list ]
  end

  defp pop(list) do
    List.pop_at(list, -1, :empty)
  end

  # GenServer callbacks

  @impl GenServer
  def init(capacity) do
    {:ok, %{capacity: capacity, items: []}}
  end

  @impl GenServer
  def handle_call({:push, item}, _from, state) do
    if state.capacity > length(state.items) do
      new_state = %{state | items: push(state.items, item)}
      {:reply, :ok, new_state}
    else
      {:reply, {:error, :full}, state}
    end
  end

  @impl GenServer
  def handle_call(:pop, _from, %{items: list} = state) do
    {item, new_list} = pop(list)
    if item == :empty do
      {:reply, {:error, :empty}, state}
    else
      {:reply, {:ok , item}, %{state | items: new_list}}
    end
  end

  @impl GenServer
  def handle_cast(:clear, state) do
    {:noreply, %{state | items: []}}
  end
end

Then we have the remaining functions, helper functions and genserver callbacks. Creating a new genserver calls the init function (@impl is elixir’s way of signalling that we’re providing an implementation of an interface). This function initialises out state, which is a keyword list where the capacity keyword is initialised with the value passed in to new above, and the items keyword is initialised to an empty list. Every message sent to our circular buffer process (by calling GenServer.call or GenServer.cast with the pid as the first argument) is then passed to the handle_call or handle_cast functions with the other arguments of the call or cast passed along. handle_call actually recieves the argument to call, the pid of the calling process (in this case we just ignore this) and the current state of the circular buffer. We then use elixir’s pattern matching to respond appropriately to the message. The return from the handle_call is an atom (normally :reply, but sometimes :noreply), the value to pass back to the calling process (i.e. {:ok, item}) and the new value of the state (i.e. the buffer). Call and cast differ as to whether you’re expecting a reply to your message. You can see that the handle_cast function has :noreply as the first item in its return tuple, and then the state as its second.

The actual circular buffer part of the solution is really just the helper functions push and pop which, as in the javascript solution, read from one end of a list and write to the other end. The handle_call functions that match on {:push, item} and :pop messages handle checking for full and empty buffers as required. So this is really largely the same actual solution as for javascript, wrapped in a layer of GenServer shenanigans. It seems like the elixir track designers in exercism decided to use the circular buffer exercise to help teach a completely different concept from what the exercise was originally supposed to be about.

WebAssembly

WebAssembly is a new language for me, and I’m still finding my feet. Some might say diving straight in to tackle an exercise exercism rates as Hard might not have been wise, and in retrospect, I would agree. But we got there in the end.

The solution is going to take a little bit of explaining, both to give you some basics of WebAssembly, and also to understand how the solution itself is working.

WebAssembly is basically a stack machine that runs in your browser. You can call WebAssemly from within javascript (and, in fact, vice versa). You can transpile code from various languages into WebAssembly or you can write WebAssembly text format yourself directly. The exercism track is about doing the latter, but a lot of the tutorials and FAQs out there presume you’re doing the former. The MDN documentation for the text format is also incomplete, so muddling through figuring this stuff out took a little effort. In what follows I’m going to refer to WebAssembly Text Format as just WAT.

There’s two styles of writing WAT. You could write it like you’re writing assembly or similar: one instruction per line. So to add two numbers together (say, 5 and 7) you’d write:

i32.const 5
i32.const 7
i32.add

This would put an integer constant 5 (an i32 type, WAT also has i64) onto the stack, then it would put a constant 7 on the stack, and then the add instruction would take two items off the stack, add them together, and put the result on the stack.

WAT also permits you a more “lispy” way to write things; the same operation could be written:

(i32.add (i32.const 5) (i32.const 7))

This latter approach is broadly what I do below. Let’s look at the first chunk of the WAT code. Apologies for the wonky formatting and indentation: I wrote this solution in the exercism web editor rather than a more lisp-aware editor, so it’s a little hard to parse. Also, it looks like the syntax highlighting engine used here doesn’t recognise webassembly. I’ll look into that at some stage. Again, we’re going to split the solution into chunks to discuss.

(module
  ;; Linear memory is allocated one page by default.
  ;; A page is 64KiB, and that can hold up to 16384 i32s.
  ;; We will permit memory to grow to a maximum of four pages.
  ;; The maximum capacity of our buffer is 65536 i32s.
  (memory (export "mem") 1 4)
  ;; Add globals here!
  (global $capacity (mut i32) (i32.const 0))
  (global $filled (mut i32) (i32.const 0))
  (global $readPos (mut i32) (i32.const 0))
  (global $writePos (mut i32) (i32.const 0))

  ;;
  ;; Initialize a circular buffer of i32s with a given capacity
  ;;
  ;; @param {i32} newCapacity - capacity of the circular buffer between 0 and 65,536
  ;;                            in order to fit in four 64KiB WebAssembly pages.
  ;;
  ;; @returns {i32} 0 on success or -1 on error
  ;; 
  (func (export "init") (param $newCapacity i32) (result i32)
    (if (i32.or 
        (i32.lt_s (local.get $newCapacity) (i32.const 0)) 
        (i32.gt_s (local.get $newCapacity) (i32.const 65536)))
      (then (return (i32.const -1))))
    ;; grow memory by capacity // 16834 - (capacity % 16834 == 0)
   (memory.grow (i32.sub 
     (i32.div_s (local.get $newCapacity) (i32.const 16384)) 
     (i32.eq (i32.rem_u (local.get $newCapacity) (i32.const 16384)) (i32.const 0))))
   drop ;; the output of memory.grow
   (global.set $capacity (i32.mul (local.get $newCapacity) (i32.const 4)))
   (call $clear)
   i32.const 0
  )

  ;;
  ;; Clear the circular buffer
  ;;
  (func $clear (export "clear")
    (global.set $filled (i32.const 0))
    (global.set $readPos (i32.const 0))
    (global.set $writePos (i32.const 0))
  )

Every WAT file consists of modules. (Is every file exactly one module? Not sure, doesn’t matter for now). A module, for our purposes, consists of some global variables and some functions. You also need to specify the amount of memory you’ll need. You specify how much memory to initialise, and what the maximum amount of memory to permit is, in units of WebAssembly’s page size of 64KiB..

Our first function is the init function above. It basically checks you didn’t pass it a silly number, and then initialises the appropriate amount of memory. The first part of a function declares the signature of the function (in terms of its parameters and return type), and any local variables you might need. Then we get to the meat of the function itself. So what we’ve got here is an (if cond (then do)), where the cond is an or where each disjunct is a check whether the input parameter is silly (i.e. too big or too small). The do part is then just a return: if you pass in a silly number, we return -1.

At this stage in the function we know you haven’t passed in a silly value, so we use that value to grow the memory to the right number of pages. This is explained in the comment underneath. The basic is to grow the memory by a number of pages equal to $newCapacity / 16834 where we’re using integer division and 16834 is the size of a page of memory. (It’s 16834 32-bit integers or 65536 bytes). But there’s a slight wrinkle: if $newCapacity is a multiple of 16384 then the capacity is off by one. 16834/16834 = 1, but a buffer of capacity 16834 fits in one page, so we don’t need to grow the memory yet. Thus, using a pythonesque pseudocode, we actually grow memory by \$newCapacity / 16834 - int($newCapacity % 16834 == 0). (In WAT we don’t actually need to cast the boolean to an int, because there’s no boolean type, if statements just evaluate to integer 0 or 1.)

One quirk of WebAssembly is that a function can only change the stack by taking its parameters off the stack and putting its return value on there. So, since the memory.grow function puts a value on the stack (a 0 if the grow was successful) and we don’t want to return that value, we need to get rid of it. That’s what drop does.

Then we set the global variable $capacity to four times the $newCapacity value (because $capacity is denominated in bytes, whereas $newCapacity is denominated in 32-bit integers which take up four bytes each). We then just call clear which sets various global variables to zero.

And now we’re at the end of the function, and we need to return a 0 for success. Instead of an explicit return, we just use i32.const 0 to put the zero on the stack. In writing this, I realise I could have set $capacity first and then just used the return value of the memory.grow as the return value for init. That would probably make more sense.

Clear is a pretty simple function it just sets some global variables. Note here that there’s two parts of naming a function. The $clear name is the “internal” name you can use to call a function with call from inside WebAssembly. And the export "clear" part is to export the name so that you can call it from a javascript module that imports the WebAssembly module. (We need these latter parts to run the exercism tests).

As an aside, WAT is a bit annoying in that variables and integer literals can’t just be referred to by their name. For example, in python, to use a literal value or the value of a variable, you’d just write the actual number or the name of the variable. But in WAT, you need to write (i32.const 5) to get the literal value 5 (as a 32 bit int) or (local.get $var) to get the value of a local variable $var. This makes this it somewhat verbose and hard to read, in my opinion.

Before we see the rest of the the WAT code, I think it’s worth explaining the idea behind the implementation. We essentially define two pointers, the read and write pointers. These define the position in a fixed length array that the next read or write will occur. When either hits the maximum value – defined by $capacity – it loops back round to zero. We achieve this by “incrementing” the pointers by doing (p + 1) % c where c is the capacity. We then also keep track of how many spots in the array are filled (that’s the $filled variable) which we use to check for a full or empty buffer. We could probably do something clever to avoid having this extra variable, since a full or empty buffer both only occur when the read and write pointers have the same value. The trick would be figuring out which circumstance we are in.

  ;; 
  ;; Add an element to the circular buffer
  ;;
  ;; @param {i32} elem - element to add to the circular buffer
  ;;
  ;; @returns {i32} 0 on success or -1 if full
  ;;
  (func $write (export "write") (param $elem i32) (result i32)
    (if (i32.eq (global.get $filled) (global.get $capacity)) (then (return (i32.const -1))))
    ;; Store element at new writePos
    (i32.store (global.get $writePos) (local.get $elem))
    ;;Increment writePos
    (global.set $writePos
      (i32.rem_u (i32.add (global.get $writePos) (i32.const 4)) (global.get $capacity)))
    ;; Increase filled
    (global.set $filled (i32.add (global.get $filled)(i32.const 4)))
    i32.const 0
  )

  ;; 
  ;; Add an element to the circular buffer, overwriting the oldest element
  ;; if the buffer is full
  ;;
  ;; @param {i32} elem - element to add to the circular buffer
  ;;
  ;; @returns {i32} 0 on success or -1 if full (capacity of zero)
  ;;
  (func (export "forceWrite") (param $elem i32) (result i32)
    (if (i32.eq (global.get $filled) (global.get $capacity)) (then 
      (call $read)
      drop
      drop
    ))
    (call $write (local.get $elem))
  )

  ;;
  ;; Read the oldest element from the circular buffer, if not empty
  ;;
  ;; @returns {i32} element on success or -1 if empty
  ;; @returns {i32} status code set to 0 on success or -1 if empty
  ;;
  (func $read (export "read") (result i32 i32)
    (local $result i32)
    (if (global.get $filled) 
      (then 
        (local.set $result (i32.load (global.get $readPos)))
        ;; increment readPos
       (global.set $readPos
       (i32.rem_u 
           (i32.add (global.get $readPos) (i32.const 4))
         (global.get $capacity)))
        ;; decrement filled
        (global.set $filled (i32.sub (global.get $filled) (i32.const 4)))
        (return  (local.get $result) (i32.const 0))
        )
    )
    (return (i32.const -1) (i32.const -1))
  )
     
)

Because $readPos and $writePos are pointers to our byte-addressable memory, and because we are reading and writing 32-bit (4-byte) numbers, we need to increment them by 4, rather than by 1. At the time, this seemed simpler than incrementing them by 1 and multiplying the store and load addresses by 4. But this choice also means incrementing $filled by 4 rather than 1 (because I want to compare it to $capacity which is also denominated in bytes). In any case, there’s no convenient shortcut to increment a variable by 1 in WAT, so it’s not like it would have made the code much neater to do things the other way.

With that background, we can now read through the remaining functions. write checks if the buffer is full and returns -1 if it is. Then, if the buffer is not full, it stores the argument in memory at the position defined by $writePos, “increments” $writePos, increments $filled, and returns 0.

forceWrite checks if the buffer is full, and if it is, it reads a value and then drops the output. (It drops two values because read returns two values). Then it calls write as above.

Finally, read checks if the buffer is not empty (which is equivalent to $filled being non-zero) and if it is it loads the value from the memory address provided by $readPos, “increments” $readPos, decrements $filled, and returns the result, and a 0 for success. Otherwise it returns a -1, -1 pair for failure.

In hindsight I should probably have been consistent in my choice of whether to check for the failure case and return early (as in the write function) or check for the happy path and have a fallthrough failure clause at the end (as in the read function). The former is probably more readable, in my view.

It would be interesting to see how different my handwritten WAT solution is from, say, my javascript solution transpiled into WebAssembly. I wonder how difficult it would be to disassemble the WebAssembly to the point where we could compare them. That’s a project for another day, perhaps.