In CRuby, is Array#shift O(n) on a large Array used as a FIFO job queue, and what keeps push/shift and unshift cheap?

seniorshould knowfreq 30%

answer

front removal without moving elements
shared array, start pointer advances
16 elements and up
push/shift pattern refills at the end
unshift leaves room at the front

basics

~20 s

No. In CRuby, shift on an Array of 16 or more elements advances a start pointer into a shared buffer instead of moving elements, and push refills the buffer's end. Large arrays also reserve front room, so repeated unshift is amortized cheap.

solid answer

~40 s

The textbook claim that dequeuing from an array's front costs O(n) does not hold for CRuby's Array#shift. For an array of at least 16 elements, shift clears the first slot and advances the array's start pointer into a shared buffer; no elements move. Smaller arrays slide their few elements, which is trivially cheap. push after shift appends into the buffer's spare end room, and when that runs out the array copies its live elements into a doubled buffer, so a push/shift queue is amortized constant time per operation. unshift on an array that grows past 64 elements likewise switches to a shared buffer with free room at the front. The costs to remember are memory, since shifted-off capacity is kept until the next reallocation, and that this is a CRuby implementation detail.

The textbook claim that dequeuing from an array's front costs O(n) does not hold for CRuby's `Array#shift`. For an array of at least 16 elements, `shift` clears the first slot and advances the array's start pointer into a **shared** buffer; no elements move. Smaller arrays slide their few elements, which is trivially cheap. `push` after `shift` appends into the buffer's spare end room, and when that runs out the array copies its live elements into a doubled buffer, so a push/shift queue is amortized constant time per operation. `unshift` on an array that grows past 64 elements likewise switches to a shared buffer with free room at the front. The costs to remember are memory, since shifted-off capacity is kept until the next reallocation, and that this is a CRuby implementation detail.

code

ruby · 17 lines

ruby

jobs = []
1_000_000.times { |i| jobs.push(i) }

# Each shift advances a start pointer into a shared buffer;
# no elements are moved, so draining is linear in total.
until jobs.empty?
  job = jobs.shift
  # render(job)
end

# Mixed producer/consumer on one thread stays amortized O(1):
queue = []
100_000.times do |i|
  queue.push(i)
  queue.push(i + 1)
  queue.shift
end

go deeper

for a junior

Recall that push with shift makes a FIFO queue and that CRuby does not move every element on shift.

for a middle

Explain the shared-array trick: a start pointer that advances, cleared slots, and push refilling the buffer's end.

for a senior

Challenge folklore with CRuby's actual costs, watch retained capacity after spikes, and move cross-thread queues to Thread::Queue.

for a principal

Decide when relying on an interpreter's implementation detail is acceptable and when a documented data structure should carry the guarantee.

The textbook cost and CRuby's answer

In a naive array-backed queue, removing the first element shifts every remaining element one slot left, so a dequeue costs O(n). Many candidates assume Ruby's Array#shift works the same way and reach for a linked list or a ring buffer. In CRuby that assumption is wrong for the sizes where it would matter.

How shift avoids moving elements

A CRuby Array is a header that points into a buffer of object references. shift exploits that:

It reads the first element and clears its slot, so the removed object can be garbage-collected.
For an array of 16 elements or more (ARY_DEFAULT_SIZE in array.c), it turns the array into a shared array: the buffer becomes a shared root and the array keeps a pointer into it. No elements are copied.
It advances the start pointer by one and decrements the length.

Each later shift is a pointer bump. Arrays under 16 elements, or small embedded arrays, simply slide their few elements down, which costs almost nothing.

push after shift

A FIFO queue alternates push at the back with shift at the front. CRuby's push path recognises this; a comment in array.c notes that a shared array is "likely it participate in push/shift pattern":

If the shared buffer has spare room past the current end, push writes there directly.
If not, the array copies its live elements into a new buffer, doubling capacity as needed, and continues from there.

The copy happens only when room runs out, so over many operations the queue costs amortized O(1) per push and per shift.

unshift and front room

unshift (alias prepend) adds at the front. For arrays that would grow beyond 64 elements (four times the default size), CRuby also makes the array shared and reserves free slots in front of the first element, so subsequent unshift calls write into that room instead of moving everything. Smaller arrays slide their elements to make space.

Operation on a large Array	Naive expectation	CRuby behaviour
`push`	amortized O(1)	amortized O(1)
`pop`	O(1)	O(1)
`shift`	O(n)	O(1), pointer advance
`unshift`	O(n)	amortized cheap, front room reserved

Costs that remain

Memory retention. Shifting does not shrink the buffer. The slots before the start pointer are cleared but still allocated until a later reallocation, so a queue that once held a million jobs can keep that capacity.
Implementation detail. These are properties of CRuby's array.c, not promises of the language; other Ruby implementations may differ, and code that depends on them should say so.
Threads. An Array is not a thread-safe queue. A producer thread pushing and a consumer thread shifting need Thread::Queue, which blocks and wakes consumers correctly.

A drawing app job queue

A drawing app queues export jobs as the user clicks Export and a background loop takes the oldest one each tick:

jobs.push(job) on click, jobs.shift in the loop, both effectively constant time on CRuby.
An urgent job can jump the line with jobs.unshift(job).
If the queue can spike to a very large size, bound it or recreate the array after a spike so retained capacity is released.

When interviewers push on this, measuring beats asserting: a quick benchmark of a million push/shift pairs on the Ruby in production settles it.

## The textbook cost and CRuby's answer In a naive array-backed queue, removing the first element shifts every remaining element one slot left, so a dequeue costs **O(n)**. Many candidates assume Ruby's `Array#shift` works the same way and reach for a linked list or a ring buffer. In **CRuby** that assumption is wrong for the sizes where it would matter. ## How shift avoids moving elements A CRuby Array is a header that points into a buffer of object references. `shift` exploits that: 1. It reads the first element and **clears its slot**, so the removed object can be garbage-collected. 2. For an array of **16 elements or more** (`ARY_DEFAULT_SIZE` in `array.c`), it turns the array into a **shared array**: the buffer becomes a shared root and the array keeps a pointer into it. No elements are copied. 3. It **advances the start pointer** by one and decrements the length. Each later `shift` is a pointer bump. Arrays under 16 elements, or small embedded arrays, simply slide their few elements down, which costs almost nothing. ## push after shift A FIFO queue alternates `push` at the back with `shift` at the front. CRuby's push path recognises this; a comment in `array.c` notes that a shared array is "likely it participate in push/shift pattern": - If the shared buffer has **spare room past the current end**, `push` writes there directly. - If not, the array **copies its live elements** into a new buffer, doubling capacity as needed, and continues from there. The copy happens only when room runs out, so over many operations the queue costs **amortized O(1)** per `push` and per `shift`. ## unshift and front room `unshift` (alias `prepend`) adds at the front. For arrays that would grow beyond **64 elements** (four times the default size), CRuby also makes the array shared and **reserves free slots in front of the first element**, so subsequent `unshift` calls write into that room instead of moving everything. Smaller arrays slide their elements to make space. | Operation on a large Array | Naive expectation | CRuby behaviour | |---|---|---| | `push` | amortized O(1) | amortized O(1) | | `pop` | O(1) | O(1) | | `shift` | O(n) | O(1), pointer advance | | `unshift` | O(n) | amortized cheap, front room reserved | ## Costs that remain - **Memory retention.** Shifting does not shrink the buffer. The slots before the start pointer are cleared but still allocated until a later reallocation, so a queue that once held a million jobs can keep that capacity. - **Implementation detail.** These are properties of CRuby's `array.c`, not promises of the language; other Ruby implementations may differ, and code that depends on them should say so. - **Threads.** An Array is not a thread-safe queue. A producer thread pushing and a consumer thread shifting need `Thread::Queue`, which blocks and wakes consumers correctly. ## A drawing app job queue A drawing app queues export jobs as the user clicks Export and a background loop takes the oldest one each tick: - `jobs.push(job)` on click, `jobs.shift` in the loop, both effectively constant time on CRuby. - An urgent job can jump the line with `jobs.unshift(job)`. - If the queue can spike to a very large size, bound it or recreate the array after a spike so retained capacity is released. When interviewers push on this, measuring beats asserting: a quick benchmark of a million push/shift pairs on the Ruby in production settles it.

Why can a long-lived push/shift queue use more memory than its current length suggests?
Shifting advances a start pointer and clears the vacated slots, but the buffer is not shrunk. The capacity stays allocated until a later push needs a reallocation and copies only the live elements. After a large spike, replacing the array releases the old buffer.
When would you still reach for Thread::Queue instead of an Array?
Whenever producers and consumers run on different threads. `Thread::Queue` synchronises access and lets a consumer block until work arrives. An Array has neither property, so concurrent `push` and `shift` calls need external locking and busy-waiting.

saying these in an interview costs you the question

Array#shift in CRuby moves every remaining element each call
A FIFO queue in Ruby needs a hand-written ring buffer for speed
shift shrinks the Array's buffer immediately
An Array is a thread-safe queue because of the GVL
unshift on a large Array always copies every element

In CRuby, is Array#shift O(n) on a large Array used as a FIFO job queue, and what keeps push/shift and unshift cheap?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The textbook cost and CRuby's answer

How shift avoids moving elements

push after shift

unshift and front room

Costs that remain

A drawing app job queue

▾common follow-ups2 questions

▾red flags5 flags

The textbook cost and CRuby's answer

How shift avoids moving elements

push after shift

unshift and front room

Costs that remain

A drawing app job queue

answer

go deeper