Filled rings unusably slow on large structures

[goddard@…]

The following bug report has been submitted:
Platform:        Darwin-19.4.0-x86_64-i386-64bit
ChimeraX Version: 1.1.dev202006011833 (2020-06-01 18:33:55 UTC)
Description
Filled rings take 128 seconds to display on a large structure 4v88.  This takes so long the user will probably kill the program assuming it is hung (I did the first time).  A main strength of ChimeraX is speed with large structures.

Log:
UCSF ChimeraX version: 1.1.dev202006011833 (2020-06-01)  
© 2016-2020 Regents of the University of California. All rights reserved.  
How to cite UCSF ChimeraX  

> open 4v88 format mmcif fromDatabase pdb

Summary of feedback from opening 4v88 fetched from pdb  
---  
warnings | Atom OP1 has no neighbors to form bonds with according to residue
template for G /A5:420  
Atom OP2 has no neighbors to form bonds with according to residue template for
G /A5:420  
Ignoring microheterogeneity for label_seq_id 3 in chain BO  
Ignoring microheterogeneity for label_seq_id 4 in chain BO  
Ignoring microheterogeneity for label_seq_id 11 in chain BO  
Ignoring microheterogeneity for label_seq_id 13 in chain BO  
Ignoring microheterogeneity for label_seq_id 16 in chain BO  
35 messages similar to the above omitted  
  
4v88 title:  
The structure of the eukaryotic ribosome at 3.0 A resolution. [more info...]  
  
Chain information for 4v88 #1  
---  
Chain | Description  
A1 A5 | 25S rRNA  
A2 | 18S ribosomal RNA  
A3 A7 | 5S rRNA  
A4 A8 | 5.8S rRNA  
A6 | 18S rRNA  
AA CA | 40S ribosomal protein S0-A  
AB CB | 40S ribosomal protein S1-A  
AC CC | 40S ribosomal protein S2  
AD CD | 40S ribosomal protein S3  
AE CE | 40S ribosomal protein S4-A  
AF CF | 40S ribosomal protein S5  
AG CG | 40S ribosomal protein S6-A  
AH CH | 40S ribosomal protein S7-A  
AI CI | 40S ribosomal protein S8-A  
AJ CJ | 40S ribosomal protein S9-A  
AK CK | 40S ribosomal protein S10-A  
AL CL | 40S ribosomal protein S11-A  
AM CM | 40S ribosomal protein S12  
AN CN | 40S ribosomal protein S13  
AO CO | 40S ribosomal protein S14-A  
AP CP | 40S ribosomal protein S15  
AQ CQ | 40S ribosomal protein S16-A  
AR CR | 40S ribosomal protein S17-A  
AS CS | 40S ribosomal protein S18-A  
AT CT | 40S ribosomal protein S19-A  
AU CU | 40S ribosomal protein S20  
AV CV | 40S ribosomal protein S21-A  
AW CW | 40S ribosomal protein S22-A  
AX CX | 40S ribosomal protein S23-A  
AY CY | 40S ribosomal protein S24-A  
AZ CZ | 40S ribosomal protein S25-A  
Aa Ca | 40S ribosomal protein S26-A  
Ab Cb | 40S ribosomal protein S27-A  
Ac Cc | 40S ribosomal protein S28-A  
Ad Cd | 40S ribosomal protein S29-A  
Ae Ce | 40S ribosomal protein S30-A  
Af Cf | 40S ribosomal protein S31  
Ag Cg | Guanine nucleotide-binding protein subunit beta-like protein (ASC1,
RACK1)  
Ah | Suppressor protein STM1  
BA DA | 60S ribosomal protein L2-A  
BB DB | 60S ribosomal protein L3  
BC DC | 60S ribosomal protein L4-A  
BD DD | 60S ribosomal protein L5  
BE DE | 60S ribosomal protein L6-A  
BF DF | 60S ribosomal protein L7-A  
BG DG | 60S ribosomal protein L8-A  
BH DH | 60S ribosomal protein L9-A  
BI DI | 60S ribosomal protein L10  
BJ DJ | 60S ribosomal protein L11-A  
BL DL | 60S ribosomal protein L13-A  
BM DM | 60S ribosomal protein L14-A  
BN DN | 60S ribosomal protein L15-A  
BO DO | 60S ribosomal protein L16-A, 60S ribosomal protein L16-B  
BP DP | 60S ribosomal protein L17-A  
BQ DQ | 60S ribosomal protein L18-A  
BR DR | 60S ribosomal protein L19-A  
BS DS | 60S ribosomal protein L20-A  
BT DT | 60S ribosomal protein L21-A  
BU DU | 60S ribosomal protein L22-A  
BV DV | 60S ribosomal protein L23-A  
BW DW | 60S ribosomal protein L24-A  
BX DX | 60S ribosomal protein L25  
BY DY | 60S ribosomal protein L26-A  
BZ DZ | 60S ribosomal protein L27-A  
Ba Da | 60S ribosomal protein L28  
Bb Db | 60S ribosomal protein L29  
Bc Dc | 60S ribosomal protein L30  
Bd Dd | 60S ribosomal protein L31-A  
Be De | 60S ribosomal protein L32  
Bf Df | 60S ribosomal protein L33-A  
Bg Dg | 60S ribosomal protein L34-A  
Bh Dh | 60S ribosomal protein L35-A  
Bi Di | 60S ribosomal protein L36-A  
Bj Dj | 60S ribosomal protein L37-A  
Bk Dk | 60S ribosomal protein L38  
Bl Dl | 60S ribosomal protein L39  
Bm Dm | 60S ribosomal protein L40  
Bn Dn | 60S ribosomal protein L41-A  
Bo Do | 60S ribosomal protein L42-A  
Bp Dp | 60S ribosomal protein L43-A  
Ch | Suppressor protein STM1  
DK | Ribosomal protein L12  
Dq | 60S acidic ribosomal protein P0  
Dr | Ribosomal protein P1 α  
Ds | Ribosomal protein P2 β  
  
