champ try_update

[fabianbs96]

Story

As a user of immer, I want to efficiently build up nested map<set> structures in an incremental way until reaching a fixpoint, achieving maximum performance. This involves frequent updates of the nested sets inside the map. The obvious solution for this problem is using the immer::map::update function to update the inner sets. However, I have found that update always re-allocates -- even if the updated value is identical to the already present value leaving a lot of performance on the table. This for example happens if inserting an element to an inner set that has already been present.

As a fallback solution, I currently do the following:

const auto *SetPtr = map.find(Key);
if (!SetPtr)
  return map.set(std::move(Key), makeSingletonSet(std::move(Value));

auto NewSet = SetPtr->insert(std::move(Value));
if (NewSet == *OldSet)
  return map;

return map.set(std::move(Key), std::move(NewSet));

Whereas I really want to do:

return map.update(std::move(Key), [Value = std::move(Value)] (const auto &OldSet){
  return OldSet.insert(std::move(Value));
});

Solution Proposal

As a solution to above problem, I propose a new API try_update within immer::map that works similar to update, just adds an additional equality check on the result of the callback fn and in case of equality leaves the map unchanged.

This PR implements try_update on the champ and provides an according public API to immer::map. In addition, it fixes a minor issue that the champ::update function takes the key by const-ref, although the underlying do_update function can deal with perfectly forwarded keys.

Design decisions:

• Implement do_try_update and do_try_update_mut within an inner struct allowing to recursively call mentioned functions without specifying the template arguments again.
• Use the same signature as do_update[_mut] and use a nullptr node as indicator that nothing has changed.
• Pass the key, the updater-fn and the value-equals-fn by value if they are small and trivial. This adds potential to the optimizer to pass these arguments in registers without touching any memory. Empty arguments, such as std::equal_to for value-equals can even be elided completely. As a policy, when to pass by value, I implemented the byval_if_possible type-trait preferring by-value for trivial types that are not larger than two pointers. This more-or-less matches the behavior of the x86-64 parameter passing conventions of the Itanium ABI (refer to https://gitlab.com/x86-psABIs/x86-64-ABI/ chapter 3.2.3 Parameter Passing)

[codecov-commenter]

Codecov Report

Merging #271 (7eec5f9) into master (5875f77) will decrease coverage by 0.07%. The diff coverage is 87.40%.

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

@@            Coverage Diff             @@
##           master     #271      +/-   ##
==========================================
- Coverage   90.53%   90.46%   -0.07%     
==========================================
  Files         119      119              
  Lines       12144    12379     +235     
==========================================
+ Hits        10994    11199     +205     
- Misses       1150     1180      +30     

Files	Coverage Δ
immer/detail/util.hpp	82.60% <ø> (-0.25%)	:arrow_down:
immer/map.hpp	99.09% <100.00%> (+0.07%)	:arrow_up:
test/algorithm.cpp	89.69% <100.00%> (+0.67%)	:arrow_up:
test/map/generic.ipp	99.23% <98.75%> (+0.10%)	:arrow_up:
immer/detail/hamts/champ.hpp	86.16% <80.60%> (-1.00%)	:arrow_down:

... and 1 file with indirect coverage changes