short pointers (32 bit) in 64 bit apps

short pointers (32 bit) in 64 bit apps

[Reza Roboubi]

Is there support for "short" pointers in 64 bit applications?  As struct 
members, these short pointers would save space, but when accessed, they 
would automatically be treated as 64 bit pointers into the "current" 4GB 
space (namely where the containing struct resides.)

Thanks a lot.

Reza.

Re: short pointers (32 bit) in 64 bit apps

[Ian Lance Taylor]

Reza Roboubi <reza@parvan.net> writes:

> Is there support for "short" pointers in 64 bit applications?  As
> struct members, these short pointers would save space, but when
> accessed, they would automatically be treated as 64 bit pointers into
> the "current" 4GB space (namely where the containing struct resides.)

No.

Sorry.

Ian

Re: short pointers (32 bit) in 64 bit apps

[Reza Roboubi]

Ian Lance Taylor wrote:
> Reza Roboubi <reza@parvan.net> writes:
> 
>> Is there support for "short" pointers in 64 bit applications?  As
>> struct members, these short pointers would save space, but when
>> accessed, they would automatically be treated as 64 bit pointers into
>> the "current" 4GB space (namely where the containing struct resides.)
> 
> No.
> 
> Sorry.
> 
> Ian

Do you know what it takes to do it?  How much work for a newcomer to get 
up to speed with gcc?  (Maybe this should go to the developer list?)

Thanks a lot.

Reza.

Re: short pointers (32 bit) in 64 bit apps

[Ian Lance Taylor]

Reza Roboubi <reza@parvan.net> writes:

> Ian Lance Taylor wrote:
>> Reza Roboubi <reza@parvan.net> writes:
>>
>>> Is there support for "short" pointers in 64 bit applications?  As
>>> struct members, these short pointers would save space, but when
>>> accessed, they would automatically be treated as 64 bit pointers into
>>> the "current" 4GB space (namely where the containing struct resides.)
>>
>> No.
>>
>> Sorry.
>>
>> Ian
>
> Do you know what it takes to do it?  How much work for a newcomer to
> get up to speed with gcc?  (Maybe this should go to the developer
> list?)

At first glance the proposed optimization seems clearly unsafe.  There
is nothing which limits a pointer to pointing into any particular 4GB
space.

If you want to limit this to struct members, you would essentially
want to rewrite struct fields with pointer type to have some different
type instead.  You would need to automatically convert values on load
and store.  It seems doable to me.  You would probably want to change
the handling of fields in stor-layout.c and change the way that
COMPONENT_REF trees are geneated.

gcc is a complex program, and some newcomers do have difficulty
understanding it.

Ian

Re: short pointers (32 bit) in 64 bit apps

[Nicholas Sherlock]

On 19/05/2010 3:58 p.m., Reza Roboubi wrote:
> Do you know what it takes to do it? How much work for a newcomer to get
> up to speed with gcc? (Maybe this should go to the developer list?)

You would need to write a memory allocator which divides the address 
space into 4GB (32-bit pages). Then you could create a new malloc 
routine which has an extra argument to allow you to allocate memory from 
within a specified 4GB page. That way you can make all of your 
allocations for a given data structure lie within the same region.

Then you can add the top 32-bits to pointer addresses within your data 
structure before you attempt to dereference them.

Cheers,
Nicholas Sherlock

Re: short pointers (32 bit) in 64 bit apps

[Reza Roboubi]

Nicholas Sherlock wrote:
> On 19/05/2010 3:58 p.m., Reza Roboubi wrote:
>> Do you know what it takes to do it? How much work for a newcomer to get
>> up to speed with gcc? (Maybe this should go to the developer list?)
> 
> You would need to write a memory allocator which divides the address 
> space into 4GB (32-bit pages). Then you could create a new malloc 
> routine which has an extra argument to allow you to allocate memory from 
> within a specified 4GB page. That way you can make all of your 
> allocations for a given data structure lie within the same region.

Since we are trying to _compress_ these structs in the first place 
malloc'ing them individually is pointless anyway.  We should probably 
have some sort of custom (fixed size) allocator.

<SIDE-NOTE>
Quote from git source code: "The standard malloc/free wastes too much 
space for objects, [...]"
</SIDE-NOTE>

Really, this whole thing is for people who care about scaling something 
specific and don't mind doing sbrk and mmap when they need to.  So the 
main change is a C language extension (nothing glibc/library related.)

Essentially, you would want a pointer type modifier:

struct list {
   struct list short * next;
};

> 
> Then you can add the top 32-bits to pointer addresses within your data 
> structure before you attempt to dereference them.

That's the point:  not having to do this manually.

