Performance optimisation: Use Map as storage of binding dictionary

remojansen commented 8 years ago

Expected Behavior

I'm preparing some nice features and improvements for 3.0 and this is one of the things I though...

We can use a Map to replace the current implementation of binding dictionary insertion and search which are implemented with using an array. This would make the library much faster!

NOTE: No performance issues has been reported by users to this date I'm just being pro-active and improving things.

Current Behavior

At the moment the binding dictionary is an array. This array contains KeyValuePair<T> the key is a ServiceIdentifier and the value is T.

The current implementation has a O(n) complexity:

private getIndexByKey(serviceIdentifier: interfaces.ServiceIdentifier<any>): number {
        let index = -1;
        for (let i = 0; i < this._dictionary.length; i++) {
            let keyValuePair = this._dictionary[i];
            if (keyValuePair.serviceIdentifier === serviceIdentifier) {
                index = i;
            }
        }
        return index;
 }

This means that as we declare more and more dependencies the library gets slower and slower. Using a Map we will reach O(1) complexity

Possible Solution

Use a Map instead of an array.

Steps to Reproduce (for bugs)

The avl-dictionary branch contains unit test that allow the performance validation:

https://github.com/inversify/InversifyJS/tree/avl-dictionary

At the moment (before Map refactor) the test fail:

  5 failing
  1) Performance Registring 5K bindings should be doen in less than 1 ms:
     AssertionError: expected 2.4989089999999123 to be below 1
      at Context.<anonymous> (test/node/performance.test.js:58:45)
  2) Performance Resolving 1 binding should be done in less than 1 ms:
     AssertionError: expected 1.115168199999971 to be below 1
      at Context.<anonymous> (test/node/performance.test.js:63:39)
  3) Performance Resolving 5 bindings should be done in less than 1 ms:
     AssertionError: expected 1.129180599999927 to be below 1
      at Context.<anonymous> (test/node/performance.test.js:68:39)
  4) Performance Resolving 1K bindings should be done in less than 1 ms:
     AssertionError: expected 1.1172302000002674 to be below 1
      at Context.<anonymous> (test/node/performance.test.js:73:40)
  5) Performance Resolving 5K bindings should be done in less than 1 ms:
     AssertionError: expected 4.970788600000015 to be below 1
      at Context.<anonymous> (test/node/performance.test.js:78:40)

We need to find realistic times to prevent random build failures.

skyrpex commented 8 years ago

Why not a WeakMap or a Map itself?

remojansen commented 8 years ago

@skyrpex thanks a lot this suggestion. Many times I made the mistake of forgetting that Map and WeakMaps are available. I though about using an AVL tree to improve complexity from O(n) to O(log n). But looks like Map uses a hash table internally and achieves O(1) complexity. I will use a Map :smile:

remojansen commented 8 years ago

Expect this to be merged soon 🎉