Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #82746 > unrolled thread

Can anyone improve this ?

Started byBonita Montero <Bonita.Montero@gmail.com>
First post2022-01-11 09:08 +0100
Last post2022-01-18 09:18 +0100
Articles 5 on this page of 25 — 8 participants

Back to article view | Back to comp.lang.c++

Contents

  Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 09:08 +0100
    Re: Can anyone improve this ? Juha Nieminen <nospam@thanks.invalid> - 2022-01-11 09:50 +0000
      Re: Can anyone improve this ? Juha Nieminen <nospam@thanks.invalid> - 2022-01-11 11:07 +0000
      Re: Can anyone improve this ? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-11 11:08 +0000
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 18:28 +0100
        Re: Can anyone improve this ? Christian Gollwitzer <auriocus@gmx.de> - 2022-01-11 18:41 +0100
          Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 19:36 +0100
        Re: Can anyone improve this ? Öö Tiib <ootiib@hot.ee> - 2022-01-11 21:54 -0800
    Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-11 21:51 +0100
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-12 14:19 +0100
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-12 14:20 +0100
        Re: Can anyone improve this ? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-12 14:14 +0000
          Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-12 17:20 +0100
            Re: Can anyone improve this ? "james...@alumni.caltech.edu" <jameskuyper@alumni.caltech.edu> - 2022-01-12 08:38 -0800
            Re: Can anyone improve this ? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-12 16:55 +0000
          Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-16 12:09 -0800
          Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-16 12:12 -0800
            Re: Can anyone improve this ? Öö Tiib <ootiib@hot.ee> - 2022-01-16 13:00 -0800
              Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 10:13 -0800
    Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 10:28 -0800
      Re: Can anyone improve this ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-01-17 21:51 +0100
        Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 16:16 -0800
        Re: Can anyone improve this ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-17 22:43 -0800
          Re: Can anyone improve this ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-01-18 12:09 +0100
      Re: Can anyone improve this ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-18 09:18 +0100

Page 2 of 2 — ← Prev page 1 [2]

#82805

From"Alf P. Steinbach" <alf.p.steinbach@gmail.com>
Date2022-01-17 21:51 +0100
Message-ID<ss4ksr$d9d$1@dont-email.me>
In reply to#82802
On 17 Jan 2022 19:28, Tim Rentsch wrote:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
> 
>> I had an idea how to write a fast UTF-8 strlen, here it is:
>>
>> size_t utf8Strlen( char const *str )
>> {
>>      struct encode_t { size_t lenIncr, strIncr; };
>>      static encode_t const encodes[] =
>>      {
>>          { 1, 1 },
>>          { 0, 0 },
>>          { 1, 2 },
>>          { 1, 3 },
>>          { 1, 4 },
>>          { 0, 0 },
>>          { 0, 0 },
>>          { 0, 0 },
>>          { 0, 0 }
>>      };
>>      size_t len = 0;
>>      for( unsigned char c; (c = *str); )
>>      {
>>          encode_t const &enc =
>>             encodes[(size_t)countl_zero<unsigned char>( ~c )];
>>          if( !enc.lenIncr ) [[unlikely]]
>>              return -1;
>>          len += enc.lenIncr;
>>          for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>>              if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>                  return -1;
>>      }
>>      return len;
>> }
>>
>> Has anyone further ideas to improve this ?
> 
> Just for fun -
> 
> size_t
> utf8_units_two( const char *s ){
>      size_t r = -1;
>      unsigned char c;
> 
>    next:
>      switch(  r++,  c = *s++,  c >> 3  ){
> 	cases(16,17,18,19,20,21,22,23,31):			return  -1;
> 
> 	cases(30):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
> 	cases(28,29):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
> 	cases(24,25,26,27):	if(  c = *s++,  c >> 6 != 2  )	return  -1;
> 	cases(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15):		goto  next;
> 
> 	cases(0):		if(  c != 0  )			goto  next;
>      }
> 
>      return  r;
> }

