8000 Use a hashtable instead · python/cpython@ba49e58 · GitHub
[go: up one dir, main page]

Skip to content

Commit ba49e58

Browse files
Use a hashtable instead
1 parent 2c6860a commit ba49e58

File tree

5 files changed

+50
-62
lines changed

5 files changed

+50
-62
lines changed

.github/workflows/reusable-macos.yml

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,6 @@ jobs:
6666
- name: Display build info
6767
run: make pythoninfo
6868
- name: Tests
69-
# Stackref debug is 2.5x slower than normal CPython,
69+
# Stackref debug is 3.5x slower than normal CPython,
7070
# so we only run it on a restricted subset of tests.
71-
run: ${{ inputs.stackref-debug && './python.exe -m test test_asyncio test_typing' || 'make test' }}
71+
run: ${{ inputs.stackref-debug && './python.exe -m test test_typing' || 'make test' }}

Include/internal/pycore_stackref.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ extern "C" {
99
#endif
1010

1111
#include "pycore_object_deferred.h"
12+
#include "pycore_hashtable.h"
1213

1314
#include <stddef.h>
1415

@@ -59,8 +60,7 @@ struct _Py_stackref_entry {
5960

6061
struct _Py_stackref_state {
6162
PyMutex lock;
62-
size_t n_entries;
63-
struct _Py_stackref_entry *entries;
63+
_Py_hashtable_t *entries;
6464
size_t next_ref;
6565
};
6666

Python/ceval.c

Lines changed: 0 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -726,16 +726,6 @@ _PyObjectArray_Free(PyObject **array, PyObject **scratch)
726726
}
727727
}
728728

729-
static int
730-
_PyEval_StackIsAllLive(_PyStackRef *stack_base, _PyStackRef *stack_pointer)
731-
{
732-
while (stack_pointer > stack_base) {
733-
assert(_PyStackRef_IsLive(stack_pointer[-1]));
734-
stack_pointer--;
735-
}
736-
return 1;
737-
}
738-
739729
/* _PyEval_EvalFrameDefault() is a *big* function,
740730
* so consume 3 units of C stack */
741731
#define PY_EVAL_C_STACK_UNITS 2

