diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -1827,8 +1827,8 @@ def debugdiscovery(ui, repo, remoteurl="
                                                                 force=True)
             common = set(common)
             if not opts.get('nonheads'):
-                ui.write(("unpruned common: %s\n") % " ".join([short(n)
-                                                            for n in common]))
+                ui.write(("unpruned common: %s\n") %
+                         " ".join(sorted(short(n) for n in common)))
                 dag = dagutil.revlogdag(repo.changelog)
                 all = dag.ancestorset(dag.internalizeall(common))
                 common = dag.externalizeall(dag.headsetofconnecteds(all))
@@ -1837,7 +1837,8 @@ def debugdiscovery(ui, repo, remoteurl="
         common = set(common)
         rheads = set(hds)
         lheads = set(repo.heads())
-        ui.write(("common heads: %s\n") % " ".join([short(n) for n in common]))
+        ui.write(("common heads: %s\n") %
+                 " ".join(sorted(short(n) for n in common)))
         if lheads <= common:
             ui.write(("local is subset\n"))
         elif rheads <= common:
@@ -2134,7 +2135,8 @@ def debugobsolete(ui, repo, precursor=No
                 ui.write(' ')
                 ui.write(hex(repl))
             ui.write(' %X ' % m._data[2])
-            ui.write(m.metadata())
+            ui.write('{%s}' % (', '.join('%r: %r' % t for t in
+                                         sorted(m.metadata().items()))))
             ui.write('\n')
 
 @command('debugpushkey', [], _('REPO NAMESPACE [KEY OLD NEW]'))
diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -36,8 +36,8 @@ Small superset:
   % -- a -> b tree
   comparing with b
   searching for changes
-  unpruned common: b5714e113bc0 66f7d451a68b 01241442b3c2
-  common heads: b5714e113bc0 01241442b3c2
+  unpruned common: 01241442b3c2 66f7d451a68b b5714e113bc0
+  common heads: 01241442b3c2 b5714e113bc0
   local is subset
   
   % -- a -> b set
@@ -45,14 +45,14 @@ Small superset:
   query 1; heads
   searching for changes
   all local heads known remotely
-  common heads: b5714e113bc0 01241442b3c2
+  common heads: 01241442b3c2 b5714e113bc0
   local is subset
   
   % -- b -> a tree
   comparing with a
   searching for changes
-  unpruned common: b5714e113bc0 01241442b3c2
-  common heads: b5714e113bc0 01241442b3c2
+  unpruned common: 01241442b3c2 b5714e113bc0
+  common heads: 01241442b3c2 b5714e113bc0
   remote is subset
   
   % -- b -> a set
@@ -60,7 +60,7 @@ Small superset:
   query 1; heads
   searching for changes
   all remote heads known locally
-  common heads: b5714e113bc0 01241442b3c2
+  common heads: 01241442b3c2 b5714e113bc0
   remote is subset
 
 
@@ -89,7 +89,7 @@ Many new:
   % -- b -> a tree
   comparing with a
   searching for changes
-  unpruned common: bebd167eb94d 66f7d451a68b
+  unpruned common: 66f7d451a68b bebd167eb94d
   common heads: bebd167eb94d
   
   % -- b -> a set
@@ -128,7 +128,7 @@ Both sides many new with stub:
   % -- b -> a tree
   comparing with a
   searching for changes
-  unpruned common: 66f7d451a68b 2dc09a01254d
+  unpruned common: 2dc09a01254d 66f7d451a68b
   common heads: 2dc09a01254d
   
   % -- b -> a set