Hiệu suất thấp từ unordered_map khi truy cập các phần tử trong hàm mẫu thành viên trong lớp dẫn xuất

Question

Tôi đang cố triển khai kiến ​​trúc dựa trên thành phần trên một dự án công cụ trò chơi. Mỗi GameObject có một số unordered_map chứa con trỏ đến Component lớp cơ sở. Tại thời điểm này, tôi chỉ có một lớp dẫn xuất thành phần, là lớp Transform. Tôi muốn triển khai cấu trúc dựa trên thành phần này tương tự như quy ước của Unity: Tôi muốn lấy một thành phần của đối tượng trò chơi bằng cách gọi hàm thành viên mẫu như GetComponent<Transform>().

Dưới đây là các tiêu đề:

Component.h

enum type{ 
    TRANSFORM // more will be added later 
}; 

class Component // base class 
{ 
public: 
    Component() : _owner(NULL) {} 
    virtual ~Component(){} 
    static type Type; 

protected: 
    GameObject* _owner; 
}; 

Transform.h

class Transform : public Component 
{ 
public: 
    Transform(); 
    ~Transform(); 
    static type Type; 

    void Rotate(float deg); 

    // to be encapsulated later on 
    Vector2D _position; 
    float _rotation; 
    Vector2D _scale; 
}; 

GameObject.h

class GameObject 
{ 
public: 
    GameObject(); 
    ~GameObject(); 

    void Update(); 
    //and more member functions 

    template<class T> 
    T* GetComponent(); 
private: 
    // some more private members 
    unordered_map<type, Component*> _componentList; // only 1 component of each type 
}; 

template<class T> 
T* GameObject::GetComponent() 
{  
    return static_cast<T*>(_componentList[T::Type]); 
} 

---

thực hiện ban đầu của tôi sử dụng std::vector để giữ Component* và ứng dụng chạy ở 60 fps (Tôi cũng có một bộ điều khiển tốc độ khung hình, mà chỉ giới hạn FPS đến 60). Khi tôi đổi thành unordered_map để truy cập vào các thành phần con trỏ đó, hiệu suất đã giảm xuống 15 FPS.

Tôi chỉ vẽ hai Quads và tôi chỉ gọi GetComponent<Transform>() 6 lần mỗi khung vào thời điểm này, do đó không được nhiều đang xảy ra trong bối cảnh đó.

---

Tôi đã thử gì?

Tôi cố gắng để sử dụng const char*, std::string, type_info và cuối cùng enum type như các giá trị quan trọng đối với các unordered_map nhưng không thực sự giúp: mọi cài đặt đã cho tôi 15-16 FPS.

Điều gì gây ra vấn đề về hiệu suất này? Làm thế nào tôi có thể cô lập vấn đề?

_{Tôi hy vọng tôi cung cấp đủ chi tiết, đừng ngần ngại hỏi cho mã hơn nếu cần thiết}

Answer 1

Disclaimer: trong khi các thông tin dưới đây sẽ tổ chức không phân biệt, việc kiểm tra sự tỉnh táo cơ bản đầu tiên được đưa ra một sự khác biệt mạnh mẽ như vậy trong hoạt động trên trường hợp đơn giản như vậy là trước tiên hãy đảm bảo rằng các tối ưu hóa xây dựng được bật. Với cách đó ...

unordered_map được thiết kế cuối cùng như một thùng chứa có quy mô khá lớn, nâng cấp một số lượng lớn các nhóm.

Xem ở đây: std::unordered_map very high memory usage

Và ở đây: How does C++ STL unordered_map resolve collisions?

Trong khi tính toán chỉ số băm là tầm thường, dung lượng bộ nhớ (và những bước tiến giữa) được truy cập cho ví dụ nhỏ unordered_maps có thể rất dễ dàng biến thành một nút cổ chai bị thiếu bộ nhớ cache với một cái gì đó như truy cập thường xuyên như lấy một giao diện thành phần ra khỏi một thực thể.

Đối với các hệ thống thành phần thực thể, thông thường bạn không có nhiều thành phần liên quan đến một thực thể - có thể giống như hàng tá và thường chỉ một vài. Kết quả là, std::vector thực sự là một cấu trúc phù hợp hơn và chủ yếu về mặt địa phương tham chiếu (các mảng nhỏ thường có thể được truy cập nhiều lần mỗi khi bạn lấy một giao diện thành phần ra khỏi thực thể). Trong khi một điểm thấp hơn, std::vector::operator[] cũng là một hàm được trivially-inlined.

Nếu bạn muốn làm thậm chí tốt hơn so với std::vector đây (nhưng tôi chỉ khuyên như vậy sau khi hồ sơ và xác định bạn cần nó), với điều kiện bạn có thể suy ra một số trường hợp phổ biến trên ràng buộc, N, cho số lượng các thành phần thường có sẵn trong một thực thể, một cái gì đó như thế này có thể làm việc thậm chí tốt hơn:

struct ComponentList 
{ 
    Component* components[N]; 
    Component** ptr; 
    int num; 
}; 

Bắt đầu tắt bằng cách thiết lập ptr để components và truy cập chúng sau đó thông qua ptr. Chèn thành phần mới sẽ tăng num. Khi num >= 4 (trường hợp hiếm hoi), hãy thay đổi ptr để trỏ đến khối được phân bổ động với kích thước lớn hơn. Khi hủy ComponentList, hãy giải phóng bộ nhớ được phân bổ động nếu ptr != components. Điều này lãng phí một ít bộ nhớ nếu bạn lưu trữ ít hơn N các phần tử (mặc dù std::vector cũng thường thực hiện điều này với công suất ban đầu và cách nó phát triển), nhưng nó biến thực thể của bạn và danh sách thành phần được cung cấp thành cấu trúc liền kề trừ khi num > N. Kết quả là, bạn có được vị trí tốt nhất để tham khảo và có thể có kết quả tốt hơn so với những gì bạn đã bắt đầu (tôi giả định từ việc giảm đáng kể tốc độ khung hình mà bạn đã tìm nạp thành phần ra khỏi các thực thể thường xuyên ra khỏi các vòng không phải là không phổ biến trong ECS).

Do tần suất giao diện thành phần có thể được truy cập từ một thực thể và rất thường xuyên trong các vòng rất chặt chẽ, điều này có thể đáng để thử.

Tuy nhiên, lựa chọn ban đầu của bạn là std::vector thực sự là một lựa chọn tốt hơn cho quy mô dữ liệu điển hình (số lượng thành phần có sẵn trong thực thể). Với các tập dữ liệu rất nhỏ, các tìm kiếm tuần tự tuyến tính cơ bản thường làm tốt hơn các cấu trúc dữ liệu tinh vi hơn, và bạn thường muốn tập trung nhiều hơn vào hiệu quả bộ nhớ/bộ nhớ cache.

Tôi cố gắng để sử dụng const char *, std :: string, type_info và cuối cùng enum loại như các giá trị quan trọng đối với các unordered_map nhưng không thực sự giúp: tất cả triển khai đã cho tôi 15-16 FPS.

Chỉ trên ghi chú này, đối với các khóa bạn muốn cái gì đó có thể so sánh trong thời gian không đổi như giá trị tích phân.Một khả năng có thể hữu ích trong trường hợp này là chuỗi nội bộ chỉ lưu trữ int để cân bằng giữa tính tiện lợi và hiệu suất (cho phép khách hàng xây dựng chúng thông qua string nhưng so sánh chúng thông qua int trong khi tra cứu thành phần).