6
\$\begingroup\$

I have a use case where improvements to the speed of calculating modulo for 64 bit integer dividends makes a significant difference in overall processing time.

The divisor isn't known statically - it can only be determined at runtime. Once it is known the same divisor is used for a period of time. Divisors are also biased towards the lower range of numbers.

Modulo of divisors of the form \$2^n\$ can be calculated with a simple bitwise AND: x mod 2^n = x AND (2^n - 1).

Modulo of divisors that are Mersenne primes, or any number of the form \$2^n-1\$, can be calculated with a similar technique that splits and accumulates the modulus. Some info on that.

Modulo of divisors that can be factored into numbers of the form \$2^n\$ or \$2^n-1\$ can also be calculated similarly with the addition of a lookup table, as long as none of the factors are repeated (e.g., 9, 25, 36 cannot be calculated this way).

Below I have code that allows one to retrieve a function representing the modulo operator for a specific divisor. Benchmarking has shown these handily outperform the built-in % operator (in my specific environment and use case - specifically, the divisor cannot be known until runtime and may change periodically).

What I am wondering, is if anyone can spot any divisors under 128 that I missed, that could be implemented faster than the % operator. In particular, this blog used a different technique for calculating the modulo of 5 by first getting the modulo of 15 and then subtracting 5 as necessary. I did not see any other divisors I could apply this technique to, and I may have missed some other factorizations, or there may be other techniques for calculating modulo more quickly that I am not aware of.

using System;
using System.Runtime.CompilerServices;

namespace OptimizedModulo
{
    static public class Modulo
    {
        // called infrequently, returned function is re-used many times
        static public Func<ulong, ulong> Optimized(ulong divisor)
        {
            if ((divisor & (divisor - 1)) == 0)
                return n => Modulo.Implementations.Long.ShiftAnd(n, divisor);

            switch (divisor)
            {
                case 0: throw new DivideByZeroException();
                case 1: return Modulo.Implementations.Long.One;
                case 3: return Modulo.Implementations.Long.Mersenne3;
                case 5: return Modulo.Implementations.Long.Mersenne5;
                case 6: return Modulo.Implementations.Long.Mersenne6;
                case 7: return Modulo.Implementations.Long.Mersenne7;
                case 10: return Modulo.Implementations.Long.Mersenne10;
                case 12: return Modulo.Implementations.Long.Mersenne12;
                case 14: return Modulo.Implementations.Long.Mersenne14;
                case 15: return Modulo.Implementations.Long.Mersenne15;
                case 20: return Modulo.Implementations.Long.Mersenne20;
                case 21: return Modulo.Implementations.Long.Mersenne21;
                case 24: return Modulo.Implementations.Long.Mersenne24;
                case 28: return Modulo.Implementations.Long.Mersenne28;
                case 30: return Modulo.Implementations.Long.Mersenne30;
                case 31: return Modulo.Implementations.Long.Mersenne31;
                case 35: return Modulo.Implementations.Long.Mersenne35;
                case 40: return Modulo.Implementations.Long.Mersenne40;
                case 42: return Modulo.Implementations.Long.Mersenne42;
                case 48: return Modulo.Implementations.Long.Mersenne48;
                case 56: return Modulo.Implementations.Long.Mersenne56;
                case 60: return Modulo.Implementations.Long.Mersenne60;
                case 62: return Modulo.Implementations.Long.Mersenne62;
                case 63: return Modulo.Implementations.Long.Mersenne63;
                case 70: return Modulo.Implementations.Long.Mersenne70;
                case 80: return Modulo.Implementations.Long.Mersenne80;
                case 84: return Modulo.Implementations.Long.Mersenne84;
                case 93: return Modulo.Implementations.Long.Mersenne93;
                case 96: return Modulo.Implementations.Long.Mersenne96;
                case 105: return Modulo.Implementations.Long.Mersenne105;
                case 112: return Modulo.Implementations.Long.Mersenne112;
                case 120: return Modulo.Implementations.Long.Mersenne120;
                case 124: return Modulo.Implementations.Long.Mersenne124;
                case 126: return Modulo.Implementations.Long.Mersenne126;
                case 127: return Modulo.Implementations.Long.Mersenne127;
                case 255: return Modulo.Implementations.Long.Mersenne255;
                case 511: return Modulo.Implementations.Long.Mersenne511;
                case 1023: return Modulo.Implementations.Long.Mersenne1023;
                default: return n => Modulo.Implementations.Long.ModuloOperator(n, divisor);
            }
        }

        static public class Implementations
        {
            static public class Long
            {
                static public ulong One(ulong dividend) => 0;
                static public ulong ModuloOperator(ulong dividend, ulong divisor) => (dividend % divisor);
                static public ulong ShiftAnd(ulong dividend, ulong divisor) => (dividend & (divisor - 1));

                static public ulong Mersenne3(ulong dividend)
                {
                    dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    dividend = (dividend >> 16) + (dividend & 0xFFFF);
                    dividend = (dividend >> 8) + (dividend & 0xFF);
                    dividend = (dividend >> 4) + (dividend & 0xF);
                    dividend = (dividend >> 2) + (dividend & 0x3);
                    dividend = (dividend >> 2) + (dividend & 0x3);
                    dividend = (dividend >> 2) + (dividend & 0x3);
                    if (dividend > 2) dividend = dividend - 3;
                    return dividend;
                }

                static public ulong Mersenne5(ulong dividend)
                {
                    dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    dividend = (dividend >> 16) + (dividend & 0xFFFF);
                    dividend = (dividend >> 8) + (dividend & 0xFF);
                    dividend = (dividend >> 4) + (dividend & 0xF);
                    dividend = (dividend >> 4) + (dividend & 0xF);
                    if (dividend > 14) dividend = dividend - 15; // mod 15
                    if (dividend > 10) dividend = dividend - 10;
                    if (dividend > 4) dividend = dividend - 5;
                    return dividend;
                }


                static private readonly ulong[] _mersenne6Table = { 0, 3, 4, 1, 2, 5 };
                static public ulong Mersenne6(ulong dividend)
                {
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne6Table[(mod3 << 1) | (dividend & 0b1)];
                }


