swift

When intuition lies: lessons from a CSV parser

When intuition lies: lessons from a CSV parser • Part 4: Parsing Booleans and Doubles

Twitter LinkedIn

Part 4 of 4

View all parts

• Part 1 When intuition lies: lessons from a CSV parser • Part 1: The 20-Second Trap
• Part 2 When intuition lies: lessons from a CSV parser • Part 2: Correct, Then Fast
• Part 3 When intuition lies: lessons from a CSV parser • Part 3: The 9%
• Part 4 When intuition lies: lessons from a CSV parser • Part 4: Parsing Booleans and Doubles

Where We Left Off Al termine della scorsa parte ci eravamo lasciati con una scomoda verità; la generazione degli oggetti a partire dai byte rimane la parte più corposa: circa il 57% di tutto il tempo speso.

Ripartiamo quindi lavorando ai due parsing che ci rimangono: booleani e double.

Leggere i booleani

Anche qui, come accaduto per gli interi, siamo sotto i sedici byte: tutto resta inline e non viene mai toccato l’heap.
Mi aspettavo quindi un incremento poco entusiasmante.

Consideriamo i casi:

Tipologia	Token True	Token False
Booleana	true	false
Booleana abbreviata	t	f
Linguaggio naturale	yes, y	no, n
Numerica / Binaria	1	0

Sono dieci tipi di token, nessuno più lungo di cinque caratteri.
Questo significa che la lunghezza del campo è sufficiente già per escludere velocemente casi dal confronto:

• 1 byte può essere solo 1, 0, t, f, y o n
• 2 byte solo no
• 3 solo yes
• 4 solo true
• 5 solo false

Qualunque altra lunghezza è nil senza guardare un solo byte.

Va poi gestita la possibilità di leggere valori in maiuscolo/minuscolo, cosa che si risolve con un classico OR bit a bit.
Nella tabella ASCII, la differenza tra una lettera maiuscola (es. A = 65) e la sua minuscola (a = 97) è esattamente 32, cioè il bit 0x20. Così se T è 0x54 e t è 0x74, un OR con 0x20 accende quel bit e trasforma ogni maiuscola in minuscola.

L’OR con 0x20 funziona con le lettere ma non con le cifre: '1' | 0x20 resta 1, ma lo diventa anche 0x11, un carattere di controllo. Per questo le cifre si confrontano esattamente, prima di piegare le maiuscole.

@inline(__always) func folded(_ i: Int) -> UInt8 { 
    p[i] | 0x20 // da maiuscolo a minuscolo (solo per le lettere!)
}

Cosa è @inline(__always)? E' una direttiva che suggerisce (o meglio, forza) il compilatore a eseguire l'inlining di quella funzione.

Dice cioè al compilatore di non effettuare una vera chiamata a funzione, ma di prendere il codice all'interno di quella funzione e "incollarlo" direttamente nel punto in cui viene chiamata.

La logica del parser booleano sarà quindi:

switch count {
case 1:
    switch p[0] {
    case UInt8(ascii: "1"): return true
    case UInt8(ascii: "0"): return false
    default: break
    }
    switch folded(0) {
    case UInt8(ascii: "t"), UInt8(ascii: "y"): return true
    case UInt8(ascii: "f"), UInt8(ascii: "n"): return false
    default: return nil
    }
case 2:
    return folded(0) == UInt8(ascii: "n") && folded(1) == UInt8(ascii: "o") ? false : nil
// ... yes, true, false
}

Prima di cronometrare, la regola di sempre: le due versioni devono dare lo stesso risultato su qualunque input. Stavolta lo spazio da coprire è piccolo, quindi il test può provarli quasi tutti:

• ogni campo da uno e da due byte, cioè tutte le 65.792 combinazioni;
• ogni combinazione di maiuscole e minuscole di yes, true e false, anche tra virgolette;
• una manciata di caratteri non-ASCII scelti apposta per provare a ingannare lowercased().

The test: both boolField stages agree on every inputThe complete code is on GitHub, along with the file used for measurements.

Nessuna differenza. E a pensarci non poteva essercene: nessun carattere Unicode diventa, in minuscolo, una di quelle lettere ASCII, e un byte da 0x80 in su resta sopra 0x80 anche dopo l’OR. Il test non ha scoperto nulla, ma ora lo so invece di crederlo.

Poi il cronometro, sugli stessi 5,6 milioni di campi per entrambe le versioni:

The benchmark: boolField, String vs bytesThe complete code is on GitHub, along with the file used for measurements.

