MicroBench

Duga

00:25

[rolfl/MicroBench] rolfl pushed commit 401ad653 to stepper

> Rename scale to remove ambiguity, consumer and function split now.

[rolfl/MicroBench] rolfl pushed commit 5aa6cc20 to stepper

> Spelling error.

rolfl

05:49

@Simon - git.tuis.net/ubench/ArraysSort.html <-- check out the page source

Duga

[rolfl/MicroBench] rolfl pushed commit 806528de to stepper

> Enable HTML template with D3 graphs and tables

Simon André Forsberg

14:36

@rolfl cool

  [1048576,90509664,11,394],
  [1572864,139210657,7,394],
  [2097152,187020753,6,394],
  [2621440,241210817,5,394],
  [3145728,297307806,4,394],
  [3670016,350751047,3,394],
  [4194304,394343487,3,394]

some numbers I didn't expect there. Trying to automatically estimate some numbers so that they don't become too big?

rolfl

Nope... I back-tracked the sequence..... logic is as follows...

as the progression doubles the scale, the last set of values become very sparse.

So, once i get to the "as much as I can do in a second....", I then back-step through 1/8th steps of the last value, and fill in so that the last 8 points have regular steps, not doubling.

Debatable logic.... but, it makes for more data points at the top end of the run.

Simon André Forsberg

ah, okay.

Reasonable logic. Useful data.

rolfl

github.com/rolfl/MicroBench/commit/…

Simon André Forsberg

Can you mark the points in D3 a bit more?

rolfl

See that commit?

Simon André Forsberg

14:39

yes

rolfl

Yes, just have to learn SVG as much as you learn D3

That line is the loop that happens after all the 'doubling' is done, and backtracks and ensures that the last 8 data points are on regular intervals.

Simon André Forsberg

So to use D3 you need to use a bit of SVG?

rolfl

It seems that D3 is a lot of things, but, in essense, SVG is a native component of HTML5....

and D3 uses it for all tthings graphics, because, to manipulate the SVG, you just need to manipuilate the DOM, and the CSS.

D3 contains a number of analytical functions to create structure on your data, and thena number of functions to createa a mating structure in the SVG.

Simon André Forsberg

I wonder how Flot does it...

rolfl

then, you just have to 'join' the data structure to the rendering structure, and you get a dynamic system.

change the data, and you can change the graphic... bit by bit, if you want.

Simon André Forsberg

14:45

What's the meaning of 394 in the source data?

rolfl

It is a nano-tick.

my computer seems to increment the nanosecond clock in units of about 394 nanoseconds.

github.com/rolfl/MicroBench/commit/…

Simon André Forsberg

And how is that data used in the HTML/JS/SVG?

other than showing up in the table?

rolfl

In other words, anything taking less than 394 nanoseconds to compute, probably will be reported as 0 nanoseconds.

It's not used, but, any value less than that is probably wrong.

Simon André Forsberg

isn't it possible that this takes more than one tick?

rolfl

Yes, so I run it 1000 times, and take the min ;-)

Simon André Forsberg

14:49

I mean, the real nanosecond tick count could be 197, but that it takes two ticks to run that piece of code

oh

rolfl

See the next method?

Simon André Forsberg

ah

and this is done for each scale value?

rolfl

No, this is done as a static initializer on the class...

Simon André Forsberg

okay

rolfl

github.com/rolfl/MicroBench/commit/…

Simon André Forsberg

14:51

so the data essentially uses a 'singleton' value. But why then copy that data to each row?

(perhaps I should read the code before I make comments about it)

rolfl

makes the data easier to manipulate..... once in Javascript, I think. I could do it differently, but it seemed useful to have just a single UScale.getJSON() and have that a single 2D array...

I am quite likely to be wrong on that assessment though

I was also regretting pulling the average time, and instead started pulling the fastest time.

but, it would actually be better to push all the values to the json... and annotate the values as an associative array:

{  nanotick: 394,
    data: [
       {scale: 1, fastest: 394, slowest: 134526, pct99: ......},
       {.....}
       .....
     ]
}

Or, perhaps, have a raw array, and a key of column-to-index in the data...

take less space... but, our data is not exactly big.

I did it all manually just to get something.

