9 ms·

A while back someone posted their patch to cpython where they replaced the hash function with a fast one and claimed this dramatically sped up the whole Python

by andai 3y ago

A while back someone posted their patch to cpython where they replaced the hash function with a fast one and claimed this dramatically sped up the whole Python runtime. They claimed that the hash function was used constantly —e.g. 11 times in print("hello world")—because it's used to look up object properties. Apparently the default implementation is not optimized for performance but for security, just in case the software is exposed to the web. None of my Python programs are, so assuming all this is true, I'd much prefer to have a "I'm offline, please run twice as fast!" flag (or env variable).

tyingq 3y ago
It looks like you can disable the slower randomized hashing yourself by setting PYTHONHASHSEED to 0. Though I don't know if there's further speedup to be had by using a different hash implementation. https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHASHSEED https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHA... The original issue: https://bugs.python.org/issue13703 https://bugs.python.org/issue13703
- masklinn 3y ago
  That only disables the keying of the hash function (sets the initial value to 0), it does not change the hash function. The hashseed is a per-process value, it has basically no impact on performances.
  - deleted 3y ago
    [deleted]
a_humean 3y ago
I'm aware that Rust has something similiar for things like `std::collections::HashMap`. By default: > The default hashing algorithm is currently SipHash 1-3, though this is subject to change at any point in the future. While its performance is very competitive for medium sized keys, other hashing algorithms will outperform it for small keys such as integers as well as large keys such as long strings, though those algorithms will typically not protect against attacks such as HashDoS. https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm... However, Rust also lets you pick or implement your own hash algorithm if you want to optimise for your usecase.
- eesmith 3y ago
  Python 3.11 appears to have switched to SipHash 1-3 for strings, from 2-4, following the lead of Rust and Ruby. https://github.com/python/cpython/issues/73596 https://github.com/python/cpython/issues/73596 However, Python does not use it for integers; >>> hash(10) 10 >>> hash(100) 100 >>> hash(2**61-2) == 2**61-2 True >>> hash(2**61-1) 0
  - danhau 3y ago
    That’s good though, right? Is there a reason for not using an identity hash (is that the right term?) for integers?
    - ynik 3y ago
      That depends on the hash table implementation and the distribution of the integers. For the commonly used hash tables with prime size that use modulo to turn the hash code into a slot index, an identity hash for integers is usually fine (unless many integers are multiples of the prime size). But other hash tables use power-of-two size to replace the modulo operation with a faster bit-and operation. Now an identity hash for integers is much more problematic, e.g. if all integers are multiples of 1000, only 1/8th of the table slots can be used. The latter kind of hash tables would like all bits in the hash value to be well-distributed; and this is typically not true of the underlying integers. So an additional mixing operation needs to be used. Whether that mixing happens in the hash function or in the hash table depends on the implementation (for some, it's even configurable, e.g. is_avalanching marker in ankerl::unordered_dense).
    - vhcr 3y ago
      Don't use user-supplied integers on dicts or sets on Python: >>> {i for i in range(10000)} Takes 0.005s >>> {i * sys.hash_info.modulus for i in range(10000)} Takes 0.76s
- yakubin 3y ago
  Which is why the Rust compiler itself uses a non-cryptographic hash, which takes just 3 x86 instructions and can work on 8 bytes at a time: <https://github.com/rust-lang/rustc-hash/blob/master/src/lib.rs#L49 https://github.com/rust-lang/rustc-hash/blob/master/src/lib....>
eesmith 3y ago
Your "just in case the software is exposed to the web" should be "exposed to untrusted data." The very old Python hash could be DoS'ed reading a data file. The original randomized version required some feedback to figure out the hash, so generally required some sort of interaction. I find that hard to believe that's a performance bottleneck. String hashes are all cached, and names like "print" are interned. For a 2x overall gain I would expect to see the hash function pop up easily in my profiling, but I haven't seen it in my own profiling which was looking for simple things like that. When siphash was evaluated, quoting https://peps.python.org/pep-0456/#performance https://peps.python.org/pep-0456/#performance , "In general the PEP 456 code with SipHash24 is about as fast as the old code with FNV" and "The summarized total runtime of the benchmark is within 1% of the runtime of an unmodified Python 3.4 binary". Since then they switched from siphash24 to the faster siphash13. https://github.com/python/cpython/pull/28752 https://github.com/python/cpython/pull/28752
ynik 3y ago
AFAIK Python strings cache their hash value. All the hash table lookups for object properties should be compile-time constant strings that reuse the string object, and thus also reuse the cached hash value. It may take 11 hash computations for the first print("hello world"), but the second call shouldn't take any.
petters 3y ago
Do you mean this post? https://www.reddit.com/r/Python/s/raofvsKCiz https://www.reddit.com/r/Python/s/raofvsKCiz That speedup was disputed in the comments. I haven’t tried it myself though
- masklinn 3y ago
  https://www.reddit.com/r/Python/comments/mgi4op/comment/gswghvi/ https://www.reddit.com/r/Python/comments/mgi4op/comment/gswg... I’d use “thoroughly disproven” rather than “disputed”. I’m sure the hash function can be changed, but as various comments noted: - the benchmark was nonsensical - cpython caches string hashes, and “symbols” are interned, so outside of dynamic attribute access from dynamically constructed strings each hash for attribute purposes or namespace lookup is computed once per process - and finally (though probably not the biggest issue) xxhash is known for being mostly useful on larger sizes (>128 bytes, although you can find better hashes (city IIRC) up to 512 or so) Much like Rust, CPython uses siphash as its default, it’s a pretty good all rounder though not the fastest. It actually used to use FNV before HashDOS. CPython does suffer from the inability of users to configure hash functions since it’s an object property rather than a container property.
  - tialaramex 3y ago
    Rust is doing something even more subtle here than just making the hash function a container property. There are two inter-related Rust traits, Hash is a trait which types implement to explain abstractly how to hash that type, but it's written in terms of a Hasher trait so you can drop in a different function with the same API. The Rust standard library provides a derive macro for Hash, so most people can just gesture vaguely at their custom type and have it hashed correctly for any hash functions they need. The naïve approach here easily ends up doing a bad job either colliding hashes for correlated objects in a surprising way or emitting different hashes for equivalent objects because people who make a user defined type probably aren't hashing experts.
    - masklinn 3y ago
      We can get into the weeds about the details, but what I'm talking about is mostly that in Python (and in most languages really, AFAIK Ruby, Java, or C# are the same to list just a few) objects have to return the hash itself, so the hash function is fixed by the type. In Rust, the Hash trait is only used to feed data to a hasher such that the type can decide what should be hashed. The creation of the hasher is done by the collection, and thus provides better opportunities / flexibility in customising the hash function.
Asraelite 3y ago
This may be a somewhat uninformed opinion, but I think CPython is just straight up not particularly good software. There are a million and one optimizations that other major scripting runtimes (V8, LuaJIT, PyPy, Ruby YJit etc.) have had for years that CPython is lacking. This is by design though. CPython has never been focused on performance, that's why it's not even JIT. It optimizes for simplicity and easy interoperability with C. The problem is that because Python is such a ubiquitous language, CPython gets more attention than it deserves. People see it as an archetypical implementation of a scripting language. We get blogposts like this examining its inner workings, discussions about how its performance could be improved, comparisons of its speed vs. compiled languages, and tutorials on how to optimize code to run faster in it. I feel like all of this effort would be better spent on discussions about runtimes that actually try to be fast.
- deleted 3y ago
  [deleted]
- lifthrasiir 3y ago
  Python rather happened to have a language design and C API design that doesn't allow a simple performant implementation. Even PyPy was not that fast compared to other JIT implementations, while its C API support was always subpar. It is easy to say that Python should trade them off for performance, but they are one of the key reasons for Python's success after all.
  - whizzter 3y ago
    The semantic issues of making a performant Python language implementation are more or less exactly the same as for JS and Lua, optimizing Ruby seems to possibly have even more "magic" that needs patching but we've seen the Shopify team get cracking on that (it includes MaximeCB that did HiggsJS). PyPy is in many aspects to be rated as a research project that tried a novel approach to reduce the workload compared to the manhours poured into V8,etc. LuaJIT managed with less with a focused language and a really capable lead. (Also I wouldn't be surprised if the PyPy team has also had to make compromises to get some kind of compatibility)
