"""Почему `s += x` в цикле иногда быстрый, а иногда квадратичный.

ЗАЧЕМ ЭТОТ СКРИПТ. «Строки неизменяемы, поэтому склейка в цикле квадратична» —
верное рассуждение с неверным следствием: на практике `s += x` в обычном цикле
работает линейно. Причина — специализация `BINARY_OP_INPLACE_ADD_UNICODE`, и у
неё ДВА условия, а не одно. Первое — форма кода: следующей инструкцией должно
стоять `STORE_FAST` в ту же локальную переменную. Второе — во время работы: у
строки должно остаться ровно столько ссылок, чтобы её можно было менять на
месте. Блок 3 предъявляет оба: у двух функций опкод совпадает, а время
различается в сотню с лишним раз, и различает их именно второе условие.

ЗДЕСЬ ПРЕДЪЯВЛЯЕТСЯ И ТО И ДРУГОЕ: линейное поведение там, где быстрый путь
срабатывает, и квадратичное — там, где он не срабатывает. Второе важнее:
именно оно объясняет, почему один и тот же приём в одном месте кода безобиден,
а в другом кладёт программу.

ПРАВИЛО ЗАМЕРА. Всё меряется ВНУТРИ ОДНОГО запуска ОДНОГО интерпретатора, и
сравниваются только числа из одного прогона (bench/README.md). Между версиями
время не сравнивается вовсе. Поэтому запись прогона одна, без суффикса версии.

МЕТОДИКА. `timeit`, лучшее из девяти раундов. Берётся лучшее, а не среднее: шум
на этой машине односторонний.

ПОЧЕМУ КОД МЕРЯЕТСЯ ФУНКЦИЕЙ, А НЕ СТРОКОЙ В timeit. Быстрый путь зависит от
того, сколько ссылок на строку. У переменной модуля ссылка лежит в словаре
глобалей, и это меняет ответ. Чтобы разница между «локальная» и «не локальная»
была тем, что меряется, а не случайностью оформления, каждый случай — отдельная
функция, а `timeit` вызывает её.

ЗАПУСК:

    python3.13 bench/strings/concat.py
"""

import dis
import io
import platform
import sys
import timeit

ROUNDS = 9
N = 20_000
PIECE = "abcdefgh"


SETUP = f"""
from io import StringIO
N = {N}
X = {PIECE!r}

def local_var():
    s = ""
    for _ in range(N):
        s += X
    return s

def extra_reference():
    s = ""
    for _ in range(N):
        keep = s
        s += X
    return s

def list_slot():
    box = [""]
    for _ in range(N):
        box[0] += X
    return box[0]

def attribute():
    class Box:
        pass
    b = Box()
    b.s = ""
    for _ in range(N):
        b.s += X
    return b.s

def prepend():
    s = ""
    for _ in range(N):
        s = X + s
    return s

def join_list():
    parts = []
    for _ in range(N):
        parts.append(X)
    return "".join(parts)

def stringio():
    buf = StringIO()
    for _ in range(N):
        buf.write(X)
    return buf.getvalue()
"""


def best(stmt: str, setup: str, number: int) -> float:
    return min(timeit.Timer(stmt, setup).repeat(ROUNDS, number)) / number


def head(n: int, title: str) -> None:
    line = f"{n}. {title}"
    print(f"\n{line}\n{'-' * len(line)}")


def main() -> None:
    print(f"Python {platform.python_version()}")
    print(f"Сборка: {sys.version.split('[')[-1].rstrip('] ')}")
    print("\nВсе числа сняты одним запуском одного интерпретатора: сравнивать")
    print("их можно только между собой, с другими версиями — нельзя.")
    print(f"Склеивается {N} кусков по {len(PIECE)} символов. Лучшее из {ROUNDS} раундов.")

    head(1, "ОДИН И ТОТ ЖЕ ПРИЁМ В СЕМИ МЕСТАХ")
    cases = [
        ("s += X, s — локальная", "local_var()", 20),
        ("s += X, но есть вторая ссылка", "extra_reference()", 3),
        ("box[0] += X, элемент списка", "list_slot()", 3),
        ("b.s += X, атрибут объекта", "attribute()", 3),
        ("s = X + s, приписывание слева", "prepend()", 3),
        ('"".join(список)', "join_list()", 20),
        ("StringIO.write", "stringio()", 20),
    ]
    print("  где лежит строка                       всего, мс   нс на кусок")
    fast = None
    results = {}
    for name, call, number in cases:
        sec = best(call, SETUP, number)
        results[name] = sec
        if fast is None:
            fast = sec
        print(f"  {name:<38s} {sec * 1e3:>8.1f} {sec / N * 1e9:>13.0f}")
    keep = results["s += X, но есть вторая ссылка"]
    print(f"\n  Первая и вторая строки различаются в {keep / fast:.0f} раз. Разница в коде")
    print("  между ними — одна строка `keep = s`, которая ничего не делает.")
    print("  Она только сохраняет ссылку — и этого хватает, чтобы быстрый путь")
    print("  перестал применяться.")

    head(2, "ЦЕНА ОДНОГО ШАГА: ЗАВИСИТ ЛИ ОНА ОТ УЖЕ НАКОПЛЕННОГО")
    print("  Вот в чём разница на самом деле. У линейного накопления цена одного")
    print("  шага постоянна; у квадратичного каждый шаг копирует всё накопленное,")
    print("  и потому дорожает вместе с длиной.")
    print("  N        локальная: мс   нс на шаг    элемент списка: мс   нс на шаг")
    for n in (2_500, 5_000, 10_000, 20_000):
        setup = SETUP.replace(f"N = {N}", f"N = {n}")
        f = best("local_var()", setup, 50)
        s_ = best("list_slot()", setup, 5)
        print(f"  {n:<8d} {f * 1e3:>13.2f} {f / n * 1e9:>11.0f} {s_ * 1e3:>21.2f} {s_ / n * 1e9:>11.0f}")
    print("\n  Левая колонка «нс на шаг» не меняется: длина накопителя на цену")
    print("  шага не влияет вовсе. Правая растёт вместе с N — это и есть")
    print("  квадратичность, предъявленная, а не названная.")
    print("  Насколько именно быстро растёт правая колонка, этот замер не")
    print("  утверждает: на больших длинах в неё входит ещё и смена стратегии")
    print("  выделения памяти, а она здесь не отделена.")

    head(3, "ПОЧЕМУ ТАК: ДВА УСЛОВИЯ, А НЕ ОДНО")
    print("  Первое условие — форма кода. Специализация выбирается по тому, что")
    print("  стоит СЛЕДУЮЩЕЙ инструкцией, и видна в разобранном байт-коде:")
    ns: dict = {}
    exec(SETUP, ns)  # noqa: S102 — код свой, не из ввода
    print("  функция                        опкод сложения после прогрева")
    for name in ("local_var", "extra_reference", "list_slot", "attribute"):
        fn = ns[name]
        fn()
        buf = io.StringIO()
        dis.dis(fn, file=buf, adaptive=True)
        hits = sorted({w for line in buf.getvalue().splitlines()
                       for w in line.split() if w.startswith("BINARY_OP")})
        print(f"  {name:<30s} {' '.join(hits)}")
    print("\n  У двух первых функций опкод ОДИН И ТОТ ЖЕ, а время из блока 1 —")
    print("  разное. Значит, опкодом дело не кончается: внутри него есть второе")
    print("  условие, и оно про число ссылок. Комментарий в Python/bytecodes.c")
    print("  говорит это прямо:")
    print('    "If `left` has only two references remaining (one from the stack,')
    print('     one in the locals), DECREFing `left` leaves only the locals')
    print('     reference, so PyUnicode_Append knows that the string is safe')
    print('     to mutate."')
    print("\n  Строка `keep = s` добавляет третью ссылку — и строка перестаёт быть")
    print("  безопасной для изменения на месте. Опкод тот же, путь внутри другой.")

    head(4, "ЧТО ИЗ ЭТОГО ДЕЛАТЬ")
    print("  Три способа собрать ту же строку, числа из блока 1:")
    for name in ("s += X, s — локальная", '"".join(список)', "StringIO.write"):
        print(f"    {name:<38s} {results[name] * 1e3:>8.1f} мс")
    print("\n  join не быстрее склейки по месту — он НАДЁЖНЕЕ: его время не зависит")
    print("  от того, где лежит накопитель, и от того, сохранил ли кто-то ссылку.")


main()