listListenerMatching optimization

[andrewluetgers]

I closed a prior PR because it was hopelessly messy. Hopefully this will make it easier to evaluate this change.

listListenerMatching optimization

This optimization was the result of experimenting with a custom omniscient mixin that allows you to do reference observer based updating of components directly as opposed to the usual top down approach. https://github.com/omniscientjs/omniscient/issues/93#issuecomment-84812169 I was able to achieve 80 fps using what would be the normal approach with immstruct, with the omniscient mixin I was able to get 100 fps and with this change to the underlying datastructure used by listListenerMatching I was able to achieve 170 fps. As a reference the fastest this app can operate on my machine is at 200 fps using vanilla js. See the above link for running code samples.

Currently the only test that is failing is 'should allow values as key paths.' This implementation expects to be able to turn keyPaths into keys in a plain JS object for the tree of observers so may be incompatible with values as key paths if those "values" cannot be easily turned into a string.

[andrewluetgers]

@mikaelbr here is a Map implementation with deepSet and deepGet demonstrating a data-structure that could be used in place of this current implementation with it's basic JS objects and string keys. It also shows how the data-structure would store the callbacks and how you could add and retrieve them. https://gist.github.com/andrewluetgers/7f0f043ea2224c315ad0

let me know if I should move forward with an update using this Map impl.

[dashed]

Looks like something similar to deepSet/deepGet is being incubated in lodash as _.get and _.set: https://github.com/lodash/lodash/commit/2edcc893034936cccb94264783453b3d6bceff45

Might be good to use that in the future, as alternative implementations, when it gets released.

[andrewluetgers]

@Dashed not exactly, this is a very specific use case and not used anywhere else in the codebase. I contributed to lodash-deep early on and am pretty familiar with the issues involved. Fundamentally you can cut a lot of corners in this case as it is an optimization and not a general use utility there should be no problem with that.

[dashed]

Fair points. But there's no harm in outsourcing these utilities to eventual modules: https://npm.im/lodash.get https://npm.im/lodash.set

I suggest this because those API methods may have the necessary optimizations you don't need to worry about, nor maintain at a higher-level library like immstruct.

[andrewluetgers]

This is the thing, there is not going to be a deepGet, or deepSet implementation in lodash that works with a Map data-structure (takes any value for keys, uses Map.get, Map.set), it will work with native js objects and arrays (strings for keys, native object access and mutation syntax). Similarly I also could write this optimization with the Map implementation in immutable.js that would obviate the use of my custom Map but that would be overkill for a performance optimization I suspect it would use more memory and be slower. Of course only testing both will tell you that but at either rate you need some code to take a keyPath into a tee of Maps and use it to set and get values into those Maps to make it all work.

https://gist.github.com/andrewluetgers/7f0f043ea2224c315ad0#file-map-js-L37-L67

[andrewluetgers]

When lodash releases a deepGet, deepSet I'll certainly look at it for some possible improvements but if I want to use their code I'll have to fork it to support working with a tree of Maps. There is already a lodash-deep which I have actually contributed to. I could have also used that but again it would be a fork and there is much complexity there because it is intended as a general use utility.

[andrewluetgers]

@mikaelbr I have merged in the Map changes so now this change supports arbitrary types for keys. I think this still needs more tests but would like your feedback. Performance-wise there is no discernible impact to switching to the new Map structure which is still logging in at ~170fps.

[mikaelbr]

I was experimenting with maps yesterday my self, but since we have access to Immutable.js I thought it made more sense to use Immutabe.Map. I had some kinks I needed to work out, though. But maybe it makes sense to use Immutable.Map? Also, while I was looking into the source code yesterday, I fpund thee code a bit hard to follow and I'm not the biggest fan of mutation and side-effect in the helper functions (match listeners etc).

But I think transitioning to maps is a good idea, and makes sense.

[andrewluetgers]

I'm not sure why you need immutability now to back the storage of callbacks, was that a concern before when you were using arrays? I think the two (needing a Map vs. needing immutability) are getting conflated. But honestly if it does not dramatically affect performance then I guess it why not?

[mikaelbr]

I don't say we need immutability, but we already have a Map implementation available - and probably don't need a custom implementation. And I think it's hard to follow the application flow with a lot of side-effects.

[andrewluetgers]

Fair enough, any suggestions on how to make the code easier to follow? Also what are the areas of mutation and side-effect that are of concern?

[dashed]

I glanced over the rework using the Map implementation. I noticed that appending __listeners__ to path doesn't actually avoid collisions:

var _pathListeners = Map();
getListenerNs(_pathListeners, ['foo']).push(1);
getListenerNs(_pathListeners, ['foo', '__listeners__']); // => error

A compromise may be to make __listeners__ configurable via Structure options. Or, if you don't want an official API for it, make it a property structure._listenersKey = '__listeners__' for advanced users.

[andrewluetgers]

@Dashed yes, it is not perfect, I think it would be good to throw friendly error message if we see a key that matches the listeners key and make it configurable.

[andrewluetgers]

@Dashed I just realized now that it uses a Map the listeners key can be a unique sentinel value ala

var listenersSentinel = {};

this would fully prevent any collisions :-)

[dashed]

That works too :+1:

[dashed]

@andrewluetgers You should probably put this map implementation as an npm module.

[mikaelbr]

@andrewluetgers I added a PR for replacing the Map with a already available Map, and re-wrote some functions to show better intent. The thing I thought was making it harder to follow was that _pathListeners was changed as a side-effect inside getListenerNs. I'd much rather have pure functions - which only change the system by its return value.

[andrewluetgers]

@mikaelbr @Dashed are either of you already or wanting to work on implementing the fix for cursor specific callbacks using cursor sentinel values, if not I will.

[dashed]

@andrewluetgers feel free to go ahead.

[andrewluetgers]

@Dashed @mikaelbr please take a look at the latest changes for unobserving, THANKS!

[dashed]

@andrewluetgers Sorry. I've been afk, and out of the country for a while. Within a week or so, I'll definitely review the changes :)

[mikaelbr]

@andrewluetgers Looks good to me. I see you extended the unobserveAll API to include "unobserve all but this". Must remember to document that. (it is only used to re-add cursor refresher for future use I see now)

I feel comfortable merging this as you've added the test of unobserve not leaking to other references, and all other tests pass. Thanks for your great work!

[andrewluetgers]

Awesome, THANKS