Производительные вычисления на Nim

Разбираем две классические вычислительные задачи на Nim и смотрим, откуда берётся выигрыш в скорости.

Компилируемый язык — это язык, программа на котором превращается в готовый машинный код ещё до запуска, а не построчно разбирается на лету, как в Python.

Зачем вообще думать о скорости

Python прекрасен почти во всём — кроме одного: он интерпретируемый. Это значит, что каждую строчку кода Python-программа разбирает и выполняет заново при каждом запуске, каждую операцию сложения или сравнения оборачивает в проверки типов «на лету». Для большинства задач — сайтов, скриптов, обработки текста — это совершенно незаметно. Но если тебе нужно посчитать что-то миллион раз подряд — просимулировать физику, обработать большой массив данных, перебрать много вариантов в олимпиадной задаче — эти накладные расходы начинают складываться в секунды и минуты ожидания.

Nim решает эту проблему в лоб: он компилируется в код на языке C, а тот, в свою очередь, компилятор C превращает в нативный машинный код под твою операционную систему. К моменту запуска программа уже не «понимает» синтаксис Nim — она состоит из готовых процессорных инструкций. Никакого разбора текста на лету, никаких проверок типов в рантайме (компилятор проверил типы заранее, ещё на этапе сборки). Отсюда и скорость, сравнимая с C и C++, при синтаксисе, который выглядит почти как Python.

Задача первая: числа Фибоначчи

Последовательность Фибоначчи — классика: каждое следующее число равно сумме двух предыдущих (1, 1, 2, 3, 5, 8, 13...). Простая с виду задача, но она отлично показывает разницу в подходах, если считать много чисел подряд.

proc fib(n: int): int =
  var a = 0
  var b = 1
  for i in 0 ..< n:
    let next = a + b
    a = b
    b = next
  result = a

for i in [10, 20, 30, 40]:
  echo "fib(", i, ") = ", fib(i)

Разберём построчно. proc fib(n: int): int = объявляет процедуру (так в Nim называют функцию) с параметром n типа int и результатом тоже типа int — оба типа компилятор проверит заранее и ни разу не станет гадать «на лету», что там за число. Дальше — два счётчика a и b, объявленных через var (значит, их можно менять), и цикл for i in 0 ..< n, который пробегает n раз (оператор ..< — это диапазон «до, но не включая», как range(n) в Python). Внутри цикла считаем следующее число суммой предыдущих двух и сдвигаем окно — ровно тот же приём, что используют и в Python-версии этой задачи. Последняя строчка процедуры записывает ответ в специальную переменную result — в Nim это встроенное имя, которое автоматически становится возвращаемым значением, отдельное слово return писать не обязательно.

Вывод:

fib(10) = 55
fib(20) = 6765
fib(30) = 832040
fib(40) = 102334155

Числа быстро растут, и если бы нам нужно было посчитать не 4 значения, а миллион (например, для проверки каких-то математических свойств последовательности), разница в скорости между скомпилированным Nim и интерпретируемым Python стала бы заметна невооружённым глазом — Nim пройдёт весь миллион итераций за доли секунды, потому что цикл for здесь превращается в такой же простой машинный цикл, как если бы мы писали это прямо на C.

Задача вторая: решето Эратосфена

Вторая классика — поиск всех простых чисел до какой-то границы. Способ, которым это делают уже больше двух тысяч лет, называется решетом Эратосфена: берём список чисел от 2 до N и последовательно «вычёркиваем» все числа, кратные уже найденным простым.

proc sieve(n: int): seq[int] =
  var isPrime = newSeq[bool](n + 1)
  for i in 0 .. n:
    isPrime[i] = true
  isPrime[0] = false
  if n >= 1:
    isPrime[1] = false

  var p = 2
  while p * p <= n:
    if isPrime[p]:
      var multiple = p * p
      while multiple <= n:
        isPrime[multiple] = false
        multiple += p
    p += 1

  result = @[]
  for i in 2 .. n:
    if isPrime[i]:
      result.add(i)