explaininjs 3y ago
What's more, you can get a significant speedup from your Python scripts by replacing the inbuilt cpython malloc calls with a static "allocate big chunk of stack at the beginning and I'll manage it myself" implementation, falling back to malloc as needed if it grows beyond that. A college class in perf engineering I TA'd did this, the results even a beginner could achieve were compelling, the top of the class produced results quite remarkable indeed.. This is most effective for reducing startup time of short lived scripts, where the runtime is dominated by many thousands of trivial mallocs right at startup. But in general if you can establish a bound on memory, it will be faster to allocate it in one shot.
- anitil 3y ago
  I'd love to see an example of this if you happen to have one available. I hit a startup-time issue in a previous life, and I wish I had spent the time looking at it back then
  - explaininjs 3y ago
    A template repo can be found here https://github.com/JacksonKearl/cpython https://github.com/JacksonKearl/cpython, but it does not implement an ideal malloc, just a baseline one - I am not sure if it is still being used as an assignment. The repo states that even this dummy implementation: > has a 60% faster startup as compared to base CPython, and in some test cases has marginally better runtime performance as well.
    - anitil 3y ago
      Thankyou so much!
2OEH8eoCRo0 3y ago
> I'd much prefer to have a "I'm offline, please run twice as fast!" If I know anything about programmers, it's that everyone would just use the "go faster" flag by default.
- xorcist 3y ago
  Yet ~ nobody uses PyPy by default. Speed is clearly not the top consideration for most Python programmers.
