Nasal GC Musings

See How the Nasal GC works for the main article about this subject.

Old PUI dialog showing the Property browser in a custom SG/FG build that exposes Nasal internals via the fgfs property tree (listeners, timers and Nasal GC info)

Nasal GC internals visualized by plotting fps, frame spacing and GC duration using gnuplot

Introduction

The focus of the following article is to promote a better understanding of garbage collection in general, specifically mark/sweep collectors and how a generational garbage collector (GC) could be implemented in FlightGear by adapting the existing mark/sweep collector.

The goal is not to create a new GC implementation from scratch, but rather to understand and improve upon the existing GC scheme to make it more efficient. But also explore what steps might be taken to further improve FlightGear/Nasal integration, especially with a focus on improving overall performance.

Understanding GC

It is important to emphasize that the very first steps in improving the garbage collection (GC) performance in Nasal should be to fully understand the existing GC implementation. This means studying the existing GC code, understanding how it works, and identifying its strengths and weaknesses. Only by thoroughly understanding the existing GC can we begin to make informed decisions about how to improve it.

Exposing GC Internals

Once the existing GC has been fully understood, the next step should be to make the internals of the GC more accessible. This could involve adding more debugging information, providing more detailed logs, or exposing more internal data to external tools. This will make it easier to diagnose GC-related issues and identify potential areas for improvement.

Implementing a Generational GC

Only after these first two steps have been taken should we consider implementing generational GC support in Nasal.

The idea is that implementing a generational GC, which is a type of GC that separates objects into different generations based on how long they have been in memory, could improve the performance of the GC in Nasal/FlightGear.

Supporting alternate GCs

The following article also suggests that generalizing the interface of the existing GC would make it easier to experiment with other GCs, such as the Boehm/Weiser GC or sgen. Given that some GC implementations are only available in C++, it might make sense to port Nasal to compile as C++ code (which would have other benefits too).

Some examples of freely available garbage collectors (GCs) that could be used in a C or C++ project include:

• Boehm GC: This is a conservative GC that is designed to work with a wide range of programming languages and environments. It is capable of garbage collecting C and C++ programs, and is available under the Apache License 2.0.
• sgen: This is a GC that is specifically designed for use with the Mono runtime, which is an open-source implementation of the .NET framework. It is available under the MIT License.
• libgc: This is a GC that is designed to be used as a library, and can be integrated into C and C++ programs. It is available under the BSD 3-Clause License.

Porting Nasal to C++

Additionally, porting the interpreter to C++ would allow the use of standard C++ STL types, such as std::string, std::vector and std::map, to implement strings and vectors/hashes in Nasal. This would make it easier to work with these data structures, and could potentially lead to better performance and improved code readability.

Overall, porting the interpreter from C to C++ would enable the use of modern C++ features and libraries, which could potentially improve the performance, efficiency, and flexibility of the scripting language. And it could help bring Nasal up to par with other parts of the FlightGear code base.

It is generally a good idea to use an existing, well-maintained third-party garbage collector (GC) instead of starting a new GC project from scratch. This is because existing GCs have already been thoroughly tested and debugged, and are likely to be more efficient and reliable than a new GC.

Additionally, using an existing GC allows you to take advantage of the expertise and knowledge of the GC developers, who have likely spent a great deal of time optimizing and improving the GC. This can save you a significant amount of time and effort, and can help you avoid common pitfalls and mistakes that are often made when developing a new GC.

See also: https://www.fgprc.org.cn/nasal_interpreter.html

Moving Scripts into Threads

See also Canvas Threading.

Over the years, FlightGear has become infamous for its comparatively poor utilization of multi-core computers, where there's often only one or two CPUs being utilized, with many others being left idle. This is regularly brought up by end-users who have experience using other, often more complex, flight simulation software on the same setup.

Thus, another goal of this article is to better understand how the existing Nasal integration inside FlightGear could be adapted or extended/improved for future scripts to make better use of multi-threading, without having to run inside the FlightGear main loop, potentially blocking frame rate/latency (spacing). The idea would be to come up with a new optional runtime mode for certain scripts to be executed outside the main loop.

Therefore, porting the Nasal scripting interpreter from C to C++ -while being really straightforward to do- would allow us to get rid of the Globals struct and instead use proper OOP (i.e. one Nasal instance per object), so that it would also become trivial to use several independent instances of a Nasal interpreter at runtime, so that certain, well-behaved, scripts could indeed be running inside their own SGThread, separate from the main loop and separate from other unrelated Nasal scripts. While this would mean, that FlightGear would use more cores, it would mean that the GC overhead caused by such scripts would be moved out of the main loop.

