swift

L'intuito mente: lezioni da un parser CSV

L'intuito mente: lezioni da un parser CSV — Parte 2: Corretto, poi veloce

Basta una virgoletta fuori posto per far crollare il parser. Come correggere il caso limite e portare l'indicizzazione a soli 65 millisecondi.

Twitter LinkedIn

Part 2 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 file GTFS da 260 MB, cinque milioni e mezzo di righe, e la scoperta che leggerlo costa l'1% del tempo: tutto il resto se ne va a trasformare byte in oggetti. Avevo preso tre decisioni di struttura (leggere a blocchi, indicizzare solo l'inizio delle righe, chiedere all'utente se c'è l'intestazione invece di indovinarla) e scritto la prima versione. Ci metteva venti secondi, quasi il doppio del codice ovvio, e non era colpa dell'algoritmo: era la build in debug.

In release erano 0,38 secondi. Il parser era veloce.

Restava da scoprire che non era corretto.

Quando una virgoletta fa sparire il file

Questa prima versione gestisce bene un a-capo tra virgolette quando queste racchiudono per intero il valore di una colonna.
Evitiamo infatti di interpretare il dato come la fine di una riga:

Mario,"Via Roma 1
00100 Roma",RM

Ma cosa succede se abbiamo " che non sono in un campo quotato?

prodotto,prezzo
monitor 24" full HD,199
tastiera,49

Quelle virgolette sono ovviamente i pollici dello schermo. Il nostro codice però vede una virgoletta e cambia stato di inQuotes. Mi sono scritto una tabellina a penna per chiarirmi il flusso: nessun benchmark, nessun test, solo quattro byte tracciati a mano su un file inventato di tre righe, ed è bastata a far crollare l’ipotesi.

Byte	inQuotes prima	Cosa fa
\n fine riga 1	false	registra la riga - OK!
" di 24"	false	toggle → true - FAIL
\n fine riga 2	true	salta - SKIP
\n fine riga 3	true	salta - SKIP

Da quel momento in avanti il resto del file finisce per essere male interpretato e diventa pressoché spazzatura.

La buona notizia è che l’RFC del CSV ci dà una semplice regola per gestire il tutto: una virgoletta apre un campo quotato solo se è il primo byte del campo.

• "Via Roma 1\n00100 Roma" la virgoletta è a inizio campo, il campo è quotato, l’a-capo dentro è un dato
• monitor 24" full HD la virgoletta è a metà campo, quindi è solo un carattere

È il motivo per cui è necessario if atFieldStart.

Le virgolette raddoppiate si annullano da sole

Un altro caso potenzialmente da gestire erano le virgolette letterali. Dentro un campo quotato, una virgoletta letterale la si scrive raddoppiandola:

Mario,"disse ""ciao"" e se ne andò"

Verrebbe da gestirlo: vedo una virgoletta, sbircio la prossima, se è ancora una virgoletta allora è un escape.
In realtà non serve. Il toggle se la cava da solo:

"hello""world"
^                inQuotes = true
      ^          inQuotes = false
       ^         inQuotes = true    ← i due si annullano
             ^   inQuotes = false

Due cambi di stato consecutivi non cambiano niente, e lo stato finale è quello giusto.

Sembra un dettaglio, e invece è la cosa che tiene in piedi tutta la lettura a blocchi: senza sbirciare in avanti, il confine dei 64 KB smette di essere un caso speciale. Un “” a cavallo di due blocchi non va gestito, perché non esiste niente da gestire: il primo byte arriva in un blocco, il secondo nell’altro, e il conto torna comunque.

Se avessi scelto di sbirciare in avanti avrei dovuto gestire quel caso limite a mano, e i casi limite scritti a mano sono esattamente quelli che ci si perde più facilmente per strada.

Il test che parla chiaro

A questo punto c’è soltanto una cosa che lavora meglio di un debugger per validare il tutto, ed è un test:

The test: the newline inside quotesThe complete code is on GitHub, along with the file used for measurements.

let bytes = Array("a,\"x\ny\",b\n1,2,3\n".utf8)
// indice:            0 1 2 3 4  5 6 7 8 9 …
#expect(offsets == [0, 10])

Tre \n nei byte, solo due righe sono vere: quello in posizione 4 è dentro le virgolette, e quello finale produce una riga fantasma da scartare.

Ma il valore del test non è nel controllo. È in cosa significano i modi di fallire:

Risultato	Diagnosi
[0, 10]	corretto
[0, 5, 10]	il tracciamento delle virgolette non sta girando affatto
[0, 10, 16]	gira, ma non scarta la riga fantasma finale

Due difetti diversi producono due numeri diversi. Il test non dice «sbagliato»: dice quale sbagliato.

E ha funzionato. Al primo lancio: [0, 5, 10].

