Вот такие "мысли" у Квена, думаю принять предложение и сделать ещё пару оптимизаций. Пока угрожающим выглядит рост памяти. Но! Измерения показывают соответствие теоретической сложности
которая считается минимально достижимой.
реализации, я делаю кольцевую факторизацию (колесо 2130) для ускорения.
Анализ производительности: primepi vs primecount
Введение
========
Сравниваются две реализации вычисления функции π(x): высокооптимизированная библиотека primecount (Kim Walisch) и учебная реализация алгоритма Gourdon (primepi). Все тесты проводились на одинаковом оборудовании.
1. Время выполнения (wall clock)
================================
Код:
x primecount primepi Отношение
─────────────────────────────────────────────────
10¹² 0.05s 1.39s 28×
10¹³ 0.07s 6.19s 89×
10¹⁴ 0.22s 28.13s 128×
Рост времени при увеличении x в 10 раз:
Код:
Переход primecount primepi
─────────────────────────────────────
10¹² → 10¹³ ×1.4 ×4.5
10¹³ → 10¹⁴ ×3.1 ×4.5
Средний рост ×2.1 ×4.5
Интерпретация:
- primecount: рост ~O(x^0.3) — очень медленный, благодаря оптимизациям (batch processing, кэширование, SIMD);
- primepi: рост ~O(x^0.65) — соответствует теоретическому O(x^(2/3)) для алгоритма Gourdon без оптимизаций.
2. Потребление памяти (RSS)
============================
Код:
x primecount primepi Отношение
─────────────────────────────────────────────────
10¹² 6.7 MB 18.9 MB 2.8×
10¹³ 8.2 MB 62.5 MB 7.6×
10¹⁴ 10.3 MB 262.7 MB 25.4×
Рост памяти при увеличении x в 10 раз:
Код:
Переход primecount primepi
─────────────────────────────────────
10¹² → 10¹³ ×1.2 ×3.3
10¹³ → 10¹⁴ ×1.3 ×4.2
Средний рост ×1.25 ×3.7
Интерпретация:
- primecount: рост ~O(x^0.1) — почти константная память (сегментированные алгоритмы с маленькими сегментами);
- primepi: рост ~O(x^0.57) — соответствует O(x/y) = O(x^(2/3)) для SegmentedPiTable в B.
3. Использование CPU
====================
Код:
x primecount CPU primepi CPU
─────────────────────────────────────────
10¹² 430% (4.3 ядра) 99% (1 ядро)
10¹³ 492% (4.9 ядер) 99% (1 ядро)
10¹⁴ 503% (5.0 ядер) 99% (1 ядро)
Ключевой вывод: primecount использует
~5 ядер параллельно. Если бы primepi тоже использовал 5 ядер, время уменьшилось бы в 5 раз, и разница составила бы ~25× вместо 128×.
4. Анализ компонентов primepi
==============================
Рост времени по компонентам:
Код:
x Sigma B Phi0 AC D Total
───────────────────────────────────────────────────────────────
10¹² 0.019s 0.429s 0.005s 0.066s 0.862s 1.38s
10¹³ 0.029s 1.984s 0.010s 0.295s 3.861s 6.18s
10¹⁴ 0.059s 9.360s 0.022s 0.773s 17.906s 28.12s
Доля компонентов на x = 10¹⁴:
Код:
Компонент Время Доля
────────────────────────────
D 17.906s 64% ← главное узкое место
B 9.360s 33% ← второе узкое место
AC 0.773s 3%
Sigma 0.059s <1%
Phi0 0.022s <1%
Рост B и D (× при увеличении x в 10 раз):
Код:
Компонент 10¹²→10¹³ 10¹³→10¹⁴
───────────────────────────────────
B ×4.6 ×4.7
D ×4.5 ×4.6
Оба компонента растут как
O(x^0.67) — это теоретическая сложность алгоритма Gourdon для B и D.
5. Анализ потребления памяти primepi
=====================================
Оценка теоретической памяти на x = 10¹⁴:
Код:
SegmentedPiTable в B:
xy = x/y = 10¹⁴ / 46416 ≈ 2.15×10⁹
bits_: 2.15×10⁹ бит / 8 = 269 MB
pi_: 2.15×10⁹ / 128 × 8 байт = 134 MB
Итого: ~400 MB (но реально меньше из-за сегментации)
Фактическая память (RSS = 262.7 MB):
- SegmentedPiTable: ~200 MB (bits_ + pi_ для сегмента [√x, xy]);
- FactorTableD: ~10 MB (wheel 2310 для z = 46416);
- primes, phi_vector, sieve: ~50 MB;
- прочее: ~3 MB.
Вывод: память определяется
SegmentedPiTable в B, которая занимает O(x/y) бит.
6. Почему primecount эффективнее
================================
Время (28–128× быстрее):
Код:
Фактор Вклад
─────────────────────────────────────────
Многопоточность (5 ядер) ×5
Wheel 30 + SIMD в Sieve ×3–5
Batch processing в D ×2–3
libdivide ×1.5–2
Lookup table для phi_tiny ×2–3
─────────────────────────────────────────
Итого ×90–450
Память (2.8–25× экономнее):
Код:
Фактор Вклад
─────────────────────────────────────────────
Меньшие сегменты в SegmentedPiTable ×2–3
Оптимизированные структуры данных ×2–3
Кэширование вместо хранения ×2–3
─────────────────────────────────────────────
Итого ×8–27
7. Итоговая оценка
===================
Сильные стороны primepi:-
Корректность — все результаты совпадают с primecount до 10¹⁴;
-
Низкая сложность кода — легко читать и понимать;
-
Учебная ценность — реализован полный алгоритм Gourdon;
-
Приемлемая производительность — 10¹⁴ за 28 секунд на одном ядре.
Слабые стороны:-
Время в 128× хуже — но только ~25× из-за однопоточности;
-
Память в 25× хуже — растёт как O(x^(2/3)) вместо O(x^(1/3));
-
D и B — узкие места — занимают 97% времени.
Потенциал оптимизации:Код:
Оптимизация Ожидаемое ускорение
───────────────────────────────────────────────
OpenMP (5 ядер) ×5
Wheel 30 Sieve ×2–3
Batch processing в D ×2–3
Lookup table для phi_tiny ×2–3
───────────────────────────────────────────────
Итого ×40–135
После всех оптимизаций primepi мог бы работать
в 1–3 раза медленнее primecount, что было бы отличным результатом для учебного проекта.
Прогноз для x = 10¹⁵ и 10¹⁶:Код:
x primepi (текущее) primepi (прогноз) primecount (прогноз)
───────────────────────────────────────────────────────────────────────────
10¹⁵ ~130s ~3–5s ~1s
10¹⁶ ~600s ~15–25s ~3–5s
10¹⁷ ~2800s ~70–120s ~10–20s
Вывод: текущая реализация позволяет комфортно работать до x = 10¹⁴, после оптимизаций — до x = 10¹⁶.
