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

Baby's First Garbage Collector

journal.stuffwithstuff.com

Post reply on HN
Print view View original

51–60 of 90 posts

Re: Baby's First Garbage Collector

#51

Post by dllthomas »

_delirium wrote: post #39
dllthomas wrote: post #34

Earlier quoted context omitted.

Of course, you can make something look like not a pointer and then make it a pointer again if you actually change the zeros and ones.

Most languages don't give you any guarantees if you do that, though. In C, for example, pointer arithmetic on a void*, or on a pointer cast to an integer, is not guaranteed to produce sensible results. The standard only provides guarantees for pointer arithmetic if it's performed on a non-void pointer that points within an array, and the results remain within the bounds of the same array (arithmetic that produces a p…

In ordinary C, without a garbage collector, I'd be baffled to find an implementation where one could not:

    1) Cast a pointer to an integer of sufficient size.
    2) Xor that integer with another value.
    3) Xor the result with the same value.
    4) Cast back to a pointer.
    5) Dereference.
It's sufficiently corner-case that I am not certain what the standard says about it. In any event, pointers matter when coding in assembly, where language standards aren't even relevant.

Re: Baby's First Garbage Collector

#52

Post by kevingadd »

bunderbunder wrote: post #42
phamilton wrote: post #3

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

C# has pointer goodness, in that you can do pointer arithmetic and bypass type safety. However, you have to declare an 'unsafe' context in which you'll do it. Unsafe contexts are tied to a local scope, which means that you can't do anything like having classes with fields of pointer types. Pointers don't outlive the function in which you use them. Also, before you can get a pointer to an object you have to "pin" it,…

You can't store a raw pointer, but you can store the 'safe' forms of pointers (IntPtr, etc) which allows you to do some of the stuff you'd want to do - allocate a buffer of given size in unmanaged heap, then manipulate it entirely using struct pointers and pointer arithmetic. The key/value store I wrote in C# does this - no data lives in the managed heap, it's all sitting in unmanaged memory (mapped files, as it happens).

Re: Baby's First Garbage Collector

#53

Post by kevingadd »

MichaelGG wrote: post #46
bunderbunder wrote: post #42

Earlier quoted context omitted.

C# has pointer goodness, in that you can do pointer arithmetic and bypass type safety. However, you have to declare an 'unsafe' context in which you'll do it. Unsafe contexts are tied to a local scope, which means that you can't do anything like having classes with fields of pointer types. Pointers don't outlive the function in which you use them. Also, before you can get a pointer to an object you have to "pin" it,…

C# can also use managed pointers (type& instead of type*). All out/ref parameters use this type of pointer, and it'll get updated by the runtime, like an object reference - no pinning necessary.

Interesting, can you link to an example of their use? I've never seen them in the documentation or examples, but I remember that Managed C++ and C++/CLI have something similar.

Or are you just saying that you can 'use' them via out/ref? I interpreted your post to mean that you can store them in fields, which would be stellar but seems like it would break reference lifetime guarantees.

Re: Baby's First Garbage Collector

#54

Post by MaulingMonkey »

kevingadd wrote: post #52
bunderbunder wrote: post #42

Earlier quoted context omitted.

C# has pointer goodness, in that you can do pointer arithmetic and bypass type safety. However, you have to declare an 'unsafe' context in which you'll do it. Unsafe contexts are tied to a local scope, which means that you can't do anything like having classes with fields of pointer types. Pointers don't outlive the function in which you use them. Also, before you can get a pointer to an object you have to "pin" it,…

You can't store a raw pointer, but you can store the 'safe' forms of pointers (IntPtr, etc) which allows you to do some of the stuff you'd want to do - allocate a buffer of given size in unmanaged heap, then manipulate it entirely using struct pointers and pointer arithmetic. The key/value store I wrote in C# does this - no data lives in the managed heap, it's all sitting in unmanaged memory (mapped files, as it happ…

> You can't store a raw pointer

You can if you mark the containing class/struct "unsafe", which allows both type safety and increased ease of use.

Re: Baby's First Garbage Collector

#55

Post by pcwalton »

samth wrote: post #41
pcwalton wrote: post #35

Earlier quoted context omitted.

Depends. Do you want, for example, a browser that pauses for upwards of 50 ms at a time? How about a game? Go's garbage collector can very much result in 50 ms pauses. When The Verge reviews new phones, they definitely dock points for a laggy OS, and dropping three frames in a row regularly is considered laggy these days...

