C versus CPP versus Java; the performance failings of naive OO

Chain.java

//package com.dnene.josephus;

// $ javac Person.java Chain.java && java Chain

public class Chain
{
    private Person first = null;

    public Chain(int size)
    {
        Person last = null;
        Person current = null;
        for (int i = 0 ; i < size ; i++)
        {
            current = new Person(i);
            if (first == null) first = current;
            if (last != null)
            {
                last.setNext(current);
                current.setPrev(last);
            }
            last = current;
        }
        first.setPrev(last);
        last.setNext(first);
    }

    public Person kill(int nth)
    {
        Person current = first;
        int shout = 1;
        while(current.getNext() != current)
        {
            shout = current.shout(shout, nth);
            current = current.getNext();
        }
        first = current;
        return current;
    }

    public Person getFirst()
    {
        return first;
    }
    public static void main(String[] args)
    {
        int ITER = Integer.parseInt(System.getenv("ITERATIONS")); // 1000000;
        int personCount = Integer.parseInt(System.getenv("PERSON_COUNT")); // 40;
        Person last = null;
        long start = System.nanoTime();
        for (int i = 0 ; i < ITER ; i++)
        {
            Chain chain = new Chain(personCount);
            last = chain.kill(3);

        }
        long end = System.nanoTime();
        double seconds = ((double)(end - start) / 1000000000);
        System.out.format("Java: Time for %d iterations = %.9f seconds\n", ITER, seconds);
        System.out.format("Java: Time iteration = %.9f seconds\n", seconds / ITER);
        System.out.format("Java: Last man standing is # %d out of %d\n", last.getCount() + 1, personCount);
    }
}

mem-alloc-overhead-fixed.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
//01 modify bignotti alberto 2008-08-18
#include <stack>
#include <assert.h>

// $ g++ -O3 -o mem-alloc-overhead-fixed mem-alloc-overhead-fixed.cpp && ./mem-alloc-overhead-fixed

class Person;
typedef std::stack<Person*> SaveArea;

class Person
{

    public:

        Person(int count) : _next(NULL), _prev(NULL) { _count = count; }
    //02 modify bignotti alberto 2008-08-18
    void reset(int count)
    {
        _next=_prev=NULL;
        _count=count;
    }
        int shout(int shout, int nth)
        {
            if (shout < nth) return (shout + 1);
            _prev->_next = _next;


            _next->_prev = _prev;
            return 1;
        }
        int count() { return _count; }
        Person* next() { return _next; }
        void next(Person* person) { this->_next = person ; }
        Person* prev() { return _prev; }
        void prev(Person* person) { this->_prev = person; }
    private:
        int _count;
        Person* _next;
        Person* _prev;
};

class Chain
{
    public:
        //03 modify bignotti alberto 2008-08-18
        Chain(int size,SaveArea& reusePersons) : _first(NULL)
        {
            Person* current = NULL;
            Person* last = NULL;
            for(int i = 0 ; i < size ; i++)
            {
                if(! reusePersons.empty() )
                {
                    current = reusePersons.top();
                    current->reset(i);
                    reusePersons.pop();
                }
                else
                    current = new Person(i);
                if (_first == NULL) _first = current;
                if (last != NULL)
                {
                    last->next(current);
                    current->prev(last);
                }
                last = current;
            }
            _first->prev(last);
            last->next(_first);
        }
        //04 modify bignotti alberto 2008-08-18
    Person* kill(int nth,SaveArea& reusePersons)
        {
            Person* current = _first;
            int shout = 1;
            while(current->next() != current)
            {
                Person* tmp = current;
                shout = current->shout(shout,nth);
                current = current->next();
                if (shout == 1)
                {
                    //delete tmp;
                    reusePersons.push(tmp);
                }
            }
            _first = current;
            return current;
        }
        Person* first() { return _first; }
    private:
        Person* _first;
};

double get_time_in_seconds(void)
{
    struct timeval tv;
    assert(gettimeofday(&tv, NULL) >= 0);
    return (double)tv.tv_sec + 1.e-6 * (double)tv.tv_usec;
}

