X++: Garbage Collection and Ax Performance Whitepaper

[Blog bot]

Источник: http://blogs.msdn.com/x/archive/2010...hitepaper.aspx
==============

Abstract:

The current paper investigates issues concerning the deterministic garbage collection strategy currently employed in Dynamics Ax, and compares its performance with the .NET non deterministic garbage collector.

Background.

Dynamics Ax uses a deterministic garbage collector to manage the lifetime of X++ objects and tables. The system is deterministic in the sense that objects are guaranteed to be disposed from the C++ memory space at the earliest possible moment. The system employs a reference counting algorithm that is enforced by the X++ interpreter. Whenever a reference is made to an object, the reference count is increased. Whenever a reference is removed, (either by another value being assigned to a variable or a variable becoming unavailable because the scope within which it is defined is exited) the reference count is decreased.



Figure 1 Object deletion through reference counting.

This simple approach is not adequate to deal with object structures containing loops: Consider the trivial case of two objects referring to each other:



Figure 2 Mutually dependent objects, requiring loopcount

Clearly in this case, the objects should be disposed as there are no external references to the objects. To cater for this, in addition to the reference count, a loop count is maintained, that indicates the number of loops in which the object takes part. When the difference of the reference count and the loop count is 0 the memory occupied by the object is reclaimed.

The algorithm described here works across the client/server boundary (which makes it unique in this respect).



Figure 3 Object graph spanning the client server boundaries. All objects are bound for destruction.

Even though the algorithm guarantees that storage is reclaimed as soon as it is possible to do so, the application programmer has no hooks into this. It is not possible to implement a method that is called when the object is reclaimed (akin to implementing the IDisposable interface in .NET)

In this distributed scenario the loop/ref information is maintained though the exchange of suitable messages over the network, causing considerable network traffic and performance degradation.

As described, tables use the same algorithm, but the case is much simpler for tables, as tables cannot contain references to other tables. Therefore there is no loop count to maintain, and the reference count is enough to determine when a table instance should be disposed. We will not discuss tables further in this document.

The garbage collection strategy used in .NET is very different. It relies on a mark-and-sweep algorithm where the set of objects are examined periodically to check if references are held to them. If that is not the case, the storage is released. This strategy specifically does not make any guarantees as to if and when storage is actually reclaimed – The sweep is done when a complex set of criteria are met, at the garbage collector’s discretion. You can find a fuller description of the .NET garbage collector in (Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework)

The present Garbage Collection Problems

The basic problem with the algorithm described above is that it scales rather poorly in the face of an increasing number of object having loops in the object graph. The reason is that any simple assignment to an object may require extensive analysis to update the loop counts for all the objects in the structure and therefore significant network traffic when the objects are distributed.

We have had many issues from customers and from internal developers that have been caused by this fact. The scenarios invariably involve structures that are self referential containing many objects. There are workarounds that can be applied to the problem, in which the reference loops are managed through lookups in suitable structures, but it is a trap into which many developers fall. Typically programmers write code that generates structures in which the objects are a monotonously increasing function of the number of records in a database table. This will work fine for test purposes, but will fail in production cases.

To illustrate the point, please consider some simple X++ code that builds a circular linked list of elements: After the list is built it is dismantled by taking each element out of the loop, thus forcing a rescan of the remaining structure. Note that all objects created and destroyed are on the same tier (namely the client tier). The source code is listed in appendix A. We illustrate the time expenditure as a function of the number of elements in the circular structure[1].



Figure 4 Performance of Deterministic GC relative to .NET GC

The x axis is the number of elements in the circular list. The y axis is the time spent in milliseconds on the algorithm in appendix A. The green line is the performance of the deterministic garbage collector. The performance is clearly exponential.

The blue line is the performance achieved doing the same thing in IL. The execution never managed to register a reading of more than 1 second, even when the number of nodes exceeded 350.000, more than one order of magnitude more than what is shown in the graph.

The deterministic garbage collector has one other serious flaw: Its traversal of the object graph is recursive. This means that it can run out of C++ stack space, which invariably results in a crash. We have not seen this in production code yet, but it is a potential problem, even for graphs that do not contain loops.

Even though the algorithm is chosen for its known aggressive nature, it should be clear from the graph above that the current deterministic GC algorithm does not scale well.

Fortunately there is a very simple way of avoiding these issues:

Resolve loops

The poor performance witnessed in the example above is caused by the fact that every time a change is made in the object graph, the whole structure must be traversed to calculate the loop count. The simplest solution, then, is to eliminate the loops.

For instance, say you are maintaining a structure describing books in a library: The library contains a number of books, that contain a number of chapters, each with its own set of paragraphs etc. Say that each chapter needed a reference to the book that it is part of. If the chapter object simply points to the book it is part of you would have introduced a loop, which would not scale well.

Instead, you could store the name of the book containing the chapter, and then have some lookup mechanism to get the book object from that unique name. Then the loop would be gone, physically, if not conceptually.

Using Managed code.

You can always use the CLR bridge, allowing you to seamlessly call managed code from X++ code, and then build the objects in managed code. If you do, you must make sure the interface between the two runtime contexts (X++ and managed code) does not become too chatty, since the managed calls are performed using reflection.

