Subj : Re: speed-up critical regions
To   : comp.programming.threads
From : chris noonan
Date : Fri Jun 17 2005 02:03 pm



Phil Frisbie, Jr. wrote:
> amorox@gmail.com wrote:
>
> > I want to thank Phil for his useful link. The Hoard is the kind of
> > implementation I was looking for.
> >
> > The Hoard solution, as described by Emery Berger in his paper, is based
> > on local heaps per thread. But as I thought, the first operation he's
> > doing in the alloc/free functions is to lock the 'choosen' heap. So,
> > local heaps don't mean mutex free. You still have the overhead of a
> > lock operation in every allocation.
>
> The Hoard can just be for reference if you wish. For example, if you engineer
> your app to guarantee that allocated memory will only be freed within the same
> thread then no mutex is needed.

An allocator doesn't have to use mutexes. The algorithms
described at:
http://www.leapheap.com/user_guide.html
are lock-free, even though they don't use per-thread subheaps.
More surprisingly, if your allocator does employ per-thread
subheaps, it doesn't even have to have expensive bus-locking
operations (e.g. LOCK CMPXCHG on Intel Pentium). This is
because it can be arranged that a freeing thread is guaranteed
not to be interfered with by any other thread: allocating
threads ignore any memory block marked as already allocated.
Then a thread can safely free a memory block from another
thread's memory pool.

Of course the data structures you need to implement a lockfree,
buslockfree allocator may not be optimal in other respects...

Chris

.