我如何推斷性能影響（更改為更緊湊的48位整數表示）？-有解無憂

與此問題類似，在 x86 上成功的非對齊訪問的實際效果是什么？

我們有一個應用程式可以搜索大量結構陣列，其中鍵是 48 位整數。我們一直使用 64 位型別來表示 48 位整數，假設空間便宜并且對齊可以提高性能。

陣列使用的空間是巨大的。所以我很好奇切換到緊湊表示實際上會產生什么影響。

這是一個性能問題，因此基本答案是衡量。還接受通過為您的使用模式選擇最佳演算法來最大程度地影響性能。

問題是我們可以在測量之前假設什么？

有效改變：

struct Entry
{
   uint64_t key;
   int32_t value1;
   int32_t value2;   
};
std::vector<Entry> foobar;

說：

struct uint48
{
   uint16_t v[3];
}

struct Entry
{
   uint48 key;
   int32_t value1;
   int32_t value2;   
} __attribute__((packed));
std::vector<Entry> snafu;

在實踐中進行此更改將節省相當多的記憶體。我很好奇我可以期望它對實踐中的性能產生什么影響。

唯一確定的方法當然是測量，但這需要相當大的努力。

我可以推斷出預期的效果嗎？

這是我的出發點：

搜索結構包括許多基于 48 位密鑰操作的操作（主要是漢明距離而不是相等）。
該結構始終保持只讀狀態。
有啟發式方法意味著連續搜索應該使用本地資料并希望利用 CPU 快取。
假設基于 x86_64 的體系結構至少具有“標準”附加組件，例如 SSE
在 Linux 上使用 g

一方面，我們有：

AnEntry當前是 128 位 = 16 位元組寬。

如果存在這種情況，將其減少到 14 將消除任何 16 位元組對齊的好處。
提取 48 位整數變得更加昂貴。

IEuint64_t foo = someEntry.key;

另一方面：

減小每個條目的大小會增加所需資料在快取中的機會。

整個資料集太大而無法完全放入任何快取中。

減少記憶體使用的成本可能會降低性能，但有沒有辦法估計它來證明執行實際實驗是合理的？

例如，如果我們預計性能會損失 50%，那么它可能甚至不值得嘗試。另一方面，如果它可能更像 5%，那么它可能是值得的。

無論如何，我希望將來進行實驗，但由于其他承諾，這可能是一個相當遙遠的未來。

我認為這是一個有趣的問題，就你應該如何思考這些問題而言。

優化是一個從演算法到手工組裝的兔子洞。您可以做很多事情，但途中會遇到很多陷阱。我從演算法方面對它很熟悉，但在理解 a 更改如何使更高層影響事物在 CPU 上的運行方式時，我就不那么熟悉了。

通常，我們通過添加內核和 RAM 以及具有更多內核的節點來進行擴展，因為這些比程式員的時間和支持不同商品硬體優化/重新編譯的成本更低。但這項練習非常具有教育意義，并且可能會從低垂的果實中獲得很多收益。

