www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Validity of cast(void*)size_t.max

reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
Is `cast(void*)size_t.max` always an invalid address?

Is so, could it be used to indicate removed/delete elements in 
hash tables with open addressing and a key type being either a 
pointer or class?

And will it work correctly with the GC?
Feb 27 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 2/27/18 9:13 AM, Nordlöw wrote:

 Is `cast(void*)size_t.max` always an invalid address?


You mean, can it point at valid data? Possibly, but likely not. In my 
past as an embedded developer, a lot of times the interrupt vectors are 
stored at the end of address space.



 Is so, could it be used to indicate removed/delete elements in hash 
 tables with open addressing and a key type being either a pointer or class?


Why not use null?

-Steve
Feb 27 2018
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Tuesday, 27 February 2018 at 16:31:51 UTC, Steven 
Schveighoffer wrote:

 Why not use null?

 -Steve


It's already used to indicate that a slot is free. :)
Feb 27 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 2/27/18 11:37 AM, Nordlöw wrote:

 On Tuesday, 27 February 2018 at 16:31:51 UTC, Steven Schveighoffer wrote:

 Why not use null?


 
 It's already used to indicate that a slot is free. :)


cast(void*)1 is likely to be unused.

-Steve
Feb 27 2018
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/27/2018 11:56 AM, Steven Schveighoffer wrote:

 On 2/27/18 11:37 AM, Nordlöw wrote:

 On Tuesday, 27 February 2018 at 16:31:51 UTC, Steven Schveighoffer wrote:

 Why not use null?


 It's already used to indicate that a slot is free. :)


 
 cast(void*)1 is likely to be unused.
 
 -Steve


And to be sure, one can have an actual object that represents nullness 
and use its pointer. (Similar to "the null object pattern".)

Ali
Feb 27 2018
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Tuesday, 27 February 2018 at 20:14:01 UTC, Ali Çehreli wrote:

 And to be sure, one can have an actual object that represents 
 nullness and use its pointer. (Similar to "the null object 
 pattern".)

 Ali


Are there any pros to this pattern compared to just using `null` 
in D?
Feb 28 2018
next sibling parent Kagamin <spam here.lot> writes:
On Wednesday, 28 February 2018 at 19:22:12 UTC, Nordlöw wrote:

 Are there any pros to this pattern compared to just using 
 `null` in D?


When null is already used to mean something else.
Feb 28 2018
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/28/2018 11:22 AM, Nordlöw wrote:

 On Tuesday, 27 February 2018 at 20:14:01 UTC, Ali Çehreli wrote:

 And to be sure, one can have an actual object that represents nullness 
 and use its pointer. (Similar to "the null object pattern".)

 Ali


 
 Are there any pros to this pattern compared to just using `null` in D?


Instead of checking explicitly against null later on, you simply use the 
object and it has no side-effects. I've probably never used it myself 
but it sounds nice if it's applicable. :)

Ali
Feb 28 2018
prev sibling parent reply Kagamin <spam here.lot> writes:
On Tuesday, 27 February 2018 at 19:56:44 UTC, Steven 
Schveighoffer wrote:

 cast(void*)1 is likely to be unused.


And since there was a word about class, cast(Class)cast(void*)1 
won't compile :)
Feb 28 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 2/28/18 3:00 PM, Kagamin wrote:

 On Tuesday, 27 February 2018 at 19:56:44 UTC, Steven Schveighoffer wrote:

 cast(void*)1 is likely to be unused.


 
 And since there was a word about class, cast(Class)cast(void*)1 won't 
 compile :)


Oh, and it has a horrible message! Says you can't cast void * to Class. 
Which you can do, but apparently not if the compiler can tell if it's an 
integer you are casting from.

This does work:

auto x = cast(Object)((cast(size_t *)null) + 1);

I used size_t instead of ubyte, because it will avoid any weird bus 
errors on certain platforms. You'll just get a segfault.

