Small multithreaded malloc() benchmark

algorithm.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "algorithm.h"

void fill(char* elements, size_t sz) {
    int i;
    
    for(i = 0; i < sz; ++i)
        elements[i] = rand() & 0xFF;
}

void discard(el_root_t* elr) {
    el_bucket_t* root = elr->root;
    el_bucket_t* next = root->next;
    
    int count = 0;
    
    do {
        free(root);
        root = next;
        next = root->next;
        
        ++count;
    } while(next != NULL);
    
    printf("Discarded: %d entries\n", count);
}

void multiply_one(char* elements, size_t sz, int i, el_root_t* elr) {
    size_t bsz = sizeof(el_bucket_t);
    el_bucket_t* b = malloc(bsz);
    el_bucket_t* b2 = NULL;
    
    int j;
    
    b->chr1 = elements[i];
    
    for(j = 0; j < (sz - i); ++j) {
        /* Clone b as b2 and add elements[j + i] as last element */ 
        b2 = malloc(bsz + sizeof(el_descr_t));
        memcpy(b2, b, bsz);
        
        b->next = NULL;
        b->chr2 = elements[j + i];
        b->descr[j].chr = elements[j + i];
        b->descr[j].count = 0;
        
        /* Insert b2 into bucket */
        if(elr->last == NULL) {
            if(elr->root == NULL)
                elr->root = b;
            elr->last = b;
        } else {
            elr->last->next = b;
            elr->last = b;
        }
        
        /* Update counters */
        bsz += sizeof(el_descr_t);
        b = b2;
    }
    
    free(b2);
}

algorithm.h

#ifndef ALGORITHM_H_
#define ALGORITHM_H_

typedef struct {
    char chr;
    int count;
} el_descr_t;

typedef struct el_bucket {
    char chr1;
    char chr2;
    
    struct el_bucket* next;
    
    el_descr_t descr[1];
} el_bucket_t;

typedef struct el_root {
    el_bucket_t* root;
    el_bucket_t* last;
} el_root_t;

void fill(char* elements, size_t sz);
void discard(el_root_t* elr);
void multiply_one(char* elements, size_t sz, int i, el_root_t* elr);

#endif

common.c

#include <stdio.h>
#include <stdlib.h>

#include "common.h"

void print_tm_diff(struct timespec* start, struct timespec* end) {
    start->tv_nsec = end->tv_nsec - start->tv_nsec;
    if(start->tv_nsec < 0) {
        start->tv_nsec += 1000000000;
        end->tv_sec -= 1;
    }
    
    start->tv_sec = end->tv_sec - start->tv_sec;
    
    printf("%llus %lluns\n", (long long) start->tv_sec, (long long) start->tv_nsec);
}

void parse_cmdline(int argc, char* argv[], int* p_num_elements, int* p_num_threads) {
    const char* usage_uni = "Usage: %s num_elements\n";
    const char* usage_multi = "Usage: %s num_elements num_threads\n";
    
    const char* usage_fmtstr = (p_num_elements == NULL) ? usage_uni : usage_multi;
    
    if(p_num_threads == NULL && argc != 2)
        goto usage;
    
    if(p_num_threads != NULL && argc != 3)
        goto usage;
    
    *p_num_elements = atoi(argv[1]);
    if(*p_num_elements < 0)
        goto usage;
    
    if(!p_num_threads)
        return;
        
    *p_num_threads = atoi(argv[2]);
    if(*p_num_threads < 1)
        goto usage;
        
    return;
    
usage:
    fprintf(stderr, usage_fmtstr, argv[0]);
    exit(1);
}

common.h

#ifndef COMMON_H_
#define COMMON_H_ 

#include <time.h>

void print_tm_diff(struct timespec* start, struct timespec* end);
void parse_cmdline(int argc, char* argv[], int* p_num_elements, int* p_num_threads);

#endif

Makefile

CFLAGS = -g
CC = gcc
LDFLAGS = -lrt

OBJS = common.o algorithm.o libptmalloc3.a

algorithm.o: algorithm.c algorithm.h
	$(CC) $(CFLAGS) -o $@ -c algorithm.c

common.o: common.c common.h
	$(CC) $(CFLAGS) -o $@ -c common.c

