[Qemu-devel] [PATCH 0/2] RFC: Rolling statistics

[Qemu-devel] [PATCH 0/2] RFC: Rolling statistics

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

Hi,
  This is an attempt at a generic rolling statistics utility to
allow data (e.g. bandwidth usage, times etc) to be collected
easily.  They hold some basic values (min/max/mean/weighted mean)
and the last 'n' raw values.    I'd like to use this
maybe in fault-tolerance code.

  This is a first cut, and I think I probably need to rework it
as a qapi type somehow, but I'm interested in thoughts.

Dave


Dr. David Alan Gilbert (2):
  Rolling statistics utilities
  Tests for rolling statistics code

 include/qemu/rolling-stats.h | 101 +++++++++++
 include/qemu/typedefs.h      |   1 +
 tests/Makefile               |   3 +
 tests/test-rolling-stats.c   | 161 ++++++++++++++++++
 util/Makefile.objs           |   1 +
 util/rolling-stats.c         | 393 +++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 660 insertions(+)
 create mode 100644 include/qemu/rolling-stats.h
 create mode 100644 tests/test-rolling-stats.c
 create mode 100644 util/rolling-stats.c

-- 
2.1.0

[Qemu-devel] [PATCH 1/2] Rolling statistics utilities

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

There are various places where it's useful to hold a series
of values that change over time and get summaries about them.

This provides:

   - a count of the number of items
   - min/max
   - mean
   - a weighted mean (where you can set the weight to determine
                      whether it changes quickly or slowly)
   - the last 'n' values

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 include/qemu/rolling-stats.h | 101 +++++++++++
 include/qemu/typedefs.h      |   1 +
 util/Makefile.objs           |   1 +
 util/rolling-stats.c         | 393 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 496 insertions(+)
 create mode 100644 include/qemu/rolling-stats.h
 create mode 100644 util/rolling-stats.c

diff --git a/include/qemu/rolling-stats.h b/include/qemu/rolling-stats.h
new file mode 100644
index 0000000..d64ce78
--- /dev/null
+++ b/include/qemu/rolling-stats.h
@@ -0,0 +1,101 @@
+/*
+ * A container for statistics that are measured repeatedly.
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <dgilbert@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ *
+ */
+
+#ifndef __QEMU_ROLLING_STATS_H
+#define __QEMU_ROLLING_STATS_H 1
+
+#include "qemu/typedefs.h"
+/**
+ * Allocate and initialise an 'RStats' structure.
+ *
+ * @len:    Number of values to hold
+ * @weight: Weight for the weighted average, between 0..1
+ *          smaller values cause the average to update more quickly.
+ *
+ * Returns: A pointer to the RStats structure.
+ */
+RStats *rstats_init(size_t len, double weight);
+
+/**
+ * Deallocate the RStats structure
+ */
+void rstats_destroy(RStats *r);
+
+/**
+ * Add a new value into the RStats record.
+ *
+ * @r: The RStats to update
+ * @value: The new value to be recorded
+ * @tag: A tag to be associated with the value, not used by the calculations
+ *       (e.g. a time or iteration count)
+ */
+void rstats_add_value(RStats *r, double value, uint64_t tag);
+
+/**
+ * Reset the RStats structure
+ *
+ */
+void rstats_reset(RStats *r);
+
+/**
+ * Return a string representing the RStats data, intended for human consumption
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g. (Without the line break!)
+ *   Min/Max: -3.57, 126.3  Mean: 7.83 (weighted: 8.56)  Values: 4.3@458,
+ *   5.8@783, 1.2@950, 7.9@951, 10.3@952
+ */
+char *rstats_as_pretty_string(RStats *r);
+
+/**
+ * Return a string representing the RStats data, intended for JSON parsing
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g.
+ *    { "min": -3.57, "max": 126.3, "mean": 7.83, "weighted_mean": 8.56,
+ *      "count": 5678,
+ *      "values": [ 4.3, 5.8, 1.2, 7.9, 10.3 ],
+ *      "tags": [ 458, 783, 950, 951, 952 ] }
+ */
+char *rstats_as_json_string(RStats *r);
+
+/**
+ * Return the mean
+ * @r: The RStats to examine
+ *
+ * Returns: The mean value
+ */
+double rstats_get_mean(const RStats *r);
+
+/**
+ * Return the weighted mean
+ * @r: The RStats to examine
+ *
+ * Returns: The weighted mean
+ */
+double rstats_get_weighted_mean(const RStats *r);
+
+/**
+ * Return the minimum and maximum values
+ * @r: The RStats to examine
+ * @min: Pointer to return the minimum in
+ * @max: Pointer to return the maximum in
+ *
+ */
+void rstats_get_min_max(const RStats *r, double *min, double *max);
+
+#endif
diff --git a/include/qemu/typedefs.h b/include/qemu/typedefs.h
index cde3314..3488dfd 100644
--- a/include/qemu/typedefs.h
+++ b/include/qemu/typedefs.h
@@ -69,6 +69,7 @@ typedef struct QEMUSizedBuffer QEMUSizedBuffer;
 typedef struct QEMUTimerListGroup QEMUTimerListGroup;
 typedef struct QEMUTimer QEMUTimer;
 typedef struct Range Range;
