Re: Do you use a garbage collector?
"Jerry Coffin" <jcoffin@taeus.com> wrote in message
news:MPG.226875e660c8657b989c6f@news.sunsite.dk...
In article <KKqdncjvUO8DJGPanZ2dnUVZ_sqinZ2d@comcast.com>,
cristom@comcast.net says...
[ ... ]
You are incorrect. Each call into "new" will "most-likely" be
"fast-pathed"
into a "local" cache. On multi-threaded systems, this "cache-hit" can
even
be accomplished without using _any_ interlocked RMW or memory barrier
instruction(s). That is, the cache would be per-thread. Some may think
that
if a cache is per-thread then a thread will not be able to free something
unless it allocated it. This is false line of thinking. There are
different
algorithms that can solve this, one of them can be found here:
http://groups.google.com/group/comp.arch/browse_frm/thread/24c40d42a04ee855
Hoard and StreamFlow also use per-thread heaps.
Most of the problem seems to be that people think in terms of a heap
having a single free list, so all other threads have to contend for
access to that free list.
I agree; most of those people have not implemented a high-performance
scaleable memory allocator.
A trivially simple design is for each thread to have its own heap, and
each heap to have one free list for every other thread in the system.
How does this efficently handle dynamic numbers of threads that can, and
will be created and joined with, or detached, during the lifetime of a given
process? It seems like you are describing a fully connected network. One
freelist per-thread, that holds N buckets, where N == current number of
threads at any one time. This implies that N is an unknown variable,
therefore, if user creates a number of threads, so on a high-end system with
many cores, they must all be interconnected. Each threads heap needs an
entry for a thread in the system, if a new thread gets added, it must auto
register, or register on "first" usage; think 'pthread_once()'.
There are some discussions here:
http://groups.google.com/group/comp.programming.threads/msg/13879a3dec53169a
which is within the following thread:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e082e1eb26397d5e
Your right, atomic XCHG gets executed when a thread hits an "exhausted
per-thread heap" state. This XCHG will reuse memory that any _other_ threads
have previously passed back to the calling thread. A "remote free" can use a
CAS, or it can simply use message-passing to notify any of the origin
threads subsequent logically failed allocation requests. Logically fails
means that a thread did not hit the fast-path. It needs to use an
interlocked RMW instruction, or use distributed messaging.
Single-Producer/Consumer queues work well, _only_ when properly managed of
course.
Each other thread can then free blocks to any heap with minimal
possibility of contention (specifically, with the thread whose heap it's
freeing memory TO, and then only if it happens while that thread is
grabbing that free list to coalesce its memory with the other free
blocks.
If you are using a dynamic network, you can easily use
single-producer/consumer queuing. Anybody who as been reading 'c.p.t' knows
where to look for source-code. You can multiplex a given threads registered
queues, and apply priorities.
This contention can normally be reduced to a single atomic exchange to
free memory and another to grab memory for coalescing. Specifically,
consider a structure something like:
struct free_block {
void *next;
size_t size;
size_t origin_threadID;
char payload[0];
};
Actually, the free-block only needs to be == to sizeof(void*):
http://groups.google.com/group/comp.arch/browse_frm/thread/24c40d42a04ee855
http://groups.google.com/group/comp.programming.threads/msg/bc019dc04362be41
http://groups.google.com/group/comp.programming.threads/msg/1d3aeaa6ebf5181f
Technically, that's not legal in C++, but I supect you get the idea.
Let's also assume each thread's heap has a vector of free-lists,
something like:
typedef std:vector<free_block *> free_list;
And we have a vector of free lists, one per thread:
std::vector<free_list> free_lists;
In that case, freeing a block looks something like:
void free_a_block(void *block) {
free_block *f = ((char *)block)-sizeof(free_block);
f->next = f;
size_t heap = f->origin_threadID;
size_t my_threadID = get_current_thread_ID();
atomic_exchange(f->next, free_lists[heap][my_thread_ID]);
}
I.e. we put this block's address into its own 'next' field, and then
exchange that with the pointer to the head of our free list in the
appropriate heap.
Simple scheme:
http://groups.google.com/group/comp.arch/browse_frm/thread/6dc825ec9999d3a8
(read all...)
[...]
If you really care about utmost portability, use a single mutex per-thread,
and an algorithm similar to the one contained within the third link I cited
in this post. Otherwise, you can tack advantage of per-architecture
builds... IMHO, thinking in per-thread distributed efficient communications
is definitely worthwhile.