Efficient continuation stack storage in languages with a garbage collector

Techniques for efficient continuation stack storage are disclosed. In some embodiments, when a continuation yields, the continuation stack, or portion thereof, is copied from a thread stack to a data object, referred to herein as a chunk, allocated from memory. The copied stack portion may maintain the same representation in the chunk as on the thread stack to minimize processing overhead of the operation. When the continuation resumes, the continuation stack, or some portion thereof, is copied from the chunk to the thread stack. During execution, the continuation stack that was copied may be modified on the thread stack. When the continuation yields again, the runtime environment may determine, based at least in part on whether the first object in memory is subject to a garbage collection barrier, whether to copy the modified portion of the continuation stack to the existing chunk or to allocate a new chunk.

TECHNICAL FIELD

The present disclosure relates, generally, to memory management in computing applications. In particular, the present disclosure relates to techniques for efficiently storing continuation stacks in garbage collection-enabled runtime environments.

BACKGROUND

Delimited continuations are a programming construct through which slices of an execution context for a program are captured. An example delimited continuation is a continuation stack, which stores a representation of an execution stack for a given thread of execution. Application runtime environments may mount and yield continuation stacks to switch between different tasks. When a continuation stack is mounted, the captured execution stack is loaded and executed. When the continuation stack is yielded, execution is suspended, and the current state of the execution stack is saved. Delimited continuations may be used for lightweight concurrent programming, allowing a runtime environment to run several more tasks in parallel than available physical processing cores.

Continuation stack management presents some challenges particular to programming languages with garbage collection (GC). GC-enabled runtime environments typically perform a stop-the-world (STW) pause to track the position of pointers on execution stacks. A STW pause prevents the pointers from being modified while the execution stacks are being scanned. When the number of execution stacks is relatively low, an STW pause may be performed quickly with negligible impact on application runtime performance. However, execution stacks captured by delimited continuations are generally managed separately from the thread stacks provided natively by the operating system (OS), meaning the number of runtime-managed, execution stacks may be much greater than the number of native OS threads. As a result, an STW pause may noticeably degrade runtime performance.

DETAILED DESCRIPTION

In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding. One or more embodiments may be practiced without these specific details. Features described in one embodiment may be combined with features described in a different embodiment. In some examples, well-known structures and devices are described with reference to a block diagram form in order to avoid unnecessarily obscuring the present invention.1. General Overview2. RUNTIME ENVIRONMENTS2.1 ARCHITECTURAL OVERVIEW2.2 EXAMPLE VIRTUAL MACHINE ARCHITECTURE3. CONTINUATION CHUNKS3.1 YIELDING CONTINUATIONS AND CHUNK MANAGEMENT3.2 RESUMING CONTINUATIONS FROM STORED CHUNKS3.3 PROMOTING CHUNKS3.4 AGE-NEUTRAL CHUNK MANAGEMENT4. GARBAGE COLLECTION INVOLVING CONTINUATION CHUNKS5. COMPUTER NETWORKS AND CLOUD NETWORKS6. HARDWARE IMPLEMENTATIONS7. MISCELLANEOUS; EXTENSIONS

1. General Overview

Techniques are described herein for efficient continuation stack storage and management in languages with garbage collection. One approach for mitigating the impact of an STW pause in the presence of a large number of continuation stacks is to translate the representation of the execution stack into one that may be scanned by a garbage collector while the program is still running. According to this approach, prior to suspension of a continuation, the thread stack used by the continuation is scanned to extract pointers for the current execution context. The pointers may then be stored in a data structure, such as a pointer array, which allows the garbage collector to quickly identify the pointers in the suspended execution stacks without performing an STW pause. Thus, the garbage collector may limit the scan to execution stacks of currently mounted continuations during an STW pause, greatly reducing the performance impact incurred from stopping program execution during GC operations. However, a tradeoff with this approach is that switching times between different continuation stacks may be negatively impacted due to the cost of translating the execution stack representation each time a continuation is yielded.

