swift

L'intuito mente: lezioni da un parser CSV

L'intuito mente: lezioni da un parser CSV — Parte 3: Il 9%

Una volta misurata l'intera pipeline arriva la sorpresa: la fase su cui mi ero accanito pesa appena il 9% del lavoro reale.

Twitter LinkedIn

Part 3 of 3

View all parts

• Part 2 L'intuito mente: lezioni da un parser CSV — Parte 2: Corretto, poi veloce
• Part 3 L'intuito mente: lezioni da un parser CSV — Parte 3: Il 9%

Dove eravamo rimasti

Un parser che non si fa ingannare da una virgoletta in mezzo a un campo, costruito sopra un file mappato in memoria.

L'indicizzazione è scesa da 0,38 a 0,065 secondi grazie a memchr e a un controllo che decide da solo quando può permettersi la scorciatoia. Le righe non copiano un byte, e i campi si materializzano soltanto se qualcuno li chiede.

Tutto misurato, tutto più veloce di prima.

Tranne che non avevo mai cronometrato il lavoro completo.

Il 9%

Era giunto il momento di riprendere il cronometro in mano per misurare le fasi separatamente. Il trucco è far girare il ciclo con il corpo vuoto:

reader.forEachRow { _ in }

Questo divide ogni riga nei suoi campi e poi butta via tutto senza costruire un solo valore. La differenza fra questo tempo e quello del ciclo che fa davvero il lavoro è, per sottrazione, il costo della materializzazione degli oggetti.

Tre misure da prendere:

• l’apertura del file
• il ciclo a vuoto
• il ciclo vero

The test: the pipeline broken down by phasesThe complete code is on GitHub, along with the file used for measurements.

Fase	Tempo	Quota
Indicizzazione	0,062s	9%
Dividere le righe in campi	0,260s	38%
Trasformare i campi in valori	0,427s	62%
Totale	0,687s

Mi ero concentrato a spremere 315 millesimi dall’indicizzazione per poi scoprire che gli altri 625 millesimi non li avevo mai guardati. Non è che avessi ottimizzato male: l’indice adesso è davvero cinque volte più veloce, e i numeri sono quelli. È che avevo ottimizzato con cura chirurgica la fase più piccola del programma, quella che nell’uso reale pesa meno di un decimo.

Questo per due motivi:

• l’indice era la parte che vedevo: il codice appena scritto, quello che avevo in testa. Le altre due fasi funzionavano già e proprio per questo erano invisibili
• l’indice era l’unico ad avere un numero: era facile da cronometrare, e quello che non ha un numero non compete per la nostra attenzione

All’inizio ho citato Knuth tagliando la parola premature. Ma la frase intera dice qualcosa di più specifico di quanto ricordassi:

«We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.»

Il 97% delle volte. Io ho trovato il mio 9% e mi ci sono buttato dentro con entusiasmo per tre sezioni.
La differenza fra me e quel consiglio non è che lui lo sapeva e io no: lo sapevo anch’io, l’ho scritto nell’introduzione di questo articolo.

È che sapere una cosa e averla misurata sono due stati mentali diversi, e solo il secondo cambia quello che fai il lunedì mattina.

Dividere i campi

Dai test era evidente come il 38% del tempo se ne andava a spezzare le righe nelle loro colonne. E’ qui che mi sono accorto che la risposta ce l’avevo già in casa ma l’avevo buttata via.

Se vi ricordate, all’apertura del file “annuso” le virgolette per decidere come costruire l’indice. Quel risultato (“questo file non contiene nemmeno una virgoletta”) lo usavo per una riga di codice e poi lo scartavo. In realtà può essere utile anche dopo: se non ci sono virgolette in tutto il file, allora quando divido una riga in campi ogni virgola che incontro è un separatore vero, senza eccezioni da controllare.

