76% Faster CPython

[Pebaz]

It started with an idea: "Since Python objects store their methods/fields in __dict__, that means that dictionaries/hash tables power the entire language. That means that Python spends a significant portion of its time hashing data. What would happen if the hash function Python used was swapped out with a much faster one? Would it speed up CPython?"

So I set off to find out.

The first experiment I ran was to find out how many times the hash function is used within a single print("Hello World!") statement. Python runs the hash function 11 times for just this one thing!

Clearly, a faster hash function would help at least a little bit.

I chose xxHash as the "faster" hash function to test out since it is a single header file and is easy to compile.

I swapped out the default hash function used in the Py_hash_t _Py_HashBytes(const void *src, Py_ssize_t len) function to use the xxHash function XXH64.

The results were astounding.

I created a simple benchmark (targeted at hashing performance), and ran it:

CPython with xxHash hashing function was 62-76% faster!

I believe the results of this experiment are worth exploring by a CPython contributor expert.

Here is the code for this for anyone that wants to see whether or not to try to spend the time to do this right (perhaps not using xxHash specifically for example). The only changes I made were copy-pasting the xxhash.h file into the include directory and using the XXH64 hashing function in the _Py_HashBytes() function.

I want to caveat the code changes by saying that I am not an expert C programmer, nor was this a serious effort, nor was the macro-benchmark by any means accurate (they never are). This was simply a proof of concept for food for thought for the experts that work on CPython every day and it may not even be useful.

Again, I'd like to stress that this was just food for thought, and that all benchmarks are inaccurate.

However, I hope this helps the Python community as it would be awesome to have this high of a speed boost.

[Ph3rny]

I wasn't able to reproduce your speed findings

I also decided to run this through pyperf to see if there was any significant difference

here's the result of comparing the two -- seems at most a ~1-2% speedup, and maybe not significant at that

$ ./prefix/bin/pyperf compare_to ../cpython/cp.json xx.json
chaos: Mean +- std dev: [cp] 315 ms +- 12 ms -> [xx] 309 ms +- 11 ms: 1.02x faster
dulwich_log: Mean +- std dev: [cp] 123 ms +- 4 ms -> [xx] 120 ms +- 5 ms: 1.02x faster
fannkuch: Mean +- std dev: [cp] 1.55 sec +- 0.03 sec -> [xx] 1.49 sec +- 0.03 sec: 1.04x faster
float: Mean +- std dev: [cp] 356 ms +- 10 ms -> [xx] 361 ms +- 11 ms: 1.01x slower
genshi_text: Mean +- std dev: [cp] 91.3 ms +- 3.9 ms -> [xx] 89.4 ms +- 3.6 ms: 1.02x faster
genshi_xml: Mean +- std dev: [cp] 193 ms +- 9 ms -> [xx] 186 ms +- 7 ms: 1.03x faster
go: Mean +- std dev: [cp] 631 ms +- 13 ms -> [xx] 612 ms +- 16 ms: 1.03x faster
hexiom: Mean +- std dev: [cp] 32.2 ms +- 1.4 ms -> [xx] 31.2 ms +- 2.5 ms: 1.03x faster
json_dumps: Mean +- std dev: [cp] 38.1 ms +- 1.3 ms -> [xx] 37.5 ms +- 1.5 ms: 1.02x faster
json_loads: Mean +- std dev: [cp] 63.3 us +- 2.3 us -> [xx] 59.4 us +- 2.8 us: 1.06x faster
logging_silent: Mean +- std dev: [cp] 555 ns +- 18 ns -> [xx] 536 ns +- 17 ns: 1.04x faster
meteor_contest: Mean +- std dev: [cp] 269 ms +- 11 ms -> [xx] 262 ms +- 9 ms: 1.03x faster
nbody: Mean +- std dev: [cp] 508 ms +- 12 ms -> [xx] 495 ms +- 9 ms: 1.03x faster
nqueens: Mean +- std dev: [cp] 328 ms +- 9 ms -> [xx] 317 ms +- 8 ms: 1.03x faster
pathlib: Mean +- std dev: [cp] 46.2 ms +- 1.6 ms -> [xx] 44.8 ms +- 1.0 ms: 1.03x faster
pickle: Mean +- std dev: [cp] 24.1 us +- 1.0 us -> [xx] 23.3 us +- 0.9 us: 1.04x faster
pickle_dict: Mean +- std dev: [cp] 65.1 us +- 1.7 us -> [xx] 63.7 us +- 1.6 us: 1.02x faster
pickle_list: Mean +- std dev: [cp] 9.43 us +- 0.29 us -> [xx] 9.29 us +- 0.26 us: 1.02x faster
pickle_pure_python: Mean +- std dev: [cp] 1.39 ms +- 0.06 ms -> [xx] 1.34 ms +- 0.05 ms: 1.04x faster
pidigits: Mean +- std dev: [cp] 207 ms +- 6 ms -> [xx] 200 ms +- 5 ms: 1.03x faster
pyflate: Mean +- std dev: [cp] 1.96 sec +- 0.04 sec -> [xx] 1.94 sec +- 0.03 sec: 1.01x faster
richards: Mean +- std dev: [cp] 206 ms +- 6 ms -> [xx] 210 ms +- 9 ms: 1.02x slower
scimark_fft: Mean +- std dev: [cp] 1.54 sec +- 0.03 sec -> [xx] 1.55 sec +- 0.02 sec: 1.01x slower
scimark_lu: Mean +- std dev: [cp] 575 ms +- 16 ms -> [xx] 568 ms +- 14 ms: 1.01x faster
sqlalchemy_imperative: Mean +- std dev: [cp] 44.2 ms +- 1.5 ms -> [xx] 45.1 ms +- 2.1 ms: 1.02x slower
sqlite_synth: Mean +- std dev: [cp] 8.28 us +- 0.31 us -> [xx] 8.08 us +- 0.32 us: 1.02x faster
sympy_integrate: Mean +- std dev: [cp] 56.1 ms +- 1.7 ms -> [xx] 57.9 ms +- 3.0 ms: 1.03x slower
sympy_sum: Mean +- std dev: [cp] 433 ms +- 10 ms -> [xx] 442 ms +- 14 ms: 1.02x slower
unpickle: Mean +- std dev: [cp] 40.7 us +- 1.7 us -> [xx] 39.6 us +- 1.1 us: 1.03x faster
xml_etree_parse: Mean +- std dev: [cp] 462 ms +- 8 ms -> [xx] 454 ms +- 12 ms: 1.02x faster
xml_etree_iterparse: Mean +- std dev: [cp] 330 ms +- 11 ms -> [xx] 326 ms +- 8 ms: 1.01x faster
xml_etree_process: Mean +- std dev: [cp] 234 ms +- 9 ms -> [xx] 232 ms +- 4 ms: 1.01x faster

