Деление MPFR быстрее, чем собственное целочисленное деление?

Я всегда предполагал, что целочисленное деление было быстрее, чем деление с плавающей запятой, но я провел несколько тестов, которые, казалось, доказывали обратное.

import gmpy2, time, math

digits = 100000

scale = 10**digits  # Decimal precision
gmpy2.get_context().precision = int(math.log2(10) * digits)  # Binary precision

def start_timer():
    global start_time  
    start_time = time.time()

def print_timer():
    print("%s s" % (time.time() - start_time))

start_timer()
for i in range(1000):
    x = scale // 3
print_timer()

start_timer()
for i in range(1000):
    x = gmpy2.mpfr(1) / 3
print_timer()

start_timer()
for i in range(1000):
    x = gmpy2.mpfr(1) / gmpy2.mpfr(3)
print_timer()

Целочисленное деление заняло 0,17 секунды, деление mpfr заняло 0,06 секунды, а деление между двумя числами с плавающей запятой - 15,56 секунды.

Мои вопросы:

  1. Я правильно настраиваю этот тест?
  2. Действительно ли деление mpfr более оптимизировано, чем нативное?
  3. Разве деление с использованием числа с плавающей запятой и целого числа намного быстрее, чем деление с использованием двух чисел с плавающей запятой?
Источник

3 ответа

Решение

Я использую IPython для составления коротких примеров, а затем попытаюсь объяснить результаты.

from gmpy2 import mpfr, get_context
get_context().precision=1000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000000 loops, best of 3: 669 ns per loop
%timeit a/3
1000000 loops, best of 3: 464 ns per loop

get_context().precision=10000
a=mpfr(1);b=mpfr(3)

%timeit a/b
100000 loops, best of 3: 12.9 µs per loop
%timeit a/3
1000000 loops, best of 3: 1.33 µs per loop

get_context().precision=100000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000 loops, best of 3: 505 µs per loop
%timeit a/3
100000 loops, best of 3: 8.13 µs per loop

Обратите внимание, что с увеличением точности время работы a/b увеличивается быстрее, чем a/3, При расчете a/bMPFR использует полную точность обоих значений, а время выполнения (приблизительно) O(n * ln(n)). При расчете a/3MPFR использует короткое, но точное представление 3, а время выполнения (примерно) O(n). Это объясняет почему a/b медленнее, чем a/3 для высокой точности. (п длина a в битах.)

Когда Python вычисляет scale//3, он использует тот факт, что 3 будет вписываться в один digit и время работы является линейным по длине scale, Это фактически тот же расчет, что и a/3 но поскольку базовая библиотека GMP работает быстрее, чем Python, a/3 вычисляется быстрее чем scale//3,

Вот краткий пример различия в производительности между Python и GMP.

from gmpy2 import mpz
scale = 10**100000

%timeit scale//3
10000 loops, best of 3: 162 µs per loop

scale = mpz(scale)

%timeit scale//3
100000 loops, best of 3: 19 µs per loop

Вы измеряли производительность между n от n разделение и n от k разделение при сравнении a/b а также a/3, (n длина a в битах, и k намного, намного меньше, чем n.) Когда вы сравнили scale//3 и `a/3', вы сравнивали простую, прямую реализацию деления с высокооптимизированной реализацией.

Примечание по реализации: В текущей ветке нестабильной разработки, a/3 звонки mpfr_div_ui непосредственно. Это исключает создание временного объекта MPFR. Это улучшает производительность, как показано ниже.

from gmpy2 import mpfr, get_context
get_context().precision=1000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000000 loops, best of 3: 593 ns per loop
%timeit a/3
1000000 loops, best of 3: 231 ns per loop

get_context().precision=10000
a=mpfr(1); b=mpfr(3)

%timeit a/b
100000 loops, best of 3: 12.7 µs per loop
%timeit a/3
1000000 loops, best of 3: 927 ns per loop

get_context().precision=100000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000 loops, best of 3: 505 µs per loop
%timeit a/3
100000 loops, best of 3: 6.77 µs per loop
Источник

Замечание о реализации GNU MPFR (я разработчик MPFR, хотя я не особо работал над делением): выбор лучшего алгоритма для умножения и деления довольно сложен, потому что существуют различные параметры (точность входы и выходы, и могут ли входы быть представлены с меньшей точностью из-за конечных нулей, в частности), и некоторые случаи могут быть более сложными для округления, чем другие. Более того, алгоритмы, таким образом, время может изменяться от одного выпуска к другому, улучшая некоторые случаи, но в то же время делая другие случаи более медленными. Еще недавно (два месяца назад) у нас была дискуссия о том, нужно ли делать специальное распознавание постоянных степеней двойки для целых чисел в mpfr_mul_ui и mpfr_div_ui.

Если вы действительно хотите сравнить целочисленное деление с MPFR FP, вам следует сравнить с целочисленным делением GMP. MPFR основан на подразделении GMP, но не наивно. Лучший способ узнать, что делает MPFR, - это использовать протоколирование MPFR (для этого может потребоваться перестройка с --enable-logging) с соответствующими переменными среды. Обратите внимание, что когда ведение журнала включено в сборке MPFR, даже если ведение журнала не используется, MPFR может быть немного медленнее.

Источник

Деление с плавающей точкой обычно быстрее, чем целочисленное деление на процессоре. Можно предположить, что это связано с тем, что FPU более оптимизирован для этой операции, или что представление с плавающей запятой облегчает деление. Но какими бы ни были причины, это не изменит факт. В конце концов, единственный способ получить конкретные ответы на ваши вторые и третьи вопросы - это проверить их. И да, ваши тесты выглядят хорошо для меня.

Если бы мне пришлось рисковать, я думаю, что случай, когда вы делите число MPFR на целое число, быстрее, потому что GMP может использовать свою ограниченную точность в своих интересах при вычислении деления.

Источник
Другие вопросы по тегам