Skip to content

Commit 3cb1537

Browse files
rbucktonrbuckton
committed
Improve performance of deduplication of sorted arrays
1 parent d9775cd commit 3cb1537

10 files changed

Lines changed: 98 additions & 66 deletions

File tree

‎src/compiler/checker.ts‎

Lines changed: 5 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -7341,24 +7341,12 @@ namespace ts {
73417341
unionIndex?: number;
73427342
}
73437343

7344+
function getTypeId(type: Type) {
7345+
return type.id;
7346+
}
7347+
73447348
function binarySearchTypes(types: Type[], type: Type): number {
7345-
let low = 0;
7346-
let high = types.length - 1;
7347-
const typeId = type.id;
7348-
while (low <= high) {
7349-
const middle = low + ((high - low) >> 1);
7350-
const id = types[middle].id;
7351-
if (id === typeId) {
7352-
return middle;
7353-
}
7354-
else if (id > typeId) {
7355-
high = middle - 1;
7356-
}
7357-
else {
7358-
low = middle + 1;
7359-
}
7360-
}
7361-
return ~low;
7349+
return binarySearch(types, type, getTypeId, compareValues);
73627350
}
73637351

73647352
function containsType(types: Type[], type: Type): boolean {

‎src/compiler/core.ts‎

Lines changed: 73 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -660,35 +660,77 @@ namespace ts {
660660
}
661661

662662
/**
663-
* Creates a new array with duplicate entries removed.
663+
* Deduplicates an array that has already been sorted.
664+
*/
665+
export function deduplicateSorted<T>(array: SortedReadonlyArray<T>, comparer: EqualityComparer<T> | Comparer<T>) {
666+
if (!array) return undefined;
667+
if (array.length === 0) return [];
668+
669+
let last = array[0];
670+
const deduplicated: T[] = [last];
671+
for (let i = 1; i < array.length; i++) {
672+
switch (comparer(last, array[i])) {
673+
// equality comparison
674+
case true:
675+
676+
// relational comparison
677+
case Comparison.LessThan:
678+
case Comparison.EqualTo:
679+
continue;
680+
}
681+
682+
deduplicated.push(last = array[i]);
683+
}
684+
685+
return deduplicated;
686+
}
687+
688+
/**
689+
* Deduplicates an unsorted array.
664690
* @param equalityComparer An optional `EqualityComparer` used to determine if two values are duplicates.
665691
* @param comparer An optional `Comparer` used to sort entries before comparison. If supplied,
666692
* results are returned in the original order found in `array`.
667693
*/
668-
export function deduplicate<T>(array: ReadonlyArray<T>, equalityComparer?: EqualityComparer<T>, comparer?: Comparer<T>): T[] {
669-
if (!array) return undefined;
670-
if (!comparer) return addRangeIfUnique([], array, equalityComparer);
671-
return deduplicateWorker(array, equalityComparer, comparer);
694+
export function deduplicate<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T>, comparer?: Comparer<T>): T[] {
695+
return !array ? undefined :
696+
array.length === 0 ? [] :
697+
array.length === 1 ? array.slice() :
698+
comparer ? deduplicateRelational(array, equalityComparer, comparer) :
699+
deduplicateEquality(array, equalityComparer);
672700
}
673701

674-
function deduplicateWorker<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T> = equateValues, comparer: Comparer<T>) {
702+
function deduplicateRelational<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T>, comparer: Comparer<T>) {
675703
// Perform a stable sort of the array. This ensures the first entry in a list of
676704
// duplicates remains the first entry in the result.
677705
const indices = sequence(0, array.length);
678706
stableSortIndices(array, indices, comparer);
679707

680-
const deduplicated: number[] = [];
681-
loop: for (const sourceIndex of indices) {
682-
for (const targetIndex of deduplicated) {
683-
if (equalityComparer(array[sourceIndex], array[targetIndex])) {
684-
continue loop;
685-
}
708+
let last = array[indices[0]];
709+
const deduplicated: number[] = [indices[0]];
710+
for (let i = 1; i < indices.length; i++) {
711+
const index = indices[i];
712+
const item = array[index];
713+
if (!equalityComparer(last, item)) {
714+
deduplicated.push(index);
715+
last = item;
686716
}
687-
deduplicated.push(sourceIndex);
688717
}
689718

690-
// return deduplicated items in original order
691-
return deduplicated.sort().map(i => array[i]);
719+
// restore original order
720+
deduplicated.sort();
721+
return deduplicated.map(i => array[i]);
722+
}
723+
724+
function deduplicateEquality<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T>) {
725+
const result: T[] = [];
726+
for (const item of array) {
727+
pushIfUnique(result, item, equalityComparer);
728+
}
729+
return result;
730+
}
731+
732+
export function sortAndDeduplicate<T>(array: ReadonlyArray<T>, comparer: Comparer<T>, equalityComparer?: EqualityComparer<T>) {
733+
return deduplicateSorted(sort(array, comparer), equalityComparer || comparer);
692734
}
693735

694736
export function arrayIsEqualTo<T>(array1: ReadonlyArray<T>, array2: ReadonlyArray<T>, equalityComparer: (a: T, b: T) => boolean = equateValues): boolean {
@@ -827,15 +869,6 @@ namespace ts {
827869
return to;
828870
}
829871

830-
function addRangeIfUnique<T>(to: T[], from: ReadonlyArray<T>, equalityComparer?: EqualityComparer<T>): T[] | undefined {
831-
for (let i = 0; i < from.length; i++) {
832-
if (from[i] !== undefined) {
833-
pushIfUnique(to, from[i], equalityComparer);
834-
}
835-
}
836-
return to;
837-
}
838-
839872
/**
840873
* @return Whether the value was added.
841874
*/
@@ -878,13 +911,20 @@ namespace ts {
878911
indices.sort((x, y) => comparer(array[x], array[y]) || compareValues(x, y));
879912
}
880913

914+
/**
915+
* Returns a new sorted array.
916+
*/
917+
export function sort<T>(array: ReadonlyArray<T>, comparer: Comparer<T>) {
918+
return array.slice().sort(comparer) as ReadonlyArray<T> as SortedReadonlyArray<T>;
919+
}
920+
881921
/**
882922
* Stable sort of an array. Elements equal to each other maintain their relative position in the array.
883923
*/
884924
export function stableSort<T>(array: ReadonlyArray<T>, comparer: Comparer<T>) {
885925
const indices = sequence(0, array.length);
886926
stableSortIndices(array, indices, comparer);
887-
return indices.map(i => array[i]);
927+
return indices.map(i => array[i]) as ReadonlyArray<T> as SortedReadonlyArray<T>;
888928
}
889929

890930
export function rangeEquals<T>(array1: ReadonlyArray<T>, array2: ReadonlyArray<T>, pos: number, end: number) {
@@ -969,25 +1009,22 @@ namespace ts {
9691009
* @param array A sorted array whose first element must be no larger than number
9701010
* @param number The value to be searched for in the array.
9711011
*/
972-
export function binarySearch<T>(array: ReadonlyArray<T>, value: T, comparer?: Comparer<T>, offset?: number): number {
1012+
export function binarySearch<T, U>(array: ReadonlyArray<T>, value: T, keySelector: Selector<T, U>, keyComparer: Comparer<U>, offset?: number): number {
9731013
if (!array || array.length === 0) {
9741014
return -1;
9751015
}
9761016

9771017
let low = offset || 0;
9781018
let high = array.length - 1;
979-
comparer = comparer !== undefined
980-
? comparer
981-
: (v1, v2) => (v1 < v2 ? -1 : (v1 > v2 ? 1 : 0));
982-
1019+
const key = keySelector(value);
9831020
while (low <= high) {
9841021
const middle = low + ((high - low) >> 1);
985-
const midValue = array[middle];
1022+
const midKey = keySelector(array[middle]);
9861023

987-
if (comparer(midValue, value) === 0) {
1024+
if (keyComparer(midKey, key) === 0) {
9881025
return middle;
9891026
}
990-
else if (comparer(midValue, value) > 0) {
1027+
else if (keyComparer(midKey, key) > 0) {
9911028
high = middle - 1;
9921029
}
9931030
else {
@@ -2452,8 +2489,8 @@ namespace ts {
24522489
return flatten<string>(results);
24532490

24542491
function visitDirectory(path: string, absolutePath: string, depth: number | undefined) {
2455-
let { files, directories } = getFileSystemEntries(path);
2456-
files = files.slice().sort(comparer);
2492+
const entries = getFileSystemEntries(path);
2493+
const files = sort(entries.files, comparer);
24572494

24582495
for (const current of files) {
24592496
const name = combinePaths(path, current);
@@ -2478,7 +2515,7 @@ namespace ts {
24782515
}
24792516
}
24802517

2481-
directories = directories.slice().sort(comparer);
2518+
const directories = sort(entries.directories, comparer);
24822519
for (const current of directories) {
24832520
const name = combinePaths(path, current);
24842521
const absoluteName = combinePaths(absolutePath, current);

‎src/compiler/scanner.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -352,7 +352,7 @@ namespace ts {
352352
* We assume the first line starts at position 0 and 'position' is non-negative.
353353
*/
354354
export function computeLineAndCharacterOfPosition(lineStarts: ReadonlyArray<number>, position: number): LineAndCharacter {
355-
let lineNumber = binarySearch(lineStarts, position);
355+
let lineNumber = binarySearch(lineStarts, position, identity, compareValues);
356356
if (lineNumber < 0) {
357357
// If the actual position was not found,
358358
// the binary search returns the 2's-complement of the next line start

‎src/compiler/tsc.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -306,7 +306,7 @@ namespace ts {
306306

307307
// Sort our options by their names, (e.g. "--noImplicitAny" comes before "--watch")
308308
const optsList = showAllOptions ?
309-
optionDeclarations.slice().sort((a, b) => compareStringsCaseInsensitive(a.name, b.name)) :
309+
sort(optionDeclarations, (a, b) => compareStringsCaseInsensitive(a.name, b.name)) :
310310
filter(optionDeclarations.slice(), v => v.showInSimplifiedHelpView);
311311

312312
// We want our descriptions to align at the same column in our output,

‎src/compiler/types.ts‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,11 @@ namespace ts {
3636
push(...values: T[]): void;
3737
}
3838

39+
/* @internal */
40+
export interface SortedReadonlyArray<T> extends ReadonlyArray<T> {
41+
" __sortedArrayBrand": any;
42+
}
43+
3944
/* @internal */
4045
export type EqualityComparer<T> = (a: T, b: T) => boolean;
4146

‎src/compiler/utilities.ts‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -321,16 +321,16 @@ namespace ts {
321321
return getSourceTextOfNodeFromSourceFile(getSourceFileOfNode(node), node, includeTrivia);
322322
}
323323

324+
function getPos(range: Node) {
325+
return range.pos;
326+
}
327+
324328
/**
325329
* Note: it is expected that the `nodeArray` and the `node` are within the same file.
326330
* For example, searching for a `SourceFile` in a `SourceFile[]` wouldn't work.
327331
*/
328332
export function indexOfNode(nodeArray: ReadonlyArray<Node>, node: Node) {
329-
return binarySearch(nodeArray, node, compareNodePos);
330-
}
331-
332-
function compareNodePos({ pos: aPos }: Node, { pos: bPos}: Node) {
333-
return aPos < bPos ? Comparison.LessThan : bPos < aPos ? Comparison.GreaterThan : Comparison.EqualTo;
333+
return binarySearch(nodeArray, node, getPos, compareValues);
334334
}
335335

336336
/**

‎src/harness/harness.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1313,7 +1313,7 @@ namespace Harness {
13131313
export const diagnosticSummaryMarker = "__diagnosticSummary";
13141314
export const globalErrorsMarker = "__globalErrors";
13151315
export function *iterateErrorBaseline(inputFiles: ReadonlyArray<TestFile>, diagnostics: ReadonlyArray<ts.Diagnostic>, pretty?: boolean): IterableIterator<[string, string, number]> {
1316-
diagnostics = diagnostics.slice().sort(ts.compareDiagnostics);
1316+
diagnostics = ts.sort(diagnostics, ts.compareDiagnostics);
13171317
let outputLines = "";
13181318
// Count up all errors that were found in files other than lib.d.ts so we don't miss any
13191319
let totalErrorsReportedInNonLibraryFiles = 0;

‎src/server/editorServices.ts‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -203,8 +203,10 @@ namespace ts.server {
203203
* This helper function processes a list of projects and return the concatenated, sortd and deduplicated output of processing each project.
204204
*/
205205
export function combineProjectOutput<T>(projects: ReadonlyArray<Project>, action: (project: Project) => ReadonlyArray<T>, comparer?: (a: T, b: T) => number, areEqual?: (a: T, b: T) => boolean) {
206-
const result = flatMap(projects, action).sort(comparer);
207-
return projects.length > 1 ? deduplicate(result, areEqual) : result;
206+
const outputs = flatMap(projects, action);
207+
return comparer
208+
? sortAndDeduplicate(outputs, comparer, areEqual)
209+
: deduplicate(outputs, areEqual);
208210
}
209211

210212
export interface HostConfiguration {

‎src/server/utilities.ts‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -250,7 +250,7 @@ namespace ts.server {
250250
return;
251251
}
252252

253-
const insertIndex = binarySearch(array, insert, compare);
253+
const insertIndex = binarySearch(array, insert, identity, compare);
254254
if (insertIndex < 0) {
255255
array.splice(~insertIndex, 0, insert);
256256
}
@@ -266,7 +266,7 @@ namespace ts.server {
266266
return;
267267
}
268268

269-
const removeIndex = binarySearch(array, remove, compare);
269+
const removeIndex = binarySearch(array, remove, identity, compare);
270270
if (removeIndex >= 0) {
271271
array.splice(removeIndex, 1);
272272
}

‎src/services/textChanges.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -581,7 +581,7 @@ namespace ts.textChanges {
581581
return applyFormatting(nonformattedText, sourceFile, initialIndentation, delta, this.rulesProvider);
582582
}
583583

584-
private static normalize(changes: Change[]): Change[] {
584+
private static normalize(changes: Change[]) {
585585
// order changes by start position
586586
const normalized = stableSort(changes, (a, b) => a.range.pos - b.range.pos);
587587
// verify that change intervals do not overlap, except possibly at end points.

0 commit comments

Comments
 (0)