如何使用SIMD指令高效實現atoi？

如何使用SIMD實現atoi？

問題：
我想嘗試編寫一個atoi使用 SIMD 指令實現，包含在 RapidJSON 中。我想出來的演算法如下：

1. 以以下方式初始化長度為N 的向量：
   [10^N..10^1]
2. 轉換將緩衝區中的每個字元轉換為整數並將它們放入另一個向量中。
3. 將有效數字向量中的每個數字乘以匹配的數字向量中的數字並對結果求和。

我的演算法正確嗎？有更好的辦法嗎？有使用任何 SIMD 指令集的 atoi 參考實作嗎？

答案：
演算法正確且完整。它適用於 int 和 uint，從 MIN_INT=-2147483648 到 MAX_INT=2147483647 以及從 MIN_UINT=0 到 MAX_UINT=4294967295。

提供了參考實現，使用 intel 語法用 GNU 彙編器編寫。

這段程式碼的屬性如下：

• 前導'-' 字元表示負數（合理），前導' ' 字元被忽略
• 前導零（帶或不帶符號字元）被忽略
• 溢出被忽略 -更大的數字只是環繞
• 零長度字符串導致值0 = -0
• 識別無效字符，並且轉換在第一個無效字符處結束
• 最後一個前導零之後的至少16 個位元組必須可訪問，並且在EOS後讀取可能有安全隱患留給呼叫者
• 只需要SSE4.2

的方法演算法如下：

• ESI 中需要指向數字字串
• 檢查第一個字元是否為“-”，然後指示EDX 中是否為負數(A)
• 檢查前導零和EOS (B)
• 檢查字串取得有效數字並取得有效字元的strlen() (C)
• 反轉字串，以便
  10^0 的冪始終為BYTE 15
  10^1始終位於位元組14
  10^2 總是位於位元組13
  10^3 總是在BYTE 12
  10^4 總是在BYTE 11
  ...
  並屏蔽掉所有以下字元(D)
• 從中減去飽和的「0」 16個可能的字元中的每一個(1)
• 取得16 個連續的位元組值，並將它們拆分為兩個XMM 暫存器中的單字
  (2)
  P O N M L K J I | H G F E D C B A ->
  H G F E | DC B A (XMM0)
  P O N M | L K J I (XMM1)
• 將每個WORD 乘以其位值模10000 (1,10,100,1000)
  （小於MAX_WORD 的因子，每個QMMWORD/halfX 4 個因子）
  ( 2) 所以我們可以在另一個之前水平組合兩次
  PMADDWD 指令可以執行此操作以及下一步：
• 將相鄰的WORD 水平添加到DWORD (3)
  H1000 G100 F10 E1 | D1000 C100 B10 A1 (XMM0)
  P1000 O100 NP1000 O100 N >1 | L1000 K100 J
10 I
• 1 (XMM1)將XMM0 和XMM1 中的相鄰DWORD 水平添加到XMM0 (
  4
  )
  xmmDst[31-0] = xmm0[63-32] xmm0[31-0]
  xmmDst[63-32] = xmm0[127-96] xmm0[95-64]
xmmDst[95-64] = xmm1[63-32] xmm1[31-0]
• xmmDst[127-96] = xmm1[127-96] xmm1[95-64]XMM0 中的值乘以因子(
  5)P1000 O100 N
  10 M 1（DWORD 因子1000000000000 = 對於DWORD來說太大，但對於QWORD 數字字串可能有用）L1000 K100 J
  10 I1（DWORD 因子100000000）HH1000 G
  100 F10 E1（DWORD 因子10000）D1000 C
100 B
• 10 A

  1（DWORD 因子1）

  最後一步是將這四個DWORD 加在一起2
  PHADDD 由2
  • (PSHUFD PADDD)
    xmm0[31-0] = xmm0[63-32] xmm0[31-0] (
    6)
  xmm0 [63-32] = xmm0[127-96] xmm0[95-64]
  • (上面的QWORD 包含相同內容，被忽略）xmm0[31-0] = xmm0[63-32] xmm0[31-0 ] (
  7
  )
• 如果數字為負數（在EDX 中表示為000...0=pos 或111...1=neg），則取反(
8

)

的結果Haswell 32 位元的Intel-IACA吞吐量分析：

吞吐量分析報告

區塊吞吐量：16.10 個週期吞吐量瓶頸：迭代

每次迭代週期中的連接埠綁定：

| 港口| 0 - DV | 1 | 2-D | 3 - D | 4 | 5 | 6 | 7 |

|週期| 9.5 0.0 | 10.0 | 4.5 4.5 | 4.5 4.5 | 0.0 | 0.0 11.1 | 11.1 11.4 | 11.4 0.0 |

N - 連接埠號碼或週期數資源衝突導致延遲，DV - 分配器管道（在連接埠0 上）
D - 資料取得管道（在連接埠0 上）
D - 資料取得管道（在連接埠02和3 上），CP - 在關鍵路徑

F -與上一條指令的巨集融合發生

• • 
    指令微操作未綁定至連接埠

    ^ - 微融合發生
    - ESP追蹤同步uop 已發出

    
    @ - SSE 指令後面跟著AVX256指令，幾十個週期的損失是預計

    ！ - 不支援指令，在分析中未考慮

| | 數量| 循環連接埠壓力| |

| 哎呀| 0 - DV | 1 | 2-D | 3 - D | 4 | 5 | 6 | 7 | |

| 0* | | | | | | | | | |異或eax, eax
| 0* | | | | | | | | | |異或ecx, ecx
| 0* | | | | | | | | |異或edx, edx

| 1 | | 0.1 | 0.1 | | | | 0.9 |

以上是如何使用SIMD指令高效實現atoi？的詳細內容。更多資訊請關注PHP中文網其他相關文章！