Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #164478
| From | Bart <bc@freeuk.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: on an analogy for verifying whether another digit fits (into an unsigned type) |
| Date | 2022-01-19 18:27 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <ss9l6b$ctv$1@dont-email.me> (permalink) |
| References | <86mtjws9cg.fsf@levado.to> <ss8g0e$8dv$1@dont-email.me> <6df246f4-204e-4fd1-ad91-bb4fce96f100n@googlegroups.com> <ss9arn$rtm$1@dont-email.me> <ss9g7q$5ud$1@dont-email.me> |
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);
}
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-15 23:27 -0300
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-16 18:44 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-17 09:48 -0300
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 17:27 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-17 18:06 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 20:59 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-18 01:01 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 22:15 -0300
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-29 02:36 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 09:12 -0300
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-30 15:13 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-16 12:15 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-17 09:53 -0300
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-17 10:12 -0300
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 08:52 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-19 06:08 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 16:31 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 18:02 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-19 18:27 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-19 19:44 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-20 08:08 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-20 09:47 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-19 18:46 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-19 20:59 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-19 21:12 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-19 22:25 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-20 03:49 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-20 10:05 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-20 17:02 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-20 19:20 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-20 19:31 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-23 14:26 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 00:13 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-24 00:38 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 01:09 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-24 01:15 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 11:21 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 15:54 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 13:08 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 22:51 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-24 15:57 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 16:52 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Öö Tiib <ootiib@hot.ee> - 2022-01-24 10:17 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 18:23 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 13:15 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 11:51 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-23 17:38 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 11:22 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-24 15:51 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-24 22:03 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 15:33 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-25 00:09 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-01-24 21:14 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Manfred <invalid@invalid.add> - 2022-01-26 21:01 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bart <bc@freeuk.com> - 2022-01-26 20:53 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Manfred <noname@add.invalid> - 2022-01-27 03:42 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-20 19:24 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-21 08:07 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 06:01 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-21 17:59 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) scott@slp53.sl.home (Scott Lurndal) - 2022-01-21 17:41 +0000
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Bonita Montero <Bonita.Montero@gmail.com> - 2022-01-21 19:26 +0100
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-21 17:12 -0800
Re: on an analogy for verifying whether another digit fits (into an unsigned type) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 22:25 -0300
csiph-web