// `start` e `end` delimitano la riga da spezzare, `ranges` raccoglie i campi.
private func splitFields(start: Int, end: Int, into ranges: inout [Range<Int>]) {
    ranges.removeAll(keepingCapacity: true)

    // `hasQuotes` è l'esito dell'annusata fatta all'apertura del file.
    // Se è falso, in tutti i 260 MB non c'è una virgoletta: nessun campo
    // è quotato, e ogni virgola che incontro è un separatore vero.
    guard hasQuotes else {
        var fieldStart = start   // dove comincia il campo che sto leggendo
        var pos = start          // da dove riprendere a cercare

        // memchr cerca la prossima virgola fra `pos` e la fine della riga.
        // Il terzo argomento, `end - pos`, limita la ricerca a questa riga:
        // non può sconfinare in quella dopo.
        // Restituisce nil quando non ne trova più: siamo all'ultimo campo.
        while pos < end,
              let hit = memchr(base + pos, Int32(delimiterByte), end - pos) {

            // memchr restituisce un puntatore, a me serve una posizione:
            // la ottengo sottraendo l'indirizzo di partenza della mappa.
            let i = UnsafeRawPointer(hit) - UnsafeRawPointer(base)

            ranges.append(fieldStart..<i)   // il campo va da fieldStart alla virgola
            fieldStart = i + 1              // il prossimo comincia subito dopo
            pos = i + 1
        }

        // L'ultimo campo non ha una virgola che lo chiude: finisce con la riga.
        ranges.append(fieldStart..<end)
        return
    }

    // Il file contiene virgolette: non si scappa dalla macchina a stati,
    // byte per byte, con i quattro rami di prima.
}

Un 1,5x.
Mi aspettavo qualcosa di più.

Perché memchr questa volta non ci ha aiutati?

Ma perchè così poco, se sull'indice lo stesso approccio mi aveva portato un 5,7x? D'altronde era la stessa funzione, stesso file, stessa idea.

In fondo però il motivo è molto più semplice: memchr conviene quando il byte che cerchiamo è raro: carica sedici byte alla volta, li confronta tutti insieme, e ci guadagna finché continua a non trovare niente. Ogni chiamata ha però un costo fisso di avvio.

Sull'indice cercavo gli a capo: uno ogni quarantasei byte. Tempo per prendere il ritmo, e cinque milioni di chiamate in tutto.

Qui cerco le virgole: una ogni quattro byte e mezzo, e cinquantasei milioni di chiamate. memchr fa si e no un giro vettoriale e torna indietro. Di fatto è quasi il caso peggiore in cui può lavorare.

La stessa ottimizzazione, sugli stessi dati, vale cinque volte o una volta e mezza a seconda di quanto è fitto quello che stai cercando. Non esistono ottimizzazioni buone: esistono ottimizzazioni adatte a una certa forma dei dati.

A questo punto restava una una cosa evidente: per ogni campo facevo append su un array per cinquatasei milioni di righe, ognuno con il suo controllo di capacità e di unicità.

Toglierli sembrava facile: se l’array è già dimensionato sul numero di colonne dell’header, posso scrivere direttamente ranges[n] invece di accodare. L’idea era di recuperare fra 170 e 280 millesimi. Ne ho recuperati 48.

Anche qui un bel buco nell’acqua.

Perché togliere gli append non ha reso quasi niente

Il motivo è che davo a ogni append tre o quattro nanosecondi, e ne costava meno di uno. Con la capacità già riservata, in release il compilatore solleva quasi del tutto il controllo di unicità, e quello sulla capacità è un ramo che il predittore della CPU azzecca ogni singola volta.

In più, scrivendo ranges[n], un controllo l'ho semplicemente sostituito con un altro: quello sui limiti dell'array.

Comuque alla fine, con due mosse, ero passato da 0,484 a 0,275 secondi, guadagnando il 1,76x complessivo sulla divisione in campi.

Fase	Tempo	Quota
Indicizzazione	0,062s	8%
Dividere in campi	0,275s	35%
Trasformare i campi in valori	0,427s	57%
Totale	0,764s

Rimane soltanto la materializzazione dei valori che adesso è la parte più grossa del programma.
Ed è l’unica fase che non ho ancora toccato.

Da byte a valori

Per leggere i dati, come ad esempio il numero di sequenza di una fermata, la via più ovvia è quella di ottenere la stringa e fare il casting.

let n = Int(row.field(at: iSeq)) ?? 0

Questa innocua operazione ne nasconde però due: field(at:) prende i byte dal file mappato e ne costruisce una String; poi Int(_:) legge quella stringa e ne ricava un numero.
Un’istruzione dopo, la stringa non serve più a nessuno.

Mi sembrava evidente che il costo fosse lì: costruire un oggetto per buttarlo via subito, cinque milioni e mezzo di volte.
Così ho scritto un accessory che i byte li legge direttamente, senza che nessuna stringa venga mai creata.

Vale la pena guardare cosa significa, perché non è complicato.

In un file non ci sono numeri: ci sono byte. Prendete 74763, uno degli identificativi di fermata della riga d’esempio all’inizio dell’articolo. Sul disco non è il numero settantaquattromilasettecentosessantatré, sono cinque byte separati, uno per cifra, ciascuno con il codice del carattere corrispondente.

