fix: made type-metadata.storage.ts much faster #2212

roypeled · 2022-06-01T12:31:36Z

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays.
This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

PR Checklist

Please check if your PR fulfills the following requirements:

The commit message follows our guidelines: https://github.com/nestjs/nest/blob/master/CONTRIBUTING.md
Tests for the changes have been added (for bug fixes / features)
Docs have been added / updated (for bug fixes / features)

PR Type

What kind of change does this PR introduce?

This change mainly modified type-metadata.storage.ts file. This file stored all the objects' metadata in arrays, and during an application bootstrap, it would iterate all the data multiple times to filter the required metadata (mostly filter by class type, but also property field names and more).

What I did was to modify how the data is stored with multiple new classes which store the metadata within Maps, thus retrieving the correct data is a simple get instead of a filter.

From my tests on my (pretty large) GQL project, the bootstrap time went from 90s to 8s.

What is the current behavior?

Issue Number: #2206

What is the new behavior?

Does this PR introduce a breaking change?

Yes
No

Other information

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

roypeled · 2022-06-01T12:40:49Z

OK, I see failing e2e tests here, but the ones I ran locally with npm run test:e2e passed (and there weren't a lot).
So I guess I'm missing a step here.
Is there another test suite somewhere?

kamilmysliwiec · 2022-06-01T13:01:33Z

You might need to clear your local jest cache (with --clearCache) - perhaps you're not actually executing those tests

roypeled · 2022-06-01T13:08:42Z

Yep, I didn't notice that I was running only the graphql package tests. Working on solving the breaking tests now.

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

roypeled · 2022-06-01T15:41:22Z

All test pass!

kamilmysliwiec · 2022-06-02T06:46:27Z

packages/graphql/lib/schema-builder/storages/type-metadata.storage.model.ts

+} from '../metadata';
+import { ObjectTypeMetadata } from '../metadata/object-type.metadata';
+
+export class MapByName<T> {


Can we create a dedicated folder, let's say, "collections" and then have a file per class there?

Sure, that's a good idea. I didn't know where to place this file but your suggestion is appropriate

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

kamilmysliwiec · 2022-06-03T08:56:47Z

packages/graphql/lib/schema-builder/collections/array.collection.ts

@@ -0,0 +1,15 @@
+export class ArrayCollection<T> extends Array<T> {


Extending built-in collections is typically considered a bad practice. Any reason we cant use Array directly?

Yeah, for every collection that we are saving per metadata class, we also need to save a global collection of all the classes collections in a flat array.
I thought the easiest way to do that is to hook on arrays push and I shift methods, but it maybe bette to have this class create an internal array and expose the required methods

Pushed another fix, now I'm wrapping the array instead of extending it. Good comment!

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

rezoled · 2022-06-12T13:51:39Z

any update on this?

kamilmysliwiec · 2022-06-14T09:30:55Z

packages/graphql/lib/schema-builder/collections/array.collection.ts

@@ -0,0 +1,35 @@
+export class ArrayCollection<T> {


This still doesn't seem right. ArrayCollection class basically wraps another array inside and hooks into some of the methods (push and unshit) to simply insert these elements into the global array . We should - at the very least - rename this class so it properly describes what's doing under the hood.

I agree. Do you think that ArrayWithUpdateHooks is appropriate?

What about ArrayWithGlobalCacheCollection? Not sure which one is better tbh

kamilmysliwiec · 2022-06-14T09:31:04Z

packages/graphql/lib/schema-builder/collections/array.collection.ts

+export class ArrayCollection<T> {
+  private array: T[] = [];
+
+  constructor(private globalArray: Array<T>) {}


Suggested change

constructor(private globalArray: Array<T>) {}

constructor(private readonly globalArray: Array<T>) {}

kamilmysliwiec · 2022-06-14T09:31:12Z

packages/graphql/lib/schema-builder/collections/array.collection.ts

@@ -0,0 +1,35 @@
+export class ArrayCollection<T> {
+  private array: T[] = [];


Suggested change

private array: T[] = [];

private readonly array: T[] = [];

kamilmysliwiec · 2022-06-14T09:33:12Z

packages/graphql/lib/schema-builder/collections/field.directive.collection.ts

+import { MetadataListByNameCollection } from './metadata.list.by.name.collection';
+import { PropertyDirectiveMetadata } from '../metadata';
+
+export class FieldDirectiveCollection extends MetadataListByNameCollection<PropertyDirectiveMetadata> {


rename file to field-directive.collection.ts

kamilmysliwiec · 2022-06-14T09:33:30Z

packages/graphql/lib/schema-builder/collections/field.directive.collection.ts

+    if (this.sdls.has(value.sdl) && this.fieldNames.has(value.fieldName))
+      return;


Suggested change

if (this.sdls.has(value.sdl) && this.fieldNames.has(value.fieldName))

return;

if (this.sdls.has(value.sdl) && this.fieldNames.has(value.fieldName)) {

return;

}

style: for the sake of consistency

kamilmysliwiec · 2022-06-14T09:33:44Z

packages/graphql/lib/schema-builder/collections/field.directive.collection.ts

+
+    this.sdls.add(value.sdl);
+    this.fieldNames.add(value.fieldName);
+    this.globalArray && this.globalArray.push(value);


Suggested change

this.globalArray && this.globalArray.push(value);

this.globalArray?.push(value);

kamilmysliwiec · 2022-06-14T09:34:18Z

packages/graphql/lib/schema-builder/collections/metadata.list.by.name.collection.ts

@@ -0,0 +1,37 @@
+import { MetadataByNameCollection } from './metadata.by.name.collection';


rename file to metadata-list-by-name.collection.ts

kamilmysliwiec · 2022-06-14T09:34:26Z

packages/graphql/lib/schema-builder/collections/metadata.by.name.collection.ts

@@ -0,0 +1,26 @@
+export class MetadataByNameCollection<T> {
+  protected map = new Map<string, T>();


same https://github.com/nestjs/graphql/pull/2212/files#r896598659

kamilmysliwiec · 2022-06-14T09:34:53Z

packages/graphql/lib/schema-builder/collections/metadata.storage.collection.ts

+    this._objectType = val;
+    this.all.objectType.push(val);
+  }
+  get objectType() {


nit: missing blank lines between getters and setters

kamilmysliwiec · 2022-06-14T09:35:31Z

packages/graphql/tests/schema-builder/storages/type-metadata.storage.model.spec.ts

@@ -0,0 +1,150 @@
+import {


we should have a dedicated test file per collection (as we now have them - collection classes - in dedicated files as well)

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

rezoled · 2022-06-21T09:44:24Z

Fixed all comments, thanks!

rezoled · 2022-06-26T14:56:06Z

Hey @kamilmysliwiec, can we merge this?

rezoled · 2022-07-06T12:59:00Z

@kamilmysliwiec we are waiting on an update for this, if you can help us this would be great

fix: made type-metadata.storage.ts much faster

fd060a8

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

rezoled mentioned this pull request Jun 1, 2022

Using maps to save data in type-metadata.storage.ts would result in a giant performance boost on app startup #2206

Closed

1 task

roypeled added 2 commits June 1, 2022 18:09

fix: made type-metadata.storage.ts much faster

316d442

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

fix: made type-metadata.storage.ts much faster

5aaefdb

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

kamilmysliwiec reviewed Jun 2, 2022

View reviewed changes

fix: made type-metadata.storage.ts much faster

5b24aae

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

kamilmysliwiec reviewed Jun 3, 2022

View reviewed changes

fix: made type-metadata.storage.ts much faster

760f154

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

kamilmysliwiec reviewed Jun 14, 2022

View reviewed changes

roypeled added 2 commits June 14, 2022 13:45

fix: made type-metadata.storage.ts much faster

1589d6d

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

fix: made type-metadata.storage.ts much faster

f60ba1c

Changed the data modeling of type-metadata storage to store the data in maps instead of arrays. This results in a dramatic improvement of application startup time since many of the lookups for metadata are now in O(1) instead of O(n)

kamilmysliwiec added the enhancement label Jul 20, 2022

kamilmysliwiec merged commit 6cb8391 into nestjs:master Jul 20, 2022

kamilmysliwiec mentioned this pull request Aug 29, 2022

Regression in 10.0.19: Error: Cannot determine a GraphQL input type ("....") for the "...". Make sure your class is decorated with an appropriate decorator. at InputTypeFactory.create #2360

Closed

4 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix: made type-metadata.storage.ts much faster #2212

fix: made type-metadata.storage.ts much faster #2212

roypeled commented Jun 1, 2022 •

edited

roypeled commented Jun 1, 2022 •

edited

kamilmysliwiec commented Jun 1, 2022

roypeled commented Jun 1, 2022

roypeled commented Jun 1, 2022

kamilmysliwiec Jun 2, 2022

roypeled Jun 2, 2022

roypeled Jun 2, 2022

kamilmysliwiec Jun 3, 2022

roypeled Jun 3, 2022 •

edited

roypeled Jun 6, 2022

rezoled commented Jun 12, 2022

kamilmysliwiec Jun 14, 2022

rezoled Jun 14, 2022

kamilmysliwiec Jun 15, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

kamilmysliwiec Jun 14, 2022

rezoled commented Jun 21, 2022

rezoled commented Jun 26, 2022

rezoled commented Jul 6, 2022

		@@ -0,0 +1,15 @@
		export class ArrayCollection<T> extends Array<T> {

	constructor(private globalArray: Array<T>) {}
	constructor(private readonly globalArray: Array<T>) {}

		@@ -0,0 +1,35 @@
		export class ArrayCollection<T> {
		private array: T[] = [];

		if (this.sdls.has(value.sdl) && this.fieldNames.has(value.fieldName))
		return;

	this.globalArray && this.globalArray.push(value);
	this.globalArray?.push(value);

		@@ -0,0 +1,37 @@
		import { MetadataByNameCollection } from './metadata.by.name.collection';

		@@ -0,0 +1,26 @@
		export class MetadataByNameCollection<T> {
		protected map = new Map<string, T>();

fix: made type-metadata.storage.ts much faster #2212

fix: made type-metadata.storage.ts much faster #2212

Conversation

roypeled commented Jun 1, 2022 • edited

PR Checklist

PR Type

What is the current behavior?

What is the new behavior?

Does this PR introduce a breaking change?

Other information

roypeled commented Jun 1, 2022 • edited

kamilmysliwiec commented Jun 1, 2022

roypeled commented Jun 1, 2022

roypeled commented Jun 1, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

roypeled Jun 3, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

rezoled commented Jun 12, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

rezoled commented Jun 21, 2022

rezoled commented Jun 26, 2022

rezoled commented Jul 6, 2022

roypeled commented Jun 1, 2022 •

edited

roypeled commented Jun 1, 2022 •

edited

roypeled Jun 3, 2022 •

edited