Unexplained performance slowdown on both official 3.13.6 and 3.14 regarding hash collisions - reproduced on dict[int, int] and set[int], cannot be reproduced when building Python locally

[JasonMendoza2008]

Bug report

Bug description:

On my computer (Windows 11, AMD CPU), this code is 5 times slower on Python 3.14 than it is on Python 3.12.
(don't mind the generation of evil_all_numbers, it's just to generate collision hashes based on those Python 3.14 comments which, as far as I can see, has not changed if we look at the Python 3.12 version):

evil_all_numbers = []

i = 40 & (2**16-1)
perturb = i
while len(evil_all_numbers) < 40000:
    evil_all_numbers.append(i+2**17)
    perturb >>= 5
    i = (5*i+ 1 + perturb) & (2**16-1)

my_dict = {}
for number in evil_all_numbers:
    my_dict[number] = 1

import timeit
print(timeit.timeit("40 in my_dict", globals=globals(), number=50000))
print(timeit.timeit("39 in my_dict", globals=globals(), number=50000))

I (surprisingly) get:

PS C:\Users\lhott\Downloads> & "C:\Users\lhott\AppData\Local\Programs\Python\Python312\python.exe" .\testHackHash.py
1.8733288999646902
0.001043599913828075
PS C:\Users\lhott\Downloads> & "C:\Users\lhott\AppData\Local\Programs\Python\Python314\python.exe" .\testHackHash.py
5.002686099964194
0.0010038999607786536

I'm using versions Python 3.14.0rc1 (tags/v3.14.0rc1:48f8831, Jul 22 2025, 17:09:57) [MSC v.1944 64 bit (AMD64)] on win32 and Python 3.12.5 (tags/v3.12.5:ff3bc82, Aug 6 2024, 20:45:27) [MSC v.1940 64 bit (AMD64)] on win32 for the comparisons. Both were downloaded from the official python website.

