C++11 Feature-ish Proposal: align base::hash_map with unordered_map

[David Benjamin]

This is distinct from flat-out using unordered_map everywhere; I assume that still has library problems.

tl;dr: How does this CL look? https://codereview.chromium.org/612323010/

We have base/containers/hash_tables.h which uses various pre-C++11 hash_map (and hash_set and friends) implementations. But they all have random differences between each other.

1. MSVC hash_map requires a total order on the key[1], so we have to define otherwise unnecessary operator<'s.

2. Mumble mumble rvalue references?? I ran into this monster [2] trying to get ssl_session_cache_openssl.cc building on Windows. I wasn't able to get it working, but I'm not familiar with rvalue references. Switching to unordered_map made the error go away, so I didn't dig further.

3. std::hash and MSVC provide a hash for T* just hashes the pointer value. __gnu_cxx::hash does not. See [3] where we define the hash on COMPILER_GCC, but not COMPILER_MSVC. (There's lots of them.)

4. C++11 does not specialize hash<const char*>. so it's still the pointer value. As far as I can tell, both __gnu_cxx::hash and MSVC's stdext::hash_value specialize to hash the C string, despite their default comparisons comparing by pointer equality (!!?!?). [4] is the case I found in Chromium. It seems to want the pointer version anyway.

I propose we align all the behaviors around C++11 semantics in advance of actually switching to unordered_map. On MSVC, just use unordered_map. Others, continue to use what we have right now, but replace the default hash with one that matches C++11[5].

I wrote https://codercodereview.chromium.eview.chromium.org/612323010/. Try bots are green. Note: This CL uses C++11 type aliases which haven't actually been okayed yet.

Thoughts?

[1] http://msdn.microsoft.com/en-us/library/1s1byw77.aspx

[2] https://docs.google.com/document/d/1searlqq47oMsa7UUpVOHvrJQjO457oPi9TwkroyBJD8/edit?usp=sharing

[3] https://code.google.com/p/chromium/codesearch#chromium/src/cc/trees/layer_sorter.h&q=BASE_HASH_NAMESPACE&sq=package:chromium&type=cs&l=19

[4] https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/font_family_cache.h&q=case:yes%20hash_(multi)?(set%7Cmap)%5C%3C($%7C%5B%5E,%5D*char)&sq=package:chromium&type=cs&l=51

[5] I was going to suggest we go to std::tr1::unordered_map on other platforms, but stlport is a problem. Looking at the headers, it has std::tr1::unordered_map, but the hash looks like the pre-standard one.

[James Robinson]

On Thu, Oct 2, 2014 at 4:02 PM, David Benjamin <davi...@chromium.org> wrote:

This is distinct from flat-out using unordered_map everywhere; I assume that still has library problems.

tl;dr: How does this CL look? https://codereview.chromium.org/612323010/

tl;dr: It looks pretty big.

I like the idea of converging on std::unordered_{set,map}'s behavior, but think it will be better to try to categorize the differences and converge piece by piece.

- James

[David Benjamin]

On Thu Oct 02 2014 at 11:30:23 PM James Robinson <jam...@chromium.org> wrote:

tl;dr: It looks pretty big.

I like the idea of converging on std::unordered_{set,map}'s behavior, but think it will be better to try to categorize the differences and converge piece by piece.

The differences I'm aware of are in the original email. I could probably split 3 out and give GCC a T* specialization before doing the rest. That'd probably also separate out the mechanical changes in the CL. (There's only two bulk changes: get rid of the old MSVC-only hash function syntax, and get rid of any GCC-only hash functions covered by the T* specialization.)

Splitting it up more would temporarily diverge behaviors between MSVC and GCC; they'd disagree on whether const char * hashes as the pointer value or a C string, without compile failures if you expected the other one. (Right now they're both C string. Granted, this is pretty crazy as-is because the default comparison is pointer value.)

The nuisance is that flipping MSVC to std::unordered_map simultaneously fixes the key's requirements (1, 2) and the hash function (4). And so resolving the GCC side of (4) wants to be done at the same time, which is why it's all one CL.

(Alternatively, we could flip MSVC and override the default hash to match the pre-standard one. Then remove the override afterwards. But it didn't seem worth the bother.)

David

[David Benjamin]

Alright, here is the proposed split:
https://codereview.chromium.org/630503002/
https://codereview.chromium.org/623383002/

David

[Viet-Trung Luu]

I'm in favor of these changes, since they:

• remove differences between MSVC and everything else
• give us a reasonable path towards C++11 unordered_*

--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev

To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.

[David Benjamin]

To follow-up, this is now on trunk. Changes from before:

- hash<T*> now defaults to hash by pointer value on all platforms, not just MSVC.

- hash<const char*> and hash<char*> now also hash by pointer value, not C string. (But they compared by pointer equality by default, so this was basically useless anyway.)
- hash_map keys no longer need to define operator< on MSVC.

- Defining and calling a default hash function is now consistent across MSVC and non-MSVC. You can now just write:

namespace BASE_HASH_NAMESPACE {

template<>

struct hash<base::FilePath> {

  size_t operator()(const base::FilePath& f) const {

    return hash<base::FilePath::StringType>()(f.value());

  }

};

}  // namespace BASE_HASH_NAMESPACE

instead of

namespace BASE_HASH_NAMESPACE {

#if defined(COMPILER_GCC)

template<>

struct hash<base::FilePath> {

  size_t operator()(const base::FilePath& f) const {

    return hash<base::FilePath::StringType>()(f.value());

  }

};

#elif defined(COMPILER_MSVC)

inline size_t hash_value(const base::FilePath& f) {

  return hash_value(f.value());

}

#endif  // COMPILER

}  // namespace BASE_HASH_NAMESPACE

And once we're properly std::unordered_map we can just replace that BASE_HASH_NAMESPACE with std. (Amusingly the pre-standard MSVC one was actually shorter, but such is life.)

David