Skip to contentSkip to conversation

RFC: Rolling statistics

PATCH Superseded Dr. David Alan Gilbert (git) 3 participants 6 messages Feb 27, 2015 – Mar 2, 2015

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Dr. David Alan Gilbert (git)

author
#0 lore raw

cover RFC: Rolling statistics

From: "Dr. David Alan Gilbert" <[email protected]>

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
Signature · 1 line
2.1.0
author
#1 lore raw

PATCH 1/2 Rolling statistics utilities

From: "Dr. David Alan Gilbert" <[email protected]>

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 <[email protected]>
---
 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
include/qemu/rolling-stats.h new file +101 -0
new file mode 100644
index 0000000..d64ce78
@@ -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 <[email protected]>
+ *
+ * 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
include/qemu/typedefs.h +1 -0
index cde3314..3488dfd 100644
@@ -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;
util/Makefile.objs +1 -0
index ceaba30..b45af66 100644
@@ -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
util/rolling-stats.c new file +393 -0

393 lines not on this page · raw message

Signature · 1 line
2.1.0
#2 lore raw

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

Quoted 20 lines · Dr. David Alan Gilbert (git)

From: "Dr. David Alan Gilbert" <[email protected]>

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 <[email protected]>
---
 include/qemu/rolling-stats.h | 101 +++++++++++
include/qemu/rolling-stats.h new file +2 -0
+
+/**

include/qemu/rolling-stats.h line 72

Quoted 10 lines
include/qemu/rolling-stats.h new file +10 -0
+ * 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.

Quoted 13 lines
util/rolling-stats.c new file +13 -0
+
+    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);

util/rolling-stats.c line 223

Quoted 10 lines
util/rolling-stats.c new file +10 -0
+
+    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.

Signature · 2 lines
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org
author
#3 lore raw

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

Quoted 55 lines · * Eric Blake ([email protected]) wrote:
Quoted 20 lines · Dr. David Alan Gilbert (git)

From: "Dr. David Alan Gilbert" <[email protected]>

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 <[email protected]>
---
 include/qemu/rolling-stats.h | 101 +++++++++++
include/qemu/rolling-stats.h new file +2 -0
+
+/**

include/qemu/rolling-stats.h line 72

Quoted 10 lines
include/qemu/rolling-stats.h new file +10 -0
+ * 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.

Quoted 19 lines
util/rolling-stats.c new file +19 -0
+
+    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;
+    }
+
Quoted 8 lines

util/rolling-stats.c line 223

Quoted 4 lines
util/rolling-stats.c new file +4 -0
+    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.

Quoted 4 lines

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

Quoted 5 lines
Signature · 3 lines
-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

--
Dr. David Alan Gilbert / [email protected] / Manchester, UK

author
#4 lore raw

PATCH 2/2 Tests for rolling statistics code

In reply to Dr. David Alan Gilbert (git)

From: "Dr. David Alan Gilbert" <[email protected]>

Signed-off-by Dr. David Alan Gilbert <[email protected]>
---
 tests/Makefile             |   3 +
 tests/test-rolling-stats.c | 161 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 164 insertions(+)
 create mode 100644 tests/test-rolling-stats.c
tests/Makefile +3 -0
index 307035c..2d42eb2 100644
@@ -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
tests/test-rolling-stats.c new file +161 -0

161 lines not on this page · raw message

Signature · 1 line
2.1.0
#5 lore raw
In reply to Dr. David Alan Gilbert (git)

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

Quoted 29 lines · Dr. David Alan Gilbert (git)

From: "Dr. David Alan Gilbert" <[email protected]>

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