unithread: unithread.c $(OBJS)
	$(CC) $(CFLAGS) -o unithread.o -c unithread.c
	$(CC) $(CFLAGS) $(LDFLAGS) -o $@ unithread.o $(OBJS)

multithread: multithread.c $(OBJS)
	$(CC) $(CFLAGS) -pthread -o multithread.o -c multithread.c
	$(CC) $(CFLAGS) $(LDFLAGS) -o $@ multithread.o $(OBJS) -pthread

all: unithread multithread

multithread.c

#include <stdlib.h>
#include <string.h>
#include <pthread.h>


#include "common.h"
#include "algorithm.h"

typedef struct {
    int tid;
    
    int start;
    int offset;
    
    el_root_t elr;
    
    char* elements;
    size_t sz;
    
    pthread_t thr;
    pthread_attr_t thr_attr;
} el_thread_t;

void* multiply_thread(void* arg) {
    el_thread_t* thr = (el_thread_t*) arg;
    
    int i;
    
    char* elements = thr->elements;
    size_t sz = thr->sz;
    
    for(i = thr->start; i < sz; i += thr->offset) {
        multiply_one(elements, sz, i, &thr->elr);
    }
    
    return NULL;
}

el_thread_t* multiply_start(char* elements, size_t sz, int num_threads) {
    el_thread_t* threads = (el_thread_t*) malloc(sizeof(el_thread_t) * num_threads);
    el_thread_t* thr = threads;
    
    int tid;
    
    for(tid = 0; tid < num_threads; ++tid) {
        thr->tid = tid;
        thr->offset = num_threads;
        
        thr->start = tid;
        thr->elements = elements;
        thr->sz = sz;
        
        thr->elr.root = NULL;
        thr->elr.last = NULL;
        
        pthread_attr_init(&thr->thr_attr);
        pthread_attr_setdetachstate(&thr->thr_attr, PTHREAD_CREATE_JOINABLE);
        pthread_attr_setstacksize(&thr->thr_attr, 16384);
        
        pthread_create(&thr->thr, &thr->thr_attr, multiply_thread, (void*) thr);
        
        ++thr;
    }
    
    return threads;
}

void multiply_wait(el_thread_t* threads, int num_threads) {
    void* retval;
    
    int tid;
    el_thread_t* thr = threads;
    
    for(tid = 0; tid < num_threads; ++tid) {
        pthread_join(thr->thr, &retval);
        pthread_attr_destroy(&thr->thr_attr);
        pthread_detach(thr->thr);
        
        ++thr;
    }
}

void multiply_finalize(el_thread_t* threads, int num_threads) {
    int tid;
    el_thread_t* thr = threads;
    
    for(tid = 0; tid < num_threads; ++tid) {
        discard(&thr->elr);
        ++thr;
    }
    
    free(threads);
}

int main(int argc, char* argv[]) {
    int num_elements, num_threads;
    
    char* elements;
    el_thread_t* threads;
    
    struct timespec start;
    struct timespec end;
    
    parse_cmdline(argc, argv, &num_elements, &num_threads);
    
    elements = (char*) malloc(num_elements);
    fill(elements, num_elements);
    
    clock_gettime(CLOCK_MONOTONIC, &start);
    
    threads = multiply_start(elements, num_elements, num_threads);
    multiply_wait(threads, num_threads);
    
    clock_gettime(CLOCK_MONOTONIC, &end);
    
    print_tm_diff(&start, &end);
    
    multiply_finalize(threads, num_threads);
    free(elements);
    
    return 0;
}

unithread.c

#include <stdlib.h>
#include <string.h>

#include "common.h"
#include "algorithm.h"

el_root_t elr = { NULL, NULL };

void multiply(char* elements, size_t sz) {
    int i;
    
    for(i = 0; i < sz; ++i) {
        multiply_one(elements, sz, i, &elr);
    }
}

int main(int argc, char* argv[]) {
    int num_elements;
    char* elements;
    
    struct timespec start;
    struct timespec end;
    
    parse_cmdline(argc, argv, &num_elements, NULL);
    
    elements = (char*) malloc(num_elements);
    fill(elements, num_elements);
    
    clock_gettime(CLOCK_MONOTONIC, &start);
    
    multiply(elements, num_elements);
    
    clock_gettime(CLOCK_MONOTONIC, &end);
    print_tm_diff(&start, &end);
    
    discard(&elr);    
    free(elements);
    
    return 0;
}