That's very ugly.


> (Note:  the cases() macro produces one 'case X:' for each
> argument X except the last one where the ':' is omitted,
> written using the standard C preprocessor, and left as an
> exercise for any ambitious readers.)

Exercise for you: test that unrevealed macro with Visual C++.

(Making it work also with Visual C++ is doable.)


> Incidentally, this code provides the only example I remember
> where using 'goto' is pretty much unavoidable, in that any
> re-writing without 'goto' seems awkward or inferior in some
> other way.  I guess I should say, at least not that I could
> find, maybe someone else can do better.

The `for(;;)`, `continue;` and `break;` constructs come to mind, so 
you're right, someone else can do better.

At a guess the code counts the number of Unicode code points?

Does it return -1 also for "too long" UTF-8 sequence?


> This code also has the interesting property that along the main
> code path there are no conditional branches (as compiled by gcc
> under -O2).

Smart compiler removed all the `if`'s?

I guess you're flame-baiting a little just for fun, but I chose to take 
it seriously.

- Alf

[toc] | [prev] | [next] | [standalone]

#82812

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2022-01-17 16:16 -0800
Message-ID<86wnixrj8t.fsf@linuxsc.com>
In reply to#82805
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:

> On 17 Jan 2022 19:28, Tim Rentsch wrote:
>
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>> I had an idea how to write a fast UTF-8 strlen, here it is:
>>>
>>> size_t utf8Strlen( char const *str )
>>> {
>>>      struct encode_t { size_t lenIncr, strIncr; };
>>>      static encode_t const encodes[] =
>>>      {
>>>          { 1, 1 },
>>>          { 0, 0 },
>>>          { 1, 2 },
>>>          { 1, 3 },
>>>          { 1, 4 },
>>>          { 0, 0 },
>>>          { 0, 0 },
>>>          { 0, 0 },
>>>          { 0, 0 }
>>>      };
>>>      size_t len = 0;
>>>      for( unsigned char c; (c = *str); )
>>>      {
>>>          encode_t const &enc =
>>>             encodes[(size_t)countl_zero<unsigned char>( ~c )];
>>>          if( !enc.lenIncr ) [[unlikely]]
>>>              return -1;
>>>          len += enc.lenIncr;
>>>          for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>>>              if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>>                  return -1;
>>>      }
>>>      return len;
>>> }
>>>
>>> Has anyone further ideas to improve this ?
>>
>> Just for fun -
>>
>> size_t
>> utf8_units_two( const char *s ){
>>      size_t r = -1;
>>      unsigned char c;
>>
>>    next:
>>      switch(  r++,  c = *s++,  c >> 3  ){
>> 	cases(16,17,18,19,20,21,22,23,31):			return  -1;
>>
>> 	cases(30):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
>> 	cases(28,29):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
>> 	cases(24,25,26,27):	if(  c = *s++,  c >> 6 != 2  )	return  -1;
>> 	cases(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15):		goto  next;
>>
>> 	cases(0):		if(  c != 0  )			goto  next;
>>      }
>>
>>      return  r;
>> }
>
> That's very ugly.

Beauty is in the eye of the beholder.  Personally I think it's
rather pretty.

>> (Note:  the cases() macro produces one 'case X:' for each
>> argument X except the last one where the ':' is omitted,
>> written using the standard C preprocessor, and left as an
>> exercise for any ambitious readers.)
>
> Exercise for you:  test that unrevealed macro with Visual C++.

I don't have access to a Visual C++ system.  The macro I wrote
compiles under gcc and g++ as C99, C11, C++11, C++14, and C++17,
using a -pedantic-errors option.  (Using clang and clang++ gives
the same results.)

> (Making it work also with Visual C++ is doable.)

Does this need more than just writing the definition in
conforming C11 or C++11?

