Ideas wanted: GC for records with linked lists

[idog]

Hi all,

In the programming section of my (Hebrew) website I offer educational programming projects in Object Pascal. While planning one of those I ran into an interesting problem; maybe someone can help with ideas/suggestions?

Basically, I'm implementing a BigInt (pseudo-integer type with arbitrary number of digits) using a Record that has a pointer to a simple linked list (for the digits). There'll also be some functions for basic arithmetic, and I figured that the most user-friendly method to implement them would be with operator overloading, as if BigInt was a standard numeric type.

However, this creates the problem of freeing the memory allocated for the linked lists when the program terminates. I don't want the programmer to have to type something like "ClearBigInt(x);" for every BigInt at the end of every function...

My idea so far was to implement a simple "Garbage Collector" - a table of all "Active" BigInts, that will be updated every time a BigInt operator is run (from the overloading operator function). This way I can trap the BigInts that are being used and free them in the unit's Finalization.

Does this solution make sense? Any better ideas?

P.S. Unless there's a very good reason to do so, I don't want to use classes for this, and naturally I'm not going to use any existing BigInt implementation because that's the point of the whole project 

Thanks in advance,

[marcov]

I'm not entirely sure this would work. This e.g. because you don't know if a result an operator gives back is a temporary result (needing to be GCed) or a final result that might be stored somewhere permanently.

To this problem there are two "normal" and two halve "weird" solutions:

the whole solutions:

- use a record with a dynamic arrays of a static or ref counted type. Since dyn arrays are automatically disposed, so will be the result
- use a class instead of a record, but make the reference an interface. Interfaces are refcounted, and can clean up after themselves

The halve solutions mess with memory allocation as a whole; I've heard both only described, not tested them myself:

The first workaround I've oassumes you need the GCed type only for intermediate results, and use a conversion (e.g to double or so) for the final result.

This means that if you hand out allocations from a block, and after a while move on to the second block, you can, after another while, simply deallocate the first block as a whole (including child fields). If the beast is a class, have a look at newinstance. Overriding it might help you there.

The last one is the big one. Try to use a existing Boehm GC as can be used with C and C++. This is a very complex issue, untested, and not much is known about it. The following page in the wiki summons up the bits that are known (i.c.w. FPC) http://wiki.freepascal.org/garbage_collection

[eny]

Or use interfaces; automatically destroyed when out going of scope.

[Vincent Snijders]

Or use interfaces; automatically destroyed when out going of scope.

That is the same as marcov's

- use a class instead of a record, but make the reference an interface. Interfaces are refcounted, and can clean up after themselves

[marcov]

Or use interfaces; automatically destroyed when out going of scope.

That is the same as marcov's

- use a class instead of a record, but make the reference an interface. Interfaces are refcounted, and can clean up after themselves

Or a variant btw. Since variants can contain automated types and thus are also finalized. (and can contain interfaces)

[skalogryz]

- use a record with a dynamic arrays of a static or ref counted type. Since dyn arrays are automatically disposed, so will be the result

the best solution, imho.

no need for manual BigInt creation and dispose (as it would be necessary for Objects). No need to care about memleaks, since dyn arrays are handled by the compiler.

[idog]

Thanks for the suggestions!

I think that using dynamic arrays is indeed the best option for this kind of project... I'll just have to teach linked lists elsewhere

By the way, Marcov - I'm not sure why you think my original idea won't work.. true, it will be a global-level GC and that's not very economic, but I still think that if I trap every pointer to a linked list (no matter if it's ad-hoc or an existing variable), I can free them all later.

[eny]

Or use interfaces; automatically destroyed when out going of scope.

That is the same as marcov's

Not really.
Except when you say that ref counting eq. interfaces, which it doesn't (although they are related).

[Vincent Snijders]

I am sorry, but I don't understand the difference between
* classes as container using interfaces as references and
* using interfaces

What is the differences between those two options?

[eny]

My mistake, missed the bit (twice) where marcov said '...but make the reference an interface....' 
(Not enough sleep last night...)

[mas steindorff]

I just got done with a project that addresses this issue.  I'm old school so my first ideal was to use linked list with all of the memory stuff as well but then I saw that a TObjectList has all of that code built into it.  I tested it's speed and memory usage and was pleased with it's performance with over 10,000 records being deleted and created with no memory leaks. 
I don't need to do a lot of .delete during a run so the I can't say how well the memory managers GC works over long term.

It's hard do say what will be the most benefit to the student in the end, to do the work or to see how much work can be saved.
marty

[eny]

... or to see how much work can be saved.

From a business perspective: less work = lower cost 

[marcov]

By the way, Marcov - I'm not sure why you think my original idea won't work.. true, it will be a global-level GC and that's not very economic, but I still think that if I trap every pointer to a linked list (no matter if it's ad-hoc or an existing variable), I can free them all later.

It will work perfectly, but it is useless You can deallocate all memory that way at the end of the program, and that is the problem, ONLY at the end of the program, which is pretty useless (since the all program memory is deallocated automatically then anyway) except for avoiding noise in heaptrc (-ghl) output

The other solutions went more in the direction of the ability to dispose when the intermediate results were no longer necessary.

[idog]

since the all program memory is deallocated automatically then anyway

True.. it's about time I got the facts right about memory management Was this always the case? I was under the impression that memory leaks could impede the OS even after a program terminates. Maybe it was just Win95 or something?

[marcov]

since the all program memory is deallocated automatically then anyway

True.. it's about time I got the facts right about memory management Was this always the case?

To my knowledge: yes.

I was under the impression that memory leaks could impede the OS even after a program terminates. Maybe it was just Win95 or something?

Win95 had a problem with not deallocating resource leaks. But that were GDI resources, not plain memory. Probably you are mixing that up. GDI resources are properly deallocated under NT4 and later too