2 hours ago, lawnjelly said:

The point of your handles is presumably to deal with a block of memory that may be relocatable.

Yes!

Quote

As far as I can see if you want to use a standard vector you either need to:

• Override the mechanism for determining the start of the vector array to go through the handle each time it is accessed (pretty inefficient) or
• Update the start of array pointer in the vector on relocating the memory (and watch for dangling pointers)

Yes! Good analysis of where this is going though specific to vector, which I agree.

Quote

Afaik, underneath it all, although the implementation isn't specified, a vector is typically just a fancy dynamic array. If you want the vector to use your handle you would presumably have to provide it with the array address, either on the fly, or when it changes (preferable).

Yes, so far I agree.

Quote

It may be an idea to write your own template wrapper if you intend to bandit an STL implementation, to emphasise it is working differently under the hood (as relocatable code may break the 'expected contract').

This I don't understand a bit. Template wrapper as in, I concretely wrap the vector?

Quote

I must say I still strongly suspect this is something that could be achieved much better with a different paradigm, however, without knowing the details we can only answer what you have asked directly.

Okay just trying to summarize, please correct me if I misinterpret. So according to you, it's impossible to sneak my object handle in through the custom STL allocator in any way unless I forge the STL implementation to work for my will, in case I'm still holding up with the paradigm of this relocatable memory for such things.

So up to this point I conclude that it is impossible, with the case I gave, to provide a custom STL allocator through the indirect memory access (the object handle)?

1 hour ago, lawnjelly said:

Actually thinking about it you may be able to force an allocation through your relocation code without modifying the STL code .. by clever use of reserve and resize. Depends on the STL implementation though and how it is about shrinking vectors.

i.e. You want to move array from A to B, array size is 10, max size is 16.

resize(10) according to this (http://www.cplusplus.com/reference/vector/vector/resize/) should result in reallocation enabling you to relocate in your custom allocator.

In the case where array size == max size, you might need to force an allocation with a resize(11) then delete the last element .. which might be costly depending on the object. There may be a better way, just an idea.

I get your idea I think, but in general this does not matter. If the vector chunk shrinks/grows due to resize, then what it does is, as you said (also according to the "Complexity" section in the link you gave), the chunk should be "updated" with new size info (as in capacity) where it means that it is reallocated to a new chunk with new size. In short basically it performs allocation/deallocation (if it will depending on the conditions). This is what this thread is about; I want my memory allocator to capture this moment, which I think (so far) should be done by intercepting the default allocator using custom STL allocator and inject it with my memory allocator that handing object handle, which as you see in the picture, I couldn't able to.

If you see figure 2 in my picture, there's an unused block (colored in grey). Whenever the vector grows beyond its current capacity or do what you proposed due to resize, if it uses the custom memory allocation I provided, the vector array will abandon its position 0x00 (a.k.a deallocate) and then "move to" (a.k.a allocate new chunk to) the unused block, whether with bigger size array or resized smaller array. It will be given a new object handle upon allocation. The abandoned (freed) 0x00 will be defragmented sometime later. This keeps going on the same with other objects too whenever there's any allocation/deallocation. So in short it should be done automatically anyway, again, if the STL allocator is successfully customized with my memory allocator with the object handle thingy.

18 minutes ago, Zakwayda said:

@mychii: Thanks for the helpful diagram.

You're welcome. I've been trying my best to ensure it's easier to get to the point.

18 minutes ago, Zakwayda said:

For me at least, the missing piece of the puzzle was that I didn't realize you wanted entire blocks of array memory to be relocatable (I thought that in some way you wanted to store multiple relocatable objects in the array, which I couldn't make sense of).

