make ConstStringTable use DenseMap rather than std::map

[llunak]

Summary

The ordering is not needed, and DenseMap is faster. I can measure time spent in the SaveToCache() calls reduced to ~40% during LLDB startup (and the total startup cost reduced to ~70%).

[JDevlieghere]

I feel like this came up in the past and there was a reason an unordered map couldn't work? Maybe I'm confusing this with something else. Added Pavel as he would certainly know.

Could we use a llvm::DenseMap here, as it's supposedly even faster than its STL counterpart?

(Adding myself as a reviewer too so this shows up in my review queue)

[llunak]

In D122980#3424636, @JDevlieghere wrote:

Could we use a llvm::DenseMap here, as it's supposedly even faster than its STL counterpart?

Yes, it is, I've updated the patch.

[labath]

In D122980#3424636, @JDevlieghere wrote:

I feel like this came up in the past and there was a reason an unordered map couldn't work? Maybe I'm confusing this with something else. Added Pavel as he would certainly know.

This is pretty new code, so I think you must be thinking of something else.

I don't see any reason why this would have to be a std::map. I think the code just hasn't been optimized yet.

[JDevlieghere]

In D122980#3426196, @labath wrote:

In D122980#3424636, @JDevlieghere wrote:

I feel like this came up in the past and there was a reason an unordered map couldn't work? Maybe I'm confusing this with something else. Added Pavel as he would certainly know.

This is pretty new code, so I think you must be thinking of something else.

I don't see any reason why this would have to be a std::map. I think the code just hasn't been optimized yet.

Cool, thanks for confirming. LGTM!

lldb/include/lldb/Core/DataFileCache.h

 //===-- DataFileCache.h -----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_CORE_DATAFILECACHE_H
 #define LLDB_CORE_DATAFILECACHE_H
 
 #include "lldb/Utility/FileSpec.h"
 #include "lldb/Utility/Status.h"
 #include "lldb/Utility/UUID.h"
 #include "lldb/lldb-forward.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Caching.h"
 #include <mutex>
 
 namespace lldb_private {
 
 /// This class enables data to be cached into a directory using the llvm
 /// caching code. Data can be stored and accessed using a unique string key.
 /// The data will be stored in the directory that is specified in the
public:
   ///   string. Duplicate strings that get inserted will return the same
   ///   byte offset.
   uint32_t Add(ConstString s);
 
   bool Encode(DataEncoder &encoder);
 
 private:
   std::vector<ConstString> m_strings;
-  std::map<ConstString, uint32_t> m_string_to_offset;
+  llvm::DenseMap<ConstString, uint32_t> m_string_to_offset;
   /// Skip one byte to start the string table off with an empty string.
   uint32_t m_next_offset = 1;
 };
 
 /// Many cache files require string tables to store data efficiently. This
 /// class helps give out strings from a string table that was read from a
 /// cache file.
 class StringTableReader {