closes bpo-31608: Fix a crash in methods of a subclass of _collections.deque with a bad __new__(). (GH-3788)

Make also minor PEP8 coding style fixes on modified imports.

Based on patch by Ville Skyttä.

Affected classes are generic sequence iterators, iterators of str, bytes,
bytearray, list, tuple, set, frozenset, dict, OrderedDict, corresponding
views and os.scandir() iterator.

Reported by John Leitch and Bryce Darling, patch by Raymond Hettinger.

Remove the old comment suggesting that it was desireable to have
blocksize+2 as a multiple of the cache line length.  That would
have made sense only if the block structure start point was always
aligned to a cache line boundary.  However, the memory allocations
are 16 byte aligned, so we don't really have control over whether
the struct spills across cache line boundaries.

(Patch contributed by Claudiu Popa.)

The former block size traded away good fit within cache lines in
order to gain faster division in deque_item().  However, compilers
are getting smarter and can now replace the slow division operation
with a fast integer multiply and right shift.  Accordingly, it makes
sense to go back to a size that lets blocks neatly fill entire
cache-lines.

GCC-4.8 and CLANG 4.0 both compute "x // 62" with something
roughly equivalent to "x * 9520900167075897609 >> 69".

The division and modulo calculation in deque_item() can be compiled
to fast bitwise operations when the BLOCKLEN is a power of two.

Timing before:

 ~/cpython $ py -m timeit -r7 -s 'from collections import deque' -s 'd=deque(range(10))' 'd[5]'
10000000 loops, best of 7: 0.0627 usec per loop

Timing after:

~/cpython $ py -m timeit -r7 -s 'from collections import deque' -s 'd=deque(range(10))' 'd[5]'
10000000 loops, best of 7: 0.0581 usec per loop

(Reviewed by Georg Brandl.)

Also made similar changes to deque.reverse() though this wasn't
strictly necessary (the edge case cannot occur with two pointers
moving to meet in the middle).  Making the change in reverse()
was more a matter of future-proofing.

svn+ssh://pythondev@svn.python.org/python/branches/py3k

........
  r86596 | ezio.melotti | 2010-11-20 21:04:17 +0200 (Sat, 20 Nov 2010) | 1 line

  #9424: Replace deprecated assert* methods in the Python test suite.
........

svn+ssh://pythondev@svn.python.org/python/trunk

........
  r78093 | georg.brandl | 2010-02-07 18:03:15 +0100 (So, 07 Feb 2010) | 1 line

  Remove unused imports in test modules.
........

A patch from Dave Malcolm.