k-nucleotide C gcc #5 program | Computer Language Benchmarks Game

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
250,000	0.76	0.25	660	2519	96% 67% 63% 84%
2,500,000	5.81	2.07	58,424	2519	99% 46% 88% 49%
25,000,000	56.66	19.51	282,036	2519	99% 97% 47% 48%

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

Read k-nucleotide benchmark to see what this program should do.

notes

gcc (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

Is mmap_stdin really line-by-line?

k-nucleotide C gcc #5 program source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/
 
   Based on bit encoding idea of C++ contribution of Andrew Moon
   Copy task division idea from Java entry, contributed by James McIlree
   Contributed by Petr Prokhorenkov
*/

//#include "simple_hash3.h"

#include <ctype.h>
#include <malloc.h>
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#define HT_SIZE 1000000

typedef unsigned char uint8_t;

/* Thread pool implementation */

struct tp_entry {
    void *job;
    void *param;
};

struct tp {
    struct tp_entry *jobs;
    int capacity;
    int size;
    pthread_mutex_t mutex;
};

struct tp *
tp_create(int max_jobs) {
    struct tp *pool = malloc(sizeof(*pool));

    pool->jobs = malloc(sizeof(struct tp_entry)*max_jobs);
    pool->capacity = max_jobs;
    pool->size = 0;
    pthread_mutex_init(&pool->mutex, 0);

    return pool;
}

void
tp_destroy(struct tp *pool) {
    free(pool->jobs);
    pthread_mutex_destroy(&pool->mutex);
    free(pool);
}

void
tp_add_job(struct tp *pool, void *job, void *param) {
    if (pool->size < pool->capacity) {
        pool->jobs[pool->size].job = job;
        pool->jobs[pool->size].param = param;
        ++pool->size;
    }
}

void *
_tp_run(void *param) {
    struct tp *pool = param;

    for (;;) {
        void (*job)(void *) = 0;
        void *param = 0;

        pthread_mutex_lock(&pool->mutex);
        if (pool->size > 0) {
            job = pool->jobs[pool->size - 1].job;
            param = pool->jobs[pool->size - 1].param;
            --pool->size;
        }
        pthread_mutex_unlock(&pool->mutex);
        if (job == 0) {
            return 0;
        } else {
            job(param);
        }
    }
}

void
tp_run(struct tp *pool, int max_threads) {
    pthread_t threads[max_threads];
    for (int i = 0; i < max_threads; i++) {
        if (pthread_create(&threads[i], 0, &_tp_run, pool) < 0) {
            perror("pthread_create");
            exit(1);
        }
    }

    for (int i = 0; i < max_threads; i++) {
        pthread_join(threads[i], 0);
    }
}

void *
mmap_stdin(off_t *stdin_size) {
    void *result;

    struct stat stat;
    if (fstat(0, &stat) < 0) {
        perror("fstat");
        exit(1);
    }

    *stdin_size = stat.st_size;

    result = mmap(0, stat.st_size, PROT_READ, MAP_PRIVATE, 0, 0);
    if (result == (void *)-1) {
        perror("mmap");
        exit(1);
    }

    return result;
}

struct input_sequence {
    char *start;
    int length;
};

void
identify_input_sequence(char *stdin_mem, int stdin_size,
        struct input_sequence *seq) {
    char *p =  strchr(strstr(stdin_mem, ">THREE"), '\n');

    while (isalpha(*p++)) {
        ;
    }

    char *end = strchr(p, '>');

    seq->start = p;
    seq->length = end == 0 ? stdin_size + stdin_mem - p : end - p;
}

char *
get_sequence_start(char *stdin_mem) {
    char *p =  strchr(strstr(stdin_mem, ">THREE"), '\n');

    while (isalpha(*p++)) {
        ;
    }

    return p;
}

static
inline uint8_t
pack_symbol(char c) {
    switch (c) {
        case 'a':
        case 'A':
            return 0;
        case 'c':
        case 'C':
            return 1;
        case 'g':
        case 'G':
            return 2;
        case 't':
        case 'T':
            return 3;
    }
    fprintf(stderr, "Unexpected: %c\n", c);
    exit(-1);
}

char unpack_symbol(uint8_t c) {
    static char table[] = {'A', 'C', 'G', 'T'};
    
    return table[c];
}

static
inline char *
next_char(char *p) {
    do {
        ++p;
    } while (isspace(*p));

    return p;
}

static
inline uint64_t
push_char(uint64_t cur, uint8_t c) {
    return (cur << 2) + pack_symbol(c);
}

static
inline uint64_t
rotate_code(uint64_t cur, uint8_t c, int frame) {
    return push_char(cur, c) & ((1ull << 2*frame) - 1);
}

uint64_t
pack_key(char *key, int len) {
    uint64_t code = 0;
    for (int i = 0; i < len; i++) {
        code = push_char(code, *key);
        key = next_char(key);
    }

    return code;
}

void
unpack_key(uint64_t key, int length, char *buffer) {
    int i;

    for (i = 0; i < length; i++) {
        buffer[i] = unpack_symbol(key & 3);
        key >>= 2;
    }
    buffer[i] = 0;

    // Reverse string.
    for (int j = (i - 1)/2; j >= 0; j--) {
        char c = buffer[j];
        buffer[j] = buffer[i - 1 - j];
        buffer[i - 1 - j] = c;
    }
}

void
generate_seqences(char *start, int length, int frame, struct ht_ht *ht) {
    uint64_t code = 0;
    char *p = start;
    char *end = start + length;

    // Pull first frame.
    for (int i = 0; i < frame; i++) {
        code = push_char(code, *p);
        p = next_char(p);
    }
    ht_find_new(ht, code)->val++;

    while (*p != '>' && p != end) {
        code = rotate_code(code, *p, frame);
        ht_find_new(ht, code)->val++;
        p = next_char(p);
    }
}

int
key_count_cmp(const void *l, const void *r) {
    const struct ht_node *lhs = l, *rhs = r;

    if (lhs->val != rhs->val) {
        return rhs->val - lhs->val;
    } else {
        // Overflow is possible here,
        // so use comparisons instead of subtraction.
        if (lhs->key < rhs->key) {
            return -1;
        } else if (lhs->key > rhs->key) {
            return 1;
        } else {
            return 0;
        }
    }
}

struct print_freqs_param {
    struct input_sequence *seq;
    int frame;
    char *output;
    int output_size;
};

struct ht_node *
ht_values_as_vector(struct ht_ht *ht) {
    struct ht_node *v = malloc(ht->items*sizeof(struct ht_node));
    struct ht_node *n = ht_first(ht);

    for (int i = 0; i < ht->items; i++) {
        v[i] = *n;
        n = ht_next(ht);
    }

    return v;
}

void
print_freqs(struct print_freqs_param *param) {
    struct input_sequence *seq = param->seq;
    int frame = param->frame;
    char *output = param->output;
    int output_size = param->output_size;

    struct ht_ht *ht = ht_create(32);
    char buffer[frame + 1];
    int output_pos = 0;

    generate_seqences(seq->start, seq->length, frame, ht);
    
    struct ht_node *counts = ht_values_as_vector(ht);
    int size = ht->items;

    qsort(counts, size, sizeof(struct ht_node), &key_count_cmp);

    int total_count = 0;
    for (int i = 0; i < size; i++) {
        total_count += counts[i].val;
    }

    for (int i = 0; i < size; i++) {
        unpack_key(counts[i].key, frame, buffer);
        output_pos += snprintf(output + output_pos, output_size - output_pos,
                "%s %.3f\n", buffer, counts[i].val*100.0f/total_count);
    }

    free(counts);
    ht_destroy(ht);
}

struct print_occurences_param {
    struct input_sequence *seq;
    char *nuc_seq;
    char *output;
    int output_size;
};

void
print_occurences(struct print_occurences_param *param) {
    struct input_sequence *seq = param->seq;
    char *nuc_seq = param->nuc_seq;
    char *output = param->output;
    int output_size = param->output_size;
    int nuc_seq_len = strlen(nuc_seq);
    struct ht_ht *ht = ht_create(HT_SIZE);

    generate_seqences(seq->start, seq->length, nuc_seq_len, ht);

    uint64_t key = pack_key(nuc_seq, nuc_seq_len);
    int count = ht_find_new(ht, key)->val;
    snprintf(output, output_size, "%d\t%s\n", count, nuc_seq);
    
    ht_destroy(ht);
}

int
get_cpu_count(void) {
    cpu_set_t cpu_set;

    CPU_ZERO(&cpu_set);
    sched_getaffinity(0, sizeof(cpu_set), &cpu_set);

    return CPU_COUNT(&cpu_set);
}

#define MAX_OUTPUT 1024

int
main(void) {
    off_t stdin_size;
    char *stdin_mem = mmap_stdin(&stdin_size);
    struct input_sequence seq;
    int cpu_count = get_cpu_count();

    identify_input_sequence(stdin_mem, stdin_size, &seq);

    char output_buffer[7][MAX_OUTPUT];

#   define DECLARE_PARAM(o, n) {\
    .seq = &seq,\
    .frame = n,\
    .output = output_buffer[o],\
    .output_size = MAX_OUTPUT }

    struct print_freqs_param freq_params[2] = {
        DECLARE_PARAM(0, 1),
        DECLARE_PARAM(1, 2)
    }; 

#   undef DECLARE_PARAM

#   define DECLARE_PARAM(o, s) {\
    .seq = &seq,\
    .nuc_seq = s,\
    .output = output_buffer[o],\
    .output_size = MAX_OUTPUT }

    struct print_occurences_param occurences_params[5] = {
        DECLARE_PARAM(2, "GGT"),
        DECLARE_PARAM(3, "GGTA"),
        DECLARE_PARAM(4, "GGTATT"),
        DECLARE_PARAM(5, "GGTATTTTAATT"),
        DECLARE_PARAM(6, "GGTATTTTAATTTATAGT")
    };

