diff --git a/src/common/windows/pdb_source_line_writer.cc b/src/common/windows/pdb_source_line_writer.cc
index 363ce7d..dace886 100644
--- a/src/common/windows/pdb_source_line_writer.cc
+++ b/src/common/windows/pdb_source_line_writer.cc
@@ -37,8 +37,11 @@
 #include <ImageHlp.h>
 #include <stdio.h>
 
+#include <algorithm>
 #include <limits>
+#include <map>
 #include <set>
+#include <utility>
 
 #include "common/windows/dia_util.h"
 #include "common/windows/guid_string.h"
@@ -106,6 +109,8 @@
 
 using std::vector;
 
+typedef std::multimap<DWORD, CComPtr<IDiaSymbol>> SymbolMultimap;
+
 // A helper class to scope a PLOADED_IMAGE.
 class AutoImage {
  public:
@@ -166,6 +171,16 @@
   return false;
 }
 
+// Computing undecorated names for all symbols is expensive, so we compare
+// decorated names.
+bool CompareSymbols(const SymbolMultimap::value_type& a,
+                    const SymbolMultimap::value_type& b) {
+  BSTR a_name, b_name;
+  a.second->get_name(&a_name);
+  b.second->get_name(&b_name);
+  return wcscmp(a_name, b_name) < 0;
+}
+
 }  // namespace
 
 PDBSourceLineWriter::PDBSourceLineWriter() : output_(NULL) {
@@ -400,7 +415,7 @@
   CComPtr<IDiaEnumSymbols> symbols = NULL;
 
   // Find all function symbols first.
-  std::set<DWORD> rvas;
+  SymbolMultimap rva_symbols;
   hr = global->findChildren(SymTagFunction, NULL, nsNone, &symbols);
 
   if (SUCCEEDED(hr)) {
@@ -408,9 +423,10 @@
 
     while (SUCCEEDED(symbols->Next(1, &symbol, &count)) && count == 1) {
       if (SUCCEEDED(symbol->get_relativeVirtualAddress(&rva))) {
-        // To maintain existing behavior of one symbol per address, place the
-        // rva onto a set here to uniquify them.
-        rvas.insert(rva);
+        // Place the symbols into a multimap indexed by rva, so we can choose
+        // the apropriate symbol name to use when multiple symbols share an
+        // address.
+        rva_symbols.insert(std::make_pair(rva, symbol));
       } else {
         fprintf(stderr, "get_relativeVirtualAddress failed on the symbol\n");
         return false;
@@ -432,8 +448,9 @@
 
     while (SUCCEEDED(symbols->Next(1, &symbol, &count)) && count == 1) {
       if (SUCCEEDED(symbol->get_relativeVirtualAddress(&rva))) {
-        if (rvas.count(rva) == 0) {
-          rvas.insert(rva); // Keep symbols in rva order.
+        if (rva_symbols.find(rva) == rva_symbols.end()) {
+          // Keep symbols in rva order.
+          rva_symbols.insert(std::make_pair(rva, symbol));
           public_only_rvas.insert(rva);
         }
       } else {
@@ -447,40 +464,29 @@
     symbols.Release();
   }
 
-  std::set<DWORD>::iterator it;
-
-  // For each rva, dump the first symbol DIA knows about at the address.
-  for (it = rvas.begin(); it != rvas.end(); ++it) {
-    CComPtr<IDiaSymbol> symbol = NULL;
-    // If the symbol is not in the public list, look for SymTagFunction. This is
-    // a workaround to a bug where DIA will hang if searching for a private
-    // symbol at an address where only a public symbol exists.
-    // See http://connect.microsoft.com/VisualStudio/feedback/details/722366
-    if (public_only_rvas.count(*it) == 0) {
-      if (SUCCEEDED(session_->findSymbolByRVA(*it, SymTagFunction, &symbol))) {
-        // Sometimes findSymbolByRVA returns S_OK, but NULL.
-        if (symbol) {
-          if (!PrintFunction(symbol, symbol))
-            return false;
-          symbol.Release();
-        }
-      } else {
-        fprintf(stderr, "findSymbolByRVA SymTagFunction failed\n");
+  // For each rva, dump one symbol at the address.
+  SymbolMultimap::iterator it = rva_symbols.begin();
+  while (it != rva_symbols.end()) {
+    std::pair<SymbolMultimap::iterator, SymbolMultimap::iterator> symbol_range =
+      rva_symbols.equal_range(it->first);
+    // Find the minimum symbol by name to make the output more consistent
+    // between runs on different releases of the same module, in the case of
+    // multiple symbols sharing an address.
+    SymbolMultimap::iterator least_symbol_iter =
+      std::min_element(symbol_range.first, symbol_range.second, CompareSymbols);
+    CComPtr<IDiaSymbol> symbol = least_symbol_iter->second;
+    // Only print public symbols if there is no function symbol for the address.
+    if (public_only_rvas.count(it->first) == 0) {
+      if (!PrintFunction(symbol, symbol))
         return false;
-      }
-    } else if (SUCCEEDED(session_->findSymbolByRVA(*it,
-                                                   SymTagPublicSymbol,
-                                                   &symbol))) {
-      // Sometimes findSymbolByRVA returns S_OK, but NULL.
-      if (symbol) {
-        if (!PrintCodePublicSymbol(symbol))
-          return false;
-        symbol.Release();
-      }
+      symbol.Release();
     } else {
-      fprintf(stderr, "findSymbolByRVA SymTagPublicSymbol failed\n");
-      return false;
+      if (!PrintCodePublicSymbol(symbol))
+        return false;
+      symbol.Release();
     }
+
+    it = symbol_range.second;
   }
 
   // When building with PGO, the compiler can split functions into