這個問題最初使用了來自（此處）[https://stackoverflow.com/a/26198075/1569204] 為 uint48 建議的另一個定義：

struct uint48
{
  unsigned long long v:48;
} __attribute__((packed));

有人指出，這實際上可能不會給出 6 位元組的布局。這被留下，否則參考它的答案沒有意義。

到目前為止的答案都建議從 AoS 布局切換到SoA 布局。這確實是一個非常好的觀點。與我單獨討論的那個相比，這可能是一個更好的改變。從這個意義上說，他們回答了性能問題。這也鼓勵了更多的思考并問自己一些更好的問題。

到目前為止還沒有討論 48 位型別的最佳布局和對齊的實際效果。

考慮：

uint64_t key:48;

int64_t x = key;

對比

struct uint48
{
   int32_t msb;
   int16_t lsb;
};
uint48 key;
int64_t x = (int64_t)key.msb   (int64_t)key.lsb;

對比

struct uint48
{
   int8_t v[6];
};
uint48 key;

等等

另外，對齊相對于其他考慮因素有多重要？

uj5u.com熱心網友回復：

您對 C 和 C 'bitfield' 特性的理解非常缺乏

您struct uint48的意思是“分配給我一個unsigned long long. 現在v使用 48 位放置在其中，留下 16 位填充。”。

一組位域成員總是被填充到其基本型別的大小。 (sizeof (uint48)) >= (sizeof (unsigned long long))

只有在同一結構中有多個具有相同基本型別的非靜態位域，它們被宣告為彼此相鄰，并且多個相鄰域適合位域的基本型別時，才能節省記憶體。

您的更改對記憶體消耗沒有影響。

為了使搜索性能更好，請使用更好的搜索演算法

您提到您正在根據漢明距離搜索不精確的匹配項。您需要對結構進行排序并實作利用該排序執行修剪的查找。

如果您正在尋找漢明距離為 4 或更少的匹配項，并且前 16 位中有 6 位不同，您應該跳過整個塊，因為無論接下來的 32 位中出現什么值，您永遠不會得到總距離為 4。因此您可以修剪整個子空間而不是搜索它。

基數樹可能會是一個合適的結構（可能不是最優的，但比你所擁有的有很大的改進），因為前綴距離為樹的那個分支更深的距離提供了一個下限，允許你跳過（修剪）大樹的部分。

這種資料結構包含了@krlmlr關于將關聯值從鍵串列中移開的優秀觀點，因為在基數樹中，鍵實際上隱含在樹結構中，并且您永遠不會到達存盤葉值的最后一層（將它們放入快取中），直到您已經處理了密鑰并驗證了您的條件得到滿足。

如果您不知道允許的失配權重，您仍然應該使用一些分支定界技術。

uj5u.com熱心網友回復：

struct uint48
{
  unsigned long long v:48;
} __attribute__((packed));

不要那樣做。它告訴編譯器物件可能只是位元組對齊的，因此它通常必須使用未對齊的加載來訪問它。使用三個可能會更好uint16_t，編譯器至少可以假設它是兩位元組對齊的。或者也許通過告訴編譯器它是兩位元組對齊的而不是打包的。（在某些情況下，根據快取模式和其他因素，保留一個陣列uint32_t和另一個陣列甚至可能是有益的uint16_t，然后編譯器可以使用適合該型別的一條指令加載每個陣列。）

假設一個基于 x86_64 的架構。

這不足以衡量績效。該架構中有許多不同的處理器模型，它們可以在不同的系統中進行不同的配置，不同的作業系統對其應用不同的設定。

如果存在這種情況，將其減少到 14 將消除任何 16 位元組對齊的好處。

在某些 x86-64 處理器上肯定有 16 位元組對齊的好處。從您問題中的資訊來看，您是否正在使用它們中的任何一個是未知的。如果您在 16 位元組結構中有不同的欄位，我懷疑會有很多好處。（統一欄位可能會受益于各種 SIMD 功能，如 SSE2、AVX 等。）

減小每個條目的大小會增加所需資料在快取中的機會。

通過仔細考慮使用模式和資料布局以及基于這些考慮的后續演算法重新設計，通常可以更好地改進快取行為，而不是稍微減少所使用的資料大小。

減少記憶體使用的成本可能會降低性能，但有沒有辦法估計它來證明執行實際實驗是合理的？

是的，如果您對演算法的資料訪問模式、您使用的硬體等有足夠的資訊。發布的問題中沒有此類資訊。

uj5u.com熱心網友回復：

我希望有一個值得考慮的選擇

struct Keys {
    uint32_t keys_msb_bits[N];
    uint16_t keys_lsb_bits[N];
};
struct Values {
    int32_t value1[N];
    int32_t value2[N];
};

使用N==8，每個結構都不會非常對齊。可以每個Values都與快取線邊界對齊，而鍵將按 16 個位元組對齊（適用于 ARM Neon、英特爾至 SSE4.1）。

當然，這一切都取決于這些資料的記憶體訪問模式，它現在具有更復雜的地址計算，但它也有機會使用 SIMD 進行搜索/替換。

轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/468449.html

標籤：C 表现内存对齐

上一篇：為什么當我定義和描述物件truck.drive()的方法時我的程式不起作用

下一篇：R在多個條件下從data.table中獲取價值的最快方法