Python/pylifecycle.c

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -841,14 +841,22 @@ pycore_init_builtins(PyThreadState *tstate)
841841
static PyStatus
842842
pycore_init_stackrefs(PyInterpreterState *interp)
843843
{
844-
interp->stackref_state.entries = PyMem_Malloc(sizeof(struct _Py_stackref_entry) * 1024);
844+
_Py_hashtable_allocator_t alloc = {
845+
.malloc = PyMem_Malloc,
846+
.free = PyMem_Free,
847+
};
848+
interp->stackref_state.entries = _Py_hashtable_new_full(
849+
_Py_hashtable_hash_ptr,
850+
_Py_hashtable_compare_direct,
851+
NULL,
852+
NULL,
853+
&alloc
854+
);
845855
if (interp->stackref_state.entries == NULL) {
846856
goto error;
847857
}
848-
interp->stackref_state.next_ref = 0;
849-
interp->stackref_state.n_entries = 1024;
850-
// Reserve NULL, True, False, None
851-
_Py_object_to_stackref_transition(NULL, Py_TAG_DEFERRED, STEAL);
858+
interp->stackref_state.next_ref = 1;
859+
// Reserve True, False, None
852860
_Py_object_to_stackref_transition(Py_True, Py_TAG_DEFERRED, STEAL);
853861
_Py_object_to_stackref_transition(Py_False, Py_TAG_DEFERRED, STEAL);
854862
_Py_object_to_stackref_transition(Py_None, Py_TAG_DEFERRED, STEAL);

Python/stackref.c

Lines changed: 33 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -8,40 +8,49 @@
88
int
99
_PyStackRef_IsLive(_PyStackRef stackref)
1010
{
11-
#if defined(Py_GIL_DISABLED) && defined(Py_STACKREF_DEBUG)
12-
PyInterpreterState *interp = PyInterpreterState_Get();
13-
struct _Py_stackref_entry *entry = &interp->stackref_state.entries[stackref.bits >> RESERVED_BITS];
14-
return entry->is_live;
15-
#else
11+
_Py_stackref_to_object_transition(stackref, BORROW);
1612
return 1;
17-
#endif
1813
}
1914

15+
2016
#if defined(Py_GIL_DISABLED) && defined(Py_STACKREF_DEBUG)
2117
PyObject *
2218
_Py_stackref_to_object_transition(_PyStackRef stackref, _PyStackRef_OpKind op)
2319
{
24-
PyObject *res;
20+
PyObject *res = NULL;
2521
PyInterpreterState *interp = PyInterpreterState_Get();
2622
assert(interp != NULL);
23+
int is_null = 0;
24+
void *bits = (void *)(stackref.bits >> RESERVED_BITS);
2725
switch (op) {
2826
case STEAL: {
27+
// We need to distinguish NULL here because _Py_hashtable_get
28+
// returns NULL if it cannot find a value.
29+
if (bits == 0) {
30+
is_null = 1;
31+
break;
32+
}
2933
PyMutex_Lock(&interp->stackref_state.lock);
30-
struct _Py_stackref_entry *entry = &interp->stackref_state.entries[stackref.bits >> RESERVED_BITS];
31-
assert(entry->is_live);
32-
res = entry->obj;
33-
entry->is_live = _Py_IsImmortal(entry->obj);
34+
res = (PyObject *)_Py_hashtable_get(interp->stackref_state.entries, bits);
35+
if (res != NULL && !_Py_IsImmortal(res)) {
36+
res = (PyObject *)_Py_hashtable_steal(interp->stackref_state.entries, bits);
37+
}
3438
PyMutex_Unlock(&interp->stackref_state.lock);
3539
break;
3640
}
3741
case NEW:
3842
case BORROW: {
39-
struct _Py_stackref_entry *entry = &interp->stackref_state.entries[stackref.bits >> RESERVED_BITS];
40-
assert(entry->is_live);
41-
res = entry->obj;
43+
if (bits == 0) {
44+
is_null = 1;
45+
break;
46+
}
47+
PyMutex_Lock(&interp->stackref_state.lock);
48+
res = (PyObject *)_Py_hashtable_get(interp->stackref_state.entries, bits);
49+
PyMutex_Unlock(&interp->stackref_state.lock);
4250
break;
4351
}
4452
}
53+
assert((res != NULL) ^ is_null);
4554
return res;
4655
}
4756

@@ -55,30 +64,17 @@ _Py_object_to_stackref_transition(PyObject *obj, char tag, _PyStackRef_OpKind op
5564
case STEAL:
5665
case NEW:
5766
{
67+
if (obj == NULL) {
68+
return PyStackRef_NULL;
69+
}
5870
PyMutex_Lock(&interp->stackref_state.lock);
59-
res.bits = (interp->stackref_state.next_ref << RESERVED_BITS) | tag;
60-
struct _Py_stackref_entry *entry = &interp->stackref_state.entries[interp->stackref_state.next_ref];
61-
entry->is_live = 1;
62-
entry->obj = obj;
63-
interp->stackref_state.next_ref++;
64-
// Out of space, allocate new one.
65-
if (interp->stackref_state.next_ref >= interp->stackref_state.n_entries) {
66-
size_t old_size = interp->stackref_state.n_entries;
67-
interp->stackref_state.n_entries *= 2;
68-
struct _Py_stackref_entry *new_mem = PyMem_Malloc(
69-
sizeof(struct _Py_stackref_entry) *
70-
interp->stackref_state.n_entries);
71-
if (new_mem == NULL) {
72-
fprintf(stderr, "OOM for PyStackRef\n");
73-
Py_FatalError("Cannot allocate memory for stack references.\n");
74-
return PyStackRef_NULL;
75-
}
76-
memcpy(new_mem,
77-
interp->stackref_state.entries,
78-
old_size * sizeof(struct _Py_stackref_entry));
79-
PyMem_Free(interp->stackref_state.entries);
80-
interp->stackref_state.entries = new_mem;
71+
uintptr_t key = interp->stackref_state.next_ref;
72+
res.bits = (key << RESERVED_BITS) | tag;
73+
int err = _Py_hashtable_set(interp->stackref_state.entries, (void *)key, obj);
74+
if (err < 0) {
75+
Py_FatalError("Stackref handle allocation failed.\n");
8176
}
77+
interp->stackref_state.next_ref++;
8278
PyMutex_Unlock(&interp->stackref_state.lock);
8379
break;
8480
}
@@ -91,13 +87,7 @@ _Py_object_to_stackref_transition(PyObject *obj, char tag, _PyStackRef_OpKind op
9187
void
9288
_PyStackRef_Close(_PyStackRef stackref)
9389
{
94-
PyInterpreterState *interp = PyInterpreterState_Get();
95-
assert(interp != NULL);
96-
PyMutex_Lock(&interp->stackref_state.lock);
97-
struct _Py_stackref_entry *entry = &interp->stackref_state.entries[stackref.bits >> RESERVED_BITS];
98-
assert(entry->is_live);
99-
entry->is_live = _Py_IsImmortal(entry->obj);
100-
PyMutex_Unlock(&interp->stackref_state.lock);
90+
_Py_stackref_to_object_transition(stackref, STEAL);
10191
}
10292

10393
_PyStackRef

0 commit comments

Comments
 (0)
0