Non-standard residues in 4v88 #1  
---  
MG — magnesium ion  
OHX — osmium (III) hexammine (osmium(6+) hexaazanide)  
ZN — zinc ion  
  
4v88 mmCIF Assemblies  
---  
1| author_defined_assembly  
2| author_defined_assembly  
  

> time style stick

> style stick

Changed 413613 atom styles  
command time 0.3252 seconds  
draw time 0.391 seconds  

> time style ring thick

> style ringFill thick

Changed 36905 residue ring styles  
command time 0.0361 seconds  
draw time 128.8 seconds  

> zoom 4

> lighting simple

> lighting soft




OpenGL version: 4.1 ATI-3.8.24
OpenGL renderer: AMD Radeon Pro Vega 20 OpenGL Engine
OpenGL vendor: ATI Technologies Inc.Hardware:

    Hardware Overview:

      Model Name: MacBook Pro
      Model Identifier: MacBookPro15,3
      Processor Name: 8-Core Intel Core i9
      Processor Speed: 2.4 GHz
      Number of Processors: 1
      Total Number of Cores: 8
      L2 Cache (per Core): 256 KB
      L3 Cache: 16 MB
      Hyper-Threading Technology: Enabled
      Memory: 32 GB
      Boot ROM Version: 1037.100.362.0.0 (iBridge: 17.16.14281.0.0,0)

Software:

    System Software Overview:

      System Version: macOS 10.15.4 (19E287)
      Kernel Version: Darwin 19.4.0
      Time since boot: 24 days 20:05

Graphics/Displays:

    Intel UHD Graphics 630:

      Chipset Model: Intel UHD Graphics 630
      Type: GPU
      Bus: Built-In
      VRAM (Dynamic, Max): 1536 MB
      Vendor: Intel
      Device ID: 0x3e9b
      Revision ID: 0x0002
      Automatic Graphics Switching: Supported
      gMux Version: 5.0.0
      Metal: Supported, feature set macOS GPUFamily2 v1

    Radeon Pro Vega 20:

      Chipset Model: Radeon Pro Vega 20
      Type: GPU
      Bus: PCIe
      PCIe Lane Width: x8
      VRAM (Total): 4 GB
      Vendor: AMD (0x1002)
      Device ID: 0x69af
      Revision ID: 0x00c0
      ROM Revision: 113-D2060I-087
      VBIOS Version: 113-D20601MA0T-016
      Option ROM Version: 113-D20601MA0T-016
      EFI Driver Version: 01.01.087
      Automatic Graphics Switching: Supported
      gMux Version: 5.0.0
      Metal: Supported, feature set macOS GPUFamily2 v1
      Displays:
        Color LCD:
          Display Type: Built-In Retina LCD
          Resolution: 2880 x 1800 Retina
          Framebuffer Depth: 24-Bit Color (ARGB8888)
          Main Display: Yes
          Mirror: Off
          Online: Yes
          Automatically Adjust Brightness: No
          Connection Type: Internal

PyQt version: 5.12.3
Compiled Qt version: 5.12.4
Runtime Qt version: 5.12.8

[Tom Goddard]

Testing some different size examples it seems the time is quadratic in the number of residues with rings.

[Greg Couch]

This is probably the same probably problem as using += to concatenate strings in Python instead of ''.join(). The rings are added one-by-one with AtomicShapeDrawing.add_shape().

[Greg Couch]

Adding a add_shapes API, to add multiple shapes at one time, changed the 4v88 drawing time for thick rings from 749 seconds to 39 seconds on my computer -- 19X faster. Subsequent removing (style ring off) and drawing of the rings (style ring thick) is 14.4 seconds. The main difference is that the rings are already computed (23.3 seconds), so that is the new bottleneck.

Not sure where to log this. Would like to put this in a bundle-specific change log.

[Tom Goddard]

Takes 4 seconds to display thick filled rings of 4v88 on my test machine with your change, not including ring finding. Other display style changes (sphere, stick, ball and stick) take a few tenths of a second. If filled rings were routinely used I'd want it under 1 second. Since they are rarely used I can live with 4 seconds.

[pett]

So, approximately 1000 years ago I looked into faster ring-finding algorithms but none of them did what I needed to be done (typically they would miss some of the important ring possibilities in a fused-ring system). But 1000 years ago there were no structures as large as there are now, so some of the trade offs in the code have changed. Specifically, it looks through unvisited atoms in a structure and tries to find rings from there, stopping at residue boundaries if 'cross_residue' is false. This involved maintaining a map of visited atoms, which we now know gets slow to maintain and test when it gets large. So, it may pay to bifurcate the algorithm based on 'cross_residue' and do the search on a per-residue basis if cross_residue is false. It's more code, and certainly wasn't worth the effort in the "old days" but it is worth at least trying out now.

[pett]

So splitting ring-finding into sibling routines based on whether cross-residue rings were wanted or not did in fact speed up ring finding. For 4v88 it went from 7.7 seconds down to 1.5 seconds. I have committed the change. As an aside I should mention that ring finding for atom-typing purposes is much much faster than this because it only looks for rings in non-standard residues (since it knows the atom types of standard residues).