I actually just realized what you thought about after I posted mine, that you probably thought "object" as in per element. So I quickly put a lot of edits on the second quote of my last response to make sure that wasn't the case. I'm glad the picture quite hopefully explained more than words (I should've done this earlier!)

18 minutes ago, Zakwayda said:

It's always possible I'm wrong, but I'm going to go out on a limb and say that I think it's unlikely there's a portable, reliable way to relocate the storage for (e.g.) a std::vector instance. (I'm happy to be corrected though.) If I'm right about that, then it seems like a custom container might be an appropriate solution.

So I guess it gets to this point after all. I'd love to to discuss about how I shouldn't (or I should) get to this point ( like what Fulcrum.013 seem to be very interested to discuss more than the question itself), but I guess I'll just open a new thread for it later when it doesn't work in the end when it scales. It's just so far I haven't found any real problem (yet) with my current way of doing it except this exact question.

18 minutes ago, Zakwayda said:

lawnjelly's idea about forcing reallocations is interesting, but as he mentions the behavior would likely be implementation-dependent. In any case, I certainly wouldn't be comfortable relying on something like that.

Yes the idea is interesting but the implementation could be done automatically if only the indirect memory access (the object handle) can work along with the custom STL allocator.

12 minutes ago, mychii said:

This I don't understand a bit. Template wrapper as in, I concretely wrap the vector?

At least give it a different name / namespace, so if you later or someone else reads your code they will realise there is something dodgy going on. e.g. my::relocatable_vector instead of std::vector.

15 minutes ago, mychii said:

So up to this point I conclude that it is impossible, with the case I gave, to provide a custom STL allocator through the indirect memory access (the object handle)?

Well, afaik STL allocator is expecting a memory location, not a handle. Unless you can overload the [] operators for the handle to make it appear like a normal array, but I somewhat doubt this would work, depending on the STL implementation, because it probably uses things like memcpy memmove etc rather than relying on [] for access.

If you want to do this directly with a handle, I would write your own vector. You could use an existing one as a 'template' (pardon the pun) if you don't feel up to it, then just change the relevant bits to use a handle. It will probably have pretty bad performance though.

33 minutes ago, lawnjelly said:

At least give it a different name / namespace, so if you later or someone else reads your code they will realise there is something dodgy going on. e.g. my::relocatable_vector instead of std::vector.

Oh I see.

33 minutes ago, lawnjelly said:

Well, afaik STL allocator is expecting a memory location, not a handle.

I have to admit that yes, it expects a memory location and that's it.

33 minutes ago, lawnjelly said:

Unless you can overload the [] operators for the handle to make it appear like a normal array, but I somewhat doubt this would work, depending on the STL implementation, because it probably uses things like memcpy memmove etc rather than relying on [] for access.

Yeah I doubt it too. It's more about being too hacky and too specific if I do that, maybe, haha. Just wanna do either the legal one like replacing the default allocator or make my own.

33 minutes ago, lawnjelly said:

If you want to do this directly with a handle, I would write your own vector. You could use an existing one as a 'template' (pardon the pun) if you don't feel up to it, then just change the relevant bits to use a handle. It will probably have pretty bad performance though.

Yeah I'm trying to avoid more overhead just to make that work. I guess I'm set to just carry on with making my own containers.

Thanks everyone!

1 hour ago, mychii said:

If you see figure 2 in my picture, there's an unused block (colored in grey).

And what about green area on diagram. What it mean? Is it a just a plain memory or a big buffer allocated using heap menager? In first case it can not work becouse to move block you have to deal with heap manager that you have no other way to communicate then malloc/free (or new/delete that usually done as wtaps around malloc/free). In second case you just try to reinvent C# heap manager on C++ that is wrong idea for C++ becouse C++ dont use a heap to simulate stack instead of C# and other managed garbage.

1 hour ago, mychii said:

This I don't understand a bit. Template wrapper as in, I concretely wrap the vector?

I guess it impossible to do just wrapping vector or providing a custom allocator. Just look to diagram how vector implemented inside.

