doctests for HashMap::drain_filter and HashMap::retain inconsistently fail on armv7-unknown-linux-gnueabihf

[decathorpe]

I'm building the latest version (0.12.3) of hashbrown on Fedora Linux, and I've been getting inconsistent failures for the doctests of HashMap::drain_filter and HashMap::retain:

failures:
---- src/map.rs - map::HashMap<K,V,S,A>::drain_filter (line 861) stdout ----
Test executable failed (exit status: 101).
stderr:
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `10`,
 right: `14`', src/map.rs:18:1
stack backtrace:
   0:   0x4cbb50 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hc28176ead3ec9d69
   1:   0x4e8328 - core::fmt::write::h7199eea8b3eefeea
   2:   0x4c98b4 - std::io::Write::write_fmt::hda04e53644f2809a
   3:   0x4cd50c - std::panicking::default_hook::{{closure}}::he15414d45960bb7f
   4:   0x4cd020 - std::panicking::default_hook::h5a65c4532dc335e8
   5:   0x4cdd44 - std::panicking::rust_panic_with_hook::h06ee924d382f72d6
   6:   0x4cda30 - std::panicking::begin_panic_handler::{{closure}}::h19789143c9fb5a3a
   7:   0x4cc0cc - std::sys_common::backtrace::__rust_end_short_backtrace::h15a938aebd8673ef
   8:   0x4cd7d0 - rust_begin_unwind
   9:   0x4a3d90 - core::panicking::panic_fmt::hb35b35df8f6d56d8
  10:   0x4e73e0 - core::panicking::assert_failed_inner::h90a1e29df5c4c81d
  11:   0x4aa6e8 - core::panicking::assert_failed::h23901b3b68e1f000
  12:   0x4b3fec - rust_out::main::_doctest_main_src_map_rs_861_0::hde253fe046ff970f
  13:   0x4b3ba4 - rust_out::main::h2f8e8bfd22a2168b
  14:   0x4a631c - core::ops::function::FnOnce::call_once::h27d453b84bd9242e
  15:   0x4a4e74 - std::sys_common::backtrace::__rust_begin_short_backtrace::h248a361728c8ae8d
  16:   0x4a4ef0 - std::rt::lang_start::{{closure}}::h5aa1021b9a9cbc5c
  17:   0x4c7778 - std::rt::lang_start_internal::h5dc7cbfeb5526414
  18:   0x4a4ec8 - std::rt::lang_start::ha03e4fc8bfcd1361
  19:   0x4b4218 - main
  20: 0xb6db7890 - __libc_start_call_main
  21: 0xb6db7998 - __libc_start_main_impl
---- src/map.rs - map::HashMap<K,V,S,A>::retain (line 808) stdout ----
Test executable failed (exit status: 101).
stderr:
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `11`,
 right: `14`', src/map.rs:15:1
stack backtrace:
   0:   0x45b600 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hc28176ead3ec9d69
   1:   0x477dd8 - core::fmt::write::h7199eea8b3eefeea
   2:   0x459364 - std::io::Write::write_fmt::hda04e53644f2809a
   3:   0x45cfbc - std::panicking::default_hook::{{closure}}::he15414d45960bb7f
   4:   0x45cad0 - std::panicking::default_hook::h5a65c4532dc335e8
   5:   0x45d7f4 - std::panicking::rust_panic_with_hook::h06ee924d382f72d6
   6:   0x45d4e0 - std::panicking::begin_panic_handler::{{closure}}::h19789143c9fb5a3a
   7:   0x45bb7c - std::sys_common::backtrace::__rust_end_short_backtrace::h15a938aebd8673ef
   8:   0x45d280 - rust_begin_unwind
   9:   0x433d78 - core::panicking::panic_fmt::hb35b35df8f6d56d8
  10:   0x476e90 - core::panicking::assert_failed_inner::h90a1e29df5c4c81d
  11:   0x43c7a8 - core::panicking::assert_failed::h23901b3b68e1f000
  12:   0x443a58 - rust_out::main::_doctest_main_src_map_rs_808_0::hf83bd556f81ce66e
  13:   0x4437d0 - rust_out::main::h2f8e8bfd22a2168b
  14:   0x436200 - core::ops::function::FnOnce::call_once::h27d453b84bd9242e
  15:   0x434ca4 - std::sys_common::backtrace::__rust_begin_short_backtrace::h248a361728c8ae8d
  16:   0x434d20 - std::rt::lang_start::{{closure}}::h5aa1021b9a9cbc5c
  17:   0x457228 - std::rt::lang_start_internal::h5dc7cbfeb5526414
  18:   0x434cf8 - std::rt::lang_start::ha03e4fc8bfcd1361
  19:   0x443cc8 - main
  20: 0xb6dce890 - __libc_start_call_main
  21: 0xb6dce998 - __libc_start_main_impl
failures:
    src/map.rs - map::HashMap<K,V,S,A>::drain_filter (line 861)
    src/map.rs - map::HashMap<K,V,S,A>::retain (line 808)

It looks like the tests both failed at the assert_eq!(map.capacity(), capacity_before_retain); statement, if I'm associating the line numbers correctly.

In one failed build, both these failures happened, while during another, only the HashMap::drain_filter doctest failed, but the HashMap::retain doctest passed.

This happens with Rust 1.62.0, compiling on and for a armv7-unknown-linux-gnueabihf target.

[Amanieu]

This is an artifact of how capacity works in hash tables: removing an element may or may not release capacity, depending on the contents of nearby buckets in the table. Only clear or a re-hash guarantees that the full capacity is released.

The reason this works on x86 but not ARM is that different platforms use different group sizes:

• x86/x86_64 use a group size of 16 because they use SSE instructions.
• 64-bit platforms use a group size of 8.
• 32-bit platforms use a group size of 4.

Smaller group sizes increase the probability that removing an element does not release capacity.

cc @JustForFun88 who worked on these examples.

[Amanieu]

Incidentally, we should probably switch to using a group size of 8 even on 32-bit platforms consider how bad the effect seems to be.

[decathorpe]

Ok, thanks for the explanation! For now, I've ignored the failing doctests for our builds, as that seems to be a safe thing to do.