Calculating rolling averages in C

.clang-format

Standard: Latest
BasedOnStyle: LLVM
IndentWidth: 4
ColumnLimit: 0
AccessModifierOffset: -2
NamespaceIndentation: All
BreakBeforeBraces: Attach
IndentCaseLabels: true
FixNamespaceComments: false
AlignOperands: true
Cpp11BracedListStyle: true

averages.c

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    double *const buf; // The buffer
    size_t capacity;   // The max capacity of the buffer
    size_t size;       // The size of the buffer
    size_t start;      // Offset to the first element in the buffer
} double_circular_buf_t;

#define new_circular_buf(name, C)                                 \
    static double __##name##_new_circular_buf_buf[C];             \
    static double_circular_buf_t name = (double_circular_buf_t) { \
        .buf = (double *)&__##name##_new_circular_buf_buf,        \
        .capacity = C,                                            \
        .size = 0,                                                \
        .start = 0                                                \
    }

/**
 * \param out The value pushed out of the buffer, if there was one
 * \returns If there was data pushed off of the buffer
 */
bool circular_buffer_push(double_circular_buf_t *cb,
                          double value,
                          double *out) {
    if (cb->size == cb->capacity) {
        cb->start += 1;
        *out = cb->buf[(cb->start + cb->size) % cb->capacity];

        cb->buf[(cb->start + cb->size) % cb->capacity] = value;

        return true;
    } else {
        cb->buf[(cb->start + cb->size) % cb->capacity] = value;
        cb->size += 1;

        return false;
    }
}

/**
 * \param out The value popped from the buffer, if there was one
 * \returns If there was data to be popped off of the buffer
 */
bool circular_buffer_pop_back(double_circular_buf_t *cb, double *out) {
    if (cb->size == 0) {
        return false;
    }

    *out = cb->buf[(cb->start + cb->size - 1) % cb->capacity];

    cb->size -= 1;

    return true;
}

/**
 * \param out The value popped from the buffer, if there was one
 * \returns If there was data to be popped off of the buffer
 */
bool circular_buffer_pop_front(double_circular_buf_t *cb, double *out) {
    if (cb->size == 0) {
        return false;
    }

    *out = cb->buf[cb->start];

    if (cb->start == 0) {
        cb->start = cb->capacity - 1;
    } else {
        cb->start -= 1;
    }

    return true;
}

double circular_buffer_average(const double_circular_buf_t *cb) {
    double sum = 0;

    for (size_t i = 0; i < cb->size; i++) {
        size_t offset = (i + cb->start) % cb->capacity;
        sum += cb->buf[offset];
    }

    return sum / cb->size;
}

typedef struct {
    double average;
    size_t size;
    size_t capacity;
    double_circular_buf_t *const buf;
} incremental_average_t;

#define new_incremental_average(name, C)                                  \
    new_circular_buf(__##name##_new_replacement_average_circular_buf, C); \
    static incremental_average_t name = (incremental_average_t) {         \
        .capacity = 10,                                                   \
        .average = 0,                                                     \
        .size = 0,                                                        \
        .buf = &__##name##_new_replacement_average_circular_buf           \
    }

double replace_in_average(double average, int size, double old, double new) {
    return (size * average - old + new) / size;
}

double add_to_average(double average, int size, double new) {
    return average + (new - average) / size;
}

/**
 * \returns The average has saturated
 */
void update_average(incremental_average_t *average, double new) {
    assert(average->capacity > 0);

    // Check if average is saturated
    if (average->size == 0) {
        average->average = new;

        {
            double old;
            circular_buffer_push(average->buf, new, &old);
        }

        average->size += 1;
    } else {
        double old;
        if (circular_buffer_push(average->buf, new, &old)) {
            average->average = replace_in_average(average->average,
                                                  average->size,
                                                  old,
                                                  new);
        } else {
            average->size += 1;

            average->average = add_to_average(average->average,
                                              average->size,
                                              new);
        }
    }
}

double sampleNormal() {
    double u = ((double)rand() / (RAND_MAX)) * 2 - 1;
    double v = ((double)rand() / (RAND_MAX)) * 2 - 1;
    double r = u * u + v * v;

    if (r == 0 || r > 1)
        return sampleNormal();

    double c = sqrt(-2 * log(r) / r);
    return u * c;
}

#define abs_diff(a, b) a > b ? a - b : b - a

new_incremental_average(incremental_average, 1000);
new_circular_buf(circular_buf, 1000);

int main() {
    // srand((unsigned int)time(NULL)); TODO: Seed the random number generator

    for (int i = 0; i < 1000000; i++) {
        double sample = sampleNormal();

        clock_t incremental_time;
        {
            clock_t start_time = clock();

            {
                update_average(&incremental_average, sample);
            }

            clock_t end_time = clock();

            incremental_time = end_time - start_time;
        }

        clock_t circular_time;
        double cb_avg;
        {
            clock_t start_time = clock();

            {
                {
                    double temp;
                    circular_buffer_push(&circular_buf, sample, &temp);
                }

                cb_avg = circular_buffer_average(&circular_buf);
            }

            clock_t end_time = clock();

            circular_time = end_time - start_time;
        }

        if (i % 10000 == 0)
            printf("i: %d, Sample: %f, "
                   "Incremental: %f (%lu clocks), "
                   "Circular: %f (%lu clocks), Diff: %f (%lu clocks)\n",
                   i, sample,
                   incremental_average.average, incremental_time,
                   cb_avg, circular_time,
                   incremental_average.average - cb_avg,
                   abs_diff(incremental_time, circular_time));
    }

    return 0;
}