Il Crivello di Eratostene

Il Crivello di Eratostene è uno degli algoritmi più antichi della storia — risale al III secolo a.C., quando il matematico greco Eratostene di Cirene lo descrisse per trovare tutti i numeri primi fino a un limite dato.

Un numero primo è un intero maggiore di 1 divisibile solo per 1 e per sé stesso. 2, 3, 5, 7, 11, 13 sono primi. 4 non lo è (è divisibile per 2). 15 non lo è (è divisibile per 3 e per 5).

L'approccio a forza bruta per trovare tutti i primi fino a N sarebbe: per ogni numero, dividilo per tutti i numeri precedenti e controlla se è divisibile. È corretto, ma lentissimo: ordine $O(N\sqrt{N})$.

Il Crivello è più intelligente. Invece di controllare ogni numero singolarmente, parte dall'assunzione opposta — tutti i numeri sono candidati primi — e poi elimina quelli che sicuramente non lo sono: i multipli dei primi già trovati.

Il procedimento:

1. Crea un array booleano di dimensione N+1, tutti inizializzati a true.
2. Parti da p = 2. Se p è true, è un numero primo.
3. Marca tutti i multipli di p — 2p, 3p, 4p, .... — come `false`.
4. Passa al successivo p non ancora eliminato e ripeti.
5. Fermati quando p supera √N. Tutti i true rimasti sono numeri primi.

L'ottimizzazione chiave è che al passo 3 si parte da p*p anziché da 2*p: tutti i multipli inferiori sono già stati eliminati nei passaggi precedenti. La complessità totale scende a $O(N \log \log N)$ — quasi lineare.

In questo articolo lo implementeremo in C e lo chiameremo da PHP usando FFI (Foreign Function Interface) — con tanto di benchmark a confronto.

Foreign Function Interface

FFI (Foreign Function Interface) è un meccanismo che permette a un linguaggio di programmazione di chiamare funzioni scritte in un altro linguaggio — tipicamente C — come se fossero funzioni native.

L'idea di fondo è semplice. Le librerie C — file .dylib su macOS — espongono un'interfaccia binaria standardizzata chiamata ABI (Application Binary Interface). Se sai come è fatta questa interfaccia, puoi chiamare quelle funzioni da PHP, senza estensioni e senza ricompilare nulla.

Cos'è un'ABI?

L'ABI è il contratto che esiste tra un programma compilato e il sistema su cui gira. Non riguarda il codice sorgente — riguarda i byte. Definisce esattamente:

• Come vengono passati gli argomenti a una funzione: quali usano i registri della CPU e quali vengono messi nello stack.
• Dove viene collocato il valore di ritorno.
• Quanto spazio occupano i tipi primitivi in memoria.
• Come si allinea lo stack prima di ogni chiamata.
• Come sono nominati i simboli nel file binario (name mangling).

Sulla maggior parte dei sistemi a 64-bit, si usa la System V AMD64 ABI. Questa convenzione definisce, tra le altre cose:

Questo è il "linguaggio" che FFI impara a parlare. Quando in PHP scrivi $ffi->sieve(1000000), il valore 1000000 viene convertito in un int a 4 byte e messo nel registro RDI. Quando la funzione C ritorna, PHP legge il puntatore risultante dal registro RAX. È esattamente quello che farebbe un programma C che chiama un'altra funzione C.

Come funziona sotto il cofano?

Il problema della differenza di mondi

PHP e C vivono in mondi radicalmente diversi:

• PHP gestisce la memoria automaticamente tramite un garbage collector. C gestisce la memoria manualmente con malloc() e free().
• PHP usa tipi dinamici: una variabile può essere un intero adesso e una stringa un momento dopo. C usa tipi statici con layout di memoria precisi e immutabili.
• PHP rappresenta ogni variabile internamente come una struttura chiamata zval, che contiene il tipo, il valore e un contatore di riferimenti. C parla direttamente con la CPU.

FFI deve costruire un ponte tra questi due modelli. Quel ponte ha due compiti precisi:

