gc.c

// rm a.out; cc -O3 -Wpedantic gc.c; time ./a.out 100000
#include <stdlib.h>

#define DEFAULT_NODE_SIZE 0
#define DEFAULT_ITERATIONS 100000000

struct QueueNode {
  struct QueueNode *next;
  struct QueueNode *prev;
  char *data;
};

struct Queue {
  struct QueueNode *head;
  struct QueueNode *tail;
};

void enqueue(struct Queue *queue, int node_size) {
  struct QueueNode *node = (struct QueueNode*)calloc(1, sizeof(struct QueueNode));
  node->data = (char*)calloc(1, node_size);
  node->prev = queue->tail;
  if (queue->tail == NULL) {
    queue->head = node;
  }
  else {
    queue->tail->next = node;
  }
  queue->tail = node;
}

void dequeue(struct Queue *queue) {
  struct QueueNode *node = queue->head;
  if (node != NULL) {
    queue->head = node->next;
    if (queue->head == NULL) {
      queue->tail = NULL;
    }
    else {
      queue->head->prev = NULL;
    }
    free(node->data);
    free(node);
  }
}

void run_queue(int queue_size, int node_size, long iterations) {
  struct Queue queue = {NULL, NULL};
  int i;
  for (i = 0; i < queue_size; i++) {
    enqueue(&queue, node_size);
  }
  for (i = 0; i < iterations; i++) {
    enqueue(&queue, node_size);
    dequeue(&queue);
  }
}

int main(int argc, char** argv) {

  int queue_size = atoi(argv[1]);
  int node_size = argc > 2 ? atoi(argv[2]) : DEFAULT_NODE_SIZE;
  long iterations = argc > 3 ? atol(argv[3]) : DEFAULT_ITERATIONS;

  run_queue(queue_size, node_size, iterations);

  return 0;
}

gc.java

// rm *.class; javac GC.java; time java GC 100000

class GC {
  static final int DEFAULT_NODE_SIZE = 0;
  static final long DEFAULT_ITERATIONS = 100000000;

  static class QueueNode {
    QueueNode next;
    QueueNode prev;
    byte[] data;
  }

  static class Queue {
    QueueNode head;
    QueueNode tail;
  }

  static void enqueue(Queue queue, int node_size) {
    QueueNode node = new QueueNode();
    node.data = new byte[node_size];
    node.prev = queue.tail;
    if (queue.tail == null) {
      queue.head = node;
    }
    else {
      queue.tail.next = node;
    }
    queue.tail = node;
  }

  static void dequeue(Queue queue) {
    QueueNode node = queue.head;
    if (node != null) {
      queue.head = node.next;
      if (queue.head == null) {
        queue.tail = null;
      }
      else {
        queue.head.prev = null;
      }


    }
  }

  static void run_queue(int queue_size, int node_size, long iterations) {
    Queue queue = new Queue();
    int i;
    for (i = 0; i < queue_size; i++) {
      enqueue(queue, node_size);
    }
    for (i = 0; i < iterations; i++) {
      enqueue(queue, node_size);
      dequeue(queue);
    }
  }

  public static void main(String[] argv) {
    int argc = argv.length;
    int queue_size = Integer.parseInt(argv[0]);
    int node_size = argc > 1 ? Integer.parseInt(argv[1]) : DEFAULT_NODE_SIZE;
    long iterations = argc > 2 ? Long.parseLong(argv[2]) : DEFAULT_ITERATIONS;

    run_queue(queue_size, node_size, iterations);

    return;
  }
}

Notes and Commands

# Note (clue): Exact queue size triggering the problem will depend on your available RAM

# Clean, compile, run C program:
rm a.out; cc -O3 -Wpedantic gc.c; time ./a.out 100000

# Clean, compile, run Java program:
rm *.class; javac GC.java; time java GC 100000

# Clean, compile, run Java program with verbose GC:
rm *.class; javac GC.java; time java -verbose:gc -XX:+PrintGCDetails GC 100000

Output: Misbehaving Java, verbose GC

