Question about sparse_hash::find_impl.

[freak82]

Hi there,

I'm using your tsl::sparse_map with its default settings (growth policy, etc) in the memory cache subsystem of our P2P proxy.
In the last two or three weeks I observed two times that one thread of the proxy was looping in some functionality consuming 100% CPU and when I provoked the process to print stacktrace it was in the
sparse_map::find function both times.
I'm still investigating if the bug is related to the tsl::sparse_map or to some other functionality from the upper levels. However, I was looking at sparse_hash::find_impl and I was wondering if it's possible for this function to loop forever in some edge case. For example, if every checked sparse_ibucket has some value but the keys are not equal to the searched key?
As I said we use the sparse_map with the default growth policy, which I think is power of two and with default search policy, which is linear, as far as I checked.
The count of the entries in the map reaches 262144 (this is the max allowed value) and then usually stays there minus 10-20-50 entries but it doesn't go beyond the set limit.

Regards,
Pavel.

[Tessil]

Hello,

Thank you for the report.

For example, if every checked sparse_ibucket has some value but the keys are not equal to the searched key?

It should not be possible as the load_factor() should always be below 1.0 (the maximum max_load_factor() authorized is 0.95). But it could come from the deleted values, a map where all entries are either with a value or marked as deleted.

Do you call erase() on this map? It could be related to this bug. I have to check it when I have a bit more time.

[freak82]

Yes, I do call erase on the map.

[Tessil]

Hello,

It could effectively come from a bug in the tsl:sparse_map. Sorry for the caused inconveniences.

I pushed a fix (and a test that reproduced the previous problem), warn me if it ever occurs again.

I'll probably also add this week-end a way to automatically shrink the map when the number of deleted buckets is too high compared to the number of free ones (kind of like min_load_factor() of google::sparse_hash_map), as currently the find method will end-up to be linear when too much buckets are marked as deleted.

[freak82]

Hi,

Thank you for the fast fix. I'm going to pull it and start using it today.
Should I close this issue or you'll close it at some point?

Pavel.

[Tessil]

I'll close it. Don't hesitate to reopen it if the problem still occurs.