1. Parsing della dichiarazione C. PHP deve sapere la firma delle funzioni che vuole chiamare: quanti argomenti, di che tipo, cosa ritornano. Questo avviene attraverso dichiarazioni nel sottoinsieme del linguaggio C — senza implementazione, solo la firma.

2. Marshalling. La conversione dei tipi PHP nei tipi C e viceversa. Un int in PHP è uno zval con type tag IS_LONG e un valore di tipo zend_long (64-bit). Un int in C è 32-bit. FFI gestisce questa conversione in modo trasparente, ma è importante capire che sta accadendo.

Caricare le librerie

Quando chiami FFI::cdef(), PHP invoca internamente dlopen() — una funzione di sistema che carica dinamicamente una shared library in memoria. Poi, per ogni funzione dichiarata, usa dlsym() per ottenere l'indirizzo esatto di quella funzione nella libreria caricata. Da quel momento, PHP sa esattamente dove saltare in memoria per eseguire il tuo codice C.

Le librerie di sistema

Prima di scrivere codice C, usiamo qualcosa che già abbiamo installato: la libreria matematica standard, libm. Espone funzioni come sin(), cos(), sqrt().

FFI::cdef() accetta due argomenti: una stringa con le dichiarazioni in stile C delle funzioni che vogliamo usare, e il nome della shared library da caricare. Non stiamo dichiarando l'implementazione — solo la firma. È il contratto ABI in pratica: diciamo a PHP la forma della funzione, così sa quanti byte aspettarsi in ingresso e in uscita.

<?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

Nessuna compilazione, nessun package PECL, nessuna estensione da installare. PHP ha caricato la libreria matematica e sta chiamando le sue funzioni C come se fossero metodi di un oggetto.

Il Crivello di Eratostene in C

Perché è un buon candidato per FFI?

Il crivello opera su grandi array contigui in memoria, dove C è nella sua zona di comfort. Ha molti accessi sequenziali — caratteristica che lo rende CPU-cache friendly: la CPU può precaricare i dati in cache e scorrere gli elementi senza interruzioni.

In PHP, ogni accesso a un elemento di array passa per una hash table interna. Anche una semplice scrittura come $is_prime[$i] = false non è un singolo byte scritto in memoria: è una lookup nella hash table, un decrement del reference count dello zval precedente, e la costruzione di un nuovo zval. In C è un singolo mov assembly.

Il codice C: sieve.c

La funzione sieve() riceve il limite superiore, alloca internamente due array — uno per i flag booleani durante il calcolo, uno per i risultati finali — e restituisce un puntatore al secondo. Il primo elemento dell'array risultato contiene il conteggio totale dei primi trovati; gli elementi successivi sono i valori stessi. La seconda funzione, free_result(), serve a rilasciare quella memoria dall'esterno, come vedremo.

#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);
}

Tre dettagli tecnici da notare. Usiamo char per i flag booleani anziché int — un byte per elemento invece di quattro, quindi su un limite di 10 milioni la differenza è 10 MB vs 40 MB di RAM. Il cast (long long)p * p evita overflow aritmetico quando p è grande e il prodotto supererebbe i 32-bit di un int. Il cast (char*) su malloc() è obbligatorio in C++ ma non in C puro — includerlo comunque è buona pratica.

Compilare come shared library

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

• -O2: ottimizzazione di livello 2. GCC può riordinare le istruzioni, fare loop unrolling (srotolare i cicli per ridurre i salti condizionali), e sostituire chiamate a funzione brevi con il loro corpo inline.
• -shared: produce una libreria condivisa invece di un eseguibile. Un eseguibile ha un entry point (main()); una libreria espone simboli che altri possono linkare a runtime.
• -fPIC: Position-Independent Code. Le librerie condivise possono essere caricate a indirizzi di memoria diversi in processi diversi. Il codice PIC usa indirizzi relativi invece di assoluti — è quindi compatibile con il caricamento dinamico.

