Introduction

For most real programs, the fastest practical way to extract the indices of non-zero bytes is a single linear pass with a caller-provided output buffer. The algorithm is simple, cache-friendly, and often limited more by memory bandwidth than by arithmetic, which means a clean scalar loop is usually the right place to start.

Start with a Straightforward Single Pass

The baseline algorithm scans the input once and writes matching indices into an output array.

1#include <stddef.h>
2#include <stdint.h>
3
4size_t collect_non_zero_indices(const uint8_t *data, size_t len, size_t *out) {
5    size_t count = 0;
6
7    for (size_t i = 0; i < len; ++i) {
8        if (data[i] != 0) {
9            out[count++] = i;
10        }
11    }
12
13    return count;
14}

This is O(n) time and usually exactly what you want. Compilers are good at optimizing code like this, and the memory access pattern is ideal for modern CPUs.

Use a Runnable Test Harness

Before optimizing, make the function easy to verify.

1#include <stdio.h>
2#include <stddef.h>
3#include <stdint.h>
4
5size_t collect_non_zero_indices(const uint8_t *data, size_t len, size_t *out) {
6    size_t count = 0;
7
8    for (size_t i = 0; i < len; ++i) {
9        if (data[i] != 0) {
10            out[count++] = i;
11        }
12    }
13
14    return count;
15}
16
17int main(void) {
18    uint8_t bytes[] = {0, 7, 0, 0, 1, 4, 0, 2};
19    size_t out[sizeof(bytes) / sizeof(bytes[0])];
20
21    size_t n = collect_non_zero_indices(bytes, sizeof(bytes), out);
22    for (size_t i = 0; i < n; ++i) {
23        printf("%zu\n", out[i]);
24    }
25
26    return 0;
27}

Compile with optimization:

cc -O3 -march=native non_zero_indices.c -o non_zero_indices

That gives you both correctness confidence and a simple benchmark target.

Allocation Strategy Matters a Lot

In repeated calls, allocation overhead often matters more than loop micro-optimizations. The caller should usually provide the output buffer so the hot function itself does not allocate.

For maximum simplicity, allocate capacity equal to the input length. In the worst case every byte is non-zero, so that capacity is always sufficient.

If memory is tight and non-zero values are rare, a two-pass design can reduce output size:

• first pass counts non-zero bytes
• second pass writes exact-size output

That can save memory but doubles the scan cost, so it is a tradeoff rather than an automatic improvement.

Branches, Data Distribution, and Branchless Variants

The if (data[i] != 0) branch can be very fast when the data distribution is predictable. If the pattern is unpredictable, a branchless variant may help on some workloads.

1size_t collect_non_zero_branchless(const uint8_t *data, size_t len, size_t *out) {
2    size_t count = 0;
3
4    for (size_t i = 0; i < len; ++i) {
5        out[count] = i;
6        count += (data[i] != 0);
7    }
8
9    return count;
10}

This avoids the explicit branch, but it also writes more aggressively. On some inputs it is faster, on others it is slower. There is no substitute for benchmarking on real data distributions.

SIMD Is Possible, but It Is Not the Starting Point

If profiling proves this loop is a genuine bottleneck on large buffers, SIMD can process many bytes per iteration and derive bitmasks for non-zero lanes. That can improve throughput, but it also increases code complexity, portability cost, and maintenance burden.

For many workloads, a scalar -O3 loop plus good buffer management is already near the practical limit. SIMD is worth considering only after measurement shows the simple version is not enough.

Benchmark the Whole Use Case

Microbenchmarks are useful, but the real question is how the function behaves in the full pipeline. Relevant factors include:

• non-zero density
• input size
• output-buffer reuse
• surrounding memory traffic
• compiler flags and target CPU

A synthetic benchmark with fifty-percent random non-zero bytes may not represent production behavior at all. The fastest algorithm on paper is not automatically the fastest in the actual application.

Common Pitfalls

The most common mistake is reaching for SIMD before proving the scalar loop is too slow. Another is allocating output buffers inside the hot path and then blaming the scan loop for the performance cost. Developers also benchmark only one artificial data distribution and miss the fact that branch prediction behavior changes a lot across sparse, dense, and random inputs. Finally, using a narrow integer type for indices can break correctness on large arrays even if the loop itself looks fast.

Summary

• Start with a single-pass scalar scan and a caller-provided output buffer.
• Expect the loop to be memory-friendly and often close to optimal already.
• Treat allocation strategy as part of performance, not a separate concern.
• Compare branch and branchless versions only with representative data.
• Add SIMD only after profiling shows that the simple solution is truly the bottleneck.