int main(int argc, char** argv)
{
    int ITER = atoi(getenv("ITERATIONS")); // 1000000;
    int personCount = atoi(getenv("PERSON_COUNT")); //40;
    Chain* chain;
    Person* last;
    double start = get_time_in_seconds();

    SaveArea reusePersons;

    for(int i = 0 ; i < ITER ; i++)
    {
        chain = new Chain(personCount, reusePersons);
        last = chain->kill(3, reusePersons);

        delete chain;
    }

    while(!reusePersons.empty())
    {
        free(reusePersons.top());
        reusePersons.pop();
    }

    double end = get_time_in_seconds();
    fprintf(stdout,"CPP: Fixed: Time for %u iterations = %f seconds\n", ITER, end - start);
    fprintf(stdout,"CPP: Fixed: Time per iteration = %.9f seconds\n", (end - start) / ITER);
    fprintf(stdout,"CPP: Fixed: Last man standing is # %d out of %d\n", (last->count() + 1), personCount);
    return 0;
}

mem-alloc-overhead.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <assert.h>

// $ # see http://blog.dhananjaynene.com/2008/07/performance-comparison-c-java-python-ruby-jython-jruby-groovy/
// $ gcc -O3 -o mem-alloc-overhead mem-alloc-overhead.c && ./mem-alloc-overhead

double get_time_in_seconds(void)
{
    struct timeval tv;
    assert(gettimeofday(&tv, NULL) >= 0);
    return (double)tv.tv_sec + 1.e-6 * (double)tv.tv_usec;
}

typedef struct PERSON {
    int next;
    int prev;
} PERSON;

PERSON * person;
int      person_first;
int      person_used;

int new_person(int count)
{
    //printf("- new_person(count=%d)\n", count);
    person_used ++;
    return person_used;
}

int person_shout(int shout, int nth, int person_current)
{
    if (shout < nth) { /* printf("- %d = person_shout(shout=%d, nth=%d, %2d=person_current)\n", shout + 1, shout, nth, person_current); */ return (shout + 1); }
    //printf("- 1 = person_shout(shout=%d, nth=%d, %2d=person_current) // killed!\n", shout, nth, person_current);
    int next = person[person_current].next;
    int prev = person[person_current].prev;
    person[prev].next = next;
    person[next].prev = prev;
    return 1;
}

void new_chain(int size)
{
    //printf("- new_chain(size=%d)\n", size);
    person_first = -1;
    person_used  = -1;
    int person_last = -1;
    for(int i = 0 ; i < size ; i++)
    {
        int person_current = new_person(i);
        person_first = -1 == person_first ? person_current : person_first;
        if (-1 != person_last)
        {
            person[person_last].next    = person_current;
            person[person_current].prev = person_last;
        }
        person_last = person_current;
    }
    person[person_first].prev = person_last;
}

int chain_kill(int nth)
{
    int person_current = person_first;
    int shout = 1;
    //printf("- chain_kill(nth=%d) // loop until 1 person alive!\n", nth);
    while (person[person_current].next != person_current)
    {
        shout = person_shout(shout, nth, person_current);
        person_current = person[person_current].next;
    }
    //printf("- chain_kill(nth=%d) // person alive is %d!\n", nth, person_current);
    person_first = person_current;
    return person_current;
}

int main(int argc, char** argv)
{
    int ITER = atoi(getenv("ITERATIONS")); // 1000000;
    int person_count = atoi(getenv("PERSON_COUNT")); //40;
    person = malloc(sizeof(PERSON) * person_count);
    double start = get_time_in_seconds();
    for(int i = 0 ; i < ITER ; i++)
    {
        new_chain(person_count);
        chain_kill(3);
    }
    double end = get_time_in_seconds();
    fprintf(stdout,"C: Array: Time for %u iterations = %f seconds\n", ITER, end - start);
    fprintf(stdout,"C: Array: Time per iteration = %.9f seconds\n", (end - start) / ITER);
    fprintf(stdout,"C: Array: Last man standing is # %d out of %d\n", person_first + 1, person_count);
    //for(int i = 0 ; i < person_count ; i++)
    //{
    //    printf("- %2d=prev %2d=person %2d=next; %2d=person_first\n", person[i].prev, i, person[i].next, person_first);
    //}
    return 0;
}

