MicroBench

Duga

00:02

RELOAD!

[retailcoder/Rubberduck] 1 opened issue.

[rolfl/MicroBench] 9 commits.

[skiwi2/TCGHand] 3 commits.

[Unihedro/JavaBot] 1 opened issue. 1 issue comment.

[Vogel612/JavaBot] 2 commits.

Simon André Forsberg

@Duga We won!

Simon André Forsberg

00:22

A thought by the way...

Perhaps a MathModel should have some isValid predicate?

For example, O(n) is not 'valid' if the coefficient has a Math.abs(value) < 0.0001

that could be a way to filter out the low parameter values

I think that for all O(1) cases, it will give a better fit on O(n) and O(n^2), but with very very low values for some of the parameters

rolfl

Only the first coefficient is significant.

If the others are 0, that's OK

Simon André Forsberg

yes, that's true.

if there are more than one parameter and the first one is around 0, then it's invalid.

that should filter some of them away.

TTGTB

rolfl

yeah, also, it makes no sense to have a -ve last coefficient

Simon André Forsberg

night

rolfl

-0.000000*n^2 + 0.064743*n + -133.483378

^^^^ -133.483378 is unreasonable

Duga

04:37

[rolfl/MicroBench] rolfl pushed commit 1d1058d1 to newton

> Make scales adjust as plots are added/removed

rolfl

^^^ Not pretty code, but the effects are super cool.

git.tuis.net/ubench/Linear.html

Simon André Forsberg

10:39

@rolfl -0.000000*n^2 is unreasonable.

what was the r-squared for it? Was that one considered the best?

@rolfl nice!

rolfl

I am in the middle of hacking it ....

you got it at a working moment.

I want the count axis to disappear when count disappears.

OK, working now.

Duga

[rolfl/MicroBench] rolfl pushed commit e731622b to newton

> Use class instead of ID to set display style, toggle count axis too.

Simon André Forsberg

11:09

@rolfl speaking of negative "unreasonable" things, here's the UScale best fit equation for Bubble Sort:

2.504717*n^2 + 528.930966*n + -187276.574540 with precision 0.9999168848777207

-187276 looks unreasonable at first sight, but for some strange reason it isn't unreasonable, actually.

Bubble Sort is clearly O(n^2) and this is the best polynomial of grade two that was applicable.

but this was interesting

by removing the linear-coefficient there, it became:
2.539981*n^2 + 334358.541916 with precision 0.9999018674621459

slightly less precise, but 'looks' more reasonable.

rolfl

@Simon, my argument against the Y-offset is because in theory it is impossible for it to be anything other than 0

Other than for O(1), which is not reasonable to have a value for scale==0 anyway

all other functions I can think of should all intersect at the origin.

Simon André Forsberg

@rolfl I understand your argument there, but I only partially agree with it. Adding that negative y-offset makes the curve fit better for the high x,y values.

A mathematical regressed model is not reality.

rolfl

I can accept that too .... but, I think of the Y-offset as being the O(1) component (the overhead) of the function.

so, I can accept a positive overhead, but not a negative one.

Simon André Forsberg

You could add a data point for zero runs (will probably have an actual y-value of slightly > 0 though), but I am not certain that it will change anything when it comes to the result of the Newton-Gauss algorithm.

rolfl

Maybe that's the way to express my thoughts, that each function is a collection of components, each component has a complexity. There is an O(1) component in there that can only be a positive value.

Regardless, I am only just more than half-convinced... and I think you're right that the general best fit is better, even with a negative offset.

One other thing to consider, is using the fastest instead of average time.

Simon André Forsberg

11:25

I think being able to see 'the big picture' (the big-O complexity) is a far more bigger advantage than determining the overhead of the function. Apparently, the value that is found here is not the overhead, as it can be negative. So your interpretation of that value is wrong.

@rolfl should be easy to accomplish

rolfl

I also have to remind myself that the values are small.... even when they look big.

Simon André Forsberg

Yes. Nanoseconds.

17 mins ago, by Simon André Forsberg

2.504717*n^2 + 528.930966*n + -187276.574540 with precision 0.9999168848777207

approximately -0.187 ms

rolfl

Oh, you said that already

What do you think of the 'smoothed' graphs?

Simon André Forsberg

And as I also said, this one was quite interesting:

14 mins ago, by Simon André Forsberg

by removing the linear-coefficient there, it became:
2.539981*n^2 + 334358.541916 with precision 0.9999018674621459

suddenly a positive overhead.

@rolfl do you mean the animation that is applied when the auto-scaling of y axis occurs? Love it. If you don't mean that, what do you mean?

rolfl

Have a look at what you have on the screen, then reload.

Compare this:

git.tuis.net/ubench/Linear.smooth.html

with this:

git.tuis.net/ubench/Linear.html

Simon André Forsberg

11:31

oh, that's interesting

looks much more like a real mathematical curve now

I think I like it

rolfl

I know I like it from a visual perspective, but, technically, it's not accurate ;-)

then again, it was not really accurate before.

Oh, I was supposed to add points to the chart to mark data locations.

// TODO: Add points to chart.

Simon André Forsberg

