Data structures under tight limits

• Select and size a fixed-capacity representation for sampled data, commands, and device state, including overflow behavior.

• programming-state

A data structure is a promise about how information is organized and what operations will be cheap. A labeled record groups one sensor sample’s time, value, and status. A queue preserves arrival order for commands. A ring buffer stores only the newest fixed number of samples by wrapping back to its first slot, much like a security camera overwriting its oldest footage.

On a microcontroller, capacity is an engineering quantity. If each sample contains a 32-bit timestamp, a 16-bit reading, and a 16-bit status field, its payload is 8 bytes. N samples therefore require at least 8N bytes, possibly more because of alignment or language-object overhead. A fixed packed buffer can make this cost predictable; a list of dynamic objects may cost several times the payload and can fragment a small heap. Measure on the chosen runtime rather than assuming desktop costs.

Access patterns determine the build decision. A screen plot needs recent samples in chronological order, so a ring buffer is suitable. A command mailbox that must never silently discard an emergency stop needs a bounded queue with an explicit full policy, perhaps reserving one high-priority flag outside the queue. Index update is write_index = (write_index + 1) mod capacity. When full, overwriting is acceptable only if “newest history wins” is part of the requirement.

A frequent misconception is that arrays are primitive and therefore always fastest or safest. An array with ambiguous positions—item[3] means temperature today but flags tomorrow—invites unit and field mistakes. Conversely, nested general-purpose objects can hide memory cost. Name fields at boundaries, use compact representations where measurements justify them, and document units and overflow behavior. Silent overwrite, unbounded growth, and mixing raw counts with converted units are data-design failures, not storage trivia.

Problem

A controller has 12 KiB available for logging. Each packed sample uses 4 bytes for milliseconds, 2 bytes for ADC counts, and 2 bytes for flags. At 50 samples/s, how much history fits if 2 KiB is reserved?

Steps

1. Usable logging memory = 12 KiB - 2 KiB = 10 × 1024 = 10,240 bytes.
2. Sample size = 4 + 2 + 2 = 8 bytes, so capacity = floor(10,240 / 8) = 1,280 samples.
3. History duration = 1,280 samples / 50 samples/s = 25.6 s.

Result

A 1,280-entry packed ring buffer retains 25.6 seconds of history before overwriting the oldest sample.

Sanity check

50 samples/s × 25.6 s × 8 bytes/sample = 10,240 bytes, exactly the allocated capacity before runtime overhead outside the packed buffer.

A 32-entry command queue is full when a new ordinary motion command arrives. The specification says commands must execute in order and none may be lost. What is the correct design response?

A. Overwrite the oldest entry because ring buffers always discard old data B. Overwrite the newest entry and report success C. Reject or back-pressure the producer and expose a queue-full status D. Allocate memory forever until the command fits

Your answer: ______________________________

Reasoning:

Goal

Build a fixed eight-sample ring buffer and prove its ordering and overflow behavior from a trace.

Equipment

• Microcontroller or desktop Python environment
• serial console or terminal
• potentiometer or generated integer sequence
• notebook

Procedure

1. Represent each sample with a sequence number, raw value, and validity flag; state the units of each field.
2. Insert values 0 through 11 into capacity 8 while printing the write index after each insertion.
3. Read the retained entries oldest-to-newest and verify that sequence numbers 4 through 11 remain.
4. Introduce a deliberate fault by removing the modulo operation; capture the out-of-range error or corrupted ordering, then restore it.
5. Repeat with a queue-full policy that rejects the ninth item instead of overwriting it and compare the contracts.

What to observe

• Expected: the write index repeats 0 after 7, and overwrite mode retains the newest eight sequence numbers.
• Record actual printed indices and retained values; if the runtime reports object memory, record it separately from the 8-byte packed estimate.
• Expected fault signature: without modulo, the ninth write targets index 8 rather than wrapping to 0.

Transfer challenge

Choose a representation and full policy for storing the last 60 fan-speed estimates while guaranteeing that a stop request cannot be overwritten.

Cautions

• If using a potentiometer, connect it only between the board’s documented logic supply and ground; its wiper must stay within the ADC input range.

Learner: ____________________ Date: ____________________

Evidence artifact or file: ____________________________________________

Notes: