histogram.h File Reference

Detailed Description

This data structure is used to analyze CPU performance.

User can report data into a histogram and later get an aggregated represenation, i.e. a histogram, of these values.

A typicsl use-case would be reporting the times it took to execure a particular section of code - and later analyzing the histogram.

Date

Dec 18, 2013

Author

Andrey Belomutskiy, (c) 2012-2020

Definition in file histogram.h.

Data Structures
struct	histogram_s

Functions
void	initHistogramsModule (void)
int	histogramGetIndex (int64_t value)
	This internal method is only public so that we can test it.
void	initHistogram (histogram_s *h, const char *name)
	Reset histogram_s to orignal state.
void	hsAdd (histogram_s *h, int64_t value)
int	hsReport (histogram_s *h, int *report)
	Prepare histogram report.

Function Documentation

histogramGetIndex()

int histogramGetIndex

(

int64_t

value

)

This internal method is only public so that we can test it.

Definition at line 66 of file histogram.cpp.

                                     {
    efiAssert(ObdCode::CUSTOM_ERR_ASSERT, initialized, "histo initialized", 0);
    if (value < 0)
        return 0;
    if (value < SBI_SIZE)
        return small_bounds_index[(int) value];
    int l = small_bounds_index[SBI_SIZE - 1];
    int r = BOUND_LENGTH - 1;
    while (l < r) {
        int m = (l + r) >> 1;
        if (bounds[m] > value)
            r = m - 1;
        else if (bounds[m + 1] <= value)
            l = m + 1;
        else
            return m;
    }
    return l;
}

Referenced by hsAdd().

Here is the caller graph for this function:

hsAdd()

void hsAdd	(	histogram_s *	h,
		int64_t	value
	)

@breif Add a new value into histogram_s

Definition at line 102 of file histogram.cpp.

                                          {
    int index = histogramGetIndex(value);
    int count = 1;
    h->total_value += value;
    h->total_count += count;
    efiAssertVoid(ObdCode::CUSTOM_ERR_6670, index < BOUND_LENGTH, "histogram issue");
 
    h->values[index] += count;
}

Here is the call graph for this function:

hsReport()

int hsReport	(	histogram_s *	h,
		int *	report
	)

Prepare histogram report.

Note

This report should be displayed using 'printHistogram' method

Definition at line 116 of file histogram.cpp.

                                          {
    int index = 0;
 
    if (h->total_count <= 5) {
        for (int j = 0; j < BOUND_LENGTH; j++) {
            for (int k = 0; k < h->values[j]; k++) {
                report[index++] = (bounds[j] + bounds[j + 1]) / 2;
            }
        }
        return index;
    }
 
    int minIndex = 0;
    while (h->values[minIndex] == 0) {
        minIndex++;
    }
    report[index++] = h->values[minIndex];
 
    int64_t acc = 0;
    // 'acc' is accumulated number of samples in [0, min - 1].
    for (int j = 0; j < 3; j++) {
        int64_t k = confidence_bounds[j] * h->total_count;
        // Always drop at least 1 'non-confident' sample...
        if (k == 0) {
            k = 1;
        }
        if (k == h->total_count) {
            k = h->total_count - 1;
        }
        // 'k' is desired number of samples.
        while (acc + h->values[minIndex] < k)
            acc += h->values[minIndex++];
        if (k < h->total_count / 2) // Converge to median (from left).
            while (acc + h->values[minIndex] <= k)
                acc += h->values[minIndex++];
        // Now: acc <= k <= acc + st.histogram[min]
        // And desired number of samples is within [min, min + 1)
        float d = bounds[minIndex];
        if (acc != k)
            d += (bounds[minIndex + 1] - 1 - bounds[minIndex]) * (k - acc) / h->values[minIndex];
        report[index++] = (int) d;
    }
 
    int maxIndex = BOUND_LENGTH - 1;
    while (h->values[maxIndex] == 0)
        maxIndex--;
    int64_t maxValue = bounds[maxIndex + 1] - 1;
    report[index++] = maxValue;
 
    return index;
}

Referenced by printHistogram().

Here is the caller graph for this function:

initHistogram()

void initHistogram	(	histogram_s *	h,
		const char *	name
	)

Reset histogram_s to orignal state.

Definition at line 89 of file histogram.cpp.

                                                     {
    if (std::strlen(name) > sizeof(h->name) - 1) {
        firmwareError(ObdCode::ERROR_HISTO_NAME, "Histogram name [%s] too long", name);
    }
    strcpy(h->name, name);
    h->total_value = 0;
    h->total_count = 0;
    memset(h->values, 0, sizeof(h->values));
}

Referenced by initWaveChart().

Here is the call graph for this function:

Here is the caller graph for this function:

initHistogramsModule()

void initHistogramsModule

(

void

)

@breif Internal histogram data structure

Definition at line 44 of file histogram.cpp.

                                {
    bounds[0] = 0;
    for (int i = 1; i < BOUND_LENGTH; i++) {
        int64_t prev = bounds[i - 1];
        int64_t next = prev + (int64_t) ((double) prev * H_ACCURACY);
        if (next == prev) // Ensure minimum step for small numbers.
            next = prev + 1;
        if (next < prev) // Overflow over Long.MAX_VALUE occurred.
            next = LONG_MAX_INT;
        bounds[i] = next;
    }
    bounds[BOUND_LENGTH - 1] = LONG_MAX_INT;
 
    for (int i = 0, j = 0; j < SBI_SIZE; i++)
        while (j < bounds[i + 1] && j < SBI_SIZE)
            small_bounds_index[j++] = i;
    initialized = TRUE;
}

Referenced by initHardwareNoConfig().

Here is the caller graph for this function:

Go to the source code of this file.