Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Weekend projects: getting silly with C

lcamtuf.substack.com

Post reply on HN
Print view View original

111–118 of 118 posts

Re: Weekend projects: getting silly with C

#111

Post by astrange »

eacnamn wrote: post #85
astrange wrote: post #80

Earlier quoted context omitted.

malloc() can't be implemented in C either because it's defined as doing things (creating new memory objects) there are no lower level mechanisms in C to do.

all malloc is defined to do is to return a pointer to storage of appropriate size and alignment, which can easily be done in pure standard C by defining a static array and chopping it up as needed. that's not a brilliant way of doing that, but achievable without leaving standard C

> The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.

> The lifetime of an allocated object extends from the allocation until the deallocation. Each such allocation shall yield a pointer to an object disjoint from any other object.

A static array is "an object" already. A pointer to the middle of it is not a new object.

Re: Weekend projects: getting silly with C

#113

Post by ICameToComment »

drzzhan wrote: post #110

I am so lost at the final block of code. Does every C developer have to deal with this everyday?

Certainly not. That's the purpose of the article where they say in the final sentence that it's entirely possible to write readable, yet totally befuddling code in C that stands a chance in the IOCCC.

Re: Weekend projects: getting silly with C

#114

Post by jstimpfle »

gpderetta wrote: post #107
jstimpfle wrote: post #104

Earlier quoted context omitted.

I think this one better illutrates the point you were making: https://godbolt.org/z/qbfhb6dKo Here I've inserted an increment of the volatile (i.e. a write access) at the start of the loop. If the divisor is 0, in the optimized version with the division hoisted out of the loop, the increment will never actually happen, not even once. Whereas it should in fact happen 1x at the beginning of the first loop iteration wit…

Well, that hoisting is contrary to what uecker says is the standard intent. I think that discussing about omitting branches is a red herring, there is no expectation that the compiler should emit branches or basic blocks that match the source code even in the boring, non-ub case. The only constraint to compiler optimizations is the as-if rule and the as-if rule only requires that side effects and their order be prese…

Thanks for clarifying, I understand much better now.

And I think I can agree that under a strict interpretation of the rule that UB doesn't get reordered with observable behaviour the GCC output in the godbolt is wrong.

Maybe it has something to do with the fact that it's volatiles? I've hardly used volatiles, but as far as I know their semantics have traditionally been somewhat wacky -- poorly understood by programmers and having inconsistent implementations in compilers. I think I've once read that a sequence of volatile accesses can't be reordered, but other memory accesses can very well be reordered around memory accesses. Something like that -- maybe the rules in the compiler are too complicated leading to an optimization like that, which seems erroneous.

But look at this, where I've replaced the volatile access with a printf() call as you describe: https://godbolt.org/z/Ec8aYnc3d . It _does_ get optimized if the division comes before the printf. The compiler seems to be able to do the hoisting (or maybe that can be called "peeling" too?). But not if you swap the two lines such that the printf comes before the division. Maybe the compiler does in fact see that to keep ordering of observable effects, it would have to duplicate both lines, effectively duplicating the entire loop body for a single loop iteration. In any case, it's keeping both the printf() and the div in the loop body.

Re: Weekend projects: getting silly with C

#115

Post by gpderetta »

eacnamn wrote: post #85
astrange wrote: post #80

Earlier quoted context omitted.

malloc() can't be implemented in C either because it's defined as doing things (creating new memory objects) there are no lower level mechanisms in C to do.

all malloc is defined to do is to return a pointer to storage of appropriate size and alignment, which can easily be done in pure standard C by defining a static array and chopping it up as needed. that's not a brilliant way of doing that, but achievable without leaving standard C

AFAIK that can break because of the strict aliasing rules (although it might work in practice). Even if char can alias anything, the reverse is not true and you can't legally store other types in a static array of char type. You should be able to use anonymous memory though, so for example if you get your storeag via mmap or some other allocator it should be fine.

Re: Weekend projects: getting silly with C

#116

Post by gpderetta »

jstimpfle wrote: post #114
gpderetta wrote: post #107

Earlier quoted context omitted.

Well, that hoisting is contrary to what uecker says is the standard intent. I think that discussing about omitting branches is a red herring, there is no expectation that the compiler should emit branches or basic blocks that match the source code even in the boring, non-ub case. The only constraint to compiler optimizations is the as-if rule and the as-if rule only requires that side effects and their order be prese…

Thanks for clarifying, I understand much better now. And I think I can agree that under a strict interpretation of the rule that UB doesn't get reordered with observable behaviour the GCC output in the godbolt is wrong. Maybe it has something to do with the fact that it's volatiles? I've hardly used volatiles, but as far as I know their semantics have traditionally been somewhat wacky -- poorly understood by programm…

I do believe that by a strict reading of the standard GCC is non conforming here. This reading of the standard is not agreed by the GCC developers though: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104800

If the first div happens before the first printf, then it can be CSE out of the loop as any trap would have happened before the printf anyway, so no reordering, and if it didn't trap the first time it wouldn't have trapped later either. In this case CSE is fine and there are no reordering.

If the div happens after printf, then reordering is prohibited not only to preserve side effects before UB (which we have seen GCC doesn't necessarily respects), but because for the most part printf is treated as an opaque function: it could legitimately exit, or longjump out of the function or never return, so on the abstract machine the UB might not happen at all. So it is not safe to hoist trapping instruction like div above opaque functions (but it is safe to sink them).

Still the modification I showed for volatile can be applied as well: peel the first iteration out of the loop so that the first printf can be done before computing the div to be CSEd out of the loop. But GCC doesn't do it although it seems desirable.

Re: Weekend projects: getting silly with C

#117

Post by astrange »

gpderetta wrote: post #115
eacnamn wrote: post #85

Earlier quoted context omitted.

all malloc is defined to do is to return a pointer to storage of appropriate size and alignment, which can easily be done in pure standard C by defining a static array and chopping it up as needed. that's not a brilliant way of doing that, but achievable without leaving standard C

AFAIK that can break because of the strict aliasing rules (although it might work in practice). Even if char can alias anything, the reverse is not true and you can't legally store other types in a static array of char type. You should be able to use anonymous memory though, so for example if you get your storeag via mmap or some other allocator it should be fine.

There isn't anything called mmap in the C standard. That's what I mean by it not being possible to implement in standard C. It is possible in some implementations of C.

Re: Weekend projects: getting silly with C

#118

Post by mgaunard »

tialaramex wrote: post #9
mgaunard wrote: post #2

aren't the switch shenanigans important to the duff's device?

Duff is relying on the fact you're allowed to intermingle the switch block and the loop in K&R C's syntax, the (common at the time but now generally frowned on or even prohibited in new languages) choice to drop-through cases if you don't explicitly break, and the related fact that C lets your loop jump back inside the switch. Duff is trying to optimise MMIO, you wouldn't do anything close to this today even in C, no…

To me the duff's device is just a mechanism to unroll a loop without having to duplicate the code for the trailing case.

While you can't use SIMD you can still benefit from instruction-level parallelism.

It's potentially better in some scenarios where you want to minimize instruction cache usage and there are few iterations of the loop.

Post reply on HN