Light green area is a static part of vector, something like a handle that live on stack/object where vector difined.  Green is a heap where buffer is allocated. Blue is other memory where code that uses vector store requested from vector iterators that as fact just a pointers inside a buffer. So to move buffer you have to uppdate MyFirst and MyLast members of vector that is private, and update a all iterators to keep it alive, or synchronize defragmentation with code that used vector to have warranty that it no alive iterators exists on start of defragmentation operation.

Now why it impossible to do using just a custom allocator without remaking of vector. Vector use allocator  to  allocate a new buffer and deallocate a old buffer on resizes and store received from allocator pointer on its static header (handle), updating a Capacity. So requesting of pointer to new location initiated by vector, but not by allocator. Vector just have no interface to update pointers in static part by request of allocator. And structure of static part is implementation defined (i just drow a minimal required set on diagram). So it no way to update static header of vector using a allocator only.

Also it no any sence to eliminate a reserved space. On each growth vector try to grab no less than 1.5 of it previous size to have a amortizated O(1) pushback and minimize a reallocations and as result fragmentations.

So good idea is to reserve for long-live vectors as many as may be required space on start of simulation and avoid a reallocations and at  result fragmentation of heap at all.

As result short-life vector not mixed with long life, so it not make a gap in heap structure after deallocation. Also fragmentation was a problem on older versions of C memory manager where allocated block still a block after deallocation. So multiple allocations/deallocations has make a continious set of tiny free bloks that can not be used to allocate a bigger buffer ever in case it can fit in total size of consequtive free blocs. Modern C++ memory managers have no it problem becouse able to join a consequtive free blocks in one big block on deallocation. So it have no problem with fragmentation.

Also any vector itself is a chache and memmove friendly as much as it applicable to its elements. So defragmentation of heap used by managed languages just for other purposes that not applicable to C++ and realtime software at all, and not related to chache friendly and so on.

Also areas that you marked by blue on your first diagram for default C++ heap manager is a gray-colored as ready for allocation. And say more it stay first in queque for allocation. it why heap called "heap"  - early dynamic memory managers has used a heap structure for prioritized queque to allocate a space from a smallest possible block first. Managed language using a dynamic memory to simulate a stack, so require a extremally fast new operation that just cut a piece from latest huge block that is O(1)  (but it much slover than use a hardware stack),instead of O(log n) search of  heap for smallest block . As drawback with time it have a run out of non-fragmentated memory so forced to initiate GC and defragmentation, that much compleхive than immidiatle heap allocation/deallocation totally, and have a so huge cost, so any "soft" realtime managed code developed around techniques that avoid to use GC and defragmentation. It achieved by reserving a long-life space enought for maximum possible quantity of elements for equalents of vectorat on start of system and avoid dealocations and as result GC and defragmentation at all, but by the way it disallow to use a temporary instances of classes that can not be placed on stack unlike C++ that allow to use a fast stack for temporary fixes-size data and as result just require to allocate/deallocate heap much rare, but trik with reserving long-life space still work.

This isn't a problem to be solved by the allocator. With the appropriate handle semantics, I don't see any reason why this shouldn't be possible:

class IObject
{
public:
    virtual void Bind(IObjectHandle* handle) = 0;
    virtual void Unbind(IObjectHandle* handle) = 0;
};

class IObjectHandle
{
public:
    virtual void Rebind(IObject* object) = 0;
};

class Object : public IObject
{
    std::set<IObjectHandle*> m_handles;

public:
    Object(const Object&)
    {
    }

    Object(Object&& other)
    {
        m_handles = std::move(other.m_handles);
        for (auto&& handle : m_handles)
        {
            handle->Rebind(this);
        }
    }

    ~Object()
    {
        assert(m_handles.empty());
        for (auto&& handle : m_handles)
        {
            handle->Rebind(nullptr);
        }
    }

    Object& operator=(const Object&)
    {
        return *this;
    }

    Object& operator=(Object&& other)
    {
        m_handles = std::move(other.m_handles);
        for (auto&& handle : m_handles)
        {
            handle->Rebind(this);
        }
        return *this;
    }

