allocate_shared homework

[albinopapa]

Posting this here as I said I would in the YT comments, albeit a day late.

WinLocalAllocResource.h

Code: Select all

#pragma once

#include <cassert>
#include <cstdint>
#include <memory_resource>
#include <Windows.h>


class WinLocalAllocResource : public std::pmr::memory_resource
{
	void* do_allocate( std::size_t size_, std::size_t alignment_ )override
	{
		// Check if alignment_ is power of 2
		assert( ( ( alignment_ & ( alignment_ - 1 ) ) == 0 ) && "Alignment must be a power of 2" );

		// Verify size_ is a multiple of alignment_
		assert( ( size_ % alignment_ ) == 0 );

		if( auto memory = LocalAlloc( LMEM_FIXED, size_ ); memory != nullptr )
		{
			// Verify that the address returned is a multiple of alignment_
			assert( ( reinterpret_cast< std::uintptr_t >( memory ) % alignment_ ) == 0 );
			return memory;
		}

		throw std::bad_alloc();
	}
	void do_deallocate( void * memory_, size_t alloc_size_, size_t alignment_ )override
	{
		// A possible reason that this function throws if you pass in a pointer
		// that wasn't allocated using LocalAlloc, the MSDN doesn't specify 
		// the reason so we can use std::system_error and std::error_code
		// to have Windows tell us what we did wrong...most of the tiem.
		if( LocalFree( memory_ ) != nullptr )
			throw std::system_error(
				std::error_code( GetLastError(), std::system_category() ),
				"Deallocation failed"
			);
	}
	bool do_is_equal( const memory_resource& other_ ) const noexcept override
	{
		// If RTTI is disabled or other_ isn't a WinLocalAllocResource, 
		// an exception is hopefully thrown and we can catch and return false
		try
		{
			const auto& other_resource =
				dynamic_cast< WinLocalAllocResource const& >( other_ );

			return true;
		}
		catch( const std::exception& )
		{
			// We'll return false even for RTTI being disabled since we 
			// have no way of knowing if other_ is or isn't a WinLocalAllocResource
			return false;
		}
	}
};

// This has no data to maintain so a global instance should be fine.
inline auto LocalAllocResource = WinLocalAllocResource{};

WinLocalAlloc.h

Code: Select all

template<typename T>
class WinLocalAlloc
{
public:
	using value_type = T;
	// Set true to let containers know to copy the allocator when container is copied
	using propagate_on_container_copy_assignment = std::true_type;
	// Set true to let containers know to move the allocator when container is moved
	using propagate_on_container_move_assignment = std::true_type;
	// We can compare always equal since WinLocalAlloc doesn't accept
	// ouside memory resource classes
	using is_always_equal = std::true_type;

public:
	WinLocalAlloc() = default;
	template<typename U> WinLocalAlloc( WinLocalAlloc<U> const& other_ )noexcept
		:
		m_resource( other_.resource() )
	{}

	// WinLocalAllocResource handles throwing if allocation not possible
	T* allocate( std::size_t count_ ) {
		auto* memory = m_resource->allocate( sizeof( T ) * count_, alignof( T ) );
			
		return static_cast< T* >( memory );
	}

	void deallocate( T* memory_, std::size_t count_ ) {
		m_resource->deallocate( memory_, sizeof( T ) * count_, alignof( T ) );
	}

	// Construct a T in-place at address pointed to by memory_ using args...
	template<typename...Args>
	void construct( T* memory_, Args...args_ )noexcept( noexcept( std::is_nothrow_constructible_v<T> ) )
	{
		new ( memory_ ) T{ std::forward<Args>( args_ )... };
	}

	// Objects constructed using placement new must have their destructors
	// called explicitly
	void destroy( T* memory_ )noexcept {
		memory_->~T();
	}

	// Returns a copy of this allocator, when you copy one container
	// to another, this function is called.
	WinLocalAlloc select_on_container_copy_construction( WinLocalAlloc const& ) {
		return *this;
	}

	// Used in conversion constructor since it's templated on a different type,
	// we can't reach the private data of the other class
	std::pmr::memory_resource* resource()const noexcept {
		return m_resource;
	}
private:
	std::pmr::memory_resource* m_resource = std::addressof( LocalAllocResource );
};

