delphi - 检查 64 位常数乘法参数

Question

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

我仍然想减少时间，所以我需要一个可以非常快速地将 NativeUInt(即 32 位平台上的 UInt32，64 位平台上的 UInt64)除以 100 的例程。所以我使用乘以常数。这在 32 位代码中工作得很好，但我不能 100% 确定在 64 位代码中。

所以我的问题是:有没有办法检查无符号 64 位值与常量相乘结果的可靠性？我通过简单地尝试 UInt32 (0..$FFFFFFFF) 的所有值来检查 32 位值。这大约需要。 3分钟。检查所有 UInt64 将花费比我一生更长的时间。有没有办法检查所使用的参数(常数、移位后)是否可靠？

我注意到，如果所选参数错误(但接近)，对于像 $4000004B 这样的值，DivMod100() 总是会失败。是否有特殊值或范围来检查 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;
}

compiles to (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

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

<小时/>

乘以 100 部分。

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

你们的评论都说他们选择的版本更快。如果是这样，那是因为一些微妙的指令对齐或其他次要影响:在 Intel SnB 系列上，它是 the same number of uops (3) ，以及相同的关键路径延迟(mov imm 不在关键路径上，mul 为 3 个周期)。

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

imul 之所以有效，是因为 you're only using the low 64b of the result 。 mul 不存在 2 或 3 个操作数形式，因为无论输入的有符号或无符号解释如何，结果的低半部分都是相同的。

顺便说一句，带有 -march=native 的 clang 使用 mulx 表示 64x64->128，而不是 mul，但没有增益任何东西。根据 Agner Fog 的表格，它的延迟比 mul 差一个周期。

<小时/>

AMD 对于 imul r,r,i(尤其是 64b 版本)的延迟比 3c 还要差，这也许就是 gcc 避免使用它的原因。我不知道 gcc 维护者在调整成本上投入了多少工作，因此像 -mtune=haswell 这样的设置工作良好，但是很多代码不是用任何 -mtune 编译的 设置(即使是 -march 隐含的设置)，因此当 gcc 做出最适合旧 CPU 或 AMD 的选择时，我并不感到惊讶。

clang 仍然使用 imul r64, r64, imm 和 -mtune=bdver1 (Bulldozer)，这可以节省 m-ops，但比使用多 1c 延迟为代价lea/lea/shl. (在 Bulldozer 上，比例>1 的 lea 延迟为 2c)。