Thanks for the reply.

Reza.

> 
> Cheers,
> Nicholas Sherlock
> 

Re: short pointers (32 bit) in 64 bit apps

[Nicholas Sherlock]

On 19/05/2010 8:54 p.m., Reza Roboubi wrote:
> Nicholas Sherlock wrote:
>> On 19/05/2010 3:58 p.m., Reza Roboubi wrote:
>>> Do you know what it takes to do it? How much work for a newcomer to get
>>> up to speed with gcc? (Maybe this should go to the developer list?)
>>
>> You would need to write a memory allocator which divides the address
>> space into 4GB (32-bit pages). Then you could create a new malloc
>> routine which has an extra argument to allow you to allocate memory
>> from within a specified 4GB page. That way you can make all of your
>> allocations for a given data structure lie within the same region.
>
> Since we are trying to _compress_ these structs in the first place
> malloc'ing them individually is pointless anyway. We should probably
> have some sort of custom (fixed size) allocator.

If the pointers only have to refer to memory within the same memory 
allocation, and that allocation is smaller than 4GB, that's a 
significantly more restricted problem. You wouldn't need a custom memory 
allocator, you could just store the difference between the pointer 
target and the pointer's location instead of an absolute pointer. That 
sounds doable.

Cheers,
Nicholas Sherlock

Re: short pointers (32 bit) in 64 bit apps

[Reza Roboubi]

Nicholas Sherlock wrote:
> On 19/05/2010 8:54 p.m., Reza Roboubi wrote:
>> Nicholas Sherlock wrote:
>>> On 19/05/2010 3:58 p.m., Reza Roboubi wrote:
>>>> Do you know what it takes to do it? How much work for a newcomer to get
>>>> up to speed with gcc? (Maybe this should go to the developer list?)
>>>
>>> You would need to write a memory allocator which divides the address
>>> space into 4GB (32-bit pages). Then you could create a new malloc
>>> routine which has an extra argument to allow you to allocate memory
>>> from within a specified 4GB page. That way you can make all of your
>>> allocations for a given data structure lie within the same region.
>>
>> Since we are trying to _compress_ these structs in the first place
>> malloc'ing them individually is pointless anyway. We should probably
>> have some sort of custom (fixed size) allocator.
> 
> If the pointers only have to refer to memory within the same memory 
> allocation, and that allocation is smaller than 4GB, that's a 
> significantly more restricted problem. You wouldn't need a custom memory 
> allocator, you could just store the difference between the pointer 
> target and the pointer's location instead of an absolute pointer. That 
> sounds doable.

And that gets your ALU's doing a lot of unneeded additions and 
subtractions, every time you access such pointers.

Reza.

Re: short pointers (32 bit) in 64 bit apps

[Clemens Eisserer]

Hi,

> Is there support for "short" pointers in 64 bit applications?  As struct members, these short pointers would save space, but when accessed, they would
> automatically be treated as 64 bit pointers into the "current" 4GB space (namely where the containing struct resides.)

Sun's JVM is able to do this, they even have two different cases for
<= 4GB heaps and <= 32GB heaps, and at least for "typical" java
applications the speedup is in the range of 10-25%,

- Clemens

Re: short pointers (32 bit) in 64 bit apps

[phi benard]

On a 64bits system, how an ILP64 (or LP64) compiled application can be
sure that returned addr from the operating system can be squeezed?

Are you assuming a flat virtual address space for a given process, and
al your memory request (sbrk/malloc/mmap) will fit into 4Gb fir a
while before exceeding this limit? because if so, I think it is a
wrong start many architecture out there are segmented, i.e there are
some bits in the MSB of a pointer that define what so called
space/region/segment name-it, so on some architecture doing an mmap()
can return various kind of address like 0x100012345678 for data
segment 0x200012345678 for a shared memory segment etc..., squeezing
from 64 bits to 32 bits mean keeping the MSB, since from architecture
to architecture this number of bits vary the remaining bits for
'offset' must be assumed not to be bigger than the smallest possible
offset, for instance there are archi with 2 bits space registers
index, and architecture with 3 bits space register, so assuming the
biggest (3 bits), this mean that the offset part of  a pointer can be
no bigger that 32-3 29bits. So since this is unknown from start, it is
unsafe to assume that any program can be coded with shortened pointer
and think they willl be portable, it could be only a special case for
a given flat architecture.

On such segmented architecture, even an mmap() with MAP_SHARED32 in an
LP64 process return and addr with segment bit setup, so a 32bit app
and a 64 bit app on this OS can share the same area in memory, the
size of the shared memory segment is then by nature smaller than 4Gb,
it is generally up to the offset size 2^(32-2) or 2^(32-3) etc...

