Live data from Hacker News

Baby's First Garbage Collector

journal.stuffwithstuff.com

61–70 of 90 posts

Re: Baby's First Garbage Collector

#61

Earlier quoted context omitted.

> 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.

Sure am.

  using System;
  
  namespace Test2012
  {
  	unsafe class C  { public byte* P; public override string ToString( ) { return new IntPtr(P).ToString( ); } }
  	unsafe struct S { public byte* P; public override string ToString( ) { return new IntPtr(P).ToString( ); } }
  
  	static class Program
  	{
  		static unsafe void Main( )
  		{
  			fixed( byte* test = new byte[] { 1, 2, 3 } )
  			{
  				var c = new C( ) { P = test };
  				var s = new S( ) { P = test };
  				Console.WriteLine( "Test: {0}", c );
  				Console.WriteLine( "Test: {0}", s );
  			}
  		}
  	}
  }
Result:

  Test: 40510364
  Test: 40510364
  Press any key to continue . . .

Re: Baby's First Garbage Collector

#62
post #6

Earlier quoted context omitted.

When you hear talk of "conservative" Garbage Collectors, what the "conservative" refers to is that anything on the stack that looks like a pointer is treated as if it is a pointer. After all, it doesn't matter what you cast a pointer to, it's all just 1s and 0s on the stack...

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.

You can serialize it to a hex string, put it in a json request that you send off to some cloud service, and then an hour later parse it back out of the json reply, with nothing left in RAM that looks like that pointer for the time inbetween.

Re: Baby's First Garbage Collector

#63
post #49
post #48

I don't understand. When sweep frees an object, it invalidates the "next" object of the previous object in the linked list, breaking the traversal next time a gc() is called. Doesn't the linked list have to be patched? (e.g., keep track of "prev_object" and set its next to unreached->next before freeing unreached)

I think `*object = unreached->next;` does that, since it's using a pointer to a pointer.

That's correct. It patches the "next" pointer of the previous object to point past the freed object.

It's a pointer to a pointer to handle the case where you're freeing the first object in the list. In that case, it's "firstObject" that needs to be modified, not some Object's "next" pointer.

Using a pointer to a pointer (while admittedly harder to read at first) lets you handle both of those cases with the same code.

Re: Baby's First Garbage Collector

#64
post #41

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 research prototypes for such GCs and usually the performance decreases if you want time guarantees. As far as I know there is no GC, which could be used in a AAA FPS game. Convincing would be CryEngine, UnrealEngine, idTech, SourceEngine, etc starting to use a GC in their rendering, physics, sound parts.

Re: Baby's First Garbage Collector

#65
post #4

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…

I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.

> I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave

Oberon, Oberon-2 allows you to use no-GC pointers via the SYSTEM package.

Active Oberon additionally adds syntax support for untraced pointers.

Modula-3 has unsafe modules which allow you to use untraced pointers.

D has unsafe pointers in system blocks.

Ada and C++11 have support for optional GC defined on the language standard. However so far, there isn't any compiler vendor that really offers them.

In Java you can do a bit of dirty pointer tricks via the com.sun.unsafe package, but it is Oracle's VM specific. Although there are plans to make it part of the official library after Java 8.

Re: Baby's First Garbage Collector

#66
post #21

So every once in a while I come across old timey C optimizations in the spirit of Duff's device or bit twiddling to swap variables, 'etc 'etc... While they have a certain kind of charm to them they seem to be almost universally bested by increasingly mature compilers and complex (or virtualized) hardware. So I'm kind of coming to the conclusion that clever pointer arithmetic games and even manual malloc/free are incr…

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...

You act like most of those phones aren't Java based. Android's GC is actually pretty nice these days.

Re: Baby's First Garbage Collector

#67
post #44
post #21

So every once in a while I come across old timey C optimizations in the spirit of Duff's device or bit twiddling to swap variables, 'etc 'etc... While they have a certain kind of charm to them they seem to be almost universally bested by increasingly mature compilers and complex (or virtualized) hardware. So I'm kind of coming to the conclusion that clever pointer arithmetic games and even manual malloc/free are incr…

For example: It's nice to be able to write a big hunk of state to persistent store and read it back in again with a single operation (like for app pause/resume) vs. iterating through a huge object graph and serializing. Of course it'd be rad if languages could help you not screw this up (maybe Rust does?) GC doesn't solve all problems, for instance some of the weak reference bugs crop up just as often in Java as they…

No, but it does simplify coding a lot.

In the presence of a GC many algorithms and code refactorings become much easier if you don't have to track all the time who is responsible for releasing a chunk of memory.

Specially in the presence of multicore algorithms and big code bases.

Added to that the fact that in today's industry developers tend to know just a little bit of the code base, given the size of some projects and team's attrition.

Re: Baby's First Garbage Collector

#68
post #21

So every once in a while I come across old timey C optimizations in the spirit of Duff's device or bit twiddling to swap variables, 'etc 'etc... While they have a certain kind of charm to them they seem to be almost universally bested by increasingly mature compilers and complex (or virtualized) hardware. So I'm kind of coming to the conclusion that clever pointer arithmetic games and even manual malloc/free are incr…

I was introduced to programming through python. Now that I'm in school, I've been doing most of my work in C++. I have to say, as much as I like programming in python, my knowledge of programming is made so much better because I've had to write C++. From an educational perspective, I think non-GC languages will always have a place (if only for teaching about computers). In production environments, I don't think that…

No all GC enabled languages are like Python.

Have a look at Oberon for example. A systems programming language with GC, used to program a fully working single user desktop system in the mid 90's.

Used at many universities around the world.

Yes it required the use of Assembly for hardware communication, but so do C and C++.

Re: Baby's First Garbage Collector

#69
post #21

So every once in a while I come across old timey C optimizations in the spirit of Duff's device or bit twiddling to swap variables, 'etc 'etc... While they have a certain kind of charm to them they seem to be almost universally bested by increasingly mature compilers and complex (or virtualized) hardware. So I'm kind of coming to the conclusion that clever pointer arithmetic games and even manual malloc/free are incr…

Let me link to a (very longwinded, sorry) post I made a while back explaining how a particular type of memory pool allocator works: https://news.ycombinator.com/item?id=6176091 tl;dr if you think "manual memory management" means "malloc thing, use thing, free thing" you're kind of missing the point. Also, tricks like Duff's device and XOR swap have long since become pessimizations, not optimizations, on desktop and m…

> Or, more bluntly, "if C and C++ are so dumb then why isn't your browser written in Python?"

Because Python's standard implementation, CPython is an interpreter?

Re: Baby's First Garbage Collector

#70
post #64
post #41

Earlier quoted context omitted.

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 research prototypes for such GCs and usually the performance decreases if you want time guarantees. As far as I know there is no GC, which could be used in a AAA FPS game. Convincing would be CryEngine, UnrealEngine, idTech, SourceEngine, etc starting to use a GC in their rendering, physics, sound parts.

The Witcher 2 for the XBox 360 has a GC on their engine, although they did face some issues.

http://www.makinggames.de/index.php/magazin/2155_porting_the...

Post reply on HN