It might just be a change in how dictionaries are handled that made the worst case worse, but I never heard of it (although admittedly I haven't scoured the changelogs).

If I'm not mistaken, the load factor is indicated to be the same in both versions as well, so that's not an explanation:

cpython/Objects/dictobject.c

Line 168 in c9d9f78

out, we usually do -- the table load factor is kept under 2/3, so the odds

cpython/Objects/dictobject.c

Line 316 in 1bde13b

out, we usually do -- the table load factor is kept under 2/3, so the odds

CPython versions tested on:

3.12, 3.13 (see this and this), 3.14

Operating systems tested on:

Windows

Sets

For the same slowdown on sets, see this.

[StanFromIreland]

I see some weird results on Linux:

Main branch:

2.2531575110042468
0.0005879429954802617

3.14:

6.174814685000456
0.003326637997815851

3.13:

1.979844592999143
0.0008711990012670867

3.12:

2.2492162800044753
0.0005370910002966411

[adqm]

I figured I'd try to bisect this, but I found that I can't reproduce it (Debian, GCC 12.2.0) 😕 I see a very little bit of difference between versions, but I definitely don't see that huge spike on 3.14.0rc1. Sharing my results in case they're helpful.

I ran everything with:

$ ./configure; make -j `nproc`; ./python ~/dictspeed.py

Results below, for a few different versions:

• tip of main branch

  3.15.0a0 (heads/main:362692852f, Aug 11 2025, 12:32:50) [GCC 12.2.0]
  3.6443712401669472
  0.0013227558229118586
  

• 3.14.0rc1 downloaded from Python.org

  3.14.0rc1 (main, Aug 11 2025, 12:26:12) [GCC 12.2.0]
  3.6922574560157955
  0.0012468001805245876
  

• tip of 3.14 branch

  3.14.0rc1+ (heads/3.14:019238ab183, Aug 11 2025, 12:25:12) [GCC 12.2.0]
  3.6401637149974704
  0.001392710953950882
  

• 3.12.5 downloaded from Python.org

  3.12.5 (main, Aug 11 2025, 12:55:09) [GCC 12.2.0]
  3.3501299149356782
  0.0011009499430656433
  

• tip of 3.12 branch

  3.12.11+ (heads/3.12:c9d9f78feb1, Aug 11 2025, 12:27:20) [GCC 12.2.0]
  3.3981235059909523
  0.0008614480029791594
  

Compiling with clang (14.0.6 from Debian's repos) gives me similar results (no substantial difference between versions).

[StanFromIreland]

I see my 3.14 build was a few commits out of date. I can no longer reproduce with the latest 3.14.

[JasonMendoza2008]

I only tried with the version available on Python official website, so I'm definitely a few commits out of date. Maybe this was fixed already? But it seems adqm couldn't reproduce with the one from Python official website. The only difference I can think of between their 3.14.0rc1 downloaded from Python.org and mine is that mine was compiled with MSVC and theirs with GCC.

[tim-one]

FYI, I see a large difference under the released Python 3.13.6 for Win64 from python.org:

8.856650999980047
0.0012924999464303255

So there are mysteries here, but unclear there's "a bug". It's not surprising that this kind of hash map implementation can be provoked into O(n) time lookup behavior

[JasonMendoza2008]

FYI, I see a large difference under the released Python 3.13.6 for Win64 from python.org:

8.856650999980047
0.0012924999464303255

So there are mysteries here, but unclear there's "a bug". It's not surprising that this kind of hash map implementation can be provoked into O(n) time lookup behavior

Of course the difference is large, I provoked the bad lookup behaviour purposely. The difference I was talking about is the "bad lookup behaviour" time is different (massively larger for that matter) in Python 3.14 compared to other versions. I'm comparing the "big" value between different versions, not the big value with the small value.

[JasonMendoza2008]

I see my 3.14 build was a few commits out of date. I can no longer reproduce with the latest 3.14.

So I compiled Python 3.14 locally on Windows from the tip of 3.14 branch. I used .\PCbuild\build.bat -e -c Release -p x64 (I could only find instructions for debug mode online (here and here), so I improvised, please advise if I'm doing anything wrong).

I cannot reproduce the bug anymore.

Lcaolly built from the tip of 3.14 branch:

PS C:\Users\lhott\Downloads> & "C:\Users\lhott\Desktop\temp\cpython\PCbuild\amd64\python.exe" .\testHackDict.py
1.7676873001037166
0.0019277000101283193

From python 3.14 on the official python webpage:

PS C:\Users\lhott\Downloads> & "C:\Users\lhott\AppData\Local\Programs\Python\Python314\python.exe" .\testHackDict.py
5.02569009992294
0.0009890999644994736

From python 3.12.5 on the official python webpage:

PS C:\Users\lhott\Downloads> & "C:\Users\lhott\AppData\Local\Programs\Python\Python312\python.exe" .\testHackDict.py
1.887535799993202
0.0009402000578120351

The issue was therefore already fixed?
I'm still confused though because as stated above it seems adqm couldn't reproduce with the one from Python official website. The only difference I can think of between their 3.14.0rc1 downloaded from Python.org and mine is that mine was compiled with MSVC and theirs with GCC.
SO maybe the official preview on 3.14 wasn't compiled in Release mode on Windows? I'm very new to CPython, take what I say with a grain of salt....

[tim-one]

Of course the difference is large, the difference I was talking about is the "bad lookup behaviour" time is different in Python 3.14 compared to other versions.

Yes, that's understood. My data point was not from Python 3,14, but from the Win64 3.13.6 release from python.org. Mysteries, yes. Bug? Unclear.

I didn't show results from other versions because 3.13.6 was the worst discrepancy i saw.

The only difference I can think of ,,, is that mine was compiled with MSVC and theirs with GCC.

That alone can make huge differences.. So can whether you're using "program guided optimization". Don't hope for easy answers here 😉

[JasonMendoza2008]

Of course the difference is large, the difference I was talking about is the "bad lookup behaviour" time is different in Python 3.14 compared to other versions.

Yes, that's understood. My data point was not from Python 3,14, but from the Win64 3.13.6 release from python.org. Mysteries, yes. Bug? Unclear.

I didn't show results from other versions because 3.13.6 was the worst discrepancy i saw.

Ah maybe I misunderstood! Apologies. Are your other timings from other versions really far from 3.13.6? That would be interesting to see, if on other versions your "bad lookup behaviour" takes half that time, that'd be another mystery indeed...

The only difference I can think of ,,, is that mine was compiled with MSVC and theirs with GCC.

That alone can make huge differences.. So can whether you're using "program guided optimization". Don't hope for easy answers here 😉

Would PGO be used if I did .\PCbuild\build.bat -e -c Release -p x64? Again, I'm a beginner with CPython, so there are subtleties that I don't get. But, I would've expected the official Python website to give Python versions with "as many optimisations as possible"?¹

Footnotes

1. or maybe the preview versions are purposely compiled in debug mode to detect more bugs? ↩

[tim-one]

Apologies for my cryptic brevity, but I can't make time for this now and only wanted to share my data point for those who can.

Are your other timings from other versions really far from 3.13.6?

"All over the map". If I saw "a pattern" that made any sense,, I would have shared them. But it appeared chaotic, and I don't have time now to dig into it, so only shared the worst I saw,

`Would PGO be used if I did .\PCbuild\build.bat -e -c Release -p x64?

Don't think so.. That's a "Release" build, so named for historical reasons, to distinguish it from a "Debug" build. PGO builds go beyond that. Relevant target names include PGInstrument and PGUpdate. I've almost never used them, so can't help you beyond just saying that.

I would've expected the official Python website to give Python versions with "as many optimisations as possible"?

To a first approximation, I believe that's a reasonable expectation. But nothing is absolute. Optimizations generally employ heuristics, and don't always "win". For example, I recall that PGO on Windows ends up making a special case of integer division by 10, where it wins big, but at the cost of slightly slowing integer division by all denominators other than 10. Because the program suite it was "trained" on happened to divide by 10 a lot,.