+typedef struct RStats RStats;
 typedef struct SerialState SerialState;
 typedef struct SHPCDevice SHPCDevice;
 typedef struct SMBusDevice SMBusDevice;
diff --git a/util/Makefile.objs b/util/Makefile.objs
index ceaba30..b45af66 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -17,4 +17,5 @@ util-obj-y += throttle.o
 util-obj-y += getauxval.o
 util-obj-y += readline.o
 util-obj-y += rfifolock.o
+util-obj-y += rolling-stats.o
 util-obj-y += rcu.o
diff --git a/util/rolling-stats.c b/util/rolling-stats.c
new file mode 100644
index 0000000..f2f1984
--- /dev/null
+++ b/util/rolling-stats.c
@@ -0,0 +1,393 @@
+/*
+ * A container for statistics that are measured repeatedly.
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <dgilbert@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ *
+ */
+
+#include <float.h>
+#include <glib.h>
+#include <stdint.h>
+
+#include "qemu-common.h"
+#include "qemu/rolling-stats.h"
+#include "qemu/thread.h"
+#include "qemu/typedefs.h"
+
+struct RStats {
+    size_t allocated;  /* Amount of space for values */
+    size_t captured;   /* Number of values currently stored */
+    size_t head;       /* Pointer to the next value to be written */
+    size_t count;      /* Count of values which the stats are calculated over */
+    double weight;     /* for weighted_mean calculation */
+    double *values;
+    uint64_t *tags;    /* Tags associated with corresponding values */
+
+    double min, max, mean, weighted_mean;
+
+    /* Allow results to be added and printed from different threads */
+    QemuMutex mutex;
+};
+
+/**
+ * Add a new value into the RStats record.
+ *
+ * @r: The RStats to update
+ * @value: The new value to be recorded
+ * @tag: A tag to be associated with the value, not used by the calculations
+ *       (e.g. a time or iteration count)
+ */
+void rstats_add_value(RStats *r, double value, uint64_t tag)
+{
+    double old_value;
+
+    qemu_mutex_lock(&r->mutex);
+
+    old_value  = r->values[r->head];
+
+    r->tags[r->head] = tag;
+    r->values[r->head++] = value;
+    if (r->head >= r->allocated) {
+        r->head = 0;
+    }
+    if (r->captured < r->allocated) {
+        double tmp;
+
+        tmp = r->mean * r->captured;
+
+        r->captured++;
+
+        r->mean = (tmp + value) / r->captured;
+    } else {
+        r->mean -= old_value / r->allocated;
+        r->mean += value / r->allocated;
+    }
+
+    if (!r->count || value < r->min) {
+        r->min = value;
+    }
+
+    if (!r->count || value > r->max) {
+        r->max = value;
+    }
+
+
+    if (r->count) {
+        r->weighted_mean = r->weighted_mean * r->weight +
+                                      value * (1 - r->weight);
+    } else {
+        r->weighted_mean = value;
+    }
+
+    r->count++;
+
+    qemu_mutex_unlock(&r->mutex);
+}
+
+/**
+ * Reset the RStats structure
+ *
+ */
+void rstats_reset(RStats *r)
+{
+    qemu_mutex_lock(&r->mutex);
+
+    r->captured = 0;
+    r->count = 0;
+    r->head = 0;
+    r->max = 0.0;
+    r->mean = 0.0;
+    r->min = 0.0;
+    r->weighted_mean = 0.0;
+
+    qemu_mutex_unlock(&r->mutex);
+}
+
+/**
+ * Return the mean
+ * @r: The RStats to examine
+ *
+ * Returns: The mean value
+ */
+double rstats_get_mean(const RStats *r)
+{
+    return r->mean;
+}
+
+/**
+ * Return the weighted mean
+ * @r: The RStats to examine
+ *
+ * Returns: The weighted mean
+ */
+double rstats_get_weighted_mean(const RStats *r)
+{
+    return r->weighted_mean;
+}
+
+/**
+ * Return the minimum and maximum values
+ * @r: The RStats to examine
+ * @min: Pointer to return the minimum in
+ * @max: Pointer to return the maximum in
+ *
+ */
+void rstats_get_min_max(const RStats *r, double *min, double *max)
+{
+    *min = r->min;
+    *max = r->max;
+}
+
+
+/*
+ * Helper for the formatters below, updates pointers, reallocates if
+ * needed.
+ *
+ * @printf_out: The result value of an snprintf saying how many chars it
+ *              wanted to print.
+ * @result: The output buffer, maybe reallocated
+ * @current: The pointer to the current text just output, will be updated
+ *           to where the next text should be output
+ * @space: The size of the output buffer, maybe updated
+ * @space_left: The number of characters remaining in the output buffer,
+ *              will be updated
+ */
+static bool maybe_realloc(int printf_out, char **result, char **current,
+                          size_t *space, size_t *space_left)
+{
+    if (printf_out >= *space_left) {
+        char *new_result;
+        *space = *space + 512;
+        new_result = g_try_realloc(*result, *space);
+
+        if (!new_result) {
+            *result = NULL;
+            return false;
+        }
+        *space_left = (*space - 1) - (*current - *result);
+        *current = new_result + (*current - *result);
+        *result = new_result;
+        return true;
+    } else {
+        *current += printf_out;
+        *space_left -= printf_out;
+        return false;
+    }
+}
+/**
+ * Return a string representing the RStats data, intended for human consumption
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g.
+ *   Min/Max: -3.57, 126.3  Mean: 7.83 (weighted: 8.56)  Values: 4.3@458,
+ *            5.8@783, 1.2@950, 7.9@951, 10.3@952
+ */
+char *rstats_as_pretty_string(RStats *r)
+{
+    char *result, *current;
+    int tmp;
+    size_t index;
+
+    /* lets get a sane initial size, we'll reallocate as we print the values */
+    size_t space, space_left;
+
+    qemu_mutex_lock(&r->mutex);
+    space  = 60 /* for text */ +
+             /* 4 double values (min/max/mean/weighted) + the stored
+              * values, plus a normal guess for the size of them printed
+              * with %g and some padding.  I'm not sure of the worst case.
+              */
+             (4 + r->allocated) * 13 +
+             /* and the count and tags as 64bit ints and some padding */
+             (1 + r->allocated) * 23;
+    space_left = space - 1;
+
+    result = g_try_malloc(space);
+
+    if (!result) {
+        qemu_mutex_unlock(&r->mutex);
+        return NULL;
+    }
+
+    current = result;
+    tmp = snprintf(current, space_left, "Min/Max: %.8g, %.8g Mean: %.8g "
+                                        "(Weighted: %.8g) Count: %" PRIu64
+                                        " Values: ",
+                   r->min, r->max, r->mean, r->weighted_mean, r->count);
+    if (tmp >= space_left) {
+        /* It's very unlikely that the values aren't large enough even for
+         * the summary. */
+        g_free(result);
+        result = NULL;
+        goto out;
+    }
+    current += tmp;
+    space_left -= tmp;
+
+    for (index = 0; index < r->captured; index++) {
+        do {
+            size_t actual_index;
+
+            /*
+             * The array is a rolling buffer, adjust so index=0 always points
+             * to the oldest.
+             */
+            if (r->captured >= r->allocated) {
+                actual_index = (index + r->head) % r->allocated;
+            } else {
+                actual_index = index;
+            }
+            tmp = snprintf(current, space_left,
+                           "%.8g@%" PRIu64 "%s",
+                           r->values[actual_index], r->tags[actual_index],
+                           (index == (r->captured - 1)) ? "" : ", ");
+
+        } while (maybe_realloc(tmp, &result, &current, &space, &space_left));
+
+        if (result == NULL) {
+            break;
+        }
+    }
+
+out:
+    qemu_mutex_unlock(&r->mutex);
+    return result;
+}
+
+/**
+ * Return a string representing the RStats data, intended for JSON parsing
+ *
+ * Returns: An allocated string the caller must free
+ *          or NULL on error
+ *
+ * e.g.
+ *    { "min": -3.57, "max": 126.3, "mean": 7.83, "weighted_mean": 8.56,
+ *      "count": 5678,
+ *      "values": [ { "value": 4.3, "tag": 458 },
+ *                  { "value": 5.8, "tag": 783 },
+ *                  { "value": 1.2, "tag": 950 },
+ *                  { "value": 7.9, "tag": 951 },
+ *                  { "value": 10.3, "tag": 952 } ] }
+ *
+ */
+char *rstats_as_json_string(RStats *r)
+{
+    char *result, *current;
+    int tmp;
+    size_t index;
+
+    /* lets get a sane initial size, we'll reallocate as we print the values */
+    size_t space, space_left;
+
+    qemu_mutex_lock(&r->mutex);
+    space  = 120 /* for text */ +
+             /* 4 double values (min/max/mean/weighted) + the stored
+              * values, plus a normal guess for the size of them printed
+              * with %g and some padding.  I'm not sure of the worst case.
+              */
+             (4 + r->allocated) * 13 +
+             /* and the count and tags as 64bit ints and some padding */
+             (1 + r->allocated) * 23;
+    space_left = space - 1;
+
+    result = g_try_malloc(space);
+
+    if (!result) {
+        qemu_mutex_unlock(&r->mutex);
+        return NULL;
+    }
+
+    current = result;
+    tmp = snprintf(current, space_left, "{ \"min\": %.8g, \"max\": %.8g,"
+                                        " \"mean\": %.8g,"
+                                        " \"weighted_mean\": %.8g,"
+                                        " \"count\": %" PRIu64 ","
+                                        " \"values\": [ %s",
+                   r->min, r->max, r->mean, r->weighted_mean, r->count,
+                   !r->captured ? "] }" : "" );
+    if (tmp >= space_left) {
+        /* It's very unlikely that the values aren't large enough even for
+         * the header. */
+        g_free(result);
+        result = NULL;
+        goto out;
+    }
+    current += tmp;
+    space_left -= tmp;
+
+    for (index = 0; index < r->captured; index++) {
+        do {
+            size_t actual_index;
+
+            /*
+             * The array is a rolling buffer, adjust so index=0 always points
+             * to the oldest.
+             */
+            if (r->captured >= r->allocated) {
+                actual_index = (index + r->head) % r->allocated;
+            } else {
+                actual_index = index;
+            }
+            tmp = snprintf(current, space_left,
+                           "{ \"value\": %.8g, \"tag\": %" PRIu64 "%s",
+                           r->values[actual_index], r->tags[actual_index],
+                           (index == (r->captured - 1)) ? " } ] }" : " }, ");
+
+        } while (maybe_realloc(tmp, &result, &current, &space, &space_left));
+
+        if (result == NULL) {
+            break;
+        }
+    }
+
+out:
+    qemu_mutex_unlock(&r->mutex);
+    return result;
+}
+
+/**
+ * Allocate and initialise an 'RStats' structure.
+ *
+ * @len:    Number of values to hold
+ * @weight: Weight for the weighted average, between 0..1
+ *          smaller values cause the average to update more quickly.
+ *
+ * Returns: A pointer to the RStats structure.
+ */
+RStats *rstats_init(size_t len, double weight)
+{
+    RStats *r = g_new0(RStats, 1);
+
+    r->values = g_new0(double, len);
+    r->tags = g_new0(uint64_t, len);
+    r->allocated = len;
+    r->weight = weight;
+
+    rstats_reset(r);
+
+    qemu_mutex_init(&r->mutex);
+    return r;
+}
+
+/**
+ * Deallocate the RStats structure
+ */
+void rstats_destroy(RStats *r)
+{
+    qemu_mutex_lock(&r->mutex);
+    g_free(r->values);
+    g_free(r->tags);
+    qemu_mutex_unlock(&r->mutex);
+    qemu_mutex_destroy(&r->mutex);
+    g_free(r);
+}
+
+
-- 
2.1.0

