Skip to content

Commit 352cfd9

Browse files
ericsnowcurrentlyericsnowcurrently
committed
[3.12] gh-106931: Intern Statically Allocated Strings Globally (gh-107272)
We tried this before with a dict and for all interned strings. That ran into problems due to interpreter isolation. However, exclusively using a per-interpreter cache caused some inconsistency that can eliminate the benefit of interning. Here we circle back to using a global cache, but only for statically allocated strings. We also use a more-basic _Py_hashtable_t for that global cache instead of a dict. Ideally we would only have the global cache, but the optional isolation of each interpreter's allocator means that a non-static string object must not outlive its interpreter. Thus we would have to store a copy of each such interned string in the global cache, tied to the main interpreter. (cherry-picked from commit b72947a)
1 parent 71c96b5 commit 352cfd9

File tree

10 files changed

+123
-4
lines changed

10 files changed

+123
-4
lines changed

‎Include/cpython/unicodeobject.h

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -140,9 +140,11 @@ typedef struct {
140140
and the kind is PyUnicode_1BYTE_KIND. If ascii is set and compact is
141141
set, use the PyASCIIObject structure. */
142142
unsigned int ascii:1;
143+
/* The object is statically allocated. */
144+
unsigned int statically_allocated:1;
143145
/* Padding to ensure that PyUnicode_DATA() is always aligned to
144146
4 bytes (see issue #19537 on m68k). */
145-
unsigned int :25;
147+
unsigned int :24;
146148
} state;
147149
} PyASCIIObject;
148150

