Drawing lines / `add_shape()` is very slow, possible quadratic Schlemiel the Painter algorithm

packages/python/plotly/plotly/basedatatypes.py の 5310 行目付近と packages/python/plotly/_plotly_utils/basevalidators.py の 2553 行目付近から始め、その後、提供された lines.py の再現コードを実行します。add_shape() を繰り返し呼び出したときに値がどのように増加するかを確認します。多数の線を描画しても、線あたりの時間が線形に増加せず、想定どおりミリ秒単位で完了すれば完了です。

To reproduce: Create lines.py as follows:

import plotly.graph_objects as go
import plotly.express as px

import time
import random

N = [50, 100, 200, 400, 800]

def plot_random_lines(n):
    fig = go.Figure()
    for i in range(n):
        c = [random.random() for _ in [0, 1, 2, 3]]
        fig.add_shape(type='line', x0=c[0], y0=c[1], x1=c[2], y1=c[3])
    # We don't show the figure to avoid any possible influence from the
    # graphics driver.

def timings():
    t_cum = []
    for n in N:
        t0 = time.process_time_ns()
        plot_random_lines(n)
        t_cum.append((time.process_time_ns() - t0) / 1e6)

    t_per_line = [t/n for (t, n) in zip(t_cum, N)]

    fig1 = px.scatter(x=N, y=t_cum, labels={'x': 'Number of lines', 'y': 'Cumulative time [ms]'})
    fig1.show()
    fig2 = px.scatter(x=N, y=t_per_line, labels={'x': 'Number of lines', 'y': 'Time per line [ms]'})
    fig2.show()

timings()

Install plotly and run the above example.

• Expected: Draws the lines in a few milliseconds
• Actual: It takes more than half a minute on a modern MacBook

Notice that the time per line increases linearly with the number of lines drawn.

This looks like a classic example of a Schlemiel the painter algorithm, candidate for
Joel Spolsky's collection.

Observations

I suspect that the following code locations are related to the bug.

• In https://github.com/plotly/plotly.py/blob/master/packages/python/plotly/plotly/basedatatypes.py#L5310, curr_val increases in length with each call to add_shape().
• In https://github.com/plotly/plotly.py/blob/master/packages/python/plotly/_plotly_utils/basevalidators.py#L2553, v increases in length with each call.