CODEWITHSUNDEEP
c++cgarbage-collectionlanguage-designmicrocontroller
Hamza Yerlikaya
Hamza Yerlikaya

Reputation: 49339

Ideas for Garbage Collection

I am working on a toy language that uses C++ as an intermediate language, currently it only supports three types all decent from a base class, integer, list and lambda. All functions pass base class back and forth. Compiled code runs on a microcontoller, which means there are certain restrictions I only have 8 kb of ram so ideally I want to get rid of the object as soon as I am done with it. Also I don't have access to most of the standart libs (no Boost, STL etc..).

So my question is how should i attack this problem? When I started I though I would just use shared pointers but that turns out does not really work say when a bunch of integers are added to a list.

Upvotes: 1

Views: 458

Answers (3)

RHSeeger
RHSeeger

Reputation: 16282

Others have mentioned reference counting and it's problems with cyclic dependencies. If you want to go with reference counting (which is fast and responsive, as mentioned), one way to avoid the cyclic problem is to use value semantics in all places. If you don't have pointers/references at the user level, then you don't have to worry about those cyclic dependencies.

It order to conserve on memory, you'd probably want to work with some copy-on-write semantics. Ie:

x = list('a','b','c','d')
y = x; 
// x and y point to the same list in memory
y.replace(2, 'e') 
// x and y point to different lists in memory
// those 2 lists share instances of 'a', 'b', and 'd'

If you don't use something like copy-on-write, the memory use can shoot up from the value semantics.

Upvotes: 1

Matthieu M.
Matthieu M.

Reputation: 300049

I know of two general mechanisms for garbage collection:

  • Reference Counting
  • Mark And Sweep

There are various flavors / improvements which correspond more to implementations strategies (Generational, Copying, Compacting, ...).

In general, the Reference Counting is the best for reactivity (which is important here), however there is the issue of reference cycles (depending on your toy language semantics).

There are complicated algorithms to deal with the collection of cycle, but the simpler solution is:

  • Use Reference Counting for on-line maintenance
  • Perform a full "Mark-And-Sweep" collection whenever the memory reaches a defined treshold to collect the leaked cycles

Upvotes: 1

DarkDust
DarkDust

Reputation: 92384

Garbage collection always has memory and CPU overhead, so on a microcontroller you should avoid it. What you might want to use is the simple, old reference counting. Works very well for Objective-C, every iPhone/iPad/iPod Touch app uses it and a lot (most ?) Mac applications. You do it like this:

Your object base class has an integer, the reference counter. Once an object gets allocated, the counter is set to 1. There's a method retain which increases the counter and a method release which decreases the counter. Once release makes the counter reach 0 the deconstructor is called and the object is deallocated (freed).

You have to be careful to avoid retain cycles, i.e. objects that retain each other as on A <-> B or A -> B -> C -> A as then the reference counter can't drop to 0 and you'd have a memory leak. Apple solves this through naming and other conventions (e.g. if an object has a delegate, the delegate is never retained).

The advantage of reference counting is that it probably is the best "garbage collection" method for keeping the memory as low as possible. It's memory and CPU overhead are fairly low. It's major disadvantage is that the previously mentioned reference cycles is a problem, and you also need to explicitly retain/release in your program as the language won't be able to guess when not to retain.

Upvotes: 2

Related Questions