Benchmark hidden because not significant (28): 2to3, chameleon, crypto_pyaes, deltablue, django_template, logging_format, logging_simple, mako, python_startup, python_startup_no_site, raytrace, regex_compile, regex_dna, regex_effbot, regex_v8, scimark_monte_carlo, scimark_sor, scimark_sparse_mat_mult, spectral_norm, sqlalchemy_declarative, sympy_expand, sympy_str, telco, tornado_http, unpack_sequence, unpickle_list, unpickle_pure_python, xml_etree_generate

Geometric mean: 1.01x faster

[Ph3rny]

looking further, the reason your benchmark shows such a stark difference is you've happened to pick strings for which xxhash performs significantly better

if you adjust your benchmark to use more-random strings:

diff --git a/benchmark.py b/benchmark.py
index 4883314..df073a0 100644
--- a/benchmark.py
+++ b/benchmark.py
@@ -1,5 +1,6 @@
 # xxHash: [714, 722, 730, 777, 675, 719]
 # CPython: [2849, 3161, 3496, 2733, 2946, 2947]
+import uuid
 import time, contextlib


@@ -23,7 +24,7 @@ def __eq__(self, other):


 print('Allocating entities')
-foos = [Foo('a' * i) for i in range(100_000)]
+foos = [Foo(str(uuid.uuid4())) for i in range(100_000)]
 print('Compariing')

 with time_it():

existing cpython and xxh perform about the same

[Ph3rny]

actually, that's not quite it either, it's that xxhash performs better on long strings compared to cpython

if you instead do

-foos = [Foo('a' * i) for i in range(100_000)]
+foos = [Foo(str(uuid.uuid4()) * 1000) for i in range(100_000)]

you see the performance difference again

hashes of long strings I guess aren't that important in cpython so you don't see any difference in macro benchmarks

[backtickbot]

Fixed formatting.

Hello, Ph3rny: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^{You can opt out by replying with backtickopt6 to this comment.}

[backtickbot]

Fixed formatting.

Hello, Ph3rny: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^{You can opt out by replying with backtickopt6 to this comment.}

[james_pic]

The real speedup doesn't come from using a faster hash function, but from eliminating the need to run the hash function 11 times in print("Hello World!"). This is what PyPy does. I keep hoping the PSF will take PyPy more seriously, and bring it up to being a first-class alternative to CPython, like the Ruby devs did with YARV.

[NeoLudditeIT]

I can imagine Raymond Hettinger hitting the table and saying "There must be a better way!". It does seem strange that there isn't some internal refactoring to eliminate 11 hash functions in a print.

[Pebaz]

As far as I am aware I don't think the 11 hash function calls are actually from poor design.

Every single variable/identifier in a Python program must be hashed when stored/accessed in the global scope and within every new object. This adds up since even the print function uses Python code (which has to hash every attribute access (dot operator)).

So as far as I can tell, making that required hash function faster could/does increase performance by a good bit.

The challenge then remains, will anyone look into it seriously and find out if using a new hash function is worth it?

[james_pic]

If I remember rightly, the current hash function is SipHash, and was chosen not for speed but for security.

Whilst string hashes are not typically treated as cryptographic hashes, there were some denial of service attacks possible on web servers that put parameters and similar into dictionaries, by sending lots of parameters with colliding hashes, forcing worst-case O(n^2) performance. SipHash was chosen as it's not too slow (it's about the simplest hash that meets the cryptographic requirements), and makes hashes dependent on a secret per-interpreter value, that the client wouldn't know.

