Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Project: Prime Sieve and a Benchmark Harness

Build a prime sieve in WebAssembly, verify it against known prime counts, write a reusable benchmark harness with warm-up, median and spread, and learn to interpret the results honestly.

The first project processed an image. This one is about measurement. You will write the Sieve of Eratosthenes as a WebAssembly module, check it against known mathematical facts, and build a small, reusable benchmark harness. Then you will use that harness to compare wasm with JavaScript on three different sizes of input, and learn why the answer depends on the size.

The sieve is a good subject: it is a classic memory-bound loop (marking multiples in a byte array), its answers are known exactly (the number of primes below one million is 78,498), and it exercises exactly the pattern that suits WebAssembly: a tight loop over linear memory with one call from the host.

The algorithm

  1. Make a table of flags for 2, 3, ..., n, all set to "prime".
  2. For each number i starting at 2, while i * i <= n: if i is still marked prime, mark i * i, i * i + i, i * i + 2i, ... up to n as not prime. (Starting at i * i is enough because smaller multiples were already marked by smaller primes.)
  3. Count the flags that are still set.

In the module the flag table is the linear memory itself: one byte per number, at address i. The module has 17 pages, about 1.1 MB, enough for n up to a bit over one million. The function is sieve(n) -> count.

WAT
(func (export "sieve") (param $n i32) (result i32)
  ;; 1. set bytes 2..n to 1
  ;; 2. for i = 2; i*i <= n; i++: if mem[i] then for j = i*i; j <= n; j += i: mem[j] = 0
  ;; 3. return the number of bytes in 2..n that are still 1
  ...)

The sieve

Flags in memory One byte per number.
Cross out Multiples of each prime.
Count Bytes still set are primes.
Known answers pi(10^6) = 78,498.

Check against facts, not feelings.

1 / 2

Step 1: correctness first

Before timing anything, make sure the answers are right. Mathematicians have tabulated the prime counting function pi(n) for a long time, so we have ground truth: pi(10) = 4, pi(100) = 25, pi(1,000) = 168, pi(10,000) = 1,229, pi(100,000) = 9,592, pi(1,000,000) = 78,498. We also write a JavaScript sieve and make sure all three agree.

Node.js Sieve in wasm, checked against known counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The last lines show something special about this design: after the call returns, the sieve's table is still sitting in linear memory, and JavaScript can read it through a view without any copying. The module returned only a count, yet the whole result is available for free.

Step 2: a reusable harness

Now the timing code. A good harness is a function you can reuse for any pair of implementations. It should:

  • Verify that the function returns the expected answer before it measures anything.
  • Warm up, because the first calls include compilation and caching effects.
  • Run several samples, each containing enough repetitions to last at least a few milliseconds, so the timer's resolution does not dominate.
  • Report the median (robust against outliers), plus the minimum (best case) and the spread (relative difference between the 25th and 75th percentile) so you can tell a stable result from a noisy one.
Node.js A benchmark harness and the sieve at three sizes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Read the numbers carefully, because the honest answer is rarely a single ratio:

  • At small sizes the per-call fixed costs (the boundary crossing in one case, allocating a fresh Uint8Array in the other) are a big part of the time. The JavaScript version allocates and zeroes a new table every call, while the wasm version reuses its memory, which is an unfair advantage you should name when you report results.
  • At large sizes memory bandwidth and cache misses dominate. Both versions walk through the table in the same pattern, so the gap often narrows.
  • The spread column tells you how much to trust a difference. If two implementations differ by less than their spread, you have measured noise.
  • Machine and engine matter. The same code gives different ratios on a laptop, a phone and a server, and between engine versions.

Step 3: make the comparison fair

When you present a benchmark, ask what could make it unfair. Here it would be:

  1. Allocation. Give JavaScript a reusable table too (allocate once, fill each call) and re-measure. Fairness means comparing the algorithms, not the allocators.
  2. Result equivalence. Both return a count, but the wasm table is also readable afterward. If your real use case needs the primes list, add the cost of extracting it to both.
  3. Input shape. Real workloads rarely run one size repeatedly; sample a realistic mix.
  4. Whole-task time. Include download and compile time if the user will pay it (see WebAssembly Performance).

Ideas to extend the project

  1. Write a segmented sieve that processes the range in 32 KB blocks to stay inside the CPU cache, in both languages, and compare.
  2. Return the primes in an i32 array in memory and read it as an Int32Array view.
  3. Use bulk-memory (memory.fill) to initialize the table in one instruction instead of a loop.
  4. Add a bit-packed version that uses one bit per number (eight times less memory) and compare cache behavior.
  5. Run the harness inside a Web Worker and send the results back with postMessage.
  6. Make the harness print a Markdown table so you can paste results into documentation.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why start marking multiples of a prime i at i * i?

    Any multiple k*i with k < i has a prime factor smaller than i, so an earlier pass already crossed it out.
  2. 2. Why does a good benchmark verify the answer before timing?

    Speed is only interesting for correct results. Checking known values (such as 78,498 primes below one million) catches mistakes early.
  3. 3. What does it mean if two implementations differ by less than the measured spread?

    The spread estimates run-to-run variation. Differences smaller than that cannot be distinguished from noise.
  4. 4. After sieve(n) returns, how can JavaScript read the table without copying?

    The flags live in linear memory, so a typed-array view over the exported memory exposes them directly.

Summary

  • The sieve stores one flag byte per number in linear memory and returns the count; results can be read afterward through a view with no copy.
  • Always verify correctness first against known values such as pi(1,000,000) = 78,498.
  • A harness should warm up, size samples to last several milliseconds, report median, minimum and spread, and refuse to time a wrong answer.
  • Interpret results by size, by fairness (allocation, equivalence) and by noise; ratios depend on machine and engine.
  • Extend it with segmented, bit-packed and bulk-memory variants.

Next: WebAssembly Practice and Interview Questions