5,6 milioni di campi	String + lowercased()	byte
timepoint del GTFS (0/1)	0,095s	0,012s	7,8x
token misti (true, FALSE, No…)	0,116s	0,016s	7,1x

Non più 1,3x, ma addirittura 7,8x. Da 17 nanosecondi a campo a 2…

Ho sbagliato di nuovo, stavolta per difetto. Nella parte 3 avevo capito che l’allocazione non c’era. Da lì avevo concluso che non ci fosse niente da guadagnare: ma l’allocazione non era l’unico costo di una String.

Per un campo da un byte la versione con le stringhe fa tre cose:

• decodifica i byte
• valida che siano UTF-8 corretto
• lowercased() percorre le regole di maiuscole e minuscole di tutto Unicode per scoprire che… 1 resta 1.

Sugli interi il lavoro utile, moltiplicare e sommare cifre, pesava abbastanza da diluire quel costo. Qui il lavoro utile è un confronto su un byte, e il resto è tutto spreco.

Quanto pesa sul nostro CSV?

Onestamente: ben poco perché lì timepoint lo leggo come Int. Il guadagno si vede solo quando si decodificano davvero dei Bool.

Leggere i double

Gestire il parsing double è un passaggi

• String + Double(String): indubbiamente la più facile, ogni campo diventa una String (compreso il costo di validazione UTF-8) poi il casting richiama la funzione C di strdo. E’ la via più semplice e pertanto la useremo come baseline su cui confrontare la nostra ottimizzazione.
• strdo_l senza passare per String: Leggiamo i byte del campo in un buffer sullo stack, aggiungo il terminatore NUL e chiamo strdo_l con locale C. Questo passaggio ci permette di valutare oggettivamente il costo della trasformazione a stringa.
• Implementare un parsing vero e proprio con fast path di Clinger se possibile, altrimenti fallback su strdo_l: con una mantissa di 53 bit al massimo e esponente +-22 il risultato diventa una semplice moltiplicazione o divisione per una potenza di 10 esatta presa da una tabella; nel caso di troppe cifre, esponenti grandi, nan o inf torniamo a strdo_l. Per le coordinate, come nel nostro caso, andremo sempre nel fast path.
• Eisel-Lemire: è quello usato da tutti i parser moderni (tipo fast_float). Richiede però molto codice, una diversa attenzione che va fuori dal nostro scopo, ma più in generale non darebbe grandi vantaggi rispetto al C.

Definire la baseline

Una nota sui dati Il nostro GTFS si compone di due differenti tipi di double: in stop_times.shape_dist_traveled ci sono gli interi corti (più della metà in entro 4 char); shapes.txt invece contiene le coordinate `lat,lon` che hanno 9 chat.
Una stringa Swift è inline fino a 15byte; oltre quella soglia finisce in allocazione sull'heap.

Il nostro dataset racchiude quindi un buon insieme per testare entrambi i casi.

