Assertion Failure in erase() about sparsepp HOT 20 CLOSED

This is a known incompatibility with std::unordered_map, and is documented in the readme.md:

"Calls to erase() may invalidate iterators. However, conformant to the C++11 standard, the position and range erase functions return an iterator pointing to the position immediately following the last of the elements erased. This makes it easy to traverse a sparse hash table and delete elements matching a condition. For example to delete odd values:"

I am sorry that it make your use case not working. Do you really need to create a vector of iterators? Please note that google's sparse_hash_map avoid this issue by not releasing the memory of the deleted items, but by replacing them with the "deleted value",

I preferred to actually release the memory, even though it does have the annoying side effect of invalidating iterators.

from sparsepp.

I see. I need to put the interators into a vector so that they can be sorted by a sort function that's different from the hash function. The sort function only looks at part of the data (the "name"). This makes the results deterministic across runs where part of the data that is hashed can change from run to run. I only need the hashing part to remove duplicates. I would use a regular map, but that's too slow. Some of my test cases have ~40M map entries and it becomes very slow with an ordered map. After sorting, some of the objects are added to a different data structure. What I want to do is remove them from the hash_map after inserting them into the new data structure. I'm basically removing a subset of the elements from the hash_map and adding them to a different vector in sorted order. It's not clear how to do this without using erase() or iterating over the hash_map in multiple passes, which would require significant changes to the code control flow.

Thanks for the quick reply.

from sparsepp.

Are you using a sparse_hash_set, or is it a sparse_hash_map with a large key?

What I want to do is remove them from the hash_map after inserting them into the new data structure

Could you first insert all the items to the new data structure, and then remove them from the sparse_hash_map using "erase(const key_type& key );", using the key values from the new data structure.

I know that this means that the values will be duplicated during that process, but that would be the case with Google's version as well.

from sparsepp.

I'm using sparse_hash_map. Both they key and value contain vectors and are large. It's okay to duplicate a few values, but if I'm removing all 40M values from the hash_map and putting them somewhere else I don't want them all to be duplicated at any point in time. I also still need to use the hash_map after filtering/erasing, so the keys do need to be removed from the map at some point.

It might be possible to clear the key/value pairs instead of erasing them from the map, then make a second pass over the hash_map to erase empty keys that had been cleared. This is slower and more complex, and I would prefer not to change it. Is it actually possible/legal to clear the map keys using the iterators instead of erasing from the map?

from sparsepp.

Is it actually possible/legal to clear the map keys using the iterators instead of erasing from the map?

I don't think that would help, because that would not prevent the duplication of memory. Also I don't think it could be done with the current sparsepp architecture.

I could provide a new erase(iterator *first, iterator *last) API that would safely erase a range of iterators. That would not help with the duplication, though, as you'd have to erase all your iterators in one call, but as I wrote earlier it wouldn't be any worse that google::sparse_hash_map which doesn't release the memory on erase() either.

from sparsepp.

Also, I forgot to mention, since your keys and values contain vectors, I hope they provide the move assignement operators for good performance.

from sparsepp.

Let me switch to using my gmail account for this, since we're getting off
the topic of the original issue report and discussing workarounds and fixes
on my side.

As for move operators: We currently build with several compilers (gcc
versions). The oldest doesn't have much C++11 support, but we need it for
RH5 builds and need to keep the code compiling there until we can drop RH5
support. At that point I can probably go add the move operators and such,
if gcc doesn't automatically generate them.

There are currently three calls to erase() in my code. Two of them are
during hash_map iteration and can be fixed to get the new iterator from
erase(). The final call is during iteration over the vector of map
iterators, and must be iterated over in that order. But this call doesn't
copy the data, it only erases the map entry. So maybe I can tag it to be
removed by using a flag in the value, and then remove them in a second
pass. But there is also a find() within that code, and it may be incorrect
to not remove the map key at that point. Or the find would have to check
the removed bit? I'll have to experiment with it.

Frank

On Thu, Oct 6, 2016 at 2:32 PM, Gregory Popovitch [email protected]
wrote:

Also, I forgot to mention, since your keys and values contain vectors, I
hope they provide the move assignement operators for good performance.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2pMzrC3B93Irei_PR8uLug_0VNaUks5qxWkIgaJpZM4KQSmy
.

from sparsepp.

Hi Frank,

