diff --git a/pkg/analysis_server/lib/src/analysis_server.dart b/pkg/analysis_server/lib/src/analysis_server.dart
index 77a5aad..4989c15 100644
--- a/pkg/analysis_server/lib/src/analysis_server.dart
+++ b/pkg/analysis_server/lib/src/analysis_server.dart
@@ -18,10 +18,10 @@
 import 'package:analysis_server/src/services/correction/namespace.dart';
 import 'package:analysis_server/src/services/index/index.dart';
 import 'package:analysis_server/src/services/search/search_engine.dart';
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
 import 'package:analyzer/file_system/file_system.dart';
 import 'package:analyzer/instrumentation/instrumentation.dart';
 import 'package:analyzer/plugin/plugin.dart';
-import 'package:analyzer/source/package_map_provider.dart';
 import 'package:analyzer/src/generated/ast.dart';
 import 'package:analyzer/src/generated/element.dart';
 import 'package:analyzer/src/generated/engine.dart';
@@ -249,7 +249,7 @@
    * running a full analysis server.
    */
   AnalysisServer(this.channel, this.resourceProvider,
-      PackageMapProvider packageMapProvider, Index _index,
+      OptimizingPubPackageMapProvider packageMapProvider, Index _index,
       AnalysisServerOptions analysisServerOptions, this.defaultSdk,
       this.instrumentationService, {this.rethrowExceptions: true})
       : index = _index,
@@ -1161,7 +1161,8 @@
     Set<AnalysisContext> contexts = new HashSet<AnalysisContext>();
     resources.forEach((Resource resource) {
       if (resource is Folder) {
-        contexts.addAll(contextDirectoryManager.contextsInAnalysisRoot(resource));
+        contexts
+            .addAll(contextDirectoryManager.contextsInAnalysisRoot(resource));
       }
     });
     return contexts;