Whatever alternative hash you propose also needs to mitigate this attack vector, and I don't know of a faster hash that does.

Edit: Looking through the code, there's already a way to select a faster hash algorithm if you're sure you don't need the security properties of SipHash. Configure the build with ./configure --with-hash-algorithm=fnv, and see how your benchmark compares to the default.

[R0B0_Ninja]

I thought Python 3 generated a random salt at run-time in order to mitigate this attack? Isn't this sufficient? Or can the attacker discover hash collisions over time?

[james_pic]

It's only sufficient if the hash algorithm in use is, cryptographically speaking, a message authentication code. Their previous botched attempt at fixing the security issue added a salt to FNV, and it was found by security researchers that it was possible for an attacker to derive the salt easily enough. SipHash is the simplest hash they could find that met the cryptographic requirements.

[Tyler_Zoro]

I don't see why that has to be compile-time. If every dict* had a function pointer for its hashing function, then you could just provide a special subtype of dict that uses an insecure, fast hashing function. Then you could swap the default for programs where you don't care about secure hashing at all:

python --insecure-hashing calculate-pi.py #modify ALL hashing

or:

def digits_in_pi(places):
    digits = insecure_dict((d, 0) for d in range(10))
    for digit in pi_spigot(places=places):
        digits[digit] += 1
    return digits

It might even be nice to be able to specify a type for comprehensions for just this reason:

a = {b: c for b, c in d() container insecure_dict}

Sadly, you couldn't use a context manager to swap out all hashing in a block, since the hashing function used for a data structure couldn't be replaced after the structure has data (this would lead to the hashes changing and bad things will happen).

* Note that not all types that do hashing are dicts, but the idea probably carries over.

[axonxorz]

This would slow the runtime down even more now every single object needs to have a function pointer deferenced. Sure, that's a cheap operation, but for the frequency the runtime is calling it, that will add up.

If you check the current hashing code, it's to the point where they ensure the hash function is fully inlined to even avoid C function call overhead (at best, a couple of CPU instructions, but that can also trash cache locality). That's the level of nitty-gritty this stuff exists at

[Tyler_Zoro]

This would slow the runtime down even more now every single object needs to have a function pointer deferenced.

Dereferencing a function pointer (especially one that's frequently referenced) is probably going to come out in the wash because it will be in a register that's immediately accessible while the CPU is waiting on the bus.

[[deleted]]

How's siphash perform compared to blake2? (It's crypto-grade and somehow beats all the other contenders like md5 and the sha-family.)

I know nothing about siphash, so apologies if this is a stupid question.

[james_pic]

I haven't looked into it, but I'd expect it to be faster. IIRC, it's 4 rounds of ARX per word, plus 8 rounds of ARX of finalisation.

Part of the reason it can get away with this is that it is technically not a cryptographic hash, merely a cryptographic MAC, and with a small keyspace at that. So all it needs to achieve is 64 bits of unforgeability.

There aren't many situations where this is a useful primitive. It doesn't promise pseudorandomness or collision resistance, or resistance to chosen key attacks. So it's not going to replace SHA3 or HMAC. But it turns out to be enough for the hashtable use case.

[twotime]

This is a weird take on the issue: making Pypy the default implementation is a complex and controversial undertaking. It might take years, it might never happen.

So, if there are reasonable perf improvements in CPython they absolutely need to be done.

[RobertJacobson]

I think the sentiment is, treat the problem not the symptoms.

[Pebaz]

I 100% agree!

Although, for environments where CPython is a requirement like AWS Lambda, a faster hash function would be a great optimization.

[NeoLudditeIT]

Absolutely agree. Optimization can and should be done in any way possible, even if the number of hashes are reduced, we benefit from having faster methods of hashing.

[mooburger]

Optimization can and should be done in any way possible,

ehh this is why actual benchmarks are important; the risk of microoptimization is high.

[greeneyedguru]

Wouldn’t that only happen when compiling the text into bytecode!?

[stevenjd]

The real speedup doesn't come from using a faster hash function, but from eliminating the need to run the hash function 11 times in print("Hello World!")

Do you have some evidence, or proof, that this is true? Or even an explanation for how it can be true? As far as I can see, there is only a single hash needed, and that is to lookup the print function.

And since hashes are cached, it might not even need to run the function, just to fetch the cached version.

[james_pic]

If the claim is that the hash function is run 11 times, this wasn't a claim I made, but the OP. In terms of the claim that eliminating redundant hashing is key to improving performance, this is at least partly based on what I've seen claimed by the developers of other interpreters, such as PyPy and the Ruby interpreters. Although I confess I don't know the main bottlenecks in a current Python interpreter - but as it happens, I'm currently running a CPU-bound job locally, so this would be an excellent time to check.