[Qemu-devel] [PATCH 2/2] Tests for rolling statistics code

[Dr. David Alan Gilbert (git)]

From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
---
 tests/Makefile             |   3 +
 tests/test-rolling-stats.c | 161 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 164 insertions(+)
 create mode 100644 tests/test-rolling-stats.c

diff --git a/tests/Makefile b/tests/Makefile
index 307035c..2d42eb2 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -72,6 +72,8 @@ check-unit-y += tests/test-qemu-opts$(EXESUF)
 gcov-files-test-qemu-opts-y = qom/test-qemu-opts.c
 check-unit-y += tests/test-write-threshold$(EXESUF)
 gcov-files-test-write-threshold-y = block/write-threshold.c
+check-unit-y += tests/test-rolling-stats$(EXESUF)
+gcov-files-test-rolling-stats = util/rolling-stats.c
 
 check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh
 
@@ -367,6 +369,7 @@ tests/vhost-user-test$(EXESUF): tests/vhost-user-test.o qemu-char.o qemu-timer.o
 tests/qemu-iotests/socket_scm_helper$(EXESUF): tests/qemu-iotests/socket_scm_helper.o
 tests/test-qemu-opts$(EXESUF): tests/test-qemu-opts.o libqemuutil.a libqemustub.a
 tests/test-write-threshold$(EXESUF): tests/test-write-threshold.o $(block-obj-y) libqemuutil.a libqemustub.a
