X Tutup
Skip to content

O(n²) performance issue in delta rename detection #2030

@anuragts

Description

@anuragts

The calculateDelta method in packages/cli/src/cli/utils/delta.ts uses a nested loop to detect renamed keys - for each
added key, it linearly scans ALL removed keys to find a matching content hash.

With large projects this scales quadratically:

  • 100 renames → 10,000 comparisons
  • 1,000 renames → 1,000,000 comparisons
  • 5,000 renames → 25,000,000 comparisons

The loop at lines 62-70:

for (const addedKey of added) {
  const addedHash = md5(params.sourceData[addedKey]);
  for (const removedKey of removed) {
    if (params.checksums[removedKey] === addedHash) {
      renamed.push([removedKey, addedKey]);
      break;
    }
  }
}

This could be replaced with a Map<hash, removedKey> pre-built from the removed keys, turning each lookup from O(n) to
O(1). Overall complexity drops from O(n×m) to O(n+m).

This affects any project that renames a large number of translation keys at once (e.g. refactoring key naming
conventions).

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

      X Tutup