Questa decisione di design ha origine dall'impegno fondamentale di Swift per le semantiche di valore per le collezioni della libreria standard. A differenza di NSMutableDictionary di Objective-C o di std::unordered_map di C++, che espongono semantiche di riferimento o consentono puntatori esterni a nodi interni, Swift tratta Dictionary e Set come tipi di valore puri. Quando Swift ha adottato ottimizzazioni Copy-on-Write (COW) per queste collezioni al fine di ottenere prestazioni di tipo riferimento pur mantenendo la sicurezza di tipo valore, il team di ingegneria si è trovato di fronte a una decisione critica riguardo alla stabilità degli indici. La risoluzione di invalidare gli indici in seguito a mutazione è stata formalizzata per evitare riferimenti pendenti a memoria riallocata durante la crescita della tabella hash, la risoluzione di collisioni o la cancellazione di voci.
Il problema centrale emerge dall'interazione tra la semantica COW e i dettagli dell'implementazione della tabella hash. Quando un Dictionary si muta tramite inserimento o cancellazione, può attivare un ridimensionamento se il fattore di carico supera le soglie, allocando un nuovo buffer più grande e ri-hashing di tutte le voci. Qualsiasi valore Index esistente creato prima della mutazione incapsula un offset o puntatore nella memoria fisica del vecchio buffer. Se quell'indice venisse accesso dopo la mutazione, dereferenzerebbe la memoria deallocata (use-after-free) o restituirebbe dati da bucket errati. Poiché Swift non può tracciare la vita di ogni valore Index attraverso copie indipendenti del Dictionary (le semantiche di valore consentono la copia illimitata), non può aggiornare in modo sicuro tutti gli indici pendenti. Pertanto, il linguaggio deve dichiarare tali indici non validi per mantenere le garanzie di sicurezza della memoria.
Swift risolve questo incorporando un conteggio di generazione o un numero di versione all'interno dell'intestazione dello storage interno del Dictionary. Ogni Index cattura questo identificatore di generazione al momento della creazione. Quando il Dictionary si muta, il runtime incrementa questo conteggio di generazione e potenzialmente rialloca il buffer sottostante. Qualsiasi uso successivo di un Index obsoleto confronta la sua generazione memorizzata con l'attuale; una discrepanza provoca un errore di runtime deterministico (fallimento della precondizione). Questo approccio sacrifica la stabilità degli indici attraverso le mutazioni a favore della sicurezza della memoria e dell'integrità delle semantiche di valore. Per l'ottimizzazione COW, il runtime controlla i conteggi di riferimento prima della mutazione: se referenziato unicamente, si muta in loco (invalidando gli indici); se condiviso, copia prima il buffer, mantenendo validi gli indici dell'istanza originale mentre la nuova copia riceve un nuovo conteggio di generazione.
var marketData: [String: Double] = ["AAPL": 150.0, "GOOGL": 2800.0] let indexBeforeUpdate = marketData.index(forKey: "AAPL")! // Generazione 0 marketData["TSLA"] = 700.0 // La mutazione incrementa la generazione, potrebbe riallocare // Errore di runtime: tentativo di accesso utilizzando un indice non valido dalla generazione 0 // let price = marketData[indexBeforeUpdate]
Un team di sviluppo stava costruendo un cruscotto di trading ad alta frequenza utilizzando Swift su iPad, utilizzando un Dictionary per memorizzare i dati dei prezzi live con i simboli ticker String come chiavi. Per ottimizzare le prestazioni di rendering dell'interfaccia durante gli aggiornamenti rapidi, memorizzavano indici diretti del Dictionary all'interno dei loro modelli di vista per evitare ripetute calcolazioni hash durante la configurazione delle celle della vista tabella. Tuttavia, quando i thread WebSocket in background inserivano nuovi punti di prezzo nel dizionario, l'applicazione mostrava crash sporadici con EXC_BAD_ACCESS o visualizzava dati corrotti da aree di memoria deallocate, poiché gli indici memorizzati facevano riferimento a bucket della tabella hash che erano stati riallocati durante le operazioni di ridimensionamento.
La prima soluzione considerata prevedeva la migrazione a NSMutableDictionary da Foundation, che offre semantiche di riferimento e riferimenti stabili agli oggetti piuttosto che semantiche di valore. Questo approccio avrebbe consentito al team di mantenere riferimenti persistenti alle voci indipendentemente dalle mutazioni del dizionario, preservando una stabilità simile agli indici durante l'intero ciclo di vita dell'applicazione. Tuttavia, questo introduceva semantiche di riferimento che rompevano l'isolamento nei tipi di valore tra i modelli di vista, portando a condivisioni di dati indesiderate e condizioni di gara durante la copia dei dizionari tra code in background e il thread principale. Inoltre, NSMutableDictionary manca della sicurezza dei tipi generici di Swift e richiede un costoso overhead di bridging per i tipi di valore come le istanze struct, costringendo operazioni di boxing che degradavano le prestazioni.
La seconda soluzione esplorava l'implementazione di una tabella hash di open-addressing personalizzata utilizzando UnsafeMutablePointer per gestire manualmente gli indirizzi di memoria dei nodi stabili, eludendo completamente il meccanismo di invalidazione degli indici di Swift. Questo avrebbe fornito stabilità dei puntatori deterministica per gli indici memorizzati, consentendo accessi O(1) senza il sovraccarico del rehash durante le ricerche. Tuttavia, questo approccio richiedeva la gestione manuale della memoria con malloc e free, introducendo rischi significativi di perdite di memoria se i nodi non venivano deallocati correttamente alla rimozione. Inoltre, eludeva le ottimizzazioni COW di Swift, il che significava che ogni copia del dizionario richiedeva una copia profonda completa del buffer allocato nel heap, distruggendo le prestazioni per dataset che superavano le diecimila voci.
Alla fine, il team scelse la terza soluzione: eliminare completamente la cache degli indici e invece memorizzare array di chiavi (String ticker) nei propri modelli di vista, eseguendo ricerche basate su chiave durante ogni ciclo di configurazione delle celle. Questo approccio è stato selezionato poiché manteneva le semantiche di valore di Swift e le garanzie di sicurezza della memoria pur offrendo prestazioni di ricerca O(1) nel caso medio. Sebbene ciò comportasse il costo di dover rehashare la chiave ad ogni accesso, l'hashing delle stringhe in Swift è altamente ottimizzato tramite SipHash, e le garanzie di sicurezza superavano la trascurabile penalità di prestazioni a livello di microsecondi. Hanno anche adottato il tipo OrderedDictionary dal pacchetto open-source Swift Collections per fornire un ordinamento deterministico senza fare affidamento su indici instabili.
Il risultato è stata una completa eliminazione dei crash EXC_BAD_ACCESS durante il successivo periodo di monitoraggio di tre mesi. L'impronta di memoria dell'applicazione è rimasta stabile anche con 50.000 voci di prezzo concorrenti, e il codice è diventato significativamente più manutenibile senza la complessità delle operazioni UnsafeMutablePointer. Il team ha stabilito una rigorosa linea guida architettonica che proibisce la memorizzazione di indici di Dictionary o Set attraverso qualsiasi confine di mutazione, documentando questo schema nel loro wiki interno per prevenire regressioni future.
Perché l'Array di Swift consente il riutilizzo degli indici dopo alcune mutazioni mentre il Dictionary no, nonostante entrambi siano tipi di valore con semantiche COW?
Gli indici di Array sono valori Int leggeri che rappresentano offset da un indirizzo base in uno storage contiguo. Sebbene le mutazioni di Array che attivano la riallocazione (come l'aggiunta oltre la capacità) invalidino tecnicamente gli indici spostando il buffer, gli indici di Array non portano metadati di generazione per la validazione, rendendoli pericolosi da memorizzare ma non esplicitamente controllati. Gli indici di Dictionary, invece, incapsulano uno stato interno complesso, inclusi offset dei bucket all'interno di una tabella hash sparsa. Poiché le voci della tabella hash si spostano in modo imprevisto durante il rehashing (attivato da soglie del fattore di carico o risoluzione delle collisioni), gli offset interi perdono significato semantico. Swift potrebbe teoricamente implementare un'indirizzazione logica degli indici per Dictionary, ma questo richiederebbe una caccia a puntatore aggiuntiva che rallenterebbe ogni accesso. Pertanto, Dictionary e Set convalidano e invalidano aggressivamente gli indici tramite conteggi di generazione, mentre gli indici di Array si basano sul programmatore per garantire la validità, riflettendo i diversi compromessi di prestazioni e sicurezza tra storage contigui e hashati.
Come determina il meccanismo Copy-on-Write se una mutazione del Dictionary richiede l'invalidazione degli indici sull'istanza corrente rispetto alla creazione di una nuova copia con nuovi indici?
Swift utilizza il conteggio dei riferimenti sul buffer interno (_NativeDictionary). Prima di qualsiasi mutazione, il runtime invoca isUniquelyReferencedNonObjC per controllare il conteggio dei riferimenti del buffer. Se il conteggio è uguale a uno (proprietà unica), la mutazione avviene in loco, invalidando solo gli indici su questa specifica istanza incrementando il conteggio di generazione. Se il conteggio dei riferimenti è superiore a uno (proprietà condivisa), Swift allocca un nuovo buffer, copia tutti gli elementi ed esegue la mutazione sulla nuova copia. L'istanza originale rimane invariata con indici validi, mentre la nuova copia inizia con un nuovo conteggio di generazione (effettivamente indice zero). Questa distinzione è cruciale per le semantiche di valore: dopo un'assegnazione di valore, entrambe le variabili condividono lo storage fino a quando una di esse si muta, attivando la copia pigra. Il punto di mutazione è dove si verifica la separazione logica, assicurando che l'istanza mutante abbia una proprietà unica prima della modifica.
È possibile eludere l'invalidazione dell'indice del Dictionary di Swift utilizzando withUnsafeMutablePointer o Unmanaged per accedere allo storage raw, e quali rischi catastrofici introduce questo?
Tecnicamente, UnsafeMutablePointer e Unmanaged possono fornire accesso diretto allo storage sottostante di un Dictionary tramite withUnsafeMutablePointer allo storage interno o tramite il casting del Dictionary in byte raw. Tuttavia, questo costituisce un comportamento indefinito. Il layout interno del Dictionary è opaco e soggetto a cambiamenti tra le versioni di Swift (resilienza). La manipolazione diretta del puntatore elude i controlli di conteggio di generazione, consentendo l'accesso a memoria deallocata se è avvenuta una riallocazione durante un ridimensionamento. Inoltre, le tabelle hash mantengono complessi vincoli riguardanti bitmap di occupazione e marcatori di tombstone per le voci cancellate. La manipolazione manuale dei puntatori può corrompere questi vincoli, portando a loop infiniti durante le sequenze di probing, corruzione silenziosa dei dati o crash nelle operazioni successive del Dictionary. Il modello di sicurezza di Swift lo vieta esplicitamente; l'unico meccanismo sicuro per mantenere riferimenti stabili è utilizzare chiavi (che vengono rehashed ad ogni accesso) oppure copiare i valori dalla collezione in un array separato.