(and did not want to pull in Jackson, or anything.

Simon André Forsberg

@rolfl I think writing to JSON is preferred. Nothing wrong with humanly-readable in this case.

Totally understandable to not use Jackson for it.

rolfl

In fairness, all I did was: github.com/rolfl/MicroBench/commit/…

asnd eclipse messed up the formatting, not me.

Simon André Forsberg

@rolfl yeah, and that can easily be changed to using associative JSON data instead of raw arrays.

yeah yeah, blame it on the IDE.

rolfl

15:06

always

rolfl

16:19

@Simon - how is the line-fitting coming? I am deep in D3 at the moment.... adding 'standard' curves, I think, but I am also probably on the wrong priority at the moment.

Simon André Forsberg

16:37

@rolfl I seem to be having an issue with getting bad lines for O(n log n). The other ones seem to work just fine.

rolfl

What are the dependencies for this, your PNG from before indicate syou are running it in a tool of sorts?

Simon André Forsberg

@rolfl the only dependency is Apache Commons Math. The tool is another program I use just to verify that I am getting the correct results.

rolfl

Your goal here is to find the closest-match, right? In terms of what 'curve' best fits.

Simon André Forsberg

yes

rolfl

OK, good, so the visualization component is not the same as the identification.,

Simon André Forsberg

16:40

nope

rolfl

I'll keep looking at some visualization things then.

Question, @Simon ....

when you have linear complexity, it produces a straight line.

Simon André Forsberg

yes

rolfl

but, the slope is determined by the delta-time per iteration.

Is your analysis going to be able to identify a good "slope" for the best-fit linear?

Simon André Forsberg

yes

I plan on finding the best possible equation (best value of 'a' and 'b') for y = a * x log x + b and for y = ax^2 + bx + c and for some other mathematical functions, and then find which one of them is the best fit.

rolfl

OK, so, I am thinking then, that the JSON output from the results, should have things like:

bestfit: "functionx",
functionx: "complexityNLogN(..., ..., ...)",
functiony: "complexityLinear(0.4455)",

in other words, provide the coefficients of all the functions tested, and also an analysis of which one is best.

Simon André Forsberg

16:45

Linear is of the form y = kx + m, so two variables there. but yes.

rolfl

Actually, the line should always intersect (0,0) for all charts.

no runs always happen in no time.

right?

Simon André Forsberg

well, yes. that is true.

rolfl

That may simplify your analysis....

Simon André Forsberg

unfortunately it doesn't.

Gauss-Newton method works the same either way. It can have any number of unknown variables.

rolfl

OK. The math is beyond my understanding at the moment, and, if you solve that all, then it can stay that way ;-)

Simon André Forsberg

16:48

I hope to solve it

just slightly frustrating that O(n log n) doesn't work as I want it to

rolfl