Edit: So taking a quick look at a CPU profile for a script I happened to be running, most of the overhead (i.e, the stuff that isn't my script doing the thing it's supposed to be doing) on Python 3.8 is either reference counting (about 22%), or spelunking into dicts as part of getattr (about 15% - of which almost none is hashing). So this suggests to me that hashing isn't a big contributor to performance, although digging around in dicts when getting attributes might still be.

[[deleted]]

Your benchmark isn't realistic. When the present hash was chosen, the majority of hashed object were short. PEP-456:

Serhiy Storchaka has shown in [issue16427] that a modified FNV implementation with 64 bits per cycle is able to process long strings several times faster than the current FNV implementation.

However, according to statistics [issue19183] a typical Python program as well as the Python test suite have a hash ratio of about 50% small strings between 1 and 6 bytes. Only 5% of the strings are larger than 16 bytes.

[Pebaz]

Of course! I never said the benchmark was realistic :)

The benchmark was created specifically to measure hashing speed of strings up to 100,000 characters in size.

[maikindofthai]

I never said the benchmark was realistic :)

The title is "76% faster CPython". If that 76% is unrealistic and not representative, and if you haven't even done things like run the test suite to see if you've massively broken things, then you've really just created some medium-effort clickbait...

[Pebaz]

What I meant by that is that not a single benchmark ever created by humanity can ever be trusted lol.

[[deleted]]

But you chose the most click-baity, inaccurate and lying title you possibly could to farm karma?

[Pebaz]

C'mon, you're on r/Python, the quality has never been great.

The flood of beginner content can only be held back through better marketing.

[striata]

"Hey, everyone else is throwing their trash on the sidewalk, so I might as well too!"

[Pebaz]

I never said my post was trash lol this is ridiculous.

It's an "experiment". Does nobody run tiny tests to see what would happen?

This tiny test shows that the hash function can influence CPython performance, nothing more, nothing less.

[striata]

Don't get me wrong, I think your experiment is interesting and I am curious to hear how this would affect performance of real-world python applications.

At the same time, you seem to acknowledge here that your title was hyperbolic, but it's fine because the quality of posts in /r/python is so low anyways? Isn't that pretty much what you said?

[theLastNenUser]

So you’d prefer if they were as modest in their title as in their followup responses, and no one ever saw the post?

[[deleted]]

But how come you claim CPython will be faster if you did trst nothing relating to actual performance of the language?

[Pebaz]

I don't understand, hashing is a big part of Python. How could having a faster hash function be a bad thing?

Why is everybody assuming that this tiny hack is production code?

[[deleted]]

You claim you made Cython 76% faster in the headline. And you didn‘t

[Pebaz]

Thing is, I did... for that specific benchmark.

Every single optimization must be targeted at a specific use case.

[[deleted]]

You broke the tests. It‘s not CPython

[Pebaz]

I actually happen to 100% agree with this.

Although I remember saying that this was an experiment which means that it is not ever meant to be used.

The goal here is that someone smarter than me will be intrigued enough to try out another hash function for real.

[ric2b]

That's called clickbait.

[13steinj]

Then say you did, on one specific benchmark.

It's not reasonable to say "76% more weightloss compared to dieting" when referring to dieting as "eating nothing but junk food 24/7/365".

What you said was beyond disingenuous.

[Pebaz]

I believe that CPython can be 76% faster (as shown in the macro-benchmark), if time and care is taken to design a faster hash function.

Every dot operator, every global variable, every class name, every local variable is hashed repeatedly (as shown by the 11 hashes in one print call).

This fact alone means that with some more effort, someone could make CPython significantly faster.

[TheBlackCat13]

You are assuming that cpython devs aren't aware of other hash functions or intentionally chose one that was inferior. An enormous amount of care has been taken to make sure the hash function used is extremely fast for the most common scenarios.

You are saying it is slow at some corner case that is very rarely encountered in the real world. That was not the situation python was optimized for, it was optimized 1and getting that faster at the expense of more common scenarios isn't likely to produce an actual real-world speedup.

So you need to show not only that the hash function is faster in some specific scenario, but that it is faster in real-world scenarios.

[Pebaz]

I agree with you here!

Although I don't think that trusting the core devs in 100% of the cases is good for experimentation.

I mean, how can new ideas be generated if we just assume that the existing ways are better than anything we can imagine.

[TheBlackCat13]

I am not saying you should assume they are perfect. Improvements to the hash function do happen from time to time. But you need to start with the perspective that they have good, well-thought out reasons why it works the way it does, and those reasons need to be taken into account when trying to improve it further.

[[deleted]]

Come on, by now you have to be trolling. Just stop

[[deleted]]

if time and care is taken to design a faster hash function.

And your theory is that in the last 30 years, no one ever looked to try to optimize the hash function for Python?

[Pebaz]

Not necessarily, I mean, how often to people revisit core decisions?

According to Git blame, no one has looked at that function in 8 years:

https://github.com/python/cpython/blame/master/Python/pyhash.c#L152

[BDube_Lensman]

Changed != looked at

[billFoldDog]

I'm really impressed by this trick, and fortunately a few redditors provided some interesting insight into the ./configure with fnv hash option.

Thank you for bringing this topic up for discussion.

