如何在固定时间内比较字符串？

TL; DR：使用程序集。

恒定时间代码确实很难实现。要真正保持恒定的时间，您需要：

• 恒定时间算法
• 所述算法的恒定时间实现。

“恒定时间算法”是什么意思？

字符串比较的例子很棒。在大多数情况下，您希望比较花费的时间越少越好，这意味着要对第一个差异有所帮助：

fn simple_compare(a: &str, b: &str) -> bool {
    if a.len() != b.len() { return false; }

    for (a, b) in a.bytes().zip(b.bytes()) {
        if a != b { return false; }
    }

    true
}

但是，无论输入如何，恒定时间版本算法版本都应具有恒定时间：

• 输入应始终具有相同的大小，
• 无论差异位于何处（如果有），计算结果所用的时间应相同。

Lukas给出的算法几乎是正确的：

/// Prerequisite: a.len() == b.len()
fn ct_compare(a: &str, b: &str) -> bool {
    debug_assert!(a.len() == b.len());

    a.bytes().zip(b.bytes())
        .fold(0, |acc, (a, b)| acc | (a ^ b) ) == 0
}

“恒定时间实施”是什么意思？

即使算法是恒定时间，实现也可能不是。

如果未使用完全相同的CPU指令序列，则在某些体系结构上，其中一条指令可能会更快，而另一条指令会更慢，并且实现会丢失。

如果该算法使用表查找，则可能会有更多或更少的缓存未命中。

您可以在Rust中编写恒定时间的字符串比较实现吗？

没有。

Rust语言可能适合该任务，但是其工具链不适合：

• LLVM优化器会对您的算法造成严重破坏，将其短路，从而消除现在或将来的不必要读取，
• LLVM后端会对您的实施造成严重破坏，选择不同的说明。

总之，今天，从Rust访问恒定时间实现的唯一方法是在汇编中编写所述实现。