diff --git a/mercurial/utils/storageutil.py b/mercurial/utils/storageutil.py
--- a/mercurial/utils/storageutil.py
+++ b/mercurial/utils/storageutil.py
@@ -379,6 +379,7 @@ def emitrevisions(
 
     fnode = store.node
     frev = store.rev
+    parents = store.parentrevs
 
     if nodesorder == b'nodes':
         revs = [frev(n) for n in nodes]
@@ -391,23 +392,21 @@ def emitrevisions(
     prevrev = None
 
     if deltamode == repository.CG_DELTAMODE_PREV or assumehaveparentrevisions:
-        prevrev = store.parentrevs(revs[0])[0]
+        prevrev = parents(revs[0])[0]
 
-    # Set of revs available to delta against.
+    # Sets of revs available to delta against.
+    emitted = set()
     available = set()
-    parents = []
+    if assumehaveparentrevisions:
+        common_heads = set(p for r in revs for p in parents(r))
+        common_heads.difference_update(revs)
+        available = store.ancestors(common_heads, inclusive=True)
 
     def is_usable_base(rev):
         """Is a delta against this revision usable over the wire"""
         if rev == nullrev:
             return False
-        # Base revision was already emitted in this group.
-        if rev in available:
-            return True
-        # Base revision is a parent that hasn't been emitted already.
-        if assumehaveparentrevisions and rev in parents:
-            return True
-        return False
+        return rev in emitted or rev in available
 
     for rev in revs:
         if rev == nullrev:
@@ -418,7 +417,7 @@ def emitrevisions(
             debug_info['revision-total'] += 1
 
         node = fnode(rev)
-        parents[:] = p1rev, p2rev = store.parentrevs(rev)
+        p1rev, p2rev = parents(rev)
 
         if debug_info is not None:
             if p1rev != p2rev and p1rev != nullrev and p2rev != nullrev:
@@ -531,7 +530,7 @@ def emitrevisions(
                     debug_info['computed-delta'] += 1  # close enough
                     debug_info['delta-full'] += 1
                 revision = store.rawdata(node)
-                available.add(rev)
+                emitted.add(rev)
             else:
                 if revdifffn:
                     if debug_info is not None:
@@ -571,7 +570,7 @@ def emitrevisions(
                         store.rawdata(baserev), store.rawdata(rev)
                     )
 
-                available.add(rev)
+                emitted.add(rev)
 
         serialized_sidedata = None
         sidedata_flags = (0, 0)