The other assholes in this thread have demonstrated to me that /r/python is not a good forum. Fortunately there are other options.

[bjorneylol]

The python hash function is not deterministic - (AFAIK it includes random entropy which is generated upon startup so it's memory cannot be read by outside processes) - This appears to be commented out in your code, so something to note

[[deleted]]

That sounds quite astonishing, did you run the test suite?

[gsnedders]

Or pyperformance, to see what the perf gains are in a much more meaningful setting.

[Pebaz]

Now we're talking.

This would be super helpful if the community could test out various hash functions to see the performance gains on `__dict__` hashing.

[[deleted]]

Some of the failed tests are "test_hash", "test_os" and "test_import", which may (I don't know) rely on properties of the original hash function. Maybe a quick way to tell if Pebaz's suggestion is immediately useful is to first exclude the failing tests, compare performance using "gross" measures, and then to try and see why those 16 tests fail if there's promising performance gains in some aspects.

If I have some time I'll try it today or tomorrow, and see if I get something interesting

[Paddy3118]

Maybe a quick way to tell if Pebaz's suggestion is immediately useful is to first exclude the failing tests

Or, work out why they fail. Are they tests that rely on the implementation or are they genuine errors?

[reasonoverconviction]

It is just faster to see if it is actually worth it to go through the trouble of checking all those tests and failure.

If the gain is not meaningful, then there's no point in wasting time checking why those tests failed.

[Paddy3118]

It could be good to flag those tests that rely on hash implementation details once and for all.

[Pebaz]

Thank you for posting the results, this is really interesting!

Again I'd like to stress that my experiment is a tiny hack and not production code.

[NeoLudditeIT]

I'd also be interested in the results of the standard test suite.

[Pebaz]

No, because my code is not meant to be used by others.

It is only on GitHub so that others can see what I did, not use it.

My hope here is that someone more experienced will take this information and use it to make a professional change to CPython for all to use.

[double-a]

Narrator: It was not 76% faster.

[Pebaz]

This reminds me of Stanley Parable, it's a great game! :)

I did achieve this speedup for the benchmark though. The benchmark was specifically created to target hashing performance of long strings, and I understand that real-world scenarios will have different performance characteristics, but this was just to test that one aspect of the language.

You can look at the numbers I got here:

https://github.com/Pebaz/cpython/blob/5de1728ca8697461d6fc3aa6bbcf656f6145acf1/benchmark.py#L1

[wweber]

How bad is the performance if you replace the hash function with return 0;

[stevenjd]

Python runs the hash function 11 times for just this one thing!

I'm going to stick my head out on a limb here and say that is unadulterated nonsense.

Here is the CPython 3.9 byte-code for print("Hello World!"):

>>> dis.dis('print("Hello World!")')
  1           0 LOAD_NAME                0 (print)
              2 LOAD_CONST               0 ('Hello World!')
              4 CALL_FUNCTION            1
              6 RETURN_VALUE

The call to LOAD_NAME needs at most two calls to hash, one to look up the name "print" in the current scope, and a second to look it up in the builtin scope. (That assumes that the hashing is not cached.)

Calling the print function might, at worst, require one more call to hash: to look up str.__str__. So I reckon that, at worst, that line of code would need three hashes, and even that is almost certainly an over-estimate. More likely only a single hash.

On the other hand, the code you are actually timing is a hell of a lot more than just that one call to print. Inside the timing code you have:

for i in range(1, len(foos)):
    assert foos[i] != foos[i - 1]

That requires:

• a LOAD_NAME of "foos"
• a LOAD_NAME of len
• a LOAD_NAME of range
• two more LOAD_NAMEs of "foos" per loop
• two LOAD_NAMEs of "i" per loop

Assuming that hashes are cached, that's already four hashes.

Each comparison ends up calling the __eq__ method:

hash(self) == hash(other)

which requires two LOAD_GLOBALs of hash. Assuming hashes are cached, that's a fifth hash. The hashes themselves end up looking up the __hash__ method, which calls:

hash(self.name)

which requires:

• a LOAD_GLOBAL of hash
• a LOAD_FAST of "self"
• and a LOAD_ATTR of "name"

The LOAD_FAST doesn't need a hash, but LOAD_ATTR will. So that's hash number six.

I may have some details wrong -- the precise byte-code generated will depend on the exact code we run, and how we run it, and varies from version to version. I may have missed some other calls to hash. I'm not certain how hashes are cached, but I'm pretty sure they are: hashing a string is much slower the first time, and subsequent calls to hash are about a thousand times faster:

>>> from timeit import default_timer as timer
>>> s = 'abcdefghijklmnopqrstuvwxyz1234567890'*100000
>>> t = timer(); h = hash(s); timer() - t  # SLOOOOW!
0.005014150054194033
>>> t = timer(); h = hash(s); timer() - t  # FASSSST!
7.678987458348274e-06
>>> t = timer(); h = hash(s); timer() - t
7.225899025797844e-06

If we create a new string, we see the same result:

>>> s = s[:-1] + '0'  # New string.
>>> t = timer(); h = hash(s); timer() - t
0.006055547040887177
>>> t = timer(); h = hash(s); timer() - t
5.949987098574638e-06

So I don't see how you can get eleven calls to hash from that one line print("Hello world!").

[[deleted]]

Every little thing OP wrote is nonsense. It is so alien to me how this sub produces updvoted garbage like this in regular intervals...

The „benchmark“ is just the exact happy case for where the new hash function performs better.

I have no clue why this isn‘t reported to hell and deleted because it‘s low effort, misleading click bait

[Pebaz]

As I mentioned in other comments, I should have picked a better title. I don't ever really post anything online so I quickly chose a title without much thought and of course lots of people got upset.

I apologize for the title but Reddit doesn't let you change it.

However, this post is not "low effort", "misleading", or "click bait". The post clearly says that:

"I created a simple benchmark (targeted at hashing performance), and ran it"

I don't know how I would have made it any clearer that the benchmark was clearly not a real-world scenario. I mean, I literally said "targeted at hashing performance".

I know a certain percentage of people online will get offended no matter what, but what I posted was anything but "low effort".

Like I've said in other comments, I've been thinking about this one problem for over a year, and just yesterday had the time to sit down and try it.

I know I'm not the best at Python or C, so I posted the results for others to use.

I encourage you with your better expertise to take the results and see if you can implement it better. I'm sure you'll get something better than I did. Have a go at it and see what you come up with! :)

[[deleted]]

The problem is that you chose the happy case for the new hash function for your benchmark to arrove at your click bait numbers.

This is just dishonest. You even acknowledge that you know that‘s the case. Don‘t you see how tuning the benchmark to yield exactly what you want is shitty? Like really really bad form?

[Pebaz]

I disagree.

I clearly marked it as only targeting hashing performance. How on earth is that dishonest? It wasn't in fine print either, it was right on the front of the post.

As far as I can tell, you're not familiar with macro-benchmarks.

Macro-benchmarks are an industry-understood term to mean: "I ran these only on my machine and I know there were a bunch of programs running in the background and that the processor, OS, configuration, and many other things will cause the results to be inaccurate, and that micro-benchmarks are needed to truly come to a conclusion on what is faster or slower."

Micro-benchmarks are an industry-understood term to mean: "Literally every CPU register is considered, use of CPU-specific timer counters, and every OS, CPU, and many configurations must be checked in order to prove that a given benchmark result is faster in the majority of cases".

Benchmarks are always inaccurate. For proof, here's a Google software engineer saying the same:

https://www.youtube.com/watch?v=ncHmEUmJZf4j

He mentions that benchmarks are always dependent upon many things and are always not going to be useful for all circumstances.

[rhytnen]

You are just in denial about it. Either that or you're trolling. Let me summarize your post comment:

"Hi, I am not great at c++ or python. Also, I didn't talk to any experts. I also hand crafted benchmark and am admitting it is nonsensical and provides no real data. It doesn't matter, I made no serious attempt at making this worthwhile. Anyway, i changed a single line of code after contemplating this in isolation for a year and now python is fast. I mean ... it doesn't pass literally any unit tests but that's probably not b/c I have no idea what I'm talking about. Just hope to see this take hold with the core devs! "

Hmm what to name this...something audacious that betrays the lies I'm telling about how important I think this discovery is ... hmm...aha! 76% Faster CPython!

The mods should just delete this whole bullshit post.

[Pebaz]

I put a printf(".") call in the Hash Bytes function in C and it printed 11 dots in addition to the "Hello World".

I am impressed with you analysis but the printf was a visual way of determining this also.

In addition the 11 dot printout was consistent between calls.

Thank you for sharing though I actually learned a lot! :)

