Efficient integer input / output (with a use case)

Question

The task:

A set of functions used to read/write integers from/to stdin/stdout as efficiently as possible.

Rationale:

printf/scanf fail to offer best possible performance. For example, it is possible to write a solution for UVA problem 10055 "Hashmat the Brave Warrior" that runs in below 0.01 sec, however a straightforward solution with printf / scanftypically runs in around 0.02 sec. Digit by digit input/output of numbers using getchar_unlocked and putchar_unlocked is the only way I'm aware of to make it run as fast as possible.

Result:

Functions rd* read integers, and functions wr* write integers.
The next few letters in the function's name describe the type the function operates on, with similar naming conventions to printf/scanf format specifiers. So for example rdllu reads an unsigned long long int, while wrhhi writes the numerical value of a signed char. (It is possible to use a function operating on unsigned integers to read / write a signed integer, this will simply skip checking if the integer is negative).
In addition, every rd* function has a counterpart ending with eof, meaning that it checks for EndOfFile and returns 0 in that case. Functions not checking for EOF always return 1. This is to enable convenient reading a few integers in a loop like while(rdllueof(&a) && rdllu(&b)) {do_something;}.
You might say that these names are cryptic and unreadable. Honestly though, I think they're not much worse than standard library functions like strncmpy. And definitely much better than the alternative, that is read_unsigned_long_long_int_while_checking_for_eof. If I am to avoid such long names I'm not sure what else can I devise.

Approach:

Sorry for using macros to generate these functions, that's another point I suppose you might think is wrong. But otherwise I'd have to write 30 repetitive functions, which would violate DRY pretty hard.

The code:

#include <stdio.h> int fisdigit(int ch) { return ch >= '0' && ch <= '9'; } #define rdi_funcname_sign_1_eof_1(abbrev) rd##abbrev##ieof #define rdi_funcname_sign_1_eof_0(abbrev) rd##abbrev##i #define rdi_funcname_sign_0_eof_1(abbrev) rd##abbrev##ueof #define rdi_funcname_sign_0_eof_0(abbrev) rd##abbrev##u #define wri_funcname_sign_1(abbrev) wr##abbrev##i #define wri_funcname_sign_0(abbrev) wr##abbrev##u #define rwi_argtype_sign_1(type) unsigned type #define rwi_argtype_sign_0(type) signed type #define read_integer(type, abbrev, check_sign, check_eof) \ int \ rdi_funcname_sign_##check_sign##_eof_##check_eof(abbrev) \ (rwi_argtype_sign_##check_sign(type)* n) \ { \ *n = 0; \ int ch; \ int is_neg = 0; \ \ do { \ ch = getchar_unlocked(); \ if(check_eof) { \ if(ch == EOF) \ return 0; \ } \ if(check_sign) { \ if(ch == '-') \ is_neg = 1; \ }\ } while(!fisdigit(ch)); \ \ do { \ *n *= 10; \ *n += ch-'0'; \ ch = getchar_unlocked(); \ } while(fisdigit(ch)); \ if(check_sign) { \ if(is_neg) \ *n *= -1; \ } \ return 1; \ } #define write_integer(type, abbrev, check_sign, max_digits) \ void \ wri_funcname_sign_##check_sign(abbrev) \ (rwi_argtype_sign_##check_sign(type) n) \ { \ size_t const buffsiz = \ (check_sign ? max_digits+1 : max_digits); \ char buff[max_digits]; \ \ size_t i = 0; \ if(check_sign) { \ if(n < 0) \ buff[i++] = '-'; \ } \ while(n != 0) { \ buff[i++] = n%10; \ n /= 10; \ } \ \ if(i == 0) \ putchar_unlocked('0'); \ else \ while(i-- != 0) \ putchar_unlocked(buff[i] + '0'); \ \ return; \ } #define rwi_variations(type, abbrev, max_digits_i, max_digits_u) \ read_integer(type, abbrev, 1, 1) \ read_integer(type, abbrev, 1, 0) \ read_integer(type, abbrev, 0, 1) \ read_integer(type, abbrev, 0, 0) \ write_integer(type, abbrev, 1, max_digits_i) \ write_integer(type, abbrev, 0, max_digits_u) rwi_variations(long long int, ll, 19, 20) rwi_variations(long int, l, 10, 10) rwi_variations(int, , 5, 5) rwi_variations(short int, h, 5, 5) rwi_variations(char, hh, 3, 3) #undef rdi_funcname_sign_1_eof_1 #undef rdi_funcname_sign_0_eof_1 #undef rdi_funcname_sign_1_eof_0 #undef rdi_funcname_sign_0_eof_0 #undef wri_funcname_sign_1 #undef wri_funcname_sign_0 #undef rwi_argtype_sign_1 #undef rwi_argtype_sign_0 #undef rwi_variations #undef read_integer #undef write_integer

Restriction:

Must compile with ANSI C 5.3.0 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE

Use case:

The solution for the aforementioned UVA Problem 10055: "Hashmat the Brave Warrior":

void wrc(char c) { putchar_unlocked(c); } int main() { unsigned long long int a, b; while(rdllueof(&a) && rdllu(&b)) { if(a > b) wrllu(a-b); else wrllu(b-a); wrc('\n'); } return 0; }

