Make StringAtom use pointer equality and hashing StringAtom previously used string equality and hashing. The rationale was that it would ensure consistent ordering with standard containers. * This makes perfect sense for ordered containers, as operator< sorting lexicographically both makes sense and is frequently used. * This makes zero sense for operator==, as pointers can be equal iff contents are equal, so whether it uses string or pointer equality is an implementation detail. * This also makes no sense for hashing, as the C++ standard states that hashes are not required to be deterministic, and thus may be seeded upon binary start (though in practice this is not usually the case). Change-Id: I58eeba92bba7723f8a9792d78b5ab5de6a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/27480 Reviewed-by: Takuto Ikuta <tikuta@google.com> Commit-Queue: Matt Stark <msta@google.com>
diff --git a/src/gn/label.h b/src/gn/label.h index a831804..4ce1882 100644 --- a/src/gn/label.h +++ b/src/gn/label.h
@@ -75,19 +75,19 @@ bool Matches(const Label& other, const Label& default_toolchain) const; bool operator==(const Label& other) const { - return hash_ == other.hash_ && name_.SameAs(other.name_) && - dir_ == other.dir_ && toolchain_dir_ == other.toolchain_dir_ && - toolchain_name_.SameAs(other.toolchain_name_); + return hash_ == other.hash_ && name_ == other.name_ && dir_ == other.dir_ && + toolchain_dir_ == other.toolchain_dir_ && + toolchain_name_ == other.toolchain_name_; } bool operator!=(const Label& other) const { return !operator==(other); } bool operator<(const Label& other) const { // This custom comparison function uses the fact that SourceDir and // StringAtom values have very fast equality comparison to avoid - // un-necessary string comparisons when components are equal. + // unnecessary string comparisons when components are equal. if (dir_ != other.dir_) return dir_ < other.dir_; - if (!name_.SameAs(other.name_)) + if (name_ != other.name_) return name_ < other.name_; if (toolchain_dir_ != other.toolchain_dir_) @@ -100,7 +100,7 @@ // other object. bool ToolchainsEqual(const Label& other) const { return toolchain_dir_ == other.toolchain_dir_ && - toolchain_name_.SameAs(other.toolchain_name_); + toolchain_name_ == other.toolchain_name_; } size_t hash() const { return hash_; } @@ -121,9 +121,9 @@ size_t ComputeHash() const { size_t h0 = dir_.hash(); - size_t h1 = name_.ptr_hash(); + size_t h1 = name_.hash(); size_t h2 = toolchain_dir_.hash(); - size_t h3 = toolchain_name_.ptr_hash(); + size_t h3 = toolchain_name_.hash(); return ((h3 * 131 + h2) * 131 + h1) * 131 + h0; }
diff --git a/src/gn/source_dir.h b/src/gn/source_dir.h index e986925..26ca6b7 100644 --- a/src/gn/source_dir.h +++ b/src/gn/source_dir.h
@@ -122,12 +122,12 @@ } bool operator==(const SourceDir& other) const { - return value_.SameAs(other.value_); + return value_ == other.value_; } bool operator!=(const SourceDir& other) const { return !operator==(other); } bool operator<(const SourceDir& other) const { return value_ < other.value_; } - size_t hash() const { return value_.ptr_hash(); } + size_t hash() const { return value_.hash(); } private: friend class SourceFile;
diff --git a/src/gn/source_file.h b/src/gn/source_file.h index b2068a2..e1e6ec5 100644 --- a/src/gn/source_file.h +++ b/src/gn/source_file.h
@@ -97,7 +97,7 @@ } bool operator==(const SourceFile& other) const { - return value_.SameAs(other.value_); + return value_ == other.value_; } bool operator!=(const SourceFile& other) const { return !operator==(other); } bool operator<(const SourceFile& other) const { @@ -111,22 +111,13 @@ : std::strong_ordering::greater; } + size_t hash() const { return value_.hash(); } + struct PtrCompare { bool operator()(const SourceFile& a, const SourceFile& b) const noexcept { return StringAtom::PtrCompare()(a.value_, b.value_); } }; - struct PtrHash { - size_t operator()(const SourceFile& s) const noexcept { - return StringAtom::PtrHash()(s.value_); - } - }; - - struct PtrEqual { - bool operator()(const SourceFile& a, const SourceFile& b) const noexcept { - return StringAtom::PtrEqual()(a.value_, b.value_); - } - }; private: friend class SourceDir; @@ -142,9 +133,7 @@ template <> struct hash<SourceFile> { - std::size_t operator()(const SourceFile& v) const { - return SourceFile::PtrHash()(v); - } + std::size_t operator()(const SourceFile& v) const { return v.hash(); } }; } // namespace std
diff --git a/src/gn/string_atom.h b/src/gn/string_atom.h index 51aa8d5..2c9b16c 100644 --- a/src/gn/string_atom.h +++ b/src/gn/string_atom.h
@@ -15,44 +15,29 @@ // when a program uses multiple instances that tend to use the same strings // (as happen very frequently in GN). // -// Note that default equality and comparison functions will compare the -// string content, not the pointers, ensuring that the behaviour of -// standard containers using StringAtom key types is the same as if -// std::string was used. +// Note that default equality and hashing functions compare and hash the +// underlying string pointers, ensuring fast O(1) operations since every +// unique string is interned. +// +// By contrast, default ordering functions (operator< and std::less) compare +// the string content lexicographically, ensuring that standard ordered +// containers have deterministic, predictable ordering. // // In addition, _ordered_ containers support heterogeneous lookups (i.e. // using an std::string_view, and by automatic conversion, a const char* // of const char[] literal) as a key type. // -// Additionally, it is also possible to implement very fast _unordered_ -// containers by using the StringAtom::Fast{Hash,Equal,Compare} structs, -// which will force containers to hash/compare pointer values instead, -// for example: +// Additionally, it is also possible to implement very fast pointer-ordered +// containers using the StringAtom::PtrCompare struct on ordered containers, +// forcing containers to compare pointer values instead, for example: // -// // A fast unordered set of unique strings. -// // -// // Implementation uses a hash table so performance will be bounded -// // by the string hash function. Does not support heterogeneous lookups. -// // -// using FastStringSet = std::unordered_set<StringAtom, -// StringAtom::PtrHash, -// StringAtom::PtrEqual>; +// // A fast set of unique strings, ordered by pointer. +// using FastStringSet = std::set<StringAtom, StringAtom::PtrCompare>; // -// // A fast unordered set of unique strings. -// // -// // Implementation uses a balanced binary tree so performance will -// // be bounded by string comparisons. Does support heterogeneous lookups, -// // but not that this does not extend to the [] operator, only to the -// // find() method. -// // -// using FastStringSet = std::set<StringAtom, StringAtom::PtrCompare> -// -// // A fast unordered { string -> VALUE } map. -// // -// // Implementation uses a balanced binary tree. Supports heterogeneous -// // lookups. +// // A fast { string -> VALUE } map, ordered by pointer. // template <typename VALUE> -// using FastStringMap = std::map<StringAtom, VALUE, StringAtom::PtrCompare> +// using FastStringMap = std::map<StringAtom, VALUE, +// StringAtom::PtrCompare>; // class StringAtom { public: @@ -92,58 +77,37 @@ // Implicit conversions. operator std::string_view() const { return {value_}; } - // Returns true iff this is the same key. - // Note that the default comparison functions compare the value instead - // in order to use them in standard containers without surprises by - // default. - bool SameAs(const StringAtom& other) const { + // Default comparison functions. + // Returns true iff string_view(*this) == string_view(other) + bool operator==(const StringAtom& other) const { + // The string contents are equal iff they point to the same underlying + // string. return &value_ == &other.value_; } - // Default comparison functions. - bool operator==(const StringAtom& other) const { - return value_ == other.value_; - } - - bool operator!=(const StringAtom& other) const { - return value_ != other.value_; - } + bool operator!=(const StringAtom& other) const { return !(*this == other); } bool operator<(const StringAtom& other) const { - // Avoid one un-necessary string comparison if values are equal. - if (SameAs(other)) + // Avoid one unnecessary string comparison if values are equal. + if (*this == other) return false; return value_ < other.value_; } - size_t hash() const { return std::hash<std::string>()(value_); } + // Pointer-based hash for fast O(1) hashing in unordered containers. + size_t hash() const { return std::hash<const std::string*>()(&value_); } - // Use the following method and structs to implement containers that - // use StringAtom values as keys, but only compare/hash the pointer - // values for speed. + // Use the following struct to implement containers that order based on + // the StringAtom pointer value for speed. // // E.g.: - // using FastSet = std::unordered_set<StringAtom, PtrHash, PtrEqual>; + // using FastSet = std::set<StringAtom, PtrCompare>; // using FastMap = std::map<StringAtom, Value, PtrCompare>; // - // IMPORTANT: Note that FastMap above is ordered based in the StringAtom - // pointer value, not the string content. + // IMPORTANT: Note that containers using PtrCompare are ordered based on the + // StringAtom pointer value, not the string content. // - size_t ptr_hash() const { return std::hash<const std::string*>()(&value_); } - - struct PtrHash { - size_t operator()(const StringAtom& key) const noexcept { - return key.ptr_hash(); - } - }; - - struct PtrEqual { - bool operator()(const StringAtom& a, const StringAtom& b) const noexcept { - return &a.value_ == &b.value_; - } - }; - struct PtrCompare { bool operator()(const StringAtom& a, const StringAtom& b) const noexcept { return &a.value_ < &b.value_;
diff --git a/src/gn/string_atom_unittest.cc b/src/gn/string_atom_unittest.cc index 0e820a6..3d9227f 100644 --- a/src/gn/string_atom_unittest.cc +++ b/src/gn/string_atom_unittest.cc
@@ -37,10 +37,16 @@ auto foo = StringAtom("foo"); auto bar = StringAtom("bar"); auto zoo = StringAtom("zoo"); + auto foo2 = StringAtom("foo"); EXPECT_TRUE(bar < foo); EXPECT_TRUE(foo < zoo); EXPECT_TRUE(bar < zoo); + + EXPECT_EQ(foo, foo2); + EXPECT_NE(foo, bar); + + EXPECT_EQ(std::hash<StringAtom>()(foo), std::hash<StringAtom>()(foo2)); } TEST(StringAtomTest, NormalSet) {