+tests/test-rolling-stats$(EXESUF): tests/test-rolling-stats.o libqemuutil.a libqemustub.a
 
 ifeq ($(CONFIG_POSIX),y)
 LIBS += -lutil
diff --git a/tests/test-rolling-stats.c b/tests/test-rolling-stats.c
new file mode 100644
index 0000000..85dc949
--- /dev/null
+++ b/tests/test-rolling-stats.c
@@ -0,0 +1,161 @@
+/*
+ * Test rolling statistics framework
+ *
+ * Copyright 2015 Red Hat, Inc. and/or its affiliates
+ *
+ * Authors:
+ *   Dr. David Alan Gilbert <dgilbert@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU LGPL, version 2 or later.
+ * See the COPYING.LIB file in the top-level directory.
+ *
+ */
+
+#include "qemu-common.h"
+#include "qemu/rolling-stats.h"
+
+static void test_1(void)
+{
+    RStats *r = rstats_init(5, 0.2);
+    char *str;
+    
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: 0, 0 Mean: 0 (Weighted: 0)"
+                             " Count: 0 Values: ");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": 0, \"max\": 0, \"mean\": 0,"
+                             " \"weighted_mean\": 0, \"count\": 0,"
+                             " \"values\": [ ] }");
+    g_free(str);
+
+    rstats_add_value(r, 1.0, 11);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: 1, 1 Mean: 1 (Weighted: 1)"
+                             " Count: 1 Values: 1@11");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": 1, \"max\": 1, \"mean\": 1,"
+                             " \"weighted_mean\": 1, \"count\": 1,"
+                             " \"values\": ["
+                             " { \"value\": 1, \"tag\": 11 }"
+                             " ] }");
+    g_free(str);
+
+    rstats_add_value(r, 2.0, 22);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: 1, 2 Mean: 1.5 (Weighted: 1.8)"
+                             " Count: 2 Values: 1@11, 2@22");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": 1, \"max\": 2, \"mean\": 1.5,"
+                             " \"weighted_mean\": 1.8, \"count\": 2,"
+                             " \"values\": ["
+                             " { \"value\": 1, \"tag\": 11 },"
+                             " { \"value\": 2, \"tag\": 22 }"
+                             " ] }");
+    g_free(str);
+
+    rstats_add_value(r, -1.5, 33);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: -1.5, 2 Mean: 0.5 (Weighted: -0.84)"
+                             " Count: 3 Values: 1@11, 2@22, -1.5@33");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": -1.5, \"max\": 2, \"mean\": 0.5,"
+                             " \"weighted_mean\": -0.84, \"count\": 3,"
+                             " \"values\": ["
+                             " { \"value\": 1, \"tag\": 11 },"
+                             " { \"value\": 2, \"tag\": 22 },"
+                             " { \"value\": -1.5, \"tag\": 33 }"
+                             " ] }");
+    g_free(str);
+
+    rstats_add_value(r, 0.5, 44);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: -1.5, 2 Mean: 0.5 (Weighted: 0.232)"
+                             " Count: 4 Values: 1@11, 2@22, -1.5@33, 0.5@44");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": -1.5, \"max\": 2,"
+                             " \"mean\": 0.5,"
+                             " \"weighted_mean\": 0.232, \"count\": 4,"
+                             " \"values\": ["
+                             " { \"value\": 1, \"tag\": 11 },"
+                             " { \"value\": 2, \"tag\": 22 },"
+                             " { \"value\": -1.5, \"tag\": 33 },"
+                             " { \"value\": 0.5, \"tag\": 44 }"
+                             " ] }");
+    g_free(str);
+
+
+    rstats_add_value(r, 1000.123, 55);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: -1.5, 1000.123 Mean: 200.4246"
+                             " (Weighted: 800.1448)"
+                             " Count: 5 Values: 1@11, 2@22, -1.5@33, 0.5@44"
+                             ", 1000.123@55");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": -1.5, \"max\": 1000.123,"
+                             " \"mean\": 200.4246,"
+                             " \"weighted_mean\": 800.1448, \"count\": 5,"
+                             " \"values\": ["
+                             " { \"value\": 1, \"tag\": 11 },"
+                             " { \"value\": 2, \"tag\": 22 },"
+                             " { \"value\": -1.5, \"tag\": 33 },"
+                             " { \"value\": 0.5, \"tag\": 44 },"
+                             " { \"value\": 1000.123, \"tag\": 55 }"
+                             " ] }");
+    g_free(str);
+
+    /*
+     * We've got 5 spaces in the value array and this is the 6th value,
+     * so we start to overwrite.
+     */
+    rstats_add_value(r, 10, 66);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: -1.5, 1000.123 Mean: 202.2246"
+                             " (Weighted: 168.02896)"
+                             " Count: 6 Values: 2@22, -1.5@33, 0.5@44"
+                             ", 1000.123@55, 10@66");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": -1.5, \"max\": 1000.123,"
+                             " \"mean\": 202.2246,"
+                             " \"weighted_mean\": 168.02896, \"count\": 6,"
+                             " \"values\": ["
+                             " { \"value\": 2, \"tag\": 22 },"
+                             " { \"value\": -1.5, \"tag\": 33 },"
+                             " { \"value\": 0.5, \"tag\": 44 },"
+                             " { \"value\": 1000.123, \"tag\": 55 },"
+                             " { \"value\": 10, \"tag\": 66 }"
+                             " ] }");
+    g_free(str);
+
+
+    /* Try a reset */
+    rstats_reset(r);
+    rstats_add_value(r, 30, 77);
+    str = rstats_as_pretty_string(r);
+    g_assert_cmpstr(str, ==, "Min/Max: 30, 30 Mean: 30"
+                             " (Weighted: 30)"
+                             " Count: 1 Values: 30@77");
+    g_free(str);
+    str = rstats_as_json_string(r);
+    g_assert_cmpstr(str, ==, "{ \"min\": 30, \"max\": 30, \"mean\": 30,"
+                             " \"weighted_mean\": 30, \"count\": 1,"
+                             " \"values\": ["
+                             " { \"value\": 30, \"tag\": 77 }"
+                             " ] }");
+    g_free(str);
+
+    rstats_destroy(r);
+}
+
+int main(int argc, char **argv)
+{
+    g_test_init(&argc, &argv, NULL);
+    g_test_add_func("/utils/rolling_stats", test_1);
+    return g_test_run();
+}
-- 
2.1.0

