search

ned14 / nedtries

A portable in-place bitwise binary Fredkin trie algorithm which allows for near constant time insertions, deletions, finds, closest fit finds and iteration. Is approx. 50-100% faster than red-black trees and up to 20% faster than O(1) hash tables.
http://www.nedprod.com/programs/portable/nedtries/
273 stars 17 forks source link

Valgrind warnings on uninitialized values in test.c #6

Closed jbemmel closed 12 years ago

jbemmel commented 12 years ago

Compile test.c using "g++ -O -march=corei7 test.c -o test -g" ( or use gcc, but then source code locations are more obscure )

Run using "valgrind --track-origins=yes ./test"

Result + g++ version used:

==25188== Memcheck, a memory error detector ==25188== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al. ==25188== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info ==25188== Command: ./test ==25188== ==25188== Conditional jump or move depends on uninitialised value(s) ==25188== at 0x4027D5: unsigned long nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<unsigned long, int, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, keyfunct>, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >(nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const) (nedtrie.h:1807) ==25188== by 0x402858: nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > nedtries::triefind<nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, 16ul, &(unsigned long nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<unsigned long, int, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, keyfunct>, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >(nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const))>(nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > > const, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const) (nedtrie.h:623) ==25188== by 0x402A95: nedtries::trie_map<unsigned long, int, keyfunct, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > > > >::insert(int const&) (nedtrie.h:1893) ==25188== by 0x4017E0: main (test.c:76) ==25188== Uninitialised value was created by a stack allocation ==25188== at 0x402A48: nedtries::trie_map<unsigned long, int, keyfunct, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > > > >::insert(int const&) (nedtrie.h:2019) ==25188== ==25188== Conditional jump or move depends on uninitialised value(s) ==25188== at 0x4027D5: unsigned long nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<unsigned long, int, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, keyfunct>, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >(nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const) (nedtrie.h:1807) ==25188== by 0x402858: nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >* nedtries::triefind<nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, 16ul, &(unsigned long nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<unsigned long, int, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, keyfunct>, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >(nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const))>(nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > > const, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > const*) (nedtrie.h:623) ==25188== by 0x4018DF: main (nedtrie.h:1893) ==25188== Uninitialised value was created by a stack allocation

==25188== at 0x402A48: nedtries::trie_map<unsigned long, int, keyfunct, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > > > >::insert(int const&) (nedtrie.h:2019) ==25188== ==25188== Conditional jump or move depends on uninitialised value(s) ==25188== at 0x4027D5: unsigned long nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<unsigned long, int, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, keyfunct>, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >(nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const) (nedtrie.h:1807) ==25188== by 0x402858: nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > nedtries::triefind<nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, 16ul, &(unsigned long nedtries::intern::to_Ckeyfunct<nedtries::intern::findkeyfunct_t<unsigned long, int, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, keyfunct>, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >(nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > const))>(nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_Listiterator > > const, nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > const*) (nedtrie.h:623) ==25188== by 0x401951: main (nedtrie.h:2206) ==25188== Uninitialised value was created by a stack allocation ==25188== at 0x402B36: nedtries::trie_multimap<unsigned long, int, keyfunct, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > >, nedtries::nedpolicy::nobblezeros, std::list<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator >, std::allocator<nedtries::trie_maptype<unsigned long, int, keyfunct, std::_List_iterator > > > >::insert(int const&) (nedtrie.h:2302) ==25188== General workout of the C API ... 0x7fefff910, 6 General workout of the C++ API ... Testing bug from https://github.com/ned14/nedtries/issues/5 (Nfind does not work in all cases) ... Nfind returned a different item to Cfind 3055 of 65536 (4.661560%) iterations

Press Return to exit ... ==25188== ==25188== HEAP SUMMARY: ==25188== in use at exit: 0 bytes in 0 blocks ==25188== total heap usage: 3 allocs, 3 frees, 216 bytes allocated ==25188== ==25188== All heap blocks were freed -- no leaks are possible ==25188== ==25188== For counts of detected and suppressed errors, rerun with: -v ==25188== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 2 from 2) Using built-in specs. COLLECT_GCC=g++ COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc/x86_64-unknown-linux-gnu/4.8.0/lto-wrapper Target: x86_64-unknown-linux-gnu Configured with: ../configure --disable-nls --enable-languages=c,c++,lto : (reconfigured) ../configure --disable-nls --enable-languages=c,c++,lto --no-create --no-recursion Thread model: posix gcc version 4.8.0 20120716 (experimental) (GCC)

ned14 commented 12 years ago

If this is true, I do apologise. There is an uninit value warning in GCC due to me using memset to zero in one branch of the code but GCC doesn't realise the dependency. If, however, valgrind is seeing an uninit value use - and I assume valgrind knows that static data is zeroed on process start - then there is a bug.

Thanks for reporting it. I'll try to look into it within the next two weeks.

Niall

ned14 commented 12 years ago

Hi, I'm not seeing your bug:

