MicroBench

Duga

04:25

[rolfl/MicroBench] rolfl pushed commit 7e10e7e8 to newton

> Export all math models to the report, and plot them.
plots are now toggleable.

rolfl

@Simon - git.tuis.net/ubench/Linear.html Good morning ;-)

I think I have my plot wrong from O(log n)....

your code indicates that is the best fit, but my visualization sucks.....

Simon André Forsberg

11:03

@rolfl What was the code that was analyzed?

Morning to you too :)

rolfl

I ran the ExampleScales, and the result is the output/Linear.html

@Simon - before you look too hard, have a look at the html source code, I dump the parameters and function in there.

my re-constitution of the curve may be the problem.

I also changed two things in your code.

1. I split the rank method out....

2. the other method just takes the best ranked.

I wonder if I got that logic the wrong way around....?

for the report I wanted all the curves, not just the best.

but, sorted in best-first order.

Oh, I also added a toJSONString() method somewhere.

Simon André Forsberg

"somewhere"... :)

rolfl

Having a 'name' for the models/functions would be nice, by the way ;-)

Simon André Forsberg

yup. good point.

rolfl

github.com/rolfl/MicroBench/commit/…

Added there ^^^

@Simon, I'll be somewhat busy today, won't probably touch things until this evening - my time.

Simon André Forsberg

11:15

@rolfl I also won't have much time to touch things today.

rolfl

No problem.

rolfl

11:31

@Simon - one thing I was thinking is that your 'best fit' algorithm should exclude functions that have a close-to-zero primary coefficient.

  models: [
    {name: "%f * log n", description: "23615.402226 * log n", parameters: [23615.402226], rsquare: 0.375837},
    {name: "%f * n log n", description: "0.007643 * n log n", parameters: [0.007643], rsquare: 0.999136},
    {name: "%f * n + %f", description: "0.052016 * n + 6.636602", parameters: [0.052016, 6.636602], rsquare: 0.999787},
    {name: "%f*n^2 + %f*n + %f", description: "-0.000000*n^2 + 0.052044*n + 0.460761", parameters: [-0.000000, 0.052044, 0.460761], rsquare: 0.999787}
  ],

Simon André Forsberg

@rolfl yeah, I've also thought about that. In those cases I think it should simply remove that coefficient entirely, which will simplify the equation and reduce the complexity.

rolfl

Did I just sort them wrong?

Simon André Forsberg

no, the sorting looks correct. rsquare is the one to sort by.

rolfl

discounting the last one because it has a 0 coefficient, that leaves the linear one which is the right one, with the almost-1 rsquare.

Simon André Forsberg

yup

rolfl

11:35

I assume the first is best, but, the last is best.

Simon André Forsberg

oh, then you order them wrong :)

order them descending if you want that.

rolfl

Look at the change I made to your code.... getting reference.....

Simon André Forsberg

0.375837 is definitely not a good fit.

Okay, I will take a look

rolfl

Ahh.... github.com/rolfl/MicroBench/commit/…

it was my fault.

you took max, not first.

I take first.... my fault.

I broke it.

Simon André Forsberg

yes you did :)

rolfl

11:40

Oh, out of interest, it occasionally hangs for me ;-)

