summaryrefslogtreecommitdiff
path: root/include/llvm/ADT/DenseMap.h
Commit message (Collapse)AuthorAge
* Rehash but don't grow when full of tombstones.Howard Hinnant2013-10-30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This problem was found and fixed by José Fonseca in March 2011 for SmallPtrSet, committed r128566. But as far as I can tell, all other llvm hash tables retain the same problem: the bucket count can grow without bound while size() remains near constant by repeated insert/erase cycles that tend to fill the container with tombstones. Here is a demo that has been reduced to a trivial case: int main() { llvm::DenseSet<unsigned> d; for (unsigned i = 0; i < 0xFFFFFFF; ++i) { d.insert(i); d.erase(i); } } While the container size() never grows above 1, the bucket count grows like this: nb = 64 nb = 128 nb = 256 nb = 512 nb = 1024 nb = 2048 nb = 4096 nb = 8192 nb = 16384 nb = 32768 nb = 65536 nb = 131072 nb = 262144 nb = 524288 nb = 1048576 nb = 2097152 nb = 4194304 nb = 8388608 nb = 16777216 nb = 33554432 nb = 67108864 nb = 134217728 nb = 268435456 The above program currently consumes a few GB ram. This patch brings the memory consumption down by several orders of magnitude, and keeps the bucket count at 64 for the above test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193689 91177308-0d34-0410-b5e6-96231b3b80d8
* Add warn_unused_result to empty() on various containers.Benjamin Kramer2013-09-13
| | | | | | empty() doesn't actually empty out the container, making this a common typo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190708 91177308-0d34-0410-b5e6-96231b3b80d8
* Calling the base class constructor from the derived class' initializer list. ↵Aaron Ballman2013-08-16
| | | | | | This matches DenseMap's behavior, and silences some warnings. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188528 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the assertion for now. This breaks lld.Dmitri Gribenko2013-08-07
| | | | | | | | | | | lld has a hashtable with StringRef keys; it needs to iterate over the keys in *insertion* order. This is currently implemented as std::vector<StringRef> + DenseMap<StringRef, T>. This will probably need a proper DenseMapInfo<StringRef> if we don't want to lose memory/performance by migrating to a different data structure. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187868 91177308-0d34-0410-b5e6-96231b3b80d8
* YAMLTraits.h: replace DenseMap that used a bad implementation of DenseMapInfoDmitri Gribenko2013-08-07
| | | | | | | | | | | for StringRef with a StringMap The bug is that the empty key compares equal to the tombstone key. Also added an assertion to DenseMap to catch similar bugs in future. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187866 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: Move the key into place when we use the move version of operator[].Benjamin Kramer2013-06-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183074 91177308-0d34-0410-b5e6-96231b3b80d8
* use static_cast to get rid of windows warning. Peng Cheng2013-05-01
| | | | | | warning C4244: 'argument' : conversion from 'uint64_t' to 'const unsigned int', possible loss of data git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180846 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unnecessary condtional assignment. The next line ignores the result ↵Craig Topper2013-02-13
| | | | | | of the assignment with the same condition. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175042 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix DenseMap when LLVM_HAS_RVALUE_REFERENCES is defined but equals 0.Joe Groff2013-01-14
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172454 91177308-0d34-0410-b5e6-96231b3b80d8
* Add DenseMap::insert(value_type&&) method.Joe Groff2013-01-14
| | | | | | | | Use the existing move implementation of the internal DenseMap::InsertIntoBucket method to provide a user-facing move insert method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172453 91177308-0d34-0410-b5e6-96231b3b80d8
* Whitespace.NAKAMURA Takumi2013-01-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171601 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: Appease -fstrict-aliasing on g++-4.4.NAKAMURA Takumi2013-01-05
| | | | | | | | | | | | With DenseMapInfo<Enum>, it is miscompiled on g++-4.4. static inline Enum getEmptyKey() { return Enum(<arbitrary int/unsigned value>); } isEauql(getEmptyKey(), ...) The compiler mis-assumes the return value is not aliased to Enum. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171600 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix warnings from llvm-gcc as seen on darwin10 (10.6).Alex Rosenberg2013-01-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171567 91177308-0d34-0410-b5e6-96231b3b80d8
* Sort the #include lines for the include/... tree with the script.Chandler Carruth2012-12-03
| | | | | | | | | | AKA: Recompile *ALL* the source code! This one went much better. No manual edits here. I spot-checked for silliness and grep-checked for really broken edits and everything seemed good. It all still compiles. Yell if you see something that looks goofy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169133 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch LLVM_USE_RVALUE_REFERENCES to LLVM_HAS_RVALUE_REFERENCES.Chandler Carruth2012-11-30
| | | | | | | | | | | | | | Rationale: 1) This was the name in the comment block. ;] 2) It matches Clang's __has_feature naming convention. 3) It matches other compiler-feature-test conventions. Sorry for the noise. =] I've also switch the comment block to use a \brief tag and not duplicate the name. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168996 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve DenseMap checks for power of 2 growth. Thanks for the tip JakobPete Cooper2012-10-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166609 91177308-0d34-0410-b5e6-96231b3b80d8
* Change DenseMap to use a power of 2 growth if one is given instead of the ↵Pete Cooper2012-10-23
| | | | | | next power of 2. This was causing DenseMaps to grow 4x instead of 2x. I'll keep an eye on the buildbots as this could impact performance git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166493 91177308-0d34-0410-b5e6-96231b3b80d8
* Fixed bug in SmallDenseMap where it wouldn't leave enough space for an empty ↵Pete Cooper2012-10-23
| | | | | | bucket if the number of values was exactly equal to the small capacity. This led to an infinite loop when finding a non-existent element git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166492 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: assert that we have found a bucket before we try to insert into it.Jordan Rose2012-09-22
| | | | | | | This silences literally dozens of analyzer warnings on LLVM (since DenseMap is such a commonly-used class). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164438 91177308-0d34-0410-b5e6-96231b3b80d8
* Flatten the aligned-char-array utility template to be a directlyChandler Carruth2012-08-17
| | | | | | | templated union at the request of Richard Smith. This makes it substantially easier to type. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162072 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid undefined behavior in DenseMap::shrink_and_clear(). Log2_32_Ceil(0)Richard Smith2012-08-14
| | | | | | | | returns 32. This change mirrors the corresponding code in SmallDenseMap::shrink_and_clear(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161829 91177308-0d34-0410-b5e6-96231b3b80d8
* Micro-optimize this function a bit. This shrinks the generated codeChandler Carruth2012-07-03
| | | | | | | | | some, and allows the routine to be inlined into common callers. The various bits that hit this code in their hotpath seem slightly lower on the profile, but I can't really measure a performance improvement as everything seems to still be bottlenecked on likely cache misses. =/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159648 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid sign compare warning.Benjamin Kramer2012-06-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159481 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't copy a potentially-uninitialized variable.David Blaikie2012-06-18
| | | | | | Based on review discussion of r158638 with Chandler Carruth, Tobias von Koch, and Duncan Sands and a -Wmaybe-uninitialized warning from GCC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158685 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a unit test for 'swap', and fix a pile of bugs inChandler Carruth2012-06-17
| | | | | | | | | | | | | | | SmallDenseMap::swap. First, make it parse cleanly. Yay for uninstantiated methods. Second, make the inline-buckets case work correctly. This is way trickier than it should be due to the uninitialized values in empty and tombstone buckets. Finally fix a few typos that caused construction/destruction mismatches in the counting unittest. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158641 91177308-0d34-0410-b5e6-96231b3b80d8
* Add tests for *DenesMap for both key and value types' construction andChandler Carruth2012-06-17
| | | | | | | | | | | | | | | | | | | destruction and fix a bug in SmallDenseMap they caught. This is kind of a poor-man's version of the testing that just adds the addresses to a set on construction and removes them on destruction. We check that double construction and double destruction don't occur. Amusingly enough, this is enough to catch a lot of SmallDenseMap issues because we spend a lot of time with fixed stable addresses in the inline buffer. The SmallDenseMap bug fix included makes grow() not double-destroy in some cases. It also fixes a FIXME there, the code was pretty crappy. We now don't have any wasted initialization, but we do move the entries in inline bucket array an extra time. It's probably a better tradeoff, and is much easier to get correct. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158639 91177308-0d34-0410-b5e6-96231b3b80d8
* Introduce a SmallDenseMap container that re-uses the existing DenseMapChandler Carruth2012-06-17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | implementation. This type includes an inline bucket array which is used initially. Once it is exceeded, an array of 64 buckets is allocated on the heap. The bucket count grows from there as needed. Some highlights of this implementation: - The inline buffer is very carefully aligned, and so supports types with alignment constraints. - It works hard to avoid aliasing issues. - Supports types with non-trivial constructors, destructors, copy constructions, etc. It works reasonably hard to minimize copies and unnecessary initialization. The most common initialization is to set keys to the empty key, and so that should be fast if at all possible. This class has a performance / space trade-off. It tries to optimize for relatively small maps, and so packs the inline bucket array densely into the object. It will be marginally slower than a normal DenseMap in a few use patterns, so it isn't appropriate everywhere. The unit tests for DenseMap have been generalized a bit to support running over different map implementations in addition to different key/value types. They've then been automatically extended to cover the new container through the magic of GoogleTest's typed tests. All of this is still a bit rough though. I'm going to be cleaning up some aspects of the implementation, documenting things better, and adding tests which include non-trivial types. As soon as I'm comfortable with the correctness, I plan to switch existing users of SmallMap over to this class as it is already more correct w.r.t. construction and destruction of objects iin the map. Thanks to Benjamin Kramer for all the reviews of this and the lead-up patches. That said, more review on this would really be appreciated. As I've noted a few times, I'm quite surprised how hard it is to get the semantics for a hashtable-based map container with a small buffer optimization correct. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158638 91177308-0d34-0410-b5e6-96231b3b80d8
* Lift the NumElements and NumTombstones members into the super classChandler Carruth2012-06-16
| | | | | | | | | | | | | | | rather than the base class. Add a pile of boilerplate to indirect around this. This is pretty ugly, but it allows the super class to change the representation of these values, which will be key for doing a SmallDenseMap. Suggestions on better method structuring / naming are welcome, but keep in mind that SmallDenseMap won't have an 'unsigned' member to expose a reference to... =/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158586 91177308-0d34-0410-b5e6-96231b3b80d8
* Factor DenseMap into a base class that implements the hashtable logic,Chandler Carruth2012-06-16
| | | | | | | | | | and a derived class that provides the allocation and growth strategy. This is the first (and biggest) step toward building a SmallDenseMap that actually behaves exactly the same as DenseMap, and supports all the same types and interface points with the same semantics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158585 91177308-0d34-0410-b5e6-96231b3b80d8
* Group the 'unsigned' members after the pointer to avoid 4 bytes ofChandler Carruth2012-06-13
| | | | | | padding on x86-64. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158421 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap's move assignment operator needs to return *thisDouglas Gregor2012-05-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157644 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: Use an early exit when there is nothing to do in DestroyAll().Benjamin Kramer2012-05-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157550 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: Provide a move ctor and move semantics for operator[] and ↵Benjamin Kramer2012-05-27
| | | | | | | | | | FindAndConstruct. The only missing part is insert(), which uses a pair of parameters and I haven't figured out how to convert it to rvalue references. It's now possible to use a DenseMap with std::unique_ptr values :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157539 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: Factor destruction into a common helper method.Benjamin Kramer2012-05-27
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157538 91177308-0d34-0410-b5e6-96231b3b80d8
* Provide move semantics for TinyPtrVector and for DenseMap's rehash function.Benjamin Kramer2012-05-19
| | | | | | This makes DenseMap<..., TinyPtrVector<...>> as cheap as it always should've been! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157113 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap: Perform the pod-like object optimization when the value type is ↵Benjamin Kramer2012-04-06
| | | | | | | | POD-like, not the DenseMapInfo for it. Purge now unused template arguments. This has been broken since r91421. Patch by Lubos Lunak! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154170 91177308-0d34-0410-b5e6-96231b3b80d8
* DenseMap::find_as() and unit tests.Talin2012-01-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149229 91177308-0d34-0410-b5e6-96231b3b80d8
* Port the trick to skip the check for empty buckets from StringMap to DenseMap.Benjamin Kramer2012-01-07
| | | | | | This should fix the odd behavior that find() is slower than lookup(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147731 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a generic 'capacity_in_bytes' function to allow inspection of memory ↵Ted Kremenek2011-07-27
| | | | | | usage of various data structures. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136233 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix more -Wnon-pod-memset warnings.Chandler Carruth2011-04-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130392 91177308-0d34-0410-b5e6-96231b3b80d8
* Add utility method to DenseMap to return the amount of memory used for its ↵Ted Kremenek2011-04-28
| | | | | | buckets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130382 91177308-0d34-0410-b5e6-96231b3b80d8
* silence some -Wnon-pod-memset warnings, since std::pair is not POD.Chris Lattner2011-04-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130364 91177308-0d34-0410-b5e6-96231b3b80d8
* Prevent infinite growth of the DenseMap.Jakob Stoklund Olesen2011-03-30
| | | | | | | | | | | | | | | | | | When the hash function uses object pointers all free entries eventually become tombstones as they are used at least once, regardless of the size. DenseMap cannot function with zero empty keys, so it double size to get get ridof the tombstones. However DenseMap never shrinks automatically unless it is cleared, so the net result is that certain tables grow infinitely. The solution is to make a fresh copy of the table without tombstones instead of doubling size, by simply calling grow with the current size. Patch by José Fonseca! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128564 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix more zero length memset warnings.Jay Foad2011-03-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128543 91177308-0d34-0410-b5e6-96231b3b80d8
* Often GCC can see that NumBuckets is zero here, resulting in a warningDuncan Sands2011-03-07
| | | | | | | about possibly swapped memset parameters. Avoid the warning. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127170 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid zero-sized allocations when copying a fresh DenseMap.Benjamin Kramer2011-03-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127110 91177308-0d34-0410-b5e6-96231b3b80d8
* Lazily allocate DenseMaps.Benjamin Kramer2011-03-05
| | | | | | | | | | This makes lookup slightly more expensive but it's worth it, unused DenseMaps are common in LLVM code apparently. 1% speedup on clang -O3 bzip2.c 4% speedup on clang -O3 oggenc.c (Release build of clang on i386/linux) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127088 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new way of silencing this warning.Nick Lewycky2010-12-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122195 91177308-0d34-0410-b5e6-96231b3b80d8
* Add missing standard headers. Patch by Joerg Sonnenberger!Nick Lewycky2010-12-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122193 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the iterator form of erase return void, since it always succeeds,Dan Gohman2010-09-01
| | | | | | | and since this is what std::map and std::set do. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112701 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-02 01:01:19 +0000