Ta decyzja projektowa pochodzi z fundamentalnego zaangażowania Swift w semantykę wartości dla kolekcji standardowej biblioteki. W przeciwieństwie do Objective-C's NSMutableDictionary lub C++'s std::unordered_map, które ujawniają semantykę referencyjną lub pozwalają na zewnętrzne wskaźniki do wewnętrznych węzłów, Swift traktuje Dictionary i Set jako czyste typy wartości. Kiedy Swift przyjął optymalizacje Copy-on-Write (COW) dla tych kolekcji w celu osiągnięcia wydajności typu referencyjnego przy zachowaniu bezpieczeństwa typów wartości, zespół inżynierski stanął przed krytyczną decyzją dotyczącą stabilności indeksu. Rozwiązanie dotyczące unieważnienia indeksów po mutacji zostało sformalizowane w celu zapobieżenia wiszącym referencjom do przeniesionej pamięci podczas wzrostu tabeli haszy, rozwiązywania kolizji lub usuwania wpisów.
Główny problem wynika z interakcji między semantyką COW a szczegółami implementacji tabeli haszy. Kiedy Dictionary mutuje przez dodanie lub usunięcie, może wywołać zmianę rozmiaru, jeśli współczynnik obciążenia przekroczy progi, alokując nowy, większy bufor i ponownie haszując wszystkie wpisy. Każda istniejąca wartość Index stworzona przed mutacją encapsuluje offset lub wskaźnik do fizycznej pamięci starego bufora. Jeśli ten indeks zostałby użyty po mutacji, odwołałby się do zwolnionej pamięci (use-after-free) lub zwrócił dane z niepoprawnych pojemników. Ponieważ Swift nie może śledzić czasu życia każdej wartości Index w niezależnych kopiach Dictionary (semantyka wartości pozwala na nieograniczone kopiowanie), nie może bezpiecznie zaktualizować wszystkich aktualnych indeksów. Dlatego język musi uznać takie indeksy za nieważne, aby utrzymać gwarancje bezpieczeństwa pamięci.
Swift rozwiązuje to, wbudowując liczbę pokoleń lub numer wersji w nagłówku wewnętrznego przechowywania Dictionary. Każdy Index uchwyca ten identyfikator pokoleniowy w momencie tworzenia. Kiedy Dictionary mutuje, mechanizm uruchamiający zwiększa tę liczbę pokoleń i potencjalnie alokuje nowy bufor. Każde późniejsze użycie przestarzałego Index porównuje jego przechowywaną generację z aktualną; niezgodność wywołuje deterministyczny błąd czasu wykonywania (błąd prekoncycji). To podejście poświęca stabilność indeksu podczas mutacji na rzecz bezpieczeństwa pamięci i integralności semantyki wartości. Dla optymalizacji COW mechanizm sprawdza liczby referencji przed mutacją: jeśli jest unikalnie odniesiony, mutuje na miejscu (unieważniając indeksy); jeśli jest współdzielony, najpierw kopiuje bufor, pozostawiając indeksy oryginalnej instancji ważne, podczas gdy nowa kopia otrzymuje nową liczbę pokoleń.
var marketData: [String: Double] = ["AAPL": 150.0, "GOOGL": 2800.0] let indexBeforeUpdate = marketData.index(forKey: "AAPL")! // Pokolenie 0 marketData["TSLA"] = 700.0 // Mutacja zwiększa pokolenie, może ponownie przydzielić // Błąd czasu działania: próba dostępu za pomocą nieważnego indeksu z pokolenia 0 // let price = marketData[indexBeforeUpdate]
Zespół deweloperów budował pulpit nawigacyjny do handlu o wysokiej częstotliwości, korzystając z Swift na iPadzie, wykorzystując Dictionary do buforowania danych o cenach na żywo z symbolami giełdowymi String jako kluczami. Aby zoptymalizować wydajność renderowania UI podczas szybkich aktualizacji, przechowywali bezpośrednie indeksy Dictionary w swoich modelach widoków, aby uniknąć powtarzających się obliczeń haszujących podczas konfigurowania komórek tabeli widoków. Jednak, gdy wątki WebSocket w tle wstawiały nowe punkty cenowe do słownika, aplikacja wykazywała sporadyczne awarie z błędami EXC_BAD_ACCESS lub wyświetlała uszkodzone dane z obszarów pamięci, które zostały zwolnione, ponieważ buforowane indeksy odnosiły się do pojemników tabeli haszy, które zostały ponownie przydzielone podczas operacji zmiany rozmiaru.
Pierwszym rozważanym rozwiązaniem było migracja do NSMutableDictionary z Foundation, który zapewnia semantykę referencyjną i stabilne referencje obiektowe, a nie semantykę wartości. Takie podejście pozwoliłoby zespołowi zachować trwałe odniesienia do wpisów, niezależnie od mutacji słownika, zachowując stabilność indeksów w całym cyklu życia aplikacji. Jednak wprowadziło to semantykę referencyjną, która złamała izolację typów wartości między modelami widoków, prowadząc do niezamierzonego współdzielenia danych i warunków wyścigu podczas kopiowania słowników między kolejkami w tle a wątkiem głównym. Dodatkowo, NSMutableDictionary nie ma bezpieczeństwa typów generycznych Swift'a i wymaga kosztownego mostu dla typów wartości, takich jak instancje struct, wymuszając operacje kodowania, które pogarszały wydajność.
Drugie rozwiązanie polegało na wdrożeniu niestandardowej tabeli haszy z otwartym adresem przy użyciu UnsafeMutablePointer, aby ręcznie zarządzać stabilnymi adresami pamięci węzłów, omijając w ten sposób mechanizm unieważnienia indeksów Swift. To zapewniłoby deterministyczną stabilność wskaźników dla przechowywanych indeksów, umożliwiając dostęp O(1) bez obciążenia ponownego haszowania podczas wyszukiwania. Jednak to podejście wymagało ręcznego zarządzania pamięcią z użyciem malloc i free, wprowadzając znaczne ryzyko wycieków pamięci, jeśli węzły nie byłyby odpowiednio zwalniane po usunięciu. Ominęło to również optymalizacje COW w Swift, co oznacza, że każda kopia słownika wymagałaby pełnej głębokiej kopii bufora alokowanego na stercie, co niszczyło wydajność dla zbiorów danych przekraczających dziesięć tysięcy wpisów.
Zespół ostatecznie wybrał trzecie rozwiązanie: całkowite eliminację buforowania indeksów i zamiast tego przechowywanie tablic kluczy (String tickerów) w swoich modelach widoków, wykonując wyszukiwania na podstawie kluczy podczas każdego cyklu konfigurowania komórek. To podejście zostało wybrane, ponieważ zachowało semantykę wartości i gwarancje bezpieczeństwa pamięci Swift`, jednocześnie nadal zapewniając wydajność średniego przypadku O(1). Chociaż wiązało się to z kosztami ponownego haszowania klucza przy każdym dostępie, nowoczesne haszowanie ciągów w Swift jest bardzo zoptymalizowane dzięki SipHash, a gwarancje bezpieczeństwa przewyższały znikomy mikrosekundowy koszt wydajności. Przyjęli również typ OrderedDictionary z pakietu Swift Collections, aby zapewnić deterministyczne porządkowanie bez polegania na niestabilnych indeksach.
Rezultatem było całkowite wyeliminowanie awarii EXC_BAD_ACCESS podczas następnego trzy miesięcznego okresu monitorowania. Pamięć aplikacji pozostała stabilna, nawet z 50,000 równoległymi wpisami cenowymi, a baza kodu stała się znacząco bardziej utrzymywalna bez złożoności operacji UnsafeMutablePointer. Zespół ustanowił surowe wytyczne architektoniczne zabraniające przechowywania indeksów Dictionary lub Set przez jakiekolwiek granice mutacji, dokumentując ten wzór w swojej wewnętrznej wiki, aby zapobiec przyszłym regresom.
Dlaczego tablica Swift'a pozwala na ponowne użycie indeksów po jakichś mutacjach, podczas gdy Dictionary tego nie robi, mimo że oba są typami wartości z semantyką COW?
Indeksy Array są lekkimi wartościami Int, które reprezentują odległości od podstawowego adresu w ciągłym przechowywaniu. Mimo że mutacje Array, które prowadzą do ponownej alokacji (takie jak dodanie ponad pojemność), technicznie unieważniają indeksy poprzez przeniesienie bufora, indeksy Array nie przenoszą metadanych dotyczących pokolenia do walidacji, co czyni je niebezpiecznymi do buforowania, ale nie są weryfikowane explicite. Indeksy Dictionary jednak encapsuluje złożony stan wewnętrzny, w tym offsety pojemników w rzadkiej tabeli haszy. Ponieważ wprowadzenia do tabeli haszy przemieszczają się nieprzewidywalnie podczas ponownego haszowania (wywołanego przez progi współczynnika obciążenia lub rozwiązywanie kolizji), całkowite offsety tracą znaczenie semantyczne. Swift teoretycznie mógłby zaimplementować logiczną indykację indeksu dla Dictionary, ale wymagałoby to dodatkowego ścigania wskaźników, co spowolniłoby każdy dostęp. Dlatego Dictionary i Set agresywnie weryfikują i unieważniają indeksy za pomocą liczby pokoleń, podczas gdy indeksy Array polegają na programiście, aby zapewnić ważność, co odzwierciedla różne kompromisy wydajności i bezpieczeństwa między ciągłym i haszowanym przechowywaniem.
Jak mechanizm Copy-on-Write ustala, czy mutacja Dictionary wymaga unieważnienia indeksu w bieżącej instancji, czy stworzenia nowej kopii z nowymi indeksami?
Swift wykorzystuje zliczanie referencji do wewnętrznego bufora (_NativeDictionary). Przed jakąkolwiek mutacją, mechanizm uruchamiający wywołuje isUniquelyReferencedNonObjC, aby sprawdzić liczbę referencji bufora. Jeśli liczba wynosi jeden (unikatowe posiadanie), mutacja odbywa się na miejscu, unieważniając tylko indeksy w tej konkretnej instancji poprzez zwiększenie liczby pokoleń. Jeśli liczba referencji przekracza jeden (wspólne posiadanie), Swift alokuje nowy bufor, kopiuje wszystkie elementy i realizuje mutację na nowej kopii. Oryginalna instancja pozostaje niezmieniona z ważnymi indeksami, podczas gdy nowa kopia zaczyna z nową liczbą pokoleń (efektywnie indeksem zero). Ta różnica jest kluczowa dla semantyki wartości: po przypisaniu wartości, obie zmienne dzielą przechowywaną pamięć, aż jedna z nich mutuje, wyzwalając leniwą kopię. Punkt mutacji to miejsce, w którym następuje logiczny podział, zapewniając, że mutująca instancja ma unikalne posiadanie przed modyfikacją.
Czy unieważnienie indeksów w słowniku Swift'a można obejść za pomocą withUnsafeMutablePointer lub Unmanaged, aby uzyskać dostęp do surowego przechowywania i jakie katastrofalne ryzyka to wprowadza?
Teoretycznie, UnsafeMutablePointer i Unmanaged mogą zapewnić bezpośredni dostęp do podstawowego przechowywania Dictionary za pomocą withUnsafeMutablePointer do wewnętrznego przechowywania lub przez rzutowanie Dictionary na surowe bajty. Jednak to stanowi nieokreślone zachowanie. Wewnętrzny układ Dictionary jest nieprzezroczysty i podlega zmianom między wersjami Swift (odporność). Bezpośrednia manipulacja wskaźnikami omija sprawdzenie liczby pokoleń, pozwalając na dostęp do zwolnionej pamięci, jeśli miała miejsce ponowna alokacja podczas zmiany rozmiaru. Ponadto tabele haszy utrzymują skomplikowane inwarianty dotyczące bitmap zajętości i znaczników grobów dla usuniętych wpisów. Ręczna manipulacja wskaźnikami może zniszczyć te inwarianty, prowadząc do nieskończonych pętli podczas sekwencji przeszukiwania, cichej korupcji danych lub awarii w kolejnych operacjach Dictionary. Model bezpieczeństwa Swift wyraźnie zabrania tego; jedynym bezpiecznym mechanizmem utrzymania stabilnych referencji jest użycie kluczy (które są ponownie haszowane przy każdym dostępie) lub kopiowanie wartości z kolekcji do osobnej tablicy.