Bug 344347 - [region] linear search to find a bundle's region hurts performance

6 files changed, 174 insertions, 62 deletions

diff --git a/bundles/org.eclipse.equinox.region.tests/META-INF/MANIFEST.MF b/bundles/org.eclipse.equinox.region.tests/META-INF/MANIFEST.MF
index c7ad9eddd..d4ca7ed65 100644
--- a/bundles/org.eclipse.equinox.region.tests/META-INF/MANIFEST.MF
+++ b/bundles/org.eclipse.equinox.region.tests/META-INF/MANIFEST.MF
@@ -8,6 +8,7 @@ Fragment-Host: org.eclipse.equinox.region
 Import-Package: junit.framework;version="4.8.1",
  org.easymock;version="2.4.0",
  org.eclipse.osgi.service.urlconversion;version="1.0.0",
+ org.eclipse.core.tests.harness,
  org.junit;version="4.8.1",
  org.osgi.util.tracker;version="1.5.0",
  org.aspectj.internal.lang.annotation;version="[1.6.3, 2.0.0)",
diff --git a/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/internal/region/BundleIdBasedRegionTests.java b/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/internal/region/BundleIdBasedRegionTests.java
index dac31331e..42d130012 100644
--- a/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/internal/region/BundleIdBasedRegionTests.java
+++ b/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/internal/region/BundleIdBasedRegionTests.java
@@ -16,8 +16,7 @@ import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 
-import java.util.HashSet;
-import java.util.Iterator;
+import java.util.*;
 import java.util.concurrent.atomic.AtomicLong;
 import org.easymock.EasyMock;
 import org.eclipse.equinox.region.*;