~/proj/gc (master) $ rm *.class; javac GC.java; time java -verbose:gc -XX:+PrintGCDetails GC 120000
[GC [PSYoungGen: 29952K->4896K(34880K)] 29952K->5032K(114624K), 0.0165590 secs] [Times: user=0.12 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 34848K->4928K(64832K)] 34984K->31664K(144576K), 0.1854460 secs] [Times: user=1.41 sys=0.02, real=0.18 secs] 
[GC [PSYoungGen: 64832K->4928K(64832K)] 91568K->91784K(151872K), 0.3939040 secs] [Times: user=2.99 sys=0.04, real=0.40 secs] 
[Full GC [PSYoungGen: 4928K->0K(64832K)] [ParOldGen: 86856K->4971K(110144K)] 91784K->4971K(174976K) [PSPermGen: 2659K->2657K(21248K)], 0.0391120 secs] [Times: user=0.26 sys=0.00, real=0.03 secs] 
[GC [PSYoungGen: 59904K->4928K(120896K)] 64875K->64459K(231040K), 0.3591040 secs] [Times: user=2.82 sys=0.01, real=0.36 secs] 
[Full GC [PSYoungGen: 4928K->0K(120896K)] [ParOldGen: 59531K->4967K(122944K)] 64459K->4967K(243840K) [PSPermGen: 2657K->2657K(21248K)], 0.0394020 secs] [Times: user=0.27 sys=0.00, real=0.04 secs] 
[GC [PSYoungGen: 115968K->4928K(124736K)] 120935K->121295K(247680K), 0.7426120 secs] [Times: user=5.80 sys=0.02, real=0.75 secs] 
[Full GC [PSYoungGen: 4928K->0K(124736K)] [ParOldGen: 116367K->4967K(166848K)] 121295K->4967K(291584K) [PSPermGen: 2657K->2657K(21248K)], 0.0388510 secs] [Times: user=0.27 sys=0.00, real=0.03 secs] 
[GC [PSYoungGen: 119808K->120032K(327616K)] 124775K->124999K(494464K), 0.7396680 secs] [Times: user=5.68 sys=0.07, real=0.74 secs] 
[GC [PSYoungGen: 317472K->154624K(352064K)] 322439K->322807K(520256K), 2.0615900 secs] [Times: user=16.04 sys=0.12, real=2.06 secs] 
[Full GC [PSYoungGen: 154624K->0K(352064K)] [ParOldGen: 168183K->4971K(210176K)] 322807K->4971K(562240K) [PSPermGen: 2657K->2657K(21248K)], 0.0398480 secs] [Times: user=0.26 sys=0.01, real=0.04 secs] 
[GC [PSYoungGen: 197440K->197728K(425088K)] 202411K->202699K(635264K), 1.2344140 secs] [Times: user=9.39 sys=0.08, real=1.23 secs] 
[GC [PSYoungGen: 410336K->212480K(425088K)] 415307K->415755K(635264K), 2.5896060 secs] [Times: user=19.35 sys=0.04, real=2.59 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 203275K->4971K(250880K)] 415755K->4971K(675968K) [PSPermGen: 2657K->2657K(21248K)], 0.0388880 secs] [Times: user=0.25 sys=0.00, real=0.04 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217763K(675968K), 1.2678070 secs] [Times: user=9.93 sys=0.02, real=1.27 secs] 
[GC [PSYoungGen: 425088K->212480K(425088K)] 430371K->431043K(675968K), 1.2962680 secs] [Times: user=10.18 sys=0.02, real=1.30 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 218563K->4971K(290944K)] 431043K->4971K(716032K) [PSPermGen: 2657K->2657K(21248K)], 0.0271900 secs] [Times: user=0.18 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217755K(716032K), 1.2740270 secs] [Times: user=9.97 sys=0.01, real=1.27 secs] 
[GC [PSYoungGen: 425088K->212480K(425088K)] 430363K->431059K(716032K), 1.2260100 secs] [Times: user=9.03 sys=0.02, real=1.23 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 218579K->4971K(323328K)] 431059K->4971K(748416K) [PSPermGen: 2657K->2657K(21248K)], 0.0260620 secs] [Times: user=0.18 sys=0.00, real=0.03 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217763K(748416K), 1.3319210 secs] [Times: user=9.90 sys=0.02, real=1.33 secs] 
[GC [PSYoungGen: 425088K->212480K(425088K)] 430371K->431075K(748416K), 1.2373690 secs] [Times: user=9.06 sys=0.02, real=1.23 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 218595K->4971K(349568K)] 431075K->4971K(774656K) [PSPermGen: 2657K->2657K(21248K)], 0.0265450 secs] [Times: user=0.17 sys=0.00, real=0.03 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217747K(774656K), 1.2664770 secs] [Times: user=9.82 sys=0.01, real=1.27 secs] 
[GC [PSYoungGen: 425088K->212480K(425088K)] 430355K->431043K(774656K), 1.2775040 secs] [Times: user=9.92 sys=0.01, real=1.28 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 218563K->4971K(370816K)] 431043K->4971K(795904K) [PSPermGen: 2657K->2657K(21248K)], 0.0324790 secs] [Times: user=0.19 sys=0.00, real=0.03 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217763K(795904K), 1.2656260 secs] [Times: user=9.81 sys=0.02, real=1.27 secs] 
[GC [PSYoungGen: 425088K->212480K(425088K)] 430371K->431059K(795904K), 1.2733260 secs] [Times: user=9.77 sys=0.01, real=1.27 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 218579K->4971K(387968K)] 431059K->4971K(813056K) [PSPermGen: 2657K->2657K(21248K)], 0.0275290 secs] [Times: user=0.19 sys=0.00, real=0.03 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217755K(813056K), 1.2739660 secs] [Times: user=9.92 sys=0.02, real=1.28 secs] 
[GC [PSYoungGen: 425088K->212480K(425088K)] 430363K->431035K(813056K), 1.2779290 secs] [Times: user=10.01 sys=0.01, real=1.28 secs] 
[Full GC [PSYoungGen: 212480K->0K(425088K)] [ParOldGen: 218555K->4971K(401920K)] 431035K->4971K(827008K) [PSPermGen: 2657K->2657K(21248K)], 0.0260030 secs] [Times: user=0.17 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 212608K->212480K(425088K)] 217579K->217755K(827008K), 1.2783360 secs] [Times: user=9.88 sys=0.01, real=1.28 secs] 
Heap
 PSYoungGen      total 425088K, used 345171K [0x000000015d080000, 0x0000000183f20000, 0x0000000183f20000)
  eden space 212608K, 62% used [0x000000015d080000,0x0000000165214c48,0x000000016a020000)
  from space 212480K, 100% used [0x0000000176fa0000,0x0000000183f20000,0x0000000183f20000)
  to   space 212480K, 0% used [0x000000016a020000,0x000000016a020000,0x0000000176fa0000)
 ParOldGen       total 401920K, used 5275K [0x000000010f320000, 0x0000000127ba0000, 0x000000015d080000)
  object space 401920K, 1% used [0x000000010f320000,0x000000010f846e00,0x0000000127ba0000)
 PSPermGen       total 21248K, used 2664K [0x000000010a120000, 0x000000010b5e0000, 0x000000010f320000)
  object space 21248K, 12% used [0x000000010a120000,0x000000010a3ba280,0x000000010b5e0000)