ned@ubuntu-sandbox:~/nedtries$ g++ -o test -O -g test.cpp
ned@ubuntu-sandbox:~/nedtries$ valgrind --track-origins=yes ./test
==888== Memcheck, a memory error detector
==888== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==888== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==888== Command: ./test
==888==
General workout of the C API ...
0xbefd4608, 6
General workout of the C++ API ...
Testing bug from https://github.com/ned14/nedtries/issues/5 (Nfind does not work in all cases) ...
Nfind returned a different item to Cfind 3055 of 65536 (4.661560%) iterations

Press Return to exit ...

==888==
==888== HEAP SUMMARY:
==888==     in use at exit: 0 bytes in 0 blocks
==888==   total heap usage: 3 allocs, 3 frees, 108 bytes allocated
==888==
==888== All heap blocks were freed -- no leaks are possible
==888==
==888== For counts of detected and suppressed errors, rerun with: -v
==888== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

This is on x86 Ubuntu 12.04 LTS running g++ v4.6.3. Are you sure this isn't a bug in GCC v4.8? It's well known to have significant issues with complex template C++.

It could also be x64 as I'm on x86 here.

Niall

jbemmel commented 12 years ago

Strange, on my platform gcc v4.6.3 does give the error, even with -m32 to force 32-bit compilation: /usr/bin/gcc -v Using built-in specs. COLLECT_GCC=/usr/bin/gcc COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/4.6.3/lto-wrapper Target: x86_64-redhat-linux Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --enable-languages=c,c++,objc,obj-c++,java,fortran,ada,go,lto --enable-plugin --enable-java-awt=gtk --disable-dssi --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-1.5.0.0/jre --enable-libgcj-multifile --enable-java-maintainer-mode --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --disable-libjava-multilib --with-ppl --with-cloog --with-tune=generic --with-arch_32=i686 --build=x86_64-redhat-linux Thread model: posix gcc version 4.6.3 20120306 (Red Hat 4.6.3-2) (GCC) [jeroen@i7 tries]$ /usr/bin/gcc -g test.c -o test -m32 /usr/bin/ld: skipping incompatible /usr/lib/gcc/x86_64-redhat-linux/4.6.3/libgcc_s.so when searching for -lgcc_s /usr/bin/ld: skipping incompatible /usr/lib/gcc/x86_64-redhat-linux/4.6.3/libgcc_s.so when searching for -lgcc_s [jeroen@i7 tries]$ valgrind --track-origins=yes ./test ==14197== Memcheck, a memory error detector ==14197== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al. ==14197== Using Valgrind-3.9.0.SVN and LibVEX; rerun with -h for copyright info ==14197== Command: ./test ==14197== General workout of the C API ... 0xfea15388, 6 Testing bug from https://github.com/ned14/nedtries/issues/5 (Nfind does not work in all cases) ... ==14197== Conditional jump or move depends on uninitialised value(s) ==14197== at 0x804A3CB: foo_tree_s_NEDTRIE_NFIND (test.c:33) ==14197== by 0x804AB08: main (test.c:162) ==14197== Uninitialised value was created by a stack allocation ==14197== at 0x804A3DA: main (test.c:46) ==14197== Nfind returned a different item to Cfind 3055 of 65536 (4.661560%) iterations

ned14 commented 12 years ago

I just recently gained access to an Ubuntu 12.04 LTS x64 install - I'll try to repeat your bug on that machine when I return to Ireland next week.

ned14 commented 12 years ago

I found out what was causing our different results - I had disabled the C++ container tests in test.cpp. It is these which are triggering valgrind (intern::to_Ckeyfunct<>). I'll look into it, but to be honest the C++ psuedo-container is very, very hacky and it may just be unfixable.

If you use the C version, or force the use of C macros, I'm seeing this:

ned@kate:~/nedtries$ valgrind --track-origins=yes ./test
==9146== Memcheck, a memory error detector
==9146== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==9146== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==9146== Command: ./test
==9146== 
General workout of the C API ...
0x7feffffe0, 6
Testing bug from https://github.com/ned14/nedtries/issues/5 (Nfind does not work in all cases) ...
==9146== Conditional jump or move depends on uninitialised value(s)
==9146==    at 0x4027F2: main (test.cpp:33)
==9146==  Uninitialised value was created by a stack allocation
==9146==    at 0x4018C8: main (test.cpp:46)
==9146== 
Nfind returned a different item to Cfind 3055 of 65536 (4.661560%) iterations

Press Return to exit ...

==9146== 
==9146== HEAP SUMMARY:
==9146==     in use at exit: 0 bytes in 0 blocks
==9146==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==9146== 
==9146== All heap blocks were freed -- no leaks are possible
==9146== 
==9146== For counts of detected and suppressed errors, rerun with: -v
==9146== ERROR SUMMARY: 142412 errors from 1 contexts (suppressed: 2 from 2)

As you mentioned though, it's very hard to know where this is happening sadly. I had taken great care to make the C macro implementation identical to the C++, but I must have slipped up somewhere.

Niall

ned14 commented 12 years ago

Fixed the valgrind warning by basically working around it appearing. It will always appear when sizeof(type)<sizeof(size_t). Fixed in a3b6a2711be7e61a16632534d70b60fb757f060b