[ADT] Add CachedHashString.

[jlebar]

Summary

This is like CachedHashStringRef, but owns its data.

This lets us use strings inside of DenseMaps.

[timshen]

llvm/include/llvm/ADT/CachedHashString.h

11

CachedHashString is not like std::string, because it doesn't support operations like operator+=. :)

24

It's not used, is it?

94

It is unfortunate to implement some of the std::string functionalities from scratch. Is there a way to implement it in terms of std::string?

[timshen]

llvm/include/llvm/ADT/CachedHashString.h

94

More specifically, I'm asking for a member function string& val(); that returns the underlying std::string object (it needs to exist first), so that CachedHashString compose better with other APIs that don't care about hashing.

[jlebar]

llvm/include/llvm/ADT/CachedHashString.h

94

We could do this, but at the cost of more than doubling its storage.

Right now this class takes two words of space on 64-bit platforms. sizeof(std::string) is 32 bytes (with whatever stdlib gcc.godbolt.org uses), so already 4 words. Plus we'd need extra space for storing the two is-empty and is-tombstone bits. (We could also use this space for storing the hash code.) So our modified class would be 40 bytes, instead of 16.

That's pretty significant for a class that's meant to be stored in open-addressing hashtables.

I agree it's unfortunate -- if you have a better idea I'm all ears.

[jlebar]

Address Tim's comments.

[jlebar]

Rafael, Tim and I were looking for a second opinion -- does this seem to you like a sane thing to do? The immediate problem I'm trying to solve here is to convert code that's using SmallSetVector<std::string>, which doesn't work after converting SmallSetVector to use DenseSet, because you can't store an std::string in a DenseSet.

Longer term, I hope to use something like this class to let us replace StringSet, StringMap, &co, but what we end up with in order to make that work may look quite different from this. I was just planning to change it as necessary.

[• rafael]

llvm/include/llvm/ADT/CachedHashString.h

167

It is common practice to declare == out of class.

Do you still need if you declare a StringRef() operator?

[jlebar]

Address Rafael's comments (get rid of explicit operators in favor of implicit
conversions to StringPiece).

[jlebar]

Thank you for the review, Rafael. I like using implicit casts -- this is better!

[mehdi_amini]

Couldn't CachedHashString just wrap a CachedHashStringRef?

Or even have a single implementation:

template<bool Owning>
class CachedHashStringRefBase {
  ...