echo sieve(50)

Смотрим по частям. seq[int] в сигнатуре процедуры — это тип «динамический массив (последовательность) целых чисел», аналог списка list в Python, только с одним важным отличием: все элементы seq[int] обязаны быть числами, никакой смеси типов внутри. newSeq[bool](n + 1) создаёт последовательность из n + 1 логических значений (по умолчанию все false) — здесь мы будем отмечать, простое число или нет. Дальше — обычная логика решета: числа 0 и 1 не простые, и мы вручную это отмечаем, а потом для каждого числа p, которое ещё осталось «не вычеркнутым», отмечаем как составные все его кратные, начиная с p * p (все кратные меньше p * p уже были вычеркнуты на более ранних шагах — это стандартная оптимизация решета). В конце собираем результат: result = @[] создаёт пустую последовательность (символ @ перед квадратными скобками — это способ Nim явно сказать «это seq, а не что-то другое»), а метод .add(i) добавляет в неё найденные простые числа одно за другим.

Вывод:

@[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Заметь: печатается 15 простых чисел до 50, и результат обёрнут в @[...] — это стандартный способ Nim показывать, что перед тобой именно seq, а не что-то ещё. Если бы граница поиска была не 50, а, скажем, 10 миллионов (обычная ситуация в задачах по теории чисел или в олимпиадном программировании), Python-версия этого же алгоритма заметно «просела» бы по времени на вложенных циклах, а Nim продолжил бы работать со скоростью, близкой к C — потому что после компиляции внутренние циклы while здесь не отличаются от таких же циклов в C-программе.

Откуда именно берётся выигрыш

Важно понимать: дело не в «магии» Nim, а в том, что происходит до запуска программы. Компилятор Nim на этапе сборки уже точно знает, что a, b, p, multiple — это целые числа, и генерирует машинный код, который работает с ними напрямую, без обёрток и проверок типов при каждой операции. Python на такое не способен в принципе, потому что в нём переменная в любой момент может «стать» чем угодно — числом, строкой, списком, — и интерпретатор обязан на каждом шаге это перепроверять. Это гибкость, за которую Python и любят, но именно она стоит скорости в задачах с большим числом повторений.

Частые ошибки

Первая ошибка новичков в Nim — писать 0 .. n там, где нужен 0 ..< n, и наоборот. Оператор .. включает оба конца диапазона, а ..< — только левый, правая граница не входит. Перепутать их — значит либо один раз лишний обработать элемент за пределами массива (и получить ошибку выхода за границы), либо, наоборот, пропустить последний нужный элемент. Вторая ошибка — забыть, что seq нужно явно создать через newSeq или @[] перед тем, как обращаться к его элементам по индексу: попытка сразу писать mySeq[5] = true в пустую, необъявленную последовательность приведёт к ошибке в рантайме, потому что физически под эти пять элементов ещё не выделена память. Третья ошибка — путать result с обычной локальной переменной: если в процедуре забыть присвоить result хоть что-то, вернётся значение по умолчанию для этого типа (для int — ноль, для seq — пустая последовательность), и это может пройти незамеченным, потому что синтаксической ошибки здесь нет.

Итоги

Nim компилируется через C в нативный машинный код, поэтому циклы и арифметика работают на скорости, сравнимой с C — без накладных расходов интерпретатора Python.
Компилятор проверяет типы заранее, на этапе сборки, а не на каждом шаге выполнения — это и есть источник выигрыша в скорости для задач с большим числом повторений.
Алгоритмы вроде чисел Фибоначчи и решета Эратосфена выглядят на Nim почти как на Python, но выполняются кардинально быстрее на больших объёмах данных.
Диапазоны .. и ..<, работа с seq через newSeq/@[] и переменная result — три места, где стоит быть внимательным новичку.