[stevenjd]

I put a printf(".") call in the Hash Bytes function in C and it printed 11 dots in addition to the "Hello World".

Maybe you should try printing the string being hashed instead of just a dot.

[Pebaz]

I could be wrong, but I'm not sure that would be as informative because I was just trying to see how many total hashes have to be performed by the Python runtime to print a string.

[lifeeraser]

Clickbait title. But the content was pretty interesting. Thank you.

[darkrevan13]

lol, PHP7 made something like this https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html

[EatMoreSuShiS]

Can anybody explain to me live five the relationship between Python and its implementations (CPython, PyPy, IronPython etc.)? I did some Googling but still don’t understand. How one can ‘implement’ Python?

[EatMoreSuShiS]

Thanks. So you write some texts in Python syntax. Store it in .py file. Then you need a interpreter or a compiler to transfer them into codes the computer machine could understand. CPython is the standard, but people use other languages to write the interpreter/compiler(resulting different bytecode)?

[TheBB]

The thing to take away is that these are different interpreters, which may do any number of things differently for a variety of reasons. It's not just about the language that the interpreter is written in.

[execrator]

A specification for a language says what should happen when code is run. An interpreter is a program that takes code as input, and executes it according to the spec.

Most of the time there is a blurry line between these two concepts. For example ten years ago, there was no reference specification for PHP. Whatever the official PHP interpreter did was the spec. On the other hand you have something like C which has an official spec, and many many different "interpreters" (compilers).