{ title: "Arrays::Sort",
  nano_tick: 19,
  data: [
    {index: 1, count: 1000000, avg: 27, fastest: 20, slowest: 14541, pct99: 34, pct95: 30},
    {index: 2, count: 1000000, avg: 29, fastest: 22, slowest: 12319, pct99: 35, pct95: 32},
    {index: 4, count: 1000000, avg: 34, fastest: 25, slowest: 19043, pct99: 43, pct95: 36},
    {index: 8, count: 1000000, avg: 63, fastest: 32, slowest: 33264, pct99: 354, pct95: 69},
    {index: 16, count: 1000000, avg: 108, fastest: 87, slowest: 21090, pct99: 161, pct95: 117},

@Simon - running on a newer machine with Linux, suddenly my nanotick is 19.....

Also, that's the proposed output for the data now... thoughts?

Simon André Forsberg

17:08

@rolfl holy crap that's faster.

proposed output looks good

also @rolfl, I finally managed to get the O(n log n) working as expected

I ¤"(/)"¤/)(!¤#=!¤#/( used the wrong Log method

hoursSpentHere = approx 4;

Graph program used Log-10, I used Log-e

rolfl

trying not to laugh here.....

@SimonAndréForsberg In general, log in big-o is log2. (checking my sources....).

31

Q: Is Big O(logn) log base e?

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've always had trouble distinguishing between the differ...

Going for a walk, back in an hour or so.

Simon André Forsberg

17:36

@rolfl In general, I think that depends...

The base of the logarithm is the number of children each node has. If it's a binary tree then it's a base 2 log. — Paul Dec 4 '09 at 5:50

theoretically, I could add a base-detection of the formula as well, but I will hold on on that.

I will clean up some code now that I have things working, add a "fit relevance" value somehow, maybe I will push something later.

probably also need to add a convergence-check, otherwise I think Gauss-Newton can cause an inf-loop

Simon André Forsberg

21:58

umm.... @rolfl?

rolfl

Well, I have been back for a while.

Sorry, did not "call in" ;-)

Simon André Forsberg

I'm expecting linear time here but for some reason the times are constant.... something is strange

no worries.

    public static void main(String[] args) {
        scale(e -> sum(e), scale -> randomData(scale), false).report();
    }

    private static int sum(int[] i) {
        int sum = 0;
        for (int a : i) {
            sum += a;
        }
        return sum;
    }

Scale    1 ->      886 (count 100000)
Scale    2 ->      893 (count 100000)
Scale    4 ->      872 (count 100000)
Scale    8 ->      994 (count 100000)
Scale   16 ->      893 (count 100000)
Scale   32 ->      836 (count 100000)
Scale   64 ->      835 (count 100000)
Scale  128 ->      838 (count 100000)
Scale  256 ->      833 (count 100000)
Scale  512 ->      840 (count 100000)
Scale 1024 ->      845 (count 100000)
Scale 2048 ->      858 (count 100000)
Scale 4096 ->      852 (count 100000)
Scale 8192 ->      862 (count 100000)

(yes, I am at an old commit, haven't pulled the recent changes)

rolfl

Simon André Forsberg

many lines

but looks cool

rolfl

plotting all the times (slow, 99th, 95th, avg, and fastest), then the count is the opposite side.

Simon André Forsberg

22:01

aha

Duga

[rolfl/MicroBench] Zomis created branch newton

rolfl

Looking at your non-linear problem now too.

Duga

[rolfl/MicroBench] Zomis pushed commit 34f31653 to newton

> added MathModel and MathEquation

[rolfl/MicroBench] Zomis pushed commit fed3023e to newton

> added Models

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

> added apache commons math dependency

Simon André Forsberg

pushed my other changes now, actual working ones...

Duga

[rolfl/MicroBench] Zomis pushed commit 353d744c to newton

> Added ScaleDetect class -- main entry point for automatically detecting the scale of a UScale instance

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

> added call to ScaleDetect in UScale.report

rolfl

22:06

Hmmm, hung my system running that test.

Simon André Forsberg

which is weird, right?

it's a simple array creation and array loop... that shouldn't cause any problems...

rolfl

Scale    1 ->       22 (count 1000000, threshold 19)
Scale    2 ->       22 (count 1000000, threshold 19)
Scale    4 ->       23 (count 1000000, threshold 19)
Scale    8 ->       25 (count 1000000, threshold 19)
Scale   16 ->       26 (count 1000000, threshold 19)
Scale   32 ->       32 (count 1000000, threshold 19)
Scale   64 ->       39 (count 1000000, threshold 19)
Scale  128 ->       63 (count 1000000, threshold 19)
Scale  256 ->      104 (count 1000000, threshold 19)
Scale  512 ->      179 (count 1000000, threshold 19)

Simon André Forsberg

the test runs for a really long time for me, but it eventually gives me those results

okay, so I guess I will pull and merge then

rolfl

It was the really long time thing, all the arrays being rebuilt.

@Simon not yet... 20 minutes.

Simon André Forsberg

okay

rolfl

22:08

if you change the false to true, it will go faster.

there's no need to create a new array to sum them every time.

(sort them, yes, sum them, no).

Simon André Forsberg

it did go faster, yes. but it is still... constant time here.

Scale    1 ->      889 (count 100000)

Scale    2 ->      898 (count 100000)

Scale    4 ->      914 (count 100000)

Scale    8 ->     1017 (count 100000)

Scale   16 ->      902 (count 100000)

Scale   32 ->      883 (count 100000)

Scale   64 ->      861 (count 100000)

Scale  128 ->      861 (count 100000)

Scale  256 ->      940 (count 100000)

Scale  512 ->      851 (count 100000)

Scale 1024 ->      853 (count 100000)

Scale 2048 ->      848 (count 100000)

Scale 4096 ->      848 (count 100000)

could it be the JIT that removes the entire loop because the result is not used?

rolfl

I would expect to see that too.... but, it could be because I am running it as a function now.... you're probably still opn a consumer

Simon André Forsberg

yup, I'm running it as a consumer apparently

in theory, isn't it possible that all (or at least a lot of them) consumers be optimized-away?

Duga

[rolfl/MicroBench] rolfl pushed commit a9516071 to stepper

> New JSON format, improved HTML rendering of performance.

rolfl

git.tuis.net/ubench/Linear.html <-- report in HTML

@Simon ^^^

working on placement of labels, etc.

Simon André Forsberg

22:18

cool

can I merge your branch into mine now? (not necessarily the other way around)

rolfl

Yes, that makes sense, There's one item you should know....

I found the internal static final class was superfluous.

and yanked it.

Simon André Forsberg

okay

I think I will find a way to solve all that

rolfl

the getIndex() on the UStats instance contains the 'scale' of the result

Simon André Forsberg

Let there be merge conflicts!

I think my code lacks quite a bit of documentation and stuff.... and needs to be improved in some cases. For example, when analyzing something with linear time, my code often tells you that the best equation is something like -0.00001x^2 + 4x + 22, in which case it is obviously not quadratic time but linear time.

It does produce quite useful and correct equations though, which I think was the hardest part.

rolfl

I am looking forward to seeing it work... ;-)

I was thinking that I would make the 'labels' for the chart have checkboxes... turn off each series as you want them gone.

Simon André Forsberg

22:23

in a way, you can see it work already. if you check out my branch ;)

