[New-bugs-announce] [issue38477] magiccube2x2 permutations 28% slower with Python 3.8.0rc1 vs 3.7

[Louis Huemiller]

New submission from Louis Huemiller <lhuemill at gmail.com>:

Have created a program that by brute force determines all reachable states of a 2-by-2 MagicCube, sometimes referred to as a 2x2 Rubick's cube. On one of my servers, which is described in the attached file 20191011b_configuration, this program takes 19520.03 seconds to execute under Python2.7.15+, while under 3.8.0rc1 it takes 21887.53 seconds. This program is taking 12.13% longer to execute with 3.8.0rc1 versus 2.7.15+. The exact versions of Python as reported by sys.version are:

  2.7.15+ (default, Oct  7 2019, 17:39:04)
  [GCC 7.4.0]

  3.8.0rc1 (default, Oct  1 2019, 21:48:24)
  [GCC 7.4.0]

Used the following script to execute this program under Python 2.7, 3.6, 3.7, and 3.8:

  mkdir -p ./results
  echo "======== git log ========" > ./results/20191011b_configuration
  git log -n4 >> ./results/20191011b_configuration

  echo ""  >> ./results/20191011b_configuration
  echo "======== uname ========" >> ./results/20191011b_configuration
  uname -a >> ./results/20191011b_configuration

  echo ""  >> ./results/20191011b_configuration
  echo "======== lsb_release ========" >> 
  ./results/20191011b_configuration
  lsb_release -a >> ./results/20191011b_configuration

  echo ""  >> ./results/20191011b_configuration
  echo "======== lshw ========" >> ./results/20191011b_configuration
  sudo lshw >> ./results/20191011b_configuration

  make clean
  make
  ./target/permutations2x2 > \
    ./results/20191011b_magiccube2x2_permutations_cxx_unordered_map 2>&1
  python3.8 ./permutations2x2  > \
    ./results/20191011b_magiccube2x2_permutations_python3.8.0rc1 2>&1
  python3.7 ./permutations2x2  > \
    ./results/20191011b_magiccube2x2_permutations_python3.7 2>&1
  python3.6 ./permutations2x2  > \
    ./results/20191011b_magiccube2x2_permutations_python3.6 2>&1
  python2.7 ./permutations2x2  > 
  ./results/20191011b_magiccube2x2_permutations_python2.7 2>&1

Doing egrep "^# Total_Time:" on each of the output files, shows that the various executions took the following amount of time:

  cxx_unordered_map:# Total_Time: 1098.25
  python2.7:# Total_Time: 19520.03
  python3.6:# Total_Time: 19562.28
  python3.7:# Total_Time: 17012.67
  python3.8.0rc1:# Total_Time: 21887.53

Under Python2.7 and Python3.6 the program ran in approximately the same amount of time, while under Python3.7 it ran 12.8% faster than execution with Python2.7. Finally, the python3.8.0rc1 execution is noticeably slower than all the other executions, at 12.1% lower than Python2.7 and 28.6% slower than Python3.7.

The source for the magic_cube2x2 program is available under gist.github.com at:

  https://gist.github.com/lhuemill/f1273291e5f5e85e4b42e5c7614e60ef

This program creates a fairly large dictionary of 88.179840M entries. Each entry has a key of a string of length 29 and a value string of with a maximum length of 22 characters. A quick back-of-the-envelope calculation shows that this dictionary would use approximately 9GB of memory, but for some reason, all of the Python executions use approximately 22.6GB of memory. Even the C++ version is using 20.2GB when the permutations are stored in an unordered_map<string, string> and 20.55GB when stored in a map<string, string>. Quite surprising that the C++ is using over twice the expected amount of memory.

  CAUTION: When executing this program with less than the needed
           amount of physical memory, be careful that swap is not
           backed by a flash device. Doing so will likely cause
           a significant amount of I/O to the flash device and
           likely quickly wear it out.

----------
files: 20191005b_configuration
messages: 354682
nosy: Louis Huemiller
priority: normal
severity: normal
status: open
title: magiccube2x2 permutations 28% slower with Python 3.8.0rc1 vs 3.7
type: performance
versions: Python 3.8
Added file: https://bugs.python.org/file48660/20191005b_configuration

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue38477>
_______________________________________