>> Incidentally, this code provides the only example I remember
>> where using 'goto' is pretty much unavoidable, in that any
>> re-writing without 'goto' seems awkward or inferior in some
>> other way.  I guess I should say, at least not that I could
>> find, maybe someone else can do better.
>
> The `for(;;)`, `continue;` and `break;` constructs come to mind, so
> you're right, someone else can do better.

It is of course possible to write the function without using any
'goto's.  Whether such a writing is an improvement is another
matter.  To my eye the goto version expresses the structure more
directly and in a form that is easier to comprehend.  I did try
actually writing a version with a continue-able loop around the
switch(), but it looked clumsy and not as easy to follow as the
goto version.  If you have an example to post I definitely would
like to see it.

> At a guess the code counts the number of Unicode code points?

Yes, sorry, I thought that was apparent from the earlier
context.

> Does it return -1 also for "too long" UTF-8 sequence?

The -1 return values is for character sequences that are not
syntactically well-formed for UTF-8.

>> This code also has the interesting property that along the main
>> code path there are no conditional branches (as compiled by gcc
>> under -O2).
>
> Smart compiler removed all the `if`'s?
>
> I guess you're flame-baiting a little just for fun, but I chose to
> take it seriously.

I'm not flame-baiting at all.  By "main code path" I mean that
part of the code that deals with normal ASCII characters (and not
counting the terminating null character).  The switch() statement
generates an unconditional indirect branch, indexing a table of
32 targets, and the 15 targets for normal ASCII characters simply
go around the loop again, with no tests.  I expect you can see
that based on the line with 15 cases, which just does a 'goto'
to start the loop again.

[toc] | [prev] | [next] | [standalone]

#82815

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2022-01-17 22:43 -0800
Message-ID<86sftlr1c7.fsf@linuxsc.com>
In reply to#82805
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:

> On 17 Jan 2022 19:28, Tim Rentsch wrote:
>
>> (Note:  the cases() macro produces one 'case X:' for each
>> argument X except the last one where the ':' is omitted,
>> written using the standard C preprocessor, and left as an
>> exercise for any ambitious readers.)
>
> Exercise for you:  test that unrevealed macro with Visual C++.

Update after my previous message.  The cases() macro I wrote has
now been tested with Visual C++, and it compiles there without
complaint.

[toc] | [prev] | [next] | [standalone]

#82819

From"Alf P. Steinbach" <alf.p.steinbach@gmail.com>
Date2022-01-18 12:09 +0100
Message-ID<ss674f$a87$1@dont-email.me>
In reply to#82815
On 18 Jan 2022 07:43, Tim Rentsch wrote:
> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:
> 
>> On 17 Jan 2022 19:28, Tim Rentsch wrote:
>>
>>> (Note:  the cases() macro produces one 'case X:' for each
>>> argument X except the last one where the ':' is omitted,
>>> written using the standard C preprocessor, and left as an
>>> exercise for any ambitious readers.)
>>
>> Exercise for you:  test that unrevealed macro with Visual C++.
> 
> Update after my previous message.  The cases() macro I wrote has
> now been tested with Visual C++, and it compiles there without
> complaint.

Good to hear. Visual C++ has or had somewhat non-standard treatment of 
token pasting and variadic macros, and either it's been fixed, or your 
code avoided running into it. A comment in some old code of mine says that

❞ [Visual C++ 2017] is unable to count `__VA_ARGS__` as *n* arguments, 
and instead counts it as 1. Mostly.

Counting the number of arguments of a variadic macro was AFAIK invented 
by Laurent Deniau in 2006, and it can go like this:


#define N_ARGUMENTS( ... )                         \
     INVOKE_MACRO(                                  \
         ARGUMENT_64,                               \
         (                                               \
             __VA_ARGS__,                                \
                                     63, 62, 61, 60,     \
             59, 58, 57, 56, 55, 54, 53, 52, 51, 50,     \
             49, 48, 47, 46, 45, 44, 43, 42, 41, 40,     \
             39, 38, 37, 36, 35, 34, 33, 32, 31, 30,     \
             29, 28, 27, 26, 25, 24, 23, 22, 21, 20,     \
             19, 18, 17, 16, 15, 14, 13, 12, 11, 10,     \
              9,  8,  7,  6,  5,  4,  3,  2,  1,  0      \
         )                                               \
     )

