如何設計適合數百萬分配的類？

Question

如果我想分配一個類的數百萬個對象Foo，並且我希望內存和時間有效，那麼我應該如何設計Foo類？

顯然，Foo不應包含太多的成員數據。

此外，我猜，它不應該使用虛擬功能？

Foo從基類派生的代價是多少？並從幾個基類？

是否有任何其他提示使數百萬個Foo對象非常有效？

Answer 1

看看Flyweight pattern。儘管如此，GoF book在解釋模式方面比維基百科做得好得多。

Answer 2

我認爲關於爲數百萬分配設計你的班級沒什麼好說的。是的，存在明顯的內存限制，所以如果你有一個固定的內存量，這可能是你真正關心的問題，否則你將永遠面臨內存不足的風險。指向虛擬表的指針就是這樣的一個指針（32或64位體系結構上的4或8個字節），不確定這是多重繼承的情況。調用虛擬函數會產生虛擬查找的開銷（如果最近沒有使用它，還會產生額外的緩存未命中），但僅限於虛擬函數，並且它們可能永遠不會被內聯。

如果有很多重複的值，您可能還需要考慮具有單獨的數據結構（flyweight模式）。爲了提高效率，確保你有一個輕量級的（內聯）構造函數和賦值操作符，特別是如果你打算使用stl向量和類似的。

這些都是很簡單的東西，所以現在我真正的建議：

什麼是真的要殺死你的內存管理，如果你得到碎片，在那裏你會突然有一大堆的內存，但仍然無處可放你的物體（沒有足夠的連續空間）。如果你有很多交錯分配，這可能會成爲一個真正的問題，所以你可能想要考慮分配大塊對象，將它們保存在一個池中並重用。或者使用自定義分配器（新運算符），在該分配器中預分配一個內存塊，該內存塊是對象大小的倍數，並將其用於對象。

Answer 3

如果一個對象可以說是高效的，那麼它應該是很小的，如果創建了一個批次，並且在進行大量調用時它的通用操作應該是可以嵌套的。就內存而言，虛擬函數通常爲每個對象第一個對象花費4或8字節（指針的大小），此後免費。正如其他人所說，如果包含可共享的重複數據，則Flyweight是使對象變小的一種方式。如果您的數百萬個對象不包含重複數據，請將其忽略。

更恰當的是它是高效或低效的代碼。虛擬呼叫可能會花費一些呼叫開銷，但這取決於調用代碼，而不是類，每個成員函數被調用多少次。在任何情況下，內聯都是大幅增長的地方，而虛擬功能只是妨礙內聯受益的特定呼叫站點的一種方式。如果您的設計通過27個虛擬成員函數進行簡化，每個函數每個月調用一次，但確保每秒調用數百萬次的2個函數可以由調用方內聯，則不需要避免虛擬函數。

基類的成本幾乎相同的相同類型的一個成員對象。有了多重繼承，static_cast可能不再是一個無操作，因爲它通常用於單一繼承，但這可能不值得擔心。虛擬繼承和dynamic_cast都可以在運行時完成的工作量方面感興趣，但僅在與虛擬成員函數類似的規模上纔有意義。

所有這一切說，你想要做的主要事情是儘快能合理模仿對象的創建和呼叫特徵已完成的代碼會得到一些代碼運行。然後你就會知道你在看什麼樣的性能 - 如果你的關鍵操作在虛擬功能上出現或多或少的速度，那麼爲了避免它們出現一些扭曲的設計方案是毫無意義的。如果你的分析器告訴你所有的時間都是用來創建對象的，但是一旦你擁有了它們就不會使用它們，那麼你需要考慮分配而不是成員函數。

之所以獲得一個估計早期就是這樣，你不想浪費時間設計的東西，肯定是行不通的。所以基本的基準測試（「我可以每秒撥打new一千次，每秒撥一百萬次嗎？就像多線程同時執行一樣快）」可以反饋到設計過程中，但是當然，直到您有一個你的實際代碼的似是而非的版本。

Answer 4

最主要的是，重新使用他們通過保持所使用的對象池中，並儘量減少使用new和delete。不要擔心虛擬功能。調用它們的開銷通常相對於程序中發生的其他任何事情都是微不足道的。

Answer 5

只是澄清自定義分配器上的一點。

使用默認的new，您可能會獲得相當多的開銷，即分配在sizeof(Foo)之上的額外內存。你真正想要發生的是將這個開銷分攤到許多Foos。