Per ricavarne un intero li si percorre uno alla volta ricostruendo il valore: si parte da zero, moltiplica per dieci, si aggiunge la cifra, si ripete. Cinque giri per questo campo soltanto, e una decina di campi per riga, su cinque milioni e mezzo di righe.

Perché non usare una funzione di sistema?

La libreria C ha strtol, che converte cifre in numeri lavorando direttamente sui byte grezzi: niente String di mezzo, ed è un candidato serio.

L'ho scartata per un motivo preciso: strtol vuole una sequenza terminata da uno zero, e i miei byte stanno in mezzo a un file mappato, dove dopo il campo c'è una virgola. In pratica funzionerebbe lo stesso, perché la funzione si ferma comunque al primo carattere che non è una cifra. Ma non è una garanzia scritta da nessuna parte, e c'è un caso cattivo: un numero all'ultimo byte di un file la cui dimensione sia un multiplo esatto della pagina. Lì leggere un byte oltre il campo significa leggere oltre la mappa, e sono di nuovo SIGBUS.

Non mi andava che la libreria funzionasse a patto che i file dei suoi utenti non fossero multipli di 16 KB.

Il parser a mano, invece, si ferma dove gli dico io:

var result = 0
var i = range.lowerBound

while i < range.upperBound {
    let digit = Int(base[i]) &- 48    // il carattere '0' vale 48
    guard digit >= 0, digit <= 9 else { return nil }

    // Un campo da trenta cifre non è impossibile in un file che non ho scritto io.
    // Con `result * 10 + digit` scritto in modo ingenuo, lì il processo muore.
    let (scaled, overflowA) = result.multipliedReportingOverflow(by: 10)
    guard !overflowA else { return nil }
    let (sum, overflowB) = scaled.addingReportingOverflow(digit)
    guard !overflowB else { return nil }

    result = sum
    i += 1
}

Le due righe sull’overflow meritano un attimo. La versione ovvia result = result * 10 + digit su un campo abbastanza lungo sfora la capacità di un Int, e in Swift sforare non dà un numero sbagliato: fa terminare il processo.
Le varianti ...ReportingOverflow costano quanto gli operatori normali, perché il controllo il compilatore lo genera comunque, ma restituiscono nil invece di ammazzare tutto.

Sui decimali la regola si inverte

Per i Double ho pensato di fare lo stesso, e ho fatto bene a fermarmi.
Scrivere un parser di virgola mobile corretto è una di quelle cose su cui esistono articoli scientifici: arrotondamento all’ultima cifra, notazione esponenziale, casi limite di precisione.
È il tipo di codice che sembra funzionare per sei mesi.

Quindi qui vince la libreria. Con una sorpresa: Double(String) di Swift non passa da strtod, ha un parser suo, e non dipende dalla locale. Il bug classico per cui su una macchina italiana 3.14 diventa 3, perché il separatore decimale atteso è la virgola, in Swift non esiste.

E la String che dovevo evitare a tutti i costi? Sotto i sedici byte Swift la tiene dentro la struct, senza toccare l’heap. 41.902782 sono nove caratteri: quella stringa vive nei registri e sparisce.

Quanto è servito

The test: the pipeline broken down by phasesThe complete code is on GitHub, along with the file used for measurements.

	Materializzazione
conversione da String	0,572s
accessori tipizzati	0,446s

Un 1,3x. Sul percorso completo, 1,18x..

Meno di quanto il ragionamento promettesse: il fatto è che la stringa che stavo evitando, in gran parte, non veniva allocata. I campi numerici di un CSV sono corti per natura, 1, 0, 1167, 07:30:00, quindi finiscono tutti dentro la soglia dei sedici byte e restano inline.

È la stessa scoperta che avevo appena fatto sui decimali dove ero convinto che il costo fosse l’allocazione. L’allocazione non c’era.

Il parser a mano resta la cosa giusta da avere, 1,3x è 1,3x, e una volta scritto non costa più niente, ma per una ragione diversa da quella per cui l’avevo scritto: non evita di allocare, evita di costruire e validare una stringa UTF-8 per poi scartarla un’istruzione dopo.

La regola d’oro qui è: crivilo a mano quando la grammatica è banale e la libreria generica ti chiede garanzie che non hai; usa la libreria quando la correttezza è difficile.
Ma soprattutto c’è bisogno di controllare cosa stai davvero risparmiando, perché nel mio caso non era quello che credevo.

Dove siamo arrivati

Questa è la fotografia finale, con i numeri dell’ultimo giro:

