VOID measurePerfData()

in unittest/lib/perf.cpp [910:1041]

• 86 lines of code
• 9 McCabe index (conditional complexity)

VOID measurePerfData(
                        PerfKeyFn keyFn,
                        PerfDataFn prepFn,
                        PerfDataFn dataFn,
                        PerfCleanFn cleanFn,
                        std::set<SIZE_T> * pDataSizes,
                        SIZE_T keySize,
                        AlgorithmImplementation::ALG_PERF_INFO * pRes )
{
    SIZE_T x[ MAX_SIZES ];
    double y[ MAX_SIZES ];
    double perByte;
    double fixed;

    SIZE_T sumXi = 0;
    SIZE_T n = 0;

    for( std::set<SIZE_T>::const_iterator i = pDataSizes->begin(); i != pDataSizes->end(); ++i )
    {
        SIZE_T dataSize = *i;

        SYMCRYPT_ASSERT( n < MAX_SIZES );

        if ( dataSize == PERF_DATASIZE_SAME_AS_KEYSIZE)
        {
            dataSize = keySize;
            x[n] = 0;           // Set this to 0 so later it will know there is only one datasize
            sumXi += 0;
        }
        else
        {
            x[n] = dataSize;
            sumXi += dataSize;
        }

        y[n] = measurePerfOneSize( keySize, dataSize, keyFn, prepFn, dataFn, cleanFn, FALSE );

        CHECK5( !isnan(y[n]), "NaN result from measurePerfOneSize: n = %d, x[n] = %d, y[n] = %f", n, x[n], y[n] );
        ++n;
    }

    SYMCRYPT_ASSERT( n > 0 );

    if( n > 1 )
    {
        double avX = (double) sumXi / n;

        //
        // Compute the average of the y values accurately.
        // Inaccuracies in this lead to numerical instabilities that are quite visible
        // in cases where the algorithm time does not depend on x.
        //
        double avY = correctAverage( 0.0, y, n );
        //print( "avY1 = %f\n", avY );
        avY = correctAverage( avY, y, n );
        //print( "avY2 = %f\n", avY );
        avY = correctAverage( avY, y, n );
        //print( "avY3 = %f\n", avY );

        double sumDxDy = 0.0;
        double sumDx2 = 0.0;
        for( SIZE_T i=0; i<n; i++ )
        {
            sumDxDy += (x[i] - avX) * (y[i] - avY );
            sumDx2 += (x[i] - avX) * (x[i] - avX );
        }


        //
        // We fit a line to the data points using Linear Regression
        //

        // iprint( "%f %f %f %f\n", avX, avY, sumDxDy, sumDx2 );

        perByte = sumDxDy / sumDx2;
        fixed = avY - perByte * avX;

        if( fixed < 0 )
        {
            // Our estimated fixed cost per request is < 0, which is nonsensical and due to measurement errors.
            // This makes reporting ugly, especially with graphs.
            // As we know that the fixed cost must be >=0, we set it to 0 and re-optimize the perByte cost.
            // Our line becomes: Y = c*X for a per-byte cost c.

            // Minimise_c Sum_i (Yi - c*Xi)^2
            // Minimise_c Sum_i (Yi^2 - 2*c*Xi*Yi + c^2*Xi^2)
            // Minimise_c (Sum_i Xi^2)*c^2 - 2*(Sum_i Xi*Yi)*c + (Sum_i Yi^2)
            // differentiate w.r.t. c
            //  2*(Sum_i Xi^2)*c - 2*(Sum_i Xi*Yi) = 0
            // and thus c = (Sum_i Xi*Yi) / (Sum_i Xi^2)

            ULONGLONG sumXiXi = 0;      // Our Xi < 2^24 or so, so a 64-bit accumulator is enough
            double sumXiYi = 0.0;
            for( SIZE_T i=0; i<n; i++ )
            {
                sumXiXi += (ULONGLONG) x[i] * x[i];
                sumXiYi += (double) x[i] * y[i];
            }
            fixed = 0;
            perByte = sumXiYi / sumXiXi;
        }

        // Note: We should consider switching to the Theil�Sen estimator because it is much less sensitive to outliers

    } else
    {
        // Only one data size. If datasize == 0, we have just a fixed overhead, otherwise we have only a perByte cost
        if( x[0] == 0 )
        {
            perByte = 0;
            fixed = y[0];
        } else {
            perByte = y[0]/x[0];
            fixed = 0;
        }
    }

    CHECK( !isnan(perByte), "NaN result for perByte" );
    CHECK( !isnan(fixed), "NaN result for fixed" );

    double lineDeviation[ MAX_SIZES ];
    for( SIZE_T i=0; i< n; i++ )
    {
        lineDeviation[i] = abs( y[i] - (fixed + perByte * x[i] ) );
    }
    qsort( lineDeviation, n, sizeof( lineDeviation[0] ), &compareDouble );
    double deviation90Percentile = lineDeviation[ (n * 9) / 10 ];

    pRes->cFixed = fixed;
    pRes->cPerByte = perByte;
    pRes->cRange = deviation90Percentile;
}