‎Include/internal/pycore_global_objects.h

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ extern "C" {
88
# error "this header requires Py_BUILD_CORE define"
99
#endif
1010

11+
#include "pycore_hashtable.h" // _Py_hashtable_t
1112
#include "pycore_gc.h" // PyGC_Head
1213
#include "pycore_global_strings.h" // struct _Py_global_strings
1314
#include "pycore_hamt.h" // PyHamtNode_Bitmap
@@ -28,6 +29,11 @@ extern "C" {
2829
#define _Py_SINGLETON(NAME) \
2930
_Py_GLOBAL_OBJECT(singletons.NAME)
3031

32+
struct _Py_cached_objects {
33+
// XXX We could statically allocate the hashtable.
34+
_Py_hashtable_t *interned_strings;
35+
};
36+
3137
struct _Py_static_objects {
3238
struct {
3339
/* Small integers are preallocated in this array so that they

‎Include/internal/pycore_hashtable.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -106,6 +106,7 @@ PyAPI_FUNC(int) _Py_hashtable_foreach(
106106
void *user_data);
107107

108108
PyAPI_FUNC(size_t) _Py_hashtable_size(const _Py_hashtable_t *ht);
109+
PyAPI_FUNC(size_t) _Py_hashtable_len(const _Py_hashtable_t *ht);
109110

110111
/* Add a new entry to the hash. The key must not be present in the hash table.
111112
Return 0 on success, -1 on memory error. */

‎Include/internal/pycore_runtime.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -157,6 +157,7 @@ typedef struct pyruntimestate {
157157
struct _types_runtime_state types;
158158

159159
/* All the objects that are shared by the runtime's interpreters. */
160+
struct _Py_cached_objects cached_objects;
160161
struct _Py_static_objects static_objects;
161162

162163
/* The following fields are here to avoid allocation during init.

‎Include/internal/pycore_runtime_init.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,7 @@ extern PyTypeObject _PyExc_MemoryError;
164164
.kind = 1, \
165165
.compact = 1, \
166166
.ascii = (ASCII), \
167+
.statically_allocated = 1, \
167168
}, \
168169
}
169170
#define _PyASCIIObject_INIT(LITERAL) \

‎Lib/test/test_sys.py

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@
1515
from test.support.script_helper import assert_python_ok, assert_python_failure
1616
from test.support import threading_helper
1717
from test.support import import_helper
18+
from test.support import interpreters
1819
import textwrap
1920
import unittest
2021
import warnings
@@ -699,6 +700,35 @@ def __hash__(self):
699700

700701
self.assertRaises(TypeError, sys.intern, S("abc"))
701702

703+
def test_subinterp_intern_dynamically_allocated(self):
704+
global INTERN_NUMRUNS
705+
INTERN_NUMRUNS += 1
706+
s = "never interned before" + str(INTERN_NUMRUNS)
707+
t = sys.intern(s)
708+
self.assertIs(t, s)
709+
710+
interp = interpreters.create()
711+
interp.run(textwrap.dedent(f'''
712+
import sys
713+
t = sys.intern({s!r})
714+
assert id(t) != {id(s)}, (id(t), {id(s)})
715+
assert id(t) != {id(t)}, (id(t), {id(t)})
716+
'''))
717+
718+
def test_subinterp_intern_statically_allocated(self):
719+
# See Tools/build/generate_global_objects.py for the list
720+
# of strings that are always statically allocated.
721+
s = '__init__'
722+
t = sys.intern(s)
723+
724+
print('------------------------')
725+
interp = interpreters.create()
726+
interp.run(textwrap.dedent(f'''
727+
import sys
728+
t = sys.intern({s!r})
729+
assert id(t) == {id(t)}, (id(t), {id(t)})
730+
'''))
731+
702732
def test_sys_flags(self):
703733
self.assertTrue(sys.flags)
704734
attrs = ("debug",

‎Misc/NEWS.d/next/Core and Builtins/2023-07-25-15-29-26.gh-issue-106931.kKU1le.rst

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
Statically allocated string objects are now interned globally instead of
2+
per-interpreter. This fixes a situation where such a string would only be
3+
interned in a single interpreter. Normal string objects are unaffected.

‎Objects/unicodeobject.c

Lines changed: 69 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -235,15 +235,54 @@ static inline PyObject *get_interned_dict(PyInterpreterState *interp)
235235
return _Py_INTERP_CACHED_OBJECT(interp, interned_strings);
236236
}
237237

238+
#define INTERNED_STRINGS _PyRuntime.cached_objects.interned_strings
239+
238240
Py_ssize_t
239241
_PyUnicode_InternedSize(void)
240242
{
241-
return PyObject_Length(get_interned_dict(_PyInterpreterState_GET()));
243+
PyObject *dict = get_interned_dict(_PyInterpreterState_GET());
244+
return _Py_hashtable_len(INTERNED_STRINGS) + PyDict_GET_SIZE(dict);
245+
}
246+
247+
static Py_hash_t unicode_hash(PyObject *);
248+
static int unicode_compare_eq(PyObject *, PyObject *);
249+
250+
static Py_uhash_t
251+
hashtable_unicode_hash(const void *key)
252+
{
253+
return unicode_hash((PyObject *)key);
254+
}
255+
256+
static int
257+
hashtable_unicode_compare(const void *key1, const void *key2)
258+
{
259+
PyObject *obj1 = (PyObject *)key1;
260+
PyObject *obj2 = (PyObject *)key2;
261+
if (obj1 != NULL && obj2 != NULL) {
262+
return unicode_compare_eq(obj1, obj2);
263+
}
264+
else {
265+
return obj1 == obj2;
266+
}
242267
}
243268

244269
static int
245270
init_interned_dict(PyInterpreterState *interp)
246271
{
272+
if (_Py_IsMainInterpreter(interp)) {
273+
assert(INTERNED_STRINGS == NULL);
274+
_Py_hashtable_allocator_t hashtable_alloc = {PyMem_RawMalloc, PyMem_RawFree};
275+
INTERNED_STRINGS = _Py_hashtable_new_full(
276+
hashtable_unicode_hash,
277+
hashtable_unicode_compare,
278+
NULL,
279+
NULL,
280+
&hashtable_alloc
281+
);
282+
if (INTERNED_STRINGS == NULL) {
283+
return -1;
284+
}
285+
}
247286
assert(get_interned_dict(interp) == NULL);
248287
PyObject *interned = interned = PyDict_New();
249288
if (interned == NULL) {
@@ -262,6 +301,10 @@ clear_interned_dict(PyInterpreterState *interp)
262301
Py_DECREF(interned);
263302
_Py_INTERP_CACHED_OBJECT(interp, interned_strings) = NULL;
264303
}
304+
if (_Py_IsMainInterpreter(interp) && INTERNED_STRINGS != NULL) {
305+
_Py_hashtable_destroy(INTERNED_STRINGS);
306+
INTERNED_STRINGS = NULL;
307+
}
265308
}
266309

267310
#define _Py_RETURN_UNICODE_EMPTY() \
@@ -1222,6 +1265,7 @@ PyUnicode_New(Py_ssize_t size, Py_UCS4 maxchar)
12221265
_PyUnicode_STATE(unicode).kind = kind;
12231266
_PyUnicode_STATE(unicode).compact = 1;
12241267
_PyUnicode_STATE(unicode).ascii = is_ascii;
1268+
_PyUnicode_STATE(unicode).statically_allocated = 0;
12251269
if (is_ascii) {
12261270
((char*)data)[size] = 0;
12271271
}
@@ -1552,7 +1596,9 @@ unicode_dealloc(PyObject *unicode)
15521596
* we accidentally decref an immortal string out of existence. Since
15531597
* the string is an immortal object, just re-set the reference count.
15541598
*/
1555-
if (PyUnicode_CHECK_INTERNED(unicode)) {
1599+
if (PyUnicode_CHECK_INTERNED(unicode)
1600+
|| _PyUnicode_STATE(unicode).statically_allocated)
1601+
{
15561602
_Py_SetImmortal(unicode);
15571603
return;
15581604
}
@@ -14502,6 +14548,7 @@ unicode_subtype_new(PyTypeObject *type, PyObject *unicode)
1450214548
_PyUnicode_STATE(self).kind = kind;
1450314549
_PyUnicode_STATE(self).compact = 0;
1450414550
_PyUnicode_STATE(self).ascii = _PyUnicode_STATE(unicode).ascii;
14551+
_PyUnicode_STATE(self).statically_allocated = 0;
1450514552
_PyUnicode_UTF8_LENGTH(self) = 0;
1450614553
_PyUnicode_UTF8(self) = NULL;
1450714554
_PyUnicode_DATA_ANY(self) = NULL;
@@ -14725,6 +14772,23 @@ _PyUnicode_InternInPlace(PyInterpreterState *interp, PyObject **p)
1472514772
return;
1472614773
}
1472714774

14775+
/* Look in the global cache first. */
14776+
PyObject *r = (PyObject *)_Py_hashtable_get(INTERNED_STRINGS, s);
14777+
if (r != NULL && r != s) {
14778+
Py_SETREF(*p, Py_NewRef(r));
14779+
return;
14780+
}
14781+
14782+
/* Handle statically allocated strings. */
14783+
if (_PyUnicode_STATE(s).statically_allocated) {
14784+
assert(_Py_IsImmortal(s));
14785+
if (_Py_hashtable_set(INTERNED_STRINGS, s, s) == 0) {
14786+
_PyUnicode_STATE(*p).interned = SSTATE_INTERNED_IMMORTAL_STATIC;
14787+
}
14788+
return;
14789+
}
14790+
14791+
/* Look in the per-interpreter cache. */
1472814792
PyObject *interned = get_interned_dict(interp);
1472914793
assert(interned != NULL);
1473014794

@@ -14740,9 +14804,11 @@ _PyUnicode_InternInPlace(PyInterpreterState *interp, PyObject **p)
1474014804
}
1474114805

1474214806
if (_Py_IsImmortal(s)) {
14807+
// XXX Restrict this to the main interpreter?
1474314808
_PyUnicode_STATE(*p).interned = SSTATE_INTERNED_IMMORTAL_STATIC;
14744-
return;
14809+
return;
1474514810
}
14811+
1474614812
#ifdef Py_REF_DEBUG
1474714813
/* The reference count value excluding the 2 references from the
1474814814
interned dictionary should be excluded from the RefTotal. The

‎Python/hashtable.c

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -128,6 +128,13 @@ _Py_hashtable_size(const _Py_hashtable_t *ht)
128128
}
129129

130130

131+
size_t
132+
_Py_hashtable_len(const _Py_hashtable_t *ht)
133+
{
134+
return ht->nentries;
135+
}
136+
137+
131138
_Py_hashtable_entry_t *
132139
_Py_hashtable_get_entry_generic(_Py_hashtable_t *ht, const void *key)
133140
{

‎Tools/build/deepfreeze.py

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -208,6 +208,7 @@ def generate_unicode(self, name: str, s: str) -> str:
208208
self.write(".kind = 1,")
209209
self.write(".compact = 1,")
210210
self.write(".ascii = 1,")
211+
self.write(".statically_allocated = 1,")
211212
self.write(f"._data = {make_string_literal(s.encode('ascii'))},")
212213
return f"& {name}._ascii.ob_base"
213214
else:
@@ -220,6 +221,7 @@ def generate_unicode(self, name: str, s: str) -> str:
220221
self.write(f".kind = {kind},")
221222
self.write(".compact = 1,")
222223
self.write(".ascii = 0,")
224+
self.write(".statically_allocated = 1,")
223225
utf8 = s.encode('utf-8')
224226
self.write(f'.utf8 = {make_string_literal(utf8)},')
225227
self.write(f'.utf8_length = {len(utf8)},')

0 commit comments

Comments
 (0)