would be nice, yes

// TODO: https://github.com/rolfl/MicroBench/issues/new

Duga

[rolfl/MicroBench] rolfl opened issue #13: Add marks to charts for UScale HTML report to indicate actual data points

> Graphs are just path elements now. They need data points too.

rolfl

That HTML page is a future CR question......

Simon André Forsberg

I think my ScaleDetect class, together with the MathModel and MathEquation is one too..

rolfl

11:43

So, there's 1 item 'to do'... what's needed before we can merge it back in and release UBench 0.2 ?

Simon André Forsberg

I think we should take a look at the reporting mechanism. Exactly what data should be printed to System.out? I feel that at the moment I'm printing a bit too much.

rolfl

I have the javadoc and all other eclipse warnings set to be very "strict", so there are a bunch of missing tags and stuff to resolve before the code is merged back

We could use proper logging (the Java built in version).

There's still the issue of passing in the title at the report, rather than the 'consumer' or 'function' level.

Simon André Forsberg

I guess we could, yes. Then we need to go over and determine at what level to log what.

rolfl

By default, log nothing.

Simon André Forsberg

Not even the actual result when calling the report() method?

    public void report() {
        stats.stream()
                .sorted(Comparator.comparingInt(UStats::getIndex))
                .map(sr -> String.format(
                        "Scale %4d -> %8d (count %d, threshold %d)",
                        sr.getIndex(), sr.getAverageRawNanos(), sr.getCount(), NANO_TICK))
                .forEach(System.out::println);
        MathEquation bestFit = ScaleDetect.detect(this);
        System.out.println("Best fit is: " + bestFit);
    }

rolfl

11:47

report() is expected to log, but the internal messages should be silent

Simon André Forsberg

okay

rolfl

I would like to make the UScale report and the UReport report systems be "similar".

So, I should probably add an HTML reprot to the UReport.

Simon André Forsberg

makes sense

rolfl

SImilarly, the report() on UScale should have an option to report to file, rather than STDOUT as well

Simon André Forsberg

yeah

rolfl

11:49

Also, that report() implementation is a hack that I put together as a first run.... there's nothing in there that was intended to be formatted nicely.

The HTML report I have is also not well laid out

Simon André Forsberg

This was interesting.... added a exponential mathematical model, for the O(2^n) case. For bubble-sort, it returns:

[1.0, 2.0, 4.0, 8.0, 16.0, 32.0, 64.0, 128.0, 256.0, 512.0, 1024.0, 2048.0, 4096.0, 8192.0, 16384.0, 14336.0, 12288.0, 10240.0, 6144.0]
[488.0, 488.0, 488.0, 488.0, 977.0, 3422.0, 11733.0, 44000.0, 170134.0, 672711.0, 2614089.0, 1.0346356E7, 4.1465605E7, 1.68587977E8, 6.8453302E8, 5.13354909E8, 3.99514184E8, 2.639047E8, 9.4308146E7]
750506311888845820.000000 variance, NaN residual sum, 114712311.315789 avg, NaN rsquared, NaN explained sum of squares
[NaN]
NaN ^ n with precision NaN

rolfl

division by zero?

Simon André Forsberg

that could be it. I will debug.

rolfl

we should probably do a code review on each other's code ;-)

I know the JS/CSS/HTML of mine is ugly

Would require a minimal understanding of D3 to review it though

Simon André Forsberg

I know the variable names in my newtonSolve method are horrible

rolfl

11:52

By the way, that 'transition/animation' effect... that's the difference between flot and D3

Simon André Forsberg

I have a minimal understanding of D3: I know it is a graph library for JavaScript.

rolfl

You're wrong ;-)

Data Driven Documents

DDD

D3

It is about the whole document, not just the graphs

Simon André Forsberg

Okay then, I know it is a JavaScript library for producing dynamic, interactive data visualizations in web browsers.

^^ that's what Wikipedia says

rolfl

Well, there is 1 chart, and 2 tables in that report, and the tables are D3 too

Simon André Forsberg

oh

rolfl

12:00

    // map the values in to the table
    var tbody = table.append("tbody")
        .selectAll("tr")
        .data(raw)
        .enter().append("tr")

        .selectAll("td")
        .data(function(d){return d;})
        .enter().append("td")
        .on("mouseover", function(){d3.select(this).style("background-color", "lightcyan")})
        .on("mouseout", function(){d3.select(this).style("background-color", "white")})
        .text(function(d){return d;});
}

I created a 2D raw version of the table, and, essentially, the code above maps each row/field to a tr/td element

Simon André Forsberg

cool

rolfl

including the color change as you move your mose from cell to cell

I could have made the .text(...) function do the mapping for me instead of pre-mapping it... but... I am not there yet

    // translate the data values in to raw arrays of numbers,
    // in same order as columns
    var raw = [];
    data.data.forEach(function(stat) {
        var row = [data.fields.length];
        for (var i = 0; i < data.fields.length; i++) {
            row[i] = stat[data.fields[i]];
        }
        raw.push(row);
    });

Simon André Forsberg

This is what is causing the NaN:

dx = new QRDecomposition(df).getSolver().solve(fxVector.mapMultiply(-1));

dx becomes a 1x1 matrix of NaN there.

I think I need to test this with some actual exponential data

rolfl

I will pretend I understand, and will nod my head condescendingly

Simon André Forsberg

bubble sort is clearly not exponential

rolfl

12:09

A wise man once said:

36 mins ago, by Simon André Forsberg

// TODO: https://github.com/rolfl/MicroBench/issues/new

Simon André Forsberg

@rolfl I don't understand much about that QRDecomposition thing either. I just know that that is how it should be done. How QRDecomposition actually works? Forgot that long ago.

haha

skiwi

So this is why @SimonAndréForsberg is so silent in our TCG room ^^

rolfl

It was his idea

promise

But, it is really cool

skiwi

It looks interesting

rolfl

42 mins ago, by rolfl

http://git.tuis.net/ubench/Linear.smooth.html

Play with that ^^^

enable/disable things

skiwi

12:14

Anbinations, nice )

rolfl

The deep thinking is in creating the right coefficients for the complexity-matching functions

Duga

12:28

[rolfl/MicroBench] Zomis pushed commit 36a98fbf to newton

> added isValid check on MathEquation, to ignore equations with a very low params[0] value, such as 0.00000x^2

[rolfl/MicroBench] Zomis pushed commit ba141642 to newton

> added output of the best fit in UScale.report

[rolfl/MicroBench] Zomis pushed commit 93369682 to newton

> added createPolynom method to create polynomial MathModels of arbitrary size, using polynomials up to grade 4 in rank method

[rolfl/MicroBench] Zomis pushed commit 3cfe06b6 to newton

> added bubble-sort example to ExampleScales

[rolfl/MicroBench] Zomis pushed commit a602f505 to newton

> improved String format for created polynomials

rolfl

  nano_tick: 394,
  models: [
    {name: "%f*n^4 + %f*n^3 + %f*n^2 + %f*n + %f", description: "-0.000000*n^4 + 0.000000*n^3 + 0.000000*n^2 + 0.058891*n + 211.040939", parameters: [-0.000000, 0.000000, 0.000000, 0.058891, 211.040939], rsquare: 0.993767},
    {name: "%f*n^3 + %f*n^2 + %f*n + %f", description: "-0.000000*n^3 + 0.000000*n^2 + 0.044280*n + 901.799191", parameters: [-0.000000, 0.000000, 0.044280, 901.799191], rsquare: 0.993546},
    {name: "%f*n^2 + %f*n + %f", description: "-0.000000*n^2 + 0.084633*n + -2528.573885", parameters: [-0.000000, 0.084633, -2528.573885], rsquare: 0.98…

"%fn^2 + %fn + %f" <-- reported twice @Simon

Simon André Forsberg

@rolfl I think I have fixed that locally. I also discovered that.

Duga

12:44

[rolfl/MicroBench] Zomis pushed commit 25842732 to newton

> set some MathModels to their polynomial. Added exponential model.

Simon André Forsberg

there you go @rolfl

beware of the exponential one though. It will probably return NaN a bit...

rolfl

ta ... I really have to go to work ;-)

it is looking so good though... the isValid flag probably needs to make it in to the JSON

It would also be nice to rank the graphs by isValid first

these are things I can do later though

Simon André Forsberg

tried to detect the scale of your N-Queens solver:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

rolfl

13:28

That's what -Xmx is for ;)

Duga

13:53

[rolfl/MicroBench] Zomis opened issue #14: Some methods might have a limit on the scale

> Some functions, for example [a specific N-queens solver](http://codereview.stackexchange.com/questions/75517/n-queens-brute-force-bit-by-bit) has a restriction on the acceptable `scale` values. In this case, the N-queens solver does not support values bigger than 32.

Other methods might throw a `StackOverflowError` for too large values of `scale`.

Can this be handled somehow? For example, by only using scale values of 1 - upperLimit for these methods?

Simon André Forsberg

22:46

@rolfl Slight issue here, when I changed the times used for the formula calculation from average to fastest, the times for i -> i / 3 function became:

[488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0, 488.0]

Which causes the following formulas:

[93.723663 * log n with precision -Infinity, 0.000012 * n log n with precision -Infinity, 488.000000 with precision NaN, 0.000000*n + 488.000000 with precision NaN, -0.000000*n^2 + 0.000000*n + 488.000000 with precision NaN, 0.000000*n^3 + -0.000000*n^2 + 0.000000*n + 488.000000 with precision NaN, 0.000000*n^4 + -0.000000*n^3 + 0.000000*n^2 + -0.000000*n + 488.000000 with precision NaN, NaN ^ n with precision NaN]

all formulas have either precision -Invinity or NaN.

because the times are identical, for all scales

> Neither formula is defined for the case where y_1 = \ldots = y_n = \bar{y}.

This kind of regression simply doesn't work for constant data like this...

rolfl

23:26

Back @Simon. I follow the logic, but not sure where you want to go with this

I would expect the system should be able to deal with "perfect" data... whether O(1) or other.

Whether the solution is to identify and avoid it first, that would be fine.

Transcript for