The Sieve of Eratosthenes

The Sieve of Eratosthenes is one of the oldest algorithms in history — it dates back to the 3rd century BC, when the Greek mathematician Eratosthenes of Cyrene described it to find all prime numbers up to a given limit.

A prime number is an integer greater than 1 divisible only by 1 and itself. 2, 3, 5, 7, 11, 13 are primes. 4 is not (it is divisible by 2). 15 is not (it is divisible by 3 and 5).

The brute-force approach to find all primes up to N would be: for each number, divide it by all previous numbers and check whether it is divisible. It is correct, but extremely slow: order $O(N\sqrt{N})$.

The Sieve is smarter. Instead of checking each number individually, it starts from the opposite assumption — all numbers are prime candidates — and then eliminates those that certainly are not: the multiples of already-found primes.

The procedure:

1. Create a boolean array of size N+1, all initialised to true.
2. Start at p = 2. If p is true, it is a prime number.
3. Mark all multiples of p — 2p, 3p, 4p, .... — as `false`.
4. Move to the next p not yet eliminated and repeat.
5. Stop when p exceeds √N. All remaining true values are prime numbers.

The key optimisation is that in step 3 we start from p*p rather than 2*p: all smaller multiples have already been eliminated in previous passes. The total complexity drops to $O(N \log \log N)$ — nearly linear.

In this article we will implement it in C and call it from PHP using FFI (Foreign Function Interface) — complete with a benchmark comparison.

Foreign Function Interface

FFI (Foreign Function Interface) is a mechanism that allows a programming language to call functions written in another language — typically C — as if they were native functions.

The underlying idea is simple. C libraries — .dylib files on macOS — expose a standardised binary interface called an ABI (Application Binary Interface). If you know how that interface is structured, you can call those functions from PHP, without extensions and without recompiling anything.

What is an ABI?

An ABI is the contract that exists between a compiled program and the system it runs on. It has nothing to do with source code — it is about bytes. It defines exactly:

• How arguments are passed to a function: which ones use CPU registers and which ones go on the stack.
• Where the return value is placed.
• How much space primitive types occupy in memory.
• How the stack is aligned before each call.
• How symbols are named in the binary file (name mangling).

On most 64-bit systems, the System V AMD64 ABI is used. This convention defines, among other things:

This is the "language" that FFI learns to speak. When you write $ffi->sieve(1000000) in PHP, the value 1000000 is converted into a 4-byte int and placed in register RDI. When the C function returns, PHP reads the resulting pointer from register RAX. It is exactly what a C program would do when calling another C function.

How it works under the hood

The problem of two different worlds

PHP and C live in radically different worlds:

• PHP manages memory automatically through a garbage collector. C manages memory manually with malloc() and free().
• PHP uses dynamic types: a variable can be an integer now and a string a moment later. C uses static types with precise and immutable memory layouts.
• PHP represents every variable internally as a structure called a zval, which contains the type, the value, and a reference count. C talks directly to the CPU.

FFI must build a bridge between these two models. That bridge has two precise tasks:

1. Parsing the C declaration. PHP needs to know the signature of the functions it wants to call: how many arguments, of what type, what they return. This happens through declarations in a subset of the C language — no implementation, just the signature.

2. Marshalling. The conversion of PHP types into C types and back. An int in PHP is a zval with type tag IS_LONG and a value of type zend_long (64-bit). An int in C is 32-bit. FFI handles this conversion transparently, but it is important to understand that it is happening.

Loading libraries

When you call FFI::cdef(), PHP internally invokes dlopen() — a system function that dynamically loads a shared library into memory. Then, for each declared function, it uses dlsym() to obtain the exact address of that function in the loaded library. From that point on, PHP knows exactly where to jump in memory to execute your C code.

System libraries

Before writing C code, let us use something already installed: the standard math library, libm. It exposes functions such as sin(), cos(), sqrt().

FFI::cdef() takes two arguments: a string with C-style declarations of the functions we want to use, and the name of the shared library to load. We are not declaring the implementation — only the signature. This is the ABI contract in practice: we tell PHP the shape of the function, so it knows how many bytes to expect in and out.

<?php

