Remove false optimization for equality comparison of hashed strings

[rhettinger]

BPO	18719
Nosy	@rhettinger, @vstinner, @alex, @serhiy-storchaka
Files	eq_optimization.diff: Remove the test-first-character test 27.diff: Remove the test-first-character test in 2.7

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2013-08-14.01:35:51.231>
created_at = <Date 2013-08-12.20:33:24.685>
labels = ['interpreter-core']
title = 'Remove false optimization for equality comparison of hashed strings'
updated_at = <Date 2013-08-14.01:35:51.231>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2013-08-14.01:35:51.231>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2013-08-14.01:35:51.231>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2013-08-12.20:33:24.685>
creator = 'rhettinger'
dependencies = []
files = ['31258', '31270']
hgrepos = []
issue_num = 18719
keywords = ['patch']
message_count = 7.0
messages = ['195011', '195014', '195015', '195040', '195042', '195116', '195117']
nosy_count = 5.0
nosy_names = ['rhettinger', 'vstinner', 'alex', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue18719'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4']

[rhettinger]

This code is only run when the kinds, lengths, and hashes match. So, the probability of the strings being equal is VERY high. Accordingly, there is no benefit to an earlier out test to see if the first characters differ.

There is a modest benefit to comparing one-character strings, but that comes at the expense of of testing all other string lengths.

This code is on the critical path for dicts and sets, so we don't want to slow it down with false optimizations or optimizations of special cases that come at the expense of the common, general case.

[alex]

does this show demonstrable results (in either direction) on stringbench or the benchmarks repo?

[vstinner]

See also issues bpo-16286 and bpo-17628.

[rhettinger]

Profiling the test suite shows that the short-cut branch NEVER gets taken.
There are no cases where the string lengths, kinds, and 64-bit hashes match, but the stings themselves are a mismatch. The whole theory behind this optimization is invalid. The first characters always match, so you don't need to test for them.

Alex, these things are very difficult to measure because the cost of a 100% predictable branch is also zero in a tight benchmark. The negative effects of useless tests are subtle and indirect (i.e. blowing other useful things out of the branch prediction table).

Victor, thanks for link to 17628. I will look at that further, but at first glance it looks like you're introducing a big wall of code right in the middle of a critical loop in code the is supposed to be in-lined. It too smells of a false optimization and places far too much hope that memcmp, case-statements, and whatnot will behave awesomely will all compilers.

Unless you object, I'm going to go ahead and remove the bogus test.

[alex]

The statistic that htis is *never* hit across a large python program is great evidence that this isn't useful. +1 on removing from me.

[python-dev]

New changeset 8f9bc9283400 by Raymond Hettinger in branch '3.3':
bpo-18719: Remove a false optimization
http://hg.python.org/cpython/rev/8f9bc9283400

[python-dev]

New changeset ac2f59a6637f by Raymond Hettinger in branch '2.7':
bpo-18719: Remove a false optimization
http://hg.python.org/cpython/rev/ac2f59a6637f