I added the wrc function just for consistency with the naming convention of wrllu et al. I think it's better to print everything with wr* rather than print integers with wr* and characters with putchar_unlocked.

PS

Any way to optimize this even more?

Please do not edit after the question has been answered, it invalidates the answer. — pacmaninbw, CommentedJun 13, 2017 at 15:43
See this help page codereview.stackexchange.com/help/someone-answers. — pacmaninbw, CommentedJun 13, 2017 at 21:56
Unclear on write_integer(type, abbrev, 1, max_digits_i) \ write_integer(type, abbrev, 0, max_digits_u). How does the receiving side separate the 2 integers as would they not be textually concatenated? — chux, CommentedJun 15, 2017 at 13:23
@chux Err it is the responsibility of the caller to separate these two integers, for example to don't do wrhhu(5); wrhhu(6); but rather wrhhu(5); wrc(' '); wrhhu(6) Not sure why should it be any other way, C++ iostream facilities work in a similar way wrt this, ideone.com/XwFCnH — gaazkam, CommentedJun 15, 2017 at 13:29

pacmaninbw · Accepted Answer · 2017-06-13 14:45:47Z

3

You worry about violating DRY, but you've violated a C standard, macros should always be all capitals.

While I don't recommend it, the fastest code would be to avoid the use of functions totally and just have the macros. Inline code should always be faster than functions, although on modern computers this is less of an issue.

The fisdigit() function can be a macro or just inline

do { ... } while(ch >= '0' && ch <= '9');

For performance reasons you don't want to call a function.

Check the ctype.h file, isdigit() may be a macro, in older versions of C (pre C89 for sure, possible pre C99 ) all functions provided by ctype.h were macros.

Type Issues
The variables a and b in main are declared as unsigned long long, however the functions are expecting pointers to long long. It's also unclear that long long is required since 2^32 is the max value for either a or b.

answered Jun 13, 2017 at 14:45

pacmaninbw♦

25.7k12 gold badges46 silver badges112 bronze badges

\$\begingroup\$Thank you for your answer! However: (a) It seems that -O2 does optimize and inline function calls godbolt.org/g/Cyp1ej , so there seems to be no difference between macroifying or manually inlining fisdigit and calling fisdigit as a function. (b) If I didn't screw the macro code, rdllu and rdllueof should be expecting ptrs to unsigned long long rather than long long I have a vague feeling that i is permitted to read an integer through a pointer of a different singedness anyway, though I'm not 100% certain.\$\endgroup\$
– gaazkam
CommentedJun 13, 2017 at 15:08
\$\begingroup\$(c) long long is required, this is a peculiarity of this task. The problem is that max value for either a or b is 2^32, while the max value of unsigned long is 2^32-1 , so we'd have an overflow in the corner case.\$\endgroup\$
– gaazkam
CommentedJun 13, 2017 at 15:09
\$\begingroup\$@gaazkam My compiler is giving me warnings about unsigned versus signed in the read functions. My comment about removing functions applied to all of the functions, both read and write.\$\endgroup\$
– pacmaninbw♦
CommentedJun 13, 2017 at 15:13
\$\begingroup\$One final note: The real reason I chose to redefine isdigit: I thought I'd sooner or later expand this "library" to doubles, fixed-point, strings, etc, and that's where locale issues would kick in if I kept using ctype.h functions, and I wanted to avoid this for the sake of simplicity and to avoid any overhead, so I thought for consistency I'd redefine everything in the first place.\$\endgroup\$
– gaazkam
CommentedJun 13, 2017 at 15:16
1
\$\begingroup\$Thank you for noting the need of inlining all rd* and wr* functions. It would seem that to achieve max performance they don't have to be explicitly macroified: instead we can get the same effect if we add the __inline__ keyword: gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/Inline.html And it does seem to be working: godbolt.org/g/586vSx\$\endgroup\$
– gaazkam
CommentedJun 13, 2017 at 15:54

| Show 5 more comments

chux · Accepted Answer · 2017-06-15 04:38:35Z

Bug: Below fails to print digits when n<0

buff[i++] = n%10; ... putchar_unlocked(buff[i] + '0')

if(i == 0) not needed, just use a do {} while

 do { buff[i++] = n%10; } while (n /= 10);

Bug. Wrong array size

size_t const buffsiz = (check_sign ? max_digits+1 : max_digits); \ // char buff[max_digits]; char buff[buffsiz];

Why stingy on buffer size? Could simply use +1 always

size_t const buffsiz = max_digits+1; char buff[buffsiz];

Bug buff[i++] = '-' ... putchar_unlocked(buff[i] + '0'); will not print a '-'.

1) You're right, thank you! 2) Indeed a neater construct, thank you! 3) You're right... I figured it out myself some time before, and even edited the question to remove this bug, but this edit got reverted... 4) Because why not? It's dispatched compile-time, so adds not runtime overhead! 5) Aaand you're right again. Have an upvote, thank you! — gaazkam, CommentedJun 15, 2017 at 9:08

Stack Exchange Network

Efficient integer input / output (with a use case)

The task:

Rationale:

Result:

Approach:

The code:

Restriction:

Use case:

PS

2 Answers 2

Hot Network Questions

Efficient integer input / output (with a use case)

The task:

Rationale:

Result:

Approach:

The code:

Restriction:

Use case:

PS

2 Answers 2

Related

Hot Network Questions