btree.c

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

#ifdef USE_BOEHM_GC
#include <gc/gc.h>
#include <sys/time.h>
#ifdef USE_INC_GC
void no_warn(char *msg, GC_word arg) { }
#define INIT GC_set_warn_proc(no_warn); GC_set_handle_fork(0); \
  GC_enable_incremental(); GC_INIT();
#else
#define INIT GC_INIT();
#endif
#define MALLOC(n) (GC_malloc(n))
#ifdef EXPLICIT_FREE
#define FREE(p) (GC_free(p))
#else
#define FREE(p) ((void) 0)
#endif
#elif defined(USE_JEMALLOC)
#include <jemalloc/jemalloc.h>
#define INIT ((void) 0)
#define MALLOC(n) (malloc(n))
#define FREE(p) (free(p))
#elif defined(USE_TINY_GC)
#include "gc/gc.h"
#define INIT GC_INIT()
#define MALLOC(n) (GC_malloc(n))
#ifdef EXPLICIT_FREE
#define FREE(p) (GC_free(p))
#else
#define FREE(p) ((void) 0)
#endif
#else
#include <stdlib.h>
#define INIT ((void) 0)
#define MALLOC(n) (malloc(n))
#define FREE(p) (free(p))
#endif

typedef intptr_t Int;

typedef struct Node {
  struct Node *left;
  struct Node *right;
} Node;

Node *make_node(Node *left, Node *right) {
  Node *result = (Node *)MALLOC(sizeof(Node));
  result->left = left;
  result->right = right;
  return result;
}

Int checksum(Node *node) {
  if (node->left)
    return 1 + checksum(node->left) + checksum(node->right);
  else
    return 1;
}

Node* make_tree(Int depth) {
  if (depth > 0)
    return make_node(make_tree(depth - 1), make_tree(depth - 1));
  else
    return make_node(NULL, NULL);
}

void delete_nodes(Node* node) {
  if (node->left)
  {
    delete_nodes(node->left);
    delete_nodes(node->right);
  }
  FREE(node);
}

#if !(defined(USE_BOEHM_GC) || defined(USE_TINY_GC)) || defined(EXPLICIT_FREE)
void delete_tree(Node *node) {
  if (node)
    delete_nodes(node);
}
#else
#define delete_tree(node) node = NULL
#endif

#ifdef USE_BOEHM_GC
int collections = 0;
double collection_time = 0.0;
double max_collection_time = 0.0;

void GCTrackStats(GC_EventType ev) {
  static struct timeval tstart, tend;
  switch (ev) {
    case GC_EVENT_START:
      gettimeofday(&tstart, NULL);
      break;
    case GC_EVENT_END:
      gettimeofday(&tend, NULL);
      collections++;
      double t =
        (tend.tv_sec + tend.tv_usec / 1000000.0) -
        (tstart.tv_sec + tstart.tv_usec / 1000000.0);
      collection_time += t;
      if (t > max_collection_time)
        max_collection_time = t;
      break;
    default:
      break;
  }
}
#endif


int main(int argc, char* argv[]) {
#ifdef USE_BOEHM_GC
  GC_set_all_interior_pointers(0);
#endif
  INIT;
#ifdef USE_BOEHM_GC
#ifdef EXPLICIT_FREE
  GC_disable();
#endif
  GC_set_on_collection_event(GCTrackStats);
#endif

  Int n = argc >= 2 ? atol(argv[1]) : 21;

  Int min_depth = 4;
  Int max_depth = n;
  if (min_depth + 2 > n)
      max_depth = min_depth + 2;

  Int stretch_depth = max_depth + 1;
  Node *stretch_tree = make_tree(stretch_depth);
  printf("stretch tree of depth %ld\t check: %ld\n", stretch_depth,
      checksum(stretch_tree));

  delete_tree(stretch_tree);
  stretch_tree = NULL;

  Node *long_lived_tree = make_tree(max_depth);

  Int depth;
  for (depth = min_depth; depth <= max_depth; depth += 2) {
    Int iter = 1L << (max_depth - depth + min_depth);
    Int check = 0;
    Int i;
    for (i = 1; i <= iter; i++) {
      Node *current_tree = make_tree(depth);
      check += checksum(current_tree);
      delete_tree(current_tree);
    }
    printf("%ld\t trees of depth %ld\t check: %ld\n",
      iter, depth, check);
  }
  printf("long lived tree of depth %ld\t check: %ld\n",
    max_depth, checksum(long_lived_tree));

#ifdef USE_BOEHM_GC
  struct GC_prof_stats_s prof;
  const Int MB = 1024 * 1024;
  GC_get_prof_stats(&prof, sizeof(prof));
  printf("%8d collections\n"
         "%8.3lf seconds/collection\n"
         "%8.3lf max seconds/collection\n"
         "%8ld MB heap size\n"
         "%8ld MB free bytes\n",
    collections, collection_time/(double)collections,
    max_collection_time, prof.heapsize_full/MB, prof.free_bytes_full/MB);
#endif
  return 0;
}

