Link.js v0.4.2

Topic: Link.js v0.4.2 (Read 1338666 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.

Re: [code] Query.js for Sphere

Reply #30 – January 04, 2014, 05:23:45 pm

Query 2 is only 429 lines, but expected to grow as more features are added.

I had thoughts of adding super-optimizations, like map-map-map and where-map-map-where, but I think that's a bit overkill, yet totally doable.

Query 2 does this:

A sequence like this: Map.Map.Where/Filter.Each();

Turns into this chain:

Map2Node -> WhereNode -> EachNode -> null

Map2Node is an optimization. Where/Filter type nodes breaks the chain early if they fail. This is not recursive or I'll run out of stack space, so it pops the chain back (via return) and restarts it, iterating to the next value. Now, it returns the successful value if it made it to an 'end node' like Each or All, or undefined if it stops part-way (Filter, Uniq etc). Checking for Undefined can aid in performing queries that involve 'contains' and 'every'. The optimizations work by reducing unnecessary node traversals and function stack creations. The optimizations speedups hit the limit of actually doing the raw for loop, and so with a sufficient optimizer I think the complexity is equal to a hand written for loop (with the only downside of traversing nodes added to the mix).

To run it, all I do is this:

Code: (javascript) [Select]


var i = -1, l = 25000000;
while (i++ < l && !Env.stop) r.exec(a[i]);

So it has a very lightweight loop on the inside, and the only overhead is node switching. Things like break and continue are handled with node chains returning early and setting the environment stop element to true.

Edit:
I was able to get Lazy to work in Sphere 1.6, it turns out the number of things I had to change was small.

How's the performance of the two? Well... The same! Everything I threw at it, they performed the same. For longer queries I notice Query 2 was always faster, but for single queries, Lazy won. To get an idea:

On map, Lazy was 1.3 times faster.
On map-map, Query2 was 2.0 times faster.
On map-map-map, Query2 was 2.2 times faster.
On map-map-map-map, Query2 was 2.7 times faster.

So, longer queries, especially the optimized cases with map-map, Query2 started to really haul ass. But, this is like 'best results' stuff and totally not typical. For typical queries (like yours with isInt and div3) the two performed the same (with Query2 slightly faster).

Re: [code] Query.js for Sphere

Reply #31 – January 05, 2014, 12:52:48 am

So when will Query 2 be ready for primetime? I'd like to use this functionality in Specs, but I'm thinking it'd be better to wait for the latest version. Unless Q2 will be API-compatible with Q1, in which case I guess I could just throw 1 in there for now...

Re: [code] Query.js for Sphere

Reply #32 – January 05, 2014, 01:14:01 am

Use Q1 for now - definitely a good start. Then when Q2 is ready (which I may rename to "Dash" when it's done), you can seamlessly upgrade. Methods will also have various names: foreach, each, forEach; where, filter; uniq, unique; length, count, size; etc. So that just increases it's drop-in compatibility. But the .from() part of it may change; if it does I'd just wrap a compatibility thing around it that's all.

I had designed Query with turn based battle systems in mind.

That said, Query2 does have all the core functionality working. It's current API (all complete except reduce and every):

Code: (text) [Select]


chainable:
 - take(n)    - take the first n results.
 - first(|fn) - take first satisfying item, or if no function, the very first item.
 - map(fn)    - perform a map operation with fn.
 - where(fn)  - perform a filter using fn as the predicate.
 - get(num)   - tries to get the indexed item.
 - uniq()     - filters the results to only unique items.

non-chainable:
 - each(fn)         - perform the query, running the results through a function.
 - toArray()        - perform the query, returning an array.
 - contains(o|p)    - perform the query, returning true if it satisfies the predicate or matches the object.
 - indexOf(o)       - perform the query, returning -1 if item not found, or the index.
 - every(fn)        - perform the query, checking to see if all items satisfy the predicate.
 - reduce(fn, memo) - perform the query, reducing the results, starting at memo, or if not, the first item.
 - length()         - perform the query, returning the overall length.
 - count(p)         - perform the query, returning the overall number of times the predicate was satisfied.

Reduce and every are not hard to implement, so they'll be done soon.

Next I have planned:
Zip,
Slice,
Reverse, <-- gonna be HARD in my very linear system

Sort, <-- gonna be HARD in my very linear system

Concat,
Union,
Intersection,
Difference,
First,
Random.

And that's all.

Re: [code] Query.js for Sphere

Reply #33 – January 05, 2014, 01:36:31 am

What does zip do? Don't think I've ever heard that term in the context of query systems...

And for what it's worth, I'm opposed to the rename to Dash. It sounds like a codename. Lazy and For.js make some sense; Dash is not self-explanatory at all, all it communicates is that it's fast, information which is irrelevant on its own. It'd be like calling TurboSphere simply "Turbo".

Re: [code] Query.js for Sphere

Reply #34 – January 05, 2014, 01:56:29 am

Underscore, lo-dash, Dash. I think it's just another one of the family... I still haven't finalized the name though, I'm still calling it Query 2 so don't fret too much!

BTW, map and reduce are done.

I just realized I can implement toArray with reduce. (But it's slower, so I won't replace toArray's functionality with that... Lazy should take note!).

Code: (javascript) [Select]

Query2.from(array).reduce(function(a, b) { a.push(b); return a; }, []);

Zip tries to insert items from another array into this stream. This is what Lazy does:

Code: (javascript) [Select]

Lazy([1, 2]).zip([3, 4]) // sequence: [[1, 3], [2, 4]]

It applies to lazy generation since you also want to delay the results of zip until you've performed your transformations.

Re: [code] Query.js for Sphere

Reply #35 – January 05, 2014, 09:11:50 pm

I was able to make Query 1 faster than lazy. Jesus, Lazy must not be all that it's cracked up to be, or I'm missing something here.

My trick:

Again optimize with wheremap and mapwhere. Query1 now has those, but instead of an optimizer figuring that out for you, you do the conscious decision of adding it in.

Code: (javascript) [Select]


var a = Query.from(arr).wheremap(even, add1).mapwhere(div3, isInt).each(noop);
var b = Query2.from(arr).where(even).map(add1).map(div3).where(isInt);
var c = Lazy(arr).where(even).map(add1).map(div3).where(isInt).each(noop);

Query 1: 212ms
Query 2: 37ms
Lazy: 249ms

Though I will say this: Query 1 is a destructive method, it will modify the array. This is good in some situations and for games, even ideal since you may want to remove certain combatants. So I think Query 1 should always be used for game loops while query 2/lazy used for large data (esp. database-y stuff).

Lord English: I'd suggest you use Query 1 for a turn based battle system.

Also, I was able to add sort to it. It's not ideal... But it's passable. The sort method is not lazy, it's eager. So when it encounters the sort method it stops everything and runs the query right there and then, then continues with the sorted data. Lazy doesn't sort arrays at all, you'd first create an array and then sort it yourself (preferably using JS .sort method), which is what I do anyways. So speed-wise they are no different. I would have liked my own sort method that works while in lazy execution, but it's hard since indices move around, etc.

Re: [code] Query.js for Sphere

Reply #36 – January 05, 2014, 11:11:37 pm

I don't know, destructive traversal makes me nervous in any case, I prefer to have control over what stays and goes in the array. Mainly because I prefer to keep my queries separate from maintenance operations. Sometimes it's unavoidable and you have to modify the structure while traversing it but I try to avoid that whenever possible, mainly to minimize the number of expensive deep copies I have to do.

Re: [code] Query.js for Sphere

Reply #37 – January 06, 2014, 12:21:58 am

You are right Lord English. It's usually better to find what get's deleted before you delete. So, there is that advantage. In that case, Query 2 would then be the only solution. But from a raw speed perspective, finding things to delete and then deleting them is a tad slower than finding and deleting at the same time; however you at least get no adverse side effects.

Re: [code] Query.js for Sphere

Reply #38 – January 07, 2014, 07:43:41 pm

Here you guys go: https://github.com/Radnen/link

Use it, abuse it, tell me of it's issues.

Re: [code] Query.js for Sphere

Reply #39 – January 12, 2014, 03:40:33 am

Okay... weird issue, that makes Link impossible to benchmark vs. other libraries.

Lazy is faster than everything - consistently - and I don't know how it is doing it. My benchmarks were not wrong for Link: the scores are indeed faster, when you run the benchmark program once. The second and third attempts it gets slow and I have no damn clue how or why.... No damn clue as to why. It can get up to 3 times slower on a second benchmark run.

Ok... so, Benchmark.js will do 'n' samples to get a good reading. That means link will run those 'n' times, and it is fast and produces good results. Then the very second time Benchmark.js is ran on it, boom it explodes and my Link library is consistently slower all the time.

There is nothing wrong with Benchmark.js - I have tried my own profiling code (not as fancy) but the same thing happens, the second benchmark run it gets slow. Not the second time Link runs it's query. Lazy produces no change in speed - at all!

The array is not being modified between each benchmark run, in fact it is recreated, but that recreation is not factored into the overall time.

I have a different version of Link that uses all arrays, and it is slower than Link, but still the same thing happens. The second benchmark run, it gets slower and Lazy remains unchanged. Whatever it is I have zero knowledge as to why this is happening. But it's literally making benchmarking impossible.

Edit:
Ok, I found the issue and it's out of my control. :/

Code: (javascript) [Select]


// A:
var link = Link(array).map(add).filter(even).map(add);

link.each(noop);

// B:
var link = Link(array).map(add).filter(even).map(add);
    link = Link(array).map(add).filter(even).map(add);

link.each(noop);

// C:
var link = Link(array).map(add);
    link = Link(array).map(add).filter(even).map(add);

link.each(noop);

Which of the above is the fastest? Well, technically all of them since link ends up doing the same thing, right? But it turns out that A is twice as fast as B and C lies somewhere in the middle. WTF?

Edit 2:
Ah ha! In Firefox this is not happening and I noticed two things:

1. Firefox's JS is 3 or more times faster than Chrome. Jesus Christ I had no clue. 0_0
2. Lazy is getting slower with each repeated call, yet Link gets faster.
3. But as I try different tests then come back, the same issue that plagued it under chrome also plagues it under firefox... Could it be a GC thing?

Re: [code] Query.js for Sphere

Reply #40 – January 12, 2014, 05:21:47 am

Bear in mind, I haven't looked too closely at the guts of link.

Quote from: Radnen – on January 12, 2014, 03:40:33 am

Okay... weird issue, that makes Link impossible to benchmark vs. other libraries.

Lazy is faster than everything - consistently - and I don't know how it is doing it.

Perhaps it was optimized for implicit asm.js compliance? What JS VM are you testing on?

Quote from: Radnen – on January 12, 2014, 03:40:33 am

My benchmarks were not wrong for Link: the scores are indeed faster, when you run the benchmark program once. The second and third attempts it gets slow and I have no damn clue how or why.... No damn clue as to why. It can get up to 3 times slower on a second benchmark run.
...
Whatever it is I have zero knowledge as to why this is happening. But it's literally making benchmarking impossible.

The following may just be silliness. It's based on my slightly shaky theoretical knowledge of the internals JavaScript VMs. And I expect the problem doesn't really need quite this deep of an explanation.

If you are testing on newer JS VMs, it's quite possible that it gives the high-optimizer hell with highly variable types being given as function parameters. The high-optimizer gets a lot of positive reinforcement for a function taking a certain type, then you through all kinds of types into the function, and because of all the previous reinforcement it keeps trying to reoptimize the function for each new type. Like branch misprediction on a CPU.

Otherwise, it might be angering the garbage collector by reusing the same space for types that have different underlying representations. That can be difficult to see at first with V8, since it takes the 'sinking ship' approach and just grows the stack for a very long time. But a more efficient (size-wise) memory model (perhaps like SpiderMonkey), and it would have to reorganize the JS stack a lot. Which is hellishly slow.

Re: [code] Query.js for Sphere

Reply #41 – January 12, 2014, 05:39:11 am

That's... not such a bad idea. But then again, this is how all functional programming libraries operate, they commonly change up the function definitions as you do different things. What I find interesting is Lazy is stable through all of that while Link is not... it varies, a lot.

Re: [code] Query.js for Sphere

Reply #42 – January 12, 2014, 08:36:42 am

If you want 100% performance, you probably shouldn't pass arguments types that integral underlying implementations and vary type with function call?

That's what I've deduced, anyway.

The alternatives I can think of would be really ugly. You'd pretty much be reimplementing the VM's internal type hierarchy. Put that way, it sounds like it's completely the VM's job to make it fast.

Quote from: Radnen – on January 12, 2014, 03:40:33 am

Ah ha! In Firefox this is not happening and I noticed two things:

1. Firefox's JS is 3 or more times faster than Chrome. Jesus Christ I had no clue. 0_0
2. Lazy is getting slower with each repeated call, yet Link gets faster.
3. But as I try different tests then come back, the same issue that plagued it under chrome also plagues it under firefox... Could it be a GC thing?

The main functional difference between SpiderMonkey and V8 is how they deal with memory. At least, it's the biggest difference I know of.

SpiderMonkey is designed to try and not call GC that much, but to free memory on the spot more often when it knows it can.

V8, however, takes the 'sinking ship' approach. It grows the stack as much as possible, using all available memory. This is because it really is faster to just not free memory. That is, until you need to. Then it's really slow. But in the context of a JS engine, you often won't get to that point.

The fact that it has such a huge difference between SM and V8 makes me believe it is either some asm.js-based optimization kicking in (V8 doesn't do that, no idea why not), or it is related to garbage collection.

Re: [code] Query.js for Sphere

Reply #43 – January 12, 2014, 06:07:55 pm

So Link is the new name for Query 2, I take it. Clever, naming it after LINQ. Now it really is LINQ for JavaScript!

I'll have to give this a test-run.

Re: [code] Query.js for Sphere

Reply #44 – January 13, 2014, 03:57:19 am

So I made some adjustments so it can use less memory, and now I'm faster.

But there is still an issue and I really think it has to do with GC'ing. My code when benchmarked runs faster than Lazy (about 2 times faster) for the first 11 trials. Then on trial 12 it becomes 5 times slower, and then on trial 14 it gets 2 times slower, on trial 15 it is back to normal speed, about 2 times faster. Lazy remains constant throughout. :/

See for yourself:

Code: (text) [Select]


Link map-filter-map-each: 0.6099999998696148ms index.html:37
Lazy map-filter-map-each: 1.0999999986961484ms index.html:37
Lo-Dash map-filter-map-each: 4.469999999273568ms index.html:37
Fastest is Link map-filter-map-each index.html:40

Link map-filter-map-each: 0.6400000001303852ms index.html:37
Lazy map-filter-map-each: 1.1199999996460974ms index.html:37
Lo-Dash map-filter-map-each: 4.359999999869615ms index.html:37
Fastest is Link map-filter-map-each index.html:40

... snip ...

Link map-filter-map-each: 0.6700000003911555ms index.html:37
Lazy map-filter-map-each: 1.1199999996460974ms index.html:37
Lo-Dash map-filter-map-each: 4.360000002197921ms index.html:37
Fastest is Link map-filter-map-each index.html:40

Link map-filter-map-each: 2.169999999459833ms index.html:37
Lazy map-filter-map-each: 1.1299999989569187ms index.html:37
Lo-Dash map-filter-map-each: 4.370000001508743ms index.html:37
Fastest is Lazy map-filter-map-each index.html:40

Link map-filter-map-each: 2.1600000001490116ms index.html:37
Lazy map-filter-map-each: 1.1199999996460974ms index.html:37
Lo-Dash map-filter-map-each: 4.340000001247972ms index.html:37
Fastest is Lazy map-filter-map-each index.html:40

Link map-filter-map-each: 1.4199999999254942ms index.html:37
Lazy map-filter-map-each: 1.1300000012852252ms index.html:37
Lo-Dash map-filter-map-each: 4.339999998919666ms index.html:37
Fastest is Lazy map-filter-map-each index.html:40

Link map-filter-map-each: 0.6199999991804361ms index.html:37
Lazy map-filter-map-each: 1.1299999989569187ms index.html:37
Lo-Dash map-filter-map-each: 4.3299999996088445ms index.html:37
Fastest is Link map-filter-map-each

Link generates far more objects than Link does, but is somehow stable throughout. There is, I find, no apparent reason for Lazy's performance, when the lazy-evaluation methodology is the same for both link and lazy.

Edit: Okay, I think I know where the trouble is. See, a JS compiler needs a static function to optimize well.

So, it turns out doing this:

Code: (javascript) [Select]


function obj() {
    this.test = function() { /***/ }
}

Is worse than this:

Code: (javascript) [Select]


function obj() { }
obj.prototype.test = function() { /***/ }

New results are even faster (even 20+ trials later):

Code: (text) [Select]


Link map-filter-map-each: 0.5799999996088445ms index.html:37
Lazy map-filter-map-each: 1.1199999996460974ms index.html:37
Lo-Dash map-filter-map-each: 4.879999998956919ms

But now that means I lose private variable closures... Oh well.

Edit thrice:
I has released teh codez.

Benchmarks: http://radnen.tengudev.com/link-benchmark
Git: https://github.com/Radnen/link

Edit to the fourth:
I updated to v0.2.1, it is much faster now.