Ubuntu : Intel® Q6600® quad-core
Computer Language Benchmarks Game      [[ Play ]]

- all benchmarks - n-body fannkuch-redux meteor-contest fasta fasta-redux spectral-norm reverse-complement mandelbrot k-nucleotide regex-dna pidigits chameneos-redux thread-ring binary-trees-redux binary-trees - all languages - Ada 2005 GNAT ATS C gcc Clojure C# Mono C++ g++ Dart Erlang HiPE F# Mono Fortran Intel Go Haskell GHC Java 7 Lisp SBCL OCaml Pascal Free Pascal Perl PHP Python 3 Racket Ruby 2.0 Ruby JRuby Scala x86 one core x64 quad-core x86 quad-core x64 one core

 performance measurements

Each table row shows performance measurements for this C gcc program with a particular command-line input value N.

N	CPU secs	Elapsed secs	Memory KB	Code B	≈ CPU Load
60,000	0.04	0.01	?	2863	50% 100% 100% 100%
600,000	0.62	0.23	324	2863	42% 100% 100% 45%
6,000,000	3.10	0.79	568	2863	99% 100% 100% 99%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read chameneos-redux benchmark to see what this program should do.

 notes

gcc (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

 chameneos-redux C gcc #5 program source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/

Contributed by Dmitry Vyukov

Kernel thread is created for each chameneous.
Atomic compare-and-swap primitive is used 
for meeting place state manipulation.
*/

#define _GNU_SOURCE
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>
#include <pthread.h>
#include <sched.h>

#define CPUINFO_FILENAME "/proc/cpuinfo"

#define CL_SIZE 64

void* cache_aligned_malloc(size_t sz)
{
    char*                       mem;
    char*                       res;
    void**                      pos;

    mem = (char*)malloc(sz + 2 * CL_SIZE);
    if (mem == 0)
        exit(1);
    res = (char*)((uintptr_t)(mem + CL_SIZE) & ~(CL_SIZE - 1));
    pos = (void**)(res - sizeof(void*));
    pos[0] = mem;
    return res;
}

void cache_aligned_free(void* res)
{
    void*                       mem;
    void**                      pos;

    assert(((uintptr_t)res & (CL_SIZE - 1)) == 0);
    pos = (void**)((char*)res - sizeof(void*));
    mem = pos[0];
    free(mem);
}

enum color_t
{
    color_blue,
    color_red,
    color_yellow,
};

char const* color_names[] = {"blue", "red", "yellow"};

enum color_t color_complement(enum color_t c1, enum color_t c2)
{
   switch (c1)
   {
   case color_blue:
      switch (c2)
      {
      case color_blue:      return color_blue;
      case color_red:       return color_yellow;
      case color_yellow:    return color_red;
      }
   case color_red:
      switch (c2)
      {
      case color_blue:      return color_yellow;
      case color_red:       return color_red;
      case color_yellow:    return color_blue;
      }
   case color_yellow:
      switch (c2)
      {
      case color_blue:      return color_red;
      case color_red:       return color_blue;
      case color_yellow:    return color_yellow;
      }
   }
   assert(0);
   return 0;
}

void print_colors()
{
    enum color_t                c1;
    enum color_t                c2;
    enum color_t                c3;

    for (c1 = color_blue; c1 <= color_yellow; c1 += 1)
    {
        for (c2 = color_blue; c2 <= color_yellow; c2 += 1)
        {
            c3 = color_complement(c1, c2);
            printf("%s + %s -> %s\n",
                color_names[c1], color_names[c2], color_names[c3]);
        }
    }
    printf("\n");
}

char const* spell_number(size_t n)
{
    static char                 buf [128];
    static char const*          numbers [] = {
        " zero", " one", " two",   " three", " four",
        " five", " six", " seven", " eight", " nine"};

    size_t                      tokens [32];
    size_t                      token_count;
    char const*                 tok;
    char*                       pos;

    token_count = 0;
    do
    {
        tokens[token_count] = n % 10;
        token_count += 1;
        n /= 10;
    }
    while (n);

    pos = buf;
    while (token_count)
    {
        token_count -= 1;
        tok = numbers[tokens[token_count]];
        while (tok[0])
            pos++[0] = tok++[0];
    }
    pos[0] = 0;
    return buf;
}

struct meeting_place_t
{
    uintptr_t volatile          state;
};

#define CHAMENEOS_IDX_MASK      0xFF
#define MEET_COUNT_SHIFT        8

struct chameneos_t
{
    enum color_t                color;
    size_t                      meet_count;
    size_t                      meet_same_count;
    int volatile                meeting_completed;
    struct meeting_place_t*     place;
    struct chameneos_t**        chameneos;
    size_t                      id;
    int                         is_smp;
    pthread_t                   thread;
    pthread_attr_t              thread_attr;
};

void* chameneos_func(void* ctx)
{
    struct chameneos_t*         chameneos;
    struct chameneos_t**        chameneoses;
    struct chameneos_t*         peer;
    size_t                      my_id;
    size_t                      is_same;
    size_t                      spin_count;
    uintptr_t volatile*         state_p;
    uintptr_t                   state;
    uintptr_t                   peer_idx;
    uintptr_t                   xchg;
    uintptr_t                   prev;
    enum color_t                new_color;
    int                         is_smp;

    chameneos = (struct chameneos_t*)ctx;
    chameneoses = chameneos->chameneos;
    state_p = &chameneos->place->state;
    my_id = chameneos->id;
    is_smp = chameneos->is_smp;

    state = state_p[0];
    for (;;)
    {
        peer_idx = state & CHAMENEOS_IDX_MASK;
        if (peer_idx)
            xchg = state - peer_idx - (1 << MEET_COUNT_SHIFT);
        else if (state)
            xchg = state | my_id;
        else
            break;
        prev = __sync_val_compare_and_swap(state_p, state, xchg);
        if (prev == state)
        {
            if (peer_idx)
            {
                is_same = (peer_idx == my_id);
                peer = chameneoses[peer_idx - 1];
                new_color = color_complement(chameneos->color, peer->color);
                peer->color = new_color;
                peer->meet_count += 1;
                peer->meet_same_count += is_same;
                peer->meeting_completed = 1;
                chameneos->color = new_color;
                chameneos->meet_count += 1;
                chameneos->meet_same_count += is_same;
            }
            else
            {
                if (is_smp)
                {
                    spin_count = 20000;
                    while (chameneos->meeting_completed == 0)
                    {
                        if (spin_count)
                            spin_count -= 1;
                        else
                            sched_yield();
                    }
                }
                else
                {
                    while (chameneos->meeting_completed == 0)
                    {
                        sched_yield();
                    }
                }
                chameneos->meeting_completed = 0;
                state = state_p[0];
            }
        }
        else
        {
            state = prev;

        }
    }
    return 0;
}

void get_affinity(int* is_smp, cpu_set_t* affinity1, cpu_set_t* affinity2)
{
    cpu_set_t                   active_cpus;
    FILE*                       f;
    char                        buf [2048];
    char const*                 pos;
    int                         cpu_idx;
    int                         physical_id;
    int                         core_id;
    int                         cpu_cores;
    int                         apic_id;
    size_t                      cpu_count;
    size_t                      i;

    char const*                 processor_str       = "processor";
    size_t                      processor_str_len   = strlen(processor_str);
    char const*                 physical_id_str     = "physical id";
    size_t                      physical_id_str_len = strlen(physical_id_str);
    char const*                 core_id_str         = "core id";
    size_t                      core_id_str_len     = strlen(core_id_str);
    char const*                 cpu_cores_str       = "cpu cores";
    size_t                      cpu_cores_str_len   = strlen(cpu_cores_str);
    
    CPU_ZERO(&active_cpus);
    sched_getaffinity(0, sizeof(active_cpus), &active_cpus);
    cpu_count = 0;
    for (i = 0; i != CPU_SETSIZE; i += 1)
    {
        if (CPU_ISSET(i, &active_cpus))
        {
            cpu_count += 1;
        }
    }

    if (cpu_count == 1)
    {
        is_smp[0] = 0;
        return;
    }

    is_smp[0] = 1;
    CPU_ZERO(affinity1);
    CPU_ZERO(affinity2);

    f = fopen(CPUINFO_FILENAME, "r");

    if (cpu_count < 4 || f == 0)
    {
        for (i = 0; i != CPU_SETSIZE; i += 1)
        {
            if (CPU_ISSET(i, &active_cpus))
            {
                CPU_SET(i, affinity1);
                CPU_SET(i, affinity2);
            }
        }
        return;
    }

    cpu_idx = physical_id = core_id = cpu_cores = -1;
    while (fgets(buf, 2048, f))
    {
        if (0 == strncmp(buf, processor_str, processor_str_len))
        {
            pos = strchr(buf + processor_str_len, ':');
            if (pos)
                cpu_idx = atoi(pos + 1);
        }
        else if (0 == strncmp(buf, physical_id_str, physical_id_str_len))
        {
            pos = strchr(buf + physical_id_str_len, ':');
            if (pos)
                physical_id = atoi(pos + 1);
        }
        else if (0 == strncmp(buf, core_id_str, core_id_str_len))
        {
            pos = strchr(buf + core_id_str_len, ':');
            if (pos)
                core_id = atoi(pos + 1);
        }
        else if (0 == strncmp(buf, cpu_cores_str, cpu_cores_str_len))
        {
            pos = strchr(buf + cpu_cores_str_len, ':');
            if (pos)
                cpu_cores = atoi(pos + 1);
        }
        if (cpu_idx >= 0 && physical_id >= 0 && core_id >= 0 && cpu_cores >= 0)
        {
            apic_id = physical_id * cpu_cores + core_id;
            if (apic_id == 0 || apic_id == 1)
                CPU_SET(cpu_idx, affinity1);
            else if (apic_id == 2 || apic_id == 3)
                CPU_SET(cpu_idx, affinity2);
            cpu_idx = physical_id = core_id = cpu_cores = -1;
        }
    }

    fclose(f);
}

void init_and_start(enum color_t* initial_colors, size_t chameneos_count,
    struct meeting_place_t** place, struct chameneos_t*** chameneos,
    size_t meet_count, int is_smp, cpu_set_t* affinity)
{
    size_t                      i;

    place[0] = (struct meeting_place_t*)
        cache_aligned_malloc(sizeof(struct meeting_place_t));
    place[0]->state = meet_count << MEET_COUNT_SHIFT;
    chameneos[0] = (struct chameneos_t**)
        cache_aligned_malloc(chameneos_count * sizeof(struct chameneos_t*));
    for (i = 0; i != chameneos_count; i += 1)
    {
        chameneos[0][i] = (struct chameneos_t*)
            cache_aligned_malloc(sizeof(struct chameneos_t));
        chameneos[0][i]->place = place[0];
        chameneos[0][i]->chameneos = chameneos[0];
        chameneos[0][i]->id = i + 1;
        chameneos[0][i]->is_smp = is_smp;
        chameneos[0][i]->meet_count = 0;
        chameneos[0][i]->meet_same_count = 0;
        chameneos[0][i]->color = initial_colors[i];
        chameneos[0][i]->meeting_completed = 0;
        if (pthread_attr_init(&chameneos[0][i]->thread_attr))
            exit(1);
        if (is_smp)
            pthread_attr_setaffinity_np(&chameneos[0][i]->thread_attr,
                sizeof(cpu_set_t), affinity);
        if (pthread_create(&chameneos[0][i]->thread,
            &chameneos[0][i]->thread_attr, chameneos_func, chameneos[0][i]))
            exit(1);
    }
}

void join_and_output(enum color_t* initial_colors, size_t chameneos_count,
    struct meeting_place_t* place, struct chameneos_t** chameneos)
{
    size_t                      total_meet_count;
    size_t                      i;

    for (i = 0; i != chameneos_count; i += 1)
        printf(" %s", color_names[initial_colors[i]]);
    printf("\n");

    for (i = 0; i != chameneos_count; i += 1)
    {
        pthread_join(chameneos[i]->thread, 0);
        pthread_attr_destroy(&chameneos[i]->thread_attr);
    }

    total_meet_count = 0;
    for (i = 0; i != chameneos_count; i += 1)
    {
        total_meet_count += chameneos[i]->meet_count;
        printf("%u%s\n", chameneos[i]->meet_count,
            spell_number(chameneos[i]->meet_same_count));
        cache_aligned_free(chameneos[i]);
    }
    printf("%s\n\n", spell_number(total_meet_count));

    cache_aligned_free(chameneos);
    cache_aligned_free(place);
}

int main(int argc, char** argv)
{
    enum color_t                initial_colors1 [] = 
        {color_blue, color_red, color_yellow};

    enum color_t                initial_colors2 [] = 
        {color_blue, color_red, color_yellow, color_red, color_yellow,
        color_blue, color_red, color_yellow, color_red, color_blue};

    struct meeting_place_t*     place1;
    struct chameneos_t**        chameneos1;
    size_t                      chameneos_count1;

    struct meeting_place_t*     place2;
    struct chameneos_t**        chameneos2;
    size_t                      chameneos_count2;

    int                         is_smp;
    cpu_set_t                   affinity1;
    cpu_set_t                   affinity2;
    size_t                      meet_count;

    meet_count = 6000000;
    if (argc > 1 && atoi(argv[1]) > 0)
        meet_count = atoi(argv[1]);

    print_colors();

    get_affinity(&is_smp, &affinity1, &affinity2);

    chameneos_count1 = sizeof(initial_colors1)/sizeof(initial_colors1[0]);
    chameneos_count2 = sizeof(initial_colors2)/sizeof(initial_colors2[0]);

    if (is_smp)
    {
        init_and_start(initial_colors1, chameneos_count1, &place1, &chameneos1, meet_count, is_smp, &affinity1);
        init_and_start(initial_colors2, chameneos_count2, &place2, &chameneos2, meet_count, is_smp, &affinity2);
        join_and_output(initial_colors1, chameneos_count1, place1, chameneos1);
        join_and_output(initial_colors2, chameneos_count2, place2, chameneos2);
    }
    else
    {
        init_and_start(initial_colors1, chameneos_count1, &place1, &chameneos1, meet_count, is_smp, &affinity1);
        join_and_output(initial_colors1, chameneos_count1, place1, chameneos1);
        init_and_start(initial_colors2, chameneos_count2, &place2, &chameneos2, meet_count, is_smp, &affinity2);
        join_and_output(initial_colors2, chameneos_count2, place2, chameneos2);
    }

    return 0;
}

 make, command-line, and program output logs

Sat, 27 Apr 2013 16:04:24 GMT

MAKE:
/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=native -pthread chameneosredux.gcc-5.c -o chameneosredux.gcc-5.gcc_run 
rm chameneosredux.gcc-5.c
0.37s to complete and log all make actions

COMMAND LINE:
./chameneosredux.gcc-5.gcc_run 6000000

PROGRAM OUTPUT:
blue + blue -> blue
blue + red -> yellow
blue + yellow -> red
red + blue -> yellow
red + red -> red
red + yellow -> blue
yellow + blue -> red
yellow + red -> blue
yellow + yellow -> yellow

 blue red yellow
5729684 zero
3202475 zero
3067841 zero
 one two zero zero zero zero zero zero

 blue red yellow red yellow blue red yellow red blue
1408158 zero
1081170 zero
1467523 zero
1151545 zero
1415137 zero
1123063 zero
1100797 zero
1071597 zero
1112605 zero
1068405 zero
 one two zero zero zero zero zero zero

  Home   Conclusions   License   Play