$ffi = FFI::cdef('
    double sin(double x);
    double cos(double x);
    double sqrt(double x);
    double pow(double base, double exp);
', 'libm.dylib');

$angle = M_PI / 4;

echo $ffi->sin($angle) . PHP_EOL;    // 0.7071
echo $ffi->cos($angle) . PHP_EOL;    // 0.7071
echo $ffi->sqrt(2.0)   . PHP_EOL;    // 1.4142
echo $ffi->pow(2.0, 10.0) . PHP_EOL; // 1024

No compilation, no PECL package, no extension to install. PHP has loaded the math library and is calling its C functions as if they were methods on an object.

The Sieve of Eratosthenes in C

Why is it a good FFI candidate?

The sieve operates on large contiguous arrays in memory, where C is in its comfort zone. It has many sequential accesses — a characteristic that makes it CPU-cache friendly: the CPU can prefetch data into cache and iterate through elements without interruption.

In PHP, every array element access goes through an internal hash table. Even a simple write like $is_prime[$i] = false is not a single byte written to memory: it is a hash table lookup, a decrement of the previous zval's reference count, and the construction of a new zval. In C, the same access is a single mov instruction.

The C code: sieve.c

The sieve() function receives the upper limit, internally allocates two arrays — one for the boolean flags during computation, one for the final results — and returns a pointer to the second. The first element of the result array holds the total count of primes found; the following elements are the prime values themselves. The second function, free_result(), is used to release that memory from the outside, as we will see.

#include <stdlib.h>
#include <string.h>

int* sieve(int limit) {
    char* is_prime = (char*)malloc((limit + 1) * sizeof(char));
    memset(is_prime, 1, (limit + 1) * sizeof(char));

    is_prime[0] = 0;
    is_prime[1] = 0;

    for (int p = 2; (long long)p * p <= limit; p++) {
        if (is_prime[p]) {
            for (int multiple = p * p; multiple <= limit; multiple += p) {
                is_prime[multiple] = 0;
            }
        }
    }

    int count = 0;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) count++;
    }

    int* result = (int*)malloc((count + 1) * sizeof(int));
    result[0] = count;

    int idx = 1;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            result[idx++] = i;
        }
    }

    free(is_prime);
    return result;
}

void free_result(int* ptr) {
    free(ptr);
}

Three technical details worth noting. We use char for the boolean flags instead of int — one byte per element rather than four, so on a limit of 10 million the difference is 10 MB vs 40 MB of RAM. The cast (long long)p * p avoids arithmetic overflow when p is large and the product would exceed the 32 bits of an int. The (char*) cast on malloc() is mandatory in C++ but not in plain C — including it is good practice regardless.

Compiling as a shared library

gcc -O2 -shared -fPIC -o sieve.dylib sieve.c

• -O2: optimisation level 2. GCC can reorder instructions, perform loop unrolling (unrolling loops to reduce conditional jumps), and replace short function calls with their inlined body.
• -shared: produces a shared library instead of an executable. An executable has an entry point (main()); a library exposes symbols that others can link against at runtime.
• -fPIC: Position-Independent Code. Shared libraries can be loaded at different memory addresses in different processes. PIC code uses relative rather than absolute addresses — it is therefore compatible with dynamic loading.

Using it from PHP

<?php