Techniques described herein allow for GC-enabled runtime environments to avoid translation costs associated with changing the representation of suspended continuation stacks without requiring an STW pause to track the position of pointers across all continuation stacks. Thus, the techniques allow for fast switching between continuation stacks with low negative impact on GC operations.

In some embodiments, continuation stacks are stored in data objects, referred to herein as chunks. During a continuation's execution, the corresponding continuation stack may make use of a native operating system thread stack. When a continuation first yields, the execution stack, or a portion thereof, that resides on the thread stack is copied to an allocated chunk and removed from the thread stack. The chunk may store the continuation stack or portion thereof in the same representation that it has on the thread stack, thereby avoiding processing overhead associated with translating the execution stack to a different structured representation.

When a continuation is mounted, the continuation stack or portion thereof may also be directly copied from a chunk to the thread stack without any translation costs. As execution of the continuation resumes, the continuation stack may be modified. When the continuation yields again, the runtime environment may determine whether to copy the modified stack or some portion thereof back to the chunk based at least in part on whether the chunk is subject to a garbage collection barrier. If the chunk is in an area of memory that is not subject to a GC barrier and there is room for the modified stack portion, then the stack portion may be copied into the chunk, thereby mutating the chunk. If the chunk is in an area of memory that is subject to a GC barrier or does not have sufficient room, then the runtime environment may allocate a new chunk into which the updated stack portion is copied.

In some embodiments, chunks are subject to garbage collection barriers based at least in part on their age. Concurrent and generational garbage collectors generally do not require any GC barriers for newly allocated data objects since the majority of data objects tend to be short-lived. These objects may be allocated within a region of memory sometimes referred to as the young generation. The oldest objects in this region of memory that are still live may then be promoted and/or moved to another memory region, referred to as the tenured generation. Once promoted, the positions of pointers within the chunk are frozen. Existing pointers within the chunk may be deleted from the chunk when frozen; however, a GC write barrier may prevent attempts to overwrite the pointers with other datatypes or otherwise move the position of the pointers. The write barrier may be strictly applied to chunks that have aged out of the young generation. Thus, pointers within the young generation are not subject to the write barrier and may be overwritten or otherwise mutated.

During a GC-triggered STW pause, the runtime environment may limit scanning of continuation stacks to chunks that reside in memory area(s) that are not subject to GC barriers and stack portions copied to the thread stack. Concurrent and generational garbage collectors generally do not require any GC barriers for newly allocated data objects and scan these objects during an STW pause. Therefore, tracking the position of pointers for young chunks during an STW pause may be done with little or no performance impact. Scanning of promoted, aged-out chunks or chunks in memory areas that are otherwise not subject to any GC barriers may be performed outside of an STW pause as the program is executing since the position of the pointers in these chunks is frozen. Thus, the number of continuation stacks that are scanned for a given STW pause may be significantly reduced.

2.1 Architectural Overview

In some embodiments, the techniques described herein for allocating and managing chunks are executed within a runtime environment. A runtime environment in this context may include supporting code, tools and/or other hardware/software components that implement a program's execution. One or more components of the runtime environment may vary depending on the programming language of the program's source code, the hardware platform on which the program is executed, the operating system version, and/or other system attributes.

FIG.1illustrates an example computing architecture in which techniques described herein may be practiced. Software and/or hardware components described with relation to the example architecture may be omitted or associated with a different set of functionality than described herein. Software and/or hardware components, not described herein, may be used within an environment in accordance with some embodiments. Accordingly, the example environment should not be constructed as limiting the scope of any of the claims.

As illustrated inFIG.1, computing architecture100includes source code files101which are compiled by compiler102into blueprints representing the program to be executed. Examples of the blueprints include class files103, which may be loaded and executed by execution platform112. Execution platform112includes runtime environment113, operating system111, and one or more application programming interfaces (APIs)110that enable communication between runtime environment113and operating system111. Runtime environment113includes virtual machine104comprising various components, such as memory manager105(which may include a garbage collector), class file verifier106to check the validity of class files103, class loader107to locate and build in-memory representations of classes, interpreter108for executing virtual machine code, and just-in-time (JIT) compiler109for producing optimized machine-level code.

