Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

deepStrictEqual bad performance on larger dataset #57242

Closed
Rymar opened this issue Feb 28, 2025 · 1 comment · Fixed by #57279
Closed

deepStrictEqual bad performance on larger dataset #57242

Rymar opened this issue Feb 28, 2025 · 1 comment · Fixed by #57279

Comments

@Rymar
Copy link

Rymar commented Feb 28, 2025 •
edited
Loading

Version

22.12.0+

Platform

Darwin 24.3.0 Darwin Kernel Version 24.3.0: Thu Jan  2 20:24:24 PST 2025; root:xnu-11215.81.4~3/RELEASE_ARM64_T6030 arm64

Subsystem

assert

What steps will reproduce the bug?

Comparing large objects with deepStrictEqual is slow and got worse after version 22.11. Version 22.12.0 is ~3x slower and 22.14.0 is ~8x slower. The bigger the object the time increases expotentially. The same goes with memory, bigger objects easily exceed 4 GB memory.

// test.mjs
import { deepStrictEqual } from 'node:assert/strict';

try {
  performance.mark('start');
  const value = {
    _media_v: {
      name: '_media_v',
      columns: {
        id: { name: 'id', type: 'serial', primaryKey: true },
        parent: {
          name: 'parent_id',
          type: 'integer',
          reference: { name: 'id', onDelete: 'set null', table: 'media' },
        },
        version_name: { name: 'version_name', type: 'varchar' },
        version_processed: { name: 'version_processed', type: 'boolean' },
        version_updatedAt: {
          name: 'version_updated_at',
          type: 'timestamp',
          mode: 'string',
          precision: 3,
          withTimezone: true,
        },
        version_createdAt: {
          name: 'version_created_at',
          type: 'timestamp',
          mode: 'string',
          precision: 3,
          withTimezone: true,
        },
        version__status: {
          name: 'version__status',
          type: 'enum',
          enumName: 'enum__media_v_version_status',
          options: ['draft', 'published'],
          default: 'draft',
        },
        version_url: { name: 'version_url', type: 'varchar' },
        version_thumbnailURL: {
          name: 'version_thumbnail_u_r_l',
          type: 'varchar',
        },
        version_filename: { name: 'version_filename', type: 'varchar' },
        version_mimeType: { name: 'version_mime_type', type: 'varchar' },
        version_filesize: { name: 'version_filesize', type: 'numeric' },
        version_width: { name: 'version_width', type: 'numeric' },
        version_height: { name: 'version_height', type: 'numeric' },
        version_focalX: { name: 'version_focal_x', type: 'numeric' },
        version_focalY: { name: 'version_focal_y', type: 'numeric' },
        'version_sizes_128-webp_url': {
          name: 'version_sizes_128_webp_url',
          type: 'varchar',
        },
        'version_sizes_128-webp_width': {
          name: 'version_sizes_128_webp_width',
          type: 'numeric',
        },
        'version_sizes_128-webp_height': {
          name: 'version_sizes_128_webp_height',
          type: 'numeric',
        },
        'version_sizes_128-webp_mimeType': {
          name: 'version_sizes_128_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_128-webp_filesize': {
          name: 'version_sizes_128_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_128-webp_filename': {
          name: 'version_sizes_128_webp_filename',
          type: 'varchar',
        },
        'version_sizes_256-webp_url': {
          name: 'version_sizes_256_webp_url',
          type: 'varchar',
        },
        'version_sizes_256-webp_width': {
          name: 'version_sizes_256_webp_width',
          type: 'numeric',
        },
        'version_sizes_256-webp_height': {
          name: 'version_sizes_256_webp_height',
          type: 'numeric',
        },
        'version_sizes_256-webp_mimeType': {
          name: 'version_sizes_256_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_256-webp_filesize': {
          name: 'version_sizes_256_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_256-webp_filename': {
          name: 'version_sizes_256_webp_filename',
          type: 'varchar',
        },
        'version_sizes_384-webp_url': {
          name: 'version_sizes_384_webp_url',
          type: 'varchar',
        },
        'version_sizes_384-webp_width': {
          name: 'version_sizes_384_webp_width',
          type: 'numeric',
        },
        'version_sizes_384-webp_height': {
          name: 'version_sizes_384_webp_height',
          type: 'numeric',
        },
        'version_sizes_384-webp_mimeType': {
          name: 'version_sizes_384_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_384-webp_filesize': {
          name: 'version_sizes_384_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_384-webp_filename': {
          name: 'version_sizes_384_webp_filename',
          type: 'varchar',
        },
        'version_sizes_640-webp_url': {
          name: 'version_sizes_640_webp_url',
          type: 'varchar',
        },
        'version_sizes_640-webp_width': {
          name: 'version_sizes_640_webp_width',
          type: 'numeric',
        },
        'version_sizes_640-webp_height': {
          name: 'version_sizes_640_webp_height',
          type: 'numeric',
        },
        'version_sizes_640-webp_mimeType': {
          name: 'version_sizes_640_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_640-webp_filesize': {
          name: 'version_sizes_640_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_640-webp_filename': {
          name: 'version_sizes_640_webp_filename',
          type: 'varchar',
        },
        'version_sizes_1080-webp_url': {
          name: 'version_sizes_1080_webp_url',
          type: 'varchar',
        },
        'version_sizes_1080-webp_width': {
          name: 'version_sizes_1080_webp_width',
          type: 'numeric',
        },
        'version_sizes_1080-webp_height': {
          name: 'version_sizes_1080_webp_height',
          type: 'numeric',
        },
        'version_sizes_1080-webp_mimeType': {
          name: 'version_sizes_1080_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_1080-webp_filesize': {
          name: 'version_sizes_1080_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_1080-webp_filename': {
          name: 'version_sizes_1080_webp_filename',
          type: 'varchar',
        },
        'version_sizes_1440-webp_url': {
          name: 'version_sizes_1440_webp_url',
          type: 'varchar',
        },
        'version_sizes_1440-webp_width': {
          name: 'version_sizes_1440_webp_width',
          type: 'numeric',
        },
        'version_sizes_1440-webp_height': {
          name: 'version_sizes_1440_webp_height',
          type: 'numeric',
        },
        'version_sizes_1440-webp_mimeType': {
          name: 'version_sizes_1440_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_1440-webp_filesize': {
          name: 'version_sizes_1440_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_1440-webp_filename': {
          name: 'version_sizes_1440_webp_filename',
          type: 'varchar',
        },
        'version_sizes_1920-webp_url': {
          name: 'version_sizes_1920_webp_url',
          type: 'varchar',
        },
        'version_sizes_1920-webp_width': {
          name: 'version_sizes_1920_webp_width',
          type: 'numeric',
        },
        'version_sizes_1920-webp_height': {
          name: 'version_sizes_1920_webp_height',
          type: 'numeric',
        },
        'version_sizes_1920-webp_mimeType': {
          name: 'version_sizes_1920_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_1920-webp_filesize': {
          name: 'version_sizes_1920_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_1920-webp_filename': {
          name: 'version_sizes_1920_webp_filename',
          type: 'varchar',
        },
        'version_sizes_2560-webp_url': {
          name: 'version_sizes_2560_webp_url',
          type: 'varchar',
        },
        'version_sizes_2560-webp_width': {
          name: 'version_sizes_2560_webp_width',
          type: 'numeric',
        },
        'version_sizes_2560-webp_height': {
          name: 'version_sizes_2560_webp_height',
          type: 'numeric',
        },
        'version_sizes_2560-webp_mimeType': {
          name: 'version_sizes_2560_webp_mime_type',
          type: 'varchar',
        },
        'version_sizes_2560-webp_filesize': {
          name: 'version_sizes_2560_webp_filesize',
          type: 'numeric',
        },
        'version_sizes_2560-webp_filename': {
          name: 'version_sizes_2560_webp_filename',
          type: 'varchar',
        },
        version_sizes_admin_url: {
          name: 'version_sizes_admin_url',
          type: 'varchar',
        },
        version_sizes_admin_width: {
          name: 'version_sizes_admin_width',
          type: 'numeric',
        },
        version_sizes_admin_height: {
          name: 'version_sizes_admin_height',
          type: 'numeric',
        },
        version_sizes_admin_mimeType: {
          name: 'version_sizes_admin_mime_type',
          type: 'varchar',
        },
        version_sizes_admin_filesize: {
          name: 'version_sizes_admin_filesize',
          type: 'numeric',
        },
        version_sizes_admin_filename: {
          name: 'version_sizes_admin_filename',
          type: 'varchar',
        },
        version_sizes_fallback_url: {
          name: 'version_sizes_fallback_url',
          type: 'varchar',
        },
        version_sizes_fallback_width: {
          name: 'version_sizes_fallback_width',
          type: 'numeric',
        },
        version_sizes_fallback_height: {
          name: 'version_sizes_fallback_height',
          type: 'numeric',
        },
        version_sizes_fallback_mimeType: {
          name: 'version_sizes_fallback_mime_type',
          type: 'varchar',
        },
        version_sizes_fallback_filesize: {
          name: 'version_sizes_fallback_filesize',
          type: 'numeric',
        },
        version_sizes_fallback_filename: {
          name: 'version_sizes_fallback_filename',
          type: 'varchar',
        },
        createdAt: {
          name: 'created_at',
          type: 'timestamp',
          defaultNow: true,
          mode: 'string',
          notNull: true,
          precision: 3,
          withTimezone: true,
        },
        updatedAt: {
          name: 'updated_at',
          type: 'timestamp',
          defaultNow: true,
          mode: 'string',
          notNull: true,
          precision: 3,
          withTimezone: true,
        },
        snapshot: { name: 'snapshot', type: 'boolean' },
        publishedLocale: {
          name: 'published_locale',
          type: 'enum',
          enumName: 'enum__media_v_published_locale',
          options: ['sv'],
        },
        latest: { name: 'latest', type: 'boolean' },
      },
      foreignKeys: {},
      indexes: {
        _media_v_parent_idx: {
          name: '_media_v_parent_idx',
          on: 'parent',
          unique: false,
        },
        _media_v_version_version_updated_at_idx: {
          name: '_media_v_version_version_updated_at_idx',
          on: 'version_updatedAt',
          unique: false,
        },
        _media_v_version_version_created_at_idx: {
          name: '_media_v_version_version_created_at_idx',
          on: 'version_createdAt',
          unique: false,
        },
        _media_v_version_version__status_idx: {
          name: '_media_v_version_version__status_idx',
          on: 'version__status',
          unique: false,
        },
        _media_v_version_version_filename_idx: {
          name: '_media_v_version_version_filename_idx',
          on: 'version_filename',
          unique: false,
        },
        _media_v_version_sizes_128_webp_version_sizes_128_webp_filename_idx: {
          name: '_media_v_version_sizes_128_webp_version_sizes_128_webp_filename_idx',
          on: 'version_sizes_128-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_256_webp_version_sizes_256_webp_filename_idx: {
          name: '_media_v_version_sizes_256_webp_version_sizes_256_webp_filename_idx',
          on: 'version_sizes_256-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_384_webp_version_sizes_384_webp_filename_idx: {
          name: '_media_v_version_sizes_384_webp_version_sizes_384_webp_filename_idx',
          on: 'version_sizes_384-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_640_webp_version_sizes_640_webp_filename_idx: {
          name: '_media_v_version_sizes_640_webp_version_sizes_640_webp_filename_idx',
          on: 'version_sizes_640-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_1080_webp_version_sizes_1080_webp_filename_idx: {
          name: '_media_v_version_sizes_1080_webp_version_sizes_1080_webp_filename_idx',
          on: 'version_sizes_1080-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_1440_webp_version_sizes_1440_webp_filename_idx: {
          name: '_media_v_version_sizes_1440_webp_version_sizes_1440_webp_filename_idx',
          on: 'version_sizes_1440-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_1920_webp_version_sizes_1920_webp_filename_idx: {
          name: '_media_v_version_sizes_1920_webp_version_sizes_1920_webp_filename_idx',
          on: 'version_sizes_1920-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_2560_webp_version_sizes_2560_webp_filename_idx: {
          name: '_media_v_version_sizes_2560_webp_version_sizes_2560_webp_filename_idx',
          on: 'version_sizes_2560-webp_filename',
          unique: false,
        },
        _media_v_version_sizes_admin_version_sizes_admin_filename_idx: {
          name: '_media_v_version_sizes_admin_version_sizes_admin_filename_idx',
          on: 'version_sizes_admin_filename',
          unique: false,
        },
        _media_v_version_sizes_fallback_version_sizes_fallback_filename_idx: {
          name: '_media_v_version_sizes_fallback_version_sizes_fallback_filename_idx',
          on: 'version_sizes_fallback_filename',
          unique: false,
        },
        _media_v_created_at_idx: {
          name: '_media_v_created_at_idx',
          on: 'createdAt',
          unique: false,
        },
        _media_v_updated_at_idx: {
          name: '_media_v_updated_at_idx',
          on: 'updatedAt',
          unique: false,
        },
        _media_v_snapshot_idx: {
          name: '_media_v_snapshot_idx',
          on: 'snapshot',
          unique: false,
        },
        _media_v_published_locale_idx: {
          name: '_media_v_published_locale_idx',
          on: 'publishedLocale',
          unique: false,
        },
        _media_v_latest_idx: {
          name: '_media_v_latest_idx',
          on: 'latest',
          unique: false,
        },
      },
    },
  };
  performance.mark('end');
  deepStrictEqual(value, {});
} catch {
  performance.mark('end');
  console.log(performance.measure('execution', 'start', 'end').duration);
}
> nvm use 22.11.0
> node test.mjs
1.9205410000000018
> nvm use 22.12.0
> node test.mjs
6.423708000000001
> nvm use 22.14.0
> node test.mjs
17.266084000000003

How often does it reproduce? Is there a required condition?

It gets noticeable on larger objects when scripts get out of memory. It happens only for versions >=22.12.0.

What is the expected behavior? Why is that the expected behavior?

Should work at least or better than 22.11.0 version.

What do you see instead?

Longer execution time and larger memory consumption.
@BridgeAR
Copy link
Member

It seems like it's actually the error creation that is now slower. This is definitely the case with Myers being in place instead of the linear algorithm being used before.
I guess there is room for more shortcuts in the current algorithm. Especially due to the shape of the input being so drastically different.

puskin94 added a commit to puskin94/node that referenced this issue Mar 2, 2025
@puskin94
assert: improve myers diff performance

Verified

This commit was signed with the committer’s verified signature.
IkumaTadokoro ikuma-t
SSH Key Fingerprint: v79/GQ8zewonDd5a8VwYuEE1fWdxVM6lrtr5AHogajk
Verified
Learn about vigilant mode
c6f4f0b 
fix: nodejs#57242
@puskin94 puskin94 mentioned this issue Mar 2, 2025
Merged
puskin94 added a commit to puskin94/node that referenced this issue Mar 3, 2025
@puskin94
assert: improve myers diff performance
3a76c93 
fix: nodejs#57242
nodejs-github-bot pushed a commit that referenced this issue Mar 6, 2025
@puskin94
assert: improve myers diff performance
Loading
Loading status checks…
395439b 
fix: #57242
PR-URL: #57279
Fixes: #57242
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>
Reviewed-By: LiviaMedeiros <livia@cirno.name>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

assert: improve myers diff performance puskin94/node
2 participants
@Rymar @BridgeAR