Sign in to follow this  
JoshuaWaring

Low Level Memory Management C++

Recommended Posts

JoshuaWaring    1359

I'm trying to create a ArrayList which initializes on demand instead of on construction. My previous implementation would initialize all objects including ones which were reserved for future push's but wastefully initialized.

 

I've got the creation working perfectly, the only issue I'm having is with the deletion, Is there a way to deconstruction a section of an array without deallocation and then deallocation of the whole array without deconstruction?

Share this post


Link to post
Share on other sites
Brother Bob    10344

If you're asking how to recreate std::vector with separate memory allocations and object constructions, then you'll do the following:

  1. Allocate memory with the operator new() or malloc() function.
  2. Construct individual objects with placement new.
  3. Destruct objects by calling their destructor.
  4. Release memory with the operator delete() or free() function.

If you're specifically asking about point 3, then destroying an object is as simple as calling the ~T() member function on it (replace T with the class name, or template type parameter you use). Look here for some example memory management: clicky.

Edited by Brother Bob

Share this post


Link to post
Share on other sites
JoshuaWaring    1359

The problem is specifically step 4, the delete[] will call the destructor, even when the object hasn't been initialized with the placement new.

As of right now I've got the manual call of the destructor, but deallocation without destruction is still an issue.

 

ptr = new (sizeof(T) * 5);

new (ptr) T();

&ptr[0]->~T();

delete[] ptr; // Calls the destructor on invalid objects

 

I've just tried casting the ptr to a char* and deleting that, but that throws a heap corruption exception. (Was hoping that the delete worked in bytes and wouldn't care)

Edited by Joshhua5

Share this post


Link to post
Share on other sites
JoshuaWaring    1359

If you delete a section of the array without freeing it's memory how are it's pointers tracked? If you stop tracking the elements you will get a memory leak which is bad.

Doesn't std::list already function how you like, could you derive or compose based on it instead?

 

Destructor's are called on objects, the problem stems from the array not being composed of only initialized objects.

Share this post


Link to post
Share on other sites
Brother Bob    10344

You're doing memory allocations with the new and delete operators, not the operator new() and operator delete() functions as I mentioned. Observe the difference in terminology: the new operator is the operator that allocates memory and constructs objects, while the function operator new() is the function used to allocate the memory.

ptr = operator new(sizeof(T) * 5);
new (ptr) T();
&ptr[0]->~T();
operator delete(ptr);

The function operator new() doesn't take any type to allocate because it doesn't work with types and constructed objects, as opposed to the new operator that has to know what type to allocate and construct.

Edited by Brother Bob

Share this post


Link to post
Share on other sites
SeanMiddleditch    17565
What are you actually trying to do?

What you're asking about has problems; they can be solved, but I'm just left asking myself, "why?" The thing you say you're trying to create sounds like a terrifyingly bad idea. Automagic initialization of vector elements is just asking for a serious pile of maintenance and performance problems.

It kinda maybe sounds like you maybe need a sparse array or maybe a stable vector or maybe are just looking for a free list, but I can't tell.

--

