------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <6492.917861783.1@mabelode.imrryr.org>

I am going to apologise in advance, if this subject has already
been brought up (or if this is the wrong list for it), but I was
recently rereading a bit of the Usenix stuff and came across the
FreeBSD malloc(3) paper.  Quite a bit of the information presented
seemed interesting, so I thought that I'd quickly compile it into
libc.  This actually proved to have only about 6 lines of added
code to get it to work.

And, after rebuilding my world to use it (on NetBSD/alpha, an
AlphaStation 200 4/233) everything seems to be working okay, for
about 3 or four days.

To add some data points, I decided to create a quick and dirty test
program to see what sort of effect that this had.  (Included at the
end as an attachment.)  The program takes 4 arguments:
	-c count	- how many times to reallocate things.
	-s size		- the number of malloc(3)'ed things to have
			  in the air at a time.
	-m new_size1	- one size of a malloc(3) call.
	-n new_size2	- the other size of a malloc(3) call.

The program first mallocs a void ** of size to hold all of our pointers,
then mallocs a lot of little things to go in them.  Then it loops through
the even numbered pointers and free(3)'s them and malloc(3)'s a new_size1
sized buffer.  Then it does the same the the odd ones and new_size2.  Then
it swaps new_size1 and new_size2.  (Repeat count times.)

To make a long story short, here are my results.  (all runs have
-m 4096 -n 513 -c 10.  The tables are thus indexed by the program
and the size.)

                  1024      2048       4096      8192     16384
NetBSDmalloc  0.776820  2.825681   246.8450*   ENOMEM    ENOMEM
FreeBSDmalloc 0.374827  1.052951   2.630907   5.88337   96.6546*
GNUmalloc     0.174587  0.390482   0.970757   3.72554   198.986*

Notes:
	o A * next to a result means that I saw the disk thrashing.
	o All results are in seconds.
	o All results are averaged over 3 runs.
	o NetBSDmalloc1 is our standard malloc run number 1.
	o ENOMEM is "ran out of memory".  (ulimit -d is 131072)
	o My box has 64MB RAM.

The tests that I have done are in no way scientific, and there are
a number of caveats:
	o the machine was not in single user mode.
	o the test program was contrived.
	o etc...

But if I ignore those for a second, the conclusions would be:
	o FreeBSD malloc is faster than our malloc,
	o FreeBSD malloc is better than GNU Malloc when paging is occurring,
	o And our malloc is not as efficient with memory as either.

I think that this justifies further examination of the issues
(perhaps applying a benchmark that was not written in 30 minutes
by me so that I had something to say in the email.  :)

The FreeBSD malloc also has a number of features that seem to be
useful for debugging and it can also be set up to call madvise(2) to
inform the kernel about pages that are not currently being used.

 == Roland
 == http://www.imrryr.org/~elric/

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <6492.917861783.2@mabelode.imrryr.org>

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include <sys/time.h>

#define MEMPOINTERS	32768

void
usage()
{
	fprintf(stderr, "usage: malloctest [-c count] [-s size] "
	    "[-m new_size1] [-n new_size2]\n");
	exit(-1);
}

int
main(int argc, char **argv)
{
	struct timeval tv1, tv2;
	void **mem, *p;
	int mempointers = 0;
	int tmp, new_size1 = 0, new_size2 = 0;
	int count = 0, c;
	int i, j;
	extern char *optarg;
	extern int optind;
	int ch;

	while ((ch = getopt(argc, argv, "c:m:n:s:")) != -1)
		switch(ch) {
		case 'c':
			count = atoi(optarg);
			break;
		case 'm':
			new_size1 = atoi(optarg);
			break;
		case 'n':
			new_size2 = atoi(optarg);
			break;
		case 's':
			mempointers = atoi(optarg);
			break;
		case '?':
		default:
			usage();
		}
	argc -= optind;
	argv += optind;

	if (count == 0)
		count = 2;
	if (mempointers == 0)
		mempointers = MEMPOINTERS;
	if (new_size1 == 0)
		new_size1 = 4096;
	if (new_size2 == 0)
		new_size2 = 513;
	printf("Test will run %d times.\n", count);
	gettimeofday(&tv1, NULL);
	mem = malloc(mempointers * sizeof(*mem));
	j = 1;
	for (i=0; i < mempointers; i++, j *= 7) {
		p = malloc(j);
		if (!p) {
			fprintf(stderr, "Malloc returned NULL\n");
			exit(-1);
		}
		*(mem + i) = p;
		*(char *)(*(mem+i) +(j-1)) = 'A';
		if (j > 1024)
			j = 1;
	}
	for (c=0; c < count; c++) {
		for (i=0; i < mempointers; i += 2) {
			free(*(mem + i));
			p = malloc(new_size1);
			if (!p) {
				fprintf(stderr, "Malloc returned NULL\n");
				exit(-1);
			}
			*(mem + i) = p;
			*(char *)(*(mem+i)) = 'B';
		}
		for (i=1; i < mempointers; i += 2) {
			free(*(mem + i));
			p = malloc(new_size2);
			if (!p) {
				fprintf(stderr, "Malloc returned NULL\n");
				exit(-1);
			}
			*(mem + i) = p;
			*(char *)(*(mem+i)) = 'C';
		}
		tmp = new_size1;
		new_size1 = new_size2;
		new_size2 = tmp;
	}
	for (i=0; i < mempointers; i++)
		free(*(mem + i));
	free(mem);
	gettimeofday(&tv2, NULL);
	tv2.tv_sec -= tv1.tv_sec;
	tv2.tv_usec -= tv1.tv_usec;
	if (tv2.tv_usec < 0) {
		tv2.tv_sec--;
		tv2.tv_usec += 1000000;
	}
	printf("This test took %d.%6d seconds\n",
		tv2.tv_sec, tv2.tv_usec);
}

------- =_aaaaaaaaaa0--