diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -450,8 +450,7 @@ def branches(ui, repo, active=False, clo
     """
 
     hexfunc = ui.debugflag and hex or short
-    activebranches = [encoding.tolocal(repo[n].branch())
-                            for n in repo.heads()]
+    activebranches = [repo[n].branch() for n in repo.heads()]
     def testactive(tag, node):
         realhead = tag in activebranches
         open = node in repo.branchheads(tag, closed=False)
@@ -462,8 +461,9 @@ def branches(ui, repo, active=False, clo
 
     for isactive, node, tag in branches:
         if (not active) or isactive:
+            encodedtag = encoding.tolocal(tag)
             if ui.quiet:
-                ui.write("%s\n" % tag)
+                ui.write("%s\n" % encodedtag)
             else:
                 hn = repo.lookup(node)
                 if isactive:
@@ -474,8 +474,8 @@ def branches(ui, repo, active=False, clo
                     notice = ' (closed)'
                 else:
                     notice = ' (inactive)'
-                rev = str(node).rjust(31 - encoding.colwidth(tag))
-                data = tag, rev, hexfunc(hn), notice
+                rev = str(node).rjust(31 - encoding.colwidth(encodedtag))
+                data = encodedtag, rev, hexfunc(hn), notice
                 ui.write("%s %s:%s%s\n" % data)
 
 def bundle(ui, repo, fname, dest=None, **opts):
@@ -1401,21 +1401,22 @@ def heads(ui, repo, *branchrevs, **opts)
         heads = []
         visitedset = set()
         for branchrev in branchrevs:
-            branch = repo[branchrev].branch()
+            branch = repo[encoding.fromlocal(branchrev)].branch()
+            encodedbranch = encoding.tolocal(branch)
             if branch in visitedset:
                 continue
             visitedset.add(branch)
             bheads = repo.branchheads(branch, start, closed=closed)
             if not bheads:
                 if not opts.get('rev'):
-                    ui.warn(_("no open branch heads on branch %s\n") % branch)
+                    ui.warn(_("no open branch heads on branch %s\n") % encodedbranch)
                 elif branch != branchrev:
                     ui.warn(_("no changes on branch %s containing %s are "
                               "reachable from %s\n")
-                            % (branch, branchrev, opts.get('rev')))
+                            % (encodedbranch, branchrev, opts.get('rev')))
                 else:
                     ui.warn(_("no changes on branch %s are reachable from %s\n")
-                            % (branch, opts.get('rev')))
+                            % (encodedbranch, opts.get('rev')))
             if hideinactive:
                 bheads = [bhead for bhead in bheads if bhead in _heads]
             heads.extend(bheads)
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -318,16 +318,6 @@ class localrepository(repo.repository):
 
         return partial
 
-    def lbranchmap(self):
-        branchcache = {}
-        partial = self.branchmap()
-
-        # the branch cache is stored on disk as UTF-8, but in the local
-        # charset internally
-        for k, v in partial.iteritems():
-            branchcache[encoding.tolocal(k)] = v
-        return branchcache
-
     def branchmap(self):
         tip = self.changelog.tip()
         if self._branchcache is not None and self._branchcachetip == tip:
@@ -351,7 +341,7 @@ class localrepository(repo.repository):
         '''return a dict where branch names map to the tipmost head of
         the branch, open heads come before closed'''
         bt = {}
-        for bn, heads in self.lbranchmap().iteritems():
+        for bn, heads in self.branchmap().iteritems():
             head = None
             for i in range(len(heads)-1, -1, -1):
                 h = heads[i]
@@ -1167,7 +1157,7 @@ class localrepository(repo.repository):
         '''
         if branch is None:
             branch = self[None].branch()
-        branches = self.lbranchmap()
+        branches = self.branchmap()
         if branch not in branches:
             return []
         # the cache returns heads ordered lowest to highest