IMHO the problem here is the capabilities of the optimizing compiler, not the language itself. I would argue that it should be the compiler's job to figure these optimizations, otherwise you might as well use inline ASM on compiler intrinsics since it won't be portable anyway.
There are certain features of the C standard that forces the compiler to generate non-optimal code by default in certain cases (like aliasing rules, as any FORTRAN proponent will remind you). I don't think it's the case in TFA.
So basically, blame the optimizer, not the language.
You could argue that it is a fault of the C language that it does not expose the carry flag of the CPU. This makes the most optimal implementation of e.g. addition impossible without resorting to (inline) assembler.
They were the three architectures that immediately sprung to mind when I though of cpus without carry bits. I have only programmed in assembly for two of them -- I might well have read that wiki page before.
Except that exposing too much hardware state to the coder might give less room for the compiler to optimize aggressively for all architectures.
What if the architecture doesn't have a carry? Then the compiler has to generate one when needed.
What if the architecture has better ways to do the addition anyway? What if the architecture is only 8bit and even regular "int" adds take several instructions anyway, so it makes so sense opmimizing for 128bit adds?
C doesn't even mandate what happens in case of an integer overflow, it has no business exposing carry flags.
If I ever write a C tutorial I'll title it "How I learned to stop worrying and love the compiler".
EDIT: of course in this case you can't really "let the compiler handle it" if you care about bignum performances. The only solution here would be
a/ expose much more hardware state to the language, which as I've already stated doesn't sound very convenient or C-ish enough for me,
b/ modify the optimizer to better handle bignum code or
c/ use a bignum library and possibly make it part of the standard.
I wouldn't be opposed to a standard <bignum.h>, I think it would make some sense. In the meantime I just use gmp.h, it's faster than anything I could come up with anyway, asm or otherwise. Bignum is hard.
I agree that the carry flag shouldn't be exposed directly, but the ability to express "add and check for overflow" would be useful and allow for these optimisations where the architecture supports it.
Edit: But if you want to exploit the processor to its fullest, go with assembly. The compiler is good, but proving optimisations is a hard problem, and complex, single-instruction-specific optimisations aren't going to take off any time soon.
> What if the architecture doesn't have a carry? Then the compiler has to generate one when needed.
Adding two N-bit numbers produces N+1-bit result, and C gives you no direct means of accessing the full result. IMO, this is a language defect and has little to do with HW support. [This pertains also to multiplication: NxN bits -> 2N-bit result.]
If the hardware actually returns the full result, excellent; if no, the compiler has to synthesize code to compute it, if needed. Whether it's needed is inferrable by the code that follows, e.g., the type of the variable the result is assigned to.
IMO, inferring that only a partial result is used (e.g., carry is discarded) is much easier for the optimizer than inferring what some instruction sequence is supposed to do. (E.g., 4+ multiplications and few additions => single 32x32=>64 multiply.)
> What if the architecture doesn't have a carry? Then the compiler has to generate one when needed.
What is your point?
If you want to do multiple precision arithmetic in assembly, then on the architectures which don't have a carry, you must indeed generate one, so what?
If a language has some operations with carry, then it is up to the programmer to use them only when he needs them..
> C doesn't even mandate what happens in case of an integer overflow
That's for performance reasons, and I would say that it is the wrong default aka 'premature optimisation', a better language would have 'int' with overflow checks (which could be disabled by a compiler switch) and int_raw for the unsafe&fast behaviour.
Unless you convey information to them, via higher level language constructs or compiler directives, it's not really fair to blame a compiler for making poor or conservative choices. Compilers can only infer or guess at what your intentions are.
The author is banging on about uint128_t for example, and bashing library approaches like boost, but uint128_t isn't even part of the C or C++ standards. Its apples and oranges.
I think the article is pretty meticulous about differentiating between compiler issues (the compiler not recognizing an opportunity to use overflow bits, for example) and C problems (multiplication producing an output the same size as the inputs, which is broken for a large proportion of inputs -- which the writer calls out as an over-generalization).
Few people actually know Fortran anymore, but in reality, C99's restrict covers only a narrow subset of what Fortran's aliasing rules covered. restrict's numerous limitations substantially reduce its usefulness, which is one reason it's not as common knowledge as one might guess.
On some pointers, for example function return types, restrict is defined to be meaningless. Also, restrict pointers can be copies of other pointers, and copies can be made of restrict pointers, subject to certain rules. So it's more involved than just "nothing aliases the pointer".
Here's another example:
// C has pretty paltry array support, so it's common for
// people to build their own stuff like this:
struct Array {
float *data;
size_t len;
};
// But then you use it:
void foo(Array *a, Array *b) {
for (i = ...)
for (j = ...)
a->data[i] = b->data[j];
}
and there's nowhere you can put restrict to declare that the two array references here are independent. The data pointer is one of the contexts where restrict is defined to be meaningless.
If you're a hyperactive squirrel, you might try rewriting all your code everywhere to do stuff like this:
void foo(Array *a, Array *b) {
for (i = ...)
for (j = ...) {
float *restrict x = a->data;
float *restrict y = b->data;
x[i] = y[i];
}
but then you'll just discover that most compilers ignore restrict in block scopes like this, because the semantics for that are tricky for compilers to deal with, so you still won't win.
Yeah, yeah, pointers are evil, memory management is hard, cache locality is a horrible mess, lame, sequential spaghetti code does not automatically scaled by a "stupid" compiler, so we all should use Java and NodeJS VMs which eliminate the necessity to think, and even to have such capacity. With VMs questions of optimal performance just never arise.)
Article poses good questions, although the load time is terrible[1]. Here's the intro while you are waiting for it:
There is one thing which has puzzled me for a while, and
it is the performance of programs written in C when it
comes to big numbers. It may or may not help with the
decades-long ‘C vs Fortran’ performance debate, but let’s
concentrate on one single and reasonably well-defined
thing – big number arithmetic in C and see if it can be
improved.
In fact, there are very few things which gain from being
rewritten in assembler (compared to C), but big number
arithmetic is one of them, with relatively little progress
in this direction over the years. Let’s take a look at
OpenSSL (a library which is among the most concerned about
big number performance: 99% of SSL connections use RSA
these days, and RSA_performance == Big_Number_Performance,
and RSA is notoriously sslloooowww).
...
OpenSSL prefers to use assembler for big number
calculations. It was the case back in 1998, and it is
still the case now (last time I checked, the difference
between C and asm implementations was 2x, but it was long
ago, so things may have easily changed since). But why
should this be the case? Why with all the optimizations
compilers are doing now, should such a common and trivial
thing still need to be written in asm (which has its own
drawbacks – from the need to write it manually for each
and every platform, to sub-optimality of generic asm when
it comes to pipeline optimizations – and hand-rewriting
asm for each new CPU -march/-mtune is not realistic)? If
it can perform in asm but cannot perform in C, it means
that all hardware support is present, but the performance
is lost somewhere in between C developer and generated
binary code; in short – the compiler cannot produce good
code. This article will try to perform some analysis of
this phenomenon.
> But why should this be the case? Why with all the optimizations compilers are doing now, should such a common and trivial thing still need to be written in asm?
Yes, if the CPU vendor keeps coming with all kinds of clowny instructions like MMX/SSE2/SSE4/SSE XP/etc to accelerate things (but really because they need new instructions so the ABI remains patented). Compilers and libraries can't keep with all the new instructions.
The current page is shown because the Blocklayout Template Engine failed to render the page, however this could be due to a problem not in BL itself but in the template. BL has raised or has left uncaught the following exception:
Database Query Error
Description: ErrorNo: 2006, Message:Database error while executing: 'SELECT inst.xar_id as bid,
btypes.xar_type as type,
btypes.xar_module as module,
inst.xar_name as name,
inst.xar_title as title,
inst.xar_content as content,
inst.xar_last_update as last_update,
inst.xar_state as state,
group_inst.xar_position as position,
bgroups.xar_id AS bgid,
bgroups.xar_name AS group_name,
bgroups.xar_template AS group_bl_template,
inst.xar_template AS inst_bl_template,
group_inst.xar_template AS group_inst_bl_template
FROM xar_block_group_instances group_inst
LEFT JOIN xar_block_groups bgroups
ON group_inst.xar_group_id = bgroups.xar_id
LEFT JOIN xar_block_instances inst
ON inst.xar_id = group_inst.xar_instance_id
LEFT JOIN xar_block_types btypes
ON btypes.xar_id = inst.xar_type_id
WHERE bgroups.xar_name = 'header'
AND inst.xar_state > 0
ORDER BY group_inst.xar_position ASC'; error description is: 'MySQL server has gone away'.
Explanation: A database query could not be executed, either because the query could not be understood or because it returned unexpected results.
When hearing a claim such as "there is a substantial gap between the capabilities of hardware and C", my first question is "what hardware"?
Last I checked, C was used on lots of hardware, lots of it which differs substantially from the X86 architecture.
C aims to be portable. For it to be portable its constructs must be so too.
If there exists hardware which doesn't have a carry-flag (like mentioned elsewhere in this thread), exposing it to the C-programmer will result in non-portable code, or a need for (possibly inefficient) compiler-internal workarounds.
Looking at it the other way around, namely upwards the abstraction layer, C has a very limited capability to convey the intent of code. Lots of hardware has the capability to process things in parallel, and C doesn't have any way to exploit that without explicit code to do so.
And as long as C is meant to be portable, that has to be allright.
Carry flag emulation may be "possibly inefficient" on architectures without carry flag, but not exposing carry flag on architectures with carry flag is definitely inefficient. I don't think it is the right tradeoff.
Consider that many architectures on which C can be used lack hardware multipliers. This is totally not an argument against having multiplication in the language.
But I don't need to run my code on that hardware. I need to run my code on a particular subset of hardware. I don't want the programming language that I use the most to tell me that I can't have the features I want because somebody else doesn't have them. "Just because a baby can't chew a steak doesn't mean that a man must drink milk for dinner"
There's a half way point: expose directives that say "I'm going to use this feature, so just refuse to compile if it's not available".
Current CPU's are largely C machines, with a few extensions past C's edges. It was not always so, see eg P-machines, AS/400, Lisp machines, even current GPUs.
37 comments
[ 264 ms ] story [ 1028 ms ] threadThere are certain features of the C standard that forces the compiler to generate non-optimal code by default in certain cases (like aliasing rules, as any FORTRAN proponent will remind you). I don't think it's the case in TFA.
So basically, blame the optimizer, not the language.
P.S.: I used this cached version since the site appears to be down: http://webcache.googleusercontent.com/search?q=cache:accu.or...
Of course not every CPU has a carry flag...
From https://en.wikipedia.org/wiki/Status_register#CPU_architectu... those architectures put the carry result in a general-purpose register, but you still can't access the result in C.
What if the architecture doesn't have a carry? Then the compiler has to generate one when needed.
What if the architecture has better ways to do the addition anyway? What if the architecture is only 8bit and even regular "int" adds take several instructions anyway, so it makes so sense opmimizing for 128bit adds?
C doesn't even mandate what happens in case of an integer overflow, it has no business exposing carry flags.
If I ever write a C tutorial I'll title it "How I learned to stop worrying and love the compiler".
EDIT: of course in this case you can't really "let the compiler handle it" if you care about bignum performances. The only solution here would be
a/ expose much more hardware state to the language, which as I've already stated doesn't sound very convenient or C-ish enough for me,
b/ modify the optimizer to better handle bignum code or
c/ use a bignum library and possibly make it part of the standard.
I wouldn't be opposed to a standard <bignum.h>, I think it would make some sense. In the meantime I just use gmp.h, it's faster than anything I could come up with anyway, asm or otherwise. Bignum is hard.
I agree that the carry flag shouldn't be exposed directly, but the ability to express "add and check for overflow" would be useful and allow for these optimisations where the architecture supports it.
Edit: But if you want to exploit the processor to its fullest, go with assembly. The compiler is good, but proving optimisations is a hard problem, and complex, single-instruction-specific optimisations aren't going to take off any time soon.
Adding two N-bit numbers produces N+1-bit result, and C gives you no direct means of accessing the full result. IMO, this is a language defect and has little to do with HW support. [This pertains also to multiplication: NxN bits -> 2N-bit result.]
If the hardware actually returns the full result, excellent; if no, the compiler has to synthesize code to compute it, if needed. Whether it's needed is inferrable by the code that follows, e.g., the type of the variable the result is assigned to.
IMO, inferring that only a partial result is used (e.g., carry is discarded) is much easier for the optimizer than inferring what some instruction sequence is supposed to do. (E.g., 4+ multiplications and few additions => single 32x32=>64 multiply.)
What is your point? If you want to do multiple precision arithmetic in assembly, then on the architectures which don't have a carry, you must indeed generate one, so what? If a language has some operations with carry, then it is up to the programmer to use them only when he needs them..
> C doesn't even mandate what happens in case of an integer overflow
That's for performance reasons, and I would say that it is the wrong default aka 'premature optimisation', a better language would have 'int' with overflow checks (which could be disabled by a compiler switch) and int_raw for the unsafe&fast behaviour.
The author is banging on about uint128_t for example, and bashing library approaches like boost, but uint128_t isn't even part of the C or C++ standards. Its apples and oranges.
It's such an important addition that I'm bit surprised why it's still not common knowledge.
I have been under the impression that restrict makes it pretty much equivalent to fortran (restrict means that nothing aliases the pointer)
Here's another example:
and there's nowhere you can put restrict to declare that the two array references here are independent. The data pointer is one of the contexts where restrict is defined to be meaningless.If you're a hyperactive squirrel, you might try rewriting all your code everywhere to do stuff like this:
but then you'll just discover that most compilers ignore restrict in block scopes like this, because the semantics for that are tricky for compilers to deal with, so you still won't win.Alternatively, for SPMD-like problems, Intel's open source ISPC[1] compiler is a pretty easy way to benefit from the SIMD hardware in your processor.
[0] http://luajit.org/dynasm.html
[1] http://ispc.github.io/
Yes, if the CPU vendor keeps coming with all kinds of clowny instructions like MMX/SSE2/SSE4/SSE XP/etc to accelerate things (but really because they need new instructions so the ABI remains patented). Compilers and libraries can't keep with all the new instructions.
[1]: https://gmplib.org/list-archives/gmp-devel/2013-August/00335... [2]: http://www.intel.com/content/www/us/en/intelligent-systems/i...
Database Query Error
Description: ErrorNo: 2006, Message:Database error while executing: 'SELECT inst.xar_id as bid, btypes.xar_type as type, btypes.xar_module as module, inst.xar_name as name, inst.xar_title as title, inst.xar_content as content, inst.xar_last_update as last_update, inst.xar_state as state, group_inst.xar_position as position, bgroups.xar_id AS bgid, bgroups.xar_name AS group_name, bgroups.xar_template AS group_bl_template, inst.xar_template AS inst_bl_template, group_inst.xar_template AS group_inst_bl_template FROM xar_block_group_instances group_inst LEFT JOIN xar_block_groups bgroups ON group_inst.xar_group_id = bgroups.xar_id LEFT JOIN xar_block_instances inst ON inst.xar_id = group_inst.xar_instance_id LEFT JOIN xar_block_types btypes ON btypes.xar_id = inst.xar_type_id WHERE bgroups.xar_name = 'header' AND inst.xar_state > 0 ORDER BY group_inst.xar_position ASC'; error description is: 'MySQL server has gone away'.
Explanation: A database query could not be executed, either because the query could not be understood or because it returned unexpected results.
Product: App - Modules
Component: Articles
Last I checked, C was used on lots of hardware, lots of it which differs substantially from the X86 architecture.
C aims to be portable. For it to be portable its constructs must be so too.
If there exists hardware which doesn't have a carry-flag (like mentioned elsewhere in this thread), exposing it to the C-programmer will result in non-portable code, or a need for (possibly inefficient) compiler-internal workarounds.
Looking at it the other way around, namely upwards the abstraction layer, C has a very limited capability to convey the intent of code. Lots of hardware has the capability to process things in parallel, and C doesn't have any way to exploit that without explicit code to do so.
And as long as C is meant to be portable, that has to be allright.
C exposes hardware much more than many other languages.
[1] http://en.wikipedia.org/wiki/Setun
Consider that many architectures on which C can be used lack hardware multipliers. This is totally not an argument against having multiplication in the language.
There's a half way point: expose directives that say "I'm going to use this feature, so just refuse to compile if it's not available".
https://web.archive.org/web/20140208005209/http://accu.org/i...