Note carefully that the nature of the example used in this test was chosen to show the problems in the current garbage collector. The example consists basically of allocation and deallocation and some glue to make it all work. In this respect the code can be seen as pathological in that it will produce an extreme performance benefit from being converted into managed code. Real production code, that often needs to pay the price of doing data access or interacting with kernel classes defined in the unmanaged kernel will not display this sort of improvements.

Appendix A: The source code used in the example

Exportfile for AOT version 1.0 or later

Formatversion: 1

***Element: CLS

; Microsoft Dynamics AX Class: GCPerformanceTest unloaded

; --------------------------------------------------------------------------------

CLSVERSION 1

CLASS #GCPerformanceTest

Id 50017

PROPERTIES

Name #GCPerformanceTest

Extends #

RunOn #Called from

ENDPROPERTIES

METHODS

Version: 3

SOURCE #classDeclaration

#class GCPerformanceTest

#{

#}

ENDSOURCE

SOURCE #Main

#static void Main(Args a)

#{

# ListElement r;

# TextBuffer tb = new TextBuffer();

# int i, j;

# int64 ticks;

#

# tb.appendText("Iterations\Time(ms)\n");

# for (i = 1; i <= 62; i++)

# {

# j = i * 500;

# print j;

# ticks = WinApi::getTickCount();

# r = GCPerformanceTest::SetupGraph(j);

# GCPerformanceTest::TearDownGraph(r);

# ticks = winAPi::getTickCount() - ticks;

# tb.appendText(strfmt("%1\t%2\n", j, ticks));

# }

#

# tb.ToFile("c:\\users\\pvillads.redmond\\results.log");

# pause;

#}

ENDSOURCE

SOURCE #SetupGraph

#static ListElement SetupGraph(int numberOfNodes)

#{

# ListElement l, root, prev = new ListElement(1);

# int i;

#

# root = prev;

#

# for (i=2; i <= numberOfNodes; i++)

# {

# l = new ListElement(i);

# prev.parmNext(l);

# prev = l;

# }

#

# prev.parmNext(root);

# return root;

#}

ENDSOURCE

SOURCE #TearDownGraph

#static void TearDownGraph(ListElement graph)

#{

# ListElement n, nn;

#

# while (graph != graph.parmNext())

# {

# n = graph.parmNext();

# nn = n.parmNext();

#

# graph.parmNext(nn); // there is no longer a ref to n

# }

#}

ENDSOURCE

ENDMETHODS

ENDCLASS

***Element: CLS

; Microsoft Dynamics AX Class: ListElement unloaded

; --------------------------------------------------------------------------------

CLSVERSION 1

CLASS #ListElement

Id 50016

PROPERTIES

Name #ListElement

Extends #Object

RunOn #Called from

ENDPROPERTIES

METHODS

Version: 3

SOURCE #classDeclaration

#class ListElement extends Object

#{

# ListElement nextElement;

# int no;

# str name;

#}

ENDSOURCE

SOURCE #new

#void new(int number)

#{

# no = number;

# super();

#}

ENDSOURCE

SOURCE #parmNext

#ListElement parmNext(ListElement _nextElement = null)

#{

# if (!PrmIsDefault(_nextElement))

# nextElement = _nextElement;

#

# return nextElement;

#}

ENDSOURCE

ENDMETHODS

ENDCLASS

***Element: PRN

; Microsoft Dynamics AX Project : GCPerformance unloaded

; --------------------------------------------------------------------------------

PROJECTVERSION 2

PROJECT #GCPerformance

PRIVATE

PROPERTIES

Name #GCPerformance

ENDPROPERTIES

PROJECTCLASS ProjectNode

BEGINNODE

FILETYPE 0

UTILTYPE 45

UTILOBJECTID 50017

NODETYPE 329

NAME #GCPerformanceTest

ENDNODE

BEGINNODE

FILETYPE 0

UTILTYPE 45

UTILOBJECTID 50016

NODETYPE 329

NAME #ListElement

ENDNODE

ENDPROJECT

***Element: END

[belugin]

В некоторых случаях также можно испоользовать класс ObjectIdent каковой представляет собой слабую ссылку соответственно к циклам не приводит

[Logger]

Цитата:

Сообщение от belugin

В некоторых случаях также можно испоользовать класс ObjectIdent каковой представляет собой слабую ссылку соответственно к циклам не приводит

А где можно про него почитать, не подскажете ?

[belugin]

я так думаю, что нигде - я сам его вычитал в классе info

[MikeR]

Прочитал несколько раз, мозг немного размяк .
Так понял интрига в том, что в некоторых случаях удобнее хранить идентификатор книги вместо глав, которые потом можно в цикле перебрать.
А GC(Х++) делает как по-главно.

PS имеется в виду цикл перебора ссылок на объект\объекты

[Logger]

Цитата:

Сообщение от belugin

я так думаю, что нигде - я сам его вычитал в классе info

А откуда поняли что он используется для слабых ссылок ?
По логике применения ?

[belugin]

я уж не помню, путем каких-то экспериментов установил - в Ax это легко потому, что мусор собирается как только становится мусором