Skip to content

Foundation Classes - Optimize NCollection_FlatMap and NCollection_FlatDataMap internals#1103

Merged
dpasukhi merged 2 commits intoOpen-Cascade-SAS:IRfrom
dpasukhi:flat_map_checkup
Feb 20, 2026
Merged

Foundation Classes - Optimize NCollection_FlatMap and NCollection_FlatDataMap internals#1103
dpasukhi merged 2 commits intoOpen-Cascade-SAS:IRfrom
dpasukhi:flat_map_checkup

Conversation

@dpasukhi
Copy link
Copy Markdown
Member

@dpasukhi dpasukhi commented Feb 20, 2026

  • Encode slot state in probe distance (myProbeDistancePlus1): 0 = empty, >0 = used
    and remove explicit SlotState/tombstone handling paths.
  • Replace internal findSlot() optional-index API with findSlotIndex() bool + out index.
  • Consolidate insertion logic into insertRehashedImpl() variants and reuse cached hash
    during rehash to avoid redundant hash recomputation.
  • Tune growth policy to max load factor 13/16 (81.25%) and update reserve() math.
  • Keep behavior and API intact while reducing per-slot metadata overhead and hot-path branching.

…d NCollection_FlatDataMap

Replace uint8_t probe distance storage/counters with size_t in both flat hash
containers, so long Robin Hood probe chains are handled without overflow and
without throwing "excessive probe length" exceptions.

- remove THE_MAX_PROBE_DISTANCE and probe-length throw checks
- update probe bookkeeping in find/insert/try-insert/bind/emplace paths
- keep lookup early-exit logic based on stored probe distance
- update class documentation: probe distance is bounded by table capacity
- add collision stress tests:
  - NCollection_FlatMapTest.LongProbeSequence
  - NCollection_FlatDataMapTest.LongProbeSequence
@dpasukhi dpasukhi requested a review from Copilot February 20, 2026 21:23
@dpasukhi dpasukhi self-assigned this Feb 20, 2026
@dpasukhi dpasukhi added the 1. Foundation Classes Containers, system calls wrappers, smart pointers and other low level of OCCT code label Feb 20, 2026
Copy link
Copy Markdown

Copilot AI left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot reviewed 4 out of 4 changed files in this pull request and generated no comments.

Comments suppressed due to low confidence (6)

src/FoundationClasses/TKernel/NCollection/NCollection_FlatDataMap.hxx:905

  • The removal of exception throwing for excessive probe length changes the behavior for users who may have been catching Standard_OutOfRange exceptions. This is an API behavior change that could affect existing code. While the new behavior is arguably better (no arbitrary limits), consider documenting this breaking change in release notes or comments to help users understand that:
  1. The exception "NCollection_FlatDataMap: excessive probe length" will no longer be thrown
  2. Operations may take longer with pathological hash functions instead of failing fast
  3. Users should ensure their hash functions distribute keys reasonably well

This is particularly important since the old behavior provided a safety mechanism against severely degraded performance.

      ++aProbe;
      aIndex = (aIndex + 1) & aMask;
    }

src/FoundationClasses/TKernel/NCollection/NCollection_FlatMap.hxx:83

  • Changing probe distance from uint8_t to size_t significantly increases memory usage per slot. On 64-bit systems, this adds 7 bytes per slot (8 bytes for size_t vs 1 byte for uint8_t). For a table with many entries, this could substantially increase memory footprint.

Consider whether there's a middle ground: could you use uint16_t or uint32_t to handle reasonable probe distances while limiting memory impact? A uint16_t would allow probe distances up to 65,535 which should be sufficient for most real-world scenarios while only adding 1 byte per slot. Alternatively, document this as a known tradeoff if size_t is deemed necessary.

    size_t    myProbeDistance; //!< Distance from ideal bucket (for Robin Hood)

src/FoundationClasses/TKernel/NCollection/NCollection_FlatDataMap.hxx:94

  • Changing probe distance from uint8_t to size_t significantly increases memory usage per slot. On 64-bit systems, this adds 7 bytes per slot (8 bytes for size_t vs 1 byte for uint8_t). For a table with many entries, this could substantially increase memory footprint.

Consider whether there's a middle ground: could you use uint16_t or uint32_t to handle reasonable probe distances while limiting memory impact? A uint16_t would allow probe distances up to 65,535 which should be sufficient for most real-world scenarios while only adding 1 byte per slot. Alternatively, document this as a known tradeoff if size_t is deemed necessary.

    size_t    myProbeDistance; //!< Distance from ideal bucket (for Robin Hood)