-Steve
Feb 28 2018
next sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 28 February 2018 at 20:07:50 UTC, Steven 
Schveighoffer wrote:

 auto x = cast(Object)((cast(size_t *)null) + 1);


Is this preferred performance-wise over `cast(void*)(size_t.max)`?
Mar 02 2018
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/2/18 3:26 PM, Nordlöw wrote:

 On Wednesday, 28 February 2018 at 20:07:50 UTC, Steven Schveighoffer wrote:

 auto x = cast(Object)((cast(size_t *)null) + 1);


 
 Is this preferred performance-wise over `cast(void*)(size_t.max)`?


No, it just works, as opposed to, um... not working ;)

I think the compiler senses you are trying to do something foolish (even 
though that's not the case), and prevents you from doing it. For some 
reason it doesn't care about it if it starts out as a pointer.

If both worked, or even cast(void *)(size_t.sizeof) worked, then the 
performance would be the same, as you are casting a constant.

What you are looking for is a sentinel to check against. Either works 
OK. As I said before, items in the zero page are not going to be mapped 
by the OS. I'm not sure about size_t.max.

-Steve
Mar 02 2018
prev sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 28 February 2018 at 20:07:50 UTC, Steven 
Schveighoffer wrote:

 auto x = cast(Object)((cast(size_t *)null) + 1);


Thanks, how do I store it as enum or static immutable struct 
member?

In

 trusted pure unittest
{
     class C { int value; }
     C x;
     C y = cast(C)((cast(size_t*)null) + 1); // indicates a lazily 
deleted key
     struct S
     {
         enum C hole1 = cast(C)((cast(size_t*)null) + 1); // TODO 
make work
         static immutable C hole2 = cast(C)((cast(size_t*)null) + 
1); // TODO make work
     }
}

both `enum` and static` immutable` member declarations fail to 
compile with the same errors:

Error: cannot perform pointer arithmetic on non-arrays at compile 
time
Error: cannot perform pointer arithmetic on non-arrays at compile 
time

My only possible solution so far is to return the expression from 
an inline member function which I guess cannot be optimized as 
good as comparing to a compile-time value.
Mar 05 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/5/18 6:41 AM, Nordlöw wrote:

 On Wednesday, 28 February 2018 at 20:07:50 UTC, Steven Schveighoffer wrote:

 auto x = cast(Object)((cast(size_t *)null) + 1);


 
 Thanks, how do I store it as enum or static immutable struct member?
 
 In
 
  trusted pure unittest
 {
      class C { int value; }
      C x;
      C y = cast(C)((cast(size_t*)null) + 1); // indicates a lazily 
 deleted key
      struct S
      {
          enum C hole1 = cast(C)((cast(size_t*)null) + 1); // TODO make
work
          static immutable C hole2 = cast(C)((cast(size_t*)null) + 1);
// 
 TODO make work
      }
 }
 
 both `enum` and static` immutable` member declarations fail to compile 
 with the same errors:
 
 Error: cannot perform pointer arithmetic on non-arrays at compile time
 Error: cannot perform pointer arithmetic on non-arrays at compile time
 
 My only possible solution so far is to return the expression from an 
 inline member function which I guess cannot be optimized as good as 
 comparing to a compile-time value.


Weird, I would have expected to be able to map addresses at compile 
time, I suppose the way you could work it is:

pragma(inline, true)
C lazyDeleted() pure nothrow  trusted { return 
cast(C)((cast(size_t*)null) + 1); }

Then you can simply use this like it was an enum or immutable. It should 
go away in terms of a function call.

-Steve
Mar 05 2018
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 5 March 2018 at 12:41:06 UTC, Steven Schveighoffer 
wrote:

 pragma(inline, true)
 C lazyDeleted() pure nothrow  trusted { return 
 cast(C)((cast(size_t*)null) + 1); }


I still can't evaluate at compile-though...

         enum holeKeyOffset = 0x1;

         pragma(inline, true)
         static K holeKey()  trusted pure nothrow  nogc
         {
             return cast(K)((cast(size_t*)null) + holeKeyOffset);
         }

         enum _ = holeKey;

fails as

     Error: cannot perform pointer arithmetic on non-arrays at 
compile time
Mar 05 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/5/18 9:01 AM, Nordlöw wrote:

 On Monday, 5 March 2018 at 12:41:06 UTC, Steven Schveighoffer wrote:

 pragma(inline, true)
 C lazyDeleted() pure nothrow  trusted { return 
 cast(C)((cast(size_t*)null) + 1); }


 
 I still can't evaluate at compile-though...
 
          enum holeKeyOffset = 0x1;
 
          pragma(inline, true)
          static K holeKey()  trusted pure nothrow  nogc
          {
              return cast(K)((cast(size_t*)null) + holeKeyOffset);
          }
 
          enum _ = holeKey;
 
 fails as
 
      Error: cannot perform pointer arithmetic on non-arrays at compile time


No, I mean you call holeKey at *runtime*. Inlined, it's just returning a 
constant, so it should reduce to a constant.

-Steve
Mar 05 2018
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 5 March 2018 at 16:07:49 UTC, Steven Schveighoffer 
wrote:

 No, I mean you call holeKey at *runtime*. Inlined, it's just 
 returning a constant, so it should reduce to a constant.


A compile-time constant visible to the optimizer?
Mar 05 2018
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Monday, 5 March 2018 at 18:04:20 UTC, Nordlöw wrote:

 On Monday, 5 March 2018 at 16:07:49 UTC, Steven Schveighoffer 
 wrote:

 No, I mean you call holeKey at *runtime*. Inlined, it's just 
 returning a constant, so it should reduce to a constant.


 A compile-time constant visible to the optimizer?


Yes indeed. For gdc and ldc the optimisation is guranteed and I 
am quite dmd can do this as well. As long as you don't have too 
many statements.
Mar 05 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/5/18 1:08 PM, Stefan Koch wrote:

 On Monday, 5 March 2018 at 18:04:20 UTC, Nordlöw wrote:

 On Monday, 5 March 2018 at 16:07:49 UTC, Steven Schveighoffer wrote:

 No, I mean you call holeKey at *runtime*. Inlined, it's just 
 returning a constant, so it should reduce to a constant.


 A compile-time constant visible to the optimizer?


 
 Yes indeed. For gdc and ldc the optimisation is guranteed and I am quite 
 dmd can do this as well. As long as you don't have too many statements.


Note, I think the error is bogus, you should be able to create 
hard-coded addresses of data at compile time -- I'm not sure how you 
would do hardware registers otherwise.

Another possibility I thought of:

struct Dummy
{
     size_t nullValue;
     void *holeKey;
}

enum holeKey = &(cast(Dummy *)null).holeKey;

But this fails as well

Error: dereference of null pointer null

-Steve
Mar 05 2018
parent reply Kagamin <spam here.lot> writes:
On Monday, 5 March 2018 at 18:28:43 UTC, Steven Schveighoffer 
wrote:

 Note, I think the error is bogus, you should be able to create 
 hard-coded addresses of data at compile time -- I'm not sure 
 how you would do hardware registers otherwise.


I'd do them as extern variables, it wouldn't be nice to have them 
as pointers.
extern int reg1;
And use linker option to define address: --defsym reg1=0x1111
Mar 05 2018
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/6/18 1:08 AM, Kagamin wrote:

 On Monday, 5 March 2018 at 18:28:43 UTC, Steven Schveighoffer wrote:

 Note, I think the error is bogus, you should be able to create 
 hard-coded addresses of data at compile time -- I'm not sure how you 
 would do hardware registers otherwise.


 
 I'd do them as extern variables, it wouldn't be nice to have them as 
 pointers.
 extern int reg1;
 And use linker option to define address: --defsym reg1=0x1111


I hadn't thought of that. It's probably a better solution than pointers.

However, I would expect D to have a proper way to do this without 
resorting to linker tricks.

-Steve
Mar 06 2018