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

31–40 of 90 posts

Re: Baby's First Garbage Collector

#31

Post by betterunix »

city41 wrote: post #4
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…

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.

OCaml, though in a very restricted sense:

http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/...

Re: Baby's First Garbage Collector

#32

Post by [deleted] »

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…

[deleted]

Re: Baby's First Garbage Collector

#33

Post by dllthomas »

recuter wrote: 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…

Given that calls to malloc aren't permitted in big swaths of the code in my current (non-embedded) job, I think it's safe to say that there are still places where GC is not appropriate.

Re: Baby's First Garbage Collector

#34

Post by dllthomas »

jballanc wrote: post #6
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…

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.

Re: Baby's First Garbage Collector

#35

Post by pcwalton »

recuter wrote: 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...

Re: Baby's First Garbage Collector

#36

Post by cperciva »

logancapaldo wrote: post #23
cperciva wrote: post #11

Earlier quoted context omitted.

it's illegal to dereference a pointer past the end of an allocation. Yes, but there's a legal way to do this. reference the other two areas with offsets relative to the first area If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer t…

What if it's not a DWIM compiler? I'm pretty sure (happy to be corrected) pointer integer conversions are implementation defined. Therefore casting between could perform some reversible operation that ensured round tripping worked, but does not require that ptr(a - b) == a - b even though a == int(ptr(a)) holds.

I'm pretty sure (happy to be corrected) pointer integer conversions are implementation defined.

Quite correct, subject to the requirement that converting the same uintptr_t value back to (void ) will return the original pointer. So the conversion could be implemented as a hash table if the compiler author wanted.

But if you look carefully at what I wrote, I'm never converting a value which was not previously returned by a (void )->(uintptr_t) conversion.

Re: Baby's First Garbage Collector

#37

Post by recuter »

dllthomas wrote: post #33
recuter wrote: 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…

Given that calls to malloc aren't permitted in big swaths of the code in my current (non-embedded) job, I think it's safe to say that there are still places where GC is not appropriate.

I never claimed otherwise, I enjoy this sort of coding but increasingly GC languages seem to be the pragmatic choice and that only makes usage like yours more precious and interesting.

As that is what I was asking about I'd love for you to elaborate. :)

Sorry for the confusion, I guess I could have worded my post better.

Re: Baby's First Garbage Collector

#38

Post by ANTSANTS »

recuter wrote: 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 mobile-class hardware. Duff's device, for instance, wastes instruction cache when any decent CPU's branch predictor can eliminate most of a simple loop's overhead anyway. With the exception of manually vectorizing tight loops to take advantage of SIMD hardware (which is more of assembly's domain anyway), I think the "optimized C" of today looks pretty straightforward and unobfuscated, just with more attention paid to the details that higher level languages mostly gloss over for you.

> ...and possibly my generation has missed out on something wonderful...

I'm pretty certain I'm younger than you, I just grew up really wanting to make games and know how computers work. Maybe you don't need or even want to think about this kind of stuff, but it's not like the problems just magically disappeared one day. Or, more bluntly, "if C and C++ are so dumb then why isn't your browser written in Python?"

Re: Baby's First Garbage Collector

#39

Post by _delirium »

dllthomas wrote: post #34
jballanc wrote: 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.

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 pointer pointing outside the array of the base pointer is undefined, with the exception that pointing to one element past the end of the array is defined).
Post reply on HN