diff mbox

[v6,08/15] qdist: add module to represent frequency distributions of data

Message ID 20160608000224.GB16255@flamenco (mailing list archive)
State New, archived
Headers show

Commit Message

Emilio Cota June 8, 2016, 12:02 a.m. UTC
On Tue, Jun 07, 2016 at 18:56:48 +0300, Sergey Fedorov wrote:
> On 07/06/16 04:05, Emilio G. Cota wrote:
> > On Sat, May 28, 2016 at 21:15:06 +0300, Sergey Fedorov wrote:
> >> On 25/05/16 04:13, Emilio G. Cota wrote:
> >>> diff --git a/util/qdist.c b/util/qdist.c
> >>> new file mode 100644
> >>> index 0000000..3343640
> >>> --- /dev/null
> >>> +++ b/util/qdist.c
> >>> @@ -0,0 +1,386 @@
> >> (snip)
> >>> +
> >>> +void qdist_add(struct qdist *dist, double x, long count)
> >>> +{
> >>> +    struct qdist_entry *entry = NULL;
> >>> +
> >>> +    if (dist->entries) {
> >>> +        struct qdist_entry e;
> >>> +
> >>> +        e.x = x;
> >>> +        entry = bsearch(&e, dist->entries, dist->n, sizeof(e), qdist_cmp);
> >>> +    }
> >>> +
> >>> +    if (entry) {
> >>> +        entry->count += count;
> >>> +        return;
> >>> +    }
> >>> +
> >>> +    dist->entries = g_realloc(dist->entries,
> >>> +                              sizeof(*dist->entries) * (dist->n + 1));
> >> Repeated doubling?
> > Can you please elaborate?
> 
> I mean dynamic array with a growth factor of 2
> [https://en.wikipedia.org/wiki/Dynamic_array].

Changed to:



> >> (snip)
> >>> +static char *qdist_pr_internal(const struct qdist *dist)
> >>> +{
> >>> +    double min, max, step;
> >>> +    GString *s = g_string_new("");
> >>> +    size_t i;
> >>> +
> >>> +    /* if only one entry, its printout will be either full or empty */
> >>> +    if (dist->n == 1) {
> >>> +        if (dist->entries[0].count) {
> >>> +            g_string_append_unichar(s, qdist_blocks[QDIST_NR_BLOCK_CODES - 1]);
> >>> +        } else {
> >>> +            g_string_append_c(s, ' ');
> >>> +        }
> >>> +        goto out;
> >>> +    }
> >>> +
> >>> +    /* get min and max counts */
> >>> +    min = dist->entries[0].count;
> >>> +    max = min;
> >>> +    for (i = 0; i < dist->n; i++) {
> >>> +        struct qdist_entry *e = &dist->entries[i];
> >>> +
> >>> +        if (e->count < min) {
> >>> +            min = e->count;
> >>> +        }
> >>> +        if (e->count > max) {
> >>> +            max = e->count;
> >>> +        }
> >>> +    }
> >>> +
> >>> +    /* floor((count - min) * step) will give us the block index */
> >>> +    step = (QDIST_NR_BLOCK_CODES - 1) / (max - min);
> >>> +
> >>> +    for (i = 0; i < dist->n; i++) {
> >>> +        struct qdist_entry *e = &dist->entries[i];
> >>> +        int index;
> >>> +
> >>> +        /* make an exception with 0; instead of using block[0], print a space */
> >>> +        if (e->count) {
> >>> +            index = (int)((e->count - min) * step);
> >> So "e->count == min" gives us one eighth block instead of just space?
> > Yes, only 0 can print a space.
> 
> So our scale is not linear. I think some users might get confused by this.

That's correct. I think special-casing 0 makes sense though, since
it increases the signal-to-noise ratio of the histogram. For example:

1) 0 as ' ':
TB hash occupancy   31.84% avg chain occ. Histogram: [0,10)%|▆ █  ▅▁▃▁▁|[90,100]%
TB hash avg chain   1.015 buckets. Histogram: 1|█▁▁|3

2) 0 as '1/8':
TB hash occupancy   32.07% avg chain occ. Histogram: [0,10)%|▆▁█▁▁▅▁▃▁▁|[90,100]%
TB hash avg chain   1.015 buckets. Histogram: 1|▇▁▁|3

I think in these examples most users would be less confused by 1) than by 2).

(snip)
> >>> +        to->n = from->n;
> >>> +        memcpy(to->entries, from->entries, sizeof(*to->entries) * to->n);
> >>> +        return;
> >>> +    }
> >>> +
> >>> + rebin:
> 
> By the way, here's a space before the 'rebin' label.