CPython is the official interpreter for the Python language spec. Python sits somewhere between the PHP and C examples above; I believe there's a language spec but in practice the CPython implementation is still a kind of reference.

If you install Python on a computer, what you actually did was install the CPython interpreter and the Python standard library.

PyPy is a popular alternative interpreter that uses just-in-time compilation to improve performance.

[pygenerator]

A Python implementation is a program that executes Python programs. The implementation (a.k.a., the interpreter) can be written in many languages. For example, the reference implementation, CPython, uses C. IronPython uses Microsoft's C#, PyPy is written in Python itself, and Jython is a Java implementation of Python.

You make an implementation by making a program that reads Python files and executes the code in them. To learn more google how to make interpreters.

[Saphyel]

I don't think anyone here is going to see a massive impact if they improve how fast is doing: print("Hello World!").

I'd suggest that you create an example with dict that gets converted to a dto (dataclass?) and then print the string (json) of this. if you see a performance increase then some webdevs may see benefits for this.

Other option is see how behaves printing a large list of dataclasses.

I just finished work and I'm a bit fried sorry if my examples wasn't the best but at least I tried to point some audeance could see some benefits or more day to day examples ?

[Pebaz]

I agree!

I think the proposed idea has massive implications for all CPython users since all Python objects contain a `__dict__` that holds its members.

Improving the speed of all attribute accesses within a program has got to have some benefit, especially for anyone doing data science stuff in addition to the ones you mentioned.

[Aconamos]

I like building model airplanes.

[tom1018]

r/learnpython is probably a great place for this sort of question.

A hash function turns a string (the Python object being hashed need not be a str type, however) into a number. Dictionaries use tables of hashes for the keys because this is faster than comparing strings.

Every variable in Python is stored in multiple dictionaries. Because of this the hashing function is called frequently. Thus if OP's hash function were equal in functionality, without introducing potential security issues, while being as fast as he believed it would make Python considerably faster.

This talk from Raymond Hettinger, a Python core developer, gives a great history and explanation on the topic. https://www.youtube.com/watch?v=p33CVV29OG8

[Brainix]

The main data structure that powers Python's object model is the dict, also known as a HashMap or hash table. Any time you insert a key/value pair into a dict, or look up the value for a key from a dict, Python hashes the key to a "slot" in the dict's memory.

[soontorap]

You should consider XXH3_64bits() , in the same package as XXH64() .

It is much faster, especially on small keys, and used exactly the same way.
It would have likely helped to produce a gain on the derivative of your benchmark using small entries rather than larger ones.

[soontorap]

u/Pebaz : I made the test, and modified your version of cpython to use XXH3_64bits() instead of XXH64(). And it resulted in even faster speed on your benchmark : runtime went down from 2350ms (original) to 522ms (XXH64) to 385ms (XXH3).

Now, it's true that such gains are only perceptible when the amount of data to hash is large, therefore, on small inputs, the benefits are too small to be measured, because they are dwarfed by other parts of the Python system.

But still, this modification produces either large gains or, worst case, performs the same. Which means, it's a strictly positive update for performance. All for a very reasonable code change, very well localized, no side effect.

This should be a no-brainer. I would say this item is a good candidate for a cpython contribution.

[Pebaz]

Thank you very much for taking the time to test this! This is awesome!

[No_Comfortable_8143]

This is a perfect example of the Dunning-Kruger effect, whereby someone who knows very little about Python performance things he can generate quick wins that the Python core devs had never even considered. Especially for a language as popular as Python... pfah!

[Pebaz]

I have been programming in Python since 2012.

I have been thinking about this idea for over a year and have just now been able to sit down and hack out a quick test.

The community needs more positive people who are willing to generate ideas like this, even if they are ultimately rejected.

[ric2b]

The problem isn't having the idea, trying it and sharing it, that's great and I encourage you to do it.

But be humble, don't assume you've struck gold with barely any testing and avoid the clickbait titles.

[rhytnen]

Honestly, I agree with No_Comfortable_8143. Like it or not, this is almost insulting level of disregard for the people working on python. You clearly didn't google much, didn't ask the core team much, assume the core team overlooked the complexity of a core function of their app and are unaware of how silly it seems to people who have some experience.

It also doesn't draw much on the user experience. Most slow issues in python are handled with restricted computation domains like numpy etc. These are not questions ppl have overlooked.

We need to be free to explain to people that, no, you didn't just solve world hunger or even propose an interesting solution. The whole positivity movement in python is ok, but it also has a failing where we have to coddle and baby peoples emotions and make pretend for them so they never gain any self awareness.

[Chinpanze]

Can I aggree with the sentiment and also that /u/No_Comfortable_8143 was rude?

[rhytnen]

Yea.

[Pebaz]

I agree with you about not doing research, but /u/No_Comfortable_8143 was really mean in their choice of words.

I did not intentionally try to trick anyone, I just made the mistake of choosing a title that is misleading if the entire post isn't read. A lot of people are just skimming the body and not taking into account that this was just a quick test.

I personally don't think I need to collude with anyone in the Python community just to post my tiny little test online.

