dn-m / performancetesting

Structures for testing performance characteristics of data structures and algorithms

dn-m

Application targets for the dn-m project.

performancetesting's Issues

Refine PerformanceTestCase API

[Minor] Change inverseFunction to inverse

Following some changes we made in other places, would it be reasonable to change:

enum Complexity {
    ...
    case customComplexity(inverseFunction: (Double) -> Double)
}

to:

enum Complexity {
    ...
    case custom(inverse: (Double) -> Double)
}

In both cases (customComplexity and inverseFunction), the second word functions to expose the type (in some sense) of the value (Complexity and Function, respectively). This type is exposed inherently by the type system.

[Tests] add tests to cover all complexity classes

These cases haven't yet been touched:

• square root
• quadratic
• cubic
• exponential
• custom

Add method for testing complexity functions of multiple parameters

e.g., gift wrapping algorithm is O(nh).

reading:
http://www.ahinson.com/algorithms_general/Sections/InterpolationRegression/RegressionPlanar.pdf

other possible avenues for exploration:

• generate an a*b matrix and either
  • transform the data and perform a + b linear regressions (criss-cross)
  • transform the data, find mean and variance across one dimension, assert variance, assert result of linear regression in other dimension

Conditionally import Glibc instead of assuming Darwin

There are several points where Darwin is imported.

-Sources/PerformanceTesting/DataSet.swift
-Sources/PerformanceTesting/Complexity.swift
-Sources/PerformanceTesting/Scale.swift

In order to serve Linux, conditionally import Glibc.

Move mapDataForLinearFit from Complexity to Benchmark

Currently, mapDataForLinearFit(_:) is on Complexity. I may be wrong, but it seems like it is more in the domain of the Benchmark than Complexity.

Instead, what if we move it to Benchmark:

extension Benchmark {
    func mappedForLinearFit(complexity: Complexity) -> Benchmark
}

Audit assertPerformanceComplexity API

First, I think we should keep the linear case under the same roof as all of the others, so that assertConstantTimePerformance is not a different public function.

Instead, for now, we should do a case let .constant = complexity { assertConstantTimePerformance(...) }

With that said, I think we could clarify the path of types.

Perhaps we could rename this to:

func assert(_ benchmark: Benchmark, isIn complexity: Complexity, minimumCorrelation: Double = 0.9)

Consider injecting Logging level into assertPerformance

Instead of using global state, we could have the user inject Logging (currently, Configuration), providing a reasonable default (which I would propose to be .none).

Naming of timeClosure and benchmarkClosure

Both time and benchmark can be nouns / verbs, which can be a bit confusing.

Currently, they are being used as verbs, though they are functions with return values. Perhaps we can orient the names around the type of the return value, instead of what it takes to create that value.

[Tests] Add Array PerformanceTestCase tests

Consider adding convenience methods for constructing standard structures

Currently, we have things like makeArray(size:), makeDictionary(size:), makeSet(size:) nested within our tests here.

Let's move these to PerformanceTestCase?

[Minor] Move sum / average to own file, use in LinearRegression

The extension properties sum and average over Array<Double> currently at the end of PerformanceTestCase.swift could help streamline some of the code in LinearRegression.swift.

Let's move those out into their own file and use 'em?

[Tests] Add Dictionary PerformanceTestCase tests

Flesh out Benchmark

Currently, Benchmark is just a typealias for [(Double,Double)].

I think it could be nice to package up all of the information the performance benchmark of a single operation. The API could fall out like this:

struct Trial {
    let size: Int
    let time: Double /* Seconds */
}

struct Benchmark {
    let trials: [Trial]
    let targetComplexity: Complexity
}

Consider making Scale an enum which produces test points

Right now, there is a slight dissonance to me regarding what a Scale is, and what testPoints are. They seem to be at two different levels of abstraction, seen from the viewpoint of the function call.

What if we implemented Scale as such:

enum Scale {
    case tiny
    case small
    case medium
    case large
}

extension Scale {
    var testPoints: [Double] {
        switch self {
            case tiny:
                exponentialSeries(size: 10, from: 5, to: 100)
             ...
        }
    }
}

Consider making PerformanceTestCase instance methods free functions (remove `PerformanceTestCase`)

It seems that the instance methods on PerformanceTestCase (benchmark, assertPerformance, etc.) don't have any dependencies on the PerformanceTestCase class.

I'm not sure this will work, but it could be worthwhile to move these methods out into free functions, calling XCTAssert (which is...a macro?).

The function calls would look identical at the call site, without requiring users to subclass PerformanceTestCase. I forgot I had to subclass PerformanceTestCase myself.

[Tests] Add Set PerformanceTestCase tests

Do we need the testPoint (Double) in Run / Operation closure?

It is used just a few times in SetTests, where it looks like it may be replaced with some other logic.

In trying to get rid of it, though, Swift gives me a very curious error at the location within the test:

Cannot use mutating member on immutable value: 'array' is a 'let' constant

This error or only seems to occur if the type is (inout Structure), but not (inout Structure, Double).