Re: arrays = pointers?

On Fri, 02 Mar 2007 17:05:42 +0800, Göran Andersson <guffa@xxxxxxxxx> wrote:
Yes, as the program code has to do nothing at all to manage the references, that means that updating a reference is perhaps twice as efficient in .NET as in an environment that uses for example reference counting.

It seems you are again responding to points I did not make. I never once brought up the question of "reference counting", nor do I find it relevant to the discussion I'm participating in.

The .NET method is nowhere near as efficient in *updating* as the old Mac "handles" method. Using handles, a single value needs to be updated. That's it. It's a few instructions at most. This is WAY faster than .NET running through all of the data structures in the memory manager, finding those that refer to a given object and modifying them.

[...]
Performance might be better the way .NET does it, but certainly the old Mac-style "handle" paradigm was much simpler, and required much less memory overhead (and back then, with memory space always being at a premium, reducing data structure and code size was always the highest priority). :)

Well, how much memory overhead is there really?

Above and beyond what .NET already requires? Practically none in the form of data storage, as far as I know. But that only happens because .NET has an enormous data overhead already. It's only because each and every variable "knows" what it's doing that the garbage collector can avoid having to store any additional data.

However, there is still the code required to do the actual garbage collection. Even when one discounts the data storage requirements, the code required to navigate the existing data and update the references is far greater than the handle method used in the old Mac OS.

With the garbage collected model, all the memory management is done by the garbage collector. Hopefully this means that as the garbage collector has all the information, it is able to do better descisions about the memory management.

I see at least two major advantages to a garabage collection paradigm:

* Lazy freeing of resources means that in many cases, memory management overhead is lower during key performance-critical code paths

* Reduced address space fragmentation (ie the virtual memory equivalent to the reduced RAM fragmentation that the old Mac OS "handle" paradigm was so important for)

The latter, of course, has only recently been very important. When the Win32 first came along, no application came close to using the full 2GB of virtual address space, nor did any application allocate large enough blocks of virtual address space to risk failing due to address space fragmentation. Things have change, of course (though, ironically .NET has only started to gain a foothold just as 64-bit Windows is nearing achieving mainstream status, eliminating the address space fragmentationissue again :) ).

I see as a minor benefit the memory manager's ability to use object type information for the purpose of memory management. Yes the additional information is useful, but I don't see it as a huge leap. We got along fine without taking advantage of that information...applications would generally implement their own layer on top of the Windows memory management, if they needed (for example) to keep objects of the same time within a single block of virtual address space (one way to help avoid fragmentation issues, also for example).

In a reference counting model, each object would be freed at the instant that the reference counter reaches zero (which means that clearing a reference is very unpredictable timewise), while in the garbage collected model an entire heap generation is cleared all at once. Usually this means moving away the few object that still are used so that the entire heap generation can be wiped clean.

Not that I mentioned reference counting in the first place, but yes...I agree that the .NET paradigm by its very design avoids some of the pitfalls of reference counting (one major one being the classic problem of the reference count being incorrect).

As the most active heap generation is regularly cleaned out completely, this vastly reduces memory fragmentation.

In theory, garabage collection should practically eliminate virtual address space fragmentation (the virtual memory manager handles the avoidance of physical memory fragmentation). Only objects that have been locked will present a problem, and one hopes that an application is wise enough to minimize those. That said, I don't see that as relevant to the question of reference counting (since you brought it up). That is, even a garbage collection scheme based on reference counting can avoid fragmentation in the same way. It's the garbage collection that is important, not how memory objects are tracked.

[...]
Yes, probably. As the applicataion code is running most of the time, and the garbage collector only occasionally (from a computer point of view), optimising the application code seems to be the obvious choise.

One hopes. The obvious counter-example is where the garbage collection, though it happens infrequently, takes an inordinate amount of time. Presumably this isn't the case in actual implementation, but the "most of the time" versus "only occasionally" difference in no way guarantees a desirable performance outcome.

Even if the garbage collector has to to ten times the work to make up for the lack of a object handle table or a reference reference table, that should be nothing compared to making every reference operation in the application code twice as fast.

Well, I haven't measured, but I'd say the garbage collector has to work a LOT harder than just ten times, at least compared to the old Mac OS "handle" paradigm.

In the "handle" paradigm, the garbage collector is basically O(n); the collector can simply scan through the handle table, coalescing the objects and updating each handle once. In the .NET paradigm, the collector has to either scan the entire collection of data for each object it wants to move, or it has to maintain some sort of hash table or other fast-access data structure in which it stores (at least temporarily) all of the current references to each given object (which is essentially the "reference reference table" method anyway). In the former case, that's essentially an O(n^2) algorithm, which as you know is much slow than an O(n) algorithm. In the latter case, the premise that the garbage collector requires no extra data is invalidated (in other words, is irrelevant to this discussion, since you have made the claim that no extra data is required by the .NET scheme).

(The O() above obviously doesn't take into account the actual copying of data when moving objects...that work is identical regardless of the collection scheme, so I don't find it relevant).

I don't actually know which scheme is used by .NET, but it's clear to me that however it is done, garbage collection is a lot more costly under ..NET than it would be under a "handle" scheme. Likely way more than just 10x difference. Do we still come out ahead? Probably. Heck, I have to assume so because I love using .NET and would hate to learn that it's moved backwards in any way. :) But I can't say that it's an obvious given.

Pete
.

Relevant Pages

  • Re: Memory Cleanup
    ... Calling GC.Collect is not the ... // The total memory has not gone down. ... reference counters, and nothing happens when objects go out of scope. ... objects just remain in memory waiting for the garbage collector to remove ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: FileStream.Close() & GarbageCollection - Memory Leak Question
    ... Somewhere in memory the memory allocated to the object still resides, ... If you don't clear the variable, then yes, this will throw an exception. ... concerned the GarbageCollector uses the reference and by nulling it I ... It is on the other hand the lack of live references to allocated memory that the garbage collector figures out what to collect. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: C++ sucks for games
    ... > own garbage collector, but i've done it better than lisp could have. ... have a reference to some level data, and you make that reference go out of ... trivial memory management problem. ... except that you can know exactly when those deallocations ...
    (comp.lang.lisp)
  • Re: C++ sucks for games
    ... > own garbage collector, but i've done it better than lisp could have. ... have a reference to some level data, and you make that reference go out of ... trivial memory management problem. ... except that you can know exactly when those deallocations ...
    (comp.lang.lisp)
  • Re: Memory Cleanup
    ... I assume that you previously programmed in an environment having a heap that uses reference counters and deallocates objects the moment when there are no more references to it. ... The objects just remain in memory waiting for the garbage collector to remove them. ... The garbage collector is only run when needed, which usually happens when the first generation heap is full. ... At that time the most of the objects in the first generation heap are unused, so the garbage collector just moves the used objects to the second generation, and the first generation is empty again. ...
    (microsoft.public.dotnet.languages.csharp)