錯誤的分配器實現

我有一個非常簡單的問題。我一直在鞭打一個非線程安全的分配器。分配器是一個相當簡單的內存競技場策略 - 分配一個大塊，將所有分配放入其中，對解除分配不做任何處理，在競技場銷燬時將其全部刪除。但是，實際上嘗試使用此方案會引發訪問衝突。錯誤的分配器實現

static const int MaxMemorySize = 80000; 
template <typename T> 
class LocalAllocator 
{ 
    public: 
     std::vector<char>* memory; 
     int* CurrentUsed; 
     typedef T value_type; 
     typedef value_type * pointer; 
     typedef const value_type * const_pointer; 
     typedef value_type & reference; 
     typedef const value_type & const_reference; 
     typedef std::size_t size_type; 
     typedef std::size_t difference_type; 

    template <typename U> struct rebind { typedef LocalAllocator<U> other; }; 

    template <typename U> 
    LocalAllocator(const LocalAllocator<U>& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    LocalAllocator(std::vector<char>* ptr, int* used) { 
     CurrentUsed = used; 
     memory = ptr; 
    } 
    template<typename U> LocalAllocator(LocalAllocator<U>&& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    pointer address(reference r) { return &r; } 
    const_pointer address(const_reference s) { return &r; } 
    size_type max_size() const { return MaxMemorySize; } 
    void construct(pointer ptr, value_type&& t) { new (ptr) T(std::move(t)); } 
    void construct(pointer ptr, const value_type & t) { new (ptr) T(t); } 
    void destroy(pointer ptr) { static_cast<T*>(ptr)->~T(); } 

    bool operator==(const LocalAllocator& other) const { return Memory == other.Memory; } 
    bool operator!=(const LocalAllocator&) const { return false; } 

    pointer allocate(size_type n) { 
     if (*CurrentUsed + (n * sizeof(T)) > MaxMemorySize) 
      throw std::bad_alloc(); 
     auto val = &(*memory)[*CurrentUsed]; 
     *CurrentUsed += (n * sizeof(T)); 
     return reinterpret_cast<pointer>(val); 
    } 
    pointer allocate(size_type n, pointer) { 
     return allocate(n); 
    } 
    void deallocate(pointer ptr, size_type n) {} 

    pointer allocate() { 
     return allocate(sizeof(T)); 
    } 
    void deallocate(pointer ptr) {} 
};

我已經初始化memory指向其調整到MaxMemorySize的矢量，並且我還初始化CurrentUsed指向一個int是零。我將這些值分配給std::unordered_map的構造函數，但它一直在STL內部拋出訪問衝突。有什麼建議麼？

編輯：這是我的用法：

std::vector<char> memory; 
int CurrentUsed = 0; 
memory.resize(80000); 
std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, LocalAllocator<std::pair<const int, int>>> dict(
    std::unordered_map<int, int>().bucket_count(), 
    std::hash<int>(), 
    std::equal_to<int>(), 
    LocalAllocator<std::pair<const int, int>>(&memory, &CurrentUsed) 
); 
// start timer 
QueryPerformanceCounter(&t1); 

for (int i=0;i<10000;i++) 
    dict[i]=i; // crash

編輯：該死。它在我將尺寸增加到1MB時起作用。我不得不將其增加到超過800,000字節，以使其在不投擲的情況下工作。

來源

2011-08-10 Puppy

這是這些新的有狀態分配器之一嗎？記錄在哪裏？ –

STL實現完全有可能還沒有真正實現有狀態分配器。另外，你使用了哪些STL實現，以及你得到了哪些錯誤？你如何在'std :: unordered_map'中使用它？ –

你如何測試這段代碼？在vc2010的unordered_map上它的簡單使用對我來說工作得很好。 – BCoates

當我測試這個代碼時，rebind被用來請求多個分配器對同一個內存塊。我把

cout << n << " " << sizeof(T) << " " << typeid(T).name() << endl;

在分配（SIZE_TYPE）的頂部，當我添加了三個元素到unordered_map了：

1 64 struct std::_List_nod<...> 
16 4 struct std::_List_iterator<...> 
1 64 struct std::_List_nod<...> 
1 64 struct std::_List_nod<...> 
1 64 struct std::_List_nod<...>

如果你的實現是不是巧合使用漂亮的一輪64個字節的請求，這類將返回錯配的分配。

來源

2011-08-10 22:19:17 BCoates

在索引它之前，我明確地去除引用指針。 – Puppy

所以你是。我在做錯操作的順序。用新理論取代答案。 – BCoates

未對齊的訪問在x64上不是錯誤 - 我添加了代碼來檢查並修復對齊而沒有任何效果。 – Puppy

對於小值類型，MSVC10的散列表類型只有很多空間開銷。它超出了你保留的空間量並拋出bad_alloc。

它實現爲list<value_t>，其中包含所有元素和一個散列桶vector<list<value_t>::iterator>，每個元素有2到16個插槽。

這是每個元素總共4到18個開銷指針。

標準可能需要像這樣的實現。與矢量不同，unordered_map要求元素一旦添加到容器中就不會移動。

來源

2011-11-06 09:03:25 BCoates

錯誤的分配器實現

回答

相關問題