RFC on mt_allocator.h

[Emery Berger]

Felix Yen says:
> Worth noting: Bonwick's 2001 allocator comparison includes Hoard,
whereas
> Berger never refers to Bonwick's work. Guess which allocator won the
> comparison?

Felix,

I'm not sure why you are casting this unwarranted aspersion on my
research integrity, but I really do not appreciate it.

I guess the title of my paper "Reconsidering Custom Memory Allocation"
was not sufficiently clear: my paper was about *custom memory
allocators*, not different implementations of malloc/free, of which
Bonwick & Adams' libumem is but one of many. It therefore had no place
in such a paper (and neither did Hoard).

Incidentally, it might be worth noting here that the Bonwick allocator
(which, as you know, was intended for use as a kernel allocator and then
adapted for use as a user-level allocator) does not provide the
false-sharing avoidance that Hoard provides. It's really easy to be
faster than Hoard, but you have to sacrifice something (scalability,
blowup, false-sharing avoidance - pick one). I had an e-mail discussion
with Jeff about these points, along with a question about the benchmark
that he used to compare libumem and Hoard. Here's Jeff's response about
the benchmark:

> It is, literally, a simple alloc/free loop:
> 
>       for (i = 0; i < iters; i++)
>                free(malloc(100));

He also noted, per my comment about allocator-induced false sharing, a
phenomenon first described in the Hoard paper:

> People looking to adopt
> magazine/slab/vmem technologies for other purposes would be well
advised
> to consider induced false sharing.

-- emery

--
Emery Berger
Assistant Professor
Dept. of Computer Science
University of Massachusetts, Amherst
www.cs.umass.edu/~emery


> -----Original Message-----
> From: Felix Yen [mailto:fwy@alumni.brown.edu]
> Sent: Friday, November 28, 2003 8:23 AM
> To: emery@cs.umass.edu
> Subject: Re: Yalloc
> 
>  >  Just getting around to cleaning my mailbox.
> 
> Emery, thanks for responding.  I'll have to add that to my
Thanksgiving
> ritual :-)
> 
>  >  What you've implemented is basically a threshold-style allocator -
>  >  I describe these in my Hoard paper.
> 
> It didn't occur to me to reread the Hoard paper, because yalloc is
> supposed to be compatible with Hoard.  In fact, an earlier
> implementation was linked with Hoard and tested for performance.
> However, we tested a server application using a client simulator and
an
> actual network connection, so the results are virtually impossible to
> reproduce.
> 
>  >  I don't think Heap Layers presents any real difficulties to
building
> such an allocator.
> 
> I agree.  The only issue, if I remember correctly, is the toolkit's
> exclusive use of header file implementations.  I think this style of
> recycling requires linking with a new translation unit.  Of course,
> that's not much of an obstacle.
> 
>  >  These allocators can suffer from a serious allocator-induced false
> sharing problem;
>  >  at a glance, I'm not sure if yours does or does not.
> 
> I suspect that it does, but I'm not sure if the problem is avoidable.
> We should be able to measure its impact though.  However, it's not
easy
> to write a small test program that simulates a heavily loaded,
> multithreaded server.  Quantifying performance is also an issue.  We
> should be willing to spend a bit more time allocating/deallocating if
> doing so minimizes context switches when the server is heavily loaded.
> Do you have a test suite I could use?
> 
> 
> Felix