News for hackers. Stuff that matters.
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.