Re: [Qemu-devel] [PATCH 1/2] Rolling statistics utilities

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2534 bytes --]

On 02/27/2015 12:06 PM, Dr. David Alan Gilbert (git) wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> 
> There are various places where it's useful to hold a series
> of values that change over time and get summaries about them.
> 
> This provides:
> 
>    - a count of the number of items
>    - min/max
>    - mean
>    - a weighted mean (where you can set the weight to determine
>                       whether it changes quickly or slowly)
>    - the last 'n' values
> 
> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> ---
>  include/qemu/rolling-stats.h | 101 +++++++++++

> +
> +/**
> + * Return a string representing the RStats data, intended for JSON parsing
> + *
> + * Returns: An allocated string the caller must free
> + *          or NULL on error
> + *
> + * e.g.
> + *    { "min": -3.57, "max": 126.3, "mean": 7.83, "weighted_mean": 8.56,
> + *      "count": 5678,
> + *      "values": [ 4.3, 5.8, 1.2, 7.9, 10.3 ],
> + *      "tags": [ 458, 783, 950, 951, 952 ] }

Looks useful at first glance.  Maybe s/weighted_mean/weighted-mean/
since we favor - in new QMP.


> +
> +    qemu_mutex_lock(&r->mutex);
> +    space  = 60 /* for text */ +
> +             /* 4 double values (min/max/mean/weighted) + the stored
> +              * values, plus a normal guess for the size of them printed
> +              * with %g and some padding.  I'm not sure of the worst case.
> +              */
> +             (4 + r->allocated) * 13 +
> +             /* and the count and tags as 64bit ints and some padding */
> +             (1 + r->allocated) * 23;
> +    space_left = space - 1;
> +
> +    result = g_try_malloc(space);
> +
> +    if (!result) {
> +        qemu_mutex_unlock(&r->mutex);
> +        return NULL;
> +    }
> +
> +    current = result;
> +    tmp = snprintf(current, space_left, "Min/Max: %.8g, %.8g Mean: %.8g "
> +                                        "(Weighted: %.8g) Count: %" PRIu64
> +                                        " Values: ",

Eww. Why pre-compute things for a possibly not-wide-enough snprintf,
when you can instead use glib's g_string_printf that allocates the
perfect size as it goes?  For that matter, your cover letter comment
about putting the struct in QAPI and letting the generated visitor
automatically produce the JSON might make this simpler than building it
by hand.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH 0/2] RFC: Rolling statistics