Il nostro parser è simile per firma a quello dei Bool: contiene quindi field che è un puntatore a un blocco di memoria contiguo con la sequenza di byte, mentre quoteByte come in precedenza è il byte che rappresenta il carattere usato per le virgolette ("):

public enum StageDoubleString {

    public static func doubleField(_ field: UnsafeBufferPointer<UInt8>, quoteByte: UInt8 = 0x22) -> Double? {
        var lower = 0
        var upper = field.count

        // Nel caso di stringhe con quote semplicemente stringiamo i margini dove leggere i dati escludendo le virgolette.
        if upper >= 2, field[0] == quoteByte, field[upper - 1] == quoteByte {
            lower += 1
            upper -= 1
        }

        // se rimane una stringa vuota semplicemente usciamo
        guard upper > lower else { return nil }

        // Qui si concentra il cuore dell'algoritmo:
        // Valida l'UTF-8 e sostituisce le sequenze invalide con U+FFFD. 
        // (Fino a 15 byte la stringa sta inline, altrimenti alloca)
        let text = String(decoding: UnsafeBufferPointer(rebasing: field[lower..<upper]), as: UTF8.self)
        // Utilizza strtod_l sotto, ma questo dipende anche dalle implementazioni sottostanti.
        return Double(text)
    }
}

I numeri da cui partiamo sono circa 18-22ns per ogni campo; negli aggregati la differenza tra il parsing di coordinate lunghe (allocate in heap) e i numeri corti (inline) è sotto il 2%.

C’è anche un’altra cosa che possiamo dire sin d’ora: considerando che la vecchia versione di boolField (quella che usava String) costava 16.9 ns per campo e che questa ne costa al più 22 ns, è lecito affermare che la parte di calcolo vero è irrisoria rispetto al tempo impiegato per convertire i byte in String e successiva validazione UTF-8.
Quanto è effettivamente questo tempo lo andremo a scoprire tagliando fuori la versione nel prossimo passo.

Parsing senza la converisione a String

public static func doubleField(_ field: UnsafeBufferPointer<UInt8>, quoteByte: UInt8 = 0x22) -> Double? {
        // Come nel precedente caso gestiamo le eventuali virgolette ai margini della stringa.
        var lower = 0
        var upper = field.count

        if upper >= 2, field[0] == quoteByte, field[upper - 1] == quoteByte {
            lower += 1
            upper -= 1
        }

        guard upper > lower else { return nil }

        // Qui facciamo qualche controllo preventivo per fallire velocemente:
        // Se l'ASCII del primo numero è:
        // - 0: Null (stringa vuota/terminatore)
        // - da 9 a 13: Caratteri di spaziatura (Tab, Newline, Carriage Return, ecc.)
        // - 32: Spazio classico
        // Se uno di questi valori coincide è inutile procedere con operazioni complesse: 
        // il codice restituisce subito nil risparmiando tempo.
        switch field[lower] {
        case 0, 9, 10, 11, 12, 13, 32: return nil
        default: break
        }

        // Invece di allocare memoria per una vera stringa in heap usiamo withUnsafeTemporaryAllocation
        // per creare un buffer temporaneo di byte (CChar) nello Stack (molto più veloce) che esiste 
        // solo per la durata di questa funzione.
        // Il +1 gestisce il terminatore alla fine che si aspetta strtod.
        let count = upper - lower
        return withUnsafeTemporaryAllocation(of: CChar.self, capacity: count + 1) { buf in
            let text = buf.baseAddress!
            UnsafeMutableRawPointer(text).copyMemory(from: field.baseAddress! + lower,
                                                     byteCount: count)
            text[count] = 0

            var result = 0.0
            // Richiamiamo strtod direttamente per salvarlo in result.
            guard let end = _swift_stdlib_strtod_clocale(text, &result),
            // end.pointee == 0: La funzione strtod restituisce un puntatore all'ultimo 
            // carattere che non è riuscita a leggere. Se questo puntatore coincide con 0
            // (il nostro null terminator), significa che tutto il testo è stato letto 
            // con successo ed era un numero valido.
                  end.pointee == 0 else { return nil }
            return result
        }
    }

Implementazione di `strtod` Prima di andare avanti va detta un'altra cosa; analizzando il runtime ho scoperto che Double(String) con Swift 6.4 non chiama più la strtod di libc: usa un parser suo, dentro il runtime. Lo si vede dai simboli che la libreria importa e dal comportamento. Il test quindi è fatto chiamando `_swift_stdlib_strtod_clocale` proprio per ottenere una baseline di riferimento valida, che non cambi le carte in tavola.</p>

Il risultato è:

┌────────────┬─────────────────────────┬─────────────────────────────┬───────┐ │ │ String + Double(String) │ stesso parser, senza String │ │ ├────────────┼─────────────────────────┼─────────────────────────────┼───────┤ │ stop_times │ 18.1 ns │ 13.0 ns │ 1.39x │ ├────────────┼─────────────────────────┼─────────────────────────────┼───────┤ │ shapes │ 23.2 ns │ 16.3 ns │ 1.42x │ └────────────┴─────────────────────────┴─────────────────────────────┴───────┘

Circa 1.4x, un quinto del guadagno ottenuto con i booleani.
La differenza non sta nell’intervento ma in ciò che resta dopo. Nei booleani la String era circa l’87% del costo e dopo averla tolta restava un confronto di pochi byte. Nei double la String pesa circa il 30%, e il restante 70% è il parser che fa lavoro vero: cifre, esponente, arrotondamento corretto.

Se il 70% del tempo è nel parser, la prossima domanda è se si può scrivere un parser migliore per i nostri dati…

Il percorso veloce

Un numero decimale è mantissa × 10^esponente. Se la mantissa ha al massimo 53 bit (≤ 2^53) e |esponente| ≤ 22, entrambi sono double esatti. Il risultato è allora una sola moltiplicazione o divisione IEEE, e IEEE garantisce che quell’operazione arrotondi correttamente.
Si ottengono gli stessi bit di un parser corretto qualsiasi, senza aritmetica a precisione multipla.

I dati del nostro GTFS rientrano in questo percorso veloce:

• 1167: mantissa 1167, esponente 0, una moltiplicazione per 1;
• 41.9120707735706: mantissa 419120707735706 (< 2^53 ≈ 9.007e15), esponente -13, una divisione.

Negli altri casi (>19 cifre, mantissa oltre 2^53, esponente fuori da ±22, nan, inf, hex, spazi…) finisce per essere masticato dal nostro fallback del paragrafo sopra.

    /// 10^0 ... 10^22: every power of ten a double represents exactly.
    private static let powersOfTen: [Double] = [
        1e0,  1e1,  1e2,  1e3,  1e4,  1e5,  1e6,  1e7,  1e8,  1e9,  1e10, 1e11,
        1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22,
    ]

    public static func doubleField(_ field: UnsafeBufferPointer<UInt8>, quoteByte: UInt8 = 0x22) -> Double? {
        var lower = 0
        var upper = field.count

        if upper >= 2, field[0] == quoteByte, field[upper - 1] == quoteByte {
            lower += 1
            upper -= 1
        }

        guard upper > lower else { return nil }

        if let value = fastPath(field, lower, upper) {
            return value
        }

        return Double(String(decoding: UnsafeBufferPointer(rebasing: field[lower..<upper]),
                             as: UTF8.self))
    }

    /// `[+-]digits[.digits][(e|E)[+-]digits]`, or nil when the input is outside the
    /// grammar or outside the exact range: nil here means "ask the standard
    /// library", not "not a number".
    @inline(__always)
    private static func fastPath(_ p: UnsafeBufferPointer<UInt8>, _ lower: Int, _ upper: Int) -> Double? {
        var i = lower
        var negative = false
        if p[i] == UInt8(ascii: "-") {
            negative = true
            i += 1
        } else if p[i] == UInt8(ascii: "+") {
            i += 1
        }

        // Digits before and after the dot go into the same integer; every digit
        // after the dot moves the decimal exponent one place down.
        var mantissa: UInt64 = 0
        var digits = 0
        var exponent = 0

        while i < upper {
            let d = p[i] &- 48
            guard d < 10 else { break }
            mantissa = mantissa &* 10 &+ UInt64(d)
            digits += 1
            i += 1
        }
        if i < upper, p[i] == UInt8(ascii: ".") {
            i += 1
            while i < upper {
                let d = p[i] &- 48
                guard d < 10 else { break }
                mantissa = mantissa &* 10 &+ UInt64(d)
                digits += 1
                exponent -= 1
                i += 1
            }
        }

        // 19 decimal digits always fit in a UInt64; past that the wrapping
        // arithmetic above has already overflowed, and the value is discarded.
        guard digits > 0, digits <= 19 else { return nil }

        if i < upper, (p[i] | 0x20) == UInt8(ascii: "e") {
            i += 1
            var exponentNegative = false
            if i < upper, p[i] == UInt8(ascii: "-") {
                exponentNegative = true
                i += 1
            } else if i < upper, p[i] == UInt8(ascii: "+") {
                i += 1
            }
            // At most four digits: anything longer is far outside ±22 anyway, and
            // stopping early leaves `i` short of `upper`, which means fallback.
            let start = i
            var e = 0
            while i < upper, i - start < 4 {
                let d = p[i] &- 48
                guard d < 10 else { break }
                e = e * 10 + Int(d)
                i += 1
            }
            guard i > start else { return nil }
            exponent += exponentNegative ? -e : e
        }

        guard i == upper,
              mantissa <= 1 << 53,
              exponent >= -22, exponent <= 22 else { return nil }

        let value = exponent < 0
            ? Double(mantissa) / powersOfTen[-exponent]
            : Double(mantissa) * powersOfTen[exponent]
        return negative ? -value : value
    }

Part 4 of 4

View all parts

• Part 1 When intuition lies: lessons from a CSV parser • Part 1: The 20-Second Trap
• Part 2 When intuition lies: lessons from a CSV parser • Part 2: Correct, Then Fast
• Part 3 When intuition lies: lessons from a CSV parser • Part 3: The 9%
• Part 4 When intuition lies: lessons from a CSV parser • Part 4: Parsing Booleans and Doubles

• #swift
• #craft

More on swift

• L'intuito mente: lezioni da un parser CSV — Parte 3: Il 9% Sep 2026
• 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