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
  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;
}

gistfile1.txt

alias Int = ptrdiff_t;

class Node {
  Node left;
  Node right;
  this() {
    left = right = null;
  }
  this (Node left, Node right) {
    this.left = left;
    this.right = right;
  }
  final Int checksum() {
    if (left) {
      return 1 + left.checksum() + right.checksum();
    } else {
      return 1;
    }
  }
}

Node make_tree(Int depth) {
  if (depth > 0)
    return new Node(make_tree(depth - 1), make_tree(depth - 1));
  else
    return new Node(null, null);
}

void delete_tree(out Node node) {
  node = null;
}


void main(string[] args) {
  import std.stdio, std.conv, core.memory;

  Int n = args.length >= 2 ? to!Int(args[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);
  writef("stretch tree of depth %d\t check: %d\n", stretch_depth,
      stretch_tree.checksum());

  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 += current_tree.checksum();
      delete_tree(current_tree);
    }
    writef("%d\t trees of depth %d\t check: %d\n",
      iter, depth, check);
  }
  writef("long lived tree of depth %d\t check: %d\n",
    max_depth, long_lived_tree.checksum());
  auto gc_stats = GC.stats();
  enum MB = 1024 * 1024;
  writefln("%8d MB used", gc_stats.usedSize/MB);
  writefln("%8d MB free", gc_stats.freeSize/MB);
}

Makefile

CC=gcc
DC=ldc2
NIMC=nim cc
CFLAGS=-O3
DFLAGS=-O3 -release
NIMFLAGS=-d:release --hints=off --warnings=off --verbosity=0 --nimcache=nimcache
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-nim btree-nim-boehm \
	 btree-d \
	 btree-sysmalloc \
	 btree-tiny-gc
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
	# Nim reference counting GC
	$(BENCH) ./btree-nim $(DEPTH) >/dev/null
	# Nim with Boehm GC
	$(BENCH) ./btree-nim-boehm $(DEPTH) >/dev/null
	# D garbage collector
	$(BENCH) ./btree-d $(DEPTH) >/dev/null
	# System malloc()/free()
	$(BENCH) ./btree-sysmalloc $(DEPTH) >/dev/null
	# Tiny GC
	$(BENCH) ./btree-tiny-gc $(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-tiny-gc: btree.c
	$(CC) $(CFLAGS) -DUSE_TINY_GC $(WITHTINYGC) -o $@ $< -lm
btree-sysmalloc: btree.c
	$(CC) $(CFLAGS) -o $@ $< -lm
btree-nim: btree.nim
	$(NIMC) $(NIMFLAGS) -o=$@ $<
btree-nim-boehm: btree.nim
	$(NIMC) $(NIMFLAGS) --gc=boehm -o=$@ $<
btree-nim-ms: btree.nim
	$(NIMC) $(NIMFLAGS) --gc=markandsweep -o=$@ $<
btree-d: btree.d
	$(DC) $(DFLAGS) -of=$@ $<

clean:
	rm -rf $(PROGRAMS) btree-d.o nimcache
.PHONY: all benchmark

output.txt

$ make benchmark DEPTH=20
# D garbage collector
/usr/bin/time ./btree-d 20 >/dev/null
       18.10 real        18.00 user         0.10 sys
# jemalloc explicit malloc()/free()
/usr/bin/time ./btree-jemalloc 20 >/dev/null
       10.21 real        10.14 user         0.06 sys
# Boehm GC with four parallel marker threads
GC_MARKERS=4 /usr/bin/time ./btree-gc 20 >/dev/null
        4.47 real         5.49 user         0.09 sys
# Boehm GC with single-threaded marking
GC_MARKERS=1 /usr/bin/time ./btree-gc 20 >/dev/null
        5.38 real         5.34 user         0.04 sys
# Boehm GC with explicit deallocation
GC_MARKERS=1 /usr/bin/time ./btree-gc-free 20 >/dev/null
        6.45 real         6.42 user         0.02 sys
# Boehm GC with incremental collection (single-threaded)
/usr/bin/time ./btree-gc-inc 20 >/dev/null
       10.46 real         8.88 user         3.33 sys
# System malloc()/free()
/usr/bin/time ./btree-sysmalloc 20 >/dev/null
       33.90 real        33.55 user         0.34 sys

$ make benchmark DEPTH=21
# D garbage collector
/usr/bin/time ./btree-d 21 >/dev/null
       34.24 real        33.96 user         0.21 sys
# jemalloc explicit malloc()/free()
/usr/bin/time ./btree-jemalloc 21 >/dev/null
       21.62 real        21.35 user         0.22 sys
# Boehm GC with four parallel marker threads
GC_MARKERS=4 /usr/bin/time ./btree-gc 21 >/dev/null
        9.39 real        12.02 user         0.18 sys
# Boehm GC with single-threaded marking
GC_MARKERS=1 /usr/bin/time ./btree-gc 21 >/dev/null
       11.42 real        11.34 user         0.06 sys
# Boehm GC with explicit deallocation
GC_MARKERS=1 /usr/bin/time ./btree-gc-free 21 >/dev/null
       13.12 real        13.05 user         0.05 sys
# Boehm GC with incremental collection (single-threaded)
/usr/bin/time ./btree-gc-inc 21 >/dev/null
       20.74 real        17.21 user         6.29 sys
# System malloc()/free()
/usr/bin/time ./btree-sysmalloc 21 >/dev/null
       67.73 real        66.97 user         0.74 sys

$ time GC_MARKERS=4 ./btree-gc 23 | tail -5
      88 collections
   0.056 seconds/collection
   0.080 max seconds/collection
     818 MB heap size
     306 MB free bytes
./btree-gc 23  57.50s user 0.91s system 147% cpu 39.695 total