@@ -1299,7 +1300,8 @@
   StreamController<ContextsChangedEvent> _onContextsChangedController;
 
   ServerContextManager(this.analysisServer, ResourceProvider resourceProvider,
-      PackageMapProvider packageMapProvider, InstrumentationService service)
+      OptimizingPubPackageMapProvider packageMapProvider,
+      InstrumentationService service)
       : super(resourceProvider, packageMapProvider, service) {
     _onContextsChangedController =
         new StreamController<ContextsChangedEvent>.broadcast();
diff --git a/pkg/analysis_server/lib/src/context_manager.dart b/pkg/analysis_server/lib/src/context_manager.dart
index b52f6ad..bd3dc86 100644
--- a/pkg/analysis_server/lib/src/context_manager.dart
+++ b/pkg/analysis_server/lib/src/context_manager.dart
@@ -8,9 +8,9 @@
 import 'dart:collection';
 
 import 'package:analysis_server/src/analysis_server.dart';
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
 import 'package:analyzer/file_system/file_system.dart';
 import 'package:analyzer/instrumentation/instrumentation.dart';
-import 'package:analyzer/source/package_map_provider.dart';
 import 'package:analyzer/source/package_map_resolver.dart';
 import 'package:analyzer/src/generated/engine.dart';
 import 'package:analyzer/src/generated/java_io.dart';
@@ -82,7 +82,7 @@
    * Provider which is used to determine the mapping from package name to
    * package folder.
    */
-  final PackageMapProvider _packageMapProvider;
+  final OptimizingPubPackageMapProvider _packageMapProvider;
 
   /**
    * The instrumentation service used to report instrumentation data.
@@ -137,6 +137,20 @@
   }
 
   /**
+   * Return a list containing all of the contexts contained in the given
+   * [analysisRoot].
+   */
+  List<AnalysisContext> contextsInAnalysisRoot(Folder analysisRoot) {
+    List<AnalysisContext> contexts = <AnalysisContext>[];
+    _contexts.forEach((Folder contextFolder, _ContextInfo info) {
+      if (analysisRoot.isOrContains(contextFolder.path)) {
+        contexts.add(info.context);
+      }
+    });
+    return contexts;
+  }
+
+  /**
    * We have finished computing the package map.
    */
   void endComputePackageMap() {
@@ -163,20 +177,6 @@
   }
 
   /**
-   * Return a list containing all of the contexts contained in the given
-   * [analysisRoot].
-   */
-  List<AnalysisContext> contextsInAnalysisRoot(Folder analysisRoot) {
-    List<AnalysisContext> contexts = <AnalysisContext>[];
-    _contexts.forEach((Folder contextFolder, _ContextInfo info) {
-      if (analysisRoot.isOrContains(contextFolder.path)) {
-        contexts.add(info.context);
-      }
-    });
-    return contexts;
-  }
-
-  /**
    * Rebuild the set of contexts from scratch based on the data last sent to
    * setRoots(). Only contexts contained in the given list of analysis [roots]
    * will be rebuilt, unless the list is `null`, in which case every context
@@ -388,16 +388,17 @@
    */
   UriResolver _computePackageUriResolver(Folder folder, _ContextInfo info) {
     if (info.packageRoot != null) {
-      info.packageMapDependencies = new Set<String>();
+      info.packageMapInfo = null;
       return new PackageUriResolver([new JavaFile(info.packageRoot)]);
     } else {
       beginComputePackageMap();
-      PackageMapInfo packageMapInfo;
+      OptimizingPubPackageMapInfo packageMapInfo;
       ServerPerformanceStatistics.pub.makeCurrentWhile(() {
-        packageMapInfo = _packageMapProvider.computePackageMap(folder);
+        packageMapInfo =
+            _packageMapProvider.computePackageMap(folder, info.packageMapInfo);
       });
       endComputePackageMap();
-      info.packageMapDependencies = packageMapInfo.dependencies;
+      info.packageMapInfo = packageMapInfo;
       if (packageMapInfo.packageMap == null) {
         return null;
       }
@@ -594,7 +595,8 @@
         break;
     }
 
-    if (info.packageMapDependencies.contains(path)) {
+    if (info.packageMapInfo != null &&
+        info.packageMapInfo.isChangedDependency(path, resourceProvider)) {
       _recomputePackageUriResolver(info);
     }
   }
@@ -744,10 +746,11 @@
   Map<String, Source> sources = new HashMap<String, Source>();
 
   /**
-   * Dependencies of the context's package map.
-   * If any of these files changes, the package map needs to be recomputed.
+   * Info returned by the last call to
+   * [OptimizingPubPackageMapProvider.computePackageMap], or `null` if the
+   * package map hasn't been computed for this context yet.
    */
-  Set<String> packageMapDependencies;
+  OptimizingPubPackageMapInfo packageMapInfo;
 
   _ContextInfo(this.folder, File pubspecFile, this.children, this.packageRoot) {
     pubspecPath = pubspecFile.path;
diff --git a/pkg/analysis_server/lib/src/socket_server.dart b/pkg/analysis_server/lib/src/socket_server.dart
index e7ad5ac..16814af 100644
--- a/pkg/analysis_server/lib/src/socket_server.dart
+++ b/pkg/analysis_server/lib/src/socket_server.dart
@@ -10,10 +10,10 @@
 import 'package:analysis_server/src/protocol.dart';
 import 'package:analysis_server/src/services/index/index.dart';
 import 'package:analysis_server/src/services/index/local_file_index.dart';
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
 import 'package:analyzer/file_system/physical_file_system.dart';
 import 'package:analyzer/instrumentation/instrumentation.dart';
 import 'package:analyzer/plugin/plugin.dart';
-import 'package:analyzer/source/pub_package_map_provider.dart';
 import 'package:analyzer/src/generated/sdk_io.dart';
 
 /**
@@ -75,7 +75,7 @@
     }
 
     analysisServer = new AnalysisServer(serverChannel, resourceProvider,
-        new PubPackageMapProvider(resourceProvider, defaultSdk), index,
+        new OptimizingPubPackageMapProvider(resourceProvider, defaultSdk), index,
         analysisServerOptions, defaultSdk, instrumentationService,
         rethrowExceptions: false);
     _initializeHandlers(analysisServer);
diff --git a/pkg/analysis_server/lib/src/source/caching_pub_package_map_provider.dart b/pkg/analysis_server/lib/src/source/caching_pub_package_map_provider.dart
index e6d0d59..f6c9bb7 100644
--- a/pkg/analysis_server/lib/src/source/caching_pub_package_map_provider.dart
+++ b/pkg/analysis_server/lib/src/source/caching_pub_package_map_provider.dart
@@ -24,6 +24,9 @@
  * [PubPackageMapProvider] extension which caches pub list results.
  * These results are cached in memory and in a single place on disk that is
  * shared cross session and between different simultaneous sessions.
+ *
+ * TODO(paulberry): before this class is used again, it should be ported over
+ * to extend OptimizingPubPackageMapProvider instead of PubPackageMapProvider.
  */
 class CachingPubPackageMapProvider extends PubPackageMapProvider {
   static const cacheKey = 'pub_list_cache';
diff --git a/pkg/analysis_server/lib/src/source/optimizing_pub_package_map_provider.dart b/pkg/analysis_server/lib/src/source/optimizing_pub_package_map_provider.dart
new file mode 100644
index 0000000..ccda5f9
--- /dev/null
+++ b/pkg/analysis_server/lib/src/source/optimizing_pub_package_map_provider.dart
@@ -0,0 +1,134 @@
+// Copyright (c) 2015, 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.
+
+library source.optimizing_pub_package_map_provider;
+
+import 'package:analyzer/file_system/file_system.dart';
+import 'package:analyzer/source/package_map_provider.dart';
+import 'package:analyzer/source/pub_package_map_provider.dart';
+import 'package:analyzer/src/generated/sdk_io.dart';
+
+/**
+ * Extension of [PackageMapInfo] that tracks the modification timestamps of
+ * pub dependencies.  This allows the analysis server to avoid making redundant
+ * calls to "pub list" when nothing has changed.
+ */
+class OptimizingPubPackageMapInfo extends PackageMapInfo {
+  /**
+   * Map from file path to the file's modification timestamp prior to running
+   * "pub list".  Since the set of dependencies is not always known prior to
+   * running "pub list", some or all of the dependencies may be missing from
+   * this map.
+   */
+  final Map<String, int> modificationTimes;
+
+  OptimizingPubPackageMapInfo(Map<String, List<Folder>> packageMap,
+      Set<String> dependencies, this.modificationTimes)
+      : super(packageMap, dependencies);
+
+  /**
+   * Return `true` if the given [path] is listed as a dependency, and we cannot
+   * prove using modification timestamps that it is unchanged.
+   * [resourceProvider] is used (if necessary) to read the [path]'s
+   * modification time.
+   */
+  bool isChangedDependency(String path, ResourceProvider resourceProvider) {
+    if (!dependencies.contains(path)) {
+      // Path is not a dependency.
+      return false;
+    }
+    int lastModificationTime = modificationTimes[path];
+    if (lastModificationTime != null) {
+      Resource resource = resourceProvider.getResource(path);
+      if (resource is File) {
+        try {
+          if (resource.modificationStamp == lastModificationTime) {
+            // Path is a dependency, but it hasn't changed since the last run
+            // of "pub list".
+            return false;
+          }
+        } on FileSystemException {
+          // Path is a dependency, but we can't read its timestamp.  Assume
+          // it's changed to be safe.
+        }
+      }
+    }
+    // Path is a dependency, and we couldn't prove that it hadn't changed.
+    // Assume it's changed to be safe.
+    return true;
+  }
+}
+
+/**
+ * Extension of [PubPackageMapProvider] that outputs additional information to
+ * allow the analysis server to avoid making redundant calls to "pub list" when
+ * nothing has changed.
+ */
+class OptimizingPubPackageMapProvider extends PubPackageMapProvider {
+  OptimizingPubPackageMapProvider(
+      ResourceProvider resourceProvider, DirectoryBasedDartSdk sdk, [RunPubList runPubList])
+      : super(resourceProvider, sdk, runPubList);
+
+  /**
+   * Compute a package map for the given folder by executing "pub list".  If
+   * [previousInfo] is provided, it is used as a guess of which files the
+   * package map is likely to depend on; the modification times of those files
+   * are captured prior to executing "pub list" so that they can be used to
+   * avoid making redundant calls to "pub list" in the future.
+   *
+   * Also, in the case where dependencies can't be determined because of an
+   * error, the dependencies from [previousInfo] will be preserved.
+   */
+  OptimizingPubPackageMapInfo computePackageMap(Folder folder,
+      [OptimizingPubPackageMapInfo previousInfo]) {
+    // Prior to running "pub list", read the modification timestamps of all of
+    // the old dependencies (if known).
+    Map<String, int> modificationTimes = <String, int>{};
+    if (previousInfo != null) {
+      for (String path in previousInfo.dependencies) {
+        Resource resource = resourceProvider.getResource(path);
+        if (resource is File) {
+          try {
+            modificationTimes[path] = resource.modificationStamp;
+          } on FileSystemException {
+            // File no longer exists.  Don't record a timestamp for it; this
+            // will ensure that if the file reappears, we will re-run "pub
+            // list" regardless of the timestamp it reappears with.
+          }
+        }
+      }
+    }
+
+    // Try running "pub list".
+    PackageMapInfo info = super.computePackageMap(folder);
+    if (info == null) {
+      // Computing the package map resulted in an error.  Merge the old
+      // dependencies with the new ones, if possible.
+      info = super.computePackageMapError(folder);
+      if (previousInfo != null) {
+        info.dependencies.addAll(previousInfo.dependencies);
+      }
+    }
+
+    // Discard any elements of modificationTimes that are no longer
+    // dependencies.
+    if (previousInfo != null) {
+      for (String dependency
+          in previousInfo.dependencies.difference(info.dependencies)) {
+        modificationTimes.remove(dependency);
+      }
+    }
+
+    // Bundle the modificationTimes with the other info.
+    return new OptimizingPubPackageMapInfo(
+        info.packageMap, info.dependencies, modificationTimes);
+  }
+
+  @override
+  PackageMapInfo computePackageMapError(Folder folder) {
+    // Return null to indicate to our override of computePackageMap that there
+    // was an error, so it can compute dependencies correctly.
+    return null;
+  }
+}
diff --git a/pkg/analysis_server/test/context_manager_test.dart b/pkg/analysis_server/test/context_manager_test.dart
index 4a4ec36..2be5cb8 100644
--- a/pkg/analysis_server/test/context_manager_test.dart
+++ b/pkg/analysis_server/test/context_manager_test.dart
@@ -7,10 +7,10 @@
 import 'dart:collection';
 
 import 'package:analysis_server/src/context_manager.dart';
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
 import 'package:analyzer/file_system/file_system.dart';
 import 'package:analyzer/file_system/memory_file_system.dart';
 import 'package:analyzer/instrumentation/instrumentation.dart';
-import 'package:analyzer/source/package_map_provider.dart';
 import 'package:analyzer/source/package_map_resolver.dart';
 import 'package:analyzer/src/generated/engine.dart';
 import 'package:analyzer/src/generated/source.dart';
@@ -858,6 +858,42 @@
     });
   }
 
+  test_watch_modifyPackageMapDependency_redundantly() async {
+    // Create two dependency files
+    String dependencyPath1 = posix.join(projPath, 'dep1');
+    String dependencyPath2 = posix.join(projPath, 'dep2');
+    resourceProvider.newFile(dependencyPath1, 'contents');
+    resourceProvider.newFile(dependencyPath2, 'contents');
+    packageMapProvider.dependencies.add(dependencyPath1);
+    packageMapProvider.dependencies.add(dependencyPath2);
+    // Create a dart file
+    String dartFilePath = posix.join(projPath, 'main.dart');
+    resourceProvider.newFile(dartFilePath, 'contents');
+    // Verify that the created context has the expected empty package map.
+    manager.setRoots(<String>[projPath], <String>[], <String, String>{});
+    _checkPackageMap(projPath, isEmpty);
+    expect(packageMapProvider.computeCount, 1);
+    // Set up a different package map
+    String packagePath = '/package/foo';
+    resourceProvider.newFolder(packagePath);
+    packageMapProvider.packageMap = {'foo': projPath};
+    // Change both dependencies.
+    resourceProvider.modifyFile(dependencyPath1, 'new contents');
+    resourceProvider.modifyFile(dependencyPath2, 'new contents');
+    // Arrange for the next call to computePackageMap to return the correct
+    // timestamps for the dependencies.
+    packageMapProvider.modificationTimes = <String, int>{};
+    for (String path in [dependencyPath1, dependencyPath2]) {
+      File resource = resourceProvider.getResource(path);
+      packageMapProvider.modificationTimes[path] = resource.modificationStamp;
+    }
+    // This should cause the new package map to be picked up, by executing
+    // computePackageMap just one additional time.
+    await pumpEventQueue();
+    _checkPackageMap(projPath, equals(packageMapProvider.packageMap));
+    expect(packageMapProvider.computeCount, 2);
+  }
+
   /**
    * Verify that package URI's for source files in [path] will be resolved
    * using a package map matching [expectation].
@@ -917,7 +953,7 @@
       <String, UriResolver>{};
 
   TestContextManager(MemoryResourceProvider resourceProvider,
-      PackageMapProvider packageMapProvider)
+      OptimizingPubPackageMapProvider packageMapProvider)
       : super(resourceProvider, packageMapProvider,
           InstrumentationService.NULL_SERVICE);
 
diff --git a/pkg/analysis_server/test/domain_completion_test.dart b/pkg/analysis_server/test/domain_completion_test.dart
index e727c6c..6ffc8ef 100644
--- a/pkg/analysis_server/test/domain_completion_test.dart
+++ b/pkg/analysis_server/test/domain_completion_test.dart
@@ -17,9 +17,9 @@
 import 'package:analysis_server/src/services/index/index.dart' show Index;
 import 'package:analysis_server/src/services/index/local_memory_index.dart';
 import 'package:analysis_server/src/services/search/search_engine.dart';
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
 import 'package:analyzer/file_system/file_system.dart';
 import 'package:analyzer/instrumentation/instrumentation.dart';
-import 'package:analyzer/source/package_map_provider.dart';
 import 'package:analyzer/src/generated/engine.dart';
 import 'package:analyzer/src/generated/sdk.dart';
 import 'package:analyzer/src/generated/source.dart';
@@ -598,13 +598,13 @@
   Stream<SourcesChangedEvent> get onSourcesChanged => mockStream;
 
   @override
-  TimestampedData<String> getContents(Source source) {
-    return source.contents;
+  bool exists(Source source) {
+    return source != null && source.exists();
   }
 
   @override
-  bool exists(Source source) {
-    return source != null && source.exists();
+  TimestampedData<String> getContents(Source source) {
+    return source.contents;
   }
 
   noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
@@ -647,7 +647,7 @@
   final MockContext mockContext = new MockContext();
 
   Test_AnalysisServer(ServerCommunicationChannel channel,
-      ResourceProvider resourceProvider, PackageMapProvider packageMapProvider,
+      ResourceProvider resourceProvider, OptimizingPubPackageMapProvider packageMapProvider,
       Index index, AnalysisServerOptions analysisServerOptions,
       DartSdk defaultSdk, InstrumentationService instrumentationService)
       : super(channel, resourceProvider, packageMapProvider, index,
diff --git a/pkg/analysis_server/test/mocks.dart b/pkg/analysis_server/test/mocks.dart
index be14732..94bc8c6 100644
--- a/pkg/analysis_server/test/mocks.dart
+++ b/pkg/analysis_server/test/mocks.dart
@@ -14,6 +14,7 @@
 import 'package:analysis_server/src/operation/operation.dart';
 import 'package:analysis_server/src/operation/operation_analysis.dart';
 import 'package:analysis_server/src/protocol.dart' hide Element, ElementKind;
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
 import 'package:analyzer/file_system/file_system.dart' as resource;
 import 'package:analyzer/file_system/memory_file_system.dart' as resource;
 import 'package:analyzer/source/package_map_provider.dart';
@@ -152,7 +153,7 @@
 /**
  * A mock [PackageMapProvider].
  */
-class MockPackageMapProvider implements PackageMapProvider {
+class MockPackageMapProvider implements OptimizingPubPackageMapProvider {
   /**
    * Package map that will be returned by the next call to [computePackageMap].
    */
@@ -169,12 +170,42 @@
    */
   Set<String> dependencies = new Set<String>();
 
+  /**
+   * Modification times that will be returned by the next call to
+   * [computePackageMap].  This will be filtered to include only those paths
+   * mentioned in the `dependencies` field of [computePackageMap]'s
+   * `previousInfo` argument.
+   */
+  Map<String, int> modificationTimes = <String, int>{};
+
+  /**
+   * Number of times [computePackageMap] has been called.
+   */
+  int computeCount = 0;
+
   @override
-  PackageMapInfo computePackageMap(resource.Folder folder) {
-    if (packageMaps != null) {
-      return new PackageMapInfo(packageMaps[folder.path], dependencies);
+  OptimizingPubPackageMapInfo computePackageMap(resource.Folder folder,
+      [OptimizingPubPackageMapInfo previousInfo]) {
+    ++computeCount;
+    Map<String, int> filteredModificationTimes = <String, int>{};
+    if (previousInfo != null) {
+      for (String dependency in previousInfo.dependencies) {
+        if (modificationTimes.containsKey(dependency)) {
+          filteredModificationTimes[dependency] = modificationTimes[dependency];
+        }
+      }
     }
-    return new PackageMapInfo(packageMap, dependencies);
+    if (packageMaps != null) {
+      return new OptimizingPubPackageMapInfo(
+          packageMaps[folder.path], dependencies, filteredModificationTimes);
+    }
+    return new OptimizingPubPackageMapInfo(
+        packageMap, dependencies, filteredModificationTimes);
+  }
+
+  noSuchMethod(Invocation invocation) {
+    // No other methods should be called.
+    return super.noSuchMethod(invocation);
   }
 }
 
diff --git a/pkg/analysis_server/test/source/optimizing_pub_package_map_provider_test.dart b/pkg/analysis_server/test/source/optimizing_pub_package_map_provider_test.dart
new file mode 100644
index 0000000..769b683
--- /dev/null
+++ b/pkg/analysis_server/test/source/optimizing_pub_package_map_provider_test.dart
@@ -0,0 +1,245 @@
+// Copyright (c) 2015, 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.
+
+library test.source.optimizing_pub_package_map_provider;
+
+import 'dart:convert';
+import 'dart:io' as io;
+
+import 'package:analysis_server/src/source/optimizing_pub_package_map_provider.dart';
+import 'package:analyzer/file_system/file_system.dart';
+import 'package:analyzer/file_system/memory_file_system.dart';
+import 'package:path/path.dart';
+import 'package:unittest/unittest.dart';
+
+import '../reflective_tests.dart';
+
+main() {
+  groupSep = ' | ';
+  runReflectiveTests(OptimizingPubPackageMapProviderTest);
+  runReflectiveTests(OptimizingPubPackageMapInfoTest);
+}
+
+@reflectiveTest
+class OptimizingPubPackageMapInfoTest {
+  MemoryResourceProvider resourceProvider;
+
+  int createFile(String path) {
+    return resourceProvider.newFile(path, 'contents').modificationStamp;
+  }
+
+  void createFolder(String path) {
+    resourceProvider.newFolder(path);
+  }
+
+  void modifyFile(String path) {
+    resourceProvider.modifyFile(path, 'contents');
+  }
+
+  void setUp() {
+    resourceProvider = new MemoryResourceProvider();
+  }
+
+  test_isChangedDependency_fileNotPresent() {
+    String path = '/dep';
+    int timestamp = 1;
+    OptimizingPubPackageMapInfo info =
+        new OptimizingPubPackageMapInfo({}, [path].toSet(), {path: timestamp});
+    expect(info.isChangedDependency(path, resourceProvider), isTrue);
+  }
+
+  test_isChangedDependency_matchingTimestamp() {
+    String path = '/dep';
+    int timestamp = createFile(path);
+    OptimizingPubPackageMapInfo info =
+        new OptimizingPubPackageMapInfo({}, [path].toSet(), {path: timestamp});
+    expect(info.isChangedDependency(path, resourceProvider), isFalse);
+  }
+
+  test_isChangedDependency_mismatchedTimestamp() {
+    String path = '/dep';
+    int timestamp = createFile(path);
+    OptimizingPubPackageMapInfo info =
+        new OptimizingPubPackageMapInfo({}, [path].toSet(), {path: timestamp});
+    modifyFile(path);
+    expect(info.isChangedDependency(path, resourceProvider), isTrue);
+  }
+
+  test_isChangedDependency_nonDependency() {
+    OptimizingPubPackageMapInfo info =
+        new OptimizingPubPackageMapInfo({}, ['/dep1'].toSet(), {});
+    expect(info.isChangedDependency('/dep2', resourceProvider), isFalse);
+  }
+
+  test_isChangedDependency_nonFile() {
+    String path = '/dep';
+    int timestamp = 1;
+    createFolder(path);
+    OptimizingPubPackageMapInfo info =
+        new OptimizingPubPackageMapInfo({}, [path].toSet(), {path: timestamp});
+    expect(info.isChangedDependency(path, resourceProvider), isTrue);
+  }
+
+  test_isChangedDependency_noTimestampInfo() {
+    String path = '/dep';
+    OptimizingPubPackageMapInfo info =
+        new OptimizingPubPackageMapInfo({}, [path].toSet(), {});
+    expect(info.isChangedDependency(path, resourceProvider), isTrue);
+  }
+}
+
+@reflectiveTest
+class OptimizingPubPackageMapProviderTest {
+  MemoryResourceProvider resourceProvider;
+  OptimizingPubPackageMapProvider provider;
+  Folder projectFolder;
+  io.ProcessResult pubListResult;
+
+  void setPubListError() {
+    pubListResult = new _MockProcessResult(0, 1, '', 'ERROR');
+  }
+
+  void setPubListResult({Map<String, String> packages: const {},
+      List<String> input_files: const []}) {
+    pubListResult = new _MockProcessResult(0, 0,
+        JSON.encode({'packages': packages, 'input_files': input_files}), '');
+  }
+
+  void setUp() {
+    resourceProvider = new MemoryResourceProvider();
+    provider = new OptimizingPubPackageMapProvider(
+        resourceProvider, null, _runPubList);
+    projectFolder = resourceProvider.newFolder('/my/proj');
+  }
+
+  test_computePackageMap_noPreviousInfo() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    String pkgName = 'foo';
+    String pkgPath = '/pkg/foo';
+    setPubListResult(packages: {pkgName: pkgPath}, input_files: [dep]);
+    OptimizingPubPackageMapInfo info =
+        provider.computePackageMap(projectFolder);
+    expect(info.dependencies, hasLength(1));
+    expect(info.dependencies, contains(dep));
+    expect(info.packageMap, hasLength(1));
+    expect(info.packageMap, contains(pkgName));
+    expect(info.packageMap[pkgName], hasLength(1));
+    expect(info.packageMap[pkgName][0].path, pkgPath);
+    expect(info.modificationTimes, isEmpty);
+  }
+
+  test_computePackageMap_noPreviousInfo_pubListError() {
+    String pubspecLock = posix.join(projectFolder.path, 'pubspec.lock');
+    setPubListError();
+    OptimizingPubPackageMapInfo info =
+        provider.computePackageMap(projectFolder);
+    expect(info.dependencies, hasLength(1));
+    expect(info.dependencies, contains(pubspecLock));
+    expect(info.packageMap, isNull);
+    expect(info.modificationTimes, isEmpty);
+  }
+
+  test_computePackageMap_withPreviousInfo() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    int timestamp = resourceProvider.newFile(dep, 'contents').modificationStamp;
+    setPubListResult(input_files: [dep]);
+    OptimizingPubPackageMapInfo info1 =
+        provider.computePackageMap(projectFolder);
+    OptimizingPubPackageMapInfo info2 =
+        provider.computePackageMap(projectFolder, info1);
+    expect(info2.dependencies, hasLength(1));
+    expect(info2.dependencies, contains(dep));
+    expect(info2.modificationTimes, hasLength(1));
+    expect(info2.modificationTimes, contains(dep));
+    expect(info2.modificationTimes[dep], timestamp);
+  }
+
+  test_computePackageMap_withPreviousInfo_newDependency() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    resourceProvider.newFile(dep, 'contents').modificationStamp;
+    setPubListResult(input_files: []);
+    OptimizingPubPackageMapInfo info1 =
+        provider.computePackageMap(projectFolder);
+    setPubListResult(input_files: [dep]);
+    OptimizingPubPackageMapInfo info2 =
+        provider.computePackageMap(projectFolder, info1);
+    expect(info2.modificationTimes, isEmpty);
+  }
+
+  test_computePackageMap_withPreviousInfo_oldDependencyNoLongerAFile() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    resourceProvider.newFile(dep, 'contents').modificationStamp;
+    setPubListResult(input_files: [dep]);
+    OptimizingPubPackageMapInfo info1 =
+        provider.computePackageMap(projectFolder);
+    resourceProvider.deleteFile(dep);
+    resourceProvider.newFolder(dep);
+    OptimizingPubPackageMapInfo info2 =
+        provider.computePackageMap(projectFolder, info1);
+    expect(info2.modificationTimes, isEmpty);
+  }
+
+  test_computePackageMap_withPreviousInfo_oldDependencyNoLongerPresent() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    resourceProvider.newFile(dep, 'contents').modificationStamp;
+    setPubListResult(input_files: [dep]);
+    OptimizingPubPackageMapInfo info1 =
+        provider.computePackageMap(projectFolder);
+    resourceProvider.deleteFile(dep);
+    OptimizingPubPackageMapInfo info2 =
+        provider.computePackageMap(projectFolder, info1);
+    expect(info2.modificationTimes, isEmpty);
+  }
+
+  test_computePackageMap_withPreviousInfo_oldDependencyNoLongerRelevant() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    resourceProvider.newFile(dep, 'contents').modificationStamp;
+    setPubListResult(input_files: [dep]);
+    OptimizingPubPackageMapInfo info1 =
+        provider.computePackageMap(projectFolder);
+    setPubListResult(input_files: []);
+    OptimizingPubPackageMapInfo info2 =
+        provider.computePackageMap(projectFolder, info1);
+    expect(info2.modificationTimes, isEmpty);
+  }
+
+  test_computePackageMap_withPreviousInfo_pubListError() {
+    String dep = posix.join(projectFolder.path, 'dep');
+    String pubspecLock = posix.join(projectFolder.path, 'pubspec.lock');
+    int timestamp = resourceProvider.newFile(dep, 'contents').modificationStamp;
+    setPubListResult(input_files: [dep]);
+    OptimizingPubPackageMapInfo info1 =
+        provider.computePackageMap(projectFolder);
+    setPubListError();
+    OptimizingPubPackageMapInfo info2 =
+        provider.computePackageMap(projectFolder, info1);
+    expect(info2.dependencies, hasLength(2));
+    expect(info2.dependencies, contains(dep));
+    expect(info2.dependencies, contains(pubspecLock));
+    expect(info2.modificationTimes, hasLength(1));
+    expect(info2.modificationTimes, contains(dep));
+    expect(info2.modificationTimes[dep], timestamp);
+  }
+
+  io.ProcessResult _runPubList(Folder folder) {
+    expect(folder, projectFolder);
+    return pubListResult;
+  }
+}
+
+class _MockProcessResult implements io.ProcessResult {
+  @override
+  final int pid;
+
+  @override
+  final int exitCode;
+
+  @override
+  final stdout;
+
+  @override
+  final stderr;
+
+  _MockProcessResult(this.pid, this.exitCode, this.stdout, this.stderr);
+}
diff --git a/pkg/analysis_server/test/source/test_all.dart b/pkg/analysis_server/test/source/test_all.dart
index 3a3e709..34a617f 100644
--- a/pkg/analysis_server/test/source/test_all.dart
+++ b/pkg/analysis_server/test/source/test_all.dart
@@ -5,10 +5,13 @@
 library test.source;
 
 import 'caching_put_package_map_provider_test.dart' as caching_provider_test;
+import 'optimizing_pub_package_map_provider_test.dart'
+    as optimizing_provider_test;
 import 'package:unittest/unittest.dart';
 
 /// Utility for manually running all tests.
 main() {
   groupSep = ' | ';
   caching_provider_test.main();
+  optimizing_provider_test.main();
 }
diff --git a/tools/VERSION b/tools/VERSION
index c1363d0..f5b7a3b 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -28,4 +28,4 @@
 MINOR 10
 PATCH 0
 PRERELEASE 1
-PRERELEASE_PATCH 4
+PRERELEASE_PATCH 5