History log of /external/llvm/unittests/ADT/HashingTest.cpp
Revision Date Author Comments (<<< Hide modified files) (Show modified files >>>)
4c5e43da7792f75567b693105cc53e3f1992ad98 08-Apr-2015 Pirama Arumuga Nainar <pirama@google.com> Update aosp/master llvm for rebase to r233350

Change-Id: I07d935f8793ee8ec6b7da003f6483046594bca49
/external/llvm/unittests/ADT/HashingTest.cpp
ebe69fe11e48d322045d5949c83283927a0d790b 23-Mar-2015 Stephen Hines <srhines@google.com> Update aosp/master LLVM for rebase to r230699.

Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9
/external/llvm/unittests/ADT/HashingTest.cpp
c6a4f5e819217e1e12c458aed8e7b122e23a3a58 21-Jul-2014 Stephen Hines <srhines@google.com> Update LLVM for rebase to r212749.

Includes a cherry-pick of:
r212948 - fixes a small issue with atomic calls

Change-Id: Ib97bd980b59f18142a69506400911a6009d9df18
/external/llvm/unittests/ADT/HashingTest.cpp
36b56886974eae4f9c5ebc96befd3e7bfe5de338 24-Apr-2014 Stephen Hines <srhines@google.com> Update to LLVM 3.5a.

Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617
/external/llvm/unittests/ADT/HashingTest.cpp
d9b0b025612992a0b724eeca8bdf10b1d7a5c355 02-Jun-2012 Benjamin Kramer <benny.kra@googlemail.com> Fix typos found by http://github.com/lyda/misspell-check

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
d4d8b2a7f6d29b44cbc084b49042f44ef109da0c 07-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Add support to the hashing infrastructure for automatically hashing both
integral and enumeration types. This is accomplished with a bit of
template type trait magic. Thanks to Richard Smith for the core idea
here to detect viable types by detecting the set of types which can be
default constructed in a template parameter.

This is used (in conjunction with a system for detecting nullptr_t
should it exist) to provide an is_integral_or_enum type trait that
doesn't need a whitelist or direct compiler support.

With this, the hashing is extended to the more general facility. This
will be used in a subsequent commit to hashing more things, but I wanted
to make sure the type trait magic went through the build bots separately
in case other compilers don't like this formulation.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152217 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
9406da6e664a24c8e408cbba63daf162ca166ed9 04-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Teach the hashing facilities how to hash std::string objects.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152000 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
21d60d51618e03a970aa4c00a0d157abceedb3e7 04-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Split this test up into two smaller, and more focused tests.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151999 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
5fa6f5bc2e29610a212c56b9f6b39469f510fc39 03-Mar-2012 Francois Pichet <pichet2000@gmail.com> Move the NonPOD struct out of the anonymous namespace instead of adding llvm:: everywhere to fix the HashingTest on MSVC .

chandlerc proposed this better solution on IRC.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151974 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
2547e7faba2b0511b88cfd2a187c072612105600 03-Mar-2012 Francois Pichet <pichet2000@gmail.com> Fixes the Hashing tests on MSVC by adding llvm:: prefix to hash_value function call.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151971 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
edf24a8be491b35f77951614d242458cf2c54669 03-Mar-2012 NAKAMURA Takumi <geek4civic@gmail.com> unittests/ADT/HashingTest.cpp: Temporarily disable a new test introduced in r151891, to appease msvc.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151970 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
1c1448984d43f1f02c0235d35ebe8460c9b57afd 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Simplify the pair optimization. Rather than using complex type traits,
just ensure that the number of bytes in the pair is the sum of the bytes
in each side of the pair. As long as thats true, there are no extra
bytes that might be padding.

Also add a few tests that previously would have slipped through the
checking. The more accurate checking mechanism catches these and ensures
they are handled conservatively correctly.

Thanks to Duncan for prodding me to do this right and more simply.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151891 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
c3f99182be33fd5c42e94539c566c476a59589bc 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Add a golden data test that I missed somehow the first time around.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151886 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
4fc5bdf16e1dc54632fd844c81af61c3c574d9cf 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Fix bad indenting that was left over from cut/paste of the golden values
for 32-bit builds in here.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151885 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
4d628e200f7133e353c38806b57a229ef6ad2ab4 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> We really want to hash pairs of directly-hashable data as directly
hashable data. This matters when we have pair<T*, U*> as a key, which is
quite common in DenseMap, etc. To that end, we need to detect when this
is safe. The requirements on a generic std::pair<T, U> are:

1) Both T and U must satisfy the existing is_hashable_data trait. Note
that this includes the requirement that T and U have no internal
padding bits or other bits not contributing directly to equality.
2) The alignment constraints of std::pair<T, U> do not require padding
between consecutive objects.
3) The alignment constraints of U and the size of T do not conspire to
require padding between the first and second elements.

Grow two somewhat magical traits to detect this by forming a pod
structure and inspecting offset artifacts on it. Hopefully this won't
cause any compilers to panic.

Added and adjusted tests now that pairs, even nested pairs, are treated
as just sequences of data.

Thanks to Jeffrey Yasskin for helping me sort through this and reviewing
the somewhat subtle traits.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151883 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
c7384cfc7addb5d2818ac0bb4492778f28183c49 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Add support for hashing pairs by delegating to each sub-object. There is
an open question of whether we can do better than this by treating pairs
as boring data containers and directly hashing the two subobjects. This
at least makes the API reasonable.

In order to make this change, I reorganized the header a bit. I lifted
the declarations of the hash_value functions up to the top of the header
with their doxygen comments as these are intended for users to interact
with. They shouldn't have to wade through implementation details. I then
defined them at the very end so that they could be defined in terms of
hash_combine or any other hashing infrastructure.

Added various pair-hashing unittests.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151882 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
4166989f10eaecfb357551788a3d91275e75f119 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Remove the misguided extension here that reserved two special values in
the hash_code. I'm not sure what I was thinking here, the use cases for
special values are in the *keys*, not in the hashes of those keys.

We can always resurrect this if needed, or clients can accomplish the
same goal themselves. This makes the general case somewhat faster (~5
cycles faster on my machine) and smaller with less branching.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151865 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
5a491ca98e1ac6fd8ae2f0e71a4ee5777e1a1ae4 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Re-disable the debug output. The comment is there explaining why we want
to keep this around -- updating golden tests is annoying otherwise.

Thanks to Benjamin for pointing this omission out on IRC.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151860 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
97312941711d0cf436399d7b46f77bbf2736461b 02-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Provide the 32-bit variant of the golden tests. Not sure how I forgot to
do this initially, sorry.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151857 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
0b66c6fca22e85f732cf58f459a06c06833d1882 01-Mar-2012 Chandler Carruth <chandlerc@gmail.com> Rewrite LLVM's generalized support library for hashing to follow the API
of the proposed standard hashing interfaces (N3333), and to use
a modified and tuned version of the CityHash algorithm.

Some of the highlights of this change:
-- Significantly higher quality hashing algorithm with very well
distributed results, and extremely few collisions. Should be close to
a checksum for up to 64-bit keys. Very little clustering or clumping of
hash codes, to better distribute load on probed hash tables.
-- Built-in support for reserved values.
-- Simplified API that composes cleanly with other C++ idioms and APIs.
-- Better scaling performance as keys grow. This is the fastest
algorithm I've found and measured for moderately sized keys (such as
show up in some of the uniquing and folding use cases)
-- Support for enabling per-execution seeds to prevent table ordering
or other artifacts of hashing algorithms to impact the output of
LLVM. The seeding would make each run different and highlight these
problems during bootstrap.

This implementation was tested extensively using the SMHasher test
suite, and pased with flying colors, doing better than the original
CityHash algorithm even.

I've included a unittest, although it is somewhat minimal at the moment.
I've also added (or refactored into the proper location) type traits
necessary to implement this, and converted users of GeneralHash over.

My only immediate concerns with this implementation is the performance
of hashing small keys. I've already started working to improve this, and
will continue to do so. Currently, the only algorithms faster produce
lower quality results, but it is likely there is a better compromise
than the current one.

Many thanks to Jeffrey Yasskin who did most of the work on the N3333
paper, pair-programmed some of this code, and reviewed much of it. Many
thanks also go to Geoff Pike Pike and Jyrki Alakuijala, the original
authors of CityHash on which this is heavily based, and Austin Appleby
who created MurmurHash and the SMHasher test suite.

Also thanks to Nadav, Tobias, Howard, Jay, Nick, Ahmed, and Duncan for
all of the review comments! If there are further comments or concerns,
please let me know and I'll jump on 'em.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151822 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp
1a4b19ef9b870d8c914bcd5ceb520a64a9a2cc52 18-Feb-2012 Talin <viridia@gmail.com> Hashing.h - utilities for hashing various data types.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150890 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/HashingTest.cpp