Makefile

CC=gcc
CFLAGS=-O3
LIBGC=-lgc
WITHTINYGC=-Itinygc -DGC_FASTCALL= tinygc/tinygc.c

BENCH=/usr/bin/time
PROGRAMS=btree-jemalloc \
         btree-gc btree-gc-inc btree-gc-free \
	 btree-sysmalloc
DEPTH=20

all: $(PROGRAMS)
benchmark: $(PROGRAMS)
	# jemalloc explicit malloc()/free()
	$(BENCH) ./btree-jemalloc $(DEPTH) >/dev/null
	# Boehm GC with four parallel marker threads
	GC_MARKERS=4 $(BENCH) ./btree-gc $(DEPTH) >/dev/null
	# Boehm GC with single-threaded marking
	GC_MARKERS=1 $(BENCH) ./btree-gc $(DEPTH) >/dev/null
	# Boehm GC with explicit deallocation
	GC_MARKERS=1 $(BENCH) ./btree-gc-free $(DEPTH) >/dev/null
	# Boehm GC with incremental collection (single-threaded)
	$(BENCH) ./btree-gc-inc $(DEPTH) >/dev/null
	# System malloc()/free()
	$(BENCH) ./btree-sysmalloc $(DEPTH) >/dev/null

btree-jemalloc: btree.c
	$(CC) $(CFLAGS) -DUSE_JEMALLOC -o $@ $< -ljemalloc -lm
btree-gc: btree.c
	$(CC) $(CFLAGS) -DUSE_BOEHM_GC -o $@ $< $(LIBGC) -lm
btree-gc-free: btree.c
	$(CC) $(CFLAGS) -DUSE_BOEHM_GC -DEXPLICIT_FREE -o $@ $< $(LIBGC) -lm
btree-gc-inc: btree.c
	$(CC) $(CFLAGS) -DUSE_BOEHM_GC -DUSE_INC_GC -o $@ $< $(LIBGC) -lm
btree-sysmalloc: btree.c
	$(CC) $(CFLAGS) -o $@ $< -lm

clean:
	rm -f $(PROGRAMS)
.PHONY: all benchmark

output.txt

$ make benchmark DEPTH=21
# jemalloc explicit malloc()/free()
/usr/bin/time ./btree-jemalloc 21 >/dev/null
       17.53 real        17.40 user         0.11 sys
# Boehm GC with four parallel marker threads
GC_MARKERS=4 /usr/bin/time ./btree-gc 21 >/dev/null
        8.50 real        10.87 user         0.09 sys
# Boehm GC with single-threaded marking
GC_MARKERS=1 /usr/bin/time ./btree-gc 21 >/dev/null
       10.40 real        10.33 user         0.05 sys
# Boehm GC with explicit deallocation
GC_MARKERS=1 /usr/bin/time ./btree-gc-free 21 >/dev/null
       11.75 real        11.70 user         0.04 sys
# Boehm GC with incremental collection (single-threaded)
/usr/bin/time ./btree-gc-inc 21 >/dev/null
       18.39 real        16.40 user         5.11 sys
# System malloc()/free()
/usr/bin/time ./btree-sysmalloc 21 >/dev/null
       64.43 real        63.69 user         0.71 sys