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

81–90 of 90 posts

Re: Baby's First Garbage Collector

#81

Post by asveikau »

ANTSANTS wrote: post #38
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 m…

I think the HN crowd honestly believes that the only reason the next browser hasn't been written in a GC language is momentum and time. That the next one will very obviously be written in Ruby or Python. I've seen discussions here to that effect.

I find it hard to read HN discussions about C. One faction is totally amazed by the C equivalent of being able to tie their shoes. The other faction believes shoelaces are obsolete and everyone should wear velcro.

This "my generation has missed out" thing is really odd... If you are honestly interested in it, go learn how it works! The commenter you're replying to should quit making excuses.

Re: Baby's First Garbage Collector

#83

Post by munificent »

unwind wrote: post #74
munificent wrote: post #63

Earlier quoted context omitted.

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.

This technique is talked about in this Stack Overflow answer: http://stackoverflow.com/questions/12914917/using-pointers-t... , which also references this Slashdot interview ( http://meta.slashdot.org/story/12/10/11/0030249/linus-torval... ) with Linus Torvalds where he gives this as his "favorite hack".

Yup, I got the idea for this from Linus. Before then, I've always done the uglier "if this is the first node then ..." special case branch instead.

Re: Baby's First Garbage Collector

#84

Post by jeffdavis »

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…

"manual malloc/free are increasingly futile unless you're targeting embedded devices"

Or have any algorithm that uses a lot of memory, or if you want control over how much memory the algorithm uses at a time.

In the article (which is great, by the way), you can see that mark-and-sweep means scanning all of the active objects. This does not have great scalability properties. CPU gets faster, but memory gets larger, so matters won't improve over time.

GCs are great for processes that are tiny. As soon as you have a memory-hungry algorithm, it starts looking worse.

Also, as others have pointed out, manual memory management is not synonymous with malloc/free. There are many other choices available, and region-oriented allocators are often nice for algorithms that use a lot of memory. PostgreSQL internally uses "memory contexts" where you allocate objects with the same lifetime (e.g. transaction-local state) in the same context, and wipe it all at once.

Re: Baby's First Garbage Collector

#85

Post by MichaelGG »

kevingadd wrote: post #53
MichaelGG wrote: post #46

Earlier quoted context omitted.

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.

You only use them via out/ref. Section 13.4.2 of the CLI spec says:

- Managed pointers can be passed as arguments, stored in local variables, and returned as values.

- Managed pointers cannot be stored in static variables, array elements, or fields of objects or value types.

So you're right, they have very limited scope as it'd be messy otherwise. It's my understanding that the JVM does not have pointers even at this level, hence Java can't do out/ref parameters. (Sure, tuples are a better way to handle many cases of out params, but sometimes a well chosen ref can really be nicer.)

I think C++ also uses the term "managed pointer" but not in the same technical sense (I think it just means reference.) Using "safe" C++/CLI generation limits the scope of pointers just like we'd expect.

Re: Baby's First Garbage Collector

#86

Post by MichaelGG »

bitwize wrote: post #77
MichaelGG wrote: post #47

Earlier quoted context omitted.

I think the parent comment was pointing out that less and less, there's no real reason to need C++. The performance in safer languages is usually far more than adequate, while requiring less code (less bugs) and blocking entire classes of bugs. Even Tim Sweeny of Epic (Unreal Engine) said they'd gladly switch languages to improve productivity. And game engines are one of the few places that still do need to eek out a…

I once read a comment that said that C++ is like a very sharp knife. If you know how to use it, it's safer than a dull knife; if you don't, then you need to have your totin' chip taken away. I like to compare it to the F4U Corsair: anyone but a talented and experienced pilot at the yoke will lead to certain disaster. But the thing is just so powerful and so absurdly versatile that until something decisively and signi…

That argument seems rather incorrectly biased. The gist is "C++ is awesome, and if you have any problems, it's because you're not awesome enough".