One potential issue with using embedded scripting in FlightGear is that the simulator uses a single-threaded main loop. This means that (by and large) all of the simulator's functions are executed one after the other, without any parallelism. This can be a problem when using garbage collection (GC), especially a purely sequential mark/sweep algorithm that cannot be parallelized.

In a single-threaded environment, garbage collection can cause delays in the execution of the main loop. This can result in frame rate and spacing issues, which can affect the overall performance of the simulator. In other words, garbage collection can cause the simulator to become unresponsive or slow down, leading to a poor user experience.

In modern web browsers, JavaScript is used to add interactivity and dynamic functionality to web pages. Like FlightGear, web browsers used to use a single-threaded main loop to execute JavaScript code in a blocking fashion. This meant that garbage collection in JavaScript could cause similar issues, such as delays and unresponsiveness.

Modern web browsers these days support so called web extensions. Web extensions are a way for developers to add custom functionality to the browser, and they are executed in background threads. FlightGear as a project could learn how to improve the integration of its scripting engine by looking at web extensions and background scripts

Status

Last updated: 12/2022

• Introduce garbage collection
• Document the existing GC
• implement a simple clock_t based timing scheme to time each GC invocation for comparison purposes Done
• Prototype a simple gen GC scheme:
  • Patch the existing GC to allocate different pools for each generation
  • update mark() to increment a new gcSurvivals counter
  • update reap() to detect objects that have previously survived GC using a configurable threshold (possibly per generation?)
  • update reap() to by default only sweep the first generation (generation 0)
  • implement a new function to promote objects from one generation to another
  • update the naRef after moving one object to another pool (use doswap), also free up dead blocks afterwards as per naGC_swapfree()
• Provide readonly stats to inspect the GC
• Provide hooks to register custom callbacks to control GC (e.g. from FlightGear)
• Generalize the existing GC interface so that it we can begin tinkering with alternate GC schemes Not done

Background

FlightGear is an open-source flight simulator that includes built-in scripting support using the Nasal programming language. Nasal is a dynamic language that uses automatic memory management, which means that it manages the allocation and deallocation of memory automatically. Over the last two decades, Nasal has become an essential part of FlightGear, and its use has grown significantly, with many subsystems and features depending on Nasal scripts to function properly.

One example of this is the Canvas 2D rendering system, which uses Nasal scripts to set up and animate render-to-texture targets inside the simulator. Additionally, FlightGear has its own addon framework, which allows developers to create the equivalent of plugins using Nasal scripts instead of binary plugins. This has contributed to the proliferation of Nasal in FlightGear, as can be seen in complex aircraft like the space shuttle and many airliners, as well as in the weather engine, which is largely implemented in Nasal.

Overall, Nasal has become an important part of FlightGear, and its use has grown significantly over time. Many of the simulator's most complex and advanced features rely on Nasal scripting, and the continued development of FlightGear's addon framework is likely to result in even more use of Nasal in the future.

Problem

In a flight simulator like FlightGear, the frame rate and latency of the graphics engine are critical to the user experience. If the frame rate is too low or the latency is too high, the simulator will feel sluggish and unresponsive, making it difficult to control the aircraft accurately.

When the garbage collector in Nasal runs for a long time, it can cause frame rate and latency issues, which can have adverse consequences for users during critical phases of a flight. For example, during takeoff or landing, the simulator may feel unresponsive, making it difficult to control the aircraft accurately. This can be particularly problematic when attempting carrier approaches or takeoff/landing on an aircraft carrier, where precise control is essential.

Overall, long garbage collection runs can have serious impacts on the performance and usability of a flight simulator, especially during critical phases of a flight. It is important to address these issues to ensure that the simulator remains responsive and usable at all times.

There are many situations in a flight simulator where a responsive and smooth experience is essential, and where long garbage collection runs can have serious impacts. For example:

• Flying gliders or helicopters: In these aircraft, precise control is essential for maneuvering and maintaining altitude. If the simulator is unresponsive or sluggish, it can make it difficult to control the aircraft accurately, leading to crashes or other accidents.
• Flying the space shuttle: The space shuttle is a complex and challenging aircraft to fly, and requires precise control during critical phases of a flight, such as launch and landing. If the simulator is affected by long garbage collection runs, it can make it difficult to maintain control of the shuttle and complete the mission successfully.
• Flying in bad weather: In bad weather, flying an aircraft can be challenging, and requires a responsive simulator to navigate turbulence and other hazards. If the simulator is unresponsive or slow due to garbage collection, it can make it difficult to maintain control of the aircraft and avoid accidents.