                static public ulong Mersenne7(ulong dividend)
                {
                    dividend = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    dividend = (dividend >> 24) + (dividend & 0xFFFFFF);
                    dividend = (dividend >> 12) + (dividend & 0xFFF);
                    dividend = (dividend >> 6) + (dividend & 0x3F);
                    dividend = (dividend >> 3) + (dividend & 0x7);
                    dividend = (dividend >> 3) + (dividend & 0x7);
                    if (dividend > 6) dividend = dividend - 7;
                    return dividend;
                }


                static private readonly ulong[] _mersenne10Table = { 0, 5, 6, 1, 2, 7, 8, 3, 4, 9 };
                static public ulong Mersenne10(ulong dividend)
                {
                    var mod5 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod5 = (mod5 >> 16) + (mod5 & 0xFFFF);
                    mod5 = (mod5 >> 8) + (mod5 & 0xFF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    if (mod5 > 14) mod5 = mod5 - 15;
                    if (mod5 > 9) mod5 = mod5 - 10;
                    if (mod5 > 4) mod5 = mod5 - 5;
                    return _mersenne10Table[(mod5 << 1) | (dividend & 0b1)];
                }


                static private readonly ulong[] _mersenne12Table = { 0, 9, 6, 3, 4, 1, 10, 7, 8, 5, 2, 11 };
                static public ulong Mersenne12(ulong dividend)
                {
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne12Table[(mod3 << 2) | (dividend & 0b11)];
                }


                static private readonly ulong[] _mersenne14Table = { 0, 7, 8, 1, 2, 9, 10, 3, 4, 11, 12, 5, 6, 13 };
                static public ulong Mersenne14(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    return _mersenne14Table[(mod7 << 1) | (dividend & 0b1)];
                }


                static public ulong Mersenne15(ulong dividend)
                {
                    dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    dividend = (dividend >> 16) + (dividend & 0xFFFF);
                    dividend = (dividend >> 8) + (dividend & 0xFF);
                    dividend = (dividend >> 4) + (dividend & 0xF);
                    dividend = (dividend >> 4) + (dividend & 0xF);
                    if (dividend > 14) dividend = dividend - 15;
                    return dividend;
                }


                static private readonly ulong[] _mersenne20Table = { 0, 5, 10, 15, 16, 1, 6, 11, 12, 17, 2, 7, 8, 13, 18, 3, 4, 9, 14, 19 };
                static public ulong Mersenne20(ulong dividend)
                {
                    var mod5 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod5 = (mod5 >> 16) + (mod5 & 0xFFFF);
                    mod5 = (mod5 >> 8) + (mod5 & 0xFF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    if (mod5 > 14) mod5 = mod5 - 15;
                    if (mod5 > 9) mod5 = mod5 - 10;
                    if (mod5 > 4) mod5 = mod5 - 5;
                    return _mersenne20Table[(mod5 << 2) | (dividend & 0b11)];
                }


                static private readonly ulong[] _mersenne21Table = { 0, 15, 9, 3, 18, 12, 6, 0, 7, 1, 16, 10, 4, 19, 13, 0, 14, 8, 2, 17, 11, 5, 20 };
                static public ulong Mersenne21(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne21Table[(mod3 << 3) | mod7];
                }


                static private readonly ulong[] _mersenne24Table = { 0, 9, 18, 3, 12, 21, 6, 15, 16, 1, 10, 19, 4, 13, 22, 7, 8, 17, 2, 11, 20, 5, 14, 23 };
                static public ulong Mersenne24(ulong dividend)
                {
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne24Table[(mod3 << 3) | (dividend & 0b111)];
                }


                static private readonly ulong[] _mersenne28Table = { 0, 21, 14, 7, 8, 1, 22, 15, 16, 9, 2, 23, 24, 17, 10, 3, 4, 25, 18, 11, 12, 5, 26, 19, 20, 13, 6, 27 };
                static public ulong Mersenne28(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    return _mersenne28Table[(mod7 << 2) | (dividend & 0b11)];
                }


                static private readonly ulong[] _mersenne30Table = { 0, 15, 16, 1, 2, 17, 18, 3, 4, 19, 20, 5, 6, 21, 22, 7, 8, 23, 24, 9, 10, 25, 26, 11, 12, 27, 28, 13, 14, 29 };
                static public ulong Mersenne30(ulong dividend)
                {
                    var mod15 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod15 = (mod15 >> 16) + (mod15 & 0xFFFF);
                    mod15 = (mod15 >> 8) + (mod15 & 0xFF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    if (mod15 > 14) mod15 = mod15 - 15;
                    return _mersenne30Table[(mod15 << 1) | (dividend & 0b1)];
                }


                static public ulong Mersenne31(ulong dividend)
                {
                    dividend = (dividend >> 40) + (dividend & 0xFFFFFFFFFF);
                    dividend = (dividend >> 20) + (dividend & 0xFFFFF);
                    dividend = (dividend >> 10) + (dividend & 0x3FF);
                    dividend = (dividend >> 5) + (dividend & 0x1F);
                    dividend = (dividend >> 5) + (dividend & 0x1F);
                    if (dividend > 30) dividend = dividend - 31;
                    return dividend;
                }


                static private readonly ulong[] _mersenne35Table = { 0, 15, 30, 10, 25, 5, 20, 0, 21, 1, 16, 31, 11, 26, 6, 0, 7, 22, 2, 17, 32, 12, 27, 0, 28, 8, 23, 3, 18, 33, 13, 0, 14, 29, 9, 24, 4, 19, 34 };
                static public ulong Mersenne35(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    var mod5 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod5 = (mod5 >> 16) + (mod5 & 0xFFFF);
                    mod5 = (mod5 >> 8) + (mod5 & 0xFF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    if (mod5 > 14) mod5 = mod5 - 15;
                    if (mod5 > 9) mod5 = mod5 - 10;
                    if (mod5 > 4) mod5 = mod5 - 5;
                    return _mersenne35Table[(mod5 << 3) | mod7];
                }


                static private readonly ulong[] _mersenne40Table = { 0, 25, 10, 35, 20, 5, 30, 15, 16, 1, 26, 11, 36, 21, 6, 31, 32, 17, 2, 27, 12, 37, 22, 7, 8, 33, 18, 3, 28, 13, 38, 23, 24, 9, 34, 19, 4, 29, 14, 39 };
                static public ulong Mersenne40(ulong dividend)
                {
                    var mod5 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod5 = (mod5 >> 16) + (mod5 & 0xFFFF);
                    mod5 = (mod5 >> 8) + (mod5 & 0xFF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    if (mod5 > 14) mod5 = mod5 - 15;
                    if (mod5 > 9) mod5 = mod5 - 10;
                    if (mod5 > 4) mod5 = mod5 - 5;
                    return _mersenne40Table[(mod5 << 3) | (dividend & 0b111)];
                }


                static private readonly ulong[] _mersenne42Table = { 0, 21, 28, 7, 14, 35, 0, 0, 36, 15, 22, 1, 8, 29, 0, 0, 30, 9, 16, 37, 2, 23, 0, 0, 24, 3, 10, 31, 38, 17, 0, 0, 18, 39, 4, 25, 32, 11, 0, 0, 12, 33, 40, 19, 26, 5, 0, 0, 6, 27, 34, 13, 20, 41 };
                static public ulong Mersenne42(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne42Table[(mod7 << 3) | (mod3 << 1) | (dividend & 0b1)];
                }


                static private readonly ulong[] _mersenne48Table = { 0, 33, 18, 3, 36, 21, 6, 39, 24, 9, 42, 27, 12, 45, 30, 15, 16, 1, 34, 19, 4, 37, 22, 7, 40, 25, 10, 43, 28, 13, 46, 31, 32, 17, 2, 35, 20, 5, 38, 23, 8, 41, 26, 11, 44, 29, 14, 47 };
                static public ulong Mersenne48(ulong dividend)
                {
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne48Table[(mod3 << 4) | (dividend & 0b1111)];
                }


                static private readonly ulong[] _mersenne56Table = { 0, 49, 42, 35, 28, 21, 14, 7, 8, 1, 50, 43, 36, 29, 22, 15, 16, 9, 2, 51, 44, 37, 30, 23, 24, 17, 10, 3, 52, 45, 38, 31, 32, 25, 18, 11, 4, 53, 46, 39, 40, 33, 26, 19, 12, 5, 54, 47, 48, 41, 34, 27, 20, 13, 6, 55 };
                static public ulong Mersenne56(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    return _mersenne56Table[(mod7 << 3) | (dividend & 0b111)];
                }


                static private readonly ulong[] _mersenne60Table = { 0, 45, 30, 15, 16, 1, 46, 31, 32, 17, 2, 47, 48, 33, 18, 3, 4, 49, 34, 19, 20, 5, 50, 35, 36, 21, 6, 51, 52, 37, 22, 7, 8, 53, 38, 23, 24, 9, 54, 39, 40, 25, 10, 55, 56, 41, 26, 11, 12, 57, 42, 27, 28, 13, 58, 43, 44, 29, 14, 59 };
                static public ulong Mersenne60(ulong dividend)
                {
                    var mod15 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod15 = (mod15 >> 16) + (mod15 & 0xFFFF);
                    mod15 = (mod15 >> 8) + (mod15 & 0xFF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    if (mod15 > 14) mod15 = mod15 - 15;
                    return _mersenne60Table[(mod15 << 2) | (dividend & 0b11)];
                }


                static private readonly ulong[] _mersenne62Table = { 0, 31, 32, 1, 2, 33, 34, 3, 4, 35, 36, 5, 6, 37, 38, 7, 8, 39, 40, 9, 10, 41, 42, 11, 12, 43, 44, 13, 14, 45, 46, 15, 16, 47, 48, 17, 18, 49, 50, 19, 20, 51, 52, 21, 22, 53, 54, 23, 24, 55, 56, 25, 26, 57, 58, 27, 28, 59, 60, 29, 30, 61 };
                static public ulong Mersenne62(ulong dividend)
                {
                    var mod31 = (dividend >> 40) + (dividend & 0xFFFFFFFFFF);
                    mod31 = (mod31 >> 20) + (mod31 & 0xFFFFF);
                    mod31 = (mod31 >> 10) + (mod31 & 0x3FF);
                    mod31 = (mod31 >> 5) + (mod31 & 0x1F);
                    mod31 = (mod31 >> 5) + (mod31 & 0x1F);
                    if (mod31 > 30) mod31 = mod31 - 31;
                    return _mersenne62Table[(mod31 << 1) | (dividend & 0b1)];
                }


                static public ulong Mersenne63(ulong dividend)
                {
                    dividend = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    dividend = (dividend >> 24) + (dividend & 0xFFFFFF);
                    dividend = (dividend >> 12) + (dividend & 0xFFF);
                    dividend = (dividend >> 6) + (dividend & 0x3F);
                    dividend = (dividend >> 6) + (dividend & 0x3F);
                    if (dividend > 62) dividend = dividend - 63;
                    return dividend;
                }


                static private readonly ulong[] _mersenne70Table = { 0, 35, 50, 15, 30, 65, 10, 45, 60, 25, 40, 5, 20, 55, 0, 0, 56, 21, 36, 1, 16, 51, 66, 31, 46, 11, 26, 61, 6, 41, 0, 0, 42, 7, 22, 57, 2, 37, 52, 17, 32, 67, 12, 47, 62, 27, 0, 0, 28, 63, 8, 43, 58, 23, 38, 3, 18, 53, 68, 33, 48, 13, 0, 0, 14, 49, 64, 29, 44, 9, 24, 59, 4, 39, 54, 19, 34, 69 };
                static public ulong Mersenne70(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    var mod5 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod5 = (mod5 >> 16) + (mod5 & 0xFFFF);
                    mod5 = (mod5 >> 8) + (mod5 & 0xFF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    if (mod5 > 14) mod5 = mod5 - 15;
                    if (mod5 > 9) mod5 = mod5 - 10;
                    if (mod5 > 4) mod5 = mod5 - 5;
                    return _mersenne70Table[(mod5 << 4) | (mod7 << 1) | (dividend & 0b1)];
                }


                static private readonly ulong[] _mersenne80Table = { 0, 65, 50, 35, 20, 5, 70, 55, 40, 25, 10, 75, 60, 45, 30, 15, 16, 1, 66, 51, 36, 21, 6, 71, 56, 41, 26, 11, 76, 61, 46, 31, 32, 17, 2, 67, 52, 37, 22, 7, 72, 57, 42, 27, 12, 77, 62, 47, 48, 33, 18, 3, 68, 53, 38, 23, 8, 73, 58, 43, 28, 13, 78, 63, 64, 49, 34, 19, 4, 69, 54, 39, 24, 9, 74, 59, 44, 29, 14, 79 };
                static public ulong Mersenne80(ulong dividend)
                {
                    var mod5 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod5 = (mod5 >> 16) + (mod5 & 0xFFFF);
                    mod5 = (mod5 >> 8) + (mod5 & 0xFF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    mod5 = (mod5 >> 4) + (mod5 & 0xF);
                    if (mod5 > 14) mod5 = mod5 - 15;
                    if (mod5 > 9) mod5 = mod5 - 10;
                    if (mod5 > 4) mod5 = mod5 - 5;
                    return _mersenne80Table[(mod5 << 4) | (dividend & 0b1111)];
                }


                static private readonly ulong[] _mersenne84Table = { 0, 21, 42, 63, 28, 49, 70, 7, 56, 77, 14, 35, 0, 0, 0, 0, 36, 57, 78, 15, 64, 1, 22, 43, 8, 29, 50, 71, 0, 0, 0, 0, 72, 9, 30, 51, 16, 37, 58, 79, 44, 65, 2, 23, 0, 0, 0, 0, 24, 45, 66, 3, 52, 73, 10, 31, 80, 17, 38, 59, 0, 0, 0, 0, 60, 81, 18, 39, 4, 25, 46, 67, 32, 53, 74, 11, 0, 0, 0, 0, 12, 33, 54, 75, 40, 61, 82, 19, 68, 5, 26, 47, 0, 0, 0, 0, 48, 69, 6, 27, 76, 13, 34, 55, 20, 41, 62, 83 };
                static public ulong Mersenne84(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne84Table[(mod7 << 4) | (mod3 << 2) | (dividend & 0b11)];
                }


                static private readonly ulong[] _mersenne93Table = { 0, 31, 62, 0, 63, 1, 32, 0, 33, 64, 2, 0, 3, 34, 65, 0, 66, 4, 35, 0, 36, 67, 5, 0, 6, 37, 68, 0, 69, 7, 38, 0, 39, 70, 8, 0, 9, 40, 71, 0, 72, 10, 41, 0, 42, 73, 11, 0, 12, 43, 74, 0, 75, 13, 44, 0, 45, 76, 14, 0, 15, 46, 77, 0, 78, 16, 47, 0, 48, 79, 17, 0, 18, 49, 80, 0, 81, 19, 50, 0, 51, 82, 20, 0, 21, 52, 83, 0, 84, 22, 53, 0, 54, 85, 23, 0, 24, 55, 86, 0, 87, 25, 56, 0, 57, 88, 26, 0, 27, 58, 89, 0, 90, 28, 59, 0, 60, 91, 29, 0, 30, 61, 92 };
                static public ulong Mersenne93(ulong dividend)
                {
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    var mod31 = (dividend >> 40) + (dividend & 0xFFFFFFFFFF);
                    mod31 = (mod31 >> 20) + (mod31 & 0xFFFFF);
                    mod31 = (mod31 >> 10) + (mod31 & 0x3FF);
                    mod31 = (mod31 >> 5) + (mod31 & 0x1F);
                    mod31 = (mod31 >> 5) + (mod31 & 0x1F);
                    if (mod31 > 30) mod31 = mod31 - 31;
                    return _mersenne93Table[(mod31 << 2) | mod3];
                }


                static private readonly ulong[] _mersenne96Table = { 0, 33, 66, 3, 36, 69, 6, 39, 72, 9, 42, 75, 12, 45, 78, 15, 48, 81, 18, 51, 84, 21, 54, 87, 24, 57, 90, 27, 60, 93, 30, 63, 64, 1, 34, 67, 4, 37, 70, 7, 40, 73, 10, 43, 76, 13, 46, 79, 16, 49, 82, 19, 52, 85, 22, 55, 88, 25, 58, 91, 28, 61, 94, 31, 32, 65, 2, 35, 68, 5, 38, 71, 8, 41, 74, 11, 44, 77, 14, 47, 80, 17, 50, 83, 20, 53, 86, 23, 56, 89, 26, 59, 92, 29, 62, 95 };
                static public ulong Mersenne96(ulong dividend)
                {
                    var mod3 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod3 = (mod3 >> 16) + (mod3 & 0xFFFF);
                    mod3 = (mod3 >> 8) + (mod3 & 0xFF);
                    mod3 = (mod3 >> 4) + (mod3 & 0xF);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    mod3 = (mod3 >> 2) + (mod3 & 0x3);
                    if (mod3 > 2) mod3 = mod3 - 3;
                    return _mersenne96Table[(mod3 << 5) | (dividend & 0b11111)];
                }


                static private readonly ulong[] _mersenne105Table = { 0, 15, 30, 45, 60, 75, 90, 0, 91, 1, 16, 31, 46, 61, 76, 0, 77, 92, 2, 17, 32, 47, 62, 0, 63, 78, 93, 3, 18, 33, 48, 0, 49, 64, 79, 94, 4, 19, 34, 0, 35, 50, 65, 80, 95, 5, 20, 0, 21, 36, 51, 66, 81, 96, 6, 0, 7, 22, 37, 52, 67, 82, 97, 0, 98, 8, 23, 38, 53, 68, 83, 0, 84, 99, 9, 24, 39, 54, 69, 0, 70, 85, 100, 10, 25, 40, 55, 0, 56, 71, 86, 101, 11, 26, 41, 0, 42, 57, 72, 87, 102, 12, 27, 0, 28, 43, 58, 73, 88, 103, 13, 0, 14, 29, 44, 59, 74, 89, 104 };
                static public ulong Mersenne105(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    var mod15 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod15 = (mod15 >> 16) + (mod15 & 0xFFFF);
                    mod15 = (mod15 >> 8) + (mod15 & 0xFF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    if (mod15 > 14) mod15 = mod15 - 15;
                    return _mersenne105Table[(mod15 << 3) | mod7];
                }


                static private readonly ulong[] _mersenne112Table = { 0, 49, 98, 35, 84, 21, 70, 7, 56, 105, 42, 91, 28, 77, 14, 63, 64, 1, 50, 99, 36, 85, 22, 71, 8, 57, 106, 43, 92, 29, 78, 15, 16, 65, 2, 51, 100, 37, 86, 23, 72, 9, 58, 107, 44, 93, 30, 79, 80, 17, 66, 3, 52, 101, 38, 87, 24, 73, 10, 59, 108, 45, 94, 31, 32, 81, 18, 67, 4, 53, 102, 39, 88, 25, 74, 11, 60, 109, 46, 95, 96, 33, 82, 19, 68, 5, 54, 103, 40, 89, 26, 75, 12, 61, 110, 47, 48, 97, 34, 83, 20, 69, 6, 55, 104, 41, 90, 27, 76, 13, 62, 111 };
                static public ulong Mersenne112(ulong dividend)
                {
                    var mod7 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod7 = (mod7 >> 24) + (mod7 & 0xFFFFFF);
                    mod7 = (mod7 >> 12) + (mod7 & 0xFFF);
                    mod7 = (mod7 >> 6) + (mod7 & 0x3F);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    mod7 = (mod7 >> 3) + (mod7 & 0x7);
                    if (mod7 > 6) mod7 = mod7 - 7;
                    return _mersenne112Table[(mod7 << 4) | (dividend & 0b1111)];
                }


                static private readonly ulong[] _mersenne120Table = { 0, 105, 90, 75, 60, 45, 30, 15, 16, 1, 106, 91, 76, 61, 46, 31, 32, 17, 2, 107, 92, 77, 62, 47, 48, 33, 18, 3, 108, 93, 78, 63, 64, 49, 34, 19, 4, 109, 94, 79, 80, 65, 50, 35, 20, 5, 110, 95, 96, 81, 66, 51, 36, 21, 6, 111, 112, 97, 82, 67, 52, 37, 22, 7, 8, 113, 98, 83, 68, 53, 38, 23, 24, 9, 114, 99, 84, 69, 54, 39, 40, 25, 10, 115, 100, 85, 70, 55, 56, 41, 26, 11, 116, 101, 86, 71, 72, 57, 42, 27, 12, 117, 102, 87, 88, 73, 58, 43, 28, 13, 118, 103, 104, 89, 74, 59, 44, 29, 14, 119 };
                static public ulong Mersenne120(ulong dividend)
                {
                    var mod15 = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    mod15 = (mod15 >> 16) + (mod15 & 0xFFFF);
                    mod15 = (mod15 >> 8) + (mod15 & 0xFF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    mod15 = (mod15 >> 4) + (mod15 & 0xF);
                    if (mod15 > 14) mod15 = mod15 - 15;
                    return _mersenne120Table[(mod15 << 3) | (dividend & 0b111)];
                }


                static private readonly ulong[] _mersenne124Table = { 0, 93, 62, 31, 32, 1, 94, 63, 64, 33, 2, 95, 96, 65, 34, 3, 4, 97, 66, 35, 36, 5, 98, 67, 68, 37, 6, 99, 100, 69, 38, 7, 8, 101, 70, 39, 40, 9, 102, 71, 72, 41, 10, 103, 104, 73, 42, 11, 12, 105, 74, 43, 44, 13, 106, 75, 76, 45, 14, 107, 108, 77, 46, 15, 16, 109, 78, 47, 48, 17, 110, 79, 80, 49, 18, 111, 112, 81, 50, 19, 20, 113, 82, 51, 52, 21, 114, 83, 84, 53, 22, 115, 116, 85, 54, 23, 24, 117, 86, 55, 56, 25, 118, 87, 88, 57, 26, 119, 120, 89, 58, 27, 28, 121, 90, 59, 60, 29, 122, 91, 92, 61, 30, 123 };
                static public ulong Mersenne124(ulong dividend)
                {
                    var mod31 = (dividend >> 40) + (dividend & 0xFFFFFFFFFF);
                    mod31 = (mod31 >> 20) + (mod31 & 0xFFFFF);
                    mod31 = (mod31 >> 10) + (mod31 & 0x3FF);
                    mod31 = (mod31 >> 5) + (mod31 & 0x1F);
                    mod31 = (mod31 >> 5) + (mod31 & 0x1F);
                    if (mod31 > 30) mod31 = mod31 - 31;
                    return _mersenne124Table[(mod31 << 2) | (dividend & 0b11)];
                }


                static private readonly ulong[] _mersenne126Table = { 0, 63, 64, 1, 2, 65, 66, 3, 4, 67, 68, 5, 6, 69, 70, 7, 8, 71, 72, 9, 10, 73, 74, 11, 12, 75, 76, 13, 14, 77, 78, 15, 16, 79, 80, 17, 18, 81, 82, 19, 20, 83, 84, 21, 22, 85, 86, 23, 24, 87, 88, 25, 26, 89, 90, 27, 28, 91, 92, 29, 30, 93, 94, 31, 32, 95, 96, 33, 34, 97, 98, 35, 36, 99, 100, 37, 38, 101, 102, 39, 40, 103, 104, 41, 42, 105, 106, 43, 44, 107, 108, 45, 46, 109, 110, 47, 48, 111, 112, 49, 50, 113, 114, 51, 52, 115, 116, 53, 54, 117, 118, 55, 56, 119, 120, 57, 58, 121, 122, 59, 60, 123, 124, 61, 62, 125 };
                static public ulong Mersenne126(ulong dividend)
                {
                    var mod63 = (dividend >> 48) + (dividend & 0xFFFFFFFFFFFF);
                    mod63 = (mod63 >> 24) + (mod63 & 0xFFFFFF);
                    mod63 = (mod63 >> 12) + (mod63 & 0xFFF);
                    mod63 = (mod63 >> 6) + (mod63 & 0x3F);
                    mod63 = (mod63 >> 6) + (mod63 & 0x3F);
                    if (mod63 > 62) mod63 = mod63 - 63;
                    return _mersenne126Table[(mod63 << 1) | (dividend & 0b1)];
                }


                static public ulong Mersenne127(ulong dividend)
                {
                    dividend = (dividend >> 56) + (dividend & 0xFFFFFFFFFFFFFF);
                    dividend = (dividend >> 28) + (dividend & 0xFFFFFFF);
                    dividend = (dividend >> 14) + (dividend & 0x3FFF);
                    dividend = (dividend >> 7) + (dividend & 0x7F);
                    dividend = (dividend >> 7) + (dividend & 0x7F);
                    if (dividend > 126) dividend = dividend - 127;
                    return dividend;
                }


                static public ulong Mersenne255(ulong dividend)
                {
                    dividend = (dividend >> 32) + (dividend & 0xFFFFFFFF);
                    dividend = (dividend >> 16) + (dividend & 0xFFFF);
                    dividend = (dividend >> 8) + (dividend & 0xFF);
                    dividend = (dividend >> 8) + (dividend & 0xFF);
                    if (dividend > 254) dividend = dividend - 255;
                    return dividend;
                }


                static public ulong Mersenne511(ulong dividend)
                {
                    dividend = (dividend >> 36) + (dividend & 0xFFFFFFFFF);
                    dividend = (dividend >> 18) + (dividend & 0x3FFFF);
                    dividend = (dividend >> 9) + (dividend & 0x1FF);
                    dividend = (dividend >> 9) + (dividend & 0x1FF);
                    if (dividend > 510) dividend = dividend - 511;
                    return dividend;
                }


                static public ulong Mersenne1023(ulong dividend)
                {
                    dividend = (dividend >> 40) + (dividend & 0xFFFFFFFFFF);
                    dividend = (dividend >> 20) + (dividend & 0xFFFFF);
                    dividend = (dividend >> 10) + (dividend & 0x3FF);
                    dividend = (dividend >> 10) + (dividend & 0x3FF);
                    if (dividend > 1022) dividend = dividend - 1023;
                    return dividend;
                }
            }
        }
    }
}

Sample benchmarks:

namespace OptimizedModulo.Benchmarks
{
    public class ModuloMod
    {
        public ulong rl;
        private ulong _lDiv5;
        private ulong _lDiv16;

        public ModuloMod()
        {
            // prevent compiler from optimizing away static values
            var counter = new List<string> { "", "", "", ""};
            _lDiv5 = (ulong)counter.Count() + 1;
            _lDiv16 = (ulong)counter.Count() + 12;
        }


        [Benchmark] public ulong Long_Mod() => LongHarness(n => Modulo.Implementations.Long.ModuloOperator(n, _lDiv5));
        [Benchmark] public ulong Long_Mersenne() => LongHarness(Modulo.Implementations.Long.Mersenne5);
        [Benchmark] public ulong Long_Pow2() => LongHarness(n => Modulo.Implementations.Long.ShiftAnd(n, _lDiv16));

        [Benchmark(Baseline = true)]
        public ulong StaticModulo_HC() 
        {
            for (ulong i = 0; i < 512; i++)
                rl += i % 5;
            return rl;
        }

        [Benchmark]
        public ulong StaticModulo() 
        {
            for (ulong i = 0; i < 512; i++)
                rl += i % _lDiv5;
            return rl;
        }

        private ulong LongHarness(Func<ulong, ulong> mod)
        {
            for (ulong i = 0; i < 512; i++)
                rl += mod(i);
            return rl;
        }
    }
}

Results from my environment where this code will actually run (yours will likely differ, mine is constrained by other factors):

benchmark results

Full code with passing test suite and benchmarks app (work in progress) here for the curious.

\$\endgroup\$
  • \$\begingroup\$ Perhaps it would be worth optimizing out the powers of two by testing (v & (v - 1)) == 0 ? \$\endgroup\$ – NetMage Jun 10 '17 at 0:07
  • \$\begingroup\$ @NetMage that is already being done. See the long list of case statements using binary integer literals that return Implementations.Long.ShiftAnd, which is (dividend & (divisor - 1) \$\endgroup\$ – quentin-starin Jun 10 '17 at 1:59
  • 3
    \$\begingroup\$ No, it isn't. NetMage meant that instead of writing 64 lines of code, you could just write one or two lines. That makes the code shorter and even more efficient, although in the part that doesn't need to be. The main point is, as a reader of the code, I am not willing to count the number of zeros in the binary literals, and I currently have to. \$\endgroup\$ – Roland Illig Jun 10 '17 at 7:38
  • \$\begingroup\$ Did you test Mersenne5? The first 10 looks like a typo to me. And you should use >= instead of > to make the code clearer. \$\endgroup\$ – Roland Illig Jun 10 '17 at 7:44
  • 1
    \$\begingroup\$ You should measure whether you need to spell out the calculations for mod3 in Mersenne6, or whether the compiler will inline them anyway. That would make the code a lot clearer. \$\endgroup\$ – Roland Illig Jun 10 '17 at 7:48
7
\$\begingroup\$

I started writing this as a comment, but as I was exploring things got worse and worse.

Your benchmarks (in the comments) do not at all line up with my experience. In fact, they're just the opposite.

I ran your benchmark code, and a few modifications to it, to test truly whether your optimization, specifically for Mersenne5, was faster than the built-in.

Now, I'm not knocking your idea, but if you claim to have a faster production than something, you should have scientifically reproducible results. I should be able to copy/paste your code (which I did) and build my own benchmark (which I did) matching your benchmark (which it did) and get a reproducible result that confirms your theory (which it did not really do). What it did confirm is that the _mod vs. _mer methods differed as you indicated, it did not confirm your version is faster.

What it did confirm, is that when compiled to x64 and using the RyuJIT, your version appears to perform faster. (I put 'appears' because of the fact that this is the only time your algorithm is faster, though your version is significantly slower when using the dispatch approach, which is it's intended usage so I don't even know if that claim can be made.)

And I had this nice long answer written out at work, but of course the draft didn't save when I closed my browser and I'm really not in the mood to go through all the work I did again, so I'm just going to tell you why your benchmarks are wrong and leave it to you to investigate.

First: you benchmarked on only x64 build. I know this because when I ran my benchmarks on x64 they came up with the same general idea as yours: ~4us for your Mersenne5(i), about 8us for ModuloOperator(i, 5) and a little less than 8us for i % 5. However, when I changed this to x86 build, the i % 5 performed over twice as fast as your version.

Second: you did not benchmark your 'dispatcher', which adds a metric tonne of overhead. When I benchmarked it I saw ~21us on x86, and ~17us on x64. So not only is your x86 algorithm slower, it's also extremely slow when using your dispatcher.

Third: you only benchmarked for the value of 5, but what about other key values? You ignored them.

Personally, with the result of the benchmarks I already did (which I may add back in later when I have more time), your code is significantly slower than the built-in, which means this 'optimization' is pointless, as it doesn't optimize at all! What I would recommend, is finding out why RyuJIT is so different (in fact, creating an opposite result) from the 32-bit LegacyJIT.


So I lied, I'm going to go into all the detail I had in my original answer, because I'm already at this point and I may as well finish up. My stress level is already maxed, so I can't give up now!

Prior rambling aside, it's time to talk about what exactly is wrong with your benchmarks.

I'm going to analyze this in a scientific manner. First, we have to ask a question, then do some research, create a hypothesis, formulate an experiment, analyze the results, construct a conclusion, and publish a result. You did some of this, but not all of it. Especially in the experiment.

Question: can the built-in modulo be made any faster?
Research: utilizing the mersenne prime identities, it is theoretically possible.
Hypothesis: Mersenne prime factorization will be faster than the built-in modulo.

Now we have the experiment, this is the really, really hard part. Benchmarking is hard, Eric Lippert taught me that. Though he didn't just teach me that, he taught me a lot more with such a simple response. He taught me what it takes to create a good benchmark, or at least a good enough benchmark.

Now a good experiment has a control, and at least one independent variable, only one of which is modified at a time. We need to identify our independent variables, and that's somewhat difficult. You identified one of them: the algorithm, but there are 4 easily identifiable independent variables:

  1. Architecture. x86 / x64 / Any CPU, this directly affects the compilation, default JITter used, and how the OS handles the resulting program, and what .NET does.
  2. Calling the algorithm directly or via a Func<>. So this is a potential issue, you call the i % 5 method via MethodCall(i, 5), which can add overhead. (Or not, depends on the JITter!)
  3. Dispatching. You built a dispatcher, but you didn't use it. This is a factor we have to grade.
  4. Other values. You tested 5, but what about other key values? Large values? Like, 2, 3, 5, 9, 15, 16, 25, 255?

Finally, to conduct an experiment we absolutely 100% entirely need a control. You cannot justify a scientific result without a control.

Our control will be a base i % n. Nothing more.

So I built a basic benchmark: five methods. One does i % 5, one does Modulo.Implementations.Long.Mersenne5(i), one does Modulo.Implementations.Long.ModuloOperator(i, 5), and the last does Modulo.Optimized(5)(i).

I'm going to post the x64 result first:

// * Summary *

BenchmarkDotNet=v0.10.8, OS=Windows 10 Redstone 2 (10.0.15063)
Processor=Intel Core i7-5930K CPU 3.50GHz (Broadwell), ProcessorCount=12
Frequency=3415991 Hz, Resolution=292.7408 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 64bit RyuJIT-v4.7.2098.0
  DefaultJob : Clr 4.0.30319.42000, 64bit RyuJIT-v4.7.2098.0


                          Method |      Mean |     Error |    StdDev | Scaled |
-------------------------------- |----------:|----------:|----------:|-------:|
                     RawModulo_5 |  7.845 us | 0.0112 us | 0.0105 us |   1.00 |
           RawModulo_ViaMethod_5 |  7.868 us | 0.0341 us | 0.0319 us |   1.00 |
     OptimizedModulo_ViaMethod_5 |  2.588 us | 0.0017 us | 0.0016 us |   0.33 |
 OptimizedModulo_ViaDispatcher_5 | 17.415 us | 0.0156 us | 0.0122 us |   2.22 |

// * Hints *
Outliers
  ModVsOptimization.OptimizedModulo_ViaDispatcher_5: Default -> 3 outliers were removed

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  Scaled : Mean(CurrentBenchmark) / Mean(BaselineBenchmark)
  1 us   : 1 Microsecond (0.000001 sec)

// ***** BenchmarkRunner: End *****

Alright, not bad. Better than when I was at work but I'm on a significantly faster PC. So, Your code runs 1/3 of the time of the base on my system. Great. Next, x86:

// * Summary *

BenchmarkDotNet=v0.10.8, OS=Windows 10 Redstone 2 (10.0.15063)
Processor=Intel Core i7-5930K CPU 3.50GHz (Broadwell), ProcessorCount=12
Frequency=3415991 Hz, Resolution=292.7408 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.7.2098.0
  DefaultJob : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.7.2098.0


                          Method |      Mean |     Error |    StdDev | Scaled |
-------------------------------- |----------:|----------:|----------:|-------:|
                     RawModulo_5 |  4.588 us | 0.0009 us | 0.0007 us |   1.00 |
           RawModulo_ViaMethod_5 |  4.587 us | 0.0003 us | 0.0002 us |   1.00 |
     OptimizedModulo_ViaMethod_5 |  8.009 us | 0.0246 us | 0.0205 us |   1.75 |
 OptimizedModulo_ViaDispatcher_5 | 23.201 us | 0.0467 us | 0.0437 us |   5.06 |

// * Hints *
Outliers
  ModVsOptimization.RawModulo_5: Default                 -> 2 outliers were removed
  ModVsOptimization.RawModulo_ViaMethod_5: Default       -> 2 outliers were removed
  ModVsOptimization.OptimizedModulo_ViaMethod_5: Default -> 2 outliers were removed

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  Scaled : Mean(CurrentBenchmark) / Mean(BaselineBenchmark)
  1 us   : 1 Microsecond (0.000001 sec)

// ***** BenchmarkRunner: End *****

Oh boy, that got awkward. This one is about 1.75x the time mine took, bad deal.

Does Any CPU hold any luck?

// * Summary *

BenchmarkDotNet=v0.10.8, OS=Windows 10 Redstone 2 (10.0.15063)
Processor=Intel Core i7-5930K CPU 3.50GHz (Broadwell), ProcessorCount=12
Frequency=3415991 Hz, Resolution=292.7408 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.7.2098.0
  DefaultJob : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.7.2098.0


                          Method |      Mean |     Error |    StdDev | Scaled |
-------------------------------- |----------:|----------:|----------:|-------:|
                     RawModulo_5 |  4.588 us | 0.0008 us | 0.0007 us |   1.00 |
           RawModulo_ViaMethod_5 |  4.588 us | 0.0005 us | 0.0005 us |   1.00 |
     OptimizedModulo_ViaMethod_5 |  8.013 us | 0.0165 us | 0.0129 us |   1.75 |
 OptimizedModulo_ViaDispatcher_5 | 22.330 us | 0.0431 us | 0.0360 us |   4.87 |

// * Hints *
Outliers
  ModVsOptimization.RawModulo_5: Default                     -> 3 outliers were removed
  ModVsOptimization.RawModulo_ViaMethod_5: Default           -> 1 outlier  was  removed
  ModVsOptimization.OptimizedModulo_ViaMethod_5: Default     -> 3 outliers were removed
  ModVsOptimization.OptimizedModulo_ViaDispatcher_5: Default -> 2 outliers were removed

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  Scaled : Mean(CurrentBenchmark) / Mean(BaselineBenchmark)
  1 us   : 1 Microsecond (0.000001 sec)

// ***** BenchmarkRunner: End *****

Nope, same as x86. Damn. Well, on the bright side, we have completely disproven whether your method is better or not. It's neither better, nor worse. Until we examine the API. Do I do i % 5 or Modulo.Implementations.Long.Mersenne5(i) (just to get a negligible speed increase)? I think I'll pick i % 5, sorry chief.


So what did we learn? We learned that benchmarking is hard, and that by the time we factor in all the candidates, we can finally come up with a result: inconclusive.

Do note, my intention is not to be rude, it just seems that way because I got a little flustered after reading the following part of the question:

Below I have code that allows one to retrieve a function representing the modulo operator for a specific divisor. Benchmarking has shown these handily outperform the built-in % operator, even with the overhead of a Func<> (which is tiny).

I don't know about 'handily', I didn't have to work too hard to make the built-in win every time. In fact, all I did is use your code the way it was intended.

The only time you win consistently, is on x64 if you have pre-cached the _mod for the specific value. But at that point, the added strain of having to do so just puts me off. I'd just prefer to stick to i % 5, especially since your code only performs faster on x64, which I bet is a bug with either RyuJIT and LegacyJIT (I tested both before making this claim), so I'm going to ask about it with some other persons, because I'm concerned about what's going on here. I'm suspecting an issue with Windows / .NET on the 64-bit platform. I also need to investigate ILDASM but that's not enough of this for our answer here.

If anyone wants the reproducible benchmarking code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace CSharpTests
{
    class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<ModVsOptimization>();
            Console.ReadLine();
        }
    }

    public class ModVsOptimization
    {
        [Benchmark(Baseline = true)]
        public ulong RawModulo_5()
        {
            ulong r = 0;
            for (ulong i = 0; i < 1000; i++)
            {
                r += i % 5;
            }
            return r;
        }

        [Benchmark]
        public ulong RawModulo_ViaMethod_5()
        {
            ulong r = 0;
            for (ulong i = 0; i < 1000; i++)
            {
                r += Modulo.Implementations.Long.ModuloOperator(i, 5);
            }
            return r;
        }

        [Benchmark]
        public ulong OptimizedModulo_ViaMethod_5()
        {
            ulong r = 0;
            for (ulong i = 0; i < 1000; i++)
            {
                r += Modulo.Implementations.Long.Mersenne5(i);
            }
            return r;
        }

        [Benchmark]
        public ulong OptimizedModulo_ViaDispatcher_5()
        {
            ulong r = 0;
            for (ulong i = 0; i < 1000; i++)
            {
                r += Modulo.Optimized(5)(i);
            }
            return r;
        }
    }
}

Don't give up, you could still make this better. You just saw where to improve: start with the Optimized(n) method, and go from there. You can make this better. You may not ever consistently beat the built-in modulo operator, but if you can get close enough that's impressive.


Addendum:

As pointed out on this Stack Overflow answer, your Mersenne5 implementation is wrong. I'll leave it to that answer to explain how and why, they did a wonderful job.

\$\endgroup\$
  • \$\begingroup\$ I'll have to read this at length later but 1. I only provided the benchmark for the single environment I am concerned with, the one my code will run in. I never claimed it was faster in every environment. Obviously it will be different. 2. You misunderstand how the dispatch will be used. It is called extremely infrequently compared to the number of times modulo is executed. If you're interested, lots more benchmarks: bitbucket.org/quentin-starin/optimizedmodulo \$\endgroup\$ – quentin-starin Jun 15 '17 at 23:31
  • 3
    \$\begingroup\$ GO SCIENCE! (And thanks for the shout-out!) \$\endgroup\$ – Eric Lippert Jun 16 '17 at 0:27
  • \$\begingroup\$ If I have learned anything from you @EricLippert, it's that you should never take what you're given at face-value. (You may also be interested in this if you haven't seen it or didn't already investigate it. I would actually be curious on what you think of the issue, as it's very curious, and I'm wondering if you can think of optimizations that could be applied at the compiler level for x64-based systems.) \$\endgroup\$ – 410_Gone Jun 16 '17 at 0:31
  • \$\begingroup\$ Yeah, I saw that question and the answers earlier today and decided that it was too long to read. :-) \$\endgroup\$ – Eric Lippert Jun 16 '17 at 0:32
  • \$\begingroup\$ @EricLippert Well as much as I'd love your input, I respect that. Slight ego stroke: I've reread your answers to my benchmarking question and my Failable<T> question many, many times, and I even went so far as to implement the remaining monad operators you mentioned on my Failable<T> (which I will be posting as a question eventually, and would love your input), and I'd like to think I've learned a lot from you. I think you've forced me to change how I think about problems, and I appreciate that. \$\endgroup\$ – 410_Gone Jun 16 '17 at 1:10
2
\$\begingroup\$

Integer division by a constant can be converted to a reciprocal multiplication followed by a right shift or addition. Division by Invariant Integers using Multiplication is probably the most well known algorithm for doing this. It uses a reciprocal upper multiplication followed by a right shift.

Here are a few ways that this could be implemented:

  • Port the C code from libdivide to C#. It is under the zlib license.
  • Call libdivide from C# - it has a C++/CLI build.
  • Compile libdivide as a native code shared library and call it with P/Invoke
  • Use BigInteger or a UInt128 type to implement the 128-bit arithmetic.
  • If the range of possible divisors is known and relatively small, then you could precompute the reciprocals and correction steps in advance.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.