template<typename T, typename U>
bool operator==( WinLocalAlloc<T> const& left_, WinLocalAlloc<U> const& right_ )noexcept {
	return ( *left_.resource() ) == ( *right_.resource() );
}
template<typename T, typename U>
bool operator!=( WinLocalAlloc<T> const& left_, WinLocalAlloc<U> const& right_ )noexcept {
	return !( left_ == right_ );
}

Main.cpp

Code: Select all

#define WIN32_LEAN_AND_MEAN
#define NOMINMAX
#include "WinLocalAllocResource.h"
#include <vector>
#include <iostream>

class Object
{
public:
	Object()
	{ 
		std::cout << "Default constructor called\n";
	}
	Object( Object const& other_ )
	{
		std::cout << "Copy constructor called\n";
	}
	Object( Object&& other_ )noexcept
	{
		std::cout << "Move constructor called\n";
	}
	Object& operator=( Object const& other_ ) 
	{
		if( this != std::addressof( other_ ) ) {}
		std::cout << "Copy assignment operator called\n";

		return *this;
	}
	Object& operator=( Object&& other_ )noexcept 
	{
		if( this != std::addressof( other_ ) ) {}
		std::cout << "Move assignment operator called\n";

		return *this;
	}
	~Object()noexcept 
	{
		std::cout << "Destructor called\n";
	}
private:
	char v4[ 99 ];
	char v1;
	bool v3;
	double v5;
	float v0;
	int v2;
};

constexpr auto szObject = sizeof( Object );
constexpr auto alObject = alignof( Object );
int main( int argc, char* argv[] )
{
	try
	{
		auto vec = std::vector<Object, WinLocalAlloc<Object>>( WinLocalAlloc<Object>{} );
		for( int i = 0; i < 10; ++i )
		{
			vec.push_back( Object{} );
		}

		auto sp_complex = 
			std::allocate_shared<Object>( WinLocalAlloc<Object>() );
		std::cout << sp_complex.use_count() << '\n';
		{
			auto sp2 = sp_complex;
			std::cout << sp2.use_count() << '\n';
		}
		std::cout << sp_complex.use_count() << '\n';
	}
	catch( std::exception const& error )
	{
		std::cout << error.what() << '\n';
	}
	return 0;
}

While coding up the C++17 memory_resource version I ran into some issues and found something interesting. The interesting thing was LocalAlloc always seemed to return an address that was aligned to sizeof(void*) either 4 bytes for x86 and 8 bytes for x64. Another thing I found out was the allocate_shared() function and many if not all of the STL containers seems to request a size that is a multiple of the alignment requirement. I originally had code to change the size if needed as well as setting up a way to offset the pointer returned to be aligned, but further testing using the STL proved I didn't need these. However, I kept the asserts there just in case. If all else, debug builds will alert you if you use this allocator in a custom container for instance.

[chili]

This is very fancy I never looked much into the use cases/motivations for the pmr stuff. What's it good for?

[albinopapa]

I really didn't think about that shit before opening my mouth on YT, but the main idea behind polymorphic memory resource was to be able to pass a typeless resource to any allocator. The allocators are usually templated and therefore may need to have multiple different allocators for different uses. Now, imagine if the allocators had state that would need to be copied, but you really wanted to reuse the stack-allocated buffer for all of your allocations. With a runtime polymorphic resource, you could have all the memory management typeless and separate from the allocators that know about types and their alignment and size requirements. This also means that allocators can become relatively stateless and unaware of the memory management strategy. The only state would be the pointer to a pmr::memory_resource base class.

So yeah, if you wanted to create a memory pool at the beginning of the program and use the old style allocator memory management system, you'd have to pass in the pool to each instantiated allocator anyway and some class would be needed to manage the blocks that would be doled out, a pointer or position of where in the pool the next allocation is coming from etc. Pmr::memory_resource just gives a standardized interface for that scenario I guess.

[albinopapa]

Also, with std::pmr::polymorphic_allocator, you don't even HAVE to create an allocator if you are just wrapping a third party memory manager.

Here's the same example using the polymorphic_allocator already defined in the STL.

Code: Select all