In some embodiments, computing architecture100includes source code files101that contain code written in a particular programming language, such as Java, C, C++, C#, Ruby, Perl, and so forth. Thus, source code files101adhere to a particular set of syntactic and/or semantic rules for the associated language. For example, code written in Java adheres to the Java Language Specification. However, since specifications are updated and revised over time, source code files101may be associated with a version number indicating the revision of the specification to which source code files101adhere. One or more of source code files101may be written in a programming language supported by automatic garbage collection.

In various embodiments, compiler102converts the source code, which is written according to a specification directed to the convenience of the programmer, to either machine or object code, which is executable directly by the particular machine environment, or an intermediate representation (“virtual machine code/instructions”), such as bytecode, which is executable by virtual machine104that is capable of running on top of a variety of particular machine environments. The virtual machine instructions are executable by virtual machine104in a more direct and efficient manner than the source code. Converting source code to virtual machine instructions includes mapping source code functionality from the language to virtual machine functionality that utilizes underlying resources, such as data structures. Often, functionality that is presented in simple terms via source code by the programmer is converted into more complex steps that map more directly to the instruction set supported by the underlying hardware on which virtual machine104resides.

In some embodiments, virtual machine104includes interpreter108and a JIT compiler109(or a component implementing aspects of both), and executes programs using a combination of interpreted and compiled techniques. For example, virtual machine104may initially begin by interpreting the virtual machine instructions representing the program via the interpreter108while tracking statistics related to program behavior, such as how often different sections or blocks of code are executed by virtual machine104. Once a block of code surpass a threshold (is “hot”), virtual machine104may invoke JIT compiler109to perform an analysis of the block and generate optimized machine-level instructions which replaces the “hot” block of code for future executions. Since programs tend to spend most time executing a small portion of overall code, compiling just the “hot” portions of the program can provide similar performance to fully compiled code, but without the start-up penalty. Furthermore, although the optimization analysis is constrained to the “hot” block being replaced, there still exists far greater optimization potential than converting each instruction individually. There are a number of variations on the above described example, such as tiered compiling.

In other embodiments, runtime environment113may not include a virtual machine. For example, some static and stack-based environments do not execute programs using a virtual machine. A runtime environment may include supporting code, tools and/or other hardware/software components that implement a given program's execution. One or more components of the runtime environment may vary depending on the programming language of the source code, the hardware platform on which the program is executed, and/or the operating system version.

Source code files101have been illustrated as the “top level” representation of the program to be executed by execution platform111. Although computing architecture100depicts source code files101as a “top level” program representation, in other embodiments source code files101may be an intermediate representation received via a “higher level” compiler that processed code files in a different language into the language of source code files101.

In some embodiments, compiler102receives as input the source code files101and converts the source code files101into class files103that are in a format expected by virtual machine104. For example, in the context of the JVM, the Java Virtual Machine Specification defines a particular class file format to which class files103are expected to adhere. In some embodiments, class files103contain the virtual machine instructions that have been converted from source code files101. However, in other embodiments, class files103may contain other structures as well, such as tables identifying constant values and/or metadata related to various structures (classes, fields, methods, and so forth).

2.2 Example Virtual Machine Architecture

FIG.2illustrates example virtual machine memory layout200according to some embodiments. Virtual machine104may adhere to the virtual machine memory layout200depicted inFIG.2. In other embodiments, the memory layout of virtual machine104may vary, such as by including additional components and/or omitting one or more of the depicted components, depending on the runtime environment. Although components of the virtual machine memory layout200may be referred to as memory “areas”, there is no requirement that the memory areas are physically contiguous.

In the example illustrated byFIG.2, virtual machine memory layout200is divided into shared area201and thread area209. Shared area201represents an area in memory where structures shared among the various threads executing on virtual machine104are stored. Shared area201includes heap202and per-class area205.

Heap202represents an area of memory allocated on behalf of a program during execution of the program. In some embodiments, heap202includes young generation203and tenured generation204. Young generation203may correspond to regions of the heap that stores newly created objects during program execution. When young generation203is filled, the oldest objects are promoted to tenured generation204to free up space for new objects in young generation203. Promoting an object may comprise moving to a different region and/or reclassifying the data objects.

