Exponential Time Complexity in adding / removing from related collections. #449
Description
Hi there Paul!
I've been a pretty happy camper with your library so far, I appreciate your work. That said, there's an unfortunate problem with the implementation that causes enormous slow down at non trivial data sizes that shouldn't be too hard to fix.
The problem lies in detecting the addition or subtraction of membership from relations around lines 644:
// When 'relatedModel' are created or destroyed, check if it affects this relation.
this.listenTo( this.instance, 'destroy', this.destroy )
.listenTo( this.relatedCollection, 'relational:add relational:change:id', this.tryAddRelated )
.listenTo( this.relatedCollection, 'relational:remove', this.removeRelated )By having each collection register a handler to manage receiving adds / destroys, the time complexity of adds / destroys becomes exponential (adding the Nth object requires N-1 handler loops, each which are fairly expensive in of themselves). Around even just 2K objects, there is severe UI lag, and each additional add beyond that is again, increasingly harder. All of the time in the profiler is, unsurprisingly, spent in the trigger handlers added here.
The fix is pretty simple: do what a database does, and have a reverse index on relation's membership ids. Instead of multiple handlers, register a single global handler unique to the combination of relatedCollection, model, and key. That handler uses the reverse index to lookup the (much smaller) group of effected objects and their relations.
I started work on fixing this myself, but got stuck on the last handful of tests when I realized I didn't quite understand the differences between keyId, keyContents, and the various event lifecycles in order to maintain the reverse index.
If this is something that would be a simple fix for you it'd be a huge win for speed in the library and would allow me to use it for non trivial datasets.