rolfl

then, add in series for the various possible functions, mostly turned off, except for the "best fit".

Simon André Forsberg

I think I have some cleaning up to do in the System.out.println though

@rolfl that is a very good idea.

rolfl

Adding series is surprisingly simple now.... so, it is just a case of figuring out how to express the series functions in Javascript, and communicate the parameters in the JSON.

Simon André Forsberg

speaking of labels, perhaps it is time to use some more github issues, and their labels, more liberally?

rolfl

Yes, I agree. issues would help us track .... issues.

asctually, it will help me focus instead of flittering around in odd places.

Simon André Forsberg

22:26

and feature-requests / ideas.

rolfl

And, speaking of feature requests... I have been requested to carve a roast... gotta run.

Simon André Forsberg

that's a roast-request!

rolfl

Hmmm, not quite ready... 10 more minutes.

Simon André Forsberg

I had an idea that the scale method (or function/consumer as it may be known now), could take a String parameter for name, for the occasions when you are doing several scale-calls and reports to System.out in a row and don't want to mix them up.

rolfl

I have a half-a-kludge on the HTML side of things, I added a name and outputfile for the report, not for the "run".

Adding it to the run makes more sense, and saving that in the UScale result instance.

Ahrgh, crap, @Simon, that's a messy merge.

on UScale, so much has been changed/relocated.

I see you made the Stats class public, and added a public getStats.

I would change getStats to return List<UStats> and be done with it.

then UStats.getIndex()

Well, my dinner is up........

Simon André Forsberg

22:38

@rolfl don't worry, I will handle that merge!

Duga

[rolfl/MicroBench] Zomis commented on src/main/java/net/tuis/ubench/UScale.java of commit 806528de

> ExampleScales is in the src/test section which is inaccessible from src/main. This does not compile.

Duga

23:26

[rolfl/MicroBench] Zomis pushed 7 commits to newton

[rolfl/MicroBench] Zomis pushed commit c62e9b8b to newton

> added reporting of sum method of O(n) complexity

[rolfl/MicroBench] Zomis pushed commit b4b26ca2 to newton

> made ScaleDetect return the best MathEquation from a number of MathModels.

[rolfl/MicroBench] Zomis pushed commit 9169fecb to newton

> Merge branch 'stepper' into newton, fixed merge conflicts and fixed compiler-error when using ExampleScales class reference in src/main

Simon André Forsberg

TTGTB

Transcript for