I think what you suggest would work, but I'd like to see if I can help to find a better solution. However, I'm not sure I understand what exactly you are doing. Above you wrote:

I only need the hashing part to remove duplicates.

Did you mean "the sorting part". And why is the hash computed not just from the name (like the sort)? Would there be a small code fragment you could share with me?

from sparsepp.

I tried to fix the erase() problem and my smaller tests are passing.
However, one of the larger test sometimes crashes with glibc errors. It's
pretty random, but here is a sample of one of the errors I've seen:
*** glibc detected *** double free or corruption (!prev):
0x0000000003123d00 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x7da26)[0x7fbcbfd5ba26]
/home/gennari/svn_work/eclair_git/bin/eclair(ZN6google11sparsegroupISt4pairIKmN5croix17val_cache_entry_tEELt48ENS_27libc_allocator_with_reallocIS5_EEE3setEtRKS5+0x1a1)[0xd99d11]
/home/gennari/svn_work/eclair_git/bin/eclair(ZN6google16sparse_hashtableISt4pairIKmN5croix17val_cache_entry_tEEmNSt3tr14hashImEENS_15sparse_hash_mapImS4_S8_St8equal_toImENS_27libc_allocator_with_reallocIS5_EEE9SelectKeyENSE_6SetKeyESB_SD_E15insert_noresizeERKS5+0x2c8)[0xd9a008]
/home/gennari/svn_work/eclair_git/bin/eclair(_ZN5croix23SquishAnalysisWindowing16preproc_classifyEPNS_16box_ml_extract_tERKNS_8vect_boxEjRKNS_3boxERNS_10flatPart_tIS3_EEj+0xd15)[0xd919c5]

It's interesting that this error seems to be in google::sparse_hash_map
(which is also still used in some places) rather than spp::sparse_hash_map.
Is there any problem with including both headers and using both hash maps
in the same file? It would think that they use different namespaces and it
would be okay, but sparsepp.h has a lot of defines at the top of the file
and I don't know if they have an effect on other code that includes this
header.

Frank

On Thu, Oct 6, 2016 at 2:39 PM, Frank Gennari [email protected] wrote:

Let me switch to using my gmail account for this, since we're getting off
the topic of the original issue report and discussing workarounds and fixes
on my side.

As for move operators: We currently build with several compilers (gcc
versions). The oldest doesn't have much C++11 support, but we need it for
RH5 builds and need to keep the code compiling there until we can drop RH5
support. At that point I can probably go add the move operators and such,
if gcc doesn't automatically generate them.

There are currently three calls to erase() in my code. Two of them are
during hash_map iteration and can be fixed to get the new iterator from
erase(). The final call is during iteration over the vector of map
iterators, and must be iterated over in that order. But this call doesn't
copy the data, it only erases the map entry. So maybe I can tag it to be
removed by using a flag in the value, and then remove them in a second
pass. But there is also a find() within that code, and it may be incorrect
to not remove the map key at that point. Or the find would have to check
the removed bit? I'll have to experiment with it.

Frank

On Thu, Oct 6, 2016 at 2:32 PM, Gregory Popovitch <
[email protected]> wrote:

Also, I forgot to mention, since your keys and values contain vectors, I
hope they provide the move assignement operators for good performance.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2pMzrC3B93Irei_PR8uLug_0VNaUks5qxWkIgaJpZM4KQSmy
.

from sparsepp.

Gregory,
I'm using the hash_map as a database. The key + value are a mixture of
various pointers to other containers that are configured by the user to
either be used or empty/null. Some of the fields are used as the key and
are uniqued across all of the insert operations. The primary key is a text
string and is always present. The values are merged in various ways when
duplicate keys are encountered.

The first step is uniquing all of the keys and merging of values. After
that, the database can be filtered by looking at the values and removing
elements that fail some test, or split into multiple databases by removing
from the primary database and inserting the {key, value} into a second
database. There is an export option to other formats (including a text
format) that are not hashed where I want the keys to be printed out in a
specific order based on the text string. Printing them out in hash_map
iteration order is no good because it changes from run to run due to other
binary data in the key that is not canonical. That's why I'm creating a
vector of iterators and sorting it by the primary key.

The hash_map is very large (~30GB of data in one example) and it takes too
much memory to store more than one copy of the keys/values. The filtering
and splitting needs to be done by transferring the data between the
hash_maps without storing two or more copies of it. Adding a level of
pointer indirection for the keys and values added runtime and memory
overhead and I lost most of the benefit of using a sparse hash map.