Usarla da 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 "Trovati {$count} numeri primi fino a {$limit}" . PHP_EOL;

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

$ffi->free_result($result);

$result non è un array PHP — è un oggetto FFI\CData, una finestra diretta sulla memoria del processo. Quando scriviamo $result[0], PHP non sta navigando nessuna hash table: sta leggendo 4 byte all'offset del puntatore C. La sintassi è identica a quella di un array, la meccanica sotto è completamente diversa.

La gestione della memoria

Bisogna avere chiaro un principio:

La memoria allocata in C non è visibile al garbage collector di PHP.

Quando PHP alloca un array ($arr = [1, 2, 3]), lo registra nel suo sistema di gestione della memoria. Quando il reference count di quella variabile scende a zero — perché non è più referenziata da nessuno — il garbage collector la libera automaticamente. È trasparente, automatico, invisibile.

Quando C chiama malloc(), alloca memoria nell'heap del processo senza informare nessun runtime. Nessun garbage collector la vede. Nessuno la libererà automaticamente. Se perdi il puntatore a quella memoria senza averla liberata, è un memory leak: la memoria rimane occupata finché il processo non termina.

Nel nostro esempio, la memoria dell'array dei risultati viene allocata in C e il puntatore viene passato a PHP. PHP non sa nulla di quella memoria. Se non chiamiamo free_result() — che a sua volta chiama free() — quella memoria non viene mai rilasciata.

FFI offre anche metodi propri per allocare memoria:

// Owned: true (default) — PHP gestisce il ciclo di vita, libera automaticamente
$buf = FFI::new('int[100]');
$buf[0] = 42;

// Owned: false — sei tu il responsabile, devi chiamare FFI::free()
$buf = FFI::new('int[100]', owned: false);
FFI::free($buf);

La regola pratica è che se la memoria è allocata da PHP con FFI::new(), usa owned: true. Se è allocata in C e restituita a PHP — come nel nostro sieve() — devi liberarla manualmente con una funzione C apposita.

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 "PHP puro : " . count($primes_php) . " primi 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} primi in {$time_ffi} ms" . PHP_EOL;

$ffi->free_result($result_ffi);

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

Su un MacBook non troppo recente, con PHP 8.3 e usando GCC con l'opzione -O2, otteniamo:

PHP puro : 78498 primi in 310 ms
FFI (C)  : 78498 primi in 9 ms
Speedup  : 34x

34x riflette l'overhead strutturale di PHP per operazioni intensive su array. Ogni accesso a $is_prime[$i] non è una semplice lettura di un byte: è una lookup nella HashTable interna, che calcola l'hash dell'indice intero, trova il bucket, e accede allo zval. Per scrivere $is_prime[$i] = false, PHP decrementa il reference count del vecchio valore e costruisce un nuovo zval. In C, lo stesso accesso è un singolo mov assembly — un'istruzione, un ciclo di clock.

I tipi C in PHP

FFI espone i tipi C attraverso stringhe di dichiarazione:

Le struct sono particolarmente potenti con FFI. Permettono di lavorare direttamente con strutture dati C complesse:

$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 "Prodotto scalare: {$dot}" . PHP_EOL; // (1×4) + (2×5) + (3×6) = 32

FFI::new('Vec3') crea un oggetto CData che rispecchia esattamente il layout in memoria della struct — 3 float da 4 byte ciascuno, 12 byte contigui. Accedere a $v1->x non è una proprietà PHP: è un accesso diretto a quei 4 byte in memoria.

Conclusione

FFI ha colmato una lacuna storica di PHP: la possibilità di uscire dal runtime gestito quando necessario, senza dover scrivere un'estensione C completa. Non trasforma PHP in C, né dovrebbe farlo. Ma quando il problema richiede potenza di calcolo grezza, accesso a memoria contigua, o integrazione con l'ecosistema di librerie C esistente, FFI è la risposta corretta.

La distanza tra PHP e C è sempre stata più concettuale che tecnica. Con FFI, quella distanza si accorcia in modo concreto e misurabile.