Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

STL: Finish replacing tag dispatch with if constexpr #189

Open
StephanTLavavej opened this issue Oct 18, 2019 · 8 comments
Open

STL: Finish replacing tag dispatch with if constexpr #189

StephanTLavavej opened this issue Oct 18, 2019 · 8 comments
Labels
throughput Must compile faster

Comments

@StephanTLavavej
Copy link
Member

StephanTLavavej commented Oct 18, 2019

Tag dispatch is the STL's original metaprogramming technique: overload a helper function on a tag struct (e.g. input_iterator_tag versus forward_iterator_tag, or true_type versus false_type) and then call it with a tag object to select the appropriate overload. This has several downsides, though - it is somewhat verbose, it interferes with code organization, and it results in actual function calls in debug mode. (This is slower, more work to step through when debugging, and bloats object files.) C++17 if constexpr supersedes tag dispatch in almost every situation (see note below) and we're using it in new C++17-and-later code. We can use it in C++14 mode too (compilers support it unconditionally with a warning that we've suppressed).

We should finish overhauling the STL to use if constexpr.

Note: Tag dispatch works with delegating constructors, whereas if constexpr works only in function bodies. subrange's delegating constructors are a rare example of necessary tag dispatch:

STL/stl/inc/xutility

Lines 3345 to 3356 in f099e9c

template <class _Rng>
constexpr subrange(true_type, _Rng&& _Val)
: subrange(_STD forward<_Rng>(_Val), static_cast<_Size_type>(_RANGES size(_Val))) {
// delegation target for subrange(_Rng&&) when we must store the range size
_STL_INTERNAL_STATIC_ASSERT(_Store_size);
}
template <class _Rng>
constexpr subrange(false_type, _Rng&& _Val) : subrange(_RANGES begin(_Val), _RANGES end(_Val)) {
// delegation target for subrange(_Rng&&) when we need not store the range size
_STL_INTERNAL_STATIC_ASSERT(!_Store_size);
}

@StephanTLavavej StephanTLavavej added enhancement Something can be improved throughput Must compile faster labels Oct 18, 2019
@StephanTLavavej StephanTLavavej removed the enhancement Something can be improved label Feb 5, 2020
@StephanTLavavej

This comment was marked as resolved.

@CaseyCarter

This comment was marked as resolved.

@AlexGuteniev

This comment was marked as resolved.

AlexGuteniev added a commit to AlexGuteniev/STL that referenced this issue Oct 20, 2021
AlexGuteniev added a commit to AlexGuteniev/STL that referenced this issue Jan 13, 2022
AlexGuteniev added a commit to AlexGuteniev/STL that referenced this issue Jan 15, 2022
Towards microsoft#189
@miscco would suggest enum instead of bool, so doing it in advance
AlexGuteniev added a commit to AlexGuteniev/STL that referenced this issue Jan 15, 2022
AlexGuteniev added a commit to AlexGuteniev/STL that referenced this issue Jan 15, 2022
@AlexGuteniev

This comment was marked as resolved.

@AlexGuteniev

This comment was marked as resolved.

AlexGuteniev added a commit to AlexGuteniev/STL that referenced this issue Jan 16, 2022
@StephanTLavavej

This comment was marked as resolved.

@StephanTLavavej
Copy link
Member Author

StephanTLavavej commented Mar 19, 2022

Dispatching on iterator strength:

  • vector::_Insert_range() (changed by Use iterator concept in vector's range constructor #1794)

    STL/stl/inc/vector

    Lines 1027 to 1166 in f099e9c

    template <class _Iter>
    _CONSTEXPR20 void _Insert_range(const_iterator _Where, _Iter _First, _Iter _Last, input_iterator_tag) {
    // insert input range [_First, _Last) at _Where
    if (_First == _Last) {
    return; // nothing to do, avoid invalidating iterators
    }
    auto& _My_data = _Mypair._Myval2;
    pointer& _Myfirst = _My_data._Myfirst;
    pointer& _Mylast = _My_data._Mylast;
    const auto _Whereoff = static_cast<size_type>(_Where._Ptr - _Myfirst);
    const auto _Oldsize = static_cast<size_type>(_Mylast - _Myfirst);
    // For one-at-back, provide strong guarantee.
    // Otherwise, provide basic guarantee (despite N4659 26.3.11.5 [vector.modifiers]/1).
    // Performance note: except for one-at-back, _Emplace_one_at_back()'s strong guarantee is unnecessary here.
    for (; _First != _Last; ++_First) {
    _Emplace_one_at_back(*_First);
    }
    _Orphan_range(_Myfirst + _Whereoff, _Myfirst + _Oldsize);
    _STD rotate(_Myfirst + _Whereoff, _Myfirst + _Oldsize, _Mylast);
    }
    template <class _Iter>
    _CONSTEXPR20 void _Insert_range(const_iterator _Where, _Iter _First, _Iter _Last, forward_iterator_tag) {
    // insert forward range [_First, _Last) at _Where
    const pointer _Whereptr = _Where._Ptr;
    const auto _Count = _Convert_size<size_type>(static_cast<size_t>(_STD distance(_First, _Last)));
    auto& _Al = _Getal();
    auto& _My_data = _Mypair._Myval2;
    pointer& _Mylast = _My_data._Mylast;
    const pointer _Oldfirst = _My_data._Myfirst;
    const pointer _Oldlast = _Mylast;
    const auto _Unused_capacity = static_cast<size_type>(_My_data._Myend - _Oldlast);
    if (_Count == 0) { // nothing to do, avoid invalidating iterators
    } else if (_Count > _Unused_capacity) { // reallocate
    const auto _Oldsize = static_cast<size_type>(_Oldlast - _Oldfirst);
    if (_Count > max_size() - _Oldsize) {
    _Xlength();
    }
    const size_type _Newsize = _Oldsize + _Count;
    const size_type _Newcapacity = _Calculate_growth(_Newsize);
    const pointer _Newvec = _Al.allocate(_Newcapacity);
    const auto _Whereoff = static_cast<size_type>(_Whereptr - _Oldfirst);
    const pointer _Constructed_last = _Newvec + _Whereoff + _Count;
    pointer _Constructed_first = _Constructed_last;
    _TRY_BEGIN
    _Uninitialized_copy(_First, _Last, _Newvec + _Whereoff, _Al);
    _Constructed_first = _Newvec + _Whereoff;
    if (_Count == 1 && _Whereptr == _Oldlast) { // one at back, provide strong guarantee
    if constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {
    _Uninitialized_move(_Oldfirst, _Oldlast, _Newvec, _Al);
    } else {
    _Uninitialized_copy(_Oldfirst, _Oldlast, _Newvec, _Al);
    }
    } else { // provide basic guarantee
    _Uninitialized_move(_Oldfirst, _Whereptr, _Newvec, _Al);
    _Constructed_first = _Newvec;
    _Uninitialized_move(_Whereptr, _Oldlast, _Newvec + _Whereoff + _Count, _Al);
    }
    _CATCH_ALL
    _Destroy_range(_Constructed_first, _Constructed_last, _Al);
    _Al.deallocate(_Newvec, _Newcapacity);
    _RERAISE;
    _CATCH_END
    _Change_array(_Newvec, _Newsize, _Newcapacity);
    } else { // Attempt to provide the strong guarantee for EmplaceConstructible failure.
    // If we encounter copy/move construction/assignment failure, provide the basic guarantee.
    // (For one-at-back, this provides the strong guarantee.)
    const auto _Affected_elements = static_cast<size_type>(_Oldlast - _Whereptr);
    _ASAN_VECTOR_EXTEND_GUARD(static_cast<size_type>(_Oldlast - _Oldfirst) + _Count);
    if (_Count < _Affected_elements) { // some affected elements must be assigned
    _Mylast = _Uninitialized_move(_Oldlast - _Count, _Oldlast, _Oldlast, _Al);
    _Move_backward_unchecked(_Whereptr, _Oldlast - _Count, _Oldlast);
    _Destroy_range(_Whereptr, _Whereptr + _Count, _Al);
    _TRY_BEGIN
    _Uninitialized_copy(_First, _Last, _Whereptr, _Al);
    _CATCH_ALL
    // glue the broken pieces back together
    _TRY_BEGIN
    _Uninitialized_move(_Whereptr + _Count, _Whereptr + 2 * _Count, _Whereptr, _Al);
    _CATCH_ALL
    // vaporize the detached piece
    _Orphan_range(_Whereptr, _Oldlast);
    _Destroy_range(_Whereptr + _Count, _Mylast, _Al);
    _Mylast = _Whereptr;
    _RERAISE;
    _CATCH_END
    _Move_unchecked(_Whereptr + 2 * _Count, _Mylast, _Whereptr + _Count);
    _Destroy_range(_Oldlast, _Mylast, _Al);
    _Mylast = _Oldlast;
    _RERAISE;
    _CATCH_END
    } else { // affected elements don't overlap before/after
    const pointer _Relocated = _Whereptr + _Count;
    _Mylast = _Uninitialized_move(_Whereptr, _Oldlast, _Relocated, _Al);
    _Destroy_range(_Whereptr, _Oldlast, _Al);
    _TRY_BEGIN
    _Uninitialized_copy(_First, _Last, _Whereptr, _Al);
    _CATCH_ALL
    // glue the broken pieces back together
    _TRY_BEGIN
    _Uninitialized_move(_Relocated, _Mylast, _Whereptr, _Al);
    _CATCH_ALL
    // vaporize the detached piece
    _Orphan_range(_Whereptr, _Oldlast);
    _Destroy_range(_Relocated, _Mylast, _Al);
    _Mylast = _Whereptr;
    _RERAISE;
    _CATCH_END
    _Destroy_range(_Relocated, _Mylast, _Al);
    _Mylast = _Oldlast;
    _RERAISE;
    _CATCH_END
    }
    _Orphan_range(_Whereptr, _Oldlast);
    _ASAN_VECTOR_RELEASE_GUARD;
    }
    }
  • vector::_Assign_range() (changed by Use iterator concept in vector's range constructor #1794)

    STL/stl/inc/vector

    Lines 1236 to 1315 in f099e9c

    template <class _Iter>
    _CONSTEXPR20 void _Assign_range(_Iter _First, _Iter _Last, input_iterator_tag) {
    // assign input range [_First, _Last)
    auto& _My_data = _Mypair._Myval2;
    pointer& _Myfirst = _My_data._Myfirst;
    pointer& _Mylast = _My_data._Mylast;
    _My_data._Orphan_all();
    pointer _Next = _Myfirst;
    for (; _First != _Last && _Next != _Mylast; ++_First, (void) ++_Next) {
    *_Next = *_First;
    }
    // Code size optimization: we've exhausted only the source, only the dest, or both.
    // If we've exhausted only the source: we Trim, then Append does nothing.
    // If we've exhausted only the dest: Trim does nothing, then we Append.
    // If we've exhausted both: Trim does nothing, then Append does nothing.
    // Trim.
    _Destroy_range(_Next, _Mylast, _Getal());
    _ASAN_VECTOR_MODIFY(static_cast<difference_type>(_Next - _Mylast)); // negative when destroying elements
    _Mylast = _Next;
    // Append.
    for (; _First != _Last; ++_First) {
    // performance note: _Emplace_one_at_back()'s strong guarantee is unnecessary here
    _Emplace_one_at_back(*_First);
    }
    }
    template <class _Iter>
    _CONSTEXPR20 void _Assign_range(_Iter _First, _Iter _Last, forward_iterator_tag) {
    // assign forward range [_First, _Last)
    const auto _Newsize = _Convert_size<size_type>(static_cast<size_t>(_STD distance(_First, _Last)));
    auto& _Al = _Getal();
    auto& _My_data = _Mypair._Myval2;
    pointer& _Myfirst = _My_data._Myfirst;
    pointer& _Mylast = _My_data._Mylast;
    pointer& _Myend = _My_data._Myend;
    constexpr bool _Nothrow_construct = conjunction_v<is_nothrow_constructible<_Ty, _Iter_ref_t<_Iter>>,
    _Uses_default_construct<_Alloc, _Ty*, _Iter_ref_t<_Iter>>>;
    _My_data._Orphan_all();
    const auto _Oldcapacity = static_cast<size_type>(_Myend - _Myfirst);
    if (_Newsize > _Oldcapacity) {
    _Clear_and_reserve_geometric(_Newsize);
    if constexpr (_Nothrow_construct) {
    _Mylast = _Uninitialized_copy(_First, _Last, _Myfirst, _Al);
    _ASAN_VECTOR_CREATE;
    } else {
    _ASAN_VECTOR_CREATE_GUARD;
    _Mylast = _Uninitialized_copy(_First, _Last, _Myfirst, _Al);
    }
    return;
    }
    const auto _Oldsize = static_cast<size_type>(_Mylast - _Myfirst);
    if (_Newsize > _Oldsize) {
    // performance note: traversing [_First, _Mid) twice
    const _Iter _Mid = _STD next(_First, static_cast<difference_type>(_Oldsize));
    _Copy_unchecked(_First, _Mid, _Myfirst);
    if constexpr (_Nothrow_construct) {
    _ASAN_VECTOR_MODIFY(static_cast<difference_type>(_Newsize - _Oldsize));
    _Mylast = _Uninitialized_copy(_Mid, _Last, _Mylast, _Al);
    } else {
    _ASAN_VECTOR_EXTEND_GUARD(_Newsize);
    _Mylast = _Uninitialized_copy(_Mid, _Last, _Mylast, _Al);
    _ASAN_VECTOR_RELEASE_GUARD;
    }
    } else {
    const pointer _Newlast = _Myfirst + _Newsize;
    _Copy_unchecked(_First, _Last, _Myfirst);
    _Destroy_range(_Newlast, _Mylast, _Al);
    _ASAN_VECTOR_MODIFY(static_cast<difference_type>(_Newsize - _Oldsize));
    _Mylast = _Newlast;
    }
    }
  • vector<bool>::_Insert() (fixed by Untag dispatch vector<👻>::_Insert #2694)

    STL/stl/inc/vector

    Lines 3089 to 3104 in f099e9c

    template <class _Iter>
    _CONSTEXPR20 void _Insert(const_iterator _Where, _Iter _First, _Iter _Last, input_iterator_tag) {
    difference_type _Off = _Where - begin();
    for (; _First != _Last; ++_First, (void) ++_Off) {
    insert(begin() + _Off, *_First);
    }
    }
    template <class _Iter>
    _CONSTEXPR20 void _Insert(const_iterator _Where, _Iter _First, _Iter _Last, forward_iterator_tag) {
    _Adl_verify_range(_First, _Last);
    auto _Count = _Convert_size<size_type>(static_cast<size_t>(_STD distance(_First, _Last)));
    size_type _Off = _Insert_x(_Where, _Count);
    _Copy_unchecked(_Get_unwrapped(_First), _Get_unwrapped(_Last), begin() + static_cast<difference_type>(_Off));
    }

@AlexGuteniev
Copy link
Contributor

There are candidates in <format> but not sure if it worth to untag dispatch them.

STL/stl/inc/format

Lines 1721 to 1743 in bd3d740

constexpr void _On_dynamic_width(const size_t _Arg_id) {
_Parse_ctx.check_arg_id(_Arg_id);
_Parse_ctx._Check_dynamic_spec_integral(_Arg_id);
_Dynamic_specs._Dynamic_width_index = _Verify_dynamic_arg_index_in_range(_Arg_id);
}
constexpr void _On_dynamic_width(_Auto_id_tag) {
const size_t _Arg_id = _Parse_ctx.next_arg_id();
_Parse_ctx._Check_dynamic_spec_integral(_Arg_id);
_Dynamic_specs._Dynamic_width_index = _Verify_dynamic_arg_index_in_range(_Arg_id);
}
constexpr void _On_dynamic_precision(const size_t _Arg_id) {
_Parse_ctx.check_arg_id(_Arg_id);
_Parse_ctx._Check_dynamic_spec_integral(_Arg_id);
_Dynamic_specs._Dynamic_precision_index = _Verify_dynamic_arg_index_in_range(_Arg_id);
}
constexpr void _On_dynamic_precision(_Auto_id_tag) {
const size_t _Arg_id = _Parse_ctx.next_arg_id();
_Parse_ctx._Check_dynamic_spec_integral(_Arg_id);
_Dynamic_specs._Dynamic_precision_index = _Verify_dynamic_arg_index_in_range(_Arg_id);
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
throughput Must compile faster
Projects
None yet
Development

No branches or pull requests

3 participants