  ~CachedHashStringRefBase() {
    if (owning) delete...
}
using CachedHashStringRef = CachedHashStringRefBase<false>;
using CachedHashString = CachedHashStringRefBase<true>;

[• rafael]

LGTM.

I am not c++ expert, but this is probably good enough for post commit review.

[timshen]

llvm/include/llvm/ADT/CachedHashString.h

119

How do you feel about this:

if (this != Other) {
  ~CachedHashString();
  new (this) CachedHashString(Other);
}
return *this;

Likewise for the move assign.

[dblaikie]

llvm/include/llvm/ADT/CachedHashString.h

119

You can potentially just use the unified copy/move op roughly:

foo &operator=(foo f) {
  swap(*this, f);
}

(you can actually implement the assignment here rather than use a custom swap - then rely on std::swap to be cheap enough - or the other way around, whichever's better/worth it)

& then you do need to implement copy and move ctors, but you've already got those.

[jlebar]

llvm/include/llvm/ADT/CachedHashString.h

119

I like this, because the swap function is simple to write. It lets me avoid the problem of blowing up on

CachedHashString x;
x = x;

which I had before.

Thank you for the suggestion!

[jlebar]

Use swap to implement copy assignment and move.

[mehdi_amini]

In D25645#574862, @mehdi_amini wrote:

Couldn't CachedHashString just wrap a CachedHashStringRef?

Or even have a single implementation:

template<bool Owning>
class CachedHashStringRefBase {
  ...

  ~CachedHashStringRefBase() {
    if (owning) delete...
}
using CachedHashStringRef = CachedHashStringRefBase<false>;
using CachedHashString = CachedHashStringRefBase<true>;

Ping?

[jlebar]

In D25645#576823, @mehdi_amini wrote:

In D25645#574862, @mehdi_amini wrote:

Couldn't CachedHashString just wrap a CachedHashStringRef?

Or even have a single implementation:

template<bool Owning>
class CachedHashStringRefBase {
  ...

  ~CachedHashStringRefBase() {
    if (owning) delete...
}
using CachedHashStringRef = CachedHashStringRefBase<false>;
using CachedHashString = CachedHashStringRefBase<true>;

Ping?

Sorry, forgot to respond to this.

I don't think this is a good idea, because the two classes do not have the same API. In particular, CachedHashString has a conversion to CachedHashStringRef. We would have to enable-if this away.

Also the bodies of about half of the functions would be different. At this point we would not be gaining much from this additional layer of indirection.

llvm/include/llvm/ADT/CachedHashString.h

 //===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines CachedHashString and CachedHashStringRef.  These are like
 // std::string and StringRef, except they store their hash in addition to their
 // string data.
 //
 // Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
 // (because, unlike std::string, CachedHashString lets us have empty and
 // tombstone values).
 //
-// TODO: Add CachedHashString.
-//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_CACHED_HASH_STRING_H
 #define LLVM_ADT_CACHED_HASH_STRING_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 /// A container which contains a StringRef plus a precomputed hash.
 class CachedHashStringRef {
   const char *P;
   uint32_t Size;
   uint32_t Hash;
template <> struct DenseMapInfo<CachedHashStringRef> {
   }
   static bool isEqual(const CachedHashStringRef &LHS,
                       const CachedHashStringRef &RHS) {
     return LHS.hash() == RHS.hash() &&
            DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
   }
 };
 
+/// A container which contains a string, which it owns, plus a precomputed hash.
+///
+/// We do not null-terminate the string.
+class CachedHashString {
+  friend struct DenseMapInfo<CachedHashString>;
+
+  char *P;
+  uint32_t Size;
+  uint32_t Hash;
+
+  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
+  static char *getTombstoneKeyPtr() {
+    return DenseMapInfo<char *>::getTombstoneKey();
+  }
+
+  bool isEmptyOrTombstone() const {
+    return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
+  }
+
+  explicit CachedHashString(char *EmptyOrTombstonePtr)
+      : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
+    assert(isEmptyOrTombstone());
+  }
+
+  // TODO: Use small-string optimization to avoid allocating.
+
+public:
+  // Explicit because copying and hashing a string isn't free.
+  explicit CachedHashString(StringRef S)
+      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
+
+  CachedHashString(StringRef S, uint32_t Hash)
+      : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
+    memcpy(P, S.data(), S.size());
+  }
+
+  // Ideally this class would not be copyable.  But SetVector requires copyable
+  // keys, and we want this to be usable there.
+  CachedHashString(const CachedHashString &Other)
+      : Size(Other.Size), Hash(Other.Hash) {
+    if (Other.isEmptyOrTombstone()) {
+      P = Other.P;
+    } else {
+      P = new char[Size];
+      memcpy(P, Other.P, Size);
+    }
+  }
+
+  CachedHashString &operator=(const CachedHashString &Other) {
+    if (!isEmptyOrTombstone())
+      delete[] P;
+
+    Size = Other.Size;
+    Hash = Other.Hash;
+
+    if (Other.isEmptyOrTombstone())
+      P = Other.P;
+    else {
+      P = new char[Size];
+      memcpy(P, Other.P, Size);
+    }
+
+    return *this;
+  }
+
+  CachedHashString(CachedHashString &&Other) LLVM_NOEXCEPT : P(Other.P),
+                                                             Size(Other.Size),
+                                                             Hash(Other.Hash) {
+    Other.P = getEmptyKeyPtr();
+  }
+
+  CachedHashString &operator=(CachedHashString &&Other) LLVM_NOEXCEPT {
+    Size = Other.Size;
+    Hash = Other.Hash;
+
+    if (!isEmptyOrTombstone())
+      delete[] P;
+
+    P = Other.P;
+    Other.P = getEmptyKeyPtr();
+    return *this;
+  }
+
+  ~CachedHashString() {
+    if (!isEmptyOrTombstone())
+      delete[] P;
+  }
+
+  StringRef val() const { return StringRef(P, Size); }
+  uint32_t size() const { return Size; }
+  uint32_t hash() const { return Hash; }
+
+  friend raw_ostream &operator<<(raw_ostream &OS, const CachedHashString &S) {
+    OS << S.val();
+    return OS;
+  }
+
+  friend bool operator==(const CachedHashString &LHS, StringRef RHS) {
+    return LHS.val() == RHS;
+  }
+  friend bool operator!=(const CachedHashString &LHS, StringRef RHS) {
+    return LHS.val() != RHS;
+  }
+};
+
+template <> struct DenseMapInfo<CachedHashString> {
+  static CachedHashString getEmptyKey() {
+    return CachedHashString(CachedHashString::getEmptyKeyPtr());
+  }
+  static CachedHashString getTombstoneKey() {
+    return CachedHashString(CachedHashString::getTombstoneKeyPtr());
+  }
+  static unsigned getHashValue(const CachedHashString &S) {
+    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
+    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
+    return S.hash();
+  }
+  static bool isEqual(const CachedHashString &LHS,
+                      const CachedHashString &RHS) {
+    if (LHS.hash() != RHS.hash())
+      return false;
+    if (LHS.P == CachedHashString::getEmptyKeyPtr())
+      return RHS.P == CachedHashString::getEmptyKeyPtr();
+    if (LHS.P == CachedHashString::getTombstoneKeyPtr())
+      return RHS.P == CachedHashString::getTombstoneKeyPtr();
+
+    // This is safe because if RHS.P is the empty or tombstone key, it will have
+    // length 0, so we'll never dereference its pointer.
+    return LHS.val() == RHS.val();
+  }
+};
+
 } // namespace llvm
 
 #endif