Какой самый быстрый способ выполнить целочисленное деление?

Используя схему, мне нужно использовать следующую функцию. (Все аргументы — натуральные числа [0, inf))

(define safe-div
  (lambda (num denom safe)
    (if (zero? denom)
        safe
        (div num denom))))

Однако эта функция вызывается довольно часто и работает недостаточно хорошо (по скорости). Есть ли более эффективный способ реализации желаемого поведения (целочисленное деление num и denom, возврат безопасного значения, если denom равен нулю)?

Примечания: я использую схему Chez, однако она используется в библиотеке, которая импортирует только rnrs, а не полный Chez.


performance integer-division scheme chez-scheme
person Ross Larson    schedule 17.04.2012    source источник
comment
Вы уверены, что ваша проблема здесь? Что делает safe?   -  person robbyphillips    schedule 17.04.2012
comment
safe — натуральное число в диапазоне [0, inf) в соответствии с первой строкой вопроса, поэтому ничего не делает   -  person Ross Larson    schedule 17.04.2012
comment
Написали ли вы несколько тестов для проверки скорости этой подпрограммы и ее отличия от простого целочисленного деления? Есть много вещей, которые могут иметь значение, но вам определенно нужно разобраться с производительностью перед настройкой.   -  person John Clements    schedule 17.04.2012

Ответы (1)


arrow_upward
7
arrow_downward

Для максимальной производительности вам нужно максимально приблизиться к кремнию. Добавление подобных проверок безопасности не поможет, если только они не будут своевременно скомпилированы в сверхэффективный машинный код системой схем.

Я вижу два варианта. Один из них — создать собственную (т. е. внешнюю) реализацию на C (или ассемблере) и вызвать это. Это может быть несовместимо с упаковкой его в виде лямбды, но опять же, динамическая природа лямбда приводит к эффективности обозначений, но не обязательно к эффективности времени выполнения. (За исключением указателей на функции, есть причина, по которой лямбда-выражения отсутствуют в C, несмотря на то, что они на много лет старше.) Если вы пойдете по этому пути, возможно, лучше сделать шаг назад и посмотреть, будет ли более крупная обработка безопасного div часть надо брать родную. Нет смысла ускорять деление в центре цикла, если все вокруг него все еще медленно.

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

Наконец, в зависимости от того, на что вы делите, может быть быстрее умножить на обратное, чем выполнить фактическое деление. Это требует быстрого обратного вычисления или пересмотра более ранних вычислений, чтобы получить обратное значение напрямую. Поскольку вы имеете дело с целыми числами, обратная величина будет храниться в фиксированной точке, что по существу составляет 2 ^ 32 * 1/деном. Умножьте это на число и сдвиньте вправо на 32 бита, чтобы получить частное. Это приводит к выигрышу, потому что в наши дни все больше процессоров имеют инструкции умножения за один цикл, но деление выполняется в цикле на чипе, что намного медленнее. Это может быть излишним для ваших нужд, но может быть полезным в какой-то момент.

person Randall Cook    schedule 17.04.2012