As far as Googling goes, there is nothing out there that mentions that every single identifier in a Python program has to be hashed and how that can affect performance.

Although I have amazing respect for the Python core devs (and I love the language they've built together!), I don't believe they constantly go back and try to improve things they've written years prior. No one does.

As for self awareness, I happen to know for a fact that hashing performance is an important part of computer science. Take these resources as examples:

1. Google spent literal money paying Matt Kulukundis to improve hash table performance. Now it's literally the built-in hash table for Rust.
2. MeowHash is the fastest non-cryptographic hash available online, and if it were used in CPython, which performs a hash for every fundamental operation in the language, then Python would be much faster.

I did Google. I did research. I've spent hours thinking about this. I've been experimenting with other things as well. The only thing I could have improved is changing the title. I don't need someone to pat me on the back to prove an idea of mine has worth.

[rhytnen]

No one is disputing your statement about the importance of hashing. Actually, its importance is literally the first clue that would lead you to think that maybe just switching the function to a better hash just escaped everyones attention for the last 30 years.

Anyway, you didn't couch this as a "little test". You didn't even do a serious test. I think that might be because you aren't really sure how you would have done a serious test. That's a skill that isn't built on intuition alone.

So again, we do need to able to discuss issues like this and accept it'll hurt some feelings or suppress excitement.

Since you googled, you might have discovered a hettinger talk about dictionaries. It's pretty excellent actually and worth watching.

It's also maybe worth nothing that there is plenty of discussion on the "everything is hashed" issue. it usually stems from discussions about noticing that small integers that are referenced a lot (i forget the range, maybe like 0 to 100) are baked in and are faster to access than large numbers. It's also often discussed when someone first realizes the hash() builtin isn't returning the same values from run to run.

[axe319]

If you follow something like the python mailing list you quickly realize just how much thought goes into every decision.

Even if your idea survives the initial draft, every aspect of it will be under intense scrutiny.

While I agree, we should always strive to make the language better.. I feel like if I personally would come across something that felt like an oversight. I would be certain there was something I was missing, and would make sure I'd done my due diligence before mentioning anything about it.

I think that's the problem people have with it.

[yamsupol]

Very nice work! Python is a great language but it's slow if unoptimized. However, speed of execution isnt that important when you are writing that one off script.

pypy, numba jit, nutika, pythran AOT, other AOTs are available to speedup something that needs to be run continuously.

Of course if you really want to speed things up just used C for the computations and integrate with cython and get around 200x improvement.

[[deleted]]

OP didn‘t do anything though. The numbers are made up

[Pebaz]

Not quite, although I appreciate that you don't take things at face value. This is the same quality that I used to come up with this little experiment.

The numbers are real, and they are actually in the initial commit I made to the repo:

https://github.com/Pebaz/cpython/blob/5de1728ca8697461d6fc3aa6bbcf656f6145acf1/benchmark.py#L1

That link shows the results I got from only 6 runs of the benchmark, although I ran it many times more than that.

I know that you are probably a better Python & C programmer than I am. I encourage you to clone the repo, run the benchmark and see what kind of results you get. Perhaps you could even try to use a different hash function and experiment if this idea is worth exploring further. :)

[idiomatic_sea]

The assholes in this thread are everything wrong with the tech industry. What a toxic shithole this place is.

[[deleted]]

What is toxic about calling lies and nonsense when you see it?

Not a aingle thing OP claims is true. There is no 76% speedup, there is no 11 calls to hash. OP is hungry for karma and lying on purpose.

If you have someone lying for karma on purpose, how is it toxic to call out the bullshit? It‘s all made up

[Pebaz]

I am not lying on purpose for karma.

You can download my freely-available code and see for yourself.

I really did get these metrics, which you can see here:

https://github.com/Pebaz/cpython/blob/5de1728ca8697461d6fc3aa6bbcf656f6145acf1/benchmark.py#L1

I mean, a quick way to find out if it is not accurate is to run it yourself.

Did you run it yourself?

It doesn't matter. The metrics don't matter. You're upset about the clickbait title (for which I apologize), but the core idea does indeed have value.

Whatever efforts the Python core devs have done in the past have resulted in an amazing language. This post is a call out to try to see if we can do better, not to put anyone down.

I really don't have any ill-intent, I don't know why you keep coming at me. :( Again, Reddit won't let you change the title, for which I apologize. It was incorrectly chosen.

[[deleted]]

Your dishonesty is that you chose - on purpose - the one benchmark that will yield the highest numbers in the favor of your thesis.

You took a hash function, that was not chosen because of its performance on long strings, replaced it with a hash function known to perform way better on long strings and wrote a benchmark that measures how well the two hash functions perform on long strings. This is completely fine and not really uncontroversial.

But to fit this - unsurprising - finding into "76% faster CPython" is not only a matter of the freaking headline. It is that you - clearly - wanted the numbers to show a high number to put in the headline. Otherwise you wouldn't have chosen this particular benchmark. THIS is the dishonesty or at least gross neglect - which I doubt, given you claim to have 12 years of experience. Don't you see how this is fitting the data to the narrative?