Frank

On Thu, Oct 6, 2016 at 2:50 PM, Gregory Popovitch [email protected]
wrote:

Hi Frank,

I think what you suggest would work, but I'd like to see if I can help to
find a better solution. However, I'm not sure I understand what exactly you
are doing. Above you wrote:

I only need the hashing part to remove duplicates.

Did you mean "the sorting part". And why is the hash computed not just
from the name (like the sort)? Would there be a small code fragment you
could share with me?

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2t2p9gE55GntsvegaXDJSV3CvSvTks5qxW0egaJpZM4KQSmy
.

from sparsepp.

Is there any problem with including both headers and using both hash maps in the same file?

I don't think so. Indeed in multiple timing tests I have I included both headers in the same cxx file and used both hash maps and I haven't seen any problem, however I cannot be 100% positive. You are right, they use different namespaces, and I believe all the macros in sparsepp.h are prefixed with SPP_.

Printing them out in hash_map iteration order is no good because it changes from run to run due to other binary data in the key that is not canonical. That's why I'm creating a vector of iterators and sorting it by the primary key

As long as you don't erase() entries, this should be no problem.
But I understand that there is an erase step somewhere in there. Here is an idea that may work:

Move the entries from the sparse_hash_map to a btree_map (from google's cpp-btree library, which is very memory efficient). Move them one by one, erasing them from the sparse_hash_map after moving then. They will be automatically sorted. Then you can export those you want (in sorted order) and reinsert some into the sparse_hash_map if need be.

from sparsepp.

Including both headers isn't the problem. It works fine if I include both
but revert the rest of the code. Hm. I get that glibc invalid free error
even if I remove all of the erase() operations, so it must be a different
problem.

Frank

On Thu, Oct 6, 2016 at 6:29 PM, Gregory Popovitch [email protected]
wrote:

Is there any problem with including both headers and using both hash maps
in the same file?

I don't think so. Indeed in multiple timing tests I have I included both
headers in the same cxx file and used both hash maps and I haven't seen any
problem, however I cannot be 100% positive. You are right, they use
different namespaces, and I believe all the macros in sparsepp.h are
prefixed with SPP_.

Printing them out in hash_map iteration order is no good because it
changes from run to run due to other binary data in the key that is not
canonical. That's why I'm creating a vector of iterators and sorting it by
the primary key

As long as you don't erase() entries, this should be no problem.
But I understand that there is an erase step somewhere in there. Here is
an idea that may work:

Move the entries from the sparse_hash_map to a btree_map (from google's
cpp-btree library, which is very memory efficient). Move them one by one,
erasing them from the sparse_hash_map after moving then. They will be
automatically sorted. Then you can export those you want (in sorted order)
and reinsert some into the sparse_hash_map if need be.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2m_NGyvWklWJVUidT0DN_HzyiJtNks5qxaB2gaJpZM4KQSmy
.

from sparsepp.

Hi Frank,

Did you make any progress with this issue? If there was a way you could share a piece of code reproducing the issue, I'd like to have a look at it.

Thanks,

greg

from sparsepp.

Greg,
I haven't been able to solve the random glibc memory corruption problem. I
don't really have any ideas. The code that uses the sparse_hash_map is
spread across thousands of lines of code in multiple files, with dozens of
different insert/find/[]/erase, etc. calls. It's in the core database used
to transfer data between our applications. It's not in one place where I
could easily send the code, and I can't send our source anyway.

I don't even have any small failing test cases, the failures tend to be
larger examples with at least 100K map entries. I have some smaller
examples where the results are incorrect, but it's not easy to figure out
what's going wrong. The map keys and values are just big blocks of
compressed binary data that will fill the terminal with thousands of lines
of (in some cases nondeterministic) hex numbers when printed out.

Frank

On Sat, Oct 8, 2016 at 4:20 PM, Gregory Popovitch [email protected]
wrote:

Hi Frank,

Did you make any progress with this issue? If there was a way you could
share a piece of code reproducing the issue, I'd like to have a look at it.

Thanks,

greg

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2sw-jqBBFgY4v0yAOlbudkS_IqDgks5qyCVYgaJpZM4KQSmy
.

from sparsepp.

Maybe you could try using a heap debugging tool like electric-fence or using the flag -fsanitize=address , with a recent g++ or clang compiler, that could provide some useful hint as to where the bug comes from.

from sparsepp.

That's a good idea. I've used -fsanitize-address before and it might work
now. I'm not sure if we have access to electric fence - or does it come
installed with gcc? I'll try this when I'm back at work on Monday. Thanks.

Frank

On Sat, Oct 8, 2016 at 7:21 PM, Gregory Popovitch [email protected]
wrote:

Maybe you could try using a heap debugging tool like electric-fence or
using the flag -fsanitize=address , with a recent g++ or clang compiler,
that could provide some useful hint as to where the bug comes from.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2reBjdiUuLN4BhJ_i133mrbiWtiYks5qyE_AgaJpZM4KQSmy
.

from sparsepp.

Greg,
I got back to looking into the sparsepp problems. I have what I believe is
a deterministic failure with a valid stack trace (below).

I'm not doing any erase() calls for this run. I believe there are only
calls to operator [] that look like this:
value_t &v( the_map[key] );
v.update( ... );
...

I'm not sure how to debug this further. My small test cases don't fail in
this way, only the larger cases that have > 100K map entries.

Frank

Program received signal SIGABRT, Aborted.
0x00007ffff44af035 in __GI_raise (sig=6)
at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
64 ../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or directory.
#0 0x00007ffff44af035 in __GI_raise (sig=6)
at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x00007ffff44b279b in __GI_abort () at abort.c:91
#2 0x00007ffff44ec22e in __libc_message (do_abort=2,
fmt=0x7ffff45f62c8 "*** glibc detected *** %s: %s: 0x%s ***\n")
at ../sysdeps/unix/sysv/linux/libc_fatal.c:201
#3 0x00007ffff44f6a26 in malloc_printerr (action=3,
str=0x7ffff45f63b8 "munmap_chunk(): invalid pointer", ptr=)
at malloc.c:5051
#4 0x0000000000c7283a in deallocate (p=0x2464b60, this=)
at ../src/../../sparsepp/sparsepp.h:1165
#5 spp::sparsegroup<std::pair<croix::hashed_squish_bits_t,
croix::subwind_map_value_t>,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t,
croix::subwind_map_value_t> > >::_free_group (this=0x245fe50, alloc=...,
num_alloc=) at ../src/../../sparsepp/sparsepp.h:2442
#6 0x0000000000ca1f06 in
spp::sparsegroup<std::pair<croix::hashed_squish_bits_t,
croix::subwind_map_value_t>,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t,
croix::subwind_map_value_t> > >::_set_aux (
this=0x245fe50, alloc=..., offset=)
at ../src/../../sparsepp/sparsepp.h:2677
#7 0x0000000000ca20ee in _set (offset=3 '\003', i=,
alloc=...,
this=0x245fe50, erased=)
at ../src/../../sparsepp/sparsepp.h:2698
#8 _set (erased=, offset=, i=,
alloc=..., this=0x245fe50) at ../src/../../sparsepp/sparsepp.h:4486
#9 set (erased=, i=, alloc=...,
this=0x245fe50)
at ../src/../../sparsepp/sparsepp.h:2712
#10 set (erased=, val=..., i=, this=0x2458748)
at ../src/../../sparsepp/sparsepp.h:3535
#11 spp::sparse_hashtable<std::pair<croix::hashed_squish_bits_t,
croix::subwind_map_value_t>, croix::hashed_squish_bits_t,
croix::has_hashcroix::hashed_squish_bits_t,
spp::sparse_hash_map<croix::hashed_squish_bits_t,
croix::subwind_map_value_t, croix::has_hashcroix::hashed_squish_bits_t,
std::equal_to<croix::hashed
_squish_bits_t>,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t
const, croix::subwind_map_value_t> > >::SelectKey,
spp::sparse_hash_map<croix::hashed_squish_bits_t,
croix::subwind_map_value_t, croix::has_hashcroix::hashed_squish_bits_t,
std::equal_tocroix::hashed_squish_bits_t,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t
const, croix::subwind_map_value_t> > >::SetKey,
std::equal_tocroix::hashed_squish_bits_t,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t
const, croix::subwind_map_value_t> > >::_insert_at (this=0x2458700,
obj=..., pos=,
erased=) at ../src/../../sparsepp/sparsepp.h:4497
#12 0x0000000000ca38eb in
spp::sparse_hashtable<std::pair<croix::hashed_squish_bits_t,
croix::subwind_map_value_t>, croix::hashed_squish_bits_t,
croix::has_hashcroix::hashed_squish_bits_t,
spp::sparse_hash_map<croix::hashed_squish_bits_t,
croix::subwind_map_value_t, croix::has_hashcroix::hashed_squish_bits_t,
std::equal_tocroix::hashed_squish_bits_t,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t
const, croix::subwind_map_value_t> > >::SelectKey,
spp::sparse_hash_map<croix::hashed_squish_bits_t,
croix::subwind_map_value_t, croix::has_hashcroix::hashed_squish_bits_t,
std::equal_tocroix::hashed_squish_bits_t,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t
const, croix::subwind_map_value_t> > >::SetKey,
std::equal_tocroix::hashed_squish_bits_t,
spp::libc_allocator_with_realloc<std::pair<croix::hashed_squish_bits_t
const, croix::subwind_map_value_t> >

