[libc++][format] Improves parsing speed.

[Mordante]

Summary

A format string like "{}" is quite common. In this case avoid parsing
the format-spec when it's not present. Before the parsing was always
called, therefore some refactoring is done to make sure the formatters
work properly when their parse member isn't called.

From the wording it's not entirely clear whether this optimization is
allowed

[tab:formatter]

and the range [pc.begin(), pc.end()) from the last call to f.parse(pc).

Implies there's always a call to f.parse even when the format-spec
isn't present. Therefore this optimization isn't done for handle
classes; it's unclear whether that would break user defined formatters.

The improvements give a small reduciton is code size:
719408 12472 488 732368 b2cd0 before
718824 12472 488 731784 b2a88 after

The performance benefits when not using a format-spec are:

Comparing ./formatter_int.libcxx.out-baseline to ./formatter_int.libcxx.out
Benchmark                                                               Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------
BM_Basic<uint32_t>                                                   -0.0688         -0.0687            67            62            67            62
BM_Basic<int32_t>                                                    -0.1105         -0.1107            73            65            73            65
BM_Basic<uint64_t>                                                   -0.1053         -0.1049            95            85            95            85
BM_Basic<int64_t>                                                    -0.0889         -0.0888            93            85            93            85
BM_BasicLow<__uint128_t>                                             -0.0655         -0.0655            96            90            96            90
BM_BasicLow<__int128_t>                                              -0.0693         -0.0694            97            90            97            90
BM_Basic<__uint128_t>                                                -0.0359         -0.0359           256           247           256           247
BM_Basic<__int128_t>                                                 -0.0414         -0.0414           239           229           239           229

For the cases where a format-spec is used the results remain similar,
some are faster some are slower, differing per run.

[vitaut]

Nice improvement! It would be good to clarify in the standard that omitting parse is allowed for user-defined types. Could you open an LWG issue?

[ldionne]

LGTM, let's wait for WG21 before skipping parse for user-defined formatters.

[Mordante]

Rebased to validate CI.

[Mordante]

In D129426#3641188, @vitaut wrote:

Nice improvement! It would be good to clarify in the standard that omitting parse is allowed for user-defined types. Could you open an LWG issue?

I'll look into that, thanks for the review!

libcxx/include/__format/formatter_bool.h

