diff -r 8ef9cdffad6a -r e9a2e1c77f28 hgext/journal.py
--- a/hgext/journal.py	Fri Jul 21 15:28:52 2023 +0200
+++ b/hgext/journal.py	Fri Jul 21 15:26:15 2023 +0200
@@ -127,7 +127,10 @@
     repo = store._repo
     if util.safehasattr(repo, 'journal'):
         oldmarks = bookmarks.bmstore(repo)
-        for mark, value in store.items():
+        all_marks = set(b for b, n in oldmarks.items())
+        all_marks.update(b for b, n in store.items())
+        for mark in sorted(all_marks):
+            value = store.get(mark, repo.nullid)
             oldvalue = oldmarks.get(mark, repo.nullid)
             if value != oldvalue:
                 repo.journal.record(bookmarktype, mark, oldvalue, value)