Yes, I always do this.
It prevents diff from mistaking the label for a function definition,
and thus wrongly using the label as context. See:
  https://lkml.org/lkml/2010/6/16/312


> >>> +    j_min = 0;
> >>> +    for (i = 0; i < n; i++) {
> >>> +        double x;
> >>> +        double left, right;
> >>> +
> >>> +        left = xmin + i * step;
> >>> +        right = xmin + (i + 1) * step;
> >>> +
> >>> +        /* Add x, even if it might not get any counts later */
> >>> +        x = left;
> >> This way we round down to the left margin of each bin like this:
> >>
> >>     xmin [*---*---*---*---*] xmax   -- from
> >>           |  /|  /|  /|  /
> >>           | / | / | / | /
> >>           |/  |/  |/  |/
> >>           |   |   |   |
> >>           V   V   V   V
> >>          [*   *   *   *]            -- to
> > (snip)
> >>     xmin [*----*----*----*] xmax    -- from
> >>         \   /\   /\   /\   /
> >>          \ /  \ /  \ /  \ /
> >>           |    |    |    |
> >>           V    V    V    V
> >>          [*    *    *    *]         -- to
> >>
> >> I'm not sure which is the more correct option from the mathematical
> >> point of view; but multiple-binning with the last variant of the
> >> algorithm we would still give the same result.
> > There's no "right" or "wrong" way as long as we're consistent
> > and we print the right counts in the right bins. I think the
> > convention I chose is simple enough, and leads to simple printing
> > of the labels. But yes other alternatives would be OK here.
> 
> Well, if we go ahead with my last suggestion the code would look like this:
> 
> rebin:
>     /* We do the binning using the following scheme:
>      *
>      *  xmin [*----*----*----*] xmax    -- from
>      *      \   /\   /\   /\   /
>      *       \ /  \ /  \ /  \ /
>      *        |    |    |    |
>      *        V    V    V    V
>      *       [*    *    *    *]         -- to
>      *
>      */
>     step = (xmax - xmin) / (n - 1);
>     j = 0;
>     for (i = 0; i < n; i++) {
>         double x;
>         double right;
> 
>         x = xmin + i * step;
>         right = x + 0.5 * step;
> 
>         /* Add x, even if it might not get any counts later */
>         qdist_add(to, x, 0);
> 
>         /* To avoid double-counting we capture [left, right) ranges */
>         while (from->entries[j].x < right && j < from->n) {
>             qdist_add(to, x, from->entries[j].count);
>             j++;
>         }
>     }
>     assert(j == from->n);
> }
> 
> Actually it's simpler than current version.