Separate treatment of different generations of objects may facilitate generational garbage collection. Generally, most objects have a short lifecycle during program execution. Thus, performing garbage collection more frequently on objects stored in young generation203may optimize the amount of space that may be reclaimed for a given scan. Continuation chunks may also be processed differently based on the generation where the chunk is stored. Although only two generations are depicted, in other embodiments, heap202may include other age-related generations, such as a permanent generation.

In some embodiments, young generation203is not subject to any GC barriers. Stated another way, the garbage collector does not restrict objects within this region of memory from being mutated. In contrast, GC barriers may be applied to tenured generation204to maintain the position of pointers within the data objects. In addition or as an alternative to young generation203and tenured generation204, heap202may organize data objects into other memory areas in a manner that is not age-based. For example, data objects may be stored in different regions based on datatype, size, and/or other object attributes. Some regions that are not age-based may be subject to GC barriers while other regions may not be subject to GC barriers. Thus, the in-memory organization of data objects may vary depending on the implementation.

Per-class area205represents the memory area where the data pertaining to the individual classes are stored. In some embodiments, per-class area205includes, for each loaded class, run-time constant pool206representing data from a constant table of the class, field and method data207(for example, to hold the static fields of the class), and the method code208representing the virtual machine instructions for methods of the class.

Thread area209represents a memory area where structures specific to individual threads are stored. InFIG.2, thread area209includes thread structures210and thread structures213, representing the per-thread structures utilized by different threads. In order to provide clear examples, thread area209depicted inFIG.2assumes two threads are executing on the virtual machine104. However, in a practical environment, virtual machine104may execute any arbitrary number of threads, with the number of thread structures scaled accordingly.

In some embodiments, program counter211and program counter214store the current address of the virtual machine instruction being executed by their respective threads. Thus, as a thread steps through the instructions, the program counters are updated to maintain an index to the current instruction.

In some embodiments, thread stack212and thread stack215each store stack frames for their respective threads, where each stack frame holds local variables for a function. A frame is a data structure that may be used to store data and partial results, return values for methods, and/or perform dynamic linking. A new frame is created each time a method is invoked. A frame is destroyed when the method that caused the frame to be generated completes. Thus, when a thread performs a method invocation, virtual machine104generates a new frame and pushes the frame onto the virtual machine stack associated with the thread.

When a method invocation completes, virtual machine104passes back the result of the method invocation to the previous frame and pops the current frame off of the stack. In some embodiments, for a given thread, one frame is active at any point. This active frame is referred to as the current frame, the method that caused generation of the current frame is referred to as the current method, and the class to which the current method belongs is referred to as the current class.

Thread stack212and thread stack215may correspond to native operating system stacks or virtual thread stacks. Generally, the number of virtual threads and continuations executing on a machine is much greater than the number of native threads. Continuations are generally much lighter weight and require less compute-intensive operations than native threads, as the continuations may leverage the native thread structures when mounted and executed.

FIG.3illustrates an example frame layout according to some embodiments. In some embodiments, frames of a thread stack, such as thread stack212and thread stack215adhere to the structure of frame300.

In some embodiments, frame300includes local variables301, operand stack302, and run-time constant pool reference table303. In some embodiments, local variables301are represented as an array of variables that each hold a value, for example, boolean, byte, char, short, int, float, or reference. Further, some value types, such as longs or doubles, may be represented by more than one entry in the array. The local variables301are used to pass parameters on method invocations and store partial results. For example, when generating the frame300in response to invoking a method, the parameters may be stored in predefined positions within the local variables301, such as indexes 1-N corresponding to the first to Nth parameters in the invocation. The parameters may include pointers and other references.

In some embodiments, the operand stack302is empty by default when the frame300is created by the virtual machine104. The virtual machine104then supplies instructions from the method code208of the current method to load constants or values from the local variables301onto the operand stack302. Other instructions take operands from the operand stack302, operate on them, and push the result back onto the operand stack302. Furthermore, the operand stack302is used to prepare parameters to be passed to methods and to receive method results. For example, the parameters of the method being invoked could be pushed onto the operand stack302prior to issuing the invocation to the method. The virtual machine104then generates a e111new frame for the method invocation where the operands on the operand stack302of the previous frame are popped and loaded into the local variables301of the new frame. When the invoked method terminates, the new frame is popped from the virtual machine stack and the return value is pushed onto the operand stack302of the previous frame.

