Python's mechanizm wewnętrznych łańcuchów znaków przechowuje tylko jedną kopię każdej distynkcyjnej wartości łańcucha w pamięci, umożliwiając porównania kluczy słownika przejście od porównań znak po znaku do porównań na podstawie porównania wskaźników. Kiedy kompilator CPython napotyka literały łańcuchów, które przypominają identyfikatory—konkretnie te zawierające tylko litery, cyfry i znaki podkreślenia—automatycznie je internuje w czasie kompilacji, przechowując je w globalnym słowniku internowanych łańcuchów. Ta optymalizacja pozwala algorytmowi wyszukiwania słownika najpierw sprawdzić tożsamość obiektu za pomocą operatora is, zanim przejdzie do bardziej kosztownego porównania ==, znacząco redukując złożoność czasową z O(n) do O(1) dla kluczy pasujących. Jednakże, łańcuchy utworzone w czasie wykonywania, takie jak te z wejścia od użytkownika lub konkatenacji, nie są automatycznie internowane, chyba że zostaną jawnie przekazane przez sys.intern(), co wymusza wstawienie do tabeli internacyjnej, jeśli nie są już obecne. Mechanizm ten opiera się na niemutowalności łańcuchów znakowych Pythona, aby zapewnić, że internowane łańcuchy pozostają bezpieczne do porównań opartych na tożsamości przez cały czas ich życia.
Zespół programistyczny budował usługę telemetryczną o wysokiej przezroczystości, która przetwarzała miliony ładunków JSON na godzinę, z których każdy zawierał powtarzające się klucze łańcuchów, takie jak "timestamp", "event_type" i "user_id". Podczas testów obciążeniowych, profilowanie pamięci ujawniło, że 35% sterty było zajmowane przez zduplikowane obiekty łańcuchów dla tych identycznych kluczy, podczas gdy profilowanie CPU pokazało znaczny czas spędzony w PyUnicode_RichCompare podczas wstawek i wyszukiwań w słowniku. Wąskim gardłem okazał się standardowy algorytm słownika porównujący zawartość łańcuchów zamiast adresów pamięci dla tych często powracających kluczy.
Jednym z rozważanych rozwiązań było ręczne wywołanie sys.intern() dla każdego klucza podczas fazy parsowania JSON. To podejście zapewniłoby, że wszystkie identyczne klucze dzieliłyby ten sam adres pamięci, co umożliwiłoby najszybsze operacje słownikowe poprzez porównania tożsamości. Jednak zespół zdał sobie sprawę, że wprowadza to znaczne zatory na globalnej tabeli internacyjnej w Pythonie 3.6 i naraża na nieograniczony wzrost pamięci, ponieważ internowane łańcuchy utrzymują się do momentu wyłączenia interpretera, co potencjalnie mogłoby doprowadzić do awarii usługi pod stałym obciążeniem.
Inne podejście polegało na wdrożeniu niestandardowej puli obiektów lub wzorca flyweight, aby ponownie używać instancji łańcuchów w warstwie aplikacji zamiast polegać na globalnej tabeli internacyjnej. Mimo że ta strategia oferowała większą kontrolę nad cyklem życia łańcuchów w puli i zapobiegała trwałej alokacji pamięci, wymagała owijania wszystkich wzorców dostępu do słownika i łamała zgodność z standardowymi bibliotekami Pythona, które oczekiwały prostych obiektów str. Dodatkowa złożoność i obciążenie konserwacyjne przewyższały korzyści wydajnościowe w tej konkretnej architekturze.
Zespół ostatecznie wybrał podejście z czarną listą, wdrażając middleware do parsowania, które stosowało sys.intern() tylko do wcześniej zdefiniowanego zestawu 50 kluczy o wysokiej częstotliwości, jednocześnie aktualizując do Pythona 3.10, aby zminimalizować zatory. Ta decyzja zrównoważyła wydajność pamięci z obawami o bezpieczeństwo, co przyniosło 40% redukcji użycia sterty i 18% poprawy w przepustowości żądań. Optymalizacja okazała się kluczowa dla osiągnięcia ich celów usługowych przy jednoczesnym utrzymaniu stabilności systemu w warunkach szczytowego obciążenia.
Dlaczego porównanie dwóch identycznych literałów łańcucha za pomocą is czasami zwraca False w sesjach interaktywnych, mimo że oba są automatycznie internowane?
Dzieje się tak, ponieważ kompilator CPython internuje łańcuchy tylko wtedy, gdy występują jako stałe w tym samym obiekcie kodu lub gdy pasują do wzorców identyfikatorów podczas kompilacji modułu. W interaktywnych powłokach każda linia kompilowana jest oddzielnie jako odrębny obiekt kodu, więc identyczne literały wpisane w różnych liniach mogą znajdować się w różnych adresach pamięci. Ponadto, łańcuchy przypominające identyfikatory, ale zawierające znaki nie-ASCII lub zaczynające się od cyfr, mogą nie być automatycznie internowane, co powoduje, że porównania za pomocą is zawodzą, nawet gdy == odnosi sukces.
Jakie są implikacje zarządzania pamięcią związane z internowaniem łańcuchów, które pochodzą z nieufnego wejścia od użytkownika, i dlaczego stanowi to potencjalny wektor potwierdzenia usługi?
Internowane łańcuchy w CPython są nieśmiertelne, co oznacza, że nigdy nie są zbierane przez garbage collector i przetrwają przez czas życia procesu interpretera. Jeśli aplikacja internuje dowolne dane wejściowe od użytkownika—takie jak nazwy użytkowników, adresy e-mail lub zapytania wyszukiwania—każdy unikalny łańcuch na stałe zużywa pamięć, która nie może być odzyskana. Atakujący mógłby to wykorzystać, wysyłając miliony unikalnych ładunków łańcuchowych, ostatecznie wyczerpując dostępną pamięć RAM i powodując awarię procesu, co czyni koniecznym oczyszczanie lub stosowanie czarnej listy dla danych wejściowych przed internowaniem.
Jak funkcja hash() współdziała z internowanymi łańcuchami podczas wstawiania do słownika, i czy internowanie wpływa na obliczenie wartości hasza?
Funkcja hash() oblicza swoją wartość opierając się wyłącznie na zawartości łańcucha, a nie na jego tożsamości lub statusie internowania, co oznacza, że internowanie nie zmienia wartości hasza łańcucha. Jednak implementacja słownika w CPython zawiera optymalizację, gdzie po porównaniu wartości haszy sprawdza tożsamość obiektu (is) przed przejściem do pełnego porównania równości (==). Dla identycznych internowanych łańcuchów, to sprawdzenie tożsamości natychmiast zwraca True, omijając porównanie O(n) znak po znaku, chociaż kandydaci często mylą to, wierząc, że internowanie zmienia sam algorytm haszowania.