In addition to the examples discussed above, there are many other situations where long garbage collection pauses can be undesirable in a flight simulator. For example:

• Recording videos of a flight: If you are recording a video of your flight, long garbage collection pauses can cause the video to be choppy and unprofessional, with stuttering and sudden jumps in the footage. This can ruin the video and make it difficult to enjoy or share with others.
• Audio/scenery mismatches: In a flight simulator, the audio and scenery are carefully synchronized to provide a realistic and immersive experience. However, if the garbage collector runs for a long time, it can cause audio and scenery to become mismatched, with sounds occurring at the wrong times or in the wrong locations. This can ruin the immersion and make the simulator less enjoyable to use.
• Multiplayer flying: In a multiplayer flight simulator, smooth and responsive performance is essential to ensure that all players have a good experience. If the garbage collector runs for a long time, it can cause stuttering and other performance issues, making it difficult to fly and interact with other players in a realistic and enjoyable way.
• Airshows and demonstrations: In an airshow or demonstration scenario, the simulator must be smooth and responsive to provide an impressive and engaging experience for spectators. If the garbage collector runs for a long time, it can cause stuttering and other performance issues, ruining the effect and making the simulator less enjoyable to watch.
• Virtual reality flying: In a virtual reality flight simulator, smooth and responsive performance is essential to provide an immersive and believable experience. If the garbage collector runs for a long time, it can cause stuttering and other performance issues, breaking the immersion and making the simulator less enjoyable to use.

Referring to VR, in addition to breaking immersion, long garbage collection pauses can also cause physical discomfort when using VR goggles. When the simulator is running smoothly, the goggles display a seamless and realistic view of the cockpit and surrounding scenery. However, if the garbage collector runs for a long time, it can cause the view to stutter and jump, making it difficult for the user's eyes and brain to track the motion. This can cause dizziness, headache, and other physical discomfort, making it difficult to use the simulator for an extended period of time.

Overall, there are many situations where long garbage collection pauses can be undesirable in a flight simulator, and it is important to address these issues to ensure that the simulator remains smooth and responsive at all times.

Over the years, Nasal has received criticism for its garbage collection implementation, as it has been linked to performance issues in FlightGear. However, this criticism ignores the fact that Nasal is just one part of the FlightGear system, and that other subsystems have also contributed to performance issues and resource leaks in the past.

The real issue is the way that subsystems are executed inside FlightGear, using a form of cooperative multitasking. This means that Nasal's mark/sweep garbage collector will inevitably be triggered at frame rate, which can cause performance issues and stuttering.

Rather than replacing Nasal entirely, a better solution would be to re-architect FlightGear to address these underlying issues. This would involve changing the way that subsystems are executed, potentially using a different approach to multitasking.

Understanding GC internals

Additionally, it would be beneficial to improve the garbage collection mechanism itself, to provide better diagnostics and metrics at runtime. This would allow end-users to more easily understand if certain issues are related to Nasal or its garbage collector, and to troubleshoot and debug performance problems more effectively.

In FlightGear, the Nasal scripting language is used to create scripts that can be run inside the simulator. These scripts are executed via callbacks that are triggered by timers and listeners, which can cause the garbage collector to be triggered in a non-deterministic fashion. This means that the garbage collector may run at different times and in different ways depending on the specific actions and events that are happening in the simulator.

This non-deterministic execution of the garbage collector can cause several challenges, including hard-to-reproduce issues that can be difficult to debug. For example, if a performance issue or bug only occurs when the garbage collector runs in a certain way, it may be difficult to reproduce the problem consistently and identify the cause. Additionally, the specific conditions under which the garbage collector runs can vary greatly for different end-users, depending on their local settings (such as the airport, aircraft, and environment) and the specific actions they take in the simulator. This can make it even more difficult to debug and diagnose problems related to the garbage collector.

Overall, the non-deterministic execution of the garbage collector in FlightGear can make it difficult to reproduce and debug issues related to its performance and behavior. This can be a challenge for script developers and end-users, and it may require careful use of profilers