public:
   parse(basic_format_parse_context<_CharT>& __parse_ctx) -> decltype(__parse_ctx.begin()) {
     auto __result = __parser_.__parse(__parse_ctx, __format_spec::__fields_integral);
     __format_spec::__process_parsed_bool(__parser_);
     return __result;
   }
 
   _LIBCPP_HIDE_FROM_ABI auto format(bool __value, auto& __ctx) const -> decltype(__ctx.out()) {
     switch (__parser_.__type_) {
+    case __format_spec::__type::__default:
     case __format_spec::__type::__string:
       return __formatter::__format_bool(__value, __ctx, __parser_.__get_parsed_std_specifications(__ctx));
 
     case __format_spec::__type::__binary_lower_case:
     case __format_spec::__type::__binary_upper_case:
     case __format_spec::__type::__octal:
     case __format_spec::__type::__decimal:
     case __format_spec::__type::__hexadecimal_lower_case:

libcxx/include/__format/formatter_char.h

public:
   _LIBCPP_HIDE_FROM_ABI constexpr auto
   parse(basic_format_parse_context<_CharT>& __parse_ctx) -> decltype(__parse_ctx.begin()) {
     auto __result = __parser_.__parse(__parse_ctx, __format_spec::__fields_integral);
     __format_spec::__process_parsed_char(__parser_);
     return __result;
   }
 
   _LIBCPP_HIDE_FROM_ABI auto format(_CharT __value, auto& __ctx) const -> decltype(__ctx.out()) {
-    if (__parser_.__type_ == __format_spec::__type::__char)
+    if (__parser_.__type_ == __format_spec::__type::__default || __parser_.__type_ == __format_spec::__type::__char)
       return __formatter::__format_char(__value, __ctx.out(), __parser_.__get_parsed_std_specifications(__ctx));
 
     if constexpr (sizeof(_CharT) <= sizeof(int))
       // Promotes _CharT to an integral type. This reduces the number of
       // instantiations of __format_integer reducing code size.
       return __formatter::__format_integer(
           static_cast<conditional_t<is_signed_v<_CharT>, int, unsigned>>(__value),
           __ctx,

libcxx/include/__format/formatter_integral.h

_LIBCPP_HIDE_FROM_ABI auto __format_integer(
     _Tp __value,
     auto& __ctx,
     __format_spec::__parsed_specifications<_CharT> __specs,
     bool __negative,
     char* __begin,
     char* __end,
     const char* __prefix,
     int __base) -> decltype(__ctx.out()) {
-  _LIBCPP_ASSERT(
-      __specs.__alignment_ != __format_spec::__alignment::__default,
-      "the caller should adjust the default to the value required by the type");
-
   char* __first = __formatter::__insert_sign(__begin, __negative, __specs.__std_.__sign_);
   if (__specs.__std_.__alternate_form_ && __prefix)
     while (*__prefix)
       *__first++ = *__prefix++;
 
   char* __last = __formatter::__to_buffer(__first, __end, __value, __base);
 
 #  ifndef _LIBCPP_HAS_NO_LOCALIZATION
case __format_spec::__type::__binary_upper_case: {
     return __formatter::__format_integer(__value, __ctx, __specs, __negative, __array.begin(), __array.end(), "0B", 2);
   }
   case __format_spec::__type::__octal: {
     // Octal is special; if __value == 0 there's no prefix.
     array<char, __formatter::__buffer_size<decltype(__value), 8>()> __array;
     return __formatter::__format_integer(
         __value, __ctx, __specs, __negative, __array.begin(), __array.end(), __value != 0 ? "0" : nullptr, 8);
   }
+  case __format_spec::__type::__default:
   case __format_spec::__type::__decimal: {
     array<char, __formatter::__buffer_size<decltype(__value), 10>()> __array;
     return __formatter::__format_integer(
         __value, __ctx, __specs, __negative, __array.begin(), __array.end(), nullptr, 10);
   }
   case __format_spec::__type::__hexadecimal_lower_case: {
     array<char, __formatter::__buffer_size<decltype(__value), 16>()> __array;
     return __formatter::__format_integer(__value, __ctx, __specs, __negative, __array.begin(), __array.end(), "0x", 16);

libcxx/include/__format/formatter_output.h

 struct _LIBCPP_TYPE_VIS __padding_size_result {
   size_t __before_;
   size_t __after_;
 };
 
 _LIBCPP_HIDE_FROM_ABI constexpr __padding_size_result
 __padding_size(size_t __size, size_t __width, __format_spec::__alignment __align) {
   _LIBCPP_ASSERT(__width > __size, "don't call this function when no padding is required");
-  _LIBCPP_ASSERT(__align != __format_spec::__alignment::__default,
-                 "the caller should adjust the default to the value required by the type");
   _LIBCPP_ASSERT(__align != __format_spec::__alignment::__zero_padding,
                  "the caller should have handled the zero-padding");
 
   size_t __fill = __width - __size;
   switch (__align) {
-  case __format_spec::__alignment::__default:
   case __format_spec::__alignment::__zero_padding:
     __libcpp_unreachable();
 
   case __format_spec::__alignment::__left:
     return {0, __fill};
 
   case __format_spec::__alignment::__center: {
     // The extra padding is divided per [format.string.std]/3
     // __before = floor(__fill, 2);
     // __after = ceil(__fill, 2);
     size_t __before = __fill / 2;
     size_t __after = __fill - __before;
     return {__before, __after};
   }
+  case __format_spec::__alignment::__default:
   case __format_spec::__alignment::__right:
     return {__fill, 0};
   }
   __libcpp_unreachable();
 }
 
 template <class _OutIt, class _CharT>
 _LIBCPP_HIDE_FROM_ABI _OutIt __write_using_decimal_separators(_OutIt __out_it, const char* __begin, const char* __first,
                                                               const char* __last, string&& __grouping, _CharT __sep,
                                                               __format_spec::__parsed_specifications<_CharT> __specs) {
-  _LIBCPP_ASSERT(__specs.__alignment_ != __format_spec::__alignment::__default,
-                 "the caller should adjust the default to the value required by the type");
-
   int __size = (__first - __begin) +    // [sign][prefix]
                (__last - __first) +     // data
                (__grouping.size() - 1); // number of separator characters
 
   __padding_size_result __padding = {0, 0};
   if (__specs.__alignment_ == __format_spec::__alignment::__zero_padding) {
     // Write [sign][prefix].
     __out_it = _VSTD::copy(__begin, __first, _VSTD::move(__out_it));

libcxx/include/__format/parser_std_format_spec.h

 }
 
 template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI constexpr void __process_display_type_char(__parser<_CharT>& __parser) {
   __format_spec::__process_display_type_bool_string(__parser);
 }
 
 template <class _CharT>
-_LIBCPP_HIDE_FROM_ABI constexpr void __process_display_type_integer(__parser<_CharT>& __parser) {
-  if (__parser.__alignment_ == __alignment::__default)
-    __parser.__alignment_ = __alignment::__right;
-}
-
-template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI constexpr void __process_parsed_bool(__parser<_CharT>& __parser) {
   switch (__parser.__type_) {
   case __format_spec::__type::__default:
-    __parser.__type_ = __format_spec::__type::__string;
-    [[fallthrough]];
   case __format_spec::__type::__string:
     __format_spec::__process_display_type_bool_string(__parser);
     break;
 
   case __format_spec::__type::__binary_lower_case:
   case __format_spec::__type::__binary_upper_case:
   case __format_spec::__type::__octal:
   case __format_spec::__type::__decimal:
   case __format_spec::__type::__hexadecimal_lower_case:
   case __format_spec::__type::__hexadecimal_upper_case:
-    __process_display_type_integer(__parser);
     break;
 
   default:
     std::__throw_format_error("The format-spec type has a type not supported for a bool argument");
   }
 }
 
 template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI constexpr void __process_parsed_char(__parser<_CharT>& __parser) {
   switch (__parser.__type_) {
   case __format_spec::__type::__default:
-    __parser.__type_ = __format_spec::__type::__char;
-    [[fallthrough]];
   case __format_spec::__type::__char:
     __format_spec::__process_display_type_char(__parser);
     break;
 
   case __format_spec::__type::__binary_lower_case:
   case __format_spec::__type::__binary_upper_case:
   case __format_spec::__type::__octal:
   case __format_spec::__type::__decimal:
   case __format_spec::__type::__hexadecimal_lower_case:
   case __format_spec::__type::__hexadecimal_upper_case:
-    __format_spec::__process_display_type_integer(__parser);
     break;
 
   default:
     std::__throw_format_error("The format-spec type has a type not supported for a char argument");
   }
 }
 
 template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI constexpr void __process_parsed_integer(__parser<_CharT>& __parser) {
   switch (__parser.__type_) {
   case __format_spec::__type::__default:
-    __parser.__type_ = __format_spec::__type::__decimal;
-    [[fallthrough]];
   case __format_spec::__type::__binary_lower_case:
   case __format_spec::__type::__binary_upper_case:
   case __format_spec::__type::__octal:
   case __format_spec::__type::__decimal:
   case __format_spec::__type::__hexadecimal_lower_case:
   case __format_spec::__type::__hexadecimal_upper_case:
-    __format_spec::__process_display_type_integer(__parser);
     break;
 
   case __format_spec::__type::__char:
     __format_spec::__process_display_type_char(__parser);
     break;
 
   default:
     std::__throw_format_error("The format-spec type has a type not supported for an integer argument");
   }
 }
 
 template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI constexpr void __process_parsed_floating_point(__parser<_CharT>& __parser) {
-  __format_spec::__process_display_type_integer(__parser);
-
   switch (__parser.__type_) {
   case __format_spec::__type::__default:
     // When no precision specified then it keeps default since that
     // formatting differs from the other types.
     if (__parser.__precision_as_arg_ || __parser.__precision_ != -1)
       __parser.__type_ = __format_spec::__type::__general_lower_case;
     break;
   case __format_spec::__type::__hexfloat_lower_case:

libcxx/include/format

 
 template <class _CharT, class _ParseCtx, class _Ctx>
 _LIBCPP_HIDE_FROM_ABI constexpr const _CharT*
 __handle_replacement_field(const _CharT* __begin, const _CharT* __end,
                            _ParseCtx& __parse_ctx, _Ctx& __ctx) {
   __format::__parse_number_result __r =
       __format::__parse_arg_id(__begin, __end, __parse_ctx);
 
+  bool __parse = *__r.__ptr == _CharT(':');
   switch (*__r.__ptr) {
   case _CharT(':'):
     // The arg-id has a format-specifier, advance the input to the format-spec.
     __parse_ctx.advance_to(__r.__ptr + 1);
     break;
   case _CharT('}'):
     // The arg-id has no format-specifier.
     __parse_ctx.advance_to(__r.__ptr);
     break;
   default:
     __throw_format_error(
         "The replacement field arg-id should terminate at a ':' or '}'");
   }
 
   if constexpr (same_as<_Ctx, __compile_time_basic_format_context<_CharT>>) {
     __arg_t __type = __ctx.arg(__r.__value);
     if (__type == __arg_t::__handle)
       __ctx.__handle(__r.__value).__parse(__parse_ctx);
     else
         __format::__compile_time_visit_format_arg(__parse_ctx, __ctx, __type);
   } else
     _VSTD::visit_format_arg(
         [&](auto __arg) {
           if constexpr (same_as<decltype(__arg), monostate>)
             __throw_format_error("Argument index out of bounds");
           else if constexpr (same_as<decltype(__arg), typename basic_format_arg<_Ctx>::handle>)
             __arg.format(__parse_ctx, __ctx);
           else {
             formatter<decltype(__arg), _CharT> __formatter;
+            if (__parse)
               __parse_ctx.advance_to(__formatter.parse(__parse_ctx));
             __ctx.advance_to(__formatter.format(__arg, __ctx));
           }
         },
         __ctx.arg(__r.__value));
 
   __begin = __parse_ctx.begin();
   if (__begin == __end || *__begin != _CharT('}'))
     __throw_format_error("The replacement field misses a terminating '}'");