real	0m27.761s
user	3m15.596s
sys	0m0.785s

Output: Well-behaved Java, verbose GC

~/proj/gc (master) $ rm *.class; javac GC.java; time java -verbose:gc -XX:+PrintGCDetails GC 100000
[GC [PSYoungGen: 29952K->4336K(34880K)] 29952K->4336K(114624K), 0.0146390 secs] [Times: user=0.09 sys=0.01, real=0.02 secs] 
[GC [PSYoungGen: 34288K->4336K(64832K)] 34288K->4336K(144576K), 0.0158910 secs] [Times: user=0.11 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 64240K->4336K(64832K)] 64240K->4336K(144576K), 0.0140500 secs] [Times: user=0.11 sys=0.00, real=0.01 secs] 
[GC [PSYoungGen: 64240K->4320K(124736K)] 64240K->4320K(204480K), 0.0144240 secs] [Times: user=0.11 sys=0.01, real=0.01 secs] 
[GC [PSYoungGen: 124128K->4336K(124736K)] 124128K->4336K(204480K), 0.0131980 secs] [Times: user=0.09 sys=0.01, real=0.01 secs] 
[GC [PSYoungGen: 124144K->4304K(243968K)] 124144K->4304K(323712K), 0.0138140 secs] [Times: user=0.10 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 243920K->4064K(243968K)] 243920K->4388K(323712K), 0.0151000 secs] [Times: user=0.10 sys=0.00, real=0.01 secs] 
[GC [PSYoungGen: 243680K->4032K(483584K)] 244004K->4356K(563328K), 0.0144300 secs] [Times: user=0.10 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 483200K->4064K(483648K)] 483524K->4388K(563392K), 0.0140180 secs] [Times: user=0.10 sys=0.00, real=0.01 secs] 
[GC [PSYoungGen: 483232K->4032K(633088K)] 483556K->4356K(712832K), 0.0140210 secs] [Times: user=0.11 sys=0.01, real=0.01 secs] 
[GC [PSYoungGen: 632640K->4064K(633088K)] 632964K->4388K(712832K), 0.0133190 secs] [Times: user=0.09 sys=0.00, real=0.01 secs] 
[GC [PSYoungGen: 632672K->4032K(633088K)] 632996K->4356K(712832K), 0.0128630 secs] [Times: user=0.09 sys=0.00, real=0.02 secs] 
[GC [PSYoungGen: 632640K->4000K(633088K)] 632964K->4324K(712832K), 0.0127500 secs] [Times: user=0.10 sys=0.00, real=0.01 secs] 
Heap
 PSYoungGen      total 633088K, used 193787K [0x0000000161210000, 0x00000001880b0000, 0x00000001880b0000)
  eden space 628608K, 30% used [0x0000000161210000,0x000000016cb66f88,0x00000001877f0000)
  from space 4480K, 89% used [0x00000001877f0000,0x0000000187bd8000,0x0000000187c50000)
  to   space 4480K, 0% used [0x0000000187c50000,0x0000000187c50000,0x00000001880b0000)
 ParOldGen       total 79744K, used 324K [0x00000001134b0000, 0x0000000118290000, 0x0000000161210000)
  object space 79744K, 0% used [0x00000001134b0000,0x0000000113501060,0x0000000118290000)
 PSPermGen       total 21248K, used 2666K [0x000000010e2b0000, 0x000000010f770000, 0x00000001134b0000)
  object space 21248K, 12% used [0x000000010e2b0000,0x000000010e54aa30,0x000000010f770000)

real	0m2.941s
user	0m3.821s
sys	0m0.292s