News for hackers. Stuff that matters.
Re:You Can't Always Hash Pointers in C by adrianratnapala on Tuesday May 31, 2016 @04:53AM (#11805481)
Or rather I wish the standard did not bend over backwards to allow every kind of aggressive optimisation that some compiler writer claims will increase speed of unoptimized code by 0.5%.
Re:You Can't Always Hash Pointers in C by qb45 on Tuesday May 31, 2016 @06:00AM (#11805663)
This one is about portability, not optimizations. There are architectures where pointer isn't a simple int, due to things like segmentation, tagging or even possibly something as stupid as lack of sufficiently wide integer type.

Heck, there were even C implementations for 36-bit machines, which had 36-bit registers and could only load/store 36-bit-sized and 36-bit-aligned chunks of memory. They packed 4 chars into such word (leaving 4 bits unused) and I don't know how they implemented char* but it must have been something totally mad and not reasonably castable to int or even int*.

Re:You Can't Always Hash Pointers in C by drfuchs on Tuesday May 31, 2016 @12:12PM (#11807386)
DEC's 36-bit PDP-10 and -20 had hardware support for pointers-to-byte: A pointer had lower 18 bits for the (word) address, while the upper 18 bits had room for the bit-offset within the addressed word, and the bit-length of the "byte" being used. So, if you were using 8-bit characters, a pointer to the beginning of a string would roughly look like (0,8,addr). A special "load and increment" instruction would fetch that first character being pointed to, and increment the pointer to (8,8,addr). So, c=*ptr++ in one instruction! After the fourth fetch, the hardware would know to increment from (24,8,addr) to (0,8,addr+1). And, best of all, if you were using plain old ASCII (and assembly rather than C), as was common in the day, you'd use 7-bit chars, packing 5 into each 36-bit word. Or six 6-bit chars if you were only using upper case, as in file names.

So, casting one of these pointers to int the most natural way (leaving the bits alone) would not give you an easily subtractable representation.

Re:You Can't Always Hash Pointers in C by pklausler on Tuesday May 31, 2016 @12:59PM (#11807817)
I don't know how any 36-bit machine implemented C's char pointers, and I can imagine all kinds of other grief stemming from the ones'-complement arithmetic on the 36-bitters with which I'm familiar, but I can tell you how we implemented char pointers on the 64-bit word-addressable Cray-1, -2, and their descendants. The 3-bit byte offset (big-endian, arbitrarily) of a linear byte address was kept in the most significant bits of a 64-bit word, and the 24-bit or 32-bit regular word address was in the least-significant bits. To do pointer arithmetic, code would have to do circular shifts (more accurately, a shift with fill from the same register) to get a linear address and to put it back into the canonical form that I described.

I don't recall whether a cast to int was raw or converted to linear.

Re:You Can't Always Hash Pointers in C by userbinator on Tuesday May 31, 2016 @07:05AM (#11805837)
but it must have been something totally mad and not reasonably castable to int or even int.*

As long as you can impose an ordering on the elements in memory and thus derive a number for each one, it's possible to define the straightforward representation of a pointer. 4 chars per word is an easy case since you can just let char* be a number with the lowest 2 bits indicating the index within a single word, and the rest of the bits are the word-address. int* can be the same number with the lowest 2 bits always 0. If word addresses are smaller than 36 bits, then values with the higher bits set are invalid, and if they're larger, then use multiple words to hold them.

Working with chars on such a machine is going to involve a lot of shifting and otherwise data movement, but there you go, a way to implement C pointers on such a machine.

Re:You Can't Always Hash Pointers in C by qb45 on Tuesday May 31, 2016 @07:33AM (#11805922)
> int* can be the same number with the lowest 2 bits always 0.

And now you have to right-shift int pointers on every dereference for some dubious benefit. It's easier and more efficient to make pointer arithmetic and casting painful.

Re:You Can't Always Hash Pointers in C by adrianratnapala on Friday June 03, 2016 @05:52PM (#11833550)
No, you left-shift them on every cast.

And is someone type-puns using a union, they get a thing four times samller than they might have expected. Stil it is totally well behaved in a hash.

Re:You Can't Always Hash Pointers in C by thomasahle on Tuesday May 31, 2016 @05:27AM (#11805580)
Isn't that the point of C/C++? "Code should run as fast as the hardware allows" and "We allow you to do crazy things that probably won't be portable, if that's what you want".

I wonder, if somebody created a language with C like semantics, like pointer arithmetic, but with a layer in between to ensure consistency and portability.. Would people want to use that, or would the semantics be considered less interesting, when they don't map directly to hardware?

Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @05:42AM (#11805615)
Corresponding directly to the hardware makes sense, sure. But what modern GCC (especially) does goes far beyond that. The intent of signed integer overflow being undefined is that it will be twos complement on a twos complement machine, not that I want half my code to not run if I had an overflow somewhere.
Re:You Can't Always Hash Pointers in C by caf on Tuesday May 31, 2016 @07:10AM (#11805849)
If that had been the intent, it would have been specified as implementation-defined, not undefined.

More likely, the intent was to also accomodate implementations that trapped on overflow.

Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @10:06AM (#11806557)
Implementation-defined includes trapping on overflow.
Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @10:12AM (#11806590)
"Evaluates to an implementation-defined value" would not include that. I'm not sure if any of the usual definitions in the standard includes trapping and doesn't include arbitrary behaviour.
Re:You Can't Always Hash Pointers in C by caf on Tuesday May 31, 2016 @08:09PM (#11811263)
Well, there's kind of one place: when a value is converted to a signed type and it's out of range for that type, the standard says "either the result is implementation-defined or an implementation-defined signal is raised."

However, integer overflow within an expression is trickier than this to define, because you want to preserve the compiler's ability to reorder sub-expressions that are mathematically equivalent when there's no overflow, without forcing the compiler to prove that there won't be overflow. The same is true of CSE and hoisting expressions out of loops.

For example, if you have a machine that traps on overflow and thus under this hypothetical standard your implementation defined signed overflow to trap, you can't simplify (a + 2 - 1) to (a + 1) because the second might trap when the second does not, and your implementation has said that the trap will happen. It also means that you can't hoist an expression out of a loop if that expression might overflow, because the trap has to happen at the point where it would happen on the C virtual machine, not later after other side-effects have become visible.

This is why trapping implementations imply "undefined behaviour" - it's because defining to trap severely restricts the compiler's freedom under the as-if rule to reorder and simplify expressions.

Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @10:57AM (#11806865)
Sure, but the standard need not say "Evaluates to an implementation-defined value". There are other wordings which use "implementation-defined" and would support trapping on overflow.
Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @11:43AM (#11807204)
Can you give an example? I struggle to think of anywhere the standard uses a wording that would fit here.
Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @12:02PM (#11807327)
Why would it have to be wording already in the standard? Does each phrasing in the standard have to appear more than once?
Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @12:33PM (#11807549)
Adding a new phrase with a new meaning would add a substantial amount of complexity to what's already a very complex standard.
Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @12:51PM (#11807737)
I disagree. There's nothing difficult to understand about new phrases with new meanings in general.

Do you have a specific phrase which you can show to be sufficiently difficult to understand by a group of people, and which you don't think could be rewritten to retain the same meaning but be easier to understand?

If you do, let me know, and I will try to simplify it for you and help you understand it.

If you don't, then there isn't much to say. Your current argument ("phrases could be written in a difficult to understand way") is too general to be useful.

Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @05:26PM (#11810400)
I suppose it's less the phrase itself than the concept. What would be a way to say "integer overflow behaviour may reflect the underlying machine, but must be sensible", rigorously enough for the C standard? We've established that "undefined behaviour" is too broad, and "implementation-defined value" is too narrow.
Re:You Can't Always Hash Pointers in C by jjnoakes on Wednesday June 01, 2016 @02:39PM (#11817007)
Why "must be sensible"? Why not just say "signed integer overflow is implementation-defined" and in a footnote say "for example, it may wrap, trap, saturate, or do anything else documented by your implementation"?

I'm not seeing the big deal here.

Re:You Can't Always Hash Pointers in C by lmm on Wednesday June 08, 2016 @05:07AM (#11860944)
> Why "must be sensible"? Why not just say "signed integer overflow is implementation-defined" and in a footnote say "for example, it may wrap, trap, saturate, or do anything else documented by your implementation"?

I don't think that actually defines anything - I don't think GCC would interpret that as anything other than undefined behaviour.

Re:You Can't Always Hash Pointers in C by Sacho on Tuesday May 31, 2016 @07:04AM (#11805832)
If that was the intent, then overflow should have been classified as enumerated implementation-defined behavior, just like the bit representation of an integer type which already deals with those variations.