mem-alloc-overhead.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <assert.h>

// $ g++ -O3 -o mem-alloc-overhead mem-alloc-overhead.cpp && ./mem-alloc-overhead

class Person
{

    public:

        Person(int count) : _next(NULL), _prev(NULL) { _count = count; }
        int shout(int shout, int nth)
        {
            if (shout < nth) return (shout + 1);
            _prev->_next = _next;


            _next->_prev = _prev;
            return 1;
        }
        int count() { return _count; }
        Person* next() { return _next; }
        void next(Person* person) { this->_next = person ; }
        Person* prev() { return _prev; }
        void prev(Person* person) { this->_prev = person; }
    private:
        int _count;
        Person* _next;
        Person* _prev;
};

class Chain
{
    public:
        Chain(int size) : _first(NULL)
        {
            Person* current = NULL;
            Person* last = NULL;
            for(int i = 0 ; i < size ; i++)
            {
                current = new Person(i);
                if (_first == NULL) _first = current;
                if (last != NULL)
                {
                    last->next(current);
                    current->prev(last);
                }
                last = current;
            }
            _first->prev(last);
            last->next(_first);
        }
        Person* kill(int nth)
        {
            Person* current = _first;
            int shout = 1;
            while(current->next() != current)
            {
                Person* tmp = current;
                shout = current->shout(shout,nth);
                current = current->next();
                if (shout == 1)
                {
                    delete tmp;
                }
            }
            _first = current;
            return current;
        }
        Person* first() { return _first; }
    private:
        Person* _first;
};

double get_time_in_seconds(void)
{
    struct timeval tv;
    assert(gettimeofday(&tv, NULL) >= 0);
    return (double)tv.tv_sec + 1.e-6 * (double)tv.tv_usec;
}

int main(int argc, char** argv)
{
    int ITER = atoi(getenv("ITERATIONS")); // 1000000;
    int personCount = atoi(getenv("PERSON_COUNT")); //40;
    Chain* chain;
    Person* last;
    double start = get_time_in_seconds();
    for(int i = 0 ; i < ITER ; i++)
    {
        chain = new Chain(personCount);
        last = chain->kill(3);

        delete chain;
    }
    double end = get_time_in_seconds();
    fprintf(stdout,"CPP: Dynamic: Time for %u iterations = %f seconds\n", ITER, end - start);
    fprintf(stdout,"CPP: Dynamic: Time per iteration = %.9f seconds\n", (end - start) / ITER);
    fprintf(stdout,"CPP: Dynamic: Last man standing is # %d out of %d\n", last->count() + 1, personCount);
    return 0;
}

Person.java

//package com.dnene.josephus;

public class Person
{
    int count;
    private Person prev = null;
    private Person next = null;

    public Person(int count)
    {
        this.count = count;
    }

    public int shout(int shout, int deadif)
    {
        if (shout < deadif) return (shout + 1);
        this.getPrev().setNext(this.getNext());
        this.getNext().setPrev(this.getPrev());
        return 1;
    }

    public int getCount()
    {
        return this.count;
    }

    public Person getPrev()
    {
        return prev;
    }

    public void setPrev(Person prev)
    {
        this.prev = prev;
    }

    public Person getNext()
    {
        return next;
    }

    public void setNext(Person next)

    {
        this.next = next;
    }
}

result-summary.txt

| 10M interation /  40  person |  wallclock |    RSS KB | Minor faults | User s | Sys S | Notes                 |
|                      C Array |   2.595171 |     1,516 |           61 |   2.59 | 0.00  |                       |
|                    CPP Fixed |   3.060870 |   315,388 |       78,238 |   2.94 | 0.12  |                       |
|                   Java GC +n |   4.143983 |   361,680 |       86,489 |   4.12 | 0.15  | default GC            |
|                   Java GC +1 |   4.142188 |   362,224 |       86,717 |   4.11 | 0.11  | best GC               |
|              Java GC +serial |   4.138099 |    45,020 |        7,869 |   4.19 | 0.03  | best GC               |
|                  CPP Dynamic |  10.061743 |   315,392 |       78,238 |   9.98 | 0.08  |                       |