(see, it's not just me who breaks things)... ;_)

Simon André Forsberg

@rolfl what hangs? what part of the code?

rolfl

the matching process.

it prints the first model results, never prints the rest.

Simon André Forsberg

ah, was afraid of that.

converging is not guaranteed.

Next time that happens, please provide the x/y data that the matching process uses

Duga

[rolfl/MicroBench] rolfl pushed commit ff8948b1 to newton

> Repair bfart about order of rsquared matching.

Simon André Forsberg

btw, why do you in JS do this? JS has one log method that uses log with base e and one that uses log with base 10. (my Java mathematical models so far uses log10 if you haven't changed it)

why is there a trailing / on this line ?

rolfl

11:44

Because, I swear, it was not working, I thought it was an ECMA5 thing compatibility...

now I have tried it, and it works.... :(

54 secs ago, by Simon André Forsberg

why is there a trailing / on this line ?

Typo?

It was late... ;-)

but, no error, how did you find that? Visually?

Simon André Forsberg

I just read through the commit diff

rolfl

Hanging again....

happens for me about half the time.

Currently my screen shows:

Preparing HTML Report output/Linear.html
solved in 3 iterations
[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, 32768.0, 65536.0, 131072.0, 262144.0, 524288.0, 1048576.0, 2097152.0, 4194304.0, 8388608.0, 7340032.0, 6291456.0, 5242880.0, 3145728.0]
[21.0, 20.0, 20.0, 20.0, 21.0, 21.0, 25.0, 30.0, 42.0, 60.0, 81.0, 137.0, 244.0, 461.0, 876.0, 1732.0, 3461.0, 6800.0, 13564.0, 27093.0, 54385.0, 108691.0, 216787.0, 436405.0, 387312.0, 327683.0, 272795.0, 166236.0]

I can't get the raw data when it is in this state.

Simon André Forsberg

okay, so it is a converging issue

> [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, 32768.0, 65536.0, 131072.0, 262144.0, 524288.0, 1048576.0, 2097152.0, 4194304.0, 8388608.0, 7340032.0, 6291456.0, 5242880.0, 3145728.0]
[21.0, 20.0, 20.0, 20.0, 21.0, 21.0, 25.0, 30.0, 42.0, 60.0, 81.0, 137.0, 244.0, 461.0, 876.0, 1732.0, 3461.0, 6800.0, 13564.0, 27093.0, 54385.0, 108691.0, 216787.0, 436405.0, 387312.0, 327683.0, 272795.0, 166236.0]

^^ that is the data

rolfl

Well, yeah, but... nevermind

OK, the log10 is working fine now. Pushing another commit.... then, I am off to work.

Duga

[rolfl/MicroBench] rolfl pushed commit 550461dc to newton

> Use direct log10(x) instead of loge(x)/loge(10), correct typo

Simon André Forsberg

20:06

@rolfl I just ran through the problematic data and re-produced the problem. I see two possible solutions.

rolfl

throw it all away, and .... ?

Sorry, cynical mood today ;)

Simon André Forsberg

That's not one of them ^^

Actually, three possible solutions.

1. increase the h variable in the newtonGauss method. This is being used to calculate the derivatives. Increasing this value solves the problem for this data at least. (Although this is not a solution I prefer)

2. increase the tolerance, to make it stop more easily. The problem was that it in this case got stuck in an infinite loop of values that didn't provide good enough tolerance.

3. Break after 1 million or so iterations. Most often a good solution is found after 3 or less iterations, so this shouldn't happen very often.

rolfl

OK.

The break after say, 100 iterations seems like a good failsafe.

the h variable seems to be what your instinct says is better than the tolerance change... changing the tolerance will decrease the accuracy of good matches, right?

you want to keep the good matches good, and allow the bad ones to exit.

Simon André Forsberg

Yes. But increasing H variable will decrease accuracy as well, I believe.

rolfl

OK, how about a cascading system.....

let it run for 100 loops, then inrease the tolerance?

(or the H).

Simon André Forsberg

20:15

that's a good solution.

I think a mix of them might be the best

and actually, I think I've been too generous with H and tolerance already.

rolfl

You know the math, but that's a system I have seen used before

you could tune the system to have a number of stages of acceptable with a final bail-out if no acceptable solution is found.

Simon André Forsberg

The issue might have been that H was bigger than the tolerance... so it was impossible to get close enough.

I will decrease H and tolerance, making it get slightly better results, and use the cascading approach you suggested.

rolfl

Sounds like something which should be a validated input?

Simon André Forsberg

the H wasn't input though, it was hard-coded in the method.

both H and TOLERANCE has now been extracted to static constants

rolfl

Ahh. Ok... time to parameterize them

Happy to be your duck

Simon André Forsberg

20:21

Quack.

2

No, wait. That's your line.

if (iterations % 100 == 0) {
    tolerance *= 10;
}

Simon André Forsberg

22:04

Hello, @Iplodman

rolfl

Boo

@Simon - I would like to find a way to report O(1) performance somehow. I know this is really f(n) = an + b where a is small, but.....

Simon André Forsberg

@rolfl I tried to have a O(1) MathModel as well, but it the R-squared was always 0 for that.

rolfl

I think the solution is to just propose an always-there "model" where the offset is the same as whatever was calculated for the O(n) version, but presented for the O(1), and then have the R-squared as whatever gets calculated for the 0 coefficient

Simon André Forsberg

on the other hand, some of the other math models returned negative r-squared for constant-time data...

rolfl

In other words, don't try to guess the O(1), just use the O(n) model with a 0 coefficient, and calculate the r-square for that

Simon André Forsberg

22:12

re-calc the r-square for that? then the r-squared will be 0.

Coefficient of determination

In statistics, the coefficient of determination, denoted R2 or r2 and pronounced R squared, is a number that indicates how well data fit a statistical model – sometimes simply a line or curve. It is a statistic used in the context of statistical models whose main purpose is either the prediction of future outcomes or the testing of hypotheses, on the basis of other related information. It provides a measure of how well observed outcomes are replicated by the model, as the proportion of total variation of outcomes explained by the model (pp. 187, 287). There are several definitions of R2 that are...

rolfl

Isn't the r-squared a measure of how closely the curve fits thereality?

Simon André Forsberg

yes. and how it is calculated is shown in the wikipedia article

rolfl

that ^^^

Yes, let me explain my reasoning, backwards.

what I want is on the HTML to have a O(1) 'line', but I need the y-offset.

the Y-offset is really the second parameter for the O(an + b) function

Simon André Forsberg

yes

rolfl

In a case where the actual data gives O(1) performance, the a will be close to 0.

Simon André Forsberg

22:15

yes

when SSres equals SStot, the r-squared becomes zero.

rolfl

but, even if it is not an actual O(1) dataset, I want an O(1) line, at the same Y-offset as the data, and with an r-squared calculated back to the data, i.e. a "bad" fit.

Simon André Forsberg

I think the r-squared will be a bit misleading in those cases.

rolfl

In the current setup, I get:

  models: [
    {name: "%f * log n", description: "23615.402226 * log n", parameters: [23615.402226], rsquare: 0.375837},
    {name: "%f * n log n", description: "0.007643 * n log n", parameters: [0.007643], rsquare: 0.999136},
    {name: "%f * n + %f", description: "0.052016 * n + 6.636602", parameters: [0.052016, 6.636602], rsquare: 0.999787},
    {name: "%f*n^2 + %f*n + %f", description: "-0.000000*n^2 + 0.052044*n + 0.460761", parameters: [-0.000000, 0.052044, 0.460761], rsquare: 0.999787}
  ],

Simon André Forsberg

it's impossible to create a "good fit" line with a 0 coefficient.

rolfl

I also want:

   {name: "%f", description: "6.636602", parameters: [6.636602], rsquare: ???????????},

which is a hacked version of:

   {name: "%f * n + %f", description: "0.052016 * n + 6.636602", parameters: [0.052016, 6.636602], rsquare: 0.999787},

but, you know how to calculate the r-squared for that line....

Simon André Forsberg

22:17

you don't need to create a hacked version of it

the Gauss-Newton solver can create a non-hacked version of it, which I used to do before

Although I did add a comment in my code:

    // CONSTANT will not produce a reasonable rSquared value. Use LINEAR instead and check coefficient.
//    public static final MathModel CONSTANT = new MathModel("%f", params -> x -> params[0], new double[]{ 1 });

rolfl

but the r-square is a value calculated to measure how closely it fits... it is "Post calculated" after you guess the coeffficients.

Simon André Forsberg

yes, it is.

rolfl

I am not suggesting that you guess the O(1) case... just calculate the r-squared from the constant valur of the an+b guess

Simon André Forsberg

with a=0, right?

rolfl

yes.

and output that as an 'equation' in your results (sorted wherever it belongs).

(based ont he r-square).

And dinner for me.....

I can draw the line easily in the HTML, but I can't calculate the r-square.

Simon André Forsberg

22:23

@rolfl technically, you can, but you don't know how :)

I will solve it Java-wise though

Duga

[rolfl/MicroBench] Zomis pushed commit 6da5ad40 to newton

> using "Simon Forsberg" for attribution

[rolfl/MicroBench] Zomis pushed commit 5d9c4797 to newton

> extracted constants and added fail-safe for when Gauss-Newton solver requires a lot of iterations

Simon André Forsberg

22:38

@rolfl I don't think you want this r-squared value. It looks worse than it is.

[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, 32768.0, 65536.0, 131072.0, 262144.0, 524288.0]
[905.0, 901.0, 939.0, 927.0, 920.0, 898.0, 884.0, 861.0, 852.0, 864.0, 869.0, 867.0, 866.0, 867.0, 857.0, 857.0, 854.0, 855.0, 872.0, 865.0]

that is the data

R-squared, when setting the coefficient for the line to 0, becomes -0.009834967033341302

> Values of R2 outside the range 0 to 1 can occur where it is used to measure the agreement between observed and modeled values and where the "modeled" values are not obtained by linear regression and depending on which formulation of R2 is used. If the first formula above is used, values can be less than zero. If the second expression is used, values can be greater than one.

It also says that "Neither formula is defined for the case where y_1 = ... = y_n = avg(y).", but I don't think that applies here. f_1 = ... = f_n = avg(y), however, would apply.

the y input data is not all the same, but the function is the same.

rolfl

trying to follow (dinner done).

Simon André Forsberg

I can't entirely explain what happens in the statistical calculations here. but the R-squared value did not improve with your approach.

rolfl

I'm not trying to improve the r^2

I just want something that looks representative of O(1) performance systems.... so that you can visually compare the actual data with the comparative O(1)

I was planning on adding the function description and r^2 values to the 'legend'.

and want an O(1) entry there....

Duga

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

> re-enabled O(1) matching, added more helper-methods in ScaleDetect

Simon André Forsberg

@rolfl that ^^ should give you that

rolfl

22:48

Ahh, looking at it.

Functional extraction....nice.

Whoa, that slowest chart is a problem.... git.tuis.net/ubench/Linear.html

Simon André Forsberg

I'm glad I'm not trying to find a mathematical formula for that!

y-axis doesn't rescale when unchecking some checkboxes disappointed ;)

Duga

[rolfl/MicroBench] rolfl pushed commit dc224f01 to newton

> Support f% O(1) curve

rolfl

OK, heh, 1-liner change to add a curve.

Now, hopefully updating the legend will be easy too. Have you run the HTML report for yourself yet?

I think I will exclude the slowest chart from the 'find the domain of the Y-axis' calculation.

Simon André Forsberg

@rolfl yes, I have. Seems to work well!

Duga

23:04

[rolfl/MicroBench] Zomis pushed commit 6fb2436d to newton

> refactored MathModel.getFunction usage to MathModel.createFunction

[rolfl/MicroBench] Zomis pushed commit cccc0953 to newton

> cleaned up some one-liner methods and added JavaDoc to newtonMethod, also made it private

Simon André Forsberg

Oh, cccc0953

rolfl

git.tuis.net/ubench/Linear.html

@Simon - slowest capped, legend with details... thoughts? (a bit messy.... layout sucks).

Simon André Forsberg

> (a bit messy.... layout sucks).

^^ that's my thoughts

~~is it possible to~~ can you make the Y-axis auto-scale somehow, whenever a checkbox is toggled?

rolfl

OK, my graphic design skills are deficient.

@SimonAndréForsberg Yes.... will require transitions.

they are cool... but.... require learning.

Simon André Forsberg

23:20

So far, I think Flot seem to create a 'nicer' graphical UI than what D3 does, from what I have seen. It seems to be easier to make it look better in Flot (not suggesting that you should change)

rolfl

I think you may be right, but I don't want you basing your perception on my implementation.

I get the impression that, for line graphs, and other 'simple' visualizations, that D3 is overkill....

but, for more complex things, D3 is the best....

Simon André Forsberg

^^ that might be true

from what I saw from the D3 examples, D3 does seem to be a lot more powerful than flot

Flot seems to use <canvas> while D3 uses <svg>

Transcript for