Reinstalled the server I'd been using for this issue, with Ubuntu 18.04.3 LTS Server amd64. This installation already came with Python3.6.8.  Downloaded and installed Python3.7.3 and 3.8.0 from:

  https://www.python.org/ftp/python/3.7.3/Python-3.7.3.tgz
  https://www.python.org/ftp/python/3.8.0/Python-3.8.0.tgz

The installation process was somewhat complicated, with several to be discovered prerequisites.  Used "apt install" to install the following needed dependencies:

  build-essential checkinstall libreadline-gplv2-dev libncursesw5-dev libssl-dev libsqlite3-dev tk-dev libgdbm-dev libc6-dev libbz2-dev zlib1g-dev libffi-dev

Then was able to do the following to build and install the downloaded Python3.7.3 and 3.8.0:

  $ sudo ./configure --enable-optimizations
  $ sudo -H make altinstall

Then downloaded a clone of my magiccube2x2 repository and obtained the following results:

  $ python3.6 ./permutations2x2 --max_depth 6 | egrep "^# Total_Time:"
  # Total_Time: 69.02
  $ python3.7 ./permutations2x2 --max_depth 6 | egrep "^# Total_Time:"
  # Total_Time: 84.52
  $ python3.8 ./permutations2x2 --max_depth 6 | egrep "^# Total_Time:"
  # Total_Time: 83.14

In this case the runtimes under both of the Python versions that I downloaded the source for and built are significantly slower than the run with python3.6, which came already as part of Ubuntu 18.04.3.

Instead of using the version of python3.7.3 that I built, was able to do:

  $ sudo apt install python3.7

to get one that had already been built for Ubuntu.  Doing this allowed the following result:

  $ /usr/bin/python3.7 ./permutations2x2 --max_depth 6 \
    | egrep "^# Total_Time:"
  # Total_Time: 62.39

Which is better than even the Python3.6 result.  Unfortunately, there is not currently a pre-built Ubuntu package for Python3.8 and the one from ppa:deadsnakes/ppa, I already know has the performance issue.

I did some searching on wiki.python.org and I was unable to find any instructions for how to build python from the source.  Perhaps the instructions are already there but I was unable to find them.

Perhaps this issue should be re-opened as a documentation error. I could really use instructions on how to built a performance version of Python and I suspect several others could also use this. For example, I'd like to pass that information to the maintainers of the deadsnakes repository.