Improving Nasal tooling would be a good idea because it would allow developers to more easily troubleshoot and debug issues in FlightGear. Nasal is integrated into FlightGear in such a way that problems can span multiple components of the simulator, making it difficult to understand and diagnose issues. By providing tools such as a profiler, debugger, and code optimizer, developers would be able to more easily identify and address issues. In addition, exposing garbage collector internals via properties would allow developers to gain a better understanding of how Nasal is working within FlightGear, and potentially provide a means of improving the efficiency of the scripting language. Overall, improving Nasal tooling would benefit FlightGear by making it easier for developers to identify and resolve issues, leading to a better user experience for those using the flight simulator.

There are several potential benefits to providing tooling that is integrated with FlightGear as a whole. One benefit is that it would allow developers to more easily reproduce and understand issues that can only be identified or properly analyzed when running inside the FlightGear environment. This is because the tooling would be able to access the full range of FlightGear's functionality and components, which would enable developers to more accurately diagnose and troubleshoot issues.

Another potential benefit of integrating tooling with FlightGear is that it would allow developers to more easily identify issues that span multiple architectural layers of FlightGear/SimGear. For example, if a problem is caused by interactions between the scripting layer and the property tree, having tooling that is integrated with FlightGear would allow developers to more easily analyze and understand these interactions. This would allow for more efficient and effective troubleshooting and debugging.

Frame Spacing and Latency

In a visual application like a flight simulator, the frame rate and frame latency are critical for providing a smooth and immersive experience for the end-user. In FlightGear, which uses the Nasal scripting language with a mark/sweep garbage collector, there is a potential for performance issues and stuttering due to the way the garbage collector is triggered and the way subsystems are updated.

One problem with using a mark/sweep garbage collector in a visual application is that it can be triggered at the frame rate. This means that if the garbage collector runs during a frame, it can cause a delay or stutter in the frame rate, which can be noticeable to the end-user. In a flight simulator, where the frame rate needs to be high and consistent in order to provide a realistic and smooth flying experience, this can be a significant problem.

Additionally, the way subsystems are updated in FlightGear, using a vector of subsystems that is traversed and updated each frame, can also cause performance issues. This approach is similar to cooperative multitasking, where each subsystem is given a chance to run and update before the next one is called. However, if one subsystem takes a long time to run (such as Nasal due to a long GC run), it can cause delays for the other subsystems, which can result in stuttering and other performance problems.

Overall, the use of a mark/sweep garbage collector in FlightGear, combined with the way subsystems are updated, can lead to performance issues and stuttering that can impact the overall flying experience for end-users. To avoid these problems, it may be necessary to optimize the garbage collector or use a different approach for managing memory and updating subsystems in FlightGear.

Garbage collection is a common approach to automatic memory management in programming languages. In a garbage collector, the runtime system automatically identifies which objects are no longer in use by the program and reclaims the memory used by those objects. This can help prevent memory leaks and make it easier for programmers to manage memory in their programs.

Motivation

Some potential benefits of fixing the mark/sweep garbage collector used by Nasal in FlightGear include:

• Improved performance: Generational and/or incremental garbage collection can help reduce the amount of work that the garbage collector needs to do, which can in turn improve overall performance by reducing the amount of time spent in garbage collection. This is especially important in a single-threaded application like FlightGear, where garbage collection pauses can result in stuttering and other performance issues.
• Improved resource management: By using a generational or incremental garbage collector, FlightGear can better manage its memory usage, which can help prevent the application from using up all available memory and crashing. This can also help reduce the amount of memory fragmentation, which can improve performance.
• Improved determinism: Because generational and/or incremental garbage collection is more predictable than mark/sweep garbage collection, it can make it easier to reproduce and diagnose performance issues in FlightGear. This can be especially useful for script developers who may need to debug their code and/or troubleshoot performance issues.

The benefits of updating the mark/sweep collector used in FlightGear include improved performance and responsiveness, especially during critical phases of a flight. By implementing a generational or incremental collector, long garbage collection pauses can be reduced or eliminated, resulting in a smoother and more responsive simulator. This can improve the user experience and make the simulator easier and more enjoyable to use.

Overall, updating the mark/sweep collector in FlightGear can provide significant benefits by improving performance, responsiveness, and user experience. This can make the simulator more enjoyable and easier to use, and can help to ensure that it remains a valuable and effective tool for pilots and aviation enthusiasts.

Updating the garbage collector used by Nasal in FlightGear offers several benefits compared to replacing the current scripting engine altogether.

