int << 0: return the number unmodified

[vstinner]

BPO	21422
Nosy	@rhettinger, @jcea, @mdickinson, @pitrou, @vstinner, @bitdancer, @serhiy-storchaka
Files	long_lshift0.patch

^{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 2014-05-12.20:44:42.385>
created_at = <Date 2014-05-03.12:34:17.703>
labels = ['performance']
title = 'int << 0: return the number unmodified'
updated_at = <Date 2014-05-13.16:28:57.380>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2014-05-13.16:28:57.380>
actor = 'francismb'
assignee = 'none'
closed = True
closed_date = <Date 2014-05-12.20:44:42.385>
closer = 'vstinner'
components = []
creation = <Date 2014-05-03.12:34:17.703>
creator = 'vstinner'
dependencies = []
files = ['35144']
hgrepos = []
issue_num = 21422
keywords = ['patch']
message_count = 17.0
messages = ['217822', '217834', '217837', '217862', '217886', '217896', '217913', '218343', '218348', '218350', '218358', '218359', '218363', '218364', '218372', '218376', '218472']
nosy_count = 10.0
nosy_names = ['rhettinger', 'jcea', 'mark.dickinson', 'pitrou', 'vstinner', 'Arfrever', 'r.david.murray', 'python-dev', 'francismb', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue21422'
versions = ['Python 3.5']

[vstinner]

I propose to add a micro-optimization for int << 0: return the number unmodified.

See attached patch.

[rhettinger]

Every branch has a cost (in particular, it tends to contaminate global branch prediction tables and blow other code out of the L1 code cache). The cost isn't big, but branches shouldn't be added unless we know there is a real benefit.

I would think that in real-world code, this branch will almost never be taken. The common case will pay a price (albiet a small one) for almost zero benefit.

[vstinner]

I would think that in real-world code, this branch will almost never be
taken. The common case will pay a price (albiet a small one) for almost
zero benefit.

I think that x << 0 is common even if it's not written like that (it's more
for i in range(8): ... x << i).

The benefit is to reduce the memory footprint.

Can you sow the overhead of the branch in a microbenchmark? The test is
only done once, it's out of a loop.

*If* it's possible to notice an overhead, we can maybe use GCC macro
unlikely().

[mdickinson]

Can you sow the overhead of the branch in a microbenchmark?

Conversely, can you show a case where this optimisation provides a benefit in real code? We should be looking for a reason *to* apply the patch, not a reason *not* to apply the patch.

[vstinner]

The reason to apply the patch is to reduce the memory footprint.

[pitrou]

Reduce the memory footprint in which actual workload? This looks rather gratuitous to me.

[mdickinson]

BTW, there's also a behaviour change here. Before the patch:

>>> True << 0
1

After the patch:

>>> True << 0
True

Which demonstrates another good reason to avoid trivial-looking optimisations: it's far too easy to accidentally change behaviour.

[francismb]

Hi,
sorry if it's trivial but shouldn't we add a 'shifted_true' test
some were to make sure that this behavior change gets noticed next time?

def test_shifted_true(self):
    self.assertEqual(True << 0, 1)
    self.assertEqual(True << 1, 2)

[bitdancer]

Francisco: I'd say that was a good idea. Would you like to propose a patch? (ie: figure out where it should go)

[Arfrever]

Use assertIs, since True == 1, but True is not 1.

[python-dev]

New changeset ef49aaad3812 by Victor Stinner in branch '3.4':
Issue bpo-21422: Add a test to check that bool << int and bool >> int return an int
http://hg.python.org/cpython/rev/ef49aaad3812

New changeset 3da4aed1d18a by Victor Stinner in branch 'default':
(Merge 3.4) Issue bpo-21422: Add a test to check that bool << int and bool >> int
http://hg.python.org/cpython/rev/3da4aed1d18a

[vstinner]

Ok, 3 core dev are opposed to the change, I close the issue.

I added a test on bool >> int and bool << int to ensure that the result is an int.

[francismb]

I Victor you were so fast, I started with one patch also in bool (at least the place was right). The problem is that I was getting some extrage (for me at least). As far I hat:

    def test_shifted_true(self):
    	with self.assertRaises(ValueError):
    	    True << -1
    	self.assertIs(True << 0, 1)
    	self.assertIs(True << 1, 2)
    	self.assertEqual(True << 63, 1 << 63)
    	self.assertIs(True << 63, 1 << 63)

And I'm getting:

======================================================================
FAIL: test_shifted_true (test.test_bool.BoolTest)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/ci/Prog/cpython/src/Lib/test/test_bool.py", line 349, in test_shifted_true
    self.assertIs(True << 63, 1 << 63)
AssertionError: 9223372036854775808 is not 9223372036854775808

---

That's:
./python --version
Python 3.5.0a0

>>> type(True<<63)
<class 'int'>
>>> type(1<<63)
<class 'int'>

hg tip
changeset: 90664:4e33c343a264

What I'm doing wrong?
That's:
./python --version
Python 3.5.0a0

>>> type(True<<63)
<class 'int'>
>>> type(1<<63)
<class 'int'>

hg tip
changeset: 90664:4e33c343a264

What I was doing wrong?

Thanks in advance!
francis

[vstinner]

What I was doing wrong?

The "is" operator should only be used to compare identical objects. Small integers (range -5..255 if I remember correctly) are singletons. I prefer to not rely on this implementation detail in a unit test of the Python standard library.

[bitdancer]

Arfrever's advice was misleading...the test would have needed to be assertIsNot(True << 0, 1), but the fact that True is not preserved is not really what we want to test. What we want to test is that the return value is of type 'int', which is what Victor's test checks.

[bitdancer]

Arfrever pointed out on irc that I misread. It would indeed be assertIs(True << 0, 1), but that wouldn't make a good test because the fact that '1 is 1' is an implementation detail of CPython and can't be relied upon.

[francismb]

What we want to test is that the return value is of type 'int', which is what Victor's test checks.

Thank you for the explanations!

for 2.7.6 type(2 << 62) is <type 'long'> and type(2 << 61) is
<type 'int'> (I suppose it's analogous in a 32 bit machine
around type(2 << 30) so I just wanted to test on that limits).

Is that still relevant? or is too much detail and we should stop here.

Regards,
francis