diff --git a/java/com/google/gitiles/GitilesFilter.java b/java/com/google/gitiles/GitilesFilter.java
index 254fe22..79dcc4c 100644
--- a/java/com/google/gitiles/GitilesFilter.java
+++ b/java/com/google/gitiles/GitilesFilter.java
@@ -383,9 +383,9 @@
     if (visibilityCache == null) {
       if (config.getSubsections("cache").contains("visibility")) {
         visibilityCache =
-            new VisibilityCache(false, ConfigUtil.getCacheBuilder(config, "visibility"));
+            new VisibilityCache(ConfigUtil.getCacheBuilder(config, "visibility"));
       } else {
-        visibilityCache = new VisibilityCache(false);
+        visibilityCache = new VisibilityCache();
       }
     }
   }
diff --git a/java/com/google/gitiles/VisibilityCache.java b/java/com/google/gitiles/VisibilityCache.java
index fe1c07e..1c6b785 100644
--- a/java/com/google/gitiles/VisibilityCache.java
+++ b/java/com/google/gitiles/VisibilityCache.java
@@ -89,16 +89,16 @@
     return CacheBuilder.newBuilder().maximumSize(1 << 10).expireAfterWrite(30, TimeUnit.MINUTES);
   }
 
-  public VisibilityCache(boolean topoSort) {
-    this(topoSort, defaultBuilder());
+  public VisibilityCache() {
+    this(new VisibilityChecker(), defaultBuilder());
   }
 
-  public VisibilityCache(boolean topoSort, CacheBuilder<Object, Object> builder) {
-    this(new VisibilityChecker(topoSort), builder);
+  public VisibilityCache(CacheBuilder<Object, Object> builder) {
+    this(new VisibilityChecker(), builder);
   }
 
   /**
-   * Use the constructors with a boolean parameter (e.g. {@link #VisibilityCache(boolean)}). The
+   * Use the constructors with a boolean parameter (e.g. {@link #VisibilityCache()}). The
    * default visibility checker should cover all common use cases.
    *
    * <p>This constructor is useful to use a checker with additional logging or metrics collection,
@@ -109,7 +109,7 @@
   }
 
   /**
-   * Use the constructors with a boolean parameter (e.g. {@link #VisibilityCache(boolean)}). The
+   * Use the constructors with a boolean parameter (e.g. {@link #VisibilityCache()}). The
    * default visibility checker should cover all common use cases.
    *
    * <p>This constructor is useful to use a checker with additional logging or metrics collection,
diff --git a/java/com/google/gitiles/VisibilityChecker.java b/java/com/google/gitiles/VisibilityChecker.java
index ccd5cf1..899d1f1 100644
--- a/java/com/google/gitiles/VisibilityChecker.java
+++ b/java/com/google/gitiles/VisibilityChecker.java
@@ -42,6 +42,7 @@
  */
 package com.google.gitiles;
 
+import com.google.common.collect.ImmutableList;
 import java.io.IOException;
 import java.util.Collection;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
@@ -49,7 +50,6 @@
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.RefDatabase;
 import org.eclipse.jgit.revwalk.RevCommit;
-import org.eclipse.jgit.revwalk.RevSort;
 import org.eclipse.jgit.revwalk.RevWalk;
 
 /**
@@ -59,16 +59,6 @@
  */
 public class VisibilityChecker {
 
-  private final boolean topoSort;
-
-  /**
-   * @param topoSort whether to use a more thorough reachability check by sorting in topological
-   *     order
-   */
-  public VisibilityChecker(boolean topoSort) {
-    this.topoSort = topoSort;
-  }
-
   /**
    * Check if any of the refs in {@code refDb} points to the object {@code id}.
    *
@@ -90,7 +80,7 @@
    * @param walk The walk to use for the reachability check
    * @param commit The starting commit. It *MUST* come from the walk in use
    * @param starters visible commits. Anything reachable from these commits is visible. Missing ids
-   *     or ids pointing to wrong kind of objects are ignored.
+   *     or ids referring to other kinds of objects are ignored.
    * @return true if we can get to {@code commit} from the {@code starters}
    * @throws IOException a pack file or loose object could not be read
    */
@@ -101,28 +91,29 @@
       return false;
     }
 
-    walk.reset();
-    if (topoSort) {
-      walk.sort(RevSort.TOPO);
+    ImmutableList<RevCommit> startCommits = objectIdsToCommits(walk, starters);
+    if (startCommits.isEmpty()) {
+      return false;
     }
 
-    walk.markStart(commit);
-    for (ObjectId id : starters) {
-      markUninteresting(walk, id);
-    }
-    // If the commit is reachable from any given tip, it will appear to be
-    // uninteresting to the RevWalk and no output will be produced.
-    return walk.next() == null;
+    return !walk.createReachabilityChecker()
+        .areAllReachable(ImmutableList.of(commit), startCommits)
+        .isPresent();
   }
 
-  private static void markUninteresting(RevWalk walk, ObjectId id) throws IOException {
-    if (id == null) {
-      return;
+  private static ImmutableList<RevCommit> objectIdsToCommits(RevWalk walk, Collection<ObjectId> ids)
+      throws IOException {
+    ImmutableList.Builder<RevCommit> commits = ImmutableList.builder();
+    for (ObjectId id : ids) {
+      try {
+        commits.add(walk.parseCommit(id));
+      } catch (MissingObjectException e) {
+        // TODO(ifrade): ResolveParser has already checked that the object exists in the repo.
+        // Report as AssertionError.
+      } catch (IncorrectObjectTypeException e) {
+        // Ignore, doesn't affect commit reachability
+      }
     }
-    try {
-      walk.markUninteresting(walk.parseCommit(id));
-    } catch (IncorrectObjectTypeException | MissingObjectException e) {
-      // Do nothing, doesn't affect reachability.
-    }
+    return commits.build();
   }
 }
diff --git a/javatests/com/google/gitiles/RevisionParserTest.java b/javatests/com/google/gitiles/RevisionParserTest.java
index b2c88ea..16e76a7 100644
--- a/javatests/com/google/gitiles/RevisionParserTest.java
+++ b/javatests/com/google/gitiles/RevisionParserTest.java
@@ -46,7 +46,7 @@
         new RevisionParser(
             repo.getRepository(),
             new TestGitilesAccess(repo.getRepository()).forRequest(null),
-            new VisibilityCache(false, CacheBuilder.newBuilder().maximumSize(0)));
+            new VisibilityCache(CacheBuilder.newBuilder().maximumSize(0)));
   }
 
   @Test
diff --git a/javatests/com/google/gitiles/TestViewFilter.java b/javatests/com/google/gitiles/TestViewFilter.java
index 68acffb..4f67efc 100644
--- a/javatests/com/google/gitiles/TestViewFilter.java
+++ b/javatests/com/google/gitiles/TestViewFilter.java
@@ -65,7 +65,7 @@
         new ViewFilter(
             new TestGitilesAccess(repo.getRepository()),
             TestGitilesUrls.URLS,
-            new VisibilityCache(false));
+            new VisibilityCache());
     MetaFilter mf = new MetaFilter();
 
     for (Pattern p : ImmutableList.of(ROOT_REGEX, REPO_REGEX, REPO_PATH_REGEX)) {
diff --git a/javatests/com/google/gitiles/VisibilityCacheTest.java b/javatests/com/google/gitiles/VisibilityCacheTest.java
index bcc2b40..92ea04b 100644
--- a/javatests/com/google/gitiles/VisibilityCacheTest.java
+++ b/javatests/com/google/gitiles/VisibilityCacheTest.java
@@ -108,7 +108,7 @@
       git.update("refs/tags/v0.1", commitA);
     }
 
-    visibilityCache = new VisibilityCache(true);
+    visibilityCache = new VisibilityCache();
     walk = new RevWalk(repo);
     walk.setRetainBody(false);
   }
diff --git a/javatests/com/google/gitiles/VisibilityCheckerTest.java b/javatests/com/google/gitiles/VisibilityCheckerTest.java
index 3171459..5470e52 100644
--- a/javatests/com/google/gitiles/VisibilityCheckerTest.java
+++ b/javatests/com/google/gitiles/VisibilityCheckerTest.java
@@ -89,7 +89,7 @@
       git.update("refs/tags/v0.1", commitA);
     }
 
-    visibilityChecker = new VisibilityChecker(true);
+    visibilityChecker = new VisibilityChecker();
     walk = new RevWalk(repo);
     walk.setRetainBody(false);
   }