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

Storing data in pointers

muxup.com

Post reply on HN
Print view View original

21–30 of 71 posts

Re: Storing data in pointers

#21

Post by none_to_remain »

marcus_holmes wrote: post #13

I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architect…

One good use case is if you are doing atomic operations on pointers, you can atomically modify the tag as well.

Re: Storing data in pointers

#22

Post by drfuchs »

jandrese wrote: post #5

Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.

What’s old is new again: IBM 360 architecture also only used 24 bits for addresses back in the 1960s, so you could stuff data in the upper byte of pointers. Eventually, programs had to declare themselves to be in “Extended Mode” if they wanted to get access to 31-bit addressing instead.

Re: Storing data in pointers

#23

Post by asb »

_a_a_a_ wrote: post #6

The alpha only accessed 8-byte aligned mem addresses (originally anyway). The bottom 3 bits were ignored (masked out) on lookups, per the spec, to allow users to stuff juicy extra info into these.

Do you have a reference on that? This summary of the Alpha AXP https://danluu.com/dick-sites-alpha-axp-architecture.pdf> states "Normal load or store instructions that specify an unaligned address take a precise data alignment trap to PALcode (which may do the access using two aligned accesses or report a fatal error, depending on the operating system design)"

Re: Storing data in pointers

#24

Post by vidarh »

jandrese wrote: post #5

Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.

I'm guessing the problem occurred specifically with CPUs newer than the 68000 irrespective of amount of RAM?

(Microsoft's) Amiga Basic also did this and stopped working on newer CPUs, as the 68000 only has 24 address lines and ignores the top 8 bits of a 32 bit address, but 68020 and up uses all 32 (I don't remember about the 68010, but that was pin compatible with the 68000 so I'm guessing not)

Re: Storing data in pointers

#25

Post by intelVISA »

marcus_holmes wrote: post #13

I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architect…

It is not a Go thing, tagged pointers have been around forever!!

Re: Storing data in pointers

#26

Post by WJW »

CoastalCoder wrote: post #11
rr808 wrote: post #9

My favorite hack back in MFC days was a combo box which I stored the pointer address in the text (to the right after a lot of spaces so was hidden). When a user chooses an item, parse the pointer and de-reference it back to an object.

I predict that some day, you'll be beaten to death by an angry mob of screen-reader users :)

It should be easy to hide from them?

Re: Storing data in pointers

#27

Post by cozzyd »

utopcell wrote: post #16
jandrese wrote: post #5

Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.

Slight correction: 256 TiB, not EiB.

2^20 is perhaps more than slight

Re: Storing data in pointers

#28

Post by wheels »

marcus_holmes wrote: post #13

I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architect…

There are a lot of data structures where doubling the size of the struct would be a big deal. I've worked on big graphs, where I used similar tricks, because most of the storage of a graph is pointers, and limits of what can be quickly computed are bound by how much of the graph you can get in memory.

Re: Storing data in pointers

#29

Post by masklinn »

Dylan16807 wrote: post #15
jandrese wrote: post #5

Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.

x86_64 (among others) specifically avoided that incompatibility, by the CPU forcing programs to mask those bits out instead of ignoring them. So programs are very compatible into the future, they just need to limit the range their memory allocator uses. Then it later added explicit automatic masking, which also avoids the problem. As long as your program can make do with smaller amounts of memory, there are no downsi…

It does not actually make the software future proof: if the kernel returns a large address the software will either fault if it checks, or stomp over then mask out the wrong thing.

Virtual memory is what mitigates the issue, as it lets the OS provide large virtual addresses on a per-process basis, and independent of physical addressing.

This was already used on 32b x86: PAE decorrelated the physical address space from the virtual (giving the OS 36 bits physical address — with a theoretical upper bound of 64 — even as individual processes were still restricted to 32); and on windows the /LARGEADDRESSAWARE link switch allowed manipulating the virtual address space on a per-process granularity.

Re: Storing data in pointers

#30

Post by JonChesterfield »

There's a trick here I hadn't noticed. Good times.

If the plan is 8 byte aligned data and use the three low bits for other stuff, you mask them off before loads/stores. An alternative is to use the high three bits, store the pointer/8, and multiply by 8 to retrieve.

That's appealing on x64 because memory operations can include a *8 in the encoding.

Specifically, I've long wondered whether the pointer masking tricks mess up prefetch/speculation. It seems plausible that making the dereference look more like a normal memory operation is helpful for that.

(It also means the low-alignment-bits and high-unused-bits can be considered contiguous modulo the *8 on decode which is probably less annoying when using both ranges)

Post reply on HN