llvm dev - Apr 2009 - [LLVMdev] infinite looping on hashtables

On OS X, this test:
------------------------------------------------------
#include <llvm/ADT/DenseSet.h>
#include <new>

#include <stdio.h>

int main(int argc, char** argv) {
   llvm::DenseSet<unsigned> set(2);
   set.insert(0);
   set.insert(1);
   if (set.count(2)) printf("error\n");
   return 0;
}
------------------------------------------------------

saved as "dense-map.cpp" and compiled thus:

	% g++ -g -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS \
		-I /Developer/usr/local/include dense-map.cpp

hangs on the "set.count(2)" call.

I think this is abusing DenseSet.h, but the bug report says it used to  
work...

There is a simple fix.  Moving this increment "fixes" the test; it  
just prevents the hash table from filling up:

Index: llvm.test/include/llvm/ADT/DenseMap.h
==================================================================---
llvm.test/include/llvm/ADT/DenseMap.h       (revision 70267)
+++ llvm.test/include/llvm/ADT/DenseMap.h       (working copy)
@@ -346,12 +346,12 @@
      // probe almost the entire table until it found the empty  
bucket.  If the
      // table completely filled with tombstones, no lookup would ever  
succeed,
      // causing infinite loops in lookup.
+    ++NumEntries;
      if (NumEntries*4 >= NumBuckets*3 ||
          NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
        this->grow(NumBuckets * 2);
        LookupBucketFor(Key, TheBucket);
      }
-    ++NumEntries;

      // If we are writing over a tombstone, remember this.
      if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))

------------------------------------------------------

Question:  How can I test this?  I was able to create a nifty  
Googletest unit test:

Index: llvm.test/unittests/ADT/DenseSetTest.cpp
==================================================================---
llvm.test/unittests/ADT/DenseSetTest.cpp    (revision 0)
+++ llvm.test/unittests/ADT/DenseSetTest.cpp    (revision 0)
@@ -0,0 +1,30 @@
+//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C 
++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open  
Source
+// License. See LICENSE.TXT for details.
+//
+// 
= 
= 
=---------------------------------------------------------------------- 
===//
+
+#include "gtest/gtest.h"
+#include <llvm/ADT/DenseSet.h>
+
+using namespace llvm;
+
+namespace {
+
+// Test fixture
+class DenseSetTest : public testing::Test {
+};
+
+// Test hashing with a set of only two entries.
+TEST_F(DenseSetTest, DoubleEntrySetTest) {
+  llvm::DenseSet<unsigned> set(2);
+  set.insert(0);
+  set.insert(1);
+  // Original failure was an infinite loop in this call:
+  EXPECT_EQ(0, set.count(2));
+}
+
+}
------------------------------------------------------

This test works fine, so long as it passes.  If the observed failure  
happens, it hangs at the set.count(2) call, and the Googletest  
framework apparently doesn't catch hangs.  (At least, it didn't wake  
up after twenty minutes.)

Suggestions?

stuart

On Apr 28, 2009, at 4:15 PM, Stuart Hastings wrote:
> I think this is abusing DenseSet.h, but the bug report says it used to
> work...
I never claimed any such thing. :)

This did come up in a real situation where I know the size of a  
particular set.  The set can get large enough to justify giving size  
advice to the implementation, but it can also be quite small, which  
triggered this bug.  2 is not an a priori unreasonable initial size to  
give to a hashtable (although I should've been scaling the size  
upwards to prevent excess collisions anyway).
> Question:  How can I test this?  I was able to create a nifty
> Googletest unit test:
> This test works fine, so long as it passes.  If the observed failure
> happens, it hangs at the set.count(2) call, and the Googletest
> framework apparently doesn't catch hangs.  (At least, it didn't
wake
> up after twenty minutes.)
Unfortunately, it looks like the current Googletest framework doesn't  
support test timeouts or anything like them.  You could probably hack  
it by creating a thread to sleep() for five seconds and then kill the  
current process, but ugh.

John.

On Apr 28, 2009, at 5:08 PM, John McCall wrote:
>>
>> This test works fine, so long as it passes.  If the observed failure
>> happens, it hangs at the set.count(2) call, and the Googletest
>> framework apparently doesn't catch hangs.  (At least, it didn't
wake
>> up after twenty minutes.)
>
> Unfortunately, it looks like the current Googletest framework doesn't
> support test timeouts or anything like them.  You could probably hack
> it by creating a thread to sleep() for five seconds and then kill the
> current process, but ugh.
My take is: just add the test.  If it infinite loops, then we'll know  
there is a problem.

:)