The behaviour isn't the same though. With this we have
that the two outer bins (leftmost and rightmost) are unnecessarily
large (since they're out of the range of the input data).

For example, assume the data is between 0 and 100 and n=5 (i.e. step=25),
it makes no sense to report the first bin as [-12.5,12.5). If we
then truncate the unnecessary edges, we'd have [0,12.5), but
then the second bin is [12.5,37.5). Bins of unequal size are
possible (although a bit unusual) in histograms, but given
our Unicode-based representation, we're limited to same-width bars.

		Emilio

Comments

Sergey Fedorov June 8, 2016, 2:10 p.m. UTC | #1
On 08/06/16 03:02, Emilio G. Cota wrote:
> On Tue, Jun 07, 2016 at 18:56:48 +0300, Sergey Fedorov wrote:
>> On 07/06/16 04:05, Emilio G. Cota wrote:
>>> On Sat, May 28, 2016 at 21:15:06 +0300, Sergey Fedorov wrote:
>>>> On 25/05/16 04:13, Emilio G. Cota wrote:
>>>>> diff --git a/util/qdist.c b/util/qdist.c
>>>>> new file mode 100644
>>>>> index 0000000..3343640
>>>>> --- /dev/null
>>>>> +++ b/util/qdist.c
>>>>> @@ -0,0 +1,386 @@
>>>> (snip)
>>>>> +
>>>>> +void qdist_add(struct qdist *dist, double x, long count)
>>>>> +{
>>>>> +    struct qdist_entry *entry = NULL;
>>>>> +
>>>>> +    if (dist->entries) {
>>>>> +        struct qdist_entry e;
>>>>> +
>>>>> +        e.x = x;
>>>>> +        entry = bsearch(&e, dist->entries, dist->n, sizeof(e), qdist_cmp);
>>>>> +    }
>>>>> +
>>>>> +    if (entry) {
>>>>> +        entry->count += count;
>>>>> +        return;
>>>>> +    }
>>>>> +
>>>>> +    dist->entries = g_realloc(dist->entries,
>>>>> +                              sizeof(*dist->entries) * (dist->n + 1));
>>>> Repeated doubling?
>>> Can you please elaborate?
>> I mean dynamic array with a growth factor of 2
>> [https://en.wikipedia.org/wiki/Dynamic_array].
> Changed to:
>
> diff --git a/include/qemu/qdist.h b/include/qemu/qdist.h
> index 6d8b701..f30050c 100644
> --- a/include/qemu/qdist.h
> +++ b/include/qemu/qdist.h
> @@ -29,6 +29,7 @@ struct qdist_entry {
>  struct qdist {
>      struct qdist_entry *entries;
>      size_t n;
> +    size_t size;
>  };
>  
>  #define QDIST_PR_BORDER     BIT(0)
> diff --git a/util/qdist.c b/util/qdist.c
> index dc9dbd1..3b54354 100644
> --- a/util/qdist.c
> +++ b/util/qdist.c
> @@ -16,6 +16,7 @@
>  void qdist_init(struct qdist *dist)
>  {
>      dist->entries = NULL;
> +    dist->size = 0;
>      dist->n = 0;
>  }
>  
> @@ -58,8 +59,11 @@ void qdist_add(struct qdist *dist, double x, long count)
>          return;
>      }
>  
> -    dist->entries = g_realloc(dist->entries,
> -                              sizeof(*dist->entries) * (dist->n + 1));
> +    if (unlikely(dist->n == dist->size)) {
> +        dist->size = dist->size ? dist->size * 2 : 1;

We could initialize 'dist->size' to 1 and allocate a 1-entry
'dist->entries' array in qdist_init() to avoid this ternary operation ;-)

Otherwise looks good.

> +        dist->entries = g_realloc(dist->entries,
> +                                  sizeof(*dist->entries) * (dist->size));
> +    }
>      dist->n++;
>      entry = &dist->entries[dist->n - 1];
>      entry->x = x;
>
>
>>>> (snip)
>>>>> +static char *qdist_pr_internal(const struct qdist *dist)
>>>>> +{
>>>>> +    double min, max, step;
>>>>> +    GString *s = g_string_new("");
>>>>> +    size_t i;
>>>>> +
>>>>> +    /* if only one entry, its printout will be either full or empty */
>>>>> +    if (dist->n == 1) {
>>>>> +        if (dist->entries[0].count) {
>>>>> +            g_string_append_unichar(s, qdist_blocks[QDIST_NR_BLOCK_CODES - 1]);
>>>>> +        } else {
>>>>> +            g_string_append_c(s, ' ');
>>>>> +        }
>>>>> +        goto out;
>>>>> +    }
>>>>> +
>>>>> +    /* get min and max counts */
>>>>> +    min = dist->entries[0].count;
>>>>> +    max = min;
>>>>> +    for (i = 0; i < dist->n; i++) {
>>>>> +        struct qdist_entry *e = &dist->entries[i];
>>>>> +
>>>>> +        if (e->count < min) {
>>>>> +            min = e->count;
>>>>> +        }
>>>>> +        if (e->count > max) {
>>>>> +            max = e->count;
>>>>> +        }
>>>>> +    }
>>>>> +
>>>>> +    /* floor((count - min) * step) will give us the block index */
>>>>> +    step = (QDIST_NR_BLOCK_CODES - 1) / (max - min);
>>>>> +
>>>>> +    for (i = 0; i < dist->n; i++) {
>>>>> +        struct qdist_entry *e = &dist->entries[i];
>>>>> +        int index;
>>>>> +
>>>>> +        /* make an exception with 0; instead of using block[0], print a space */
>>>>> +        if (e->count) {
>>>>> +            index = (int)((e->count - min) * step);
>>>> So "e->count == min" gives us one eighth block instead of just space?
>>> Yes, only 0 can print a space.
>> So our scale is not linear. I think some users might get confused by this.
> That's correct. I think special-casing 0 makes sense though, since
> it increases the signal-to-noise ratio of the histogram. For example:
>
> 1) 0 as ' ':
> TB hash occupancy   31.84% avg chain occ. Histogram: [0,10)%|▆ █  ▅▁▃▁▁|[90,100]%
> TB hash avg chain   1.015 buckets. Histogram: 1|█▁▁|3
>
> 2) 0 as '1/8':
> TB hash occupancy   32.07% avg chain occ. Histogram: [0,10)%|▆▁█▁▁▅▁▃▁▁|[90,100]%
> TB hash avg chain   1.015 buckets. Histogram: 1|▇▁▁|3
>
> I think in these examples most users would be less confused by 1) than by 2).

I was meaning to represent all bars whose value < 1/8 as a space, not
only whose value is pure zero. Otherwise we can see 1/8 bar where the
actual value is negligibly differ from zero as in the second example.

>
> (snip)
>>>>> +        to->n = from->n;
>>>>> +        memcpy(to->entries, from->entries, sizeof(*to->entries) * to->n);
>>>>> +        return;
>>>>> +    }
>>>>> +
>>>>> + rebin:
>> By the way, here's a space before the 'rebin' label.
> Yes, I always do this.
> It prevents diff from mistaking the label for a function definition,
> and thus wrongly using the label as context. See:
>   https://lkml.org/lkml/2010/6/16/312