So far as your actual question, you'll have to keep track of which elements in your array are constructed or not. When you're about to free memory, walk the list of objects that are constructed and call their destructor. Then deallocate the memory. You should use the C++ allocator model for allocations and deallocations and never call new, new[], delete, or delete[], unless you _really really_ have to (and you don't).

An option is to keep a parallel array of bits that you can iterate over and check to see which items are allocated. Something like:
 
template <typename T, typename A = std::allocator<T>>
class sparse_array
{
  std::vector<std::aligned_union<0, T>::type, A> _data;
  bit_vector<std::allocator_traits<A>::rebind_alloc<char>> _used;

public:
  template <typename U>
  void insert(siz_t index, U&& value)
  {
    if (index == _used.size())
    {
      _data.emplace_back();
      _used.push_back(false);
    }
    assert(!_used[index]);
    _used[index] = true;
    _data.get_allocator().construct(&data[index], std::forward<U>(value));
  }

  template <typename U>
  void push_back(U&& value)
  {
    auto index = _used.find_index(false);
    insert(index, std::forward<U>(value));
  }

  T& operator[](size_t index)
  {
    assert(index < _used.size() && _used[index]);
    return reinterpret_cast<T const&>(data[index]);
  }

  void clear()
  {
    for (size_t i = 0; i != _used.size(); ++i)
    {
      if (_used[i])
      {
        _data.get_allocator().destroy(reinterpret_cast<T*>(&_data[i]));
        _used[i] = false;
      }
    }
  }  

  ~sparse_array() { clear(); }

  sparse_array& operator=(sparse_array const& rhs); // check this!=&rhs, then clear(), then copy
  sparse_array& operator=(sparse_array&& rhs); // check this!=&rhs, then clear(), then move

  // ...
};
You'll need to find a bit_vector (there ones many online) or just use std::vector<bool> (shudder) - and of course learn how to rebind the allocator to it - but that's the gist.

You should also be sure to make the container fully conforming to the C++ container requirements (mostly by forwarding functions and type alises to the internal vector).

--

You also seem to have an important misunderstanding of how the C++ allocation operators work (the ones I just said you shouldn't use, and this is partly why):
 
ptr = new (sizeof(T) * 5);
new (ptr) T();
&ptr[0]->~T();
delete[] ptr; // Calls the destructor on invalid objects
Your error is that you're allocating with new but freeing with delete[]. You MUST pair new with delete and new[] with delete[], always. If you used C++ allocators, you'd use allocator_traits<Allocator>::allocate and ::deallocate to acquire and release memory, allocator_traits<Allocator>::construct and ::destroy to invoke the constructor and destructor when needed.

This model avoids the nastiness of new and delete, makes your code easier to audit for bugs, and allows users of your class to supply custom allocators which is a _very_ frequent requirement in games (many games mandate that the default allocator - including new/delete/malloc/free - can never ever be used; not just replaced with something else, but never used).

If all you're doing is storing an array and doing your own tracking of lifetime, just use std::vector over something like std::aligned_union<0, T>::type; then you can explicitly construct or destruct items in the vector but the memory is managed intelligently for you with full allocator support.

Share this post


Link to post
Share on other sites
rip-off    10979
Your smart_array assignment operators appear to be incorrect, it doesn't decrement the reference count of the current object (if any). Also, I think it is surprising and not advisable to support arbitrary pointer identity comparison. I'd recommend instead having an explicit member function if this is actually required. The detach member function seems poorly designed, it doesn't guarantee ownership transfer (as other references may still exist), so the client cannot safely assume ownership of the returned pointer.

As for the ArrayList, the class is certainly not thread safe. Generally, it is really hard to provide thread safety at such a low level, as most client code will need to make multiple calls to the object to achieve many tasks. If you wish to provide a thread safe collection, I'd recommend a separate class (possibly making using of this class, or std::vector<> internally) with a limited, "transactional" oriented interface. The limited interface makes it easier to validate the thread safety. In addition, you are using a mixture of low and high level thread primitives, I'd recommend picking one (e.g. mutex locking) and using it consistently (e.g. the entry point to every public member function).

Other than that, I find many of the member functions to be very surprising. For example, the difference between size() and count() is very subtle and I would say unnecessarily error prone. The behaviour of resize() is bizarre, it does nothing if the array is smaller than specified, otherwise it expands the array by the number of elements passed.

In any case, one issue is that the smart_array assumes it can delete[] the pointer it manages, but the wrapping ArrayList is giving it pointers that were not allocated with new[].

Overall, I find the classes a confusing mix of thread-safety, reference counting, memory management and dynamic array logic. As mentioned above, the first thing I would recommend is removing the thread safety from the equation. You can write a thread-safe wrapper for this later - if it is really required! Ideally, you try not to share objects between threads when you can avoid it, the only objects that should be shared are thread-oriented things like work queues for producer / consumer relationships. I'd also recommend dropping the reference counting, again if required this can be handled at a higher level.

Once you've dropped these, then it becomes clear that you're essentially re-implementing std::vector. Consider not doing that, but instead using the tried and tested implementation. You can then wrap something like that in a thread safe interface, if that is really something your program requires.

Share this post


Link to post
Share on other sites
JoshuaWaring    1359
The ArrayList is still a work in progress and a lot will be changed in time.
The smart_array should update the references correctly in the call to destroy() (edit: I see where you mean), although I'm going to remove the smart_array since its purpose is invalid since changing how memory is initialized.

Resize hasn't been reworked yet although it does nothing because to be smaller that m_size would cull objects.

Thread safety is also in progress, although I agree that thread safety should be optional and I've been thinking about it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this