First, FlightGear has a large and active user base, and over the years, hundreds of aircraft and thousands of scripts and addons have been developed by dozens of contributors.

These scripts and addons rely on the Nasal scripting engine and are used by many FlightGear users on a daily basis. If the scripting engine were to be replaced, it would require a significant effort to port all of these existing scripts and addons to the new engine, and this would likely take several years to complete. In contrast, updating the garbage collector is a much smaller and more focused effort, and it can be done without disrupting or breaking existing scripts and addons.

Second, the garbage collector is an entirely self-contained module of less than 350 lines of C code. In comparison to large-scale rewrites, this makes it relatively easy to understand and modify, compared to the larger and more complex Nasal scripting engine or a completely new scripting engine altogether. As a result, updating the garbage collector should be a relatively straightforward task, compared to the much larger effort required to replace the entire scripting engine.

The FlightGear project, being an open source project, faces constraints that make it difficult to undertake large-scale rewrites of critical components like the scripting engine. This is particularly true given the large number of existing scripts and addons used by hundreds of aircraft, which have been written by dozens of contributors over the course of two decades.

Third, in the past, the project has ambitiously attempted, and failed, to do large-scale rewrites in other areas, such as the HLA/RTI and QtQuick efforts (or even the OSG port that never got completed), which have either taken years to manifest or never materialized at all. As a result, it is often more effective to focus on updating and improving existing components, rather than attempting to rewrite them from scratch.

By focusing on updating the garbage collector, the FlightGear project can avoid repeating these mistakes and make significant improvements to the performance and usability of the simulator without undertaking a massive and risky overhaul of the scripting engine.

Reworking an existing mark/sweep collector to become generational or incremental is likely to be superior to integrating a new scripting language for several reasons. First, changing the garbage collector would involve modifying the existing code base, but the overall structure and organization of the code would remain the same. This means that the existing code and scripts could continue to function without requiring significant changes or porting.

In contrast, integrating a new scripting language would require significant changes to the code, as well as the creation of new interfaces and support for existing scripts. This would likely require a greater amount of time and manpower, as well as a higher level of expertise and familiarity with the new language.

Additionally, implementing a new scripting language would introduce compatibility and interoperability issues, as the existing code and scripts would need to be adapted to work with the new language. This could potentially lead to conflicts or errors, and would require careful testing and debugging to ensure that the existing code continues to function correctly.

On the other hand, reworking the garbage collector to be generational or incremental would likely provide significant performance benefits, as these types of collectors are generally more efficient and effective at managing memory. This could result in improved runtime performance and overall system stability, without requiring significant changes to the existing code base.

Overall, while both options would involve a significant amount of effort and expertise, reworking the existing garbage collector is likely to be the more practical and efficient choice, given the existing code base and the resources available.

Nasal in FlightGear

The mark/sweep collector is one type of garbage collector. It works by first "marking" all objects that are currently in use by the program, then "sweeping" through memory and reclaiming any objects that were not marked. This can help prevent memory leaks, but it can also cause performance issues because the mark/sweep process can be expensive in terms of computational time and can cause stuttering or non-deterministic behavior in the program.

In Nasal, arrays (vectors) and objects (also known as hashes) are implemented as a single reference, so they only count as one object for the purposes of garbage collection. This means that using arrays and objects can be efficient in terms of memory usage.

However, it is important to note that the efficiency of garbage collection depends on many factors, including the complexity of the data structures being used and the number of references that need to be searched during the mark/sweep process. If a script has a large number of complex data structures, it may still cause performance issues even if the individual objects only count as one reference each.

In terms of how loops and other control structures affect garbage collection, it is important to understand that garbage collection is a global process that cannot be restricted to a local context. When the garbage collector runs, it needs to search through all references in the program to identify which objects are no longer in use. This means that even if a particular loop or control structure does not use many references, it can still trigger the garbage collector to run and search through all references in the program.

memory management

In the programming language Nasal, variables do not point to garbage. Instead, the objects that they reference are garbage. This means that when the garbage collector runs, it only needs to search through the objects being pointed to by variables, rather than the variables themselves. Additionally, scalar values such as numbers are not treated as references in Nasal and are stored directly in the hash record, rather than being pointed to by a reference.

The "var" syntax in Nasal has no effect on allocation and is only used for scoping. This means that it defines a local variable within the current function, regardless of any outer scope it may be in.

