Add some magic to arrays manipulation to boost perf

[alshakero]

Consider

const arr = [1,2,3,4,5,6];

When you arr.shift() what technically happens is

MOV 2 -> 1
MOV 3 -> 2
MOV 4 -> 3
MOV 5 -> 4
DELETE [6]

Same happens if you splice. But starting from the index you pass. Now imagine you have an array of 1000 items. Shifting it would produce 1000 operations! All sent via web socket. Assuming it's an array of integers (not deep objects), smallest operation is 50 bytes, 50 * 1000 = ~50KB of transfer for deleting a single list item! Can you imagine how slow is this? It takes ~100ms to do a single shift operation on the same host, imagine via network. And this applies to jsonpatch and to proxies. It's not proxies fault.

Proposed solution:

Simply produce a single remove operation.

How?

With jsonpatch this cannot happen. But with proxies when you call shift and splice you're invoking the proxy getter with key = shift, and I can return to you any method I want. And I can return a special shift/splice function that does exactly the same job for you but emits a single patch instead of N.

Challenges

• JSON-Patch RFC compliance: Luckily, this complies with the RFC, the RFC actually defines a single remove op as the correct behaviour, and it's the applying end duty to shift the array, not the observer to issue all those operations.
• jsonpatch.applyPatch support: I tested. Applying a remove operation on the array yields the correct results.
• Server support: I don't know about this and will need some testing.

Objective:

This will give a great boost to general Starcounter performance.

/cc @warpech @tomalec

[tomalec]

With jsonpatch this cannot happen. But with proxies when you call shift and splice you're invoking the proxy getter with key = shift, and I can return to you any method I want. And I can return a special shift/splice function that does exactly the same job for you but emits a single patch instead of N.

😍

This will give us not only a perf boost, but will also let us cover existing issues and request to support move and remove in a more sane way. Plus this will make debugging such patches 100x easier.

[tomalec]

BTW, what do I miss something or the only "magic" here is just the Proxies?

[alshakero]

@tomalec there is some actual magic.

1. When you call shift, I give you a function that extends original shift, and this function sets a boolean called currentlyShifting = true when called.
2. Now all replace operations will still happen inside the set proxy trap, and there is no way to escape that, but since the currentlyShifting is true we don't emit them and keep silent.
3. Then comes the last operation, which is deleteProperty invocation, JS actually deletes the last array element since it shifted everything left. But what we do is check if currentlyShifting = true and return remove, path=0 instead (as opposed to path = N - 1), and set currentlyShifting = false to go back to the normal non-shifting state.

Same explanation applies to splice but with a bit more logic.

[tomalec]

Are you saying that you will overwrite array's native shift? Could you write a sample code form users perspective?

[alshakero]

Are you saying that you will overwrite array's native shift?

Not on the global scope. Only the proxified arrays will be affected.

The user will not have to do anything.

var myObj = { numbers: [1, 2, 3] };
var jsonPatcherProxy = new JSONPatcherProxy( myObj );
var observedObject = jsonPatcherProxy.observe(true);
observedObject.numbers.shift();
jsonPatcherProxy.generate() // => {op: 'remove', path: '/0'}

[tomalec]

Not on the global scope. Only the proxified arrays will be affected.

👍

However, then we could miss it in cases like:

var myObj = { numbers: [1, 2, 3] };
var jsonPatcherProxy = new JSONPatcherProxy( myObj );
var observedObject = jsonPatcherProxy.observe(true);
Array.prototype.shift.call(observedObject.numbers); 
jsonPatcherProxy.generate() // => two replaces and  remove

[alshakero]

@tomalec correct, I thought about it but I dug Polymer source and they use yourArray.splice 💃

[tomalec]

The good thing is that in the case I describe we will still be JSON Patch compatible, but just less consise.

[alshakero]

Exactly.

[warpech]

With Starcounter apps this is an edge case, because server only allows remove operation on the arrays of primitives.

It would be 100x more worth it to implement this in C# Palindrom as of now, because that one often generates patches that remove objects from an array.

[warpech]

This is in line with what @miyconst said about the same problem here: Palindrom/Palindrom#128 (comment)

[alshakero]

because that one often generates patches that remove objects from an array.

Aha! Didn't know that, even though it's obvious now that I think about it.

This is in line with what @miyconst said about the same problem here

I'm not talking looping or any bad design though, arr.shift()/arr.splice() is all you need to have the issue. And this happens with jsonpatch and JSONPatcherProxy.

[miyconst]

This brings us to the very old design decision which was and still is:

• JSON view-model tree has to be defined on the server.
• Clint is allowed to change primitive values only.
• Array actions (add/move/remove items) are equal to JSON tree modification.

So, before solving any implementation difficulties, we should reconsider or design decision, and what/why should be allowed, to what extend.