    void BindHandle(IObjectHandle* handle) override
    {
        m_handles.insert(handle);
    }

    void UnbindHandle(IObjectHandle* handle) override
    {
        m_handles.erase(handle);
    }
};

class ObjectHandle : public IObjectHandle
{
    IObject* m_object = nullptr;

public:
    ObjectHandle(const ObjectHandle& other)
    {
        m_object = other.m_object;
        if (m_object)
        {
            m_object->BindHandle(this);
        }
    }

    ObjectHandle(ObjectHandle&& other)
    {
        if (other.m_object)
        {
            other.m_object->UnbindHandle(&other);
            other.m_object = nullptr;
        }
        m_object = other.m_object;
        if (m_object)
        {
            m_object->BindHandle(this);
        }
    }

    ObjectHandle(IObject* object)
    {
        m_object = object;
        if (m_object)
        {
            m_object->BindHandle(this);
        }
    }

    ~ObjectHandle()
    {
        if (m_object)
        {
            m_object->UnbindHandle(this);
        }
    }

    ObjectHandle& operator=(ObjectHandle handle)
    {
        handle.swap(*this);
        return *this;
    }

    void RebindObject(IObject* object) override
    {
        m_object = object;
    }

    operator bool() const
    {
        return m_object != nullptr;
    }

    IObject* operator->() const
    {
        return m_object;
    }

    IObject& operator*()
    {
        return *m_object;
    }

    const IObject& operator*() const
    {
        return *m_object;
    }

    void swap(ObjectHandle& other)
    {
        if (&other != this)
        {
            if (m_object) m_object->UnbindHandle(this);
            if (other.m_object) other.m_object->UnbindHandle(&other);

            using std::swap;
            swap(m_object, other.m_object);

            if (m_object) m_object->BindHandle(this);
            if (other.m_object) other.m_object->BindHandle(&other);
        }
    }
};

Note that most of the heavy lifting happens as part of the move and swap semantics. The copy semantics of the object are also stubbed out, since handles are uniquely bound to a single object.

However I also have to question why this is needed in the first place. If fragmentation is a real concern, it's usually a symptom of another problem like sub-optimal allocation strategies or memory usage patterns.

On 10/6/2018 at 3:09 AM, Zipster said:

This isn't a problem to be solved by the allocator. With the appropriate handle semantics, I don't see any reason why this shouldn't be possible:

class IObject
{
public:
    virtual void Bind(IObjectHandle* handle) = 0;
    virtual void Unbind(IObjectHandle* handle) = 0;
};

class IObjectHandle
{
public:
    virtual void Rebind(IObject* object) = 0;
};

class Object : public IObject
{
    std::set<IObjectHandle*> m_handles;

public:
    Object(const Object&)
    {
    }

    Object(Object&& other)
    {
        m_handles = std::move(other.m_handles);
        for (auto&& handle : m_handles)
        {
            handle->Rebind(this);
        }
    }

    ~Object()
    {
        assert(m_handles.empty());
        for (auto&& handle : m_handles)
        {
            handle->Rebind(nullptr);
        }
    }

    Object& operator=(const Object&)
    {
        return *this;
    }

    Object& operator=(Object&& other)
    {
        m_handles = std::move(other.m_handles);
        for (auto&& handle : m_handles)
        {
            handle->Rebind(this);
        }
        return *this;
    }

    void BindHandle(IObjectHandle* handle) override
    {
        m_handles.insert(handle);
    }

    void UnbindHandle(IObjectHandle* handle) override
    {
        m_handles.erase(handle);
    }
};

class ObjectHandle : public IObjectHandle
{
    IObject* m_object = nullptr;

public:
    ObjectHandle(const ObjectHandle& other)
    {
        m_object = other.m_object;
        if (m_object)
        {
            m_object->BindHandle(this);
        }
    }

