isCircular() cause performance issues about class-transformer HOT 12 CLOSED

Thank you guys very much for your hard work. Released in 0.1.7

from class-transformer.

Ping... please review my Pull Request. Thanks!

from class-transformer.

@pleerock can you please review my pull request? Thanks!

from class-transformer.

@sheiidan thank you for such detailed exploration of this issue and sorry for my quite delayed answer. Im very busy with other libs and this lib is taking less priority and less of my time.

What you are describing is quite serious. Having a flag seems like its fixing this issue - but only for those who know about this issue. So, probably better fix for this issue would be if we figure out why this is happening in isCircular method. From the code it looks simple:

    private isCircular(object: Object, level: number) {
        return !!this.transformedTypes.find(transformed => transformed.object === object && transformed.level < level);
    }

so the question is: how such a small peace of code with simple find operation can bring such huge performance issues?

from class-transformer.

@pleerock, the problem is that isCircular() is being called too many times during the operation (in my case it's 9 times for each object), so we left with a simple math:
isCircular() takes ~0.08ms to run.
for 10K objects, isCircular() is being called 90K times.
0.08ms * 90000 = 7.2 seconds

This is my model:

export class Person {
    @Type(() => Date)
    public birthDate: Date;
    public name: string;
    @Type(() => Number)
    public grades: number[];
}

And this is my code that creates 10K objects:

        let p: Person = {
            birthDate: new Date(1999, 2, 12),
            name: "Jon Doe",
            grades: [20, 90, 56, 67, 85]
        };
        this.arr = [];
        for (let i = 0; i < 10000; i++) {
            this.arr.push(_.cloneDeep(p));
        }
```TS

from class-transformer.

The issue is that the find method will iterate through the entire transformedTypes array each time isCircular is called. isCircular is called every time a record is added to the transformed object, and every object that has been previously transformed is included in transformedTypes (as well as nested objects), so the best case performance would be around (n/2)^2. So, for a collection of 10,000 items, the anonymous method called in the find method will be executed 50,000,000 times.

Long story short, transformedTypes should be changed to a dictionary. The skipCircularCheck option seems reasonable, especially since the most common use case for classTransformer is probably for deserializing data, where it is not necessary. If that option is added, I would suggest not bothering to populate transformedTypes (or transformedTypesDictionary/hashtable/whatever). Regardless, the isCircular performance issue should be tackled as well.

from class-transformer.

I think best if we change transformedTypes to dictionary as @JarvisJ suggested and instead of skipCircularCheck we do enableCircularCheck which will be false by default to prevent such issue for all users. Or maybe even better we simply return circular check at all if it cause such bad performance issues it becomes bottleneck. What do you think?

from class-transformer.

@pleerock , I updated the pull request to enableCircularCheck option and now circular check is turned off by default. Regarding, changing transformedTypes to dictionary, I'm not sure it will improve performance dramatically (improve it from worse to bad is still bad...), and in addition, transformTypes is now defined as:

private transformedTypes: { level: number, object: Object }[] = [];

and being used in isCircular:

    private isCircular(object: Object, level: number) {
        return !!this.transformedTypes.find(transformed => transformed.object === object && transformed.level < level);
    }

so how do you suggest change it to dictionary?

from class-transformer.

You should see a dramatic improvement by converting transformedTypes to a Map or WeakMap. If isCircular was being executed 90k times on a collection of 10k items, then this block of code:
transformed.object === object && transformed.level < level
was being executed at least 450,000,000 times. Changing it to a O(1) operation will reduce that number to 90,000 times. So, an operation that was taking 5.8s, could be reduced to a few milliseconds.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakMap
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

isCircular would need to be modified to something like:

private isCircular(object: Object, level: number) { var transformed = this.transformedTypesMap.get(object); return transformed.level < level; }
and the code to load the transformedTypes collection would need to change from:

this.transformedTypes.push({ level: level, object: value });
to
this.transformedTypesMap.set(value, { level: level, object: value })

I must admit to not having a ton of experience with these native ES6 objects, nor am I too familiar with this codebase, so the above code may need to be tweaked.

from class-transformer.

@JarvisJ you're correct, thanks for the advice. I changed the pull request to use Map and it improves the performance.

from class-transformer.

@pleerock can ypu please review my PR? thanks

from class-transformer.

This issue has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.

from class-transformer.