In short, this idea is a false good idea I guess :)

Furthermore, memory is ship nowaday, and the backing store even
cheaper. Who would take the risk to implement something in the
compiler that is by nature non portable and would requier much more
than just 'short' as a keyword but would require a short pointer to be
a struct of 2 member some bits for teh segment selection, and the rest
for offset selection, and possibly way to setup region register (that
many os don't allow) etc....

I guess you better stay away from this, are code indeed the
compress/decompress of your data structure as needed.

Cheers,
Phi

Re: short pointers (32 bit) in 64 bit apps

[Clemens Eisserer]

Hi Phi,

> On a 64bits system, how an ILP64 (or LP64) compiled application can be
> sure that returned addr from the operating system can be squeezed?

In java you can limit the amount of RAM which may be allocated for a
single JVM instance, and allocations are aligned on 2-word boundries.
Yes, they have to do a bit of encoding/decoding but for typical java
applications speedups of 5-25% are not uncommon,

- Clemens

Re: short pointers (32 bit) in 64 bit apps

[Ian Lance Taylor]

Reza Roboubi <reza@parvan.net> writes:

> And that gets your ALU's doing a lot of unneeded additions and
> subtractions, every time you access such pointers.

I don't see how you can possibly avoid ALU operations given your
design goals (i.e., permitting the pointers to exist in memory areas
other than the low 4GB).  You are just asking for a way to make the
compiler generate them automatically.

Heck, even if you don't like C++, you can do it yourself with macros.

struct s
{
  uint32_t ps; /* Pseudo-pointer to next struct in list.  */
  ...
};

#define GET_SPS(p) \
  ((struct s *) ((p)->ps | ((uintptr_t) (p) & 0xffffffff00000000ULL)))
#ifdef NDEBUG
#define SET_SPS(p, q) \
  ((p)->ps = (uint32_t) ((uintptr_t) q & 0xffffffff))
#else
#define SET_SPS(p, q) \
  (assert (((uintptr_t) (p) & 0xffffffff00000000ULL)
           == (uintptr_t) (q) & 0xffffffff00000000ULL),
   (p)->ps = (uint32_t) ((uintptr_t) (q) & 0xffffffff))
#endif

For extra credit use statement expressions to avoid multiple
evaluation of the macro arguments.

Ian

Re: short pointers (32 bit) in 64 bit apps

[Nicholas Sherlock]

On 20/05/2010 3:06 p.m., Ian Lance Taylor wrote:
> I don't see how you can possibly avoid ALU operations given your
> design goals (i.e., permitting the pointers to exist in memory areas
> other than the low 4GB).  You are just asking for a way to make the
> compiler generate them automatically.
>
> Heck, even if you don't like C++, you can do it yourself with macros.

Here's the relative-pointer idea expressed as macros, too:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef uint32_t relptr;

struct s {
   relptr p;
   int elem;
};

#define GET_RELPTR(p) \
   ((void*) ((p) + (uintptr_t) &(p)))

#define SET_RELPTR(p, q) \
   (p) = (relptr) ((char*) (q) - (char*) &(p))


int main(void) {

   struct s arr[100];

   arr[0].elem=143;
   arr[99].elem=42;

   SET_RELPTR(arr[0].p, &arr[99]);
   SET_RELPTR(arr[99].p, &arr[0]);

   printf("%d\n", ((struct s *) GET_RELPTR(arr[0].p))->elem);
   printf("%d\n", ((struct s *) GET_RELPTR(arr[99].p))->elem);

   return 0;
}

A relptr can point to anywhere else within the same object the pointer 
is stored in, so long as the object is smaller than 4GB.

Cheers,
Nicholas Sherlock

Re: short pointers (32 bit) in 64 bit apps

[Andrew Haley]

On 05/19/2010 09:54 AM, Reza Roboubi wrote:
> Nicholas Sherlock wrote:
>> On 19/05/2010 3:58 p.m., Reza Roboubi wrote:
>>> Do you know what it takes to do it? How much work for a newcomer to get
>>> up to speed with gcc? (Maybe this should go to the developer list?)
>>
>> You would need to write a memory allocator which divides the address
>> space into 4GB (32-bit pages). Then you could create a new malloc
>> routine which has an extra argument to allow you to allocate memory
>> from within a specified 4GB page. That way you can make all of your
>> allocations for a given data structure lie within the same region.
> 
> Since we are trying to _compress_ these structs in the first place
> malloc'ing them individually is pointless anyway.  We should probably
> have some sort of custom (fixed size) allocator.
> 
> <SIDE-NOTE>
> Quote from git source code: "The standard malloc/free wastes too much
> space for objects, [...]"
> </SIDE-NOTE>
> 
> Really, this whole thing is for people who care about scaling something
> specific and don't mind doing sbrk and mmap when they need to.  So the
> main change is a C language extension (nothing glibc/library related.)
> 
> Essentially, you would want a pointer type modifier:
> 
> struct list {
>   struct list short * next;
> };
> 
>>
>> Then you can add the top 32-bits to pointer addresses within your data
>> structure before you attempt to dereference them.
> 
> That's the point:  not having to do this manually.

I don't see the point of changing the language.  Define a custom allocator
and store the pointers in uint32_t variables.  C++ makes this very easy:
see below.

Andrew.





#include <cstdint>
#include <cstdio>

template<class T> class shortptr
{
  uint32_t the_ptr;

public:

  T& operator*()
  {
    return *(T*)the_ptr;
  }

  shortptr(T *p)
  {
    the_ptr = (uint32_t)(uintptr_t)p;
  }
};

int foo (shortptr<int> p)
{
  return *p;
}

int a = 99;

int
main ()
{
  shortptr<int> p = &a;

  int m = foo (p);
  printf ("%d %d\n", m, sizeof p);
}

Re: short pointers (32 bit) in 64 bit apps

[Reza Roboubi]

Andrew Haley wrote:
>> Essentially, you would want a pointer type modifier:
>>
>> struct list {
>>   struct list short * next;
>> };
>>
>>> Then you can add the top 32-bits to pointer addresses within your data
>>> structure before you attempt to dereference them.
>> That's the point:  not having to do this manually.
> 
> I don't see the point of changing the language.  Define a custom allocator
> and store the pointers in uint32_t variables.  C++ makes this very easy:
> see below.
> 
> Andrew.
> 
> #include <cstdint>
> #include <cstdio>
> 
> template<class T> class shortptr
> {
 > [...]

---------------------------------------
Two more quotes from Linus Torvalds:
"C++ leads to really really bad design choices [...]"
"the whole C++ exception handling thing is fundamentally broken. It's
    _especially_ broken for kernels"
---------------------------------------

Trust me, doing this in the compiler is a _much_ more sane, easy to 
implement, and clean solution.  As Ian Taylor said, you just need some 
tweaking of loads and stores.  That, and the "short" language keyword.
(The problem is that gcc is huge and complex for getting started.)

If you use C++ templates, it can get crazy very quickly:  imagine trying 
to reference this template based object (using a void short **) (for 
passing to a generic function like memcpy.)  Now suddenly, you must 
write another template to represent that (assuming C++ even allows that, 
and the g++ implementation of "void **" or "char **" templates is bug 
free.)  You must then make your generic function("memcpy") aware of 
these types, which wasn't part of the original design plan (it's really 
crazy!)  Then, you'll have to write type converters (say what!) to go 
back and forth between all these templates.

It's an awful mess!  The more you try to "fix" it, the more you realize 
it's broken.  The reason is that this "type-first-logic-second" 
mentality of C++ is just WRONG at a fundamental level, and that cannot 
be fixed.

C++ _might_ be useful for something like KDE, but then again GUI people 
don't need things like "short pointers" in the first place.

Reza.

Re: short pointers (32 bit) in 64 bit apps

[John S. Fine]

Reza Roboubi wrote:
> Trust me, doing this in the compiler is a _much_ more sane, easy to 
> implement, and clean solution.
Trust me instead.  Using C++ and a templated type for the short pointer 
is easy.  Modifying the compiler is hard.   They aren't anywhere close 
to a scale where you might reach the opposite conclusion.

If this were a common requirement (both to save that space despite the 
complications and restrictions, and to do so for programs written in C, 
not C++) then there might be a case to do a difficult project in the 
compiler instead of many people doing simpler projects in their own 
code.  But I doubt you will convince any experienced GCC maintainer that 
this will be a common requirement.
> If you use C++ templates, it can get crazy very quickly:  imagine 
> trying to reference this template based object (using a void short **) 
> (for passing to a generic function like memcpy.)
The template would obviously have a conversion operator to the correct 
type of ordinary pointer, which you might further cast to void* if you 
wanted to use it with memcpy etc.  But I can't think of any reason you 
might want anything like void short** to ever exist.

> It's an awful mess!  The more you try to "fix" it, the more you 
> realize it's broken.  The reason is that this 
> "type-first-logic-second" mentality of C++ is just WRONG at a 
> fundamental level, and that cannot be fixed.
I won't try further to fix your bias against C++, I assume that wouldn't 
be possible.