diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1242,7 +1242,8 @@
                               **pycompat.strkwargs(args))
             if hook.hashook(repo.ui, 'pretxnclose-phase'):
                 cl = repo.unfiltered().changelog
-                for rev, (old, new) in tr.changes['phases'].items():
+                phasechanges = phases.phasechanges(tr.changes['phases'])
+                for rev, (old, new) in phasechanges:
                     args = tr.hookargs.copy()
                     node = hex(cl.node(rev))
                     args.update(phases.preparehookargs(node, old, new))
@@ -1277,7 +1278,7 @@
                                      checkambigfiles=_cachedfiles)
         tr.changes['revs'] = xrange(0, 0)
         tr.changes['obsmarkers'] = set()
-        tr.changes['phases'] = {}
+        tr.changes['phases'] = [set() for i in range(7)]
         tr.changes['bookmarks'] = {}
 
         tr.hookargs['txnid'] = txnid
@@ -1306,7 +1307,7 @@
 
                 if hook.hashook(repo.ui, 'txnclose-phase'):
                     cl = repo.unfiltered().changelog
-                    phasemv = sorted(tr.changes['phases'].items())
+                    phasemv = sorted(phases.phasechanges(tr.changes['phases']))
                     for rev, (old, new) in phasemv:
                         args = tr.hookargs.copy()
                         node = hex(cl.node(rev))
diff --git a/mercurial/phases.py b/mercurial/phases.py
--- a/mercurial/phases.py
+++ b/mercurial/phases.py
@@ -186,17 +186,38 @@
         headsbyphase[phase].append(node)
     return headsbyphase
 
+def phasechanges(data):
+    offset = len(allphases)
+    for tgtphase in allphases:
+        for rev in data[tgtphase + offset]:
+            srcphase = None
+            for phase in allphases:
+                if rev in data[phase]:
+                    srcphase = phase
+                    break
+            yield (rev, (srcphase, tgtphase))
+
 def _trackphasechange(data, rev, old, new):
-    """add a phase move the <data> dictionnary
+    """add a phase move the <data> sets
 
     If data is None, nothing happens.
     """
     if data is None:
         return
-    existing = data.get(rev)
-    if existing is not None:
-        old = existing[0]
-    data[rev] = (old, new)
+    assert old in allphases or old is None
+    assert new in allphases
+    offset = len(allphases)
+
+    if rev not in data[new + offset]:
+        found = False
+        for phase in allphases:
+            if phase == new:
+                data[phase + offset].add(rev)
+            elif rev in data[phase + offset]:
+                data[phase + offset].discard(rev)
+                found = True
+        if not found and old is not None:
+            data[old].add(rev)
 
 class phasecache(object):
     def __init__(self, repo, phasedefaults, _load=True):
diff --git a/tests/testlib/ext-phase-report.py b/tests/testlib/ext-phase-report.py
--- a/tests/testlib/ext-phase-report.py
+++ b/tests/testlib/ext-phase-report.py
@@ -1,11 +1,12 @@
 # tiny extension to report phase changes during transaction
 
 from __future__ import absolute_import
+from mercurial import phases
 
 def reposetup(ui, repo):
 
     def reportphasemove(tr):
-        for rev, move in sorted(tr.changes['phases'].iteritems()):
+        for rev, move in sorted(phases.phasechanges(tr.changes['phases'])):
             if move[0] is None:
                 ui.write(('test-debug-phase: new rev %d:  x -> %d\n'
                           % (rev, move[1])))