diff --git a/source/dub/dub.d b/source/dub/dub.d
index c236d3d..8a4854e 100644
--- a/source/dub/dub.d
+++ b/source/dub/dub.d
@@ -1243,6 +1243,7 @@
 		SelectedVersions m_selectedVersions;
 		Package m_rootPackage;
 		bool[string] m_packagesToUpgrade;
+		Package[PackageDependency] m_packages;
 	}
 
 
@@ -1344,7 +1345,7 @@
 		}
 		auto basepack = pack.basePackage;
 
-		foreach (d; pack.getAllDependencies()) {
+		foreach (d; pack.getAllDependenciesRange()) {
 			auto dbasename = getBasePackageName(d.name);
 
 			// detect dependencies to the root package (or sub packages thereof)
@@ -1396,6 +1397,16 @@
 
 	private Package getPackage(string name, Dependency dep)
 	{
+		auto key = PackageDependency(name, dep);
+		if (auto pp = key in m_packages)
+			return *pp;
+		auto p = getPackageRaw(name, dep);
+		m_packages[key] = p;
+		return p;
+	}
+
+	private Package getPackageRaw(string name, Dependency dep)
+	{
 		auto basename = getBasePackageName(name);
 
 		// for sub packages, first try to get them from the base package
diff --git a/source/dub/package_.d b/source/dub/package_.d
index 98d0dc9..5197a45 100644
--- a/source/dub/package_.d
+++ b/source/dub/package_.d
@@ -526,14 +526,24 @@
 	PackageDependency[] getAllDependencies()
 	const {
 		auto ret = appender!(PackageDependency[]);
-		foreach (n, d; this.recipe.buildSettings.dependencies)
-			ret ~= PackageDependency(n, d);
-		foreach (ref c; this.recipe.configurations)
-			foreach (n, d; c.buildSettings.dependencies)
-				ret ~= PackageDependency(n, d);
+		getAllDependenciesRange().copy(ret);
 		return ret.data;
 	}
 
+	// Left as package until the final API for this has been found
+	package auto getAllDependenciesRange()
+	const {
+		return this.recipe.buildSettings.dependencies.byKeyValue
+			.map!(bs => PackageDependency(bs.key, bs.value))
+			.chain(
+				this.recipe.configurations
+					.map!(c => c.buildSettings.dependencies.byKeyValue
+						.map!(bs => PackageDependency(bs.key, bs.value))
+					)
+					.joiner()
+			);
+	}
+
 
 	/** Returns a description of the package for use in IDEs or build tools.
 	*/