/mobile Handheld Friendly website

 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,0000.090.09?2863  0% 0% 0% 100%
600,0000.790.796642863  1% 0% 1% 100%
6,000,0007.787.786642863  1% 1% 1% 100%

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 version 4.8.1 (Ubuntu/Linaro 4.8.1-10ubuntu8)

 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, 19 Oct 2013 20:20:25 GMT

MAKE:
/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=native -pthread chameneosredux.gcc-5.c -o chameneosredux.gcc-5.gcc_run 
chameneosredux.gcc-5.c: In function ‘join_and_output’:
chameneosredux.gcc-5.c:400:13: warning: format ‘%u’ expects argument of type ‘unsigned int’, but argument 2 has type ‘size_t’ [-Wformat=]
             spell_number(chameneos[i]->meet_same_count));
             ^
rm chameneosredux.gcc-5.c
0.24s 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
3908055 zero
4047289 zero
4044656 zero
 one two zero zero zero zero zero zero

 blue red yellow red yellow blue red yellow red blue
1208260 zero
1213299 zero
1218385 zero
1171493 zero
1172816 zero
1220203 zero
1222155 zero
1229142 zero
1172477 zero
1171770 zero
 one two zero zero zero zero zero zero

Revised BSD license

  Home   Conclusions   License   Play