Optimize paths comparision in source closure sorting.

pkg/analyzer/lib/src/summary/incremental_cache.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import 'dart:convert';
 import 'dart:core' hide Resource;
 
 import 'package:analyzer/dart/element/element.dart';
 import 'package:analyzer/file_system/file_system.dart';
 import 'package:analyzer/src/generated/engine.dart';
 import 'package:analyzer/src/generated/error.dart';
 import 'package:analyzer/src/generated/source.dart';
 import 'package:analyzer/src/summary/format.dart';
 import 'package:analyzer/src/summary/idl.dart';
 import 'package:analyzer/src/summary/summarize_elements.dart';
 import 'package:convert/convert.dart';
 import 'package:crypto/crypto.dart';
 
 /**
  * The version of the incremental cache.  It should be incremented every time
  * when any cache data structure is changed.
  */
 const int _VERSION = 1;
 
 /**
+ * Compare the given file paths [a] and [b].  Because paths usually have long
+ * equal prefix, comparison is done not as comparision of two generic [String]s.
+ * Instead it starts from the ends of each strings.
+ *
+ * Return `-1` if [a] is ordered before [b], `1` if `this` is ordered after [b],
+ * and zero if [a] and [b] are ordered together.
+ */
+int comparePaths(String a, String b) {
+  int thisLength = a.length;
+  int otherLength = b.length;
+  int len = (thisLength < otherLength) ? thisLength : otherLength;
+  for (int i = 0; i < len; i++) {
+    int thisCodeUnit = a.codeUnitAt(thisLength - 1 - i);
+    int otherCodeUnit = b.codeUnitAt(otherLength - 1 - i);
+    if (thisCodeUnit < otherCodeUnit) {
+      return -1;
+    }
+    if (thisCodeUnit > otherCodeUnit) {
+      return 1;
+    }
+  }
+  if (thisLength < otherLength) {

[Brian Wilkerson, 2016/06/10 21:19:12]

Couldn't these length tests come before the character comparisons (before the
'for')?

[Brian Wilkerson, 2016/06/10 21:20:11]

Nevermind, I realized why not as I clicked "send".

+    return -1;
+  }
+  if (thisLength > otherLength) {
+    return 1;
+  }
+  return 0;
+}
+
+/**
  * Storage for cache data.
  */
 abstract class CacheStorage {
   /**
    * Return bytes for the given [key], `null` if [key] is not in the storage.
    */
   List<int> get(String key);
 
   /**
    * Associate the [key] with the given [bytes].
@@ skipping 370 matching lines @@
   /**
    * Return the whole source closure of the library with the given
    * [librarySource]. It includes defining units and parts of the library and
    * of all its directly or indirectly imported or exported libraries.
    */
   List<Source> _getLibraryClosure(Source librarySource) {
     return _libraryClosureMap.putIfAbsent(librarySource, () {
       Set<Source> closureSet = new Set<Source>();
       _appendLibraryClosure(closureSet, librarySource);
       List<Source> closureList = closureSet.toList();
-      closureList.sort((a, b) => a.fullName.compareTo(b.fullName));
+      closureList.sort((a, b) => comparePaths(a.fullName, b.fullName));
       return closureList;
     });
   }
 
   /**
    * Return the [context]-specific hash of the closure of the library with
    * the given [librarySource].
    */
   List<int> _getLibraryClosureHash(Source librarySource) {
     return _libraryClosureHashMap.putIfAbsent(librarySource, () {
@@ skipping 136 matching lines @@
    */
   final String id;
 
   /**
    * The payload bundle.
    */
   final PackageBundle bundle;
 
   LibraryBundleWithId(this.source, this.id, this.bundle);
 }