|  40 interation /  10M person |  wallclock |    RSS KB | Minor faults | User s | Sys S | Notes                 |
|                      C Array |   5.523370 |    79,748 |       19,595 |   5.50 | 0.01  | 1 thread              |
|                    CPP Fixed | 153.253313 |   396,568 |       99,090 | 153.11 | 0.14  | 1 thread              |
|                   Java GC +n |  50.260279 | 1,023,508 |      263,613 | 261.25 | 5.78  | 8 threads, default GC |
|                   Java GC +1 |  59.405543 |   979,616 |      247,019 |  59.12 | 0.34  | 2 threads             |
|              Java GC +serial |  41.308497 |   736,492 |      474,564 |  40.82 | 0.59  | 2 threads, best GC    |
|                  CPP Dynamic | 186.309237 |   315,448 |       78,237 | 189.17 | 0.10  | 1 thread              |

|  40 interation /   1M person |  wallclock |    RSS KB | Minor faults | User s | Sys S | Notes                 |
|                      C Array |   0.479585 |     9,280 |        2,015 |   0.47 | 0.00  | 1 thread              |
|                    CPP Fixed |  11.307122 |    42,064 |        9,999 |  11.26 | 0.03  | 1 thread              |
|                   Java GC +n |   1.364553 |   213,592 |       49,596 |   2.75 | 0.08  | 8 threads, default GC |
|                   Java GC +1 |   1.570767 |   237,088 |       55,495 |   1.59 | 0.08  | 2 threads, best GC    |
|              Java GC +serial |   2.939497 |   102,084 |       37,878 |   2.95 | 0.07  | 2 threads             |
|                  CPP Dynamic |  14.820864 |    33,988 |        7,922 |  14.99 | 0.01  | 1 thread              |

|  40 interation / 100k person |  wallclock |    RSS KB | Minor faults | User s | Sys S | Notes                 |
|                      C Array |   0.038181 |     2,248 |          258 |   0.03 | 0.00  | 1 thread              |
|                    CPP Fixed |   0.236402 |     6,836 |        2,181 |   0.23 | 0.00  | 1 thread              |
|                   Java GC +n |   0.096783 |    63,660 |       11,945 |   0.19 | 0.01  | 8 threads, default GC |
|                   Java GC +1 |   0.105271 |    63,360 |       11,855 |   0.17 | 0.02  | 2 threads, best GC    |
|              Java GC +serial |   0.097546 |    47,780 |        8,054 |   0.17 | 0.02  | 2 threads, best GC    |
|                  CPP Dynamic |   0.307559 |     6,072 |          893 |   0.31 | 0.00  | 1 thread              |

ubuntu-vm-on-macbook.txt

$ # Results for 40 persons and 10 million iterations

