I've been trying to think of an analogy for the verification

if( ((UINT64_MAX - c) / 10) >= r)
r = r * 10 + c;
else return -1; /* doesn't fit */

in the procedure below.

I thought of the following, which doesn't quite work. Consider fill up
a bucker of water where we must make sure not to overflow. We're given
one last glass of water to throw in the bucket and we need a strategy to
know whether that last glass would or would not overflow the bucket. We
have all the quantities involved --- the maximum volume in the bucket,
the volume of the glass of water and the volume currently in the bucket.
Say the maximum is M, r is the current volume and c is the volume of
water in the glass. The subtraction M - c represents the amount of
water that would be the exact amount to fill up the bucket completely
without a drop overflowing if we add c to the bucket. So, if the
current volume is greater than M - c, then we can't put c in the bucket.

That gives the general strategy, but it's not too good because there's
nothing in this analogy that matches the division by 10. I could of
course make a up world in which every glass of water you throw in a
bucket makes the volume in the bucket to be multiplied by a factor of 10
before the glass of water goes in. The purpose of an analogy is to make
something odd look natural, so this is a poor analogy.

Any cool ideas? Thank you.

(*) The procedure

uint64_t array_to_uint64(char *s, uint64_t *u)
{ uint64_t pos;
uint64_t r;
uint64_t c;

pos = 0; r = 0;

for ( ;; ) {
c = (uint64_t) (unsigned char) (s[pos] - '0');
if (c < 10) {
if( ((UINT64_MAX - c) / 10) >= r)
r = r * 10 + c;
else return -1; /* doesn't fit */
++pos; continue;
}
break;
}

*u = r;
return pos;
}