@@ -59,10 +58,12 @@ public class BundleIdBasedRegionTests {
 
 	private ThreadLocal<Region> threadLocal;
 	private Object globalUpdateMonitor = new Object();
+	private Map<Long, Region> globalBundleToRegion = new HashMap<Long, Region>();
 	private AtomicLong globalTimeStamp = new AtomicLong();
 
 	@Before
 	public void setUp() throws Exception {
+		this.globalBundleToRegion.clear();
 		this.threadLocal = new ThreadLocal<Region>();
 		this.mockBundle = EasyMock.createMock(Bundle.class);
 		EasyMock.expect(this.mockBundle.getSymbolicName()).andReturn(BUNDLE_SYMBOLIC_NAME).anyTimes();
@@ -111,7 +112,7 @@ public class BundleIdBasedRegionTests {
 	public void testGetName() {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		assertEquals(REGION_NAME, r.getName());
 	}
 
@@ -142,7 +143,7 @@ public class BundleIdBasedRegionTests {
 		EasyMock.expect(this.mockGraph.getEdges(EasyMock.isA(Region.class))).andReturn(edges).anyTimes();
 		replayMocks();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(this.mockBundle);
 	}
 
@@ -150,7 +151,7 @@ public class BundleIdBasedRegionTests {
 	public void testAddExistingBundle() throws BundleException {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(this.mockBundle);
 		r.addBundle(this.mockBundle);
 	}
@@ -165,7 +166,7 @@ public class BundleIdBasedRegionTests {
 		EasyMock.expect(mockBundle2.getBundleId()).andReturn(BUNDLE_ID_2).anyTimes();
 		EasyMock.replay(mockBundle2);
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(this.mockBundle);
 		r.addBundle(mockBundle2);
 	}
@@ -210,10 +211,11 @@ public class BundleIdBasedRegionTests {
 		EasyMock.expect(this.mockGraph.getEdges(EasyMock.isA(Region.class))).andReturn(new HashSet<FilteredRegion>()).anyTimes();
 		EasyMock.expect(this.mockRegion.contains(EasyMock.eq(BUNDLE_ID))).andReturn(true).anyTimes();
 		EasyMock.expect(this.mockRegion2.contains(EasyMock.eq(BUNDLE_ID))).andReturn(false).anyTimes();
+		this.globalBundleToRegion.put(BUNDLE_ID, mockRegion);
 
 		replayMocks();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		return r;
 	}
 
@@ -235,7 +237,7 @@ public class BundleIdBasedRegionTests {
 	public void testContains() throws BundleException {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(this.mockBundle);
 		assertTrue(r.contains(this.mockBundle));
 	}
@@ -244,7 +246,7 @@ public class BundleIdBasedRegionTests {
 	public void testDoesNotContain() throws BundleException {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		assertFalse(r.contains(this.mockBundle));
 	}
 
@@ -252,7 +254,7 @@ public class BundleIdBasedRegionTests {
 	public void testGetBundle() throws BundleException {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(this.mockBundle);
 		assertEquals(this.mockBundle, r.getBundle(BUNDLE_SYMBOLIC_NAME, BUNDLE_VERSION));
 	}
@@ -261,7 +263,7 @@ public class BundleIdBasedRegionTests {
 	public void testGetBundleNotFound() throws BundleException {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(this.mockBundle);
 		assertNull(r.getBundle(BUNDLE_SYMBOLIC_NAME_2, BUNDLE_VERSION));
 	}
@@ -270,7 +272,7 @@ public class BundleIdBasedRegionTests {
 	public void testConnectRegion() throws BundleException {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.connectRegion(this.mockRegion, this.mockRegionFilter);
 	}
 
@@ -278,8 +280,8 @@ public class BundleIdBasedRegionTests {
 	public void testEquals() {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
-		Region s = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
+		Region s = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		assertEquals(r, r);
 		assertEquals(r, s);
 		assertEquals(r.hashCode(), s.hashCode());
@@ -289,8 +291,8 @@ public class BundleIdBasedRegionTests {
 	public void testNotEqual() {
 		defaultSetUp();
 
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
-		Region s = new BundleIdBasedRegion(OTHER_REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
+		Region s = new BundleIdBasedRegion(OTHER_REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		assertFalse(r.equals(s));
 		assertFalse(r.equals(null));
 	}
@@ -298,7 +300,7 @@ public class BundleIdBasedRegionTests {
 	@Test
 	public void testAddRemoveBundleId() throws BundleException {
 		defaultSetUp();
-		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp);
+		Region r = new BundleIdBasedRegion(REGION_NAME, this.mockGraph, this.mockBundleContext, this.threadLocal, this.globalUpdateMonitor, this.globalTimeStamp, this.globalBundleToRegion);
 		r.addBundle(TEST_BUNDLE_ID);
 		assertTrue(r.contains(TEST_BUNDLE_ID));
 		r.removeBundle(TEST_BUNDLE_ID);
diff --git a/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/region/tests/system/RegionPerformanceTests.java b/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/region/tests/system/RegionPerformanceTests.java
new file mode 100644
index 000000000..e7eda631f
--- /dev/null
+++ b/bundles/org.eclipse.equinox.region.tests/src/org/eclipse/equinox/region/tests/system/RegionPerformanceTests.java
@@ -0,0 +1,114 @@
+/*******************************************************************************
+ * Copyright (c) 2011 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.equinox.region.tests.system;
+
+import java.util.Collection;
+import org.eclipse.core.tests.harness.PerformanceTestRunner;
+import org.eclipse.equinox.region.*;
+import org.osgi.framework.*;
+
+public class RegionPerformanceTests extends AbstractRegionSystemTest {
+	Bundle testBundle;
+
+	@Override
+	protected void setUp() throws Exception {
+		super.setUp();
+		testBundle = bundleInstaller.installBundle(PP1);
+		testBundle.start();
+	}
+
+	private void doTestGetBundles(String fingerPrintName, String degradation) {
+		final BundleContext context = testBundle.getBundleContext();
+		PerformanceTestRunner runner = new PerformanceTestRunner() {
+			protected void test() {
+				Bundle[] bundles = context.getBundles();
+				for (Bundle bundle : bundles) {
+					context.getBundle(bundle.getBundleId());
+				}
+			}
+		};
+		runner.setRegressionReason(degradation);
+		runner.run(this, fingerPrintName, 10, 300);
+	}
+
+	public void testGetBundlesNoRegions() throws BundleException {
+		regionBundle.stop();
+		doTestGetBundles(null, null);
+	}
+
+	public void testGetBundles10Regions() throws BundleException {
+		createRegions(10);
+		doTestGetBundles(null, null);
+	}
+
+	public void testGetBundles100Regions() throws BundleException {
+		createRegions(100);
+		doTestGetBundles(null, null);
+	}
+
+	public void testGetBundles1000Regions() throws BundleException {
+		createRegions(1000);
+		doTestGetBundles(null, null);
+	}
+
+	public void testGetServicesNoRegions() throws BundleException {
+		regionBundle.stop();
+		doTestGetServices(null, null);
+	}
+
+	public void testGetServices10Regions() throws BundleException {
+		createRegions(10);
+		doTestGetServices(null, null);
+	}
+
+	public void testGetServices100Regions() throws BundleException {
+		createRegions(100);
+		doTestGetBundles(null, null);
+	}
+
+	public void testGetServices1000Regions() throws BundleException {
+		createRegions(1000);
+		doTestGetBundles(null, null);
+	}
+
+	private void doTestGetServices(String fingerPrintName, String degradation) {
+		final BundleContext context = testBundle.getBundleContext();
+		PerformanceTestRunner runner = new PerformanceTestRunner() {
+			protected void test() {
+				try {
+					Collection<ServiceReference<RegionDigraph>> refs = context.getServiceReferences(RegionDigraph.class, null);
+				} catch (InvalidSyntaxException e) {
+					fail(e.getMessage());
+				}
+			}
+		};
+		runner.setRegressionReason(degradation);
+		runner.run(this, fingerPrintName, 10, 2000);
+	}
+
+	private void createRegions(final int numRegions) throws BundleException {
+		System.out.println("Starting region create: " + numRegions);
+		long time = System.currentTimeMillis();
+		Region system = digraph.getRegion(0);
+		RegionFilterBuilder builder = digraph.createRegionFilterBuilder();
+		builder.allowAll(RegionFilter.VISIBLE_BUNDLE_NAMESPACE);
+		builder.allowAll(RegionFilter.VISIBLE_HOST_NAMESPACE);
+		builder.allowAll(RegionFilter.VISIBLE_PACKAGE_NAMESPACE);
+		builder.allowAll(RegionFilter.VISIBLE_REQUIRE_NAMESPACE);
+		builder.allowAll(RegionFilter.VISIBLE_SERVICE_NAMESPACE);
+		RegionFilter filter = builder.build();
+		for (int i = 0; i < numRegions; i++) {
+			Region r = digraph.createRegion(getName() + i);
+			digraph.connect(system, filter, r);
+		}
+		System.out.println("Done creating region: " + (System.currentTimeMillis() - time));
+	}
+}
diff --git a/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/BundleIdBasedRegion.java b/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/BundleIdBasedRegion.java
index 5ec039155..02026498c 100644
--- a/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/BundleIdBasedRegion.java
+++ b/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/BundleIdBasedRegion.java
@@ -14,10 +14,7 @@ package org.eclipse.equinox.internal.region;
 import java.io.*;
 import java.net.MalformedURLException;
 import java.net.URL;
-import java.util.HashSet;
-import java.util.Set;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ConcurrentMap;
+import java.util.*;
 import java.util.concurrent.atomic.AtomicLong;
 import org.eclipse.equinox.region.*;
 import org.eclipse.equinox.region.RegionDigraph.FilteredRegion;
@@ -39,16 +36,12 @@ final class BundleIdBasedRegion implements Region {
 
 	private static final String FILE_SCHEME = "file:";
 
-	// A concurrent data structure ensures the contains method does not need synchronisation.
-	private final ConcurrentMap<Long, Boolean> bundleIds = new ConcurrentHashMap<Long, Boolean>();
-
-	// This monitor guards bundleIds. bundleIds is a concurrent data structure and
-	// may be read without synchronisation, but updates need synchronising to avoid races.
-	// Note that this monitor also locks modifications and read operations on the RegionDigraph
-	// As well as bundle id modifications of other Regions in the digraph
+	// Note that this global digraph monitor locks modifications and read operations on the RegionDigraph
+	// This includes modifying and reading the bunlde ids included in this region
 	// It should be considered a global lock on the complete digraph.
 	private final Object globalUpdateMonitor;
 	private final AtomicLong globalTimeStamp;
+	private final Map<Long, Region> globalBundleToRegion;
 
 	private final String regionName;
 
@@ -58,19 +51,22 @@ final class BundleIdBasedRegion implements Region {
 
 	private final ThreadLocal<Region> threadLocal;
 
-	BundleIdBasedRegion(String regionName, RegionDigraph regionDigraph, BundleContext bundleContext, ThreadLocal<Region> threadLocal, Object globalUpdateMonitor, AtomicLong globalTimeStamp) {
+	BundleIdBasedRegion(String regionName, RegionDigraph regionDigraph, BundleContext bundleContext, ThreadLocal<Region> threadLocal, Object globalUpdateMonitor, AtomicLong globalTimeStamp, Map<Long, Region> globalBundleToRegion) {
 		if (regionName == null)
 			throw new IllegalArgumentException("The region name must not be null");
 		if (regionDigraph == null)
 			throw new IllegalArgumentException("The region digraph must not be null");
 		if (globalUpdateMonitor == null)
 			throw new IllegalArgumentException("The global update monitor must not be null");
+		if (globalBundleToRegion == null)
+			throw new IllegalArgumentException("The global bundle to region must not be null");
 		this.regionName = regionName;
 		this.regionDigraph = regionDigraph;
 		this.bundleContext = bundleContext;
 		this.threadLocal = threadLocal;
 		this.globalUpdateMonitor = globalUpdateMonitor;
 		this.globalTimeStamp = globalTimeStamp;
+		this.globalBundleToRegion = globalBundleToRegion;
 	}
 
 	/**
@@ -93,13 +89,11 @@ final class BundleIdBasedRegion implements Region {
 	// There is a global lock obtained to ensure consistency across the complete digraph
 	public void addBundle(long bundleId) throws BundleException {
 		synchronized (this.globalUpdateMonitor) {
-			// note that obtaining the Iterator for the digraph requires locking the digraph monitor; but we already have it
-			for (Region r : this.regionDigraph) {
-				if (!this.equals(r) && r.contains(bundleId)) {
-					throw new BundleException("Bundle '" + bundleId + "' is already associated with region '" + r + "'", BundleException.INVALID_OPERATION);
-				}
+			Region r = this.globalBundleToRegion.get(bundleId);
+			if (r != null && r != this) {
+				throw new BundleException("Bundle '" + bundleId + "' is already associated with region '" + r + "'", BundleException.INVALID_OPERATION);
 			}
-			this.bundleIds.putIfAbsent(bundleId, Boolean.TRUE);
+			this.globalBundleToRegion.put(bundleId, this);
 			this.globalTimeStamp.incrementAndGet();
 		}
 
@@ -178,8 +172,8 @@ final class BundleIdBasedRegion implements Region {
 		if (bundleContext == null)
 			return null; // this region is not connected to an OSGi framework
 
-		// The following iteration is weakly consistent and will never throw ConcurrentModificationException.
-		for (long bundleId : this.bundleIds.keySet()) {
+		Set<Long> bundleIds = getBundleIds();
+		for (long bundleId : bundleIds) {
 			Bundle bundle = bundleContext.getBundle(bundleId);
 			if (bundle != null && symbolicName.equals(bundle.getSymbolicName()) && version.equals(bundle.getVersion())) {
 				return bundle;
@@ -195,22 +189,20 @@ final class BundleIdBasedRegion implements Region {
 		this.regionDigraph.connect(this, filter, headRegion);
 	}
 
-	// The contains methods must not acquire the updateMonitor in order to prevent
-	// deadlock since a thread holding the updateMonitor of one region can call
-	// checkBundleNotAssociatedWithAnotherRegion which can call the contains
-	// method on another region.
 	/**
 	 * {@inheritDoc}
 	 */
 	public boolean contains(long bundleId) {
-		return this.bundleIds.containsKey(bundleId);
+		synchronized (globalUpdateMonitor) {
+			return globalBundleToRegion.get(bundleId) == this;
+		}
 	}
 
 	/**
 	 * {@inheritDoc}
 	 */
 	public boolean contains(Bundle bundle) {
-		return this.bundleIds.containsKey(bundle.getBundleId());
+		return contains(bundle.getBundleId());
 	}
 
 	public int hashCode() {
@@ -247,7 +239,7 @@ final class BundleIdBasedRegion implements Region {
 	 */
 	public void removeBundle(long bundleId) {
 		synchronized (this.globalUpdateMonitor) {
-			this.bundleIds.remove(bundleId);
+			this.globalBundleToRegion.remove(bundleId);
 			this.globalTimeStamp.incrementAndGet();
 		}
 	}
@@ -263,7 +255,11 @@ final class BundleIdBasedRegion implements Region {
 	public Set<Long> getBundleIds() {
 		Set<Long> bundleIds = new HashSet<Long>();
 		synchronized (this.globalUpdateMonitor) {
-			bundleIds.addAll(this.bundleIds.keySet());
+			for (Map.Entry<Long, Region> entry : globalBundleToRegion.entrySet()) {
+				if (entry.getValue() == this) {
+					bundleIds.add(entry.getKey());
+				}
+			}
 		}
 		return bundleIds;
 	}
diff --git a/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/StandardRegionDigraph.java b/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/StandardRegionDigraph.java
index 35fa3ae12..10214b760 100644
--- a/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/StandardRegionDigraph.java
+++ b/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/StandardRegionDigraph.java
@@ -39,6 +39,12 @@ public final class StandardRegionDigraph implements RegionDigraph {
 
 	private final Set<Region> regions = new HashSet<Region>();
 
+	/*
+	 * bundleToRegion maps a given bundle id to the region for which it belongs.
+	 * this is a global map for all regions in the digraph
+	 */
+	private final Map<Long, Region> bundleToRegion = new HashMap<Long, Region>();
+
 	/* edges maps a given region to an immutable set of edges with their tail at the given region. To update
 	 * the edges for a region, the corresponding immutable set is replaced atomically. */
 	private final Map<Region, Set<FilteredRegion>> edges = new HashMap<Region, Set<FilteredRegion>>();
@@ -97,7 +103,7 @@ public final class StandardRegionDigraph implements RegionDigraph {
 	 * {@inheritDoc}
 	 */
 	public Region createRegion(String regionName) throws BundleException {
-		Region region = new BundleIdBasedRegion(regionName, this, this.bundleContext, this.threadLocal, this.monitor, this.timeStamp);
+		Region region = new BundleIdBasedRegion(regionName, this, this.bundleContext, this.threadLocal, this.monitor, this.timeStamp, this.bundleToRegion);
 		synchronized (this.monitor) {
 			if (getRegion(regionName) != null) {
 				throw new BundleException("Region '" + regionName + "' already exists", BundleException.UNSUPPORTED_OPERATION);
@@ -223,14 +229,7 @@ public final class StandardRegionDigraph implements RegionDigraph {
 	 * {@inheritDoc}
 	 */
 	public Region getRegion(Bundle bundle) {
-		synchronized (this.monitor) {
-			for (Region region : this) {
-				if (region.contains(bundle)) {
-					return region;
-				}
-			}
-			return null;
-		}
+		return getRegion(bundle.getBundleId());
 	}
 
 	/**
@@ -238,12 +237,7 @@ public final class StandardRegionDigraph implements RegionDigraph {
 	 */
 	public Region getRegion(long bundleId) {
 		synchronized (this.monitor) {
-			for (Region region : this) {
-				if (region.contains(bundleId)) {
-					return region;
-				}
-			}
-			return null;
+			return bundleToRegion.get(bundleId);
 		}
 	}
 
@@ -406,6 +400,7 @@ public final class StandardRegionDigraph implements RegionDigraph {
 			}
 			this.regions.clear();
 			this.edges.clear();
+			this.bundleToRegion.clear();
 			for (Region original : filteredRegions.keySet()) {
 				Region copy = this.createRegion(original.getName());
 				for (Long id : original.getBundleIds()) {
diff --git a/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/hook/RegionDigraphVisitorBase.java b/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/hook/RegionDigraphVisitorBase.java
index 67e60ec12..d9f94d3e3 100644
--- a/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/hook/RegionDigraphVisitorBase.java
+++ b/bundles/org.eclipse.equinox.region/src/org/eclipse/equinox/internal/region/hook/RegionDigraphVisitorBase.java
@@ -11,9 +11,8 @@
 
 package org.eclipse.equinox.internal.region.hook;
 
-import org.eclipse.equinox.region.*;
-
 import java.util.*;
+import org.eclipse.equinox.region.*;
 
 /**
  * {@link RegionDigraphVisitorBase} is an abstract base class for {@link RegionDigraphVisitor} implementations in the
@@ -103,6 +102,11 @@ abstract class RegionDigraphVisitorBase<C> implements RegionDigraphVisitor {
 				allow(candidate);
 			}
 		}
+		if (allowed.containsAll(candidates)) {
+			// there is no need to traverse edges of this region,
+			// it contains all the remaining filtered candidates
+			return false;
+		}
 		return true;
 	}