The direction of malloc?

[Ondřej Bílka]

On Tue, Dec 17, 2013 at 01:59:57PM +0100, Torvald Riegel wrote:
> On Mon, 2013-12-16 at 22:23 +0100, Ondřej Bílka wrote:
> > On Mon, Dec 16, 2013 at 05:59:00PM +0100, Torvald Riegel wrote:
> > > On Tue, 2013-12-10 at 22:05 +0100, Ondřej Bílka wrote:
> > > > We have fastbins that sorta do this but with several problems. 
> > > > 1. They are not really lockless, for malloc they need a lock, only
> > > > freeing will be when bug 15073 gets fixed.
> > > 
> > > Note that *properly tuned* locks can be as fast as lock-less code in
> > > several cases.  When you use a, say, stock PTHREAD_MUTEX_NORMAL lock,
> > > this won't be well-suited to short critical sections because it doesn't
> > > spin.  PTHREAD_MUTEX_ADAPTIVE_NP spins, but the number of spinning
> > > iterations seems to be an arbitrary choice, and isn't very useful in my
> > > experiments so far.  Also, there's no back-off whatsoever in the
> > > spinning.
> > >
> > As will said acquiring a lock is hot part in a single thread
> > applications.
> 
> You said you wanted lock-less code.  You didn't say you want
> nonconcurrent code.  Thus there is concurrency, and you need to
> synchronize in some way.  If it involves modifications, you need a CAS
> or other RMW op of some kind, typically, independent of whether you use
> a lock or not.  Thus, the lock can have as many or fewer atomic RMW/CAS
> ops than other concurrent code.  That's what I pointed out.
> 
There are different degrees of synchronization that may be required. In
malloc sources of concurency are having many threads, free from
different thread and realloc from different thread.

A first one could be treated by a cache, for a free we could make a
synchronization overhead arbitrary low by waiting until we accumulate n
bytes for given arena and only then return these and I think that for
realloc best course of action is just copy data to our arena as I posted
earlier.

> > Please explain how spinning could improve performance in single thread
> > applications.
> 
> You spoke about lockless code, so obviously concurrent code.  My comment
> was thus referring to concurrent code.  If you have a single-threaded
> program, then you can avoid synchronization, obviously (ignoring
> synchronization just for reentrancy...).
>
And we for malloc use a switch variable to avoid lock path and set it
when pthread_create is called? For reentancy a ordinary variable suffices.

> > > 
> > > > Second problem is that fastbins are per-arena not per-thread which
> > > > forces us to use atomic operations. These are expensive (typicaly more than 50 cycles).
> > > 
> > > Especially on x86, atomic operations that *hit in the cache* have become
> > > very fast compared to their costs in the past.  I don't have current
> > > numbers, but I believe the 50 cycle number is too high; I vaguely
> > > remember 10-20.
> > 
> > A simple benchmark could check a real cost. A problem is that while for core2
> > and i7 cost of CAS is around 20 cycles for bulldozer its still 50 cycles.
> 
> Sure, this differs per architecture.  But recent Intel CPUs *are*
> common, so it's not quite correct to say that the latency (or
> throughput, depending on the algorithm) of an atomic RMW/CAS op is
> really the primary problem.
> 
> > Even with these a malloc+free pair contains 5 atomic instructions on
> > fastbin path which gives 100 cycle penalty (malloc: lock, get item from bin, unlock,
> > free: set bit that fastbins are in use, put item to bin) 
> 
> Maybe, but you still need to be careful when drawing conclusions from
> that because there are more performance effects in allocation than just
> the "cycle penalty" you mention (e.g., locality and other memory-system
> effects caused by differences in where data is placed).
>
Its not just that, pretty much every modern allocator uses some
per-thread cache so it looks like good idea, also oprofile shows lock
cmpxchg instruction as one of likely culprits. When I try a per-thread
cache that I posted earlier on a test that does just malloc and free it
nearly doubles performance.

There are several factors that come in play a first one is lack of
locking, second is getting expects correct, third is saving a call of
int_malloc. Then there are several cycles saved by omiting test for hook
and malloc_perturb.

Real implementation will be bit faster as dynamic tls slows this down a
bit.

Memory system effects are not a factor here, as allocation pattern is
identical (stack in both cases).

For benchmark use following commands:

$ gcc test.c -O3 -o test
$ gcc malloc_cache.c -O3 -fPIC -shared -mtls-dialect=gnu2 -lpthread -ldl -o malloc_cache.so