#define ARGUMENT_64( \
      a1,  a2,  a3,  a4,  a5,  a6,  a7,  a8,  a9, a10,  \
     a11, a12, a13, a14, a15, a16, a17, a18, a19, a20,  \
     a21, a22, a23, a24, a25, a26, a27, a28, a29, a30,  \
     a31, a32, a33, a34, a35, a36, a37, a38, a39, a40,  \
     a41, a42, a43, a44, a45, a46, a47, a48, a49, a50,  \
     a51, a52, a53, a54, a55, a56, a57, a58, a59, a60,  \
     a61, a62, a63, a64, ... ) \
     a64


... where `INVOKE_MACRO` tackles the Visual C++ quirks:


/// \brief Invokes the specified macro with the specified arguments list.
/// \hideinitializer
/// \param m        The name of a macro to invoke.
/// \param arglist  A parenthesized list of arguments. Can be empty.
///
/// The only difference between `INVOKE_MACRO` and `INVOKE_MACRO_B` is 
that they're
/// *different* macros. One may have to use both in order to guarantee 
macro expansion in
/// certain (not very well defined) situations.

#define INVOKE_MACRO( m, arglist ) \
     m arglist

#define INVOKE_MACRO_B( m, arglist ) \
     m arglist


I've removed macro name prefixes in the above. For reusable code there 
better be name prefixes, to reduce or avoid name collisions.

- Alf

[toc] | [prev] | [next] | [standalone]

#82817

FromBonita Montero <Bonita.Montero@gmail.com>
Date2022-01-18 09:18 +0100
Message-ID<ss5t4r$efe$1@dont-email.me>
In reply to#82802
Am 17.01.2022 um 19:28 schrieb Tim Rentsch:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
> 
>> I had an idea how to write a fast UTF-8 strlen, here it is:
>>
>> size_t utf8Strlen( char const *str )
>> {
>>      struct encode_t { size_t lenIncr, strIncr; };
>>      static encode_t const encodes[] =
>>      {
>>          { 1, 1 },
>>          { 0, 0 },
>>          { 1, 2 },
>>          { 1, 3 },
>>          { 1, 4 },
>>          { 0, 0 },
>>          { 0, 0 },
>>          { 0, 0 },
>>          { 0, 0 }
>>      };
>>      size_t len = 0;
>>      for( unsigned char c; (c = *str); )
>>      {
>>          encode_t const &enc =
>>             encodes[(size_t)countl_zero<unsigned char>( ~c )];
>>          if( !enc.lenIncr ) [[unlikely]]
>>              return -1;
>>          len += enc.lenIncr;
>>          for( char const *cpEnd = str + enc.strIncr; ++str != cpEnd; )
>>              if( ((unsigned char)*str & 0x0C0) != 0x080 ) [[unlikely]]
>>                  return -1;
>>      }
>>      return len;
>> }
>>
>> Has anyone further ideas to improve this ?
> 
> Just for fun -
> 
> size_t
> utf8_units_two( const char *s ){
>      size_t r = -1;
>      unsigned char c;
> 
>    next:
>      switch(  r++,  c = *s++,  c >> 3  ){
> 	cases(16,17,18,19,20,21,22,23,31):			return  -1;
> 
> 	cases(30):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
> 	cases(28,29):		if(  c = *s++,  c >> 6 != 2  )	return  -1;
> 	cases(24,25,26,27):	if(  c = *s++,  c >> 6 != 2  )	return  -1;
> 	cases(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15):		goto  next;
> 
> 	cases(0):		if(  c != 0  )			goto  next;
>      }
> 
>      return  r;
> }

That's not C or C++ and it does have a lot of branch-mispredictions.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web