和快于整数模运算？

Question

可以重新表达:

• 我%

如:

• 我和(m-1)

哪里,

• 我是无符号整数
• m是2的幂

我的问题是:AND操作更快吗？现代CPU在单个指令中不支持硬件中的整数模数吗？我对ARM很感兴趣,但是在它的指令集中看不到模运算.

Answer 1

这些日子比"单指令"更复杂.现代CPU是复杂的野兽,需要将其指令分解为问题/执行/延迟.它通常还取决于除法/模数的宽度 - 涉及多少位.

在任何情况下,我都不知道32位是任何内核(ARM)上的单周期延迟.在"现代"ARM上有整数除法指令,但仅限于某些实现,最值得注意的是不是最常见的指令 - Cortex A8和A9.

在某些情况下,编译器可以省去将除法/模数转换为位移/掩码操作的麻烦.但是,只有在编译时知道该值时才可以执行此操作.在你的情况下,如果编译器可以确定 'm'总是一个2的幂,那么它将优化它到位操作,但如果它是传递给函数的一个变量(或以其他方式计算),那么它可以并且,将采用完全分割/模数.这种代码构造通常有效(但并非总是如此 - 取决于优化器的智能程度):

unsigned page_size_bits = 12;
unsigned foo(unsigned address) {
  unsigned page_size = 1U << page_size_bits;
  return address / page_size;
}

诀窍是让编译器知道"page_size"是2的幂.我知道gcc和变体会特殊情况,但我不确定其他编译器.

作为任何核心的经验法则 - 无论是否为ARM(甚至是x86),更喜欢使用位移/掩码来划分/模数.即使您的核心存在硬件鸿沟,手动执行也会更快.

Answer 2

您可能对Embedded Live:ARM Cortex-M Architecture的嵌入式程序员指南感兴趣.

ARM Cortex-M系列具有无符号和有符号的除法指令UDIV和SDIV,需要2到12个周期.没有MOD指令,但是通过{S,U} DIV后跟乘法和减法指令MLS获得等效结果,该指令需要2个周期,总共4-14个周期.

AND指令是单周期,因此快4-14倍.