There are certainly GCs that don't pause for 50ms at a time -- Go's GC is not very good, and they even admit it. Felix Klock's PhD is an interesting exploration of this: http://www.ccs.neu.edu/home/pnkfelix/thesis/ although his collector does have some long pauses on particularly evil programs (those programs cause much longer pauses on conventional collectors).

> There are certainly GCs that don't pause for 50ms at a time -- Go's GC is not very good, and they even admit it.

Of course. I'm just refuting the specific claim of "ballpark C" performance with an immature GC.

Re: Baby's First Garbage Collector

#57

Post by aidenn0 »

phamilton wrote: post #3

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, an…

See this: http://www.hpl.hp.com/personal/Hans_Boehm/gc/

But also with a very small number of restrictions, you can make C have non-conservative GC.

ANSI C forbids aliasing as any type but a character. Furthermore, unions are to be interpreted as the last type they are accessed as.

The three places you run into issues are:

1) You can treat two structs that begin with the same values interchangeably so long as you only access the common beginning of the structures.

2) You can freely convert pointers to integers and back.

3) Storage returned by malloc() can be used heterogeneously (however, with strict aliasing rules, you can't switch types of the data once you've accessed it)

If you forbid those three things, then you can have a strict gc by adding runtime overhead to accessing data (once malloced data is accessed by a non-character type, you can treat it like that type forever).

However, lots and lots of code violates these rules, (the most famous code that does is probably the fast inverse square-root)[1]

http://betterexplained.com/articles/understanding-quakes-fas...

Re: Baby's First Garbage Collector

#58

Post by aidenn0 »

dllthomas wrote: post #51
_delirium wrote: post #39

Earlier quoted context omitted.

Most languages don't give you any guarantees if you do that, though. In C, for example, pointer arithmetic on a void*, or on a pointer cast to an integer, is not guaranteed to produce sensible results. The standard only provides guarantees for pointer arithmetic if it's performed on a non-void pointer that points within an array, and the results remain within the bounds of the same array (arithmetic that produces a p…

In ordinary C, without a garbage collector, I'd be baffled to find an implementation where one could not: 1) Cast a pointer to an integer of sufficient size. 2) Xor that integer with another value. 3) Xor the result with the same value. 4) Cast back to a pointer. 5) Dereference. It's sufficiently corner-case that I am not certain what the standard says about it. In any event, pointers matter when coding in assembly,…

That is actually allowed in the standard; it specifically says that casting a pointer to an integral type of sufficient size is a reversible operation (though it I'm not sure if this is not well defined: (int i[2]; (int )((int)i)+sizeof(int)

Re: Baby's First Garbage Collector

#59

Post by dllthomas »

aidenn0 wrote: post #58
dllthomas wrote: post #51

Earlier quoted context omitted.

In ordinary C, without a garbage collector, I'd be baffled to find an implementation where one could not: 1) Cast a pointer to an integer of sufficient size. 2) Xor that integer with another value. 3) Xor the result with the same value. 4) Cast back to a pointer. 5) Dereference. It's sufficiently corner-case that I am not certain what the standard says about it. In any event, pointers matter when coding in assembly,…

That is actually allowed in the standard; it specifically says that casting a pointer to an integral type of sufficient size is a reversible operation (though it I'm not sure if this is not well defined: (int i[2]; (int )((int)i)+sizeof(int)

Could you have a standards-conforming implementation where pointers were big-endian and other integral values little-endian? That would break your example code. I don't know of any architecture that would motivate that, of course...

Re: Baby's First Garbage Collector

#60

Post by kevingadd »

MaulingMonkey wrote: post #54
kevingadd wrote: post #52

Earlier quoted context omitted.

You can't store a raw pointer, but you can store the 'safe' forms of pointers (IntPtr, etc) which allows you to do some of the stuff you'd want to do - allocate a buffer of given size in unmanaged heap, then manipulate it entirely using struct pointers and pointer arithmetic. The key/value store I wrote in C# does this - no data lives in the managed heap, it's all sitting in unmanaged memory (mapped files, as it happ…

> You can't store a raw pointer You can if you mark the containing class/struct "unsafe", which allows both type safety and increased ease of use.

Hmmm, I've never seen this done. Thanks for the heads-up, I'll have to try it out. Are you sure you can do it with classes? I would not be shocked by being able to do it with structs.
Post reply on HN