60secs 3y ago
So your solution to if statements is to add more if statements?
matheusmoreira 3y ago
Hash function security is certainly a concern due to hash flooding attacks which force worst case performance hash table lookup and leads to denial of service. https://peps.python.org/pep-0456/ https://peps.python.org/pep-0456/
- tesdinger 3y ago
  A lot of code never sees data input by untrusted sources. Just let me ignore the possible attacks and run python faster on my own data.

by andai 3y ago

tyingq 3y ago

It looks like you can disable the slower randomized hashing yourself by setting PYTHONHASHSEED to 0. Though I don't know if there's further speedup to be had by using a different hash implementation. https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHASHSEED https://docs.python.org/3/using/cmdline.html#envvar-PYTHONHA... The original issue: https://bugs.python.org/issue13703 https://bugs.python.org/issue13703

masklinn 3y ago
That only disables the keying of the hash function (sets the initial value to 0), it does not change the hash function. The hashseed is a per-process value, it has basically no impact on performances.
- deleted 3y ago
  [deleted]

a_humean 3y ago

I'm aware that Rust has something similiar for things like `std::collections::HashMap`. By default: > The default hashing algorithm is currently SipHash 1-3, though this is subject to change at any point in the future. While its performance is very competitive for medium sized keys, other hashing algorithms will outperform it for small keys such as integers as well as large keys such as long strings, though those algorithms will typically not protect against attacks such as HashDoS. https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm... However, Rust also lets you pick or implement your own hash algorithm if you want to optimise for your usecase.

