Skip to content

GH-109369: Add machinery for deoptimizing tier2 executors, both individually and globally. #110384

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
markshannon merged 11 commits into from
Oct 23, 2023
Merged

GH-109369: Add machinery for deoptimizing tier2 executors, both individually and globally. #110384

Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift + click to select a range
dd606ae
Add valid flag to executor objects
markshannon Sep 28, 2023
45c30d3
Add ability to invalidate executors as a result of changes to other o…
markshannon Oct 1, 2023
30844bb
Merge branch 'main' into tier2-deopt
markshannon Oct 2, 2023
79bda49
Remove unrelated change
markshannon Oct 4, 2023
76dad94
Tidier logic and add explanatory comment
markshannon Oct 4, 2023
02201f2
Merge branch 'main' into tier2-deopt
markshannon Oct 4, 2023
60306d8
Tidy up code and add test
markshannon Oct 4, 2023
0436c1a
Remove _JUMP_IF_INVALID. Save for next PR.
markshannon Oct 5, 2023
77ef658
Address some review comments
markshannon Oct 23, 2023
41f54b8
Use a single 64 bit hash function and more clearly document how the b…
markshannon Oct 23, 2023
11985ea
Fix unlinking of executors
markshannon Oct 23, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Use a single 64 bit hash function and more clearly document how the b… 
…loom filter works.
  • Loading branch information
@markshannon
markshannon committed Oct 23, 2023
commit 41f54b8b1bab830b3b5b9076b463db4225ed9fbf
39 changes: 17 additions & 22 deletions Python/optimizer.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1002,30 +1002,22 @@ PyUnstable_Optimizer_NewUOpOptimizer(void)

#define K 6

#define SEED 20221211

/* TO DO -- Use more modern hash functions with better distribution of bits */
static uint32_t
address_to_hash(void *ptr, uint32_t seed, uint32_t multiplier) {
static uint64_t
address_to_hash(void *ptr) {
assert(ptr != NULL);
uint32_t uhash = seed;
uint64_t uhash = SEED;
uintptr_t addr = (uintptr_t)ptr;
for (int i = 0; i < SIZEOF_VOID_P; i++) {
uhash ^= addr & 255;
uhash *= multiplier;
uhash *= (uint64_t)_PyHASH_MULTIPLIER;
addr >>= 8;
}
return uhash;
}

static const uint32_t multipliers[2] = {
_PyHASH_MULTIPLIER,
110351524,
};

static const uint32_t seeds[2] = {
20221211,
2147483647,
};

void
_Py_BloomFilter_Init(_PyBloomFilter *bloom)
{
Expand All @@ -1034,17 +1026,20 @@ _Py_BloomFilter_Init(_PyBloomFilter *bloom)
}
}

/* We want K hash functions that each set 1 bit.
* A hash function that sets 1 bit in M bits can be trivially
* derived from a log2(M) bit hash function.
* So we extract 8 (log2(256)) bits at a time from
* the 64bit hash. */
void
_Py_BloomFilter_Add(_PyBloomFilter *bloom, void *ptr)
{
/* Set k (6) bits */
for (int i = 0; i < 2; i++) {
uint32_t hash = address_to_hash(ptr, seeds[i], multipliers[i]);
for (int j = 0; j < (K/2); j++) {
uint8_t bits = hash & 255;
bloom->bits[bits >> 5] |= (1 << (bits&31));
hash >>= 8;
}
uint64_t hash = address_to_hash(ptr);
assert(K <= 8);
for (int i = 0; i < K; i++) {
uint8_t bits = hash & 255;
bloom->bits[bits >> 5] |= (1 << (bits&31));
hash >>= 8;
}
}

Expand Down