检查乘以64位的常数参数

Question

对于我的BigInteger代码,对于非常大的BigIntegers,输出结果很慢.所以现在我使用一个递归的分而治之算法,它仍然需要2'30"才能将当前最大的已知素数转换为超过2200万位数的十进制字符串(但只有135 ms将其转换为十六进制字符串) .

我仍然想减少时间,所以我需要一个例程,可以将NativeUInt(即32位平台上的UInt32,64位平台上的UInt64)除以100非常快.所以我使用乘法乘法.这在32位代码中工作正常,但我对64位不是100%肯定.

所以我的问题是:有没有办法检查乘以无符号64位值的乘法结果的可靠性？我通过简单地尝试使用UInt32的所有值(0 .. $ FFFFFFFF)来检查32位值.这花费了大约.3分钟.检查所有UInt64将花费比我的生命更长的时间.有没有办法检查使用的参数(恒定,换档后)是否可靠？

我注意到,如果所选参数错误(但接近),则DivMod100()总是失败$4000004B.是否有特殊值或范围来检查64位,所以我不必检查所有值？

我目前的代码:

const
{$IF DEFINED(WIN32)}
  // Checked
  Div100Const = UInt32(UInt64($1FFFFFFFFF) div 100 + 1);
  Div100PostShift = 5;
{$ELSEIF DEFINED(WIN64)}
  // Unchecked!!
  Div100Const = $A3D70A3D70A3D71; 
  // UInt64(UInt128($3 FFFF FFFF FFFF FFFF) div 100 + 1); 
  // UInt128 is fictive type.
  Div100PostShift = 2;
{$IFEND}

// Calculates X div 100 using multiplication by a constant, taking the
// high part of the 64 bit (or 128 bit) result and shifting
// right. The remainder is calculated as X - quotient * 100;
// This was tested to work safely and quickly for all values of UInt32.
function DivMod100(var X: NativeUInt): NativeUInt;
{$IFDEF WIN32}
asm
        // EAX = address of X, X is UInt32 here.
        PUSH    EBX
        MOV     EDX,Div100Const
        MOV     ECX,EAX
        MOV     EAX,[ECX]
        MOV     EBX,EAX
        MUL     EDX
        SHR     EDX,Div100PostShift
        MOV     [ECX],EDX       // Quotient

        // Slightly faster than MUL

        LEA     EDX,[EDX + 4*EDX] // EDX := EDX * 5;
        LEA     EDX,[EDX + 4*EDX] // EDX := EDX * 5;
        SHL     EDX,2             // EDX := EDX * 4; 5*5*4 = 100.

        MOV     EAX,EBX
        SUB     EAX,EDX         // Remainder
        POP     EBX
end;
{$ELSE WIN64}
asm
        .NOFRAME

        // RCX is address of X, X is UInt64 here.
        MOV     RAX,[RCX]
        MOV     R8,RAX
        XOR     RDX,RDX
        MOV     R9,Div100Const
        MUL     R9
        SHR     RDX,Div100PostShift
        MOV     [RCX],RDX      // Quotient

        // Faster than LEA and SHL

        MOV     RAX,RDX
        MOV     R9D,100
        MUL     R9
        SUB     R8,RAX
        MOV     RAX,R8         // Remainder
end;
{$ENDIF WIN32}

Answer 1

像往常一样，在编写优化代码时，使用编译器输出作为提示/起点。可以安全地假设它所做的任何优化在一般情况下都是安全的。错误代码编译器错误很少见。

gcc 实现无符号 64 位 divmod，常数为0x28f5c28f5c28f5c3. 我还没有详细研究生成除法常量，但是有一些生成它们的算法可以给出已知的良好结果（因此不需要进行详尽的测试）。

该代码实际上有一些重要的区别：它使用与 OP 常量不同的常量。

请参阅评论来分析它实际上在做什么：首先除以 4，因此它可以使用一个仅适用于当被除数足够小时除以 25 的常量。这也避免了以后需要添加。

#include <stdint.h>

// rem, quot ordering takes one extra instruction
struct divmod { uint64_t quotient, remainder; }
 div_by_100(uint64_t x) {
    struct divmod retval = { x%100, x/100 };
    return retval;
}

编译为（gcc 5.3 -O3 -mtune=haswell）：

    movabs  rdx, 2951479051793528259
    mov     rax, rdi            ; Function arg starts in RDI (SysV ABI)
    shr     rax, 2
    mul     rdx
    shr     rdx, 2
    lea     rax, [rdx+rdx*4]    ; multiply by 5
    lea     rax, [rax+rax*4]    ; multiply by another 5
    sal     rax, 2              ; imul rax, rdx, 100 is better here (Intel SnB).
    sub     rdi, rax
    mov     rax, rdi
    ret
; return values in rdx:rax

使用“binary”选项查看十六进制常量，因为反汇编器输出就是这样做的，这与 gcc 的 asm 源输出不同。

乘以 100 部分。

gcc 使用上述 lea/lea/shl 序列，与您的问题相同。您的答案是使用mov imm/mul序列。

你们的评论都说他们选择的版本更快。如果是这样，这是因为一些微妙的指令对齐或其他次要影响：在英特尔 SnB 系列上，微指令数量相同 (3)，并且关键路径延迟相同（mov imm偏离关键路径，mul为 3 个周期） 。

clang 使用我认为最好的选择 ( imul rax, rdx, 100)。在看到 clang 选择它之前我就想到了这一点，但这并不重要。那是 1 个融合域 uop（只能在 p0 上执行），仍然具有 3c 延迟。因此，如果您使用此例程进行多精度处理时受到延迟限制，它可能不会有帮助，但它是最好的选择。（如果您受到延迟限制，将代码内联到循环中而不是通过内存传递参数之一可以节省大量周期。）

imul有效，因为您只使用结果的低 64b。没有 2 或 3 操作数形式mul因为无论输入的有符号或无符号解释如何，结果的低半部分都是相同的。

顺便说一句， clang with-march=native用于mulx64x64->128，而不是mul，但不会从中获得任何东西。根据 Agner Fog 的表格，它的延迟比mul.

AMD 的延迟比 3c 更差imul r,r,i（尤其是 64b 版本），这也许就是 gcc 避免使用它的原因。我不知道 gcc 维护者投入了多少工作来调整成本，这样设置就-mtune=haswell可以很好地工作，但是很多代码都没有使用任何-mtune设置进行编译（即使是 暗示的设置-march），所以当 gcc 做出最适合旧版本的选择时，我并不感到惊讶CPU，或AMD。

clang 仍然使用imul r64, r64, immwith -mtune=bdver1(Bulldozer)，它可以节省 m-ops，但比使用 lea/lea/shl 多花费 1c 的延迟。（在 Bulldozer 上，比例>1 的 lea 延迟为 2c）。