[Markus Armbruster]

Copying qemu-block, because it could be of interest for block I/O
accounting.

"Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> writes:

> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
>
> Hi,
>   This is an attempt at a generic rolling statistics utility to
> allow data (e.g. bandwidth usage, times etc) to be collected
> easily.  They hold some basic values (min/max/mean/weighted mean)
> and the last 'n' raw values.    I'd like to use this
> maybe in fault-tolerance code.
>
>   This is a first cut, and I think I probably need to rework it
> as a qapi type somehow, but I'm interested in thoughts.
>
> Dave
>
>
> Dr. David Alan Gilbert (2):
>   Rolling statistics utilities
>   Tests for rolling statistics code
>
>  include/qemu/rolling-stats.h | 101 +++++++++++
>  include/qemu/typedefs.h      |   1 +
>  tests/Makefile               |   3 +
>  tests/test-rolling-stats.c   | 161 ++++++++++++++++++
>  util/Makefile.objs           |   1 +
>  util/rolling-stats.c         | 393 +++++++++++++++++++++++++++++++++++++++++++
>  6 files changed, 660 insertions(+)
>  create mode 100644 include/qemu/rolling-stats.h
>  create mode 100644 tests/test-rolling-stats.c
>  create mode 100644 util/rolling-stats.c

Re: [Qemu-devel] [PATCH 1/2] Rolling statistics utilities