eesmith 3y ago
Python 3.11 appears to have switched to SipHash 1-3 for strings, from 2-4, following the lead of Rust and Ruby. https://github.com/python/cpython/issues/73596 https://github.com/python/cpython/issues/73596 However, Python does not use it for integers; >>> hash(10) 10 >>> hash(100) 100 >>> hash(2**61-2) == 2**61-2 True >>> hash(2**61-1) 0
- danhau 3y ago
  That’s good though, right? Is there a reason for not using an identity hash (is that the right term?) for integers?
  - ynik 3y ago
    That depends on the hash table implementation and the distribution of the integers. For the commonly used hash tables with prime size that use modulo to turn the hash code into a slot index, an identity hash for integers is usually fine (unless many integers are multiples of the prime size). But other hash tables use power-of-two size to replace the modulo operation with a faster bit-and operation. Now an identity hash for integers is much more problematic, e.g. if all integers are multiples of 1000, only 1/8th of the table slots can be used. The latter kind of hash tables would like all bits in the hash value to be well-distributed; and this is typically not true of the underlying integers. So an additional mixing operation needs to be used. Whether that mixing happens in the hash function or in the hash table depends on the implementation (for some, it's even configurable, e.g. is_avalanching marker in ankerl::unordered_dense).
  - vhcr 3y ago
    Don't use user-supplied integers on dicts or sets on Python: >>> {i for i in range(10000)} Takes 0.005s >>> {i * sys.hash_info.modulus for i in range(10000)} Takes 0.76s
yakubin 3y ago
Which is why the Rust compiler itself uses a non-cryptographic hash, which takes just 3 x86 instructions and can work on 8 bytes at a time: <https://github.com/rust-lang/rustc-hash/blob/master/src/lib.rs#L49 https://github.com/rust-lang/rustc-hash/blob/master/src/lib....>

eesmith 3y ago

Your "just in case the software is exposed to the web" should be "exposed to untrusted data." The very old Python hash could be DoS'ed reading a data file. The original randomized version required some feedback to figure out the hash, so generally required some sort of interaction. I find that hard to believe that's a performance bottleneck. String hashes are all cached, and names like "print" are interned. For a 2x overall gain I would expect to see the hash function pop up easily in my profiling, but I haven't seen it in my own profiling which was looking for simple things like that. When siphash was evaluated, quoting https://peps.python.org/pep-0456/#performance https://peps.python.org/pep-0456/#performance , "In general the PEP 456 code with SipHash24 is about as fast as the old code with FNV" and "The summarized total runtime of the benchmark is within 1% of the runtime of an unmodified Python 3.4 binary". Since then they switched from siphash24 to the faster siphash13. https://github.com/python/cpython/pull/28752 https://github.com/python/cpython/pull/28752

ynik 3y ago

AFAIK Python strings cache their hash value. All the hash table lookups for object properties should be compile-time constant strings that reuse the string object, and thus also reuse the cached hash value. It may take 11 hash computations for the first print("hello world"), but the second call shouldn't take any.

petters 3y ago

Do you mean this post? https://www.reddit.com/r/Python/s/raofvsKCiz https://www.reddit.com/r/Python/s/raofvsKCiz That speedup was disputed in the comments. I haven’t tried it myself though

masklinn 3y ago
https://www.reddit.com/r/Python/comments/mgi4op/comment/gswghvi/ https://www.reddit.com/r/Python/comments/mgi4op/comment/gswg... I’d use “thoroughly disproven” rather than “disputed”. I’m sure the hash function can be changed, but as various comments noted: - the benchmark was nonsensical - cpython caches string hashes, and “symbols” are interned, so outside of dynamic attribute access from dynamically constructed strings each hash for attribute purposes or namespace lookup is computed once per process - and finally (though probably not the biggest issue) xxhash is known for being mostly useful on larger sizes (>128 bytes, although you can find better hashes (city IIRC) up to 512 or so) Much like Rust, CPython uses siphash as its default, it’s a pretty good all rounder though not the fastest. It actually used to use FNV before HashDOS. CPython does suffer from the inability of users to configure hash functions since it’s an object property rather than a container property.
- tialaramex 3y ago
  Rust is doing something even more subtle here than just making the hash function a container property. There are two inter-related Rust traits, Hash is a trait which types implement to explain abstractly how to hash that type, but it's written in terms of a Hasher trait so you can drop in a different function with the same API. The Rust standard library provides a derive macro for Hash, so most people can just gesture vaguely at their custom type and have it hashed correctly for any hash functions they need. The naïve approach here easily ends up doing a bad job either colliding hashes for correlated objects in a surprising way or emitting different hashes for equivalent objects because people who make a user defined type probably aren't hashing experts.
  - masklinn 3y ago
    We can get into the weeds about the details, but what I'm talking about is mostly that in Python (and in most languages really, AFAIK Ruby, Java, or C# are the same to list just a few) objects have to return the hash itself, so the hash function is fixed by the type. In Rust, the Hash trait is only used to feed data to a hasher such that the type can decide what should be hashed. The creation of the hasher is done by the collection, and thus provides better opportunities / flexibility in customising the hash function.

Asraelite 3y ago

This may be a somewhat uninformed opinion, but I think CPython is just straight up not particularly good software. There are a million and one optimizations that other major scripting runtimes (V8, LuaJIT, PyPy, Ruby YJit etc.) have had for years that CPython is lacking. This is by design though. CPython has never been focused on performance, that's why it's not even JIT. It optimizes for simplicity and easy interoperability with C. The problem is that because Python is such a ubiquitous language, CPython gets more attention than it deserves. People see it as an archetypical implementation of a scripting language. We get blogposts like this examining its inner workings, discussions about how its performance could be improved, comparisons of its speed vs. compiled languages, and tutorials on how to optimize code to run faster in it. I feel like all of this effort would be better spent on discussions about runtimes that actually try to be fast.

deleted 3y ago
[deleted]
lifthrasiir 3y ago
Python rather happened to have a language design and C API design that doesn't allow a simple performant implementation. Even PyPy was not that fast compared to other JIT implementations, while its C API support was always subpar. It is easy to say that Python should trade them off for performance, but they are one of the key reasons for Python's success after all.
- whizzter 3y ago
  The semantic issues of making a performant Python language implementation are more or less exactly the same as for JS and Lua, optimizing Ruby seems to possibly have even more "magic" that needs patching but we've seen the Shopify team get cracking on that (it includes MaximeCB that did HiggsJS). PyPy is in many aspects to be rated as a research project that tried a novel approach to reduce the workload compared to the manhours poured into V8,etc. LuaJIT managed with less with a focused language and a really capable lead. (Also I wouldn't be surprised if the PyPy team has also had to make compromises to get some kind of compatibility)

