profile.c File Reference

Profiling. More...

#include <stdint.h>
#include <stdio.h>
#include <strings.h>
#include <limits.h>
#include <assert.h>
#include <ipxe/isqrt.h>
#include <ipxe/profile.h>

Go to the source code of this file.

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static const char *	profile_hex_fraction (signed long long value, unsigned int shift)
	Format a hex fraction (for debugging) More...
static unsigned int	profile_mean_shift (struct profiler *profiler)
	Calculate bit shift for mean sample value. More...
static unsigned int	profile_accvar_shift (struct profiler *profiler)
	Calculate bit shift for accumulated variance value. More...
void	profile_update (struct profiler *profiler, unsigned long sample)
	Update profiler with a new sample. More...
unsigned long	profile_mean (struct profiler *profiler)
	Get mean sample value. More...
unsigned long	profile_variance (struct profiler *profiler)
	Get sample variance. More...
unsigned long	profile_stddev (struct profiler *profiler)
	Get sample standard deviation. More...

Variables
unsigned long	profile_excluded
	Accumulated time excluded from profiling. More...

Detailed Description

Profiling.

The profiler computes basic statistics (mean, variance, and standard deviation) for the samples which it records. Note that these statistics need not be completely accurate; it is sufficient to give a rough approximation.

The algorithm for updating the mean and variance estimators is from The Art of Computer Programming (via Wikipedia), with adjustments to avoid the use of floating-point instructions.

Definition in file profile.c.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

profile_hex_fraction()

static const char* profile_hex_fraction ( signed long long  value, unsigned int  shift  )

static

Format a hex fraction (for debugging)

Parameters

value	Value
shift	Bit shift

Return values

string

Formatted hex fraction

Definition at line 58 of file profile.c.

                                                                {
        static char buf[23] = "-"; /* -0xXXXXXXXXXXXXXXXX.XX + NUL */
        unsigned long long int_part;
        uint8_t frac_part;
        char *ptr;

        if ( value < 0 ) {
                value = -value;
                ptr = &buf[0];
        } else {
                ptr = &buf[1];
        }
        int_part = ( value >> shift );
        frac_part = ( value >> ( shift - ( 8 * sizeof ( frac_part ) ) ) );
        snprintf ( &buf[1], ( sizeof ( buf ) - 1  ), "%#llx.%02x",
                   int_part, frac_part );
        return ptr;
}

References snprintf(), and value.

Referenced by profile_update().

profile_mean_shift()

static unsigned int profile_mean_shift ( struct profiler *  profiler )

inlinestatic

Calculate bit shift for mean sample value.

Parameters

profiler

Profiler

Return values

shift

Bit shift

Definition at line 84 of file profile.c.

                                                                            {

        return ( ( ( 8 * sizeof ( profiler->mean ) ) - 1 ) /* MSB */
                 - 1 /* Leave sign bit unused */
                 - profiler->mean_msb );
}

References profiler::mean, and profiler::mean_msb.

Referenced by profile_mean(), and profile_update().

profile_accvar_shift()

static unsigned int profile_accvar_shift ( struct profiler *  profiler )

inlinestatic

Calculate bit shift for accumulated variance value.

Parameters

profiler

Profiler

Return values

shift

Bit shift

Definition at line 97 of file profile.c.

                                                                              {

        return ( ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) /* MSB */
                 - 1 /* Leave top bit unused */
                 - profiler->accvar_msb );
}

References profiler::accvar, and profiler::accvar_msb.

Referenced by profile_update(), and profile_variance().

profile_update()

void profile_update	(	struct profiler *	profiler,
		unsigned long	sample
	)

Update profiler with a new sample.

Parameters

profiler	Profiler
sample	Sample value