$ /usr/bin/time ./a.out 
Command exited with non-zero status 32
0.29user 0.00system 0:00.29elapsed 99%CPU (0avgtext+0avgdata
512maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps
$ /usr/bin/time ./a.out 
Command exited with non-zero status 32
0.30user 0.00system 0:00.30elapsed 99%CPU (0avgtext+0avgdata
512maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps
$ /usr/bin/time ./a.out 
Command exited with non-zero status 32
0.30user 0.00system 0:00.31elapsed 99%CPU (0avgtext+0avgdata
512maxresident)k
0inputs+0outputs (0major+168minor)pagefaults 0swaps

$ LD_PRELOAD=./malloc_cache.so /usr/bin/time
./a.out 
Command exited with non-zero status 32
0.19user 0.04system 0:00.23elapsed 98%CPU (0avgtext+0avgdata
117796maxresident)k
0inputs+0outputs (0major+29503minor)pagefaults 0swaps
$ LD_PRELOAD=./malloc_cache.so /usr/bin/time
./a.out 
Command exited with non-zero status 32
0.17user 0.04system 0:00.22elapsed 99%CPU (0avgtext+0avgdata
117796maxresident)k
0inputs+0outputs (0major+29503minor)pagefaults 0swaps
$ LD_PRELOAD=./malloc_cache.so /usr/bin/time
./a.out 
Command exited with non-zero status 32
0.12user 0.06system 0:00.19elapsed 99%CPU (0avgtext+0avgdata
117796maxresident)k
0inputs+0outputs (0major+29503minor)pagefaults 0swaps
-------------- next part --------------
#include <stdlib.h>
char *x[1024];
int main(){
  int i;
  for (i=0;i<10000000;i++)
    {
      free (x[i%1024]);
      x[i%1024] = malloc (32 + (i % 64));
    }
}
-------------- next part --------------
#define _GNU_SOURCE
#include <dlfcn.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>

#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size */
#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
#define CHUNKSIZE (2 * SIZE_SZ)

#define PREV_INUSE 0x1
#define IS_MMAPPED 0x2
#define NON_MAIN_ARENA 0x4

#define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)
#define chunksize(p)         ((p)->size & ~(SIZE_BITS))


typedef struct malloc_chunk* mchunkptr;

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))



static void *(*mallocp)(size_t);
static void *(*reallocp)(void *, size_t);
static void (*freep)(void *);


static pthread_key_t destructor_key;

static void free_thread_data (void *);

static void init_blocks()
{
  pthread_key_create (&destructor_key, free_thread_data);
  mallocp = dlsym (RTLD_NEXT, "malloc");
  reallocp = dlsym (RTLD_NEXT, "realloc");
  freep = dlsym (RTLD_NEXT, "free");
};

char temp[10000];
int tempno;

struct stack
{
  struct stack *next;
};

struct thread_pool
{
  struct stack *stack[17];
  int recursed;

  /* Frees from different stack or signal could be done by atomic addition to 
     this stack, that owner thread consumes.  */
  struct stack *to_free;
  int zombie;
};

static __thread struct thread_pool pool;

static int inited;

static pthread_key_t key;
static void init_thread ()
{
  if (!inited)
    {
      inited = 1;
      init_blocks ();
      inited = 2;
    }
  if (inited == 1)
    abort();

  pthread_setspecific(destructor_key, &key);
}


void *malloc_by_mmap (size_t size)
{
  /* In separate patch.  */
  abort();
}

static void free_thread_data (void *data)
{
  size_t idx;
  for (idx = 1; idx <= 16; idx++)
    {
      struct stack *p = pool.stack[idx], *oldp;
      while (p)
        {
          oldp = p;
          p = p->next;
          freep (oldp);
        }
    }
}

#define REC_FREE 1
#define REC_LOCK 2
static inline int as_lock ()
{
  if (__builtin_expect (pool.recursed != REC_FREE, 0))
    {
      if (pool.recursed == 0)
        {
          init_thread ();
          pool.recursed = REC_FREE; 
        }
      else
        return -1;
    }
  pool.recursed = REC_LOCK;
  return 0;
}

static inline void as_unlock ()
{
  pool.recursed = REC_FREE;
}

void *malloc (size_t size)
{
  size_t idx = (size + CHUNKSIZE - 1) / (CHUNKSIZE);

  if (__builtin_expect (inited == 1, 0))
    {
      char *ret = temp + tempno;
      tempno += idx * CHUNKSIZE;
      return ret;
    }
 

 
  if (__builtin_expect (as_lock (), 0))
    return malloc_by_mmap (size);

  if (__builtin_expect (idx <= 16, 1))
    {
      size_t idx = (size + CHUNKSIZE - 1) / CHUNKSIZE;

      if (__builtin_expect (!pool.stack[idx], 0))
        {
          as_unlock ();
          char *p = mallocp (size);

	  return p;
        }
      struct stack *ret = pool.stack[idx];
      pool.stack[idx] = ret->next;

      as_unlock ();
      return (void *) ret;
    }
  else
    {
      as_unlock ();
      char *p = mallocp (size);

      return p;

    }
}

void *calloc (size_t n, size_t el)
{
  void *ret = malloc(n * el);
  memset (ret, 0, n * el);
  return ret;
}

void *realloc (void *old, size_t size)
{
  return reallocp (old, size);
  if (old == NULL)
    return malloc (size);

  mchunkptr p;
  p = mem2chunk(old);
  size_t oldsize = chunksize (p) - CHUNKSIZE;
  size_t idx = (oldsize + CHUNKSIZE - 1) / CHUNKSIZE;

  if (idx <= 16)
    { 
      if (size > oldsize)
        {
          char *new = malloc (size);
          memcpy (new, old, oldsize);
          free (old);
          return new;
        }
      else
        return old;
    }
  reallocp (old, size);
}

void free (void *mem)
{
  if (__builtin_expect (!mem, 0))
    return;
  mchunkptr p;
  p = mem2chunk(mem);
  size_t size = chunksize (p) - CHUNKSIZE;
  size_t idx = (size + CHUNKSIZE - 1) / CHUNKSIZE;
 
  if (__builtin_expect (idx <= 16, 1))
    {
      struct stack *ret = (struct stack *) mem;

      if (as_lock ())
        return;
      ret->next = pool.stack[idx];
      pool.stack[idx] = ret;
    
      as_unlock ();
    }
  else
    freep (mem);
}