explaininjs 3y ago

What's more, you can get a significant speedup from your Python scripts by replacing the inbuilt cpython malloc calls with a static "allocate big chunk of stack at the beginning and I'll manage it myself" implementation, falling back to malloc as needed if it grows beyond that. A college class in perf engineering I TA'd did this, the results even a beginner could achieve were compelling, the top of the class produced results quite remarkable indeed.. This is most effective for reducing startup time of short lived scripts, where the runtime is dominated by many thousands of trivial mallocs right at startup. But in general if you can establish a bound on memory, it will be faster to allocate it in one shot.

anitil 3y ago
I'd love to see an example of this if you happen to have one available. I hit a startup-time issue in a previous life, and I wish I had spent the time looking at it back then
- explaininjs 3y ago
  A template repo can be found here https://github.com/JacksonKearl/cpython https://github.com/JacksonKearl/cpython, but it does not implement an ideal malloc, just a baseline one - I am not sure if it is still being used as an assignment. The repo states that even this dummy implementation: > has a 60% faster startup as compared to base CPython, and in some test cases has marginally better runtime performance as well.
  - anitil 3y ago
    Thankyou so much!

2OEH8eoCRo0 3y ago

> I'd much prefer to have a "I'm offline, please run twice as fast!" If I know anything about programmers, it's that everyone would just use the "go faster" flag by default.

xorcist 3y ago
Yet ~ nobody uses PyPy by default. Speed is clearly not the top consideration for most Python programmers.

60secs 3y ago

So your solution to if statements is to add more if statements?

matheusmoreira 3y ago

Hash function security is certainly a concern due to hash flooding attacks which force worst case performance hash table lookup and leads to denial of service. https://peps.python.org/pep-0456/ https://peps.python.org/pep-0456/

tesdinger 3y ago
A lot of code never sees data input by untrusted sources. Just let me ignore the possible attacks and run python faster on my own data.