的想法是爲執行一個呼叫到new分配足夠大的字節的單個塊連續Foo S的保持100的或1000（或更多？），然後分配單Foo出去了這一點。

如果您保留一個預先分配的Foo s池，即使其更快，您仍可能在每個實例上都承受內存開銷。

在C++ pl2e，約「我的機器上」字節Stroustrup的談判，所以你必須自己做實驗：實際上是多少內存佔用分配一個Foo與new？

查找池分配器（例如Boost）或小對象分配器（例如Loki）。

Answer 6

關於類對象的分配，請看一下boost Pool庫，對於許多小對象分配而言，這可能比通過系統分配器進行的常規新/刪除操作更高效。它也可能讓它們在記憶中更接近。 fast_pool_allocator作爲C++分配器實現非常方便，您可以輕鬆地將其放入應用程序以評估其優勢。無論如何，我建議使用分配器，因爲它可以更容易地比較不同的分配方案。

另一件需要考慮的事情是什麼時候要創建對象 - 例如，您是否事先知道需要多少人（並且因此其他人描述的共用/重用系統會有用），或者你是否知道在不同的點上需要O（1m）。一次性創建大量數據應比分別分配大量數據快得多。從我自己的工作中，我經常發現爲許多小對象重複分配內存會成爲分析中的一大瓶頸。

我會建議搭建一個測試應用程序，它將模擬您需要的分配數量並對不同策略進行基準測試。您可能需要合併多個。

Answer 7

其他人提到了Flyweight模式，但是因爲您爲C++標記了這個標籤，我會考慮Boost.Flyweight。它的設計符合您的需求，如果您需要重新發明輪子，您可以隨時查看其詳細信息。

Answer 8

爲了什麼值得...你也可以從使用另一個成語中獲益。

我知道Flyweight模式是相當的憤怒，但在這裏你也可以從沒有分配這些數以百萬計的對象中受益。

如果看起來很奇怪，請考慮Python中的String對象。如在許多最近的語言中，String在Python中是不可變的。當然，你操作的對象可以改變，但真正的String不會：你的句柄只是重新定位。

當然，Python有自動垃圾回收，這使得它更容易，但它也可以爲你工作。這裏是一個草圖：

class FooImpl; 

class Foo 
{ 
public: 
    explicit Foo(int i): mImpl(FooImpl::Build(i)) {} 

    int foo() const { return mImpl->foo(); } 

    void foo(int i) { mImpl = mImpl->foo(i); } 

private: 
    const FooImpl* mImpl; 
}; // class Foo 

class FooImpl 
{ 
public: 
    static const FooImpl* Build(int i) 
    { 
    typedef std::unordered_set<FooImpl> foos_type; 
    FooImpl tmp(i); 
    foos_type::iterator it = gFooImplCollection.insert(tmp); 
    return &(*it); 
    } 

    int foo() const { return mFoo; } 

    const FooImpl* foo(int i) const 
    { 
    return Build(i); 
    } 

    // Useful thingy 
    bool operator==(const FooImpl& rhs) const { return mFoo == rhs.mFoo; } 
    size_t hash() const { return mFoo; } 

private: 
    explicit FooImpl(int i): mFoo(i) {} 

    int mFoo; 
}; 

std::unordered_set<FooImpl> gFooImplCollection; 

當然，這是非常粗糙，只給你一個想法。如果不同項目的潛在數量很重要，則需要垃圾收集。垃圾收集是另一個話題，我傾向於給你留下一個核心類的概念（只公開const方法）和一個可變的句柄（它簡單地改變了它在被要求改變時指向的核心類）。

而現在，你已經採取了讀取時間，加速了它：Boost.Flyweight :)

注：

這似乎是準確的重要，因爲Foo應該被分配（上堆棧）數百萬次，其大小應該儘可能接近指針。這是通過使用Intrusive參考couting（我希望這是什麼Boost）來完成的。另外，在Foo,virtual爲FooImpl和Build可能實際上在幕後調用AbstractFactory沒有必要有virtual方法。

因此，由於Foo：

• 沒有任何基礎類
• 沒有任何虛擬方法
• 僅具有一個屬性（指針）

其有效尺寸將是指針的大小...這是最好的，你可以希望如果你不想存儲一個ID在每次電話會議費用查找費用:)