    ObjectHandle(ObjectHandle&& other)
    {
        if (other.m_object)
        {
            other.m_object->UnbindHandle(&other);
            other.m_object = nullptr;
        }
        m_object = other.m_object;
        if (m_object)
        {
            m_object->BindHandle(this);
        }
    }

    ObjectHandle(IObject* object)
    {
        m_object = object;
        if (m_object)
        {
            m_object->BindHandle(this);
        }
    }

    ~ObjectHandle()
    {
        if (m_object)
        {
            m_object->UnbindHandle(this);
        }
    }

    ObjectHandle& operator=(ObjectHandle handle)
    {
        handle.swap(*this);
        return *this;
    }

    void RebindObject(IObject* object) override
    {
        m_object = object;
    }

    operator bool() const
    {
        return m_object != nullptr;
    }

    IObject* operator->() const
    {
        return m_object;
    }

    IObject& operator*()
    {
        return *m_object;
    }

    const IObject& operator*() const
    {
        return *m_object;
    }

    void swap(ObjectHandle& other)
    {
        if (&other != this)
        {
            if (m_object) m_object->UnbindHandle(this);
            if (other.m_object) other.m_object->UnbindHandle(&other);

            using std::swap;
            swap(m_object, other.m_object);

            if (m_object) m_object->BindHandle(this);
            if (other.m_object) other.m_object->BindHandle(&other);
        }
    }
};

Note that most of the heavy lifting happens as part of the move and swap semantics. The copy semantics of the object are also stubbed out, since handles are uniquely bound to a single object.

However I also have to question why this is needed in the first place. If fragmentation is a real concern, it's usually a symptom of another problem like sub-optimal allocation strategies or memory usage patterns.

Sorry for the late reply, thanks for the effort of the code. Sorry I don't quite understand, if it isn't solved by the allocator, so how does this work for? I actually wrap the object handle in form of smart pointers (and soon the custom containers as well) quite similar like this. Is that what you mean?

Fragmentation isn't a real concern, the way I do it is just a gc technique which anyone can replace with any other technique they wishes to (that's why I'm so lazy to debate about it as there is no single answer), but what I'm asking right now is one of technique I do that leads to this, the only one that couldn't be integrated to STL containers, somehow.

My main concern was ease of usage. It is meant for high level codes such as gameplay codes, where users don't/expected to not care much about memory management and just produce features. It's a C# kind of thing (which I don't know, where some people kinda allergic about when they hear "managed, garbage-collected code", when I believe it is necessary in such particular issue, but AGAIN this is a different matter to debate about). It's in C++ cause if the users want to do something outside of the managed environment, they can, like allocating their own memory and manage it from there, with their own way or other memory allocators I have, and then/or turn it off entirely when they reached to the point they can optimize it after rapid iterations for the features or if they feel they can code safe enough in unsafe environment. This has nothing to do with other modules/subsystems, especially low level ones.

On 10/6/2018 at 11:06 PM, mychii said:

Sorry for the late reply, thanks for the effort of the code. Sorry I don't quite understand, if it isn't solved by the allocator, so how does this work for? I actually wrap the object handle in form of smart pointers (and soon the custom containers as well) quite similar like this. Is that what you mean?

When an object is moved, any references to it must be updated with the new location. The "handles" register themselves with the object so that for the duration of their lifetime, they can be informed of any such relocation. But aside from this registration logic, they're just simple wrappers around naked pointers that implement a few operators so they behave "pointer-like" to a user.

7 hours ago, Zipster said:

When an object is moved, any references to it must be updated with the new location. The "handles" register themselves with the object so that for the duration of their lifetime, they can be informed of any such relocation. But aside from this registration logic, they're just simple wrappers around naked pointers that implement a few operators so they behave "pointer-like" to a user.

Yes, that is what the object handle I have in the picture does, a simple wrapper that handles relocatable objects in memory, which I'm trying to inject to STL container through custom STL allocator rather than making custom container using that object handle.