binary_copy.c

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

#include <mach/mach_time.h>
#include <stdint.h>


#define MIN(a, b) ((a) <= (b) ? (a) : (b))


typedef struct {
    char *data;
    unsigned len;
} binary;

static binary copy_slow(binary bin, unsigned n) {
    unsigned new_len = bin.len * n;
    char *new_data = (char *)malloc(new_len);
    assert(new_data);

    unsigned offset = 0;
    for (unsigned i = 0; i < n; i++, offset += bin.len) {
        memcpy(new_data+offset, bin.data, bin.len);
    }
    return (binary){ new_data, new_len };
}

static binary copy_fast(binary bin, unsigned n) {
    unsigned new_len = bin.len * n;
    char *new_data = (char *)malloc(new_len);
    assert(new_data);

    unsigned block_size = bin.len;
    if (n > 0) {
        memcpy(new_data, bin.data, block_size);
    }
    while (block_size < new_len) {
        unsigned size = MIN(block_size, new_len-block_size);
        memcpy(new_data+block_size, new_data, size);
        block_size *= 2;
    }
    return (binary){ new_data, new_len };
}


static binary make_binary(const char *str) {
    unsigned len = strlen(str);
    char *data = (char *)malloc(len);
    assert(data);
    strncpy(data, str, len);
    return (binary){ data, len };
}

static void print_binary(binary bin) {
    fwrite(bin.data, bin.len, 1, stdout);
    putc('\n', stdout);
}



static double ticks_to_nano(uint64_t ticks) {
    static double ratio = 0.0;

    // The first time we get here, ask the system
    // how to convert mach time units to nanoseconds
    if (ratio == 0.0) {
        mach_timebase_info_data_t timebase;
        mach_timebase_info(&timebase);
        ratio = (double)timebase.numer / timebase.denom;
    }

    return ticks * ratio;
}

#define SLOW 1

#if SLOW
#define COPY copy_slow
#define NAME "slow"
#else
#define COPY copy_fast
#define NAME "fast"
#endif


int main(int argc, const char *argv[])
{
    binary bin = make_binary("abc.");

    for (unsigned N = 10; N < 1000000; N *= 10) {
        uint64_t start_time = mach_absolute_time();
        binary dup = COPY(bin, N);
        uint64_t elapsed = mach_absolute_time() - start_time;
        /*print_binary(dup);*/
        printf(NAME " Input size = %u, time = %f µs\n", N, ticks_to_nano(elapsed)/1000.0);
    }

    return 0;
}

results

# average of a few runs

slow Input size = 10, time = 2.280000 µs
slow Input size = 100, time = 2.064000 µs
slow Input size = 1000, time = 23.111000 µs
slow Input size = 10000, time = 189.480000 µs
slow Input size = 100000, time = 1918.361000 µs

fast Input size = 10, time = 2.371000 µs
fast Input size = 100, time = 0.830000 µs
fast Input size = 1000, time = 7.228000 µs
fast Input size = 10000, time = 24.088000 µs
fast Input size = 100000, time = 254.149000 µs