::find_or_insert<spp::sparse_hash_map<croix::hashed_squish_bits_t,
croix::subwind_map_value_t, croix::has_hashcroix::hashed_squish_bits_t,
std::equal_tocroix::hashed_squish_bits_t, spp::libc_allo---Type
to continue, or q to quit---
cator_with_realloc<std::pair<croix::hashed_squish_bits_t const,
croix::subwind_map_value_t> > >::DefaultValue> (this=0x2458700, key=...)
at ../src/../../sparsepp/sparsepp.h:4597
#13 0x0000000000c82783 in operator[](key=..., this=0x2458700)
at ../src/../../sparsepp/sparsepp.h:5129
#14 lookup (key=..., this=0x2458700) at ../src/SquishWindowing.cc:393

On Sat, Oct 8, 2016 at 9:31 PM, Frank Gennari [email protected] wrote:

That's a good idea. I've used -fsanitize-address before and it might work
now. I'm not sure if we have access to electric fence - or does it come
installed with gcc? I'll try this when I'm back at work on Monday. Thanks.

Frank

On Sat, Oct 8, 2016 at 7:21 PM, Gregory Popovitch <
[email protected]> wrote:

Maybe you could try using a heap debugging tool like electric-fence or
using the flag -fsanitize=address , with a recent g++ or clang compiler,
that could provide some useful hint as to where the bug comes from.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2reBjdiUuLN4BhJ_i133mrbiWtiYks5qyE_AgaJpZM4KQSmy
.