Definition at line 110 of file profile.c.

                                                                        {
        unsigned int sample_msb;
        unsigned int mean_shift;
        unsigned int delta_shift;
        signed long pre_delta;
        signed long post_delta;
        signed long long accvar_delta;
        unsigned int accvar_delta_shift;
        unsigned int accvar_delta_msb;
        unsigned int accvar_shift;

        /* Our scaling logic assumes that sample values never overflow
         * a signed long (i.e. that the high bit is always zero).
         */
        assert ( ( ( signed ) sample ) >= 0 );

        /* Update sample count, limiting to avoid signed overflow */
        if ( profiler->count < INT_MAX )
                profiler->count++;

        /* Adjust mean sample value scale if necessary.  Skip if
         * sample is zero (in which case flsl(sample)-1 would
         * underflow): in the case of a zero sample we have no need to
         * adjust the scale anyway.
         */
        if ( sample ) {
                sample_msb = ( flsl ( sample ) - 1 );
                if ( profiler->mean_msb < sample_msb ) {
                        profiler->mean >>= ( sample_msb - profiler->mean_msb );
                        profiler->mean_msb = sample_msb;
                }
        }

        /* Scale sample to internal units */
        mean_shift = profile_mean_shift ( profiler );
        sample <<= mean_shift;

        /* Update mean */
        pre_delta = ( sample - profiler->mean );
        profiler->mean += ( pre_delta / ( ( signed ) profiler->count ) );
        post_delta = ( sample - profiler->mean );
        delta_shift = mean_shift;
        DBGC ( profiler, "PROFILER %p sample %#lx mean %s", profiler,
               ( sample >> mean_shift ),
                profile_hex_fraction ( profiler->mean, mean_shift ) );
        DBGC ( profiler, " pre %s",
               profile_hex_fraction ( pre_delta, delta_shift ) );
        DBGC ( profiler, " post %s\n",
               profile_hex_fraction ( post_delta, delta_shift ) );

        /* Scale both deltas to fit in half of an unsigned long long
         * to avoid potential overflow on multiplication.  Note that
         * shifting a signed quantity is "implementation-defined"
         * behaviour in the C standard, but gcc documents that it will
         * always perform sign extension.
         */
        if ( sizeof ( pre_delta ) > ( sizeof ( accvar_delta ) / 2 ) ) {
                unsigned int shift = ( 8 * ( sizeof ( pre_delta ) -
                                             ( sizeof ( accvar_delta ) / 2 ) ));
                pre_delta >>= shift;
                post_delta >>= shift;
                delta_shift -= shift;
        }

        /* Update variance, if applicable.  Skip if either delta is
         * zero (in which case flsl(delta)-1 would underflow): in the
         * case of a zero delta there is no change to the accumulated
         * variance anyway.
         */
        if ( pre_delta && post_delta ) {

                /* Calculate variance delta */
                accvar_delta = ( ( ( signed long long ) pre_delta ) *
                                 ( ( signed long long ) post_delta ) );
                accvar_delta_shift = ( 2 * delta_shift );
                assert ( accvar_delta > 0 );

                /* Calculate variance delta MSB, using flsl() on each
                 * delta individually to provide an upper bound rather
                 * than requiring the existence of flsll().
                 */
                accvar_delta_msb = ( flsll ( accvar_delta ) - 1 );
                if ( accvar_delta_msb > accvar_delta_shift ) {
                        accvar_delta_msb -= accvar_delta_shift;
                } else {
                        accvar_delta_msb = 0;
                }

                /* Adjust scales as necessary */
                if ( profiler->accvar_msb < accvar_delta_msb ) {
                        /* Rescale accumulated variance */
                        profiler->accvar >>= ( accvar_delta_msb -
                                               profiler->accvar_msb );
                        profiler->accvar_msb = accvar_delta_msb;
                } else {
                        /* Rescale variance delta */
                        accvar_delta >>= ( profiler->accvar_msb -
                                           accvar_delta_msb );
                        accvar_delta_shift -= ( profiler->accvar_msb -
                                                accvar_delta_msb );
                }

                /* Scale delta to internal units */
                accvar_shift = profile_accvar_shift ( profiler );
                accvar_delta <<= ( accvar_shift - accvar_delta_shift );

                /* Accumulate variance */
                profiler->accvar += accvar_delta;

                /* Adjust scale if necessary */
                if ( profiler->accvar &
                     ( 1ULL << ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) ) ) {
                        profiler->accvar >>= 1;
                        profiler->accvar_msb++;
                        accvar_delta >>= 1;
                        accvar_shift--;
                }

                DBGC ( profiler, "PROFILER %p accvar %s", profiler,
                       profile_hex_fraction ( profiler->accvar, accvar_shift ));
                DBGC ( profiler, " delta %s\n",
                       profile_hex_fraction ( accvar_delta, accvar_shift ) );
        }
}

References profiler::accvar, profiler::accvar_msb, assert(), profiler::count, DBGC, flsl, flsll, INT_MAX, profiler::mean, profiler::mean_msb, profile_accvar_shift(), profile_hex_fraction(), and profile_mean_shift().

Referenced by profile_custom(), profile_okx(), and profile_stop_at().

profile_mean()

unsigned long profile_mean

(

struct profiler *

profiler

)

Get mean sample value.

Parameters

profiler

Profiler

Return values

mean	Mean sample value

Definition at line 241 of file profile.c.

                                                         {
        unsigned int mean_shift = profile_mean_shift ( profiler );

        /* Round to nearest and scale down to original units */
        return ( ( profiler->mean + ( 1UL << ( mean_shift - 1 ) ) )
                 >> mean_shift );
}

References profiler::mean, and profile_mean_shift().

Referenced by cipher_cost(), digest_cost(), memcpy_test_speed(), profile_okx(), profstat(), and tcpip_random_okx().

profile_variance()

unsigned long profile_variance

(

struct profiler *

profiler

)

Get sample variance.

Parameters

profiler

Profiler

Return values

variance

Sample variance

Definition at line 255 of file profile.c.

                                                             {
        unsigned int accvar_shift = profile_accvar_shift ( profiler );

        /* Variance is zero if fewer than two samples exist (avoiding
         * division by zero error).
         */
        if ( profiler->count < 2 )
                return 0;

        /* Calculate variance, round to nearest, and scale to original units */
        return ( ( ( profiler->accvar / ( profiler->count - 1 ) )
                   + ( 1ULL << ( accvar_shift - 1 ) ) ) >> accvar_shift );
}

References profiler::accvar, profiler::count, and profile_accvar_shift().

Referenced by profile_stddev().

profile_stddev()

unsigned long profile_stddev

(

struct profiler *

profiler

)

Get sample standard deviation.

Parameters

profiler

Profiler

Return values

stddev

Sample standard deviation

Definition at line 275 of file profile.c.

                                                           {

        return isqrt ( profile_variance ( profiler ) );
}

References isqrt(), and profile_variance().

Referenced by memcpy_test_speed(), profile_okx(), profstat(), and tcpip_random_okx().

Variable Documentation

profile_excluded

unsigned long profile_excluded

Accumulated time excluded from profiling.

Definition at line 49 of file profile.c.

Referenced by profile_exclude(), profile_start_at(), profile_started(), profile_stop_at(), and profile_stopped().