Prev: C++ Memory Management Innovation: GC Allocator
Next: C++ Memory Management Innovation: GC Allocator
From: Chris Thomasson on 22 Apr 2008 13:25
"xushiwei" <xushiweizh(a)gmail.com> wrote in message
news:52ee8318-2611-4883-bbef-33c9a566bb75(a)s50g2000hsb.googlegroups.com...
> On 4��22��, ����9ʱ52��, "Chris Thomasson" <cris...(a)comcast.net> wrote:
>> "Chris Thomasson" <cris...(a)comcast.net> wrote in message
>>
>> If I am correct, well, "perhaps" I have something that just might be able
>> to
>> help your allocator. There is an invention that can transform most
>> single-threaded memory allocators into scaleable multi-threaded ones;
>> here
>> is my initial post:
>>
>> http://groups.google.com/group/comp.arch/browse_frm/thread/6dc825ec99...
>>
>> basically, you create single-threaded allocator and plug it into the
>> system,
>> then, boom, its multi-threaded. If you have any questions, feel free to
>> fire
>> away...
>
>
> I'm sorry but I think you misunderstand my points. I don't want to
> create single-threaded allocator.
>
> Why? Sharing GC Allocator in multi threads is not recommended. It
> means that sharing memory between threads is also not recommended. If
> you REALLY want to share memory, use new/delete or anything else.
>
> For users of GC Allocator, we suggest that only use ONE BlockPool
> instance in ONE thread, and ONE thread may use multiple PRIVATE
> "ScopeAlloc" instances (depend on your requirement) to allocate
> memory.
[...]

You did create a purely single-threaded allocator. Your saying that I need
to create an allocator instance per-thread, but I cannot do cross thread
deallocations using them because they provide no support for
synchronization. Did you know that there are multi-threaded allocators that
are based on per-thread heaps? Check StreamFlow or Hoard documentation. If I
use those allocators I can allocate memory in Thread A and deallocate in
Thread A without any synchronization whatsoever, however, if I deallocate in
Thread B then there is an interlocked RMW instruction. This aspect makes
them more flexible. For your own words, I cannot create a simple
producer/consumer pattern using your algorithm because they are not
thread-safe.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: xushiwei on 23 Apr 2008 05:43
{ Please do not quote extraneous material, such as the clc++m banner.
Please also note that top posting is discouraged in this group. -mod }

Yes, GC Allocator is not thread-safe. It's my EMPHASES in
implementation section. And that is
why GC Allocator is so fast.

I don't think implementing a producer/consumer pattern is a common
case. So, why not implement an allocator without a multithreaded lock,
then use it with a explicit lock when you implement a producer/
consumer pattern (or something that need to share memory)?

On 4��22��, ����5ʱ39��, "Chris Thomasson" <cris...(a)comcast.net> wrote:
> "xushiwei" <xushiwe...(a)gmail.com> wrote in message
>
> AFAICT, your implementation is not thread-safe. For instance, I could not
> use it to implement a producer/consumer pattern. Thread A allocates blocks
> and passes them to thread B which frees them. Am I missing something?

{ banner removed -mod }

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Michael Kilburn on 5 May 2008 23:22
On Apr 22, 4:13 am, xushiwei <xushiwe...(a)gmail.com> wrote:
> To obtain a copy of this paper in pdf format click here (http://
> xushiwei.com/local--files/gc-allocator/GCAllocator.pdf or from google
> code:http://code.google.com/p/stdext/downloads/list). Another copy is
> also available on google docs (http://docs.google.com/View?
> docid=dds5zgx6_353dc5k4fcq) in html format.
[ the rest skipped]

Had a look at your code... Looks unnecessarily complicated to me. Here
is the result of about 15 minutes of work:

[code]
#include <deque>
#include <cassert>


using namespace std;


struct FastAlloc
{
struct Block
{
unsigned char memory[1024];
};
deque<Block> m_pool;
size_t m_left;

FastAlloc() : m_left(0) {}

void* allocate(size_t size)
{
assert(size <= 1024);
if (size > m_left)
{
m_pool.resize(m_pool.size() + 1);
m_left = 1024;
}

void* res = m_pool.back().memory + 1024 - m_left;
m_left -= size;
return res;
}
};


template<class T>
class my_alloc
{
public:
FastAlloc* m_alloc;
typedef T value_type;

typedef value_type* pointer;
typedef value_type& reference;
typedef value_type const* const_pointer;
typedef value_type const& const_reference;

typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;

template<class _Other>
struct rebind
{ // convert an my_alloc<_Ty> to an my_alloc <_Other>
typedef my_alloc<_Other> other;
};

pointer address(reference _Val) const
{ // return address of mutable _Val
return pointer(&_Val);
}

const_pointer address(const_reference _Val) const
{ // return address of nonmutable _Val
return const_pointer(&_Val);
}
/*
my_alloc()
{ // construct default my_alloc (do nothing)
}
*/

my_alloc(FastAlloc& alloc) : m_alloc(&alloc)
{ // construct default my_alloc (do nothing)
}

my_alloc(const my_alloc<T>& o)
{ // construct by copying (do nothing)
m_alloc = o.m_alloc;
}

template<class _Other>
my_alloc(const my_alloc<_Other>& o)
{ // construct from a related my_alloc (do nothing)
m_alloc = o.m_alloc;
}

template<class _Other>
my_alloc<T>& operator=(const my_alloc<_Other>&)
{ // assign from a related my_alloc (do nothing)
m_alloc = o.m_alloc;
return (*this);
}

void deallocate(pointer _Ptr, size_type)
{ // deallocate object at _Ptr, ignore size
}

pointer allocate(size_type _Count, const void _FARQ * = 0)
{ // allocate array of _Count elements, ignore hint
return pointer(m_alloc->allocate(_Count*sizeof(T)));
}

void construct(pointer _Ptr, T const& _Val)
{ // construct object at _Ptr with value _Val
new (_Ptr) T(_Val);
}

void destroy(pointer _Ptr)
{ // destroy object at _Ptr
(*_Ptr).~T();
}

std::size_t max_size() const
{ // estimate maximum array size
std::size_t _Count = (std::size_t)(-1) / sizeof (T);
return (0 < _Count ? _Count : 1);
}
};

int main()
{
FastAlloc alloc;

deque<int, my_alloc<int> > q(alloc);

q.push_back(1024);
return 1;
}
[/code]

add STD_NEW/STD_DELETE support, parametrize my_alloc with allocator
type, write few different allocator classes and that's it. Looks much
more simple.

Sincerely yours,
Michael.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

First  |  Prev  | 
Pages: 1 2
Prev: C++ Memory Management Innovation: GC Allocator
Next: C++ Memory Management Innovation: GC Allocator