In some embodiments, run-time constant pool reference table303contains a reference to the run-time constant pool of the current class (e.g., runtime constant pool206). Run-time constant pool reference table303is used to support resolution. Resolution is the process whereby symbolic references in the constant pool are translated into concrete memory addresses, loading classes to resolve as-yet-undefined symbols and translating variable accesses into appropriate offsets into storage structures associated with the run-time location of these variables.

3.1 Yielding Continuations and Chunk Management

During application runtime, continuations may be mounted to native threads and yielded at various points in time. A scheduler or some other programmatic means may be used to select which continuations are mounted and which continuations are yielded. At a given moment, multiple continuations may be mounted to different threads stacks and executed concurrently by different central processing unit (CPU) cores, while another set of continuations are in a suspended state. In some cases, the number of continuations that have been yielded may be much larger than the currently mounted continuations.

When a continuation yields, runtime environment113may capture the execution context associated with the continuation such that the continuation may be resumed at a later time. The execution context includes the execution stack for the continuation, also referred to herein as the continuation stack. At the moment a yield is initiated, all or a portion of the continuation stack may reside on a native thread stack for the thread to which the continuation is mounted. The continuation stack or portion thereof that is on the thread stack may be stored in one or more chunk data objects, which may be managed based in part on age, as described further herein. The continuation stack or portion thereof may then be removed from the thread stack to allow the thread to be used by other continuations or jobs.

FIG.4illustrates an example set of operations for chunk management upon a continuation yield in accordance with some embodiments. One or more operations illustrated inFIG.4may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.4should not be construed as limiting the scope of one or more embodiments.

Referring toFIG.4, runtime environment113executes a continuation, updating frames on the thread stack (operation402). For example, a new frame may be created when method code in a continuation is invoked and destroyed when the method code that caused the frame to be generated completes. Method code within the continuation may further update local variables (e.g., local pointers, arrays, and/or other datatypes) and/or other data within a stack frame. Thus, during continuation execution, one or more frames of the continuation stack may be pushed, popped, and/or mutated.

Runtime environment113next suspends execution of the continuation (operation404). Suspension may be triggered at a scheduled time, at a certain point in the execution of the continuation code, to make the thread available for a higher priority job, or based on some other event.

Once execution is suspended, runtime environment113determines whether a chunk has been allocated for the continuation (operation406). The first time a continuation yields, there may be no existing chunks for the continuation. In this case, runtime environment allocates a new chunk for the continuation from heap202(operation410). The size of a chunk may vary depending on the particular implementation.

If the continuation has previously yielded and been remounted, then one or more chunks may already exist for the continuation. In this case, runtime environment113determines whether the most recently allocated chunk for the continuation is full or has been promoted from young generation203(operation408).

If the chunk is full or has aged out of young generation203, then runtime environment113allocates a new chunk for the continuation from heap202(operation410). The new chunk may be allocated even if an aged-out chunk is not full as write barriers may prevent the aged-out chunk from being mutated. In some embodiments, new chunks are allocated within young generation203and not subject to the same write barriers as the aged-out chunks.

When a new chunk is allocated, runtime environment113copies one or more frames from the thread stack to the new chunk (operation412). In some embodiments, the frames are directly copied, maintaining the same data structure of the frames as they exist on the thread stack. By maintaining the same representation, processing overhead incurred from translating the frames to a new representation may be avoided. In particular, the copying may be done without extracting pointers from the frames and placing the pointers in a pointer array.

In the case where there is an existing continuation chunk that is not full and has not aged out of young generation203, runtime environment113copies the one or more frames from the thread stack to the existing chunk, thereby mutating the existing chunk (operation414). In some cases, the position of pointers and/or other local variables may be moved to a different location within the frame. In other cases, the pointers within the frame may be overwritten or deleted. Additionally or alternatively, one or more frames may have been added (pushed) and/or removed (popped) from the continuation stack. Thus, the mutated version of the chunk may store a different set of frames and the composition/shape of individual frames may vary from the previous version of the chunk.

Once the one or more frames have been copied from the thread stack to the chunk, runtime environment113removes these frames from the thread stack (operation416). The thread stack may then be used to execute a different continuation or pick up another job.

FIG.5illustrates an example memory layout upon a continuation yield in accordance with some embodiments. In the example illustrated, thread stack212stores a set of frames that have been pushed during execution of a continuation. At the top of the stack, run500and enter501indicate that the continuation has started execution. In the present example, three frames (frame502A, frame502B, and frame502C) are stored on thread stack212. For example, during execution, function A may call function B, which calls function C. The invocation of each function cause frame502A, frame502B, and frame502C, respectively, to be pushed to thread stack212. The continuation is then suspended as indicated by yield503and freeze504.

Once suspended, frame502A, frame502B, and frame502C are copied to chunk505, which is allocated from young generation203in heap202. Chunk506has been promoted to tenured generation204and stores frame507A, frame507B, and frame507C, which may be for the same or a different continuation. Although only one chunk is depicted for each of young generation203and tenured generation204, there may be several chunks in each region of memory.

3.2 Resuming Continuations from Stored Chunks

In some embodiments, the chunks that are stored for a given continuation are used to resume execution of the continuation.FIG.6illustrates an example set of operations for resuming execution of a continuation in accordance with some embodiments. One or more operations illustrated inFIG.6may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.6should not be construed as limiting the scope of one or more embodiments.

Referring toFIG.6, runtime environment113identifies a continuation to mount (operation602). As previously mentioned, a scheduler may be used to control when continuations are mounted and yielded. In some embodiments, runtime environment113may suspend another continuation per the operations described inFIG.4to free up a thread for a continuation that is scheduled for execution.

Runtime environment113further identifies one or more chunks mapped to the continuation (operation604). In some embodiments, the scheduler maintains a mapping between continuations and chunks. For example, the mapping may include a list of continuation identifiers. Each continuation identifier may be linked or otherwise associated with one or more chunk identifiers, which may be a pointer to a memory location, such as the starting address, where the chunk is stored in heap202.

In some embodiments, runtime environment113identifies the most recently allocated chunk for the continuation during operation604. The most recently allocated chunk generally includes frames from the most recently invoked methods within the continuation code. Other continuation chunks may be ignored since the entire continuation stack does not need to be copied to the thread stack to resume execution. Thus, chunk processing may be reduced to a subset of one or more of the most recent chunks that have been allocated for the continuation.

Runtime environment113next copies one or more frames from one or more of the identified continuation chunks to the thread stack (operation606). For example, referring toFIG.5, frame502A, frame502B, and frame502C may be copied back to thread stack212to resume execution of the continuation. In other cases, only a subset of the frames within a chunk may be copied back. For instance, only frame502C, or only frame502B and frame502C may be copied back to thread stack212from chunk505.

Referring again toFIG.6, runtime environment113further resumes execution of the continuation, updating frames on the thread stack (operation608). Frames on the thread stack may be added, removed, and/or mutated depending on the continuation code that is executed. In some cases, runtime environment113may load more frames onto the thread stack from one or more chunks during continuation runtime. For example, if only frame502C has been loaded, and the frame is popped during execution, then runtime environment113may copy frame502B to the thread stack. The method that caused the creation of frame502B may then call another method, pushing a new frame onto the stack. Thus, continuation stack may change significantly as a continuation is executed.

Once the continuation yields again, runtime environment113may execute the set of operations depicted inFIG.4. Thus, the updated set of frames or some portion thereof may be copied to a newly allocated chunk and/or an existing chunk in younger generation203, potentially mutating the existing chunk.

In some embodiments, chunks are promoted from young generation203based at least in part on age. Once a chunk has been aged out, the position of the pointers within the chunk may be frozen, preserving the shape of the chunk, which allows garbage collection to be run on the chunks outside of an STW pause.

FIG.7illustrates an example set of operations for promoting a chunk in accordance with some embodiments. One or more operations illustrated inFIG.7may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.7should not be construed as limiting the scope of one or more embodiments.

Referring toFIG.7, runtime environment113detects memory pressure on young generation203(operation702). Memory pressure may exist when the amount of available space is less than a threshold or, conversely, when the amount of consumed space exceeds a threshold. The amount of memory allocated for young generation203and the thresholds for aging out objects may vary depending on the particular implementation.

Responsive to detecting the memory pressure, runtime environment113identifies one or more objects to promote based on age (operation704). For example, runtime environment113may identify the top n oldest chunks or any chunks that are older than a threshold age. Each chunk may be associated with a timestamp that indicates the age of the chunk. Runtime environment113may scan the timestamps to identify the oldest chunks in younger generation203.

Runtime environment113next moves the identified one or more chunks to tenured generation204(operation706). In some embodiments, the one or more chunks may be physically moved to a different region in memory. In other embodiments, moving the chunks to tenured region204does not physically move the chunks but rather reclassifies the chunks. For example, chunk metadata may be updated to indicate that the chunk is no longer part of young generation203.

Runtime environment113further enforces write barriers on the aged-out chunks to preserve the position of pointers within the stack frames stored in the chunk (operation708). A write barrier may be implemented as a GC barrier, which comprises code that programmatically enforces the write constraints. For example, the barrier may be emitted before every move of a chunk to tenured generation204to ensure that the position of the pointers is maintained within the chunk.

It is noted that frames within a chunk that has aged out of young generation203may be copied to a thread stack and thereby mutated. In this case, the mutated frames may be copied to a newly allocated chunk or a different chunk in young generation203. Pointers may be deleted from a chunk in tenured generation204; however, the position of the pointers may still be maintained.

In some embodiments, chunks that are promoted may be translated into a representation that may be more quickly processed by a garbage collector. For example, the pointers in the chunk may be extracted and placed into a pointer array. The translation in this context occurs during promotion rather than continuation yield. Thus, the speed of switching between continuations may not be negatively impacted. However, in other embodiments, promoted chunks may maintain the same representation as before promotion. Pointer extraction may then be performed at the time of garbage collection.

In some embodiments, chunks may be stored in memory areas and/or promoted based on factors other than age. As previously mentioned, objects may be stored in memory areas based on datatype, object size, and/or other object attributes. In these cases, age may not factor into the determination of whether or not to allocate a new chunk when a continuation yields. Rather, the determination may depend on whether the memory area storing an existing chunk is subject to a GC barrier. For example, a first memory area may not be subject to any GC barriers and store data objects below a certain size threshold. A second memory area that is subject to a GC write barrier may store data objects that are above the size threshold. In this case, if the chunk resides in the first memory area, then it may be mutated with updated frames when the continuation yields. If the chunk instead resides in the second memory area, then a new chunk may be allocated to store the updated portion of the continuation stack. Similarly, these techniques may be applied to other regions in memory as a function of which regions are subject to GC barriers.

4. Garbage Collection Involving Continuation Chunks

Garbage collection techniques may vary significantly depending on the programming language and runtime environment. Generally, garbage collectors identify objects that are no longer reachable by a chain of references from root objects, signifying that the objects are no longer in use by the program. The garbage collector may then reclaim memory consumed by these objects to free up space for other objects.

Many garbage collectors, including concurrent and incremental garbage collectors, perform an STW pause to locate pointers in the root objects. Once located, the program may be resumed, and the live objects may be marked by tracing the reference pointers located in the root objects. These approaches work well when there are a small number of root objects. However, continuation stacks may be treated as root objects and may vastly outnumber the number of native thread stacks. As previously noted, scanning a large number of continuation stacks during an STW pause may degrade application runtime performance beyond acceptable limits.

With the chunk management techniques described above, garbage collectors may process chunks in young generation203differently than chunks in tenured generation204. In particular, the write barriers imposed on the aged-out chunks prevent the position of pointers from changing. As such, these roots may be scanned outside of an STW pause during program runtime. The chunks in the young generation may be scanned during an STW pause. However, the number of continuation stacks that are scanned may be significantly reduced. Further, many concurrent and generational garbage collectors scan young generation objects as a matter of course; therefore, locating the pointers in the young generation chunks may be done with little to no overhead.

FIG.8illustrates an example set of operations for performing garbage collection when chunks are stored in memory in accordance with some embodiments. One or more operations illustrated inFIG.8may be modified, rearranged, or omitted all together. Accordingly, the particular sequence of operations illustrated inFIG.8should not be construed as limiting the scope of one or more embodiments.

Referring toFIG.8, runtime environment113performs an STW pause (operation802). Thus, all application threads being executed by runtime environment113are paused, which prevents the threads from mutating frames in young generation203.

Runtime environment113next scans chunks within young generation203to locate pointers (operation804). In some embodiments, runtime environment113parses the stack portion stored in each young generation chunk to track the references. For example, runtime environment113may read the metadata stored in the stack frames, including the frames' return addresses, to obtain other metadata used to locate the pointers. The other metadata may include a stack map which identifies object references with the stack frames. Runtime environment113may also scan, concurrently or sequentially, thread stacks in the same manner to locate the pointers for currently mounted continuations.

Once the pointers have been identified, runtime environment resumes program execution (operation806). Thus, all application threads, including continuations mounted thereto, may continue to run, updating stack frames in the thread stacks. It is noted that continuations may also yield during runtime, potentially mutating chunks in young generation203. In other embodiments, one or more of operation804and/or806may occur outside of a STW pause during garbage collection. As previously mentioned, garbage collection techniques may vary depending on the programming language and runtime environment of the system executing the program code.

Runtime environment113further scans chunks in tenured generation204to locate the pointers (operation808). The chunks may be parsed in the same manner previously described to obtain a stack map of object references within the stack frames. The position of pointers for chunks in tenured generation204are frozen, allowing this operation to be performed while the application threads are executing without corrupting the garbage collection process.

Runtime environment113further identifies and marks live objects on the heap based on the pointers extracted from the chunks (operation810). Example marking methods include, but are not limited to, tri-color marking, although other marking techniques may be used, depending on the particular implementation. Marking involves identifying which objects are reachable from the roots, which include the continuation stacks, and marking these objects as live. These objects may be identified by traversing references from the pointers extracted from the root continuation chunks. Objects that are not reachable from the roots may then be collected to reclaim memory consumed by the unused objects.

5. Computer Networks and Cloud Networks

6. Hardware Implementations

For example,FIG.9is a block diagram that illustrates computer system900upon which an embodiment of the invention may be implemented. Computer system900includes bus902or other communication mechanism for communicating information, and a hardware processor904coupled with bus902for processing information. Hardware processor904may be, for example, a general purpose microprocessor.

Computer system900further includes read only memory (ROM)908or other static storage device coupled to bus902for storing static information and instructions for processor904. Storage device910, such as a magnetic disk or optical disk, is provided and coupled to bus902for storing information and instructions.

Computer system900may be coupled via bus902to display912, such as a cathode ray tube (CRT) or light emitting diode (LED) monitor, for displaying information to a computer user. Input device914, which may include alphanumeric and other keys, is coupled to bus902for communicating information and command selections to processor904. Another type of user input device is cursor control916, such as a mouse, a trackball, touchscreen, or cursor direction keys for communicating direction information and command selections to processor904and for controlling cursor movement on display912. Input device914typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor904for execution. For example, the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a network line, such as a telephone line, a fiber optic cable, or a coaxial cable, using a modem. A modem local to computer system900can receive the data on the network line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus902. Bus902carries the data to main memory906, from which processor904retrieves and executes the instructions. The instructions received by main memory906may optionally be stored on storage device910either before or after execution by processor904.

Computer system900can send messages and receive data, including program code, through the network(s), network link920and communication interface918. In the Internet example, a server930might transmit a requested code for an application program through Internet928, ISP926, local network922and communication interface918.

The received code may be executed by processor904as it is received, and/or stored in storage device910, or other non-volatile storage for later execution.