How to write an efficient queue in Roc? · beginners

I'm slowly making my way through some Everybody Codes problems and a lot of the time I'm reaching for a queue data structure. In Go, I'm able to make a simple queue using slices. To enqueue, I append to the slice and to dequeue, I can get the head using q[0] and get the tail using q[1:].

In Roc, I'm experiencing slow performance anytime there are a lot of elements involved. I tried to make a simple flood-fill example:

main! = |args| {
    size = U64.from_str(args.get(0)?)?

    # Flood fill a 1D array, starting in its middle.
    # Use a queue to keep track of the next flood points under consideration.
    var $array = List.repeat(0, size)
    var $queue = [size / 2]
    while $queue.len() > 0 {
        head = $queue.get(0)?
        $queue = $queue.drop_first(1)
        $array = $array.set(head, 1)?
        if head > 0 {
            left = head - 1
            if $array.get(left)? == 0 {
                $queue = $queue.append(left)
            }
        }
        if head < $array.len() - 1 {
            right = head + 1
            if $array.get(right)? == 0 {
                $queue = $queue.append(right)
            }
        }
    }

    for a in $array {
        if a != 1 {
            return Err(FloodFillIncorrect)
        }
    }

    Ok({})
}

$ time ./floodfill 1000
real    0m0.008s
user    0m0.002s
sys 0m0.006s

$ time ./floodfill 10000
real    0m0.087s
user    0m0.025s
sys 0m0.059s

$ time ./floodfill 100000
real    0m0.454s
user    0m0.110s
sys 0m0.340s

$ time ./floodfill 1000000
real    0m4.246s
user    0m1.004s
sys 0m3.203s

$ time ./floodfill 10000000
real    0m42.567s
user    0m10.011s
sys 0m32.195s

So are my problems due to my queue implementation being inefficient or due to a performance bug in the Roc compiler? Any guidance you could give me would be great!

Luke Boswell (Aug 20 2026 at 00:24):

Thanks for the clear example @cerk this was interesting to dig into and uncovered some bugs and compiler optimizations we can follow up with.

I asked my agentic friends to swing off some performance tools. The results are here if anyone is interested to read more about the approach

In short, the List.drop_first(1) creates a seamless slice whose data pointer has moved past the beginning of the allocation. When you then call append, Roc doesn't reuse the capacity before that pointer, it allocates a new list, copies the remaining elements, and release the old allocation.

A better general representation retains the list and advance instead of repeatedly calling drop_first like;

var $queue = List.with_capacity(size)
$queue = $queue.append(start)
var $cursor = 0
while $cursor < $queue.len() {
    point = $queue.get($cursor)?
    $cursor = $cursor + 1
    # enqueue with $queue.append(...)
}

For this flood fill, marking cells as visited when they are enqueued also prevents the same cell from being queued more than once. Explicitly using 0.U8 and 1.U8 for the visited array avoids the original program’s inferred 16-byte Dec elements.

With those changes, the Roc implementation became allocation-free inside the traversal loop and took about 8.7 ms at 1,000,000 elements. The corresponding Zig implementation took about 2.2 ms. The remaining difference looks like compiler optimization work.

cerk (Aug 20 2026 at 02:56):

Thanks @Luke Boswell. Your explanation was helpful and clear. I'll stop using List.drop_first(1), preallocate the queue when possible and use $cursor.

Note that the queue size in my example only gets up to a maximum of 2 because of the 0 checks in the array. I.e., if I put this check in the while loop...

    while $queue.len() > 0 {
        if $queue.len() > 2 {
            crash "too many items in queue!"
        }
        .
        .
        .
    }

...the program never crashes. I now understand that I'm continually allocating because of List.drop_first(1) but it should be a small allocation. This repeated small allocation would be enough to cause the slowdown I'm seeing?

Eric Rogstad (Aug 20 2026 at 04:21):

I didn't follow the cursor suggestion. Is the idea that you reserve some size in memory and then wrap around to the beginning if you append off the end (and if the beginning has been freed up by dequeues)? Or is it something else?

Stream: beginners

Topic: How to write an efficient queue in Roc?

cerk (Aug 19 2026 at 22:41):

Luke Boswell (Aug 20 2026 at 00:24):

cerk (Aug 20 2026 at 02:56):

Eric Rogstad (Aug 20 2026 at 04:21):

Luke Boswell (Aug 20 2026 at 04:27):

Richard Feldman (Aug 20 2026 at 11:35):