There are several operations in Nasal that create heap blocks or garbage, including string composition with the "~" operator, vector creation with a "[...]" expression, hash creation with a "{...}" expression, function calls, and closure binding with a "func ..." expression. These operations can create objects that are eligible for garbage collection and should be used carefully to avoid performance issues.

Thus, the primary operations in Nasal that create heap blocks/garbage are:

• String composition with the "~" operator
• Vector creation with a "[...]" expression
• Hash creation with a "{...}" expression
• Function calls (which create a hash for the namespace)
• Closure binding with a "func ..." expression.

The garbage collector used by Nasal is a mark/sweep collector. It works by first "marking" all objects that are currently in use by the program, then "sweeping" through memory and reclaiming any objects that were not marked. This is done using the mark and reap functions.

The mark function takes a reference to an object and recursively searches through all references that are reachable from that object, marking each one as in use. The reap function is called for each object type, and it searches through all objects of that type to find and free any that were not marked by the mark function.

The garbage collection process is initiated by the garbageCollect function, which is called when the garbage collector is needed. This function first searches through all contexts in the program to mark all reachable objects, then it marks several global objects, and finally it calls the reap function for each object type to free any unreferenced objects.

The garbage collector is called from several places in the code, including the naModUnlock function, which is called when a thread releases its lock on the global data structures. The garbage collector needs to run exclusively, such as when it needs to free the list of dead blocks. In these cases, the bottleneck function is called to engage the "bottleneck" and block all other threads until the garbage collector has finished running.

mark/sweep GC

A mark/sweep garbage collector is a type of automatic memory management system that is commonly used in programming languages that lack built-in support for garbage collection. The basic idea behind a mark/sweep garbage collector is to periodically scan through the program's memory and identify any blocks of memory that are no longer being used by the program. These blocks of memory, known as garbage, are then freed up for use by the program.

The mark/sweep garbage collector works in two phases: the mark phase and the sweep phase. In the mark phase, the garbage collector identifies which blocks of memory are currently in use by the program. This is typically done by starting at the root objects in the program and then traversing the object graph to identify all of the objects that are reachable from the root objects. Any objects that are not reachable from the root objects are considered garbage and are eligible for collection.

In the sweep phase, the garbage collector then frees up the memory that was identified as garbage in the mark phase. This typically involves iterating through all of the blocks of memory in the program and freeing up any blocks that were marked as garbage.

As for type specific memory pools, these are pools of memory that are dedicated to holding objects of a specific type. For example, a memory pool for scalars would only hold objects that are scalars, such as integers or floating-point numbers. Similarly, a memory pool for vectors would only hold objects that are vectors, such as arrays or lists. By using type specific memory pools, the garbage collector can more efficiently manage memory, as it knows exactly what type of objects are being stored in each pool and can tailor its collection strategies accordingly.

threaded GC

Note  need to document previous efforts here, i.e. by AndersG, ThorstenB, James and Richard

generational GC

A generational garbage collector is another approach that can help improve performance. It works by dividing objects into different "generations" based on how long they have been in use. New objects are placed in the youngest generation, and as the program runs, objects that survive multiple garbage collection cycles are promoted to older generations. Because younger generations are more likely to contain objects that are no longer in use, the garbage collector can focus its efforts on those generations and avoid spending time on older objects that are less likely to be garbage. This can help make the garbage collection process more efficient.

A generational garbage collector is a type of garbage collector that divides objects in a program's memory into different generations based on how long they have been in use. The idea behind a generational garbage collector is that most objects in a program's memory are short-lived, meaning they are created and then quickly become garbage. Because of this, it is more efficient to focus the garbage collection efforts on the objects in the youngest generation, as these are the most likely to be garbage.

To implement a generational garbage collector using a mark/sweep collector, we can divide the memory pools into different generations, with each generation representing objects of a certain age. For example, the youngest generation could contain objects that have been in use for less than a certain amount of time, while the oldest generation could contain objects that have been in use for a longer amount of time.

When the garbage collector runs, it first focuses on collecting garbage from the youngest generation. If there is still memory available in this generation, the garbage collector moves on to the next oldest generation and collects garbage from there. This continues until all generations have been collected, or until the amount of free memory reaches a certain threshold.

By focusing on the youngest generation first, the garbage collector can quickly free up memory that is likely to be garbage, without having to spend as much time scanning through the entire program's memory. This can improve the performance of the garbage collector and make it more efficient.

One way to implement type-specific memory pools for a generational garbage collector is to have a separate memory pool for each type and generation. For example, we could have a memory pool for scalars in the youngest generation, a separate memory pool for scalars in the next oldest generation, and so on. This allows the garbage collector to easily collect garbage from each generation and type without having to scan through the entire program's memory.

Adding generations to a mark/sweep garbage collector can greatly improve its performance. Most objects in a program's memory are short-lived, so by focusing the garbage collection efforts on the youngest generation, the garbage collector can quickly free up memory that is likely to be garbage. This can reduce the amount of time the garbage collector spends scanning through the entire program's memory and improve its overall performance.

Additionally, by using a generational garbage collector, you can reduce the impact of long-lived objects on the garbage collector's performance. In a traditional mark/sweep garbage collector, long-lived objects can cause the garbage collector to spend a significant amount of time scanning through the entire program's memory, even if most of the objects in memory are short-lived and eligible for collection. With a generational garbage collector, long-lived objects are only scanned during the initial collection of the youngest generation, after which they are moved to older generations and are not scanned as frequently. This can further improve the performance of the garbage collector and reduce its impact on the program's overall performance.

Allocating objects into generations and only mark/sweeping the youngest generation on most iterations is a simple and effective optimization for a mark/sweep garbage collector. By focusing on the youngest generation, the garbage collector can quickly free up memory that is likely to be garbage, without having to spend as much time scanning through the entire program's memory. This can improve the performance of the garbage collector and make it more efficient.

Additionally, by only mark/sweeping the youngest generation on most iterations, the garbage collector can reduce the impact of long-lived objects on its performance. In a traditional mark/sweep garbage collector, long-lived objects can cause the garbage collector to spend a significant amount of time scanning through the entire program's memory, even if most of the objects in memory are short-lived and eligible for collection. With a generational garbage collector, long-lived objects are only scanned during the initial collection of the youngest generation, after which they are moved to older generations and are not scanned as frequently. This can further improve the performance of the garbage collector and reduce its impact on the program's overall performance.

Heuristics

There are several heuristics that can be used to determine if an existing mark/sweep garbage collector (GC) has been successfully ported to a generational GC scheme.

• Self-checks: These are checks that can be performed by the GC itself to ensure that it is functioning correctly. Some examples of self-checks include:
  • Checking the number of pools in use: A generational GC typically divides the heap into multiple pools based on the age of the objects contained within them. The GC can check that the expected number of pools is being used.
  • Checking the number of objects and references in use: The GC can track the number of objects and references that are currently being used and ensure that this number is within expected limits.
  • Tracking memory allocations and deallocations: The GC can track the number of memory allocations and deallocations that are occurring within each pool and ensure that this number is within expected limits.

There are some additional heuristics that can be used to detect if a generational GC is working properly:

1. Age distribution of objects: The GC can track the age distribution of the objects in the heap and ensure that they are being properly divided into the different generations. This can help to ensure that the GC is correctly identifying which objects are likely to be short-lived and which are likely to be long-lived.
2. Collection frequency: The GC can track the frequency at which collections are being performed on each generation and ensure that this frequency is appropriate. For example, it may be appropriate to perform collections more frequently on the younger generations, since objects in these generations are more likely to be short-lived.
3. Promotion rate: The GC can track the rate at which objects are being promoted from one generation to the next and ensure that this rate is within expected limits. This can help to ensure that the GC is correctly identifying which objects are likely to be long-lived and promoting them to higher generations.
4. Throughput and pause time: As mentioned previously, the GC can track its throughput and pause time to ensure that it is functioning efficiently. However, it may also be useful to track these metrics separately for each generation to ensure that the GC is functioning optimally within each generation.
5. Memory usage: The GC can track the amount of memory being used by each generation and ensure that it is within expected limits. This can help to ensure that the GC is not allowing any single generation to consume too much memory.
6. Fragmentation: The GC can track the level of fragmentation in the heap and ensure that it is within acceptable limits. High levels of fragmentation can cause performance issues, so it is important to ensure that the GC is keeping fragmentation under control.

incremental GC

an incremental garbage collector can help improve performance by spreading out the work of garbage collection over multiple small increments rather than performing it all at once. This can help prevent stuttering and make the garbage collection process more deterministic.

The developer of Nasal, Andy Ross, originally considered implementing an incremental garbage collection scheme in Nasal. The idea was to perform garbage collection normally, but to check timestamps periodically and interrupt the garbage collection process if it exceeded a certain threshold (then longjmp() out of it past some threshold, leaving the intermediate sweep stuff in place.). This would allow the garbage collector to continue its work in the background, rather than blocking the program until it had finished.

However, implementing an incremental garbage collection scheme in Nasal would require additional steps to ensure that all objects are properly collected. For example, it would be necessary to track mutated reference-storing objects in a separate list so that they can be swept again. Additionally, a heuristic would be needed to determine when it is safe to restart the sweep and continue garbage collection.

Overall, implementing an incremental garbage collection scheme in Nasal would be a complex undertaking that would require careful design and implementation. It is not clear whether the benefits of an incremental garbage collection scheme would outweigh the additional complexity and overhead that it would introduce.

the current Nasal GC implementation does not include a maximum delay and restart facility. If it did, that would entirely satisfy the current performance/stuttering issues.

One idea discussed on the mailing list was adding timestamps to the data blocks and by making sure new blocks are inserted at the beginning of the linked list is would be easy to do something like this for the garbage collector:

• process the linked list every second up to the point that timestamps get older than 8 seconds.
• process blocks that are older than 8 second and less than 1 minute every minute.
• treat blocks that are older than 1 minute as semi-permanent and only process them incrementally with (say) 16 blocks at a time.

It might spread the load a little that way.

concurrent GC

running the garbage collector in a separate thread can be an effective way to improve its performance, especially in a program like FlightGear that does not use multiple cores effectively. By running the garbage collector in a separate thread, you can offload its work to a different CPU core and reduce the impact of garbage collection on the program's overall performance.

One way to do this is to identify times during processing a new frame when no Nasal code is being run but something else is time-consuming, such as rendering graphics. This could be the perfect opportunity to run the garbage collector in a separate thread, as the main thread would be busy with other work and would not be impacted by the garbage collector's latency.

To ensure that the garbage collector is not running at the same time as Nasal execution, you could use a single condition variable to coordinate between the two threads. This condition variable could be used to signal when it is safe to run the garbage collector, and to prevent the garbage collector from running while Nasal code is being executed. By using a condition variable in this way, you can effectively coordinate between the two threads and ensure that the garbage collector is not impacting the program's overall performance.

there is still the issue of not being able to execute Nasal code while the garbage collector is running. In order to fully address this issue, you would need to implement a concurrent garbage collector, which is a type of garbage collector that can run concurrently with the program and perform garbage collection without stopping the program's execution.

A concurrent garbage collector is typically more complex to implement than a traditional mark/sweep garbage collector, as it needs to be designed in a way that allows it to run concurrently with the program without interfering with the program's execution. This can involve using sophisticated synchronization mechanisms, such as atomic operations and lock-free data structures, to coordinate between the garbage collector and the program.

In the case of FlightGear, implementing a concurrent garbage collector would likely be a significant undertaking and would require a deep understanding of the program's internal workings and how it interacts with Nasal code. It would also require careful design and testing to ensure that the garbage collector does not interfere with the program's execution or cause any performance issues.

Therefore, while running the garbage collector in a separate thread can improve its performance and reduce its impact on the program, it may not completely eliminate the issue of not being able to execute Nasal code while the garbage collector is running. In order to fully address this issue, a concurrent garbage collector would need to be implemented (or rather, an existing one, being integrated).

Foo

Coccinelle (spatch): patch

this is experimental code / just kept here for future reference

@@
enum { NUM_NASAL_TYPES };
struct naPool {
  //...
};
struct Block {
  //...
};
struct Context {
  //...
  int ntemps;
  naRef* temps;
};

@@

// Introduce a new enum to track the different generations in the generational GC
@@
enum { GEN0, GEN1, GEN2, GEN_MAX };

@@

// Extend the naPool structure to track the current generation for each pool
@@
struct naPool {
  //...
  int generation;
};

@@

// Update the globals->pools array to be an array of generations, with each generation containing an array of pools of different types
@@
struct GlobalContext {
  //...
  struct naPool pools[GEN_MAX][NUM_NASAL_TYPES];
};

@@

// Update the naRef structure to track the number of GC survivals for each object
@@
struct naRef {
  //...
  int gcSurvivals;
};

@@

// Update the mark() function to increment the number of GC survivals for each object
@@
static void mark(naRef r)
{
  //...
  ++r.gcSurvivals;
}

@@

References

• Hackathon Proposal:Nasal GC Inspection
• How the Nasal GC works

References