$ gcc -O3 -o mem-alloc-overhead mem-alloc-overhead.c && (export ITERATIONS=10000000 ; export PERSON_COUNT=40 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(C:|Max|User|System|page|context)")
C: Array: Time for 10000000 iterations = 2.595171 seconds
C: Array: Time per iteration = 0.000000260 seconds
C: Array: Last man standing is # 28 out of 40
        User time (seconds): 2.59
        System time (seconds): 0.00
        Maximum resident set size (kbytes): 1516
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 61
        Voluntary context switches: 1
        Involuntary context switches: 180

$ g++ -O3 -o mem-alloc-overhead-fixed mem-alloc-overhead-fixed.cpp && (export ITERATIONS=10000000 ; export PERSON_COUNT=40 ; /usr/bin/time -v ./mem-alloc-overhead-fixed 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Fixed: Time for 10000000 iterations = 3.060870 seconds
CPP: Fixed: Time per iteration = 0.000000306 seconds
CPP: Fixed: Last man standing is # 28 out of 40
        User time (seconds): 2.94
        System time (seconds): 0.12
        Maximum resident set size (kbytes): 315388
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 78238
        Voluntary context switches: 1
        Involuntary context switches: 11

$ javac Person.java Chain.java && (export ITERATIONS=10000000 ; export PERSON_COUNT=40 ; /usr/bin/time -v java Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 10000000 iterations = 4.143983493 seconds
Java: Time iteration = 0.000000414 seconds
Java: Last man standing is # 28 out of 40
        User time (seconds): 4.12
        System time (seconds): 0.15
        Maximum resident set size (kbytes): 361680
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 86489
        Voluntary context switches: 1554
        Involuntary context switches: 653

$ javac Person.java Chain.java && (export ITERATIONS=10000000 ; export PERSON_COUNT=40 ; /usr/bin/time -v java -XX:ParallelGCThreads=1 Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 10000000 iterations = 4.142188205 seconds
Java: Time iteration = 0.000000414 seconds
Java: Last man standing is # 28 out of 40
        User time (seconds): 4.11
        System time (seconds): 0.11
        Maximum resident set size (kbytes): 362224
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 86717
        Voluntary context switches: 920
        Involuntary context switches: 558

$ javac Person.java Chain.java && (export ITERATIONS=10000000 ; export PERSON_COUNT=40 ; /usr/bin/time -v java -XX:+UseSerialGC Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 10000000 iterations = 4.138099093 seconds
Java: Time iteration = 0.000000414 seconds
Java: Last man standing is # 28 out of 40
        User time (seconds): 4.19
        System time (seconds): 0.03
        Maximum resident set size (kbytes): 45020
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 7869
        Voluntary context switches: 3025
        Involuntary context switches: 2529

$ g++ -O3 -o mem-alloc-overhead mem-alloc-overhead.cpp && (export ITERATIONS=10000000 ; export PERSON_COUNT=40 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Dynamic: Time for 10000000 iterations = 10.061743 seconds
CPP: Dynamic: Time per iteration = 0.000001006 seconds
CPP: Dynamic: Last man standing is # 28 out of 40
        User time (seconds): 9.98
        System time (seconds): 0.08
        Maximum resident set size (kbytes): 315392
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 78238
        Voluntary context switches: 1
        Involuntary context switches: 49

$ # Results for 10 million persons and 40 iterations

$ gcc -O3 -o mem-alloc-overhead mem-alloc-overhead.c && (export ITERATIONS=40 ; export PERSON_COUNT=10000000 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(C:|Max|User|System|page|context)")
C: Array: Time for 40 iterations = 5.523370 seconds
C: Array: Time per iteration = 0.138084251 seconds
C: Array: Last man standing is # 3093013 out of 10000000
        User time (seconds): 5.50
        System time (seconds): 0.01
        Maximum resident set size (kbytes): 79748
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 19595
        Voluntary context switches: 1
        Involuntary context switches: 10

$ g++ -O3 -o mem-alloc-overhead-fixed mem-alloc-overhead-fixed.cpp && (export ITERATIONS=40 ; export PERSON_COUNT=10000000 ; /usr/bin/time -v ./mem-alloc-overhead-fixed 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Fixed: Time for 40 iterations = 153.253313 seconds
CPP: Fixed: Time per iteration = 3.831332821 seconds
CPP: Fixed: Last man standing is # 3093025 out of 10000000
        User time (seconds): 153.11
        System time (seconds): 0.14
        Maximum resident set size (kbytes): 396568
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 99090
        Voluntary context switches: 1
        Involuntary context switches: 258

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=10000000 ; /usr/bin/time -v java Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 50.260279144 seconds
Java: Time iteration = 1.256506979 seconds
Java: Last man standing is # 3093025 out of 10000000
        User time (seconds): 261.25
        System time (seconds): 5.78
        Maximum resident set size (kbytes): 1023508
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 263613
        Voluntary context switches: 4634
        Involuntary context switches: 17885

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=10000000 ; /usr/bin/time -v java -XX:ParallelGCThreads=1 Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 59.405543721 seconds
Java: Time iteration = 1.485138593 seconds
Java: Last man standing is # 3093025 out of 10000000
        User time (seconds): 59.12
        System time (seconds): 0.34
        Maximum resident set size (kbytes): 979616
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 247019
        Voluntary context switches: 2016
        Involuntary context switches: 1598

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=10000000 ; /usr/bin/time -v java -XX:+UseSerialGC Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 41.308497086 seconds
Java: Time iteration = 1.032712427 seconds
Java: Last man standing is # 3093025 out of 10000000
        User time (seconds): 40.82
        System time (seconds): 0.59
        Maximum resident set size (kbytes): 736492
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 474564
        Voluntary context switches: 1318
        Involuntary context switches: 986

$ g++ -O3 -o mem-alloc-overhead mem-alloc-overhead.cpp && (export ITERATIONS=40 ; export PERSON_COUNT=10000000 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Dynamic: Time for 40 iterations = 186.309237 seconds
CPP: Dynamic: Time per iteration = 4.657730925 seconds
CPP: Dynamic: Last man standing is # 3093025 out of 10000000
        User time (seconds): 189.17
        System time (seconds): 0.10
        Maximum resident set size (kbytes): 315448
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 78237
        Voluntary context switches: 1
        Involuntary context switches: 178

$ # Results for 1 million persons and 40 iterations

$ gcc -O3 -o mem-alloc-overhead mem-alloc-overhead.c && (export ITERATIONS=40 ; export PERSON_COUNT=1000000 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(C:|Max|User|System|page|context)")
C: Array: Time for 40 iterations = 0.479585 seconds
C: Array: Time per iteration = 0.011989623 seconds
C: Array: Last man standing is # 637792 out of 1000000
        User time (seconds): 0.47
        System time (seconds): 0.00
        Maximum resident set size (kbytes): 9280
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 2015
        Voluntary context switches: 1
        Involuntary context switches: 28

$ g++ -O3 -o mem-alloc-overhead-fixed mem-alloc-overhead-fixed.cpp && (export ITERATIONS=40 ; export PERSON_COUNT=1000000 ; /usr/bin/time -v ./mem-alloc-overhead-fixed 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Fixed: Time for 40 iterations = 11.307122 seconds
CPP: Fixed: Time per iteration = 0.282678050 seconds
CPP: Fixed: Last man standing is # 637798 out of 1000000
        User time (seconds): 11.26
        System time (seconds): 0.03
        Maximum resident set size (kbytes): 42064
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 9999
        Voluntary context switches: 1
        Involuntary context switches: 380

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=1000000 ; /usr/bin/time -v java Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 1.364553010 seconds
Java: Time iteration = 0.034113825 seconds
Java: Last man standing is # 637798 out of 1000000
        User time (seconds): 2.75
        System time (seconds): 0.08
        Maximum resident set size (kbytes): 213592
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 49596
        Voluntary context switches: 717
        Involuntary context switches: 1512

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=1000000 ; /usr/bin/time -v java -XX:ParallelGCThreads=1 Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 1.570767788 seconds
Java: Time iteration = 0.039269195 seconds
Java: Last man standing is # 637798 out of 1000000
        User time (seconds): 1.59
        System time (seconds): 0.08
        Maximum resident set size (kbytes): 237088
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 55495
        Voluntary context switches: 391
        Involuntary context switches: 91

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=1000000 ; /usr/bin/time -v java -XX:+UseSerialGC Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 2.939497528 seconds
Java: Time iteration = 0.073487438 seconds
Java: Last man standing is # 637798 out of 1000000
        User time (seconds): 2.95
        System time (seconds): 0.07
        Maximum resident set size (kbytes): 102084
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 37878
        Voluntary context switches: 407
        Involuntary context switches: 73

$ g++ -O3 -o mem-alloc-overhead mem-alloc-overhead.cpp && (export ITERATIONS=40 ; export PERSON_COUNT=1000000 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Dynamic: Time for 40 iterations = 14.820864 seconds
CPP: Dynamic: Time per iteration = 0.370521599 seconds
CPP: Dynamic: Last man standing is # 637798 out of 1000000
        User time (seconds): 14.99
        System time (seconds): 0.01
        Maximum resident set size (kbytes): 33988
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 7922
        Voluntary context switches: 1
        Involuntary context switches: 34

$ # Results for 100k persons and 40 iterations

$ gcc -O3 -o mem-alloc-overhead mem-alloc-overhead.c && (export ITERATIONS=40 ; export PERSON_COUNT=100000 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(C:|Max|User|System|page|context)")
C: Array: Time for 40 iterations = 0.038181 seconds
C: Array: Time per iteration = 0.000954521 seconds
C: Array: Last man standing is # 91912 out of 100000
        User time (seconds): 0.03
        System time (seconds): 0.00
        Maximum resident set size (kbytes): 2248
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 258
        Voluntary context switches: 1
        Involuntary context switches: 8

$ g++ -O3 -o mem-alloc-overhead-fixed mem-alloc-overhead-fixed.cpp && (export ITERATIONS=40 ; export PERSON_COUNT=100000 ; /usr/bin/time -v ./mem-alloc-overhead-fixed 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Fixed: Time for 40 iterations = 0.236402 seconds
CPP: Fixed: Time per iteration = 0.005910051 seconds
CPP: Fixed: Last man standing is # 92620 out of 100000
        User time (seconds): 0.23
        System time (seconds): 0.00
        Maximum resident set size (kbytes): 6836
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 2181
        Voluntary context switches: 1
        Involuntary context switches: 0

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=100000 ; /usr/bin/time -v java Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 0.096783994 seconds
Java: Time iteration = 0.002419600 seconds
Java: Last man standing is # 92620 out of 100000
        User time (seconds): 0.19
        System time (seconds): 0.01
        Maximum resident set size (kbytes): 63660
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 11945
        Voluntary context switches: 381
        Involuntary context switches: 114

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=100000 ; /usr/bin/time -v java -XX:ParallelGCThreads=1 Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 0.105271219 seconds
Java: Time iteration = 0.002631780 seconds
Java: Last man standing is # 92620 out of 100000
        User time (seconds): 0.17
        System time (seconds): 0.02
        Maximum resident set size (kbytes): 63360
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 11855
        Voluntary context switches: 292
        Involuntary context switches: 32

$ javac Person.java Chain.java && (export ITERATIONS=40 ; export PERSON_COUNT=100000 ; /usr/bin/time -v java -XX:+UseSerialGC Chain 2>&1 | egrep "(Java:|Max|User|System|page|context)")
Java: Time for 40 iterations = 0.097546259 seconds
Java: Time iteration = 0.002438656 seconds
Java: Last man standing is # 92620 out of 100000
        User time (seconds): 0.17
        System time (seconds): 0.02
        Maximum resident set size (kbytes): 47780
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 8054
        Voluntary context switches: 269
        Involuntary context switches: 27

$ g++ -O3 -o mem-alloc-overhead mem-alloc-overhead.cpp && (export ITERATIONS=40 ; export PERSON_COUNT=100000 ; /usr/bin/time -v ./mem-alloc-overhead 2>&1 | egrep "(CPP:|Max|User|System|page|context)")
CPP: Dynamic: Time for 40 iterations = 0.307559 seconds
CPP: Dynamic: Time per iteration = 0.007688975 seconds
CPP: Dynamic: Last man standing is # 92620 out of 100000
        User time (seconds): 0.31
        System time (seconds): 0.00
        Maximum resident set size (kbytes): 6072
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 893
        Voluntary context switches: 1
        Involuntary context switches: 2

Fast and small pure C implementation:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

struct person {
	struct person *next;
};

int kill(int size, int nth)
{
	struct person *chain_array;
	struct person *cur, *last, *prev;
	int n;

	if (size == 1)
		return 0;

	chain_array = malloc(sizeof(*chain_array) * size);
	if (chain_array == NULL)
		return -1;

	last = chain_array + size - 1;
	for(cur = chain_array; cur < last; cur++ )
		cur->next = cur + 1;
	cur->next = chain_array;

	n = nth;
	prev = last;
	cur = chain_array;
	while(1) {
		if (!--n) {
			cur = cur->next;
			if (prev == cur)
				break;

			prev->next = cur;
			n = nth;
			continue;
		}

		prev = cur;
		cur = cur->next;
	}

	free(chain_array);
	return cur - chain_array;
}

#define ITER 1000000

int main(void)
{
	int last;
        struct timeval start, end, delta;

        gettimeofday(&start, NULL);
        for (int i = 0 ; i < ITER ; i++){
		last = kill(40, 3);
        }
        gettimeofday(&end, NULL);

	timersub(&end, &start, &delta);

        fprintf(stdout, "Time = %d microseconds\n",
		(int) (delta.tv_sec * 1000000 + delta.tv_usec));

        fprintf(stdout,"Last man standing is %d\n", last + 1);

	return 0;
}