src/FoundationClasses/TKernel/GTests/NCollection_FlatMap_Test.cxx:172

  • The test uses 400 elements with a constant hasher to create worst-case collisions. While this effectively tests the removal of the probe cap, consider testing with even higher values to ensure the new size_t-based implementation truly handles extreme cases. Also, consider adding a comment explaining why 400 was chosen as the test size (presumably because it's significantly larger than the old 250 limit).
TEST_F(NCollection_FlatMapTest, LongProbeSequence)
{
  struct ConstantHasher
  {
    size_t operator()(int) const { return 0; }

    bool operator()(int theKey1, int theKey2) const { return theKey1 == theKey2; }
  };

  constexpr int                            THE_NUM_ELEMENTS = 400;
  NCollection_FlatMap<int, ConstantHasher> aMap;

  for (int i = 0; i < THE_NUM_ELEMENTS; ++i)
  {
    EXPECT_TRUE(aMap.Add(i));
  }

  EXPECT_EQ(THE_NUM_ELEMENTS, aMap.Size());
  for (int i = 0; i < THE_NUM_ELEMENTS; ++i)
  {
    EXPECT_TRUE(aMap.Contains(i)) << "Key " << i << " not found";
  }
}

src/FoundationClasses/TKernel/GTests/NCollection_FlatDataMap_Test.cxx:325

  • The test uses 400 elements with a constant hasher to create worst-case collisions. While this effectively tests the removal of the probe cap, consider testing with even higher values to ensure the new size_t-based implementation truly handles extreme cases. Also, consider adding a comment explaining why 400 was chosen as the test size (presumably because it's significantly larger than the old 250 limit).
TEST_F(NCollection_FlatDataMapTest, LongProbeSequence)
{
  struct ConstantHasher
  {
    size_t operator()(int) const { return 0; }

    bool operator()(int theKey1, int theKey2) const { return theKey1 == theKey2; }
  };

  constexpr int                                     THE_NUM_ELEMENTS = 400;
  NCollection_FlatDataMap<int, int, ConstantHasher> aMap;

  for (int i = 0; i < THE_NUM_ELEMENTS; ++i)
  {
    EXPECT_TRUE(aMap.Bind(i, i * 3));
  }

  EXPECT_EQ(THE_NUM_ELEMENTS, aMap.Size());
  for (int i = 0; i < THE_NUM_ELEMENTS; ++i)
  {
    EXPECT_TRUE(aMap.IsBound(i)) << "Key " << i << " not found";
    EXPECT_EQ(i * 3, aMap.Find(i));
  }
}

src/FoundationClasses/TKernel/NCollection/NCollection_FlatMap.hxx:678

  • The removal of exception throwing for excessive probe length changes the behavior for users who may have been catching Standard_OutOfRange exceptions. This is an API behavior change that could affect existing code. While the new behavior is arguably better (no arbitrary limits), consider documenting this breaking change in release notes or comments to help users understand that:
  1. The exception "NCollection_FlatMap: excessive probe length" will no longer be thrown
  2. Operations may take longer with pathological hash functions instead of failing fast
  3. Users should ensure their hash functions distribute keys reasonably well

This is particularly important since the old behavior provided a safety mechanism against severely degraded performance.

      ++aProbe;
      aIndex = (aIndex + 1) & aMask;
    }

…tDataMap internals

- Encode slot state in probe distance (`myProbeDistancePlus1`): 0 = empty, >0 = used
  and remove explicit `SlotState`/tombstone handling paths.
- Replace internal `findSlot()` optional-index API with `findSlotIndex()` bool + out index.
- Consolidate insertion logic into `insertRehashedImpl()` variants and reuse cached hash
  during rehash to avoid redundant hash recomputation.
- Tune growth policy to max load factor 13/16 (81.25%) and update `reserve()` math.
- Keep behavior and API intact while reducing per-slot metadata overhead and hot-path branching.
@dpasukhi dpasukhi changed the title Foundation Classes - Remove fixed probe cap in NCollection_FlatMap and NCollection_FlatDataMap Foundation Classes - Optimize NCollection_FlatMap and NCollection_FlatDataMap internals Feb 20, 2026
@dpasukhi dpasukhi merged commit 2a09e06 into Open-Cascade-SAS:IR Feb 20, 2026
18 checks passed
@dpasukhi dpasukhi deleted the flat_map_checkup branch February 20, 2026 23:40
@github-project-automation github-project-automation bot moved this from Todo to Done in Maintenance Feb 20, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

1. Foundation Classes Containers, system calls wrappers, smart pointers and other low level of OCCT code

Projects

Status: Done

Development

Successfully merging this pull request may close these issues.

2 participants