int main( int argc, char* argv[] )
{
	using LocalAllocWin32 = std::pmr::polymorphic_allocator<Object>;

	// LocalAllocResource is still the global instance of the WinLocalAllocResource
	try
	{
		auto vec = std::vector<Object, LocalAllocWin32>( LocalAllocWin32{ &LocalAllocResource } );
		for( int i = 0; i < 10; ++i )
		{
			vec.push_back( Object{} );
		}

		auto sp_complex = 
			std::allocate_shared<Object>( LocalAllocWin32{ &LocalAllocResource } );
		std::cout << sp_complex.use_count() << '\n';
		{
			auto sp2 = sp_complex;
			std::cout << sp2.use_count() << '\n';
		}
		std::cout << sp_complex.use_count() << '\n';
	}
	catch( std::exception const& error )
	{
		std::cout << error.what() << '\n';
	}
	return 0;
}

It's a bit overkill, but Box2D has a small object allocator.

Code: Select all

#ifndef B2_BLOCK_ALLOCATOR_H
#define B2_BLOCK_ALLOCATOR_H

#include "Box2D/Common/b2Settings.h"

const int32 b2_chunkSize = 16 * 1024;
const int32 b2_maxBlockSize = 640;
const int32 b2_blockSizes = 14;
const int32 b2_chunkArrayIncrement = 128;

struct b2Block;
struct b2Chunk;

/// This is a small object allocator used for allocating small
/// objects that persist for more than one time step.
/// See: http://www.codeproject.com/useritems/Small_Block_Allocator.asp
class b2BlockAllocator
{
public:
	b2BlockAllocator();
	~b2BlockAllocator();

	/// Allocate memory. This will use b2Alloc if the size is larger than b2_maxBlockSize.
	void* Allocate(int32 size);

	/// Free memory. This will use b2Free if the size is larger than b2_maxBlockSize.
	void Free(void* p, int32 size);

	void Clear();

private:

	b2Chunk* m_chunks;
	int32 m_chunkCount;
	int32 m_chunkSpace;

	b2Block* m_freeLists[b2_blockSizes];

	static int32 s_blockSizes[b2_blockSizes];
	static uint8 s_blockSizeLookup[b2_maxBlockSize + 1];
	static bool s_blockSizeLookupInitialized;
};

#endif

( Cpp file left out for space reasons )

If you wanted to use this allocator with STL containers, you could just change the interface a bit and then turn it into a template. Problem is, a new instance of all the member data would be instantiated for each type. Now, turn this into a b2SmallObjectResource that inherits from std::pmr::memory_resource, then you can use std::pmr::polymorphic_allocator as the allocation user facing interface, and the allocator will use the hypothetical b2SmallObjectResource to allocate from.

[albinopapa]

One thing I forget about is that Box2D's b2BlockAllocator actually this allocator is more like the std::pmr::monotonic_buffer_resource.

b2BlockAllocator uses malloc to allocate a memory pool ( b2Chunk ), then grabs memory from the pool to construct object there. If the chunk is exhausted or the allocation is larger than expected, it is allocated directly using malloc.

Std::pmr::monotonic_buffer_resource allows you to either create a memory_resource derived type to allocate the pool or by default will use operator new ( or whatever is returned by std::pmr::get_default_resource() ) and allocate blocks very similar to what the b2BlockAllocator is doing.

Off topic somewhat
One of the issues I have with Box2D's code is a lot of the classes have multiple responsibilities. For instance, b2Body and b2Joint act as both body/joint objects, but also linked lists. They point to the next instance of their respective types. Another one is because the b2BlockAllocator just allocates, the use of placement new us used inline everywhere. So for cleanup, each object in the linked list must remove itself by linking the previous with next and each destructor must be called manually ( required when using placement new ).

In the STL, allocators would handle the whole placement new upon calling allocator.construct() and would call the destructor upon calling allocator.destroy(). Of course, normally, you'd also be using containers either STL or custom which would handle the using of the allocators which hides the need to explicitly call construct/destroy on the allocators as well as if the authors would have used std::list or made their own, they wouldn't have all the linked list code hanging out cluttering up the rest of their code nor would they have had to repeat the same steps over and over.