[Dr. David Alan Gilbert]

* Eric Blake (eblake@redhat.com) wrote:
> On 02/27/2015 12:06 PM, Dr. David Alan Gilbert (git) wrote:
> > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > 
> > There are various places where it's useful to hold a series
> > of values that change over time and get summaries about them.
> > 
> > This provides:
> > 
> >    - a count of the number of items
> >    - min/max
> >    - mean
> >    - a weighted mean (where you can set the weight to determine
> >                       whether it changes quickly or slowly)
> >    - the last 'n' values
> > 
> > Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
> > ---
> >  include/qemu/rolling-stats.h | 101 +++++++++++
> 
> > +
> > +/**
> > + * Return a string representing the RStats data, intended for JSON parsing
> > + *
> > + * Returns: An allocated string the caller must free
> > + *          or NULL on error
> > + *
> > + * e.g.
> > + *    { "min": -3.57, "max": 126.3, "mean": 7.83, "weighted_mean": 8.56,
> > + *      "count": 5678,
> > + *      "values": [ 4.3, 5.8, 1.2, 7.9, 10.3 ],
> > + *      "tags": [ 458, 783, 950, 951, 952 ] }
> 
> Looks useful at first glance.  Maybe s/weighted_mean/weighted-mean/
> since we favor - in new QMP.
> 
> 
> > +
> > +    qemu_mutex_lock(&r->mutex);
> > +    space  = 60 /* for text */ +
> > +             /* 4 double values (min/max/mean/weighted) + the stored
> > +              * values, plus a normal guess for the size of them printed
> > +              * with %g and some padding.  I'm not sure of the worst case.
> > +              */
> > +             (4 + r->allocated) * 13 +
> > +             /* and the count and tags as 64bit ints and some padding */
> > +             (1 + r->allocated) * 23;
> > +    space_left = space - 1;
> > +
> > +    result = g_try_malloc(space);
> > +
> > +    if (!result) {
> > +        qemu_mutex_unlock(&r->mutex);
> > +        return NULL;
> > +    }
> > +
> > +    current = result;
> > +    tmp = snprintf(current, space_left, "Min/Max: %.8g, %.8g Mean: %.8g "
> > +                                        "(Weighted: %.8g) Count: %" PRIu64
> > +                                        " Values: ",
> 
> Eww. Why pre-compute things for a possibly not-wide-enough snprintf,
> when you can instead use glib's g_string_printf that allocates the
> perfect size as it goes?

Ah, because I didn't know about that; useful.

>  For that matter, your cover letter comment
> about putting the struct in QAPI and letting the generated visitor
> automatically produce the JSON might make this simpler than building it
> by hand.

Right; I'd got this far, tried to glue it into the 'info' commands
and realised it needed to return soemthing more QAPI friendly;
but thought it best to see if people liked the general idea before attacking
that.

I'm not sure; but I think the approach would be to have a QAPI
type to hold the same data (Lets say a RollingStats type)
and then have a rstats_copy_to_rolling_stats function
that, under lock, copied the data out, that way the QAPI
type doesn't need to worry about the lock and neither does
anything outside this code.

Dave

> 
> -- 
> Eric Blake   eblake redhat com    +1-919-301-3266
> Libvirt virtualization library http://libvirt.org
> 


--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK