Tiny Pointers
arxiv.org
Tiny Pointers
1–10 of 38 posts
Re: Tiny Pointers
#2Can someone ELI5?
Re: Tiny Pointers
#3Can someone ELI5?
Most likely related with this post: https://news.ycombinator.com/item?id=43002511
Re: Tiny Pointers
#4Can someone ELI5?
I could be wrong, but I think the easiest way to think of this is to consider how much extra memory programs took when compiled with 64 bit pointers over 32 bit ones. Suddenly every pointer takes double the memory. Which, sure, isn't a huge deal if you don't have a lot of memory allocations. But, if you do, it can add up.
Places it would likely impact more than you'd realize is in higher level language arrays where each item in the array is a pointer. For similar reasons, many datastructures can be coded such that each "pointer" is an array index instead.
So, extending all of that, what if you could make your pointers even smaller than 32 bits? If you know the addressable need for where the pointer is used, there is no reason you can't go smaller.
Re: Tiny Pointers
#5Can someone ELI5?
I could be wrong, but I think the easiest way to think of this is to consider how much extra memory programs took when compiled with 64 bit pointers over 32 bit ones. Suddenly every pointer takes double the memory. Which, sure, isn't a huge deal if you don't have a lot of memory allocations. But, if you do, it can add up. Places it would likely impact more than you'd realize is in higher level language arrays where e…
Yet these aren't offsets from an address, that is, array indexes?
Re: Tiny Pointers
#6Earlier quoted context omitted.
I could be wrong, but I think the easiest way to think of this is to consider how much extra memory programs took when compiled with 64 bit pointers over 32 bit ones. Suddenly every pointer takes double the memory. Which, sure, isn't a huge deal if you don't have a lot of memory allocations. But, if you do, it can add up. Places it would likely impact more than you'd realize is in higher level language arrays where e…
Yet these aren't offsets from an address, that is, array indexes?
But the idea is still the same? You can make "smart pointers" that are attached to arenas or whatever you want to call them. On those, the addressable size of the pointer is confined to how large the arena is.
Re: Tiny Pointers
#7Earlier quoted context omitted.
Yet these aren't offsets from an address, that is, array indexes?
But the idea is still the same? You can make "smart pointers" that are attached to arenas or whatever you want to call them. On those, the addressable size of the pointer is confined to how large the arena is.
Eh, you underestimate my naivety. To rephrase: are these just array indexes, then?
I mean I presume it's something cleverer than just "let's bit-pack our indexes to save space".
..."and make it dynamic" (arenas)
Oh wait, variable-size tiny pointers. Yes. Now it's getting satisfyingly complicated. Maybe like how UTF-8 works?
Re: Tiny Pointers
#8Didn't Python's compact dictionary implementation do this a decade ago?
"The dict type now uses a “compact” representation based on a proposal by Raymond Hettinger which was first implemented by PyPy. The memory usage of the new dict() is between 20% and 25% smaller compared to Python 3.5." -- https://docs.python.org/3.6/whatsnew/3.6.html#whatsnew36-com...
"Note, the sizeof(index) can be as small as a single byte for small dicts, two bytes for bigger dicts and up to sizeof(Py_ssize_t) for huge dict." -- https://mail.python.org/pipermail/python-dev/2012-December/1...
The "tiny pointers" are in the _make_index method in the proof of concept code. -- https://code.activestate.com/recipes/578375-proof-of-concept...
@staticmethod
def _make_index(n):
'New sequence of indices using the smallest possible datatype'
if n dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1)
or DKIX_DUMMY(-2).
Size of indices is dk_size. Type of each index in indices varies with dk_size:
* int8 for dk_size Re: Tiny Pointers
#9Earlier quoted context omitted.
But the idea is still the same? You can make "smart pointers" that are attached to arenas or whatever you want to call them. On those, the addressable size of the pointer is confined to how large the arena is.
Eh, you underestimate my naivety. To rephrase: are these just array indexes, then? I mean I presume it's something cleverer than just "let's bit-pack our indexes to save space". ..."and make it dynamic" (arenas) Oh wait, variable-size tiny pointers. Yes. Now it's getting satisfyingly complicated. Maybe like how UTF-8 works?
[deleted]
Re: Tiny Pointers
#10Earlier quoted context omitted.
But the idea is still the same? You can make "smart pointers" that are attached to arenas or whatever you want to call them. On those, the addressable size of the pointer is confined to how large the arena is.
Eh, you underestimate my naivety. To rephrase: are these just array indexes, then? I mean I presume it's something cleverer than just "let's bit-pack our indexes to save space". ..."and make it dynamic" (arenas) Oh wait, variable-size tiny pointers. Yes. Now it's getting satisfyingly complicated. Maybe like how UTF-8 works?
I mean, in a way, a pointer is just an array index into heap space? Such that, I think this is accurate? I'd drop the "just", though. They can be thought of that way, but the idea is how to keep the programmer from having to do that manually.
To rephrase, this is how to mechanically bit-pack indexes to save space. Doing it in a pointer means you are likely wanting to share these pointers with other parts of the code, so you also need to have them be self contained. Naive way would be for each pointer to be a tuple identifying arena and having its offset. But there is still a lot of effort that has to be done for that to work well. This paper looks at that effort and gives a pass at how worthwhile it is.