performance - 使用查找表或左/右位移以获得 2 整数的幂是否更快？

Question

假设我想用第 N 位设置构建位掩码。我有 N 作为整数。

哪个更好？1 << N还是查找表（指针算术加法）？

我的猜测是，单个位移操作比内存查找更快，并且只有一次高速缓存热，LUT 才有战斗机会。但是，如果是这种情况，那么为什么 LUT 通常是位旋转问题中最快的解决方案？仅仅是因为我们这些天在我们的 CPU 中拥有巨大的缓存吗？

让我用我最关心 x86-64 上的这个操作这一事实来限定这个问题。

Answer 1

位移总是比查找表或计算快得多。

Answer 2

你确定吗？我运行了这个 VB 程序，结果有点变化，但查找通常比位移快，并且比空时间高不了多少。这可能是因为缓存的原因，所以很难从这里一概而论。

我从随机移位值中得到了类似的结果，但当然随机数生成所花费的时间比其他任何事情都长。

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim SW As New Stopwatch()
Dim TimeShift As Long
Dim TimeLookUp As Long
Dim Timenull As Long
Dim i As Integer
Dim j As Integer
Dim Bit As UInteger
Dim R As New Random()
Dim total As UInteger
Dim S = New System.Text.StringBuilder()

total = 0
SW.Start()
j = 0
For i = 1 To RepCount
  Bit = CUInt(1) << (j And 31)
  j += 1
  'Bit = 1 << (R.Next(31))
  total = total Or Bit
Next
SW.Stop()
TimeShift = SW.ElapsedMilliseconds

SW.Reset()
SW.Start()
For i = 1 To RepCount
  Bit = Bits(j And 31)
  j += 1
  'Bit = Bits(R.Next(31))
  total = total Or Bit
Next
SW.Stop()
TimeLookUp = SW.ElapsedMilliseconds

SW.Reset()
SW.Start()
For i = 1 To RepCount
  total = total Or (j And 31)
  j += 1
Next
SW.Stop()
Timenull = SW.ElapsedMilliseconds

If Stopwatch.IsHighResolution Then
  S.Append("High")
Else
  S.Append("Low")

End If
S.Append(" frequency clock")
S.AppendLine()
S.Append("Shift time= " & TimeShift & " ms")
S.AppendLine()
S.Append("Lookup time= " & TimeLookUp & " ms")
S.AppendLine()
S.Append("Null time=" & Timenull & " ms")
S.AppendLine()
S.Append("Total= " & total.ToString)

MsgBox(S.ToString)
End Sub
End Class