blob: 6e2a7f2f96d3559878bb6d35a11bd85994cb3962 [file] [log] [blame]
/*
* Copyright (c) 2021 Daniel R. Carvalho
* Copyright (c) 2019 Arm Limited
* All rights reserved.
*
* The license below extends only to copyright in the software and shall
* not be construed as granting a license to any other intellectual
* property including but not limited to intellectual property relating
* to a hardware implementation of the functionality of the software
* licensed hereunder. You may use the software subject to the license
* terms below provided that you ensure that this notice is replicated
* unmodified and in its entirety in all distributions of the software,
* modified or unmodified, in source code or in binary form.
*
* Copyright (c) 2003-2005 The Regents of The University of Michigan
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met: redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer;
* redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution;
* neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "base/stats/storage.hh"
#include <cmath>
namespace Stats {
void
DistStor::sample(Counter val, int number)
{
assert(bucket_size > 0);
if (val < min_track)
underflow += number;
else if (val > max_track)
overflow += number;
else {
cvec[std::floor((val - min_track) / bucket_size)] += number;
}
if (val < min_val)
min_val = val;
if (val > max_val)
max_val = val;
sum += val * number;
squares += val * val * number;
samples += number;
}
void
HistStor::growOut()
{
int size = cvec.size();
int zero = size / 2; // round down!
int top_half = zero + (size - zero + 1) / 2; // round up!
int bottom_half = (size - zero) / 2; // round down!
// grow down
int low_pair = zero - 1;
for (int i = zero - 1; i >= bottom_half; i--) {
cvec[i] = cvec[low_pair];
if (low_pair - 1 >= 0)
cvec[i] += cvec[low_pair - 1];
low_pair -= 2;
}
assert(low_pair == 0 || low_pair == -1 || low_pair == -2);
for (int i = bottom_half - 1; i >= 0; i--)
cvec[i] = Counter();
// grow up
int high_pair = zero;
for (int i = zero; i < top_half; i++) {
cvec[i] = cvec[high_pair];
if (high_pair + 1 < size)
cvec[i] += cvec[high_pair + 1];
high_pair += 2;
}
assert(high_pair == size || high_pair == size + 1);
for (int i = top_half; i < size; i++)
cvec[i] = Counter();
max_bucket *= 2;
min_bucket *= 2;
bucket_size *= 2;
}
void
HistStor::growDown()
{
const int size = cvec.size();
const int zero = size / 2; // round down!
const bool even = ((size - 1) % 2) == 0;
// Make sure that zero becomes the lower bound of the middle bucket. On
// an even number of buckets the last bucket does not change its lower
// bound, therefore it does not need to absorb any other bucket
int pair = size - 1;
if (even) {
pair--;
}
for (int i = pair; i >= zero; --i) {
cvec[i] = cvec[pair];
if (pair - 1 >= 0)
cvec[i] += cvec[pair - 1];
pair -= 2;
}
for (int i = zero - 1; i >= 0; i--)
cvec[i] = Counter();
// Double the range by using the negative of the lower bound of the last
// bucket as the new lower bound of the first bucket
min_bucket = -max_bucket;
// A special case must be handled when there is an odd number of
// buckets so that zero is kept as the lower bound of the middle bucket
if (!even) {
min_bucket -= bucket_size;
max_bucket -= bucket_size;
}
// Only update the bucket size once the range has been updated
bucket_size *= 2;
}
void
HistStor::growUp()
{
int size = cvec.size();
int half = (size + 1) / 2; // round up!
int pair = 0;
for (int i = 0; i < half; i++) {
cvec[i] = cvec[pair];
if (pair + 1 < size)
cvec[i] += cvec[pair + 1];
pair += 2;
}
assert(pair == size || pair == size + 1);
for (int i = half; i < size; i++)
cvec[i] = Counter();
max_bucket *= 2;
bucket_size *= 2;
}
void
HistStor::sample(Counter val, int number)
{
assert(min_bucket < max_bucket);
if (val < min_bucket) {
if (min_bucket == 0)
growDown();
while (val < min_bucket)
growOut();
} else if (val >= max_bucket + bucket_size) {
if (min_bucket == 0) {
while (val >= max_bucket + bucket_size)
growUp();
} else {
while (val >= max_bucket + bucket_size)
growOut();
}
}
assert(bucket_size > 0);
size_type index =
(int64_t)std::floor((val - min_bucket) / bucket_size);
assert(index < size());
cvec[index] += number;
sum += val * number;
squares += val * val * number;
logs += std::log(val) * number;
samples += number;
}
void
HistStor::add(HistStor *hs)
{
int b_size = hs->size();
assert(size() == b_size);
assert(min_bucket == hs->min_bucket);
sum += hs->sum;
logs += hs->logs;
squares += hs->squares;
samples += hs->samples;
while (bucket_size > hs->bucket_size)
hs->growUp();
while (bucket_size < hs->bucket_size)
growUp();
for (uint32_t i = 0; i < b_size; i++)
cvec[i] += hs->cvec[i];
}
} // namespace Stats