Cool!

>
>
>>>>> +    j_min = 0;
>>>>> +    for (i = 0; i < n; i++) {
>>>>> +        double x;
>>>>> +        double left, right;
>>>>> +
>>>>> +        left = xmin + i * step;
>>>>> +        right = xmin + (i + 1) * step;
>>>>> +
>>>>> +        /* Add x, even if it might not get any counts later */
>>>>> +        x = left;
>>>> This way we round down to the left margin of each bin like this:
>>>>
>>>>     xmin [*---*---*---*---*] xmax   -- from
>>>>           |  /|  /|  /|  /
>>>>           | / | / | / | /
>>>>           |/  |/  |/  |/
>>>>           |   |   |   |
>>>>           V   V   V   V
>>>>          [*   *   *   *]            -- to
>>> (snip)
>>>>     xmin [*----*----*----*] xmax    -- from
>>>>         \   /\   /\   /\   /
>>>>          \ /  \ /  \ /  \ /
>>>>           |    |    |    |
>>>>           V    V    V    V
>>>>          [*    *    *    *]         -- to
>>>>
>>>> I'm not sure which is the more correct option from the mathematical
>>>> point of view; but multiple-binning with the last variant of the
>>>> algorithm we would still give the same result.
>>> There's no "right" or "wrong" way as long as we're consistent
>>> and we print the right counts in the right bins. I think the
>>> convention I chose is simple enough, and leads to simple printing
>>> of the labels. But yes other alternatives would be OK here.
>> Well, if we go ahead with my last suggestion the code would look like this:
>>
>> rebin:
>>     /* We do the binning using the following scheme:
>>      *
>>      *  xmin [*----*----*----*] xmax    -- from
>>      *      \   /\   /\   /\   /
>>      *       \ /  \ /  \ /  \ /
>>      *        |    |    |    |
>>      *        V    V    V    V
>>      *       [*    *    *    *]         -- to
>>      *
>>      */
>>     step = (xmax - xmin) / (n - 1);
>>     j = 0;
>>     for (i = 0; i < n; i++) {
>>         double x;
>>         double right;
>>
>>         x = xmin + i * step;
>>         right = x + 0.5 * step;
>>
>>         /* Add x, even if it might not get any counts later */
>>         qdist_add(to, x, 0);
>>
>>         /* To avoid double-counting we capture [left, right) ranges */
>>         while (from->entries[j].x < right && j < from->n) {
>>             qdist_add(to, x, from->entries[j].count);
>>             j++;
>>         }
>>     }
>>     assert(j == from->n);
>> }
>>
>> Actually it's simpler than current version.
> The behaviour isn't the same though. With this we have
> that the two outer bins (leftmost and rightmost) are unnecessarily
> large (since they're out of the range of the input data).
>
> For example, assume the data is between 0 and 100 and n=5 (i.e. step=25),
> it makes no sense to report the first bin as [-12.5,12.5). If we
> then truncate the unnecessary edges, we'd have [0,12.5), but
> then the second bin is [12.5,37.5). Bins of unequal size are
> possible (although a bit unusual) in histograms, but given
> our Unicode-based representation, we're limited to same-width bars.

That is why I noted that I'm not sure what is the most correct from
mathematical point of view. Maybe consider the second option? I.e.
rounding to the middle of each bin with:

    x = left + step / 2;

which would give the picture like this:


    xmin [*---*---*---*---*] xmax   -- from
          |   |   |   |   |
           \ / \ / \ / \ /
            |   |   |   |
            V   V   V   V
           [*   *   *   *]          -- to

Anyway, you may consider if you like whether it's possible to apply some
simplifications from my code to the final version.

Kind regards,
Sergey
diff mbox

Patch

diff --git a/include/qemu/qdist.h b/include/qemu/qdist.h
index 6d8b701..f30050c 100644
--- a/include/qemu/qdist.h
+++ b/include/qemu/qdist.h
@@ -29,6 +29,7 @@  struct qdist_entry {
 struct qdist {
     struct qdist_entry *entries;
     size_t n;
+    size_t size;
 };
 
 #define QDIST_PR_BORDER     BIT(0)
diff --git a/util/qdist.c b/util/qdist.c
index dc9dbd1..3b54354 100644
--- a/util/qdist.c
+++ b/util/qdist.c
@@ -16,6 +16,7 @@ 
 void qdist_init(struct qdist *dist)
 {
     dist->entries = NULL;
+    dist->size = 0;
     dist->n = 0;
 }
 
@@ -58,8 +59,11 @@  void qdist_add(struct qdist *dist, double x, long count)
         return;
     }
 
-    dist->entries = g_realloc(dist->entries,
-                              sizeof(*dist->entries) * (dist->n + 1));
+    if (unlikely(dist->n == dist->size)) {
+        dist->size = dist->size ? dist->size * 2 : 1;
+        dist->entries = g_realloc(dist->entries,
+                                  sizeof(*dist->entries) * (dist->size));
+    }
     dist->n++;
     entry = &dist->entries[dist->n - 1];
     entry->x = x;