Che è precisamente l’output di un parser che ignora le virgolette: quindi il problema non era la logica delle quote, era che quella logica non veniva eseguita. Sono andato a guardare il solo punto in cui poteva succedere, e il colpevole era un else scritto male:

} else {                  // scatta su qualunque byte
} else if !inQuotes {     // scatta solo fuori dalle virgolette

Il ramo dei separatori si attivava anche dentro un campo quotato. Un \n protetto dalle virgolette veniva registrato lo stesso. Il debugger non l’ho aperto.

A un test non chiedo di dirmi che ho sbagliato: quello lo so già.
Gli chiedo di dirmi dove.

L’ottimizzazione che non ha ottimizzato niente

A questo punto il parser generava correttamente un array con tutti gli indici di partenza delle righe.
Peccato che i dati, letti a blocchi da 64 KB, fossero già stati scartati: ogni blocco sovrascriveva il precedente.

Per estrarre davvero una riga dovevo tornare a prendermi quei byte, e le strade per farlo erano poche:

• Rileggere riga per riga, saltando ogni volta alla posizione giusta: vuol dire una chiamata al sistema operativo per riga, sei milioni di chiamate per leggere in media quarantasei byte l’una. Decisamente da escludere.
• Rileggere a blocchi e consegnare le righe man mano, ma vuol dire attraversare il file una seconda volta e rifare tutte quelle copie che volevo evitare. In più una riga può cominciare in un blocco e finire in quello dopo: per consegnarla intera devo conservare la coda del primo e attaccarla alla testa del secondo, con un caso speciale da scrivere e da ricordarsi. Anche questa poco attraente.
• Mappare il file e tenermelo tutto indirizzabile in una volta.

Ed è qui che mi sono accorto di una cosa che avevo davanti dall’inizio: l’indice che avevo appena costruito contiene posizioni assolute dentro il file. Non sono offset relativi a un blocco, ma numeri che danno la posizione assoliuta.
Che è esattamente il linguaggio di una memoria mappata, dove il file è un array.

In effetti avevo già fatto metà del lavoro che rendeva mmap comodo:

let fd = open(fileURL.path, O_RDONLY)
defer { 
    // Una volta creata la mappa, il descrittore del file non serve più. 
    // La mappatura tiene un suo riferimento, e la memoria resta valida anche a file chiuso.
    close(fd)
}

var info = stat()
fstat(fd, &info)
let size = Int(info.st_size)

// mmap non dà i byte: riserva soltanto un intervallo di indirizzi nello spazio di memoria del processo 
// e dice al kernel «quando qualcuno tocca questi indirizzi, vai a prendere i pezzi di quel file». 
let mapped = mmap(nil, size, PROT_READ, MAP_PRIVATE, fd, 0)!
defer { munmap(mapped, size) } // rilascia la prenotazione alla fine

// crea il puntatore alla memoria tipizzato
let base = UnsafePointer(mapped.assumingMemoryBound(to: UInt8.self))

La parte di indicizzazione di colpo si era semplificata, senza il while, senza readData e senza dover mantenere un fileOffset.

Inoltre le tre variabili di stato, che erano fuori dal ciclo per tenere traccia tra una lettura e l’altra del blocco, ora erano normali variabili locale di un ciclo che percorre il file dall’inizio alla fine.
Il campo quotato spezzato a metà fra due letture, che non è stato risolto, aveva ha smesso di poter accadere.

var offsets: [Int] = [0]

var atFieldStart = true
var fieldIsQuoted = false
var inQuotes = false

for i in 0..<size {
    let b = base[i]
    // ...identico a prima, gli stessi quattro rami byte per byte
}

A parte la semplificazione del codice mi aspettavo però anche un miglioramento delle performance; ho quindi provato a misurare la differenza con la lettura a blocchi:

The test: three indexing stages comparedThe complete code is on GitHub, along with the file used for measurements.

	Release
blocchi da 64 KB	0,384s
mmap	0,373s

Niente. Un uno virgola zero.

Neanche madvise(MADV_SEQUENTIAL) ha funzionato, ho rosicchiato giusto un altro centesimo.

Cos'è madvise()?

È un modo per dire al kernel come vogliamo usare una regione di memoria mappata, così che possa regolarsi di conseguenza. Con MADV_SEQUENTIAL stiamo dicendo «questo file lo leggerò dall'inizio alla fine, una volta sola».

Due cose cambiano. La prima è il readahead: quando tocchiamo una pagina, il kernel ne carica in anticipo anche un certo numero di quelle successive, invece di aspettare che gliele chiediamo una per una. Senza il suggerimento deve prima accorgersi da solo che stiamo procedendo in ordine, quindi parte più cauto.

La seconda è che le pagine che ci seiamo lasciati indietro vengono liberate prima, perché gli hai promesso che non tornerai a guardarle. Su un file da 260 MB è la differenza fra tenerselo tutto residente e tenerne una finestra che scorre.

È un suggerimento, non un ordine: il kernel può tranquillamente ignorarlo.

Che non abbia funzionato, comunque, ha perfettamente senso.

Pensandoci il collo di bottiglia non è mai stato il modo in cui i byte arrivano, ma il ciclo che ne guarda uno alla volta facendogli quattro domande. Ho cambiato come il file viene preparato, non come viene letto, e il tempo se ne andava tutto nella lettura.

Ora, tenersi una modifica che non fa guadagnare niente somiglia parecchio a un capriccio.
La differenza fra le due cose sta però tutta nel saper dire cosa ci ha comprato, anche quando non è velocità.

Qui erano meno codice e un caso limite in meno da ricordare, ma soprattutto un puntatore stabile: un indirizzo valido per tutta la vita del lettore, su cui potrò far puntare i campi senza doverli copiare da nessuna parte. A cosa serva davvero lo vedremo fra poco.

Per ora il cronometro segna 0,373 secondi, e non si è mosso di un millimetro.

Cercare invece di guardare

All’interno del mio ciclo di indicizzazione facciamo quattro domande per ogni byte.

Sono però domande che il più delle volte non servono a niente: la stragrande maggioranza dei byte sono dati, non caratteri di controllo (virgolette, virgole, a-capo).
Un sacco di domande la cui risposta non ci interessa, e che in ogni caso sarebbe “no”.

L’obiettivo era quindi evitare di esaminare ogni byte: bastava trovare il prossimo byte interessante nella sequenza.

Fortunamente il C ha da sempre una funzione dedicata: memchr prende un blocco di memoria e un byte, e restituisce la posizione della prima occorrenza. Dentro non c’è niente di magico, solo del codice scritto in SIMD a mano: invece di confrontare un byte alla volta ne carica sedici in un registro e li confronta tutti insieme.

SIMD? SIMD (Single Instruction, Multiple Data) è una tecnica di parallelismo a livello di microprocessore che consente di eseguire un'unica istruzione su un intero insieme di dati contemporaneamente, anziché elaborare un singolo dato alla volta. Solitamente scrivere codice SIMD non è la cosa più facile del mondo: fortunatamente qui il lavoro è già fatto ed è più veloce di qualunque ciclo che potrei scrivere in Swift.

C’è un problema, però, ed è grosso: memchr cerca un byte solo. Il mio parser non deve trovare un byte, deve sapere se in questo momento si trova dentro o fuori dalle virgolette. Quello è uno stato, e uno stato non si esprime con una ricerca.

La domanda che scioglie il nodo

Sembrava un vicolo cieco, finché non mi sono posto una domanda diversa: quand’è che lo stato non serve?

La risposta è quasi banale una volta detta: Se in tutto il file non c’è nemmeno una virgoletta, allora nessun campo può essere quotato. E se nessun campo è quotato, nessun a capo può trovarsi dentro un campo. Quindi cercare gli a capo e basta non è un’approssimazione: è dimostrabilmente corretto.

E per saperlo basta una memchr che cerchi una virgoletta sull’intero file.

// C'è almeno una virgoletta, in tutti i 260 MB?
let hasQuotes = memchr(base, Int32(quoteByte), size) != nil

guard hasQuotes else {
    // No. Allora nessun campo è quotato, e trovare gli a capo basta.
    var pos = 0
    while pos < size, let hit = memchr(base + pos, 0x0A, size - pos) {
        let i = UnsafeRawPointer(hit) - UnsafeRawPointer(base)
        offsets.append(i + 1)
        pos = i + 1
    }
    return offsets
}

// Sì. Allora serve la macchina a stati, byte per byte, come prima.

La parte che mi piace di più non è la velocità: è che non sto chiedendo niente a chi usa la libreria. Nessuna opzione da attivare, nessuna promessa da fare sui propri dati. Il codice guarda il file e decide da solo quale scorciatoia può permettersi.

Quanto ha reso

The test: three indexing stages comparedThe complete code is on GitHub, along with the file used for measurements.

	Release
mmap, ciclo scalare	0,373s
mmap + annusata + memchr	0,065s

Un 5,7x, il primo vero salto di velocità.
C’è anche un effetto collaterale che non mi aspettavo. Prima dell’annusata avevo una variabile di configurazione — «prometto che nessun campo contiene a capo», che dava il percorso veloce a chi la attivava. Dopo, non serviva più a niente: la velocità arriva comunque. L’ho tolta.

E se avessi misurato in debug? Ricordate la figuraccia della build in debug? Vale la pena tornarci, perché questa ottimizzazione ci dà un altro punto di vista. Se avessi misurato questo stesso passaggio in debug, avrei visto un 176x invece di un 5,7x. Il motivo è che `memchr` è codice C già compilato, che la build di debug non tocca nemmeno, mentre il ciclo scritto a mano in Swift è precisamente ciò che il debug massacra.
Il confronto fra i due, in debug, è truccato in favore del primo di un fattore trenta.

Misurare nella configurazione sbagliata non dà soltanto il numero sbagliato, ma un suggerimento sbagliato di cosa convenga ottimizzare. Cosa che, come vedremo fra poco, è esattamente quello che avevo appena finito di fare.

Una riga che non contiene niente

A questo punto avevo ottenuto un codice più leggibile, meno flag di configurazione e non ultimo, la fase di indicizzazione era passata da 0,38s a 0,065s.

Batti il cinque! …Peccato che non sapessi come ottenere la riga numero n.

Due problemi, una soluzione

Prima di andare avanti abbiamo necessità di rappresenta è una riga. Potrebbe essere qualcosa di simile a questo?

struct CSVRow {
    let fields: [String] // i vari campi di ogni riga
}

potremmo leggerla con un cursore che avanza, una riga alla volta:

while let row = reader.nextRow() {
    print(row.field(at: 0))
}

È sicuramente l’approccio più semplice, ma anche il più costoso: per costruirla dovrei prendere i byte dal file, copiarli in una stringa nuova e metterla in un array.
Per ogni campo 56 milioni di stringhe, ognuna con la sua allocazione sull’heap.

Di fatto questo è l’approccio che si ottiene attraverso components(separatedBy:) e che avrebbe eclissato per tempi e consumi i piccoli passi di ottimizzazione fatti sopra.

Pensandoci però, i dati sono già in memoria: sono nel file mappato, contigui e già pronti. Vale davvero la pena copiarli per renderli visibili da un’altra parte?

struct CSVRow {
    let base: UnsafePointer<UInt8>  // il riferimento al file mappato
    let fields: UnsafeBufferPointer<Range<Int>>   // gli intervalli di ogni campo
}

In questa versione il testo della riga non viene mai copiato (zero-copy); si crea semplicemente una finestra su dati che sono già caricati altrove che vengono letti e processati solo nel momento in cui vengono richiesti (un po’ come fa Substring).

Ma anche questo approccio crea un problema: una riga che non contiene i propri dati è una riga che dipende da qualcun altro per restare valida in memoria; nel nostro caso dipenderà dall’esistenza della mappa nella classe CSVReader.

var riga: CSVRow?
do {
    let reader = try CSVReader(fileURL: url)
    riga = reader.nextRow()
} // qui il reader muore, e con lui la munmap
print(riga!.field(at: 0))   // SIGBUS

Il compilatore non segnalerà nulla ma a runtime la memoria non è più mappata e il processo muore con un SIGBUS.

Un secondo problema riguarda nuovamente le allocazioni.
Per dare accesso alle varie colonne per ogni riga c’è bisogno di un array di intervalli: un array per riga, cioè 5,6 milioni di altre allocazioni.

Suona familiare?
E’ esattamente il problema con cui siamo partiti all’inizio leggendo le righe, questa volta applicato alle colonne.

I due problemi hanno una radice comune: non c’è nessun momento in cui io sappia che una riga ha finito di servire. Se lo sapessi, potrei riusare lo stesso buffer per la riga successiva, e potrei garantire che nessuna riga sopravviva alla mappa. Quel momento me lo posso costruire, ed è la fine di una closure:

reader.forEachRow { row in
    // qui `row` è valida, e solo qui
} // qui non più

Dentro la closure il reader è vivo per definizione, quindi la mappa c’è.
E all’uscita so che quella riga è finita, quindi posso svuotare il buffer degli intervalli e riempirlo con la riga dopo.
Questo si traduce in una sola allocazione per l’intero file, invece di una per riga.

Il prezzo da pagare

Questa scelta ha un prezzo: si perde il while let, che è più familiare. Si perde l’uscita anticipata: per fermarsi alla prima riga che interessa serve un artificio, perché una closure che restituisce Void non sa dire «basta così» (nulla di complicato, qui, basterà far tornare un Bool in uscita).

Ovviamente niente mi vieta di catturare la riga dentro la closure e portarmela fuori, e se lo faccio torno al SIGBUS di prima. Per ora è una convenzione, non una regola: sta scritto nella documentazione, non nel compilatore. Swift avrebbe gli strumenti per renderlo un errore di compilazione, ma quella è una storia per un’altra volta.

A questo punto avevo tutto: un indice veloce, righe che non copiano niente, campi che si materializzano solo se qualcuno li chiede.
Mancava misurare quanto costasse davvero leggere quel file.

Part 2 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 3: Il 9% 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