#   undef DECLARE_PARAM

    struct tp *tp = tp_create(7);

    for (int i = 0 ; i < 2; i++) {
        tp_add_job(tp, &print_freqs, &freq_params[i]);
    }
    for (int i = 0 ;i <  5; i++) {
        tp_add_job(tp, &print_occurences, &occurences_params[i]);
    }

    tp_run(tp, cpu_count + 1);

    tp_destroy(tp);

    for (int i = 0; i < 2; i++) {
        printf("%s\n", output_buffer[i]);
    }
    for (int i = 2; i < 7; i++) {
        printf("%s", output_buffer[i]);
    }

    if (munmap(stdin_mem, stdin_size) < 0) {
        perror("munmap");
        return 1;
    }

    return 0;
}

make, command-line, and program output logs

Sat, 27 Apr 2013 04:42:49 GMT

MAKE:
/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=native -std=c99 -include Include/simple_hash3.h -pthread knucleotide.gcc-5.c -o knucleotide.gcc-5.gcc_run 
In file included from <command-line>:0:0:
./Include/simple_hash3.h:195:31: warning: ‘ht_node_create’ is static but used in inline function ‘ht_find_new’ which is not static [enabled by default]
./Include/simple_hash3.h:191:24: warning: ‘ht_node_create’ is static but used in inline function ‘ht_find_new’ which is not static [enabled by default]
./Include/simple_hash3.h:173:21: warning: ‘ht_hashcode’ is static but used in inline function ‘ht_find_new’ which is not static [enabled by default]
./Include/simple_hash3.h:156:21: warning: ‘ht_hashcode’ is static but used in inline function ‘ht_find’ which is not static [enabled by default]
rm knucleotide.gcc-5.c
0.35s to complete and log all make actions

COMMAND LINE:
./knucleotide.gcc-5.gcc_run 0 < knucleotide-input25000000.txt

PROGRAM OUTPUT:
A 30.295
T 30.151
C 19.800
G 19.754

AA 9.177
TA 9.132
AT 9.131
TT 9.091
CA 6.002
AC 6.001
AG 5.987
GA 5.984
CT 5.971
TC 5.971
GT 5.957
TG 5.956
CC 3.917
GC 3.911
CG 3.909
GG 3.902

1471758	GGT
446535	GGTA
47336	GGTATT
893	GGTATTTTAATT
893	GGTATTTTAATTTATAGT

Home Conclusions License Play

x64 Ubuntu : Intel® Q6600® quad-coreComputer Language Benchmarks Game [[ Play ]]

performance measurements

notes

k-nucleotide C gcc #5 program source code

make, command-line, and program output logs

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