On 16/01/2022 02:27, Meredith Montgomery wrote:
> uint64_t array_to_uint64(char *s, uint64_t *u)
> {
> uint64_t pos;
> uint64_t r;
> uint64_t c;
>
> pos = 0; r = 0;
>
> for ( ;; ) {
> c = (uint64_t) (unsigned char) (s[pos] - '0');
> if (c < 10) {
> if( ((UINT64_MAX - c) / 10) >= r)

Dividing by 10 each time is unnecessary (even if usually optimised to
shifts and multiplies).

You only need to make this check after you've already processed 19
characters, as it could overflow on the 20th, but not before.

I think when pos >= 18.

On Sunday, 16 January 2022 at 04:28:22 UTC+2, Meredith Montgomery wrote:
> Any cool ideas? Thank you.

It can not be cool or something as decimal system is arbitrary and
nothing in real world (besides count of human fingers) suggests to
use it. I can try ...

If we want to take 10 times as lot of water as we currently have plus
some then it makes sense to first try if the current water (together with
1/10th of "plus some") fits into 10 times smaller bucket.

But it is unclear if that analogy helps to clarify anything.

Bart <bc@freeuk.com> writes:

> On 16/01/2022 02:27, Meredith Montgomery wrote:
>> uint64_t array_to_uint64(char *s, uint64_t *u)
>> {
>> uint64_t pos;
>> uint64_t r;
>> uint64_t c;
>> pos = 0; r = 0;
>> for ( ;; ) {
>> c = (uint64_t) (unsigned char) (s[pos] - '0');
>> if (c < 10) {
>> if( ((UINT64_MAX - c) / 10) >= r)
>
> Dividing by 10 each time is unnecessary (even if usually optimised to
> shifts and multiplies).
>
> You only need to make this check after you've already processed 19
> characters, as it could overflow on the 20th, but not before.
>
> I think when pos >= 18.

I suppose you're right, but imagine putting such check there. It would
take even more paragraphs to explain it to myself some time later when
I'm trying to figure out what I wrote a while back.

Öö Tiib <ootiib@hot.ee> writes:

> On Sunday, 16 January 2022 at 04:28:22 UTC+2, Meredith Montgomery wrote:
>> Any cool ideas? Thank you.
>
> It can not be cool or something as decimal system is arbitrary and
> nothing in real world (besides count of human fingers) suggests to
> use it. I can try ...
>
> If we want to take 10 times as lot of water as we currently have plus
> some then it makes sense to first try if the current water (together with
> 1/10th of "plus some") fits into 10 times smaller bucket.
>
> But it is unclear if that analogy helps to clarify anything.

Hey, I think that helps: we're at least reading out (more clearly) what
we're doing in the arithmetic expression. I'll go with that for now.
Thank you with so much.

Meredith Montgomery <mmontgomery@levado.to> writes:

> Öö Tiib <ootiib@hot.ee> writes:
>
>> On Sunday, 16 January 2022 at 04:28:22 UTC+2, Meredith Montgomery wrote:
>>> Any cool ideas? Thank you.
>>
>> It can not be cool or something as decimal system is arbitrary and
>> nothing in real world (besides count of human fingers) suggests to
>> use it. I can try ...
>>
>> If we want to take 10 times as lot of water as we currently have plus
>> some then it makes sense to first try if the current water (together with
>> 1/10th of "plus some") fits into 10 times smaller bucket.
>>
>> But it is unclear if that analogy helps to clarify anything.
>
> Hey, I think that helps: we're at least reading out (more clearly) what
> we're doing in the arithmetic expression. I'll go with that for now.
> Thank you with so much.

Hm. A good analogy here is anything with a certain exponential growth
because base-10 numbers grow exponentially. So I guess a colony of
bacteria would do. I can say whenever I add, say, c amount food to the
colony, they multiply themselves by 10 and (remarkably) c new members
are born too. (Researchers are investigating why.) Also astounding is
the fact that once they get very near UINT64_MAX members, they just stop
growing no matter what --- baffling the biologists. The exact condition
is that if the new population size would exceed UINT64_MAX, the c amount
of food does nothing at all. (They stop eating at that point and
everything stays at it is.)

That's probably the best I can do.

Meredith Montgomery <mmontgomery@levado.to> writes:

> Bart <bc@freeuk.com> writes:
>
>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>> {
>>> uint64_t pos;
>>> uint64_t r;
>>> uint64_t c;
>>> pos = 0; r = 0;
>>> for ( ;; ) {
>>> c = (uint64_t) (unsigned char) (s[pos] - '0');
>>> if (c < 10) {
>>> if( ((UINT64_MAX - c) / 10) >= r)
>>
>> Dividing by 10 each time is unnecessary (even if usually optimised to
>> shifts and multiplies).
>>
>> You only need to make this check after you've already processed 19
>> characters, as it could overflow on the 20th, but not before.
>>
>> I think when pos >= 18.
>
> I suppose you're right, but imagine putting such check there. It would
> take even more paragraphs to explain it to myself some time later when
> I'm trying to figure out what I wrote a while back.

You could just check that the array contains a string of digits
lexicographically less than or equal to 18446744073709551615. If there
are fewer digits than this, or, at every position, the digit you have is
no greater than the corresponding digit of that number, you are ok.

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>Meredith Montgomery <mmontgomery@levado.to> writes:
>
>> Bart <bc@freeuk.com> writes:
>>
>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>> {
>>>> uint64_t pos;
>>>> uint64_t r;
>>>> uint64_t c;
>>>> pos = 0; r = 0;
>>>> for ( ;; ) {
>>>> c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>> if (c < 10) {
>>>> if( ((UINT64_MAX - c) / 10) >= r)
>>>
>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>> shifts and multiplies).
>>>
>>> You only need to make this check after you've already processed 19
>>> characters, as it could overflow on the 20th, but not before.
>>>
>>> I think when pos >= 18.
>>
>> I suppose you're right, but imagine putting such check there. It would
>> take even more paragraphs to explain it to myself some time later when
>> I'm trying to figure out what I wrote a while back.
>
>You could just check that the array contains a string of digits
>lexicographically less than or equal to 18446744073709551615. If there
>are fewer digits than this, or, at every position, the digit you have is
>no greater than the corresponding digit of that number, you are ok.

That reminds me of an algorithm used on BCD mainframes to do addition
and subtraction on large (up to 100 digit) variable length operands.

The most significant digit was stored as the lowest addressed digit (nibble).

The algorithm handled addition and subtraction of two variable length
operands (with overflow detection) with a single pass starting from the
most significant digit of each operand.

"The processor uses an adder that accumulates two
fields from the most sigificant to the least significant
digit positions. Reverse addition ... has the advantage of
detecting an overflow condition prior to altering the
receiving field for the result"

"If the data fields are signed, sign manipulation takes place
prior to the addition since they are the most significant digits."

Fundamentally, the algorithm sign/zero extends the smaller operand
and adds a digit from each operand; if carry occurs and if all prior additions
(if any) had summed to nine, overflow is signaled and the operation completes.

To avoid writing to the receiving field before overflow is detected,
the processor had a nines-counter which counted the number of leading
digits each having the value 9. Once a digit no longer sums to 9 or has
a carry, the BCD digit '9' is flushed to the receiving field until the nines
counter is zero. The most recent digit sum is stored in a register
to accomodate carry (add one to the register, flush it, and move current
result to register).

1025475_B2500_B3500_RefMan_Oct69.pdf (flowchart p. 5-11)

scott@slp53.sl.home (Scott Lurndal) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>Meredith Montgomery <mmontgomery@levado.to> writes:
>>
>>> Bart <bc@freeuk.com> writes:
>>>
>>>> On 16/01/2022 02:27, Meredith Montgomery wrote:
>>>>> uint64_t array_to_uint64(char *s, uint64_t *u)
>>>>> {
>>>>> uint64_t pos;
>>>>> uint64_t r;
>>>>> uint64_t c;
>>>>> pos = 0; r = 0;
>>>>> for ( ;; ) {
>>>>> c = (uint64_t) (unsigned char) (s[pos] - '0');
>>>>> if (c < 10) {
>>>>> if( ((UINT64_MAX - c) / 10) >= r)
>>>>
>>>> Dividing by 10 each time is unnecessary (even if usually optimised to
>>>> shifts and multiplies).
>>>>
>>>> You only need to make this check after you've already processed 19
>>>> characters, as it could overflow on the 20th, but not before.
>>>>
>>>> I think when pos >= 18.
>>>
>>> I suppose you're right, but imagine putting such check there. It would
>>> take even more paragraphs to explain it to myself some time later when
>>> I'm trying to figure out what I wrote a while back.
>>
>>You could just check that the array contains a string of digits
>>lexicographically less than or equal to 18446744073709551615. If there
>>are fewer digits than this, or, at every position, the digit you have is
>>no greater than the corresponding digit of that number, you are ok.
>
> That reminds me of an algorithm used on BCD mainframes to do addition
> and subtraction on large (up to 100 digit) variable length operands.
>
> The most significant digit was stored as the lowest addressed digit (nibble).
>
> The algorithm handled addition and subtraction of two variable length
> operands (with overflow detection) with a single pass starting from the
> most significant digit of each operand.
>
> "The processor uses an adder that accumulates two
> fields from the most sigificant to the least significant
> digit positions. Reverse addition ... has the advantage of
> detecting an overflow condition prior to altering the
> receiving field for the result"
>
> "If the data fields are signed, sign manipulation takes place
> prior to the addition since they are the most significant digits."
>
> Fundamentally, the algorithm sign/zero extends the smaller operand
> and adds a digit from each operand; if carry occurs and if all prior additions
> (if any) had summed to nine, overflow is signaled and the operation completes.
>
> To avoid writing to the receiving field before overflow is detected,
> the processor had a nines-counter which counted the number of leading
> digits each having the value 9. Once a digit no longer sums to 9 or has
> a carry, the BCD digit '9' is flushed to the receiving field until the nines
> counter is zero. The most recent digit sum is stored in a register
> to accomodate carry (add one to the register, flush it, and move current
> result to register).
>
> 1025475_B2500_B3500_RefMan_Oct69.pdf (flowchart p. 5-11)

Interesting. Thanks.

Unrelated, but I noticed this gem in the list of the system's
advantages:

d. Programming so simple it can be started by one programmer and
finished by another

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>scott@slp53.sl.home (Scott Lurndal) writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

>>>
>>>You could just check that the array contains a string of digits
>>>lexicographically less than or equal to 18446744073709551615. If there
>>>are fewer digits than this, or, at every position, the digit you have is
>>>no greater than the corresponding digit of that number, you are ok.
>>
>> That reminds me of an algorithm used on BCD mainframes to do addition
>> and subtraction on large (up to 100 digit) variable length operands.
>>
>> The most significant digit was stored as the lowest addressed digit (nibble).
>>
>> The algorithm handled addition and subtraction of two variable length
>> operands (with overflow detection) with a single pass starting from the
>> most significant digit of each operand.
>>
>> "The processor uses an adder that accumulates two
>> fields from the most sigificant to the least significant
>> digit positions. Reverse addition ... has the advantage of
>> detecting an overflow condition prior to altering the
>> receiving field for the result"
>>
>> "If the data fields are signed, sign manipulation takes place
>> prior to the addition since they are the most significant digits."
>>
>> Fundamentally, the algorithm sign/zero extends the smaller operand
>> and adds a digit from each operand; if carry occurs and if all prior additions
>> (if any) had summed to nine, overflow is signaled and the operation completes.
>>
>> To avoid writing to the receiving field before overflow is detected,
>> the processor had a nines-counter which counted the number of leading
>> digits each having the value 9. Once a digit no longer sums to 9 or has
>> a carry, the BCD digit '9' is flushed to the receiving field until the nines
>> counter is zero. The most recent digit sum is stored in a register
>> to accomodate carry (add one to the register, flush it, and move current
>> result to register).
>>
>> 1025475_B2500_B3500_RefMan_Oct69.pdf (flowchart p. 5-11)
>
>Interesting. Thanks.
>
>Unrelated, but I noticed this gem in the list of the system's
>advantages:
>
> d. Programming so simple it can be started by one programmer and
> finished by another

Indeed, it was quite simple to program. Reading a memory
dump was a breeze:

RECD NO FILE: TRKTAP EOF = 394 7/27/2021 (TUESDAY) 17:05 PAGE 0001

1 40F87AF2F8 4000100064 0790000000 6430017400 4001000000 0010010426 94C2000064 0000060768 5600100007 7972000000
8 : 2 8 m B `
(00100) 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0003000064
...00100/001
2 E3D9D2E3C1 D7F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0
T R K T A P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(00100) F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0 F0F0F0F0F0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...00100/001
3 E3D76DD6E4 E340404040 4040D7D9D6 C6C9D30400 0040404040 4040E00149 6001600000 00000000C4 C9E2D24040 0040404040
T P _ O U T P R O F I L \ - - D I S K
(00100) 4040404040 4040404040 4040400000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
...00100/001
4 D7D9C9D5E3 4040404040 4040D7D9E3 E3D9D20200 0040404040 4040E00600 8001600000 00000000C4 C9E2D24040 0040404040
P R I N T P R T T R K \ - D I S K
(00100) 4040404040 4040404040 4040400000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
...00100/001
5 E3D9D2E3C1 D740404040 4040E3D9D2 E3C1D70400 0040404040 4040E00668 0001600000 00000000C4 C9E2D24040 0040404040
T R K T A P T R K T A P \ - D I S K
(00100) 4040404040 4040404040 4040400000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
...00100/001
Decoding the instruction stream was trivial by eye:

0547000E LIX IX1 IX4 Save table address 003104 670740 100008
0548000E Validate(IX2,"+ERR-6:") /Validate Address
0548000M MVW IX2 -VRqst Set request ptr 003116 120002 000016 C00340
0548000M MVN +ERR-6 LL -VLab Set error label 003134 11A606 004446 C00348
0548000M VEN -Vparm Valid Do the validation 003152 350007 E00340 0D008356
0549000E
0550000E MVW RQ-CSD X2 STRCSD X7 Set descriptor 003172 120005 800004 4E000002
0551000E MPY 05 BADR SZ TBL-RN X4 IX1 Branch table offset 003192 05A502 000060 4D000004 100008
0552000E INC DOVRD1 IX1 Make code relative 003218 010707 100108 100008

note the MPY instruction:
Opcode = 05
AFBF = A502 (A Field and B field lengths, bcd; AF=A5 (5 digit unsigned literal), BF=02
A = 000060 (Literal 6 encoded in address field)
B = 4D000004 (Four digits from the base of Index Register 4)
C = 100008 (Signed 7 (AF + BF) digit result at address 8 in memory, which is also IX1)

How about that. I wrote it with g++ and it should fit with clang++:

#include <iostream>
#include <stdexcept>
#include <string>

using namespace std;

unsigned long long parseUll( char const *str )
{ using ull_t = unsigned long long;
ull_t value = 0;
for( unsigned char const *scn = (unsigned char const *)str; *scn; ++scn )
{
if( __builtin_umulll_overflow( value, 10, &value ) )
throw overflow_error( "parseUll overflow" );;
if( __builtin_uaddll_overflow( value, *scn - '0', &value ) )
throw overflow_error( "parseUll overflow" );;
}
return value;
}

int main()
{ for( ; ; )
try
{
string strValue;
cin >> strValue;
cout << parseUll( strValue.c_str() ) << endl;
}
catch( overflow_error & )
{
cout << "overflow" << endl;
}
}

On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
> How about that. I wrote it with g++ and it should fit with clang++:
>

The analogy that OP asked for was likely meant from real word not from
other programming language.

Am 19.01.2022 um 15:08 schrieb Öö Tiib:
> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
>> How about that. I wrote it with g++ and it should fit with clang++:
>>
>
> The analogy that OP asked for was likely meant from real word not from
> other programming language.

It's just about the principle; the code can be easily ported to C.

Am 19.01.2022 um 16:31 schrieb Bonita Montero:

> Am 19.01.2022 um 15:08 schrieb Öö Tiib:

>> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:

>>> How about that. I wrote it with g++ and it should fit with clang++:
>>>

>> The analogy that OP asked for was likely meant from real word not from
>> other programming language.

> It's just about the principle; the code can be easily ported to C.

Here's a slightly better implementation with improvements for MSVC
with a benchmark.

#include <iostream>
#include <stdexcept>
#include <string>
#include <string>
#include <vector>
#include <random>
#include <sstream>
#include <chrono>
#include <immintrin.h>

using namespace std;
using namespace chrono;

#if defined(_MSC_VER)
__declspec(noinline)
#elif defined(__GNUC__)
__attribute__((noinline))
#endif
unsigned long long parseUll( char const *str )
{ unsigned long long value = 0;
for( ; *str; ++str )
{
#if (!defined(__llvm__) && defined(__GNUC__) && !defined(_MSC_VER)) ||
defined(PARSE_ULL_SIMPLE)
if( value * 10 / 10 != value )
goto overflow;
value *= 10;
unsigned char digit = *str - '0';
if( value + digit < value )
goto overflow;
value += digit;
#elif defined(__llvm__) || defined(__GNUC__)
if( __builtin_umulll_overflow( value, 10, &value ) )
goto overflow;
if( __builtin_uaddll_overflow( value, (unsigned char)*str - '0', &value) )
goto overflow;
#elif defined(_MSC_VER)
unsigned long long hi;
value = _mulx_u64( value, 10, &hi );
if( hi )
goto overflow;
// _addcarry_u64 specified but missing (MSVC 2022)
if( value + ((unsigned char)*str - '0') < value )
goto overflow;
value += (unsigned char)*str - '0';
#endif
}
return value;
overflow:
throw overflow_error( "parseUll() overflow" );
}

unsigned long long volatile vSum;

int main()
{ constexpr size_t N = 1000;
vector<string> rNums;
rNums.reserve( N );
mt19937_64 mt;
uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
ostringstream oss;
for( size_t i = 0; i != N; ++i )
{
oss.str( "" );
oss << uidValues( mt );
rNums.emplace_back( oss.str() );
}
unsigned long long sum = 0;
auto start = high_resolution_clock::now();
for( size_t i = 0; i != 1000; ++i )
for( string &str : rNums )
sum += parseUll( str.c_str() );
::vSum = sum;
double ns = (int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / (1000.0 * N);
cout << ns << endl;
}

On 19/01/2022 17:02, Bonita Montero wrote:
> Am 19.01.2022 um 16:31 schrieb Bonita Montero:
>
>> Am 19.01.2022 um 15:08 schrieb Öö Tiib:
>
>>> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
>
>>>> How about that. I wrote it with g++ and it should fit with clang++:
>>>>
>
>>> The analogy that OP asked for was likely meant from real word not from
>>> other programming language.
>
>> It's just about the principle; the code can be easily ported to C.
>
> Here's a slightly better implementation with improvements for MSVC
> with a benchmark.
>
> #include <iostream>
> #include <stdexcept>
> #include <string>
> #include <string>
> #include <vector>
> #include <random>
> #include <sstream>
> #include <chrono>
> #include <immintrin.h>
>
> using namespace std;
> using namespace chrono;
>
> #if defined(_MSC_VER)
> __declspec(noinline)
> #elif defined(__GNUC__)
> __attribute__((noinline))
> #endif
> unsigned long long parseUll( char const *str )
> {
>     unsigned long long value = 0;
>     for( ; *str; ++str )
>     {
> #if (!defined(__llvm__) && defined(__GNUC__) && !defined(_MSC_VER)) ||
> defined(PARSE_ULL_SIMPLE)
>         if( value * 10 / 10 != value )
>             goto overflow;
>         value *= 10;
>         unsigned char digit = *str - '0';
>         if( value + digit < value )
>             goto overflow;
>         value += digit;
> #elif defined(__llvm__) || defined(__GNUC__)
>         if( __builtin_umulll_overflow( value, 10, &value ) )
>             goto overflow;
>         if( __builtin_uaddll_overflow( value, (unsigned char)*str -
> '0', &value) )
>             goto overflow;
> #elif defined(_MSC_VER)
>         unsigned long long hi;
>         value = _mulx_u64( value, 10, &hi );
>         if( hi )
>             goto overflow;
>         // _addcarry_u64 specified but missing (MSVC 2022)
>         if( value + ((unsigned char)*str - '0') < value )
>             goto overflow;
>         value += (unsigned char)*str - '0';
> #endif
>     }
>     return value;
> overflow:
>     throw overflow_error( "parseUll() overflow" );
> }
>
> unsigned long long volatile vSum;
>
> int main()
> {
>     constexpr size_t N = 1000;
>     vector<string> rNums;
>     rNums.reserve( N );
>     mt19937_64 mt;
>     uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
>     ostringstream oss;
>     for( size_t i = 0; i != N; ++i )
>     {
>         oss.str( "" );
>         oss << uidValues( mt );
>         rNums.emplace_back( oss.str() );
>     }
>     unsigned long long sum = 0;
>     auto start = high_resolution_clock::now();
>     for( size_t i = 0; i != 1000; ++i )
>         for( string &str : rNums )
>             sum += parseUll( str.c_str() );
>     ::vSum = sum;
>     double ns = (int64_t)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / (1000.0 * N);
>     cout << ns << endl;
> }

Complicated. I used the simpler **C** code below. It's runtime was 10%
slower than the C++ (that is, elapsed time of the 10,000 outer loop for
both).

(Building the C++ took 3.3 seconds; building the C even with a slow gcc
took 0.32 seconds. Faster C compilers do it instantly.)

My version calls strlen on the string (which is also assumed here to
contain the number without signs, leading zeros, and to end on the last
digit).

In practice this information will often already be known. If I modify
parseull() to take a length (here emulated with a table of precalculated
values), then the C version is 25% faster than your C++.

Maybe your C++ version can also benefit from knowing the length, but I
can't see how from the way it's written.

------------------------------------------------------------

u64 parseull(char* s) {
int length=strlen(s);

if (length>20 || (length==20 && strcmp(s,
"18446744073709551615")>0)) {
puts("Overflow"); exit(1);
}

u64 a=*s -'0';
while (--length) {a=a*10+*++s-'0';};
return a;
}

int main(void) {
u64 a;
volatile u64 sum=0;

for (int j=0; j<10000; ++j) {
for (int i=0; i<1000; ++i) {
sum+=parseull(numbers[i]);
}
}

printf("%llu\n",sum);
}

Am 19.01.2022 um 19:27 schrieb Bart:
> On 19/01/2022 17:02, Bonita Montero wrote:
>> Am 19.01.2022 um 16:31 schrieb Bonita Montero:
>>
>>> Am 19.01.2022 um 15:08 schrieb Öö Tiib:
>>
>>>> On Wednesday, 19 January 2022 at 09:52:58 UTC+2, Bonita Montero wrote:
>>
>>>>> How about that. I wrote it with g++ and it should fit with clang++:
>>>>>
>>
>>>> The analogy that OP asked for was likely meant from real word not from
>>>> other programming language.
>>
>>> It's just about the principle; the code can be easily ported to C.
>>
>> Here's a slightly better implementation with improvements for MSVC
>> with a benchmark.
>>
>> #include <iostream>
>> #include <stdexcept>
>> #include <string>
>> #include <string>
>> #include <vector>
>> #include <random>
>> #include <sstream>
>> #include <chrono>
>> #include <immintrin.h>
>>
>> using namespace std;
>> using namespace chrono;
>>
>> #if defined(_MSC_VER)
>> __declspec(noinline)
>> #elif defined(__GNUC__)
>> __attribute__((noinline))
>> #endif
>> unsigned long long parseUll( char const *str )
>> {
>>      unsigned long long value = 0;
>>      for( ; *str; ++str )
>>      {
>> #if (!defined(__llvm__) && defined(__GNUC__) && !defined(_MSC_VER)) ||
>> defined(PARSE_ULL_SIMPLE)
>>          if( value * 10 / 10 != value )
>>              goto overflow;
>>          value *= 10;
>>          unsigned char digit = *str - '0';
>>          if( value + digit < value )
>>              goto overflow;
>>          value += digit;
>> #elif defined(__llvm__) || defined(__GNUC__)
>>          if( __builtin_umulll_overflow( value, 10, &value ) )
>>              goto overflow;
>>          if( __builtin_uaddll_overflow( value, (unsigned char)*str -
>> '0', &value) )
>>              goto overflow;
>> #elif defined(_MSC_VER)
>>          unsigned long long hi;
>>          value = _mulx_u64( value, 10, &hi );
>>          if( hi )
>>              goto overflow;
>>          // _addcarry_u64 specified but missing (MSVC 2022)
>>          if( value + ((unsigned char)*str - '0') < value )
>>              goto overflow;
>>          value += (unsigned char)*str - '0';
>> #endif
>>      }
>>      return value;
>> overflow:
>>      throw overflow_error( "parseUll() overflow" );
>> }
>>
>> unsigned long long volatile vSum;
>>
>> int main()
>> {
>>      constexpr size_t N = 1000;
>>      vector<string> rNums;
>>      rNums.reserve( N );
>>      mt19937_64 mt;
>>      uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
>>      ostringstream oss;
>>      for( size_t i = 0; i != N; ++i )
>>      {
>>          oss.str( "" );
>>          oss << uidValues( mt );
>>          rNums.emplace_back( oss.str() );
>>      }
>>      unsigned long long sum = 0;
>>      auto start = high_resolution_clock::now();
>>      for( size_t i = 0; i != 1000; ++i )
>>          for( string &str : rNums )
>>              sum += parseUll( str.c_str() );
>>      ::vSum = sum;
>>      double ns = (int64_t)duration_cast<nanoseconds>(
>> high_resolution_clock::now() - start ).count() / (1000.0 * N);
>>      cout << ns << endl;
>> }
>
> Complicated. I used the simpler **C** code below. It's runtime was 10%
> slower than the C++ (that is, elapsed time of the 10,000 outer loop for
> both).
>
> (Building the C++ took 3.3 seconds; building the C even with a slow gcc
> took 0.32 seconds. Faster C compilers do it instantly.)
>
> My version calls strlen on the string (which is also assumed here to
> contain the number without signs, leading zeros, and to end on the last
> digit).
>
> In practice this information will often already be known. If I modify
> parseull() to take a length (here emulated with a table of precalculated
> values), then the C version is 25% faster than your C++.
>
> Maybe your C++ version can also benefit from knowing the length, but I
> can't see how from the way it's written.
>
>
> ------------------------------------------------------------
>
>     u64 parseull(char* s) {
>         int length=strlen(s);
>
>         if (length>20 || (length==20 && strcmp(s,
> "18446744073709551615")>0)) {
>             puts("Overflow"); exit(1);
>         }
>
>         u64 a=*s -'0';
>         while (--length) {a=a*10+*++s-'0';};
>         return a;
>     }
>
>     int main(void) {
>         u64 a;
>         volatile u64 sum=0;
>
>         for (int j=0; j<10000; ++j) {
>             for (int i=0; i<1000; ++i) {
>                 sum+=parseull(numbers[i]);
>             }
>         }
>
>         printf("%llu\n",sum);
>     }
>
>

That's slower than the variants with intrinsics.

Bart <bc@freeuk.com> writes:
>On 19/01/2022 17:02, Bonita Montero wrote:

>
>Complicated. I used the simpler **C** code below. It's runtime was 10%
>slower than the C++ (that is, elapsed time of the 10,000 outer loop for
>both).

I just use strtoll. Why reinvent the wheel?

On 19/01/2022 18:46, Scott Lurndal wrote:
> Bart <bc@freeuk.com> writes:
>> On 19/01/2022 17:02, Bonita Montero wrote:
>
>>
>> Complicated. I used the simpler **C** code below. It's runtime was 10%
>> slower than the C++ (that is, elapsed time of the 10,000 outer loop for
>> both).
>
> I just use strtoll. Why reinvent the wheel?

It needs to be stroull() for this purpose, which is more elusive (gcc
has it on Windows, but the two other compilers I have don't),

As to why it's worth reinventing, if I use strtoull instead, then my
benchmarks runs in 2.8 seconds instead of 0.28 seconds; it's much slower!

Besides which, when I need to do this stuff, the requirements are more
diverse (eg dealing with numeric separators, or determining whether the
literal fits in i64, u64, i128, u128, or represents a big number).

Bart <bc@freeuk.com> writes:
>On 19/01/2022 18:46, Scott Lurndal wrote:
>> Bart <bc@freeuk.com> writes:
>>> On 19/01/2022 17:02, Bonita Montero wrote:
>>
>>>
>>> Complicated. I used the simpler **C** code below. It's runtime was 10%
>>> slower than the C++ (that is, elapsed time of the 10,000 outer loop for
>>> both).
>>
>> I just use strtoll. Why reinvent the wheel?
>
>It needs to be stroull() for this purpose, which is more elusive (gcc
>has it on Windows, but the two other compilers I have don't),
>
>As to why it's worth reinventing, if I use strtoull instead, then my
>benchmarks runs in 2.8 seconds instead of 0.28 seconds; it's much slower!

Does your benchmark measure anything useful?

Very, very, very few application will have strtoull as a dominant
performance driver.

On 19/01/2022 21:12, Scott Lurndal wrote:
> Bart <bc@freeuk.com> writes:
>> On 19/01/2022 18:46, Scott Lurndal wrote:
>>> Bart <bc@freeuk.com> writes:
>>>> On 19/01/2022 17:02, Bonita Montero wrote:
>>>
>>>>
>>>> Complicated. I used the simpler **C** code below. It's runtime was 10%
>>>> slower than the C++ (that is, elapsed time of the 10,000 outer loop for
>>>> both).
>>>
>>> I just use strtoll. Why reinvent the wheel?
>>
>> It needs to be stroull() for this purpose, which is more elusive (gcc
>> has it on Windows, but the two other compilers I have don't),
>>
>> As to why it's worth reinventing, if I use strtoull instead, then my
>> benchmarks runs in 2.8 seconds instead of 0.28 seconds; it's much slower!
>
> Does your benchmark measure anything useful?

Only text to binary conversion of numbers, but then nobody ever does
that do that? Apart from processing textual formats such XML, HTML,
source code of virtually every language, configuration files, database
files, CDF/CSV and other data files.

>
> Very, very, very few application will have strtoull as a dominant
> performance driver.

Plenty of slow software about. Ignoring things like this adds up.

But in the case of strtoull, there are other issues with it:

* Not all compilers may recognise it

* The performance depends on the library used

Using your own routine for this simple task eliminates those variables.

The timing I quoted was the worst:

* gcc/strtoull on Windows: 2.8 seconds (for 1M conversions)

* gcc/strtoull on WSL: 0.6 seconds

* gcc/_strtoui64 on Windows (in msvcrt): 0.7 seconds

* My parseull routine on Windows: 0.28/0.35 seconds (with/without length)

The intention was anyway to match that complex C++ code, which was also
the wrong language, and also took 10 times as long to compile.

Bart <bc@freeuk.com> writes:

> But in the case of strtoull, there are other issues with it:
>
> * Not all compilers may recognise it

It's almost always library issue, not a compiler issue. Any
implementation (compiler + library) that does not have it is a poor one
since it's been standard for a long time now.

> * The performance depends on the library used
>
> Using your own routine for this simple task eliminates those variables.
>
> The timing I quoted was the worst:
>
> * gcc/strtoull on Windows: 2.8 seconds (for 1M conversions)
>
> * gcc/strtoull on WSL: 0.6 seconds
>
> * gcc/_strtoui64 on Windows (in msvcrt): 0.7 seconds

You keep citing figures with little useful information. What length
numbers? What are these various (apparently slow) implementation of
strtoull that you have managed to find? Calling them gcc/strtoull is
not helpful.

For 10^6 numbers with, on average, 18.3 digits, the strtoull on a recent
Ubuntu install (glibc 2.34) does the conversions in 0.042 seconds
(i5-8265U CPU). Is your machine really more than 10 times slower than
my laptop?

> * My parseull routine on Windows: 0.28/0.35 seconds (with/without
> length)

This one probably doesn't do the same job, so it's not a direct
comparison.

--
Ben.

Am 19.01.2022 um 19:44 schrieb Bonita Montero:

> That's slower than the variants with intrinsics.

Here's a little benchmark:

#include <iostream>
#include <stdexcept>
#include <string>
#include <string>
#include <vector>
#include <random>
#include <sstream>
#include <chrono>
#include <cstring>
#include <immintrin.h>

using namespace std;
using namespace chrono;

unsigned long long parseUllIntrinsic( char const *str );
unsigned long long parseUllStd( char const *str );
unsigned long long parseUllBart( char const *str );

unsigned long long volatile vSum;

int main()
{ constexpr size_t N = 1000;
vector<string> rNums;
rNums.reserve( N );
mt19937_64 mt;
uniform_int_distribution<unsigned long long> uidValues( 0, -1 );
ostringstream oss;
for( size_t i = 0; i != N; ++i )
{
oss.str( "" );
oss << uidValues( mt );
rNums.emplace_back( oss.str() );
}
auto bench = [&]( unsigned long long (*parseUllFn)( char const *) ) ->
double
{
unsigned long long sum = 0;
auto start = high_resolution_clock::now();
for( size_t i = 0; i != 10'000; ++i )
for( string &str : rNums )
sum += parseUllFn( str.c_str() );
::vSum = sum;
return (int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / (10'000.0 * N);
};
cout << "intrinsic: " << bench( parseUllIntrinsic ) << endl;
cout << "std: " << bench( parseUllStd ) << endl;
cout << "Bart: " << bench( parseUllBart ) << endl;
}

#if defined(_MSC_VER)
__declspec(noinline)
#elif defined(__GNUC__)
__attribute__((noinline))
#endif
unsigned long long parseUllIntrinsic( char const *str )
{ if( !*str )
return 0;
unsigned long long value = (unsigned char)*str++ - '0';
for( ; *str; ++str )
{
#if defined(__llvm__) || defined(__GNUC__)
if( __builtin_umulll_overflow( value, 10, &value ) )
goto overflow;
if( __builtin_uaddll_overflow( value, (unsigned char)*str - '0', &value) )
goto overflow;
#elif defined(_MSC_VER)
unsigned long long hi;
value = _mulx_u64( value, 10, &hi );
if( hi )
goto overflow;
// _addcarry_u64 specified but missing (MSVC 2022)
if( value + ((unsigned char)*str - '0') < value )
goto overflow;
value += (unsigned char)*str - '0';
#else
#error no intinsic version
#endif
}
return value;
overflow:
throw overflow_error( "parseUll() overflow" );
}

#if defined(_MSC_VER)
__declspec(noinline)
#elif defined(__GNUC__)
__attribute__((noinline))
#endif
unsigned long long parseUllStd( char const *str )
{ unsigned long long value;
if( !*str )
return 0;
value = (unsigned char)*str++ - '0';
for( ; *str; ++str )
{
if( value * 10 / 10 != value )
goto overflow;
value *= 10;
unsigned char digit = *str - '0';
if( value + digit < value )
goto overflow;
value += digit;
}
return value;
overflow:
throw overflow_error( "parseUll() overflow" );
}

#if defined(_MSC_VER)
__declspec(noinline)
#elif defined(__GNUC__)
__attribute__((noinline))
#endif
unsigned long long parseUllBart( char const *str )
{ size_t len = strlen( str );
unsigned long long value;
if( len > 20 || len == 20 && strcmp( str, "18446744073709551615" ) > 0 )
goto overflow;
if( !*str )
return 0;
value = (unsigned char)*str++ - '0';
while( *str )
value *= 10,
value += (unsigned char)*str++ - '0';
return value;
overflow:
throw overflow_error( "parseUll() overflow" );
}

Here are the MSVC-results:

intrinsic: 20.4304
std: 20.3481
Bart: 22.2739

The gcc/O2-results:

intrinsic: 20.4639
std: 20.7395
Bart: 23.3007

The clang++/O2-results:

intrinsic: 21.1037
std: 21.9567
Bart: 22.7341

On 20/01/2022 03:49, Ben Bacarisse wrote:
> Bart <bc@freeuk.com> writes:
>
>> But in the case of strtoull, there are other issues with it:
>>
>> * Not all compilers may recognise it
>
> It's almost always library issue, not a compiler issue. Any
> implementation (compiler + library) that does not have it is a poor one
> since it's been standard for a long time now.
>
>> * The performance depends on the library used
>>
>> Using your own routine for this simple task eliminates those variables.
>>
>> The timing I quoted was the worst:
>>
>> * gcc/strtoull on Windows: 2.8 seconds (for 1M conversions)
>>
>> * gcc/strtoull on WSL: 0.6 seconds
>>
>> * gcc/_strtoui64 on Windows (in msvcrt): 0.7 seconds
>
> You keep citing figures with little useful information. What length
> numbers? What are these various (apparently slow) implementation of
> strtoull that you have managed to find? Calling them gcc/strtoull is
> not helpful.
>

The full program is here:

https://github.com/sal55/langs/blob/master/parseull.c

You need to uncomment the routine you want in the inner loop. The
numbers are the ones generated with BM's program. Timings are elapsed
time from running the program, measured externally.

> For 10^6 numbers with, on average, 18.3 digits, the strtoull on a recent
> Ubuntu install (glibc 2.34) does the conversions in 0.042 seconds
> (i5-8265U CPU). Is your machine really more than 10 times slower than
> my laptop?

Sorry, that was my mistake: it's 10^7 conversions (originally 10^6 in
the C++ code but that was too quick to easily measure).

>> * My parseull routine on Windows: 0.28/0.35 seconds (with/without
>> length)
>
> This one probably doesn't do the same job, so it's not a direct
> comparison.

It was supposed to do the same job as BM's program: take a string
containing only digits and convert them while checking for overflows.

Although mine won't allow leading zeros if the overflow check is to
work; that would slow it down slightly to eliminate them.

Bart <bc@freeuk.com> writes:

> On 20/01/2022 03:49, Ben Bacarisse wrote:
>> Bart <bc@freeuk.com> writes:

>>> * My parseull routine on Windows: 0.28/0.35 seconds (with/without
>>> length)
>>
>> This one probably doesn't do the same job, so it's not a direct
>> comparison.
>
> It was supposed to do the same job as BM's program: take a string
> containing only digits and convert them while checking for overflows.

Right. But it does not do the same job as the other functions you gave
timings for /in the post I replied to/.

--
Ben.

On Thursday, 20 January 2022 at 09:08:39 UTC+2, Bonita Montero wrote:
> Am 19.01.2022 um 19:44 schrieb Bonita Montero:
>
> > That's slower than the variants with intrinsics.
> Here's a little benchmark:

All those test functions do something strange compared to what OP's posted
code did. OP posted relatively reasonable function like that:

uint64_t array_to_uint64(char *s, uint64_t *u) {./*...*/}

For example to string "15A" that function returned 2 and put 15 into value
pointed by u. That made sense.
Your code however returns 167. That feels nonsense, where it was specified?
It does not matter at what speed a code gives such nonsense answers. At
least among my customers.