Tim Sweeny's talk[1] indicates that a majority of their bugs are due to low-level "unsafe" code issues. If the people writing Unreal have those problems, I think it's safe to say that it's a problem with the language. Unless you want to make the argument that Epic doesn't hired "talent and experienced" pilots.

C++ sure has places where it might be needed, but those places are growing less every day. And it's more due to the momentum, not the inherent merits of C++. If, say, Microsoft threw their weight behind a language like, say, Rust, the landscape could change. Or if they really pushed on the CLR to make the type system encompass more things and really beef up codegen, we might get somewhere. (The CLR can already easily slide into low level code, even hand-written assembly; the general codegen and limited memory management options are what kills.) Instead, we'll see more things grafted on to C++ (like recent type inference and lambdas) that make C++ somewhat less painful and further reduce the pressure to switch.

1: http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-...

Re: Baby's First Garbage Collector

#87

Post by recuter »

asveikau wrote: post #81
ANTSANTS wrote: post #38

Earlier quoted context omitted.

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…

I think the HN crowd honestly believes that the only reason the next browser hasn't been written in a GC language is momentum and time. That the next one will very obviously be written in Ruby or Python. I've seen discussions here to that effect. I find it hard to read HN discussions about C. One faction is totally amazed by the C equivalent of being able to tie their shoes. The other faction believes shoelaces are o…

Sorry for the poor phrasing, maybe you've misunderstood: I've mentioned that I'm interested, am fond of it, and have learned how it works. Not sure what excuses you're talking about.

OTOH, for when I'm not writing a browser, a HFTs, or the next-gen video game engine, the trade offs are increasingly not worth it. On top of that we don't have Amigas to have fun with anymore and stay close to the hardware on (I guess maybe Raspberry Pi qualifies as some sort of substitute) and so that particular brand of hacker, a small group to begin with, keeps on shrinking. That's what I meant by missing out.

Re: Baby's First Garbage Collector

#88

Post by hornetblack »

qznc wrote: post #64
samth wrote: 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.

John Carmack suggest that someone should write a engine in more functional way (with GC).

So you would reconstruct all the objects given access to the last frame's memory, (which would immutable). Then run the GC between frames. This may cause problems if a slower computer never has time between frames to run GC. (Running at 27fps trying to reach 30fps, my old Laptop would do this most of the time)

Re: Baby's First Garbage Collector

#89

Post by pjmlp »

inoop wrote: post #75
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…

I grew up on assembler, cycle counting, and computer graphics. You're right, a lot of the old-timey optimizations are not applicable on today's hardware, but this is just the march of technology. I didn't have to worry about generating graphics scanline-by-scanline like those poor Atari 2600 programmers. They didn't have to worry about instruction pairing on the Pentium though. Each generation has their tricks. As fo…

> In that light, it's too bad MSR canned Singularity:

Or that few people are aware of Oberon and Spin projects outside the respective universities.

As for Singularity at least parts of the native C# (Sing#) compiler landed on the Windows Phone 8 .NET native compiler (MDIL).

I would really like to know how project Midori relates to Singularity, but it is still kept internal.

Re: Baby's First Garbage Collector

#90

Post by pjmlp »

MichaelGG wrote: post #86
bitwize wrote: post #77

Earlier quoted context omitted.

I once read a comment that said that C++ is like a very sharp knife. If you know how to use it, it's safer than a dull knife; if you don't, then you need to have your totin' chip taken away. I like to compare it to the F4U Corsair: anyone but a talented and experienced pilot at the yoke will lead to certain disaster. But the thing is just so powerful and so absurdly versatile that until something decisively and signi…

That argument seems rather incorrectly biased. The gist is "C++ is awesome, and if you have any problems, it's because you're not awesome enough". Tim Sweeny's talk[1] indicates that a majority of their bugs are due to low-level "unsafe" code issues. If the people writing Unreal have those problems, I think it's safe to say that it's a problem with the language. Unless you want to make the argument that Epic doesn't…

CLR seems to be getting some new toys past Visual Studio 2013.

There is the new JIT compiler based on Visual C++ backend and more targets besides Windows Phone 8 will be supported for native code deployment.

Post reply on HN