$ffi = FFI::cdef('
    int* sieve(int limit);
    void free_result(int* ptr);
', __DIR__ . '/sieve.dylib');

$limit = 1_000_000;

$result = $ffi->sieve($limit);
$count  = $result[0];

echo "Found {$count} prime numbers up to {$limit}" . PHP_EOL;

echo "First 10 primes: ";
for ($i = 1; $i <= min(10, $count); $i++) {
    echo $result[$i] . " ";
}
echo PHP_EOL;

$ffi->free_result($result);

$result is not a PHP array — it is an FFI\CData object, a direct window into the process memory. When we write $result[0], PHP is not navigating any hash table: it is reading 4 bytes at the offset of the C pointer. The syntax is identical to that of an array; the mechanics underneath are completely different.

Memory management

One principle must be clear:

Memory allocated in C is not visible to PHP's garbage collector.

When PHP allocates an array ($arr = [1, 2, 3]), it registers it in its own memory management system. When the reference count of that variable drops to zero — because it is no longer referenced by anyone — the garbage collector frees it automatically. It is transparent, automatic, invisible.

When C calls malloc(), it allocates memory on the process heap without notifying any runtime. No garbage collector sees it. Nobody will free it automatically. If you lose the pointer to that memory without having freed it, you have a memory leak: the memory remains occupied until the process terminates.

In our example, the memory of the result array is allocated in C and the pointer is passed to PHP. PHP knows nothing about that memory. If we do not call free_result() — which in turn calls free() — that memory is never released.

FFI also provides its own methods for allocating memory:

// owned: true (default) — PHP manages the lifecycle, frees automatically
$buf = FFI::new('int[100]');
$buf[0] = 42;

// owned: false — you are responsible, you must call FFI::free()
$buf = FFI::new('int[100]', owned: false);
FFI::free($buf);

The practical rule is: if the memory is allocated by PHP with FFI::new(), use owned: true. If it is allocated in C and returned to PHP — as in our sieve() — you must free it manually with a dedicated C function.

Benchmark: PHP vs FFI

<?php

function sieve_php(int $limit): array {
    $is_prime = array_fill(0, $limit + 1, true);
    $is_prime[0] = false;
    $is_prime[1] = false;

    for ($p = 2; $p * $p <= $limit; $p++) {
        if ($is_prime[$p]) {
            for ($multiple = $p * $p; $multiple <= $limit; $multiple += $p) {
                $is_prime[$multiple] = false;
            }
        }
    }

    return array_keys(array_filter($is_prime));
}

$limit = 1_000_000;

$start = hrtime(true);
$primes_php = sieve_php($limit);
$end = hrtime(true);
$time_php = ($end - $start) / 1e6;

echo "Pure PHP : " . count($primes_php) . " primes in {$time_php} ms" . PHP_EOL;

$ffi = FFI::cdef('
    int* sieve(int limit);
    void free_result(int* ptr);
', __DIR__ . '/sieve.dylib');

$start = hrtime(true);
$result_ffi = $ffi->sieve($limit);
$count_ffi  = $result_ffi[0];
$end = hrtime(true);
$time_ffi = ($end - $start) / 1e6;

echo "FFI (C)  : {$count_ffi} primes in {$time_ffi} ms" . PHP_EOL;

$ffi->free_result($result_ffi);

$speedup = round($time_php / $time_ffi, 1);
echo "Speedup  : {$speedup}x" . PHP_EOL;

On a not-too-recent MacBook, with PHP 8.3 and GCC with the -O2 flag:

Pure PHP : 78498 primes in 310 ms
FFI (C)  : 78498 primes in 9 ms
Speedup  : 34x

34x reflects the structural overhead of PHP for array-intensive operations. Every access to $is_prime[$i] is not a simple byte read: it is a lookup in the internal HashTable, which computes the hash of the integer index, finds the bucket, and accesses the zval. To write $is_prime[$i] = false, PHP decrements the reference count of the old value and constructs a new zval. In C, the same access is a single mov instruction — one instruction, one clock cycle.

C types in PHP

FFI exposes C types through declaration strings:

Structs are particularly powerful with FFI. They allow working directly with complex C data structures:

$ffi = FFI::cdef('
    typedef struct {
        float x;
        float y;
        float z;
    } Vec3;

    float dot_product(Vec3 a, Vec3 b);
    Vec3 normalize(Vec3 v);
');

$v1 = $ffi->new('Vec3');
$v1->x = 1.0;
$v1->y = 2.0;
$v1->z = 3.0;

$v2 = $ffi->new('Vec3');
$v2->x = 4.0;
$v2->y = 5.0;
$v2->z = 6.0;

$dot = $ffi->dot_product($v1, $v2);
echo "Dot product: {$dot}" . PHP_EOL; // (1×4) + (2×5) + (3×6) = 32

FFI::new('Vec3') creates a CData object that mirrors exactly the in-memory layout of the struct — 3 floats of 4 bytes each, 12 contiguous bytes. Accessing $v1->x is not a PHP property: it is a direct read of those 4 bytes in memory.

Conclusion

FFI has filled a historical gap in PHP: the ability to step outside the managed runtime when necessary, without having to write a full C extension. It does not turn PHP into C, nor should it. But when the problem demands raw computational power, contiguous memory access, or integration with the existing C library ecosystem, FFI is the right answer.

The distance between PHP and C has always been more conceptual than technical. With FFI, that distance narrows in a concrete and measurable way.