from sparsepp.

Frank, I wish I could help, but I don't know what I can do. From your stack trace, it looks like there is a memory issue, but I don't see a bug when I review the sparsepp code. Without being able to reproduce the issue myself, there is not much I can do.

I would recommend using a tool like electric-fence or Valgrind, or maybe linking in a debug malloc replacement such as dmalloc.

from sparsepp.

Greg,
Thanks for your help with this. Unfortunately, I can't share either the
source code or the inputs (customer data). I don't have time to put much
more effort into debugging this issue. I think I'm going to have to
continue to use a combination of Google's hash maps and the gcc has_map in
our code for now. I'll let you know if I figure anything else out.

Oh, and I was able to use sparsepp to replace another
google::sparse_hash_map in the code, and I didn't have any problems with it
there. That means it's an issue with the input data and call sequence, not
a problem with my development flow/libraries/compiler/etc. But the other
usage is less performance critical and I wasn't able to observe a
difference in either runtime or memory, so there's not much point in
switching to sparsepp.

Frank

On Sun, Oct 16, 2016 at 1:09 PM, Gregory Popovitch <[email protected]

wrote:

Frank, I wish I could help, but I don't know what I can do. From your
stack trace, it looks like there is a memory issue, but I don't see a bug
when I review the sparsepp code. Without being able to reproduce the issue
myself, there is not much I can do.

I would recommend using a tool like electric-fence
http://linux.softpedia.com/get/Programming/Debuggers/Electric-Fence-3305.shtml
or Valgrind http://valgrind.org/, or maybe linking in a debug malloc
replacement such as dmalloc http://dmalloc.com/.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#12 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AL9W2rssuflFbS6cexUdJm3jCfnwAFGvks5q0oSHgaJpZM4KQSmy
.

from sparsepp.

Frank,

Sorry I couldn't help more. I'll close the issue for now, since I can't work on it on my end, but feel free to reopen it if you have any more information. Thanks again for trying out sparsepp.

from sparsepp.