Быстрый расчёт остатка от деления

В процессе работы над статьёй про FrozenDictionary заметил немало интересных деталей, о которых хочется рассказать. Начнём с простого, поэтому сегодня о быстром алгоритме расчёта остатка от деления.

Как известно, индекс бакета в словаре рассчитывается как остаток от деления hashCode на bucketsCount. В C# и многих других языках программирования для этого используется оператор %:

var bucketNum = hashCode % bucketsCount;

В общем случае, эта операция включает в себя деление, которое выполняется медленнее, чем другие арифметические операции. Поэтому была придумана следующая формула:

uint FastModLemier(
  uint hashcode, 
  ulong multiplier, 
  uint bucketsNum) => 
  (uint)((((UInt128)(hashcode 
    * multiplier))
      * bucketsNum) >> 64);

Идея этого подхода в том, что если количество бакетов известно заранее, то можно вычислить значение multiplier по формуле ulong.MaxValue / bucketsNum + 1. Это позволяет заменить деление на умножение и битовые сдвиги. Если интересны подробности и математическое обоснование формулы, то можете ознакомиться со статьёй Дэниела Лемира, разработчика данного метода. Для общего понимания достаточно прочитать главы 1 и 3.2.

В FrozenDictionary и Dictionary используется другой вариант формулы, который, по словам разработчиков Microsoft немного быстрее, что подтверждается результатами бенчмарка (рисунок 1):

uint FastModDotNet(
  uint hashcode, 
  ulong multiplier, 
  uint bucketsNum) => 
    (uint)(((((multiplier
      * hashcode) >> 32) 
      + 1) * bucketsNum) >> 32);

Кроме того, JIT-компилятор способен оптимизировать код и заменить деление на несколько операций умножения и битовый сдвиг, если значение bucketsCount известно на этапе компиляции. В результате ASM-код для DefaultModConst будет идентичен коду FastModDotNet (рисунок 2).

Код бенчмарка и результаты тут.