The test: the pipeline broken down by phasesThe complete code is on GitHub, along with the file used for measurements.

Fase	Tempo	Quota
Indicizzazione	0,064s	8%
Dividere le righe in campi	0,271s	35%
Trasformare i campi in valori	0,446s	57%
Totale	0,781s

La fase su cui ho lavorato di più, tre sezioni, quattro riscritture, mmap e memchr e l’annusata delle virgolette, è quella che pesa l’8%. Quella che ne pesa il 57% l’ho grattata una volta sola, per un 1,3x, e mi sono fermato lì.

Non perché sia la scelta giusta. Perché è dove sono arrivato.

E il confronto con cui abbiamo aperto

Undici secondi contro 0,34: quei 0,34 sono l’indicizzazione più la divisione in campi, cioè esattamente il lavoro che faceva la versione ovvia, leggere il file e spezzare ogni riga nelle sue colonne. Il confronto regge.

Costruire i valori tipizzati sopra è un lavoro in più che la versione ovvia non faceva affatto, e porta il totale a 0,781s. Se l’avesse fatto anche lei, i suoi undici secondi sarebbero stati parecchi di più.

I 250 MB

Anche l’altro numero dell’apertura merita una spiegazione, perché non è quello che sembra.

Dei 251 MB occupati, circa 45 sono l’indice: cinque milioni e mezzo di posizioni da otto byte l’una. Memoria vera, allocata da me, e l’unico punto del programma in cui la struttura dati costa più di quanto verrebbe da pensare. Con offset a 32 bit invece che a 64 sarebbero 22, al prezzo di rinunciare ai file oltre i 4 GB — un compromesso che non ho voluto fare, ma che è lì.

Gli altri 206 MB sono le pagine del file mappato, finite nel conteggio perché la scansione le tocca tutte. E qui la differenza con i 782 MB della versione ovvia non è solo di quantità: quelle pagine sono pulite, il kernel le può scartare gratis quando ha bisogno di spazio e rileggerle dal disco se servono ancora. Le stringhe della versione ovvia sono memoria sporca: o stanno in RAM, o finiscono in swap.

Due modi molto diversi di occupare un quarto di gigabyte.

Cosa mi porto via

Riguardando l’intera storia, la parte che mi resta non sono le ottimizzazioni.
Sono le volte in cui ero convinto di qualcosa e il cronometro ha detto un’altra cosa.

• Ho creduto che il mio parser fosse lento e invece era il compilatore, in debug, a essere cinquantacinque volte più lento.
• Ho creduto che mmap avrebbe accelerato la scansione e non l’ha accelerata di un millesimo.
• Ho creduto che memchr avrebbe reso poco sui delimitatori e ha reso un 1,5x; poi ho creduto che togliere cinquantasei milioni di append avrebbe reso molto, e ha reso 48 millesimi.
• Ho creduto che gli accessori tipizzati evitassero un’allocazione, e quell’allocazione non c’era mai stata.

Cinque previsioni, e quasi tutte sbagliate, alcune per eccesso, altre per difetto, il che almeno esclude che stessi barando a favore della mia tesi.

Quello che le ha smontate, ogni volta, non è stata l’esperienza o l’intuizione. È stato costruire la cosa che le avrebbe potute smentire: un benchmark, un test fatto per distinguere due guasti diversi, una tabellina su un foglio.

Non è che misurare renda più intelligenti. È che ti costringe a scoprire cosa stai davvero facendo, che di solito è un’altra cosa rispetto a quella che credevi.

Quello che resta sul tavolo

Il 57% della materializzazione è ancora lì e non l’ho quasi toccato. E c’è un salto più grosso che non ho nemmeno tentato: le righe sono indipendenti fra loro, grazie all’indice, e nessuna dipende da quella prima o da quella dopo. Su otto core quei 0,78 secondi potrebbero diventarne 0,14.

Ma lì entra (forse) in gioco SIMD, quindi il tetto lo fissa proprio la fase che vale l’8%.
È la storia delle prossime parti.

Part 3 of 3

View all parts

• Part 2 L'intuito mente: lezioni da un parser CSV — Parte 2: Corretto, poi veloce
• Part 3 L'intuito mente: lezioni da un parser CSV — Parte 3: Il 9%

• #swift
• #craft

More on swift

• L'intuito mente: lezioni da un parser CSV — Parte 2: Corretto, poi veloce Sep 2026
• When intuition lies: lessons from a CSV parser • Part 1: The 20-Second Trap Sep 2026
• When intuition lies: lessons from a CSV parser • Part 3: The 9% Sep 2026