HK1175270B - A conservative garbage collecting method and a memory management device - Google Patents

Description

Conservative garbage collection method and memory management device

Technical Field

The invention relates to a conservative garbage collection algorithm using concurrent markers and concurrent sweeps.

Background

As background with respect to some conventional systems, it should be noted that computing devices have traditionally stored information and associated applications. For these and related results, it should also be noted that implementing an efficient memory management scheme can help achieve optimal computing performance. The development in automatic memory management schemes has performed well compared to manual memory management schemes. Garbage collector algorithms are, for example, automatic memory management schemes that attempt to retrieve memory occupied by objects that are no longer used by a particular program.

Tracking garbage collectors are a common type of garbage collector. The tracking garbage collector first determines which objects are reachable (or, possibly, reachable) and then discards all remaining objects. An reachable object may be defined as an object that: there is some variable in the program environment that can lead to an object, either directly or through a reference from another reachable object. More precisely, objects can generally be reached in two ways. First, assume that a distinct set of objects (distinggushed sets), called roots, are reachable. Generally, these objects include all objects that reference anywhere within the self-call stack (i.e., all local variables and parameters in the function currently being called) as well as any global variables. Second, any object that references self-reachable objects is itself considered reachable. However, a complication with conventional garbage collectors is that such garbage collectors need to quickly and efficiently free memory allocated to objects that are no longer reachable.

The above-described shortcomings of present day memory management schemes are intended only to provide an overview of some of the problems of conventional systems and are not intended to be exhaustive. Other problems in the current art and the corresponding benefits of various non-limiting embodiments may become apparent upon a careful reading of the following detailed description.

Disclosure of Invention

A simplified summary is provided herein to facilitate a basic or general understanding of various aspects of exemplary, non-limiting embodiments that follow in the more detailed description and the accompanying drawings. This summary is not intended, however, to be exhaustive or exhaustive. Rather, the sole purpose of this summary is to present some concepts related to some exemplary non-limiting embodiments in a simplified form as a prelude to the more detailed description of the various embodiments that follow.

In accordance with one or more embodiments and corresponding disclosure thereof, various non-limiting aspects are described in connection with conservative garbage collection for memory management. In one such aspect, a method is provided for concurrently marking and sweeping objects within a conservative garbage collection algorithm. The method may include generating a heap of objects during execution of the script, and tracking script objects included in an unexecuted portion of the script to a set of corresponding memory locations on the heap. This embodiment may also include marking at least a portion of the heap concurrently with execution of the script such that the marked heap includes reachable objects and unreachable objects. For this particular embodiment, the reachable objects are reachable by the unexecuted portion of the script, and the unreachable objects are unreachable by the unexecuted portion of the script. The method may then further include releasing memory allocated to each unreachable object based on the tag concurrently with execution of the script.

In another aspect, a memory management device configured to concurrently mark and sweep objects is disclosed. In this embodiment, the memory management device includes a processor configured to execute computer-executable components stored in a memory. The computer-executable components include a heap component, a tracking component, a tagging component, and a reclamation component. The heap component is configured to generate a heap of objects during execution of the script, and the tracking component is configured to track script objects included in an unexecuted portion of the script to a set of corresponding memory locations on the heap. The marking component is then configured to mark at least a portion of the heap concurrently with execution of the script. For this embodiment, the marked heap includes reachable objects that are reachable by the unexecuted portion of the script, and unreachable objects that are not reachable by the unexecuted portion of the script. The reclamation component is then configured to free memory allocated to the unreachable object concurrently with execution of the script and according to the marked heap.

In yet another aspect, a computer-readable storage medium for concurrently marking and sweeping objects in a conservative garbage collection algorithm is disclosed. In this embodiment, the computer-readable storage medium includes computer-readable instructions for causing the at least one processor to perform the various acts. For example, the actions include generating an object graph associated with a call stack, and tracking the object graph such that script objects included in an unexecuted portion of the call stack are tracked to a corresponding set of memory locations on the heap. This embodiment also includes marking the heap object concurrently with execution of the call stack. For this particular embodiment, the marked heap includes reachable objects that are reachable by the unexecuted portion of the call stack and unreachable objects that are not reachable by the unexecuted portion of the call stack. Memory allocated to the unreachable objects is then cleared based on the marked heap concurrently with execution of the call stack.

Other embodiments and various non-limiting examples, scenarios, and implementations are described in more detail below.

Drawings

Various non-limiting embodiments are further described with reference to the accompanying drawings in which:

FIG. 1 illustrates an exemplary system that facilitates implementing a conservative garbage collection algorithm in accordance with an embodiment;

FIG. 2 is a diagram illustrating an exemplary heap of objects according to one embodiment;

FIG. 3 is a diagram illustrating an exemplary object diagram according to one embodiment;

FIG. 4 is a diagram illustrating an exemplary release of memory according to one embodiment;

FIG. 5 is a block diagram illustrating an exemplary memory management device in accordance with one embodiment;

FIG. 6 is a flow diagram illustrating an exemplary, non-limiting embodiment for implementing a conservative garbage collection algorithm according to an embodiment;

FIG. 7 is a block diagram illustrating an exemplary resource management unit in accordance with one embodiment;

FIG. 8 is a flow diagram illustrating an exemplary, non-limiting embodiment for concurrently marking and sweeping objects according to an embodiment;

FIG. 9 is a block diagram representing exemplary non-limiting networked environments in which various embodiments described herein can be implemented; and

FIG. 10 is a block diagram representing an exemplary non-limiting computing system or operating environment in which one or more aspects of various embodiments described herein can be implemented.

Detailed Description

Overview

As indicated in the background, it is desirable to implement a conservative garbage collector algorithm that distinguishes between reachable and unreachable objects on a heap. In various embodiments, memory management is redesigned for native code compatibility. In one aspect, script objects are less managed objects than just native pieces of memory, such that reference counts between objects are eliminated. Furthermore, a conservative garbage collection algorithm is implemented, where it is not assumed that everything that is a pointer is known. Using a Common Language Runtime (CLR) garbage collector as an example, the stack is strongly typed. However, with native code (e.g., C code and script code), one does not know what is on the stack. In this regard, instead of utilizing a reference counting model, it is contemplated to interact directly with the object.

Various embodiments disclosed herein relate to marking and sweeping objects concurrently in a conservative garbage collection algorithm. Further, aspects disclosed herein relate to marking and sweeping objects concurrently to facilitate efficient execution of scripts (e.g., java scripts) for a document object model. In an exemplary embodiment, the concurrency marking includes traversing objects on the heap, wherein each object that is reachable is assigned a "1" and each object that is unreachable is assigned a "0". Once the concurrency marking has been completed, the concurrency scanner scans the heap and places unreachable objects (i.e., those marked with a "0") in a "free memory" list.

An advantage of implementing a concurrent scanner is that less memory is used because memory is reclaimed back to the allocator while the script thread is executing. Here, it should be noted that some data structures are generated as concurrent markers and sweeps are implemented. For example, some data structures maintain free bits separate from marked bits. Further, separate pages of heap blocks may be maintained such that an entire page may be identified as free. The resources required to retrieve these pages are therefore minimized relative to previous techniques, where many pages are undesirably allocated chunks and thus require more resources for retrieval. Further, by implementing the disclosed aspects, an entire page can be quickly identified as free with a simple check.

On the other hand, lock-free queues are created side-by-side with the sweep process, in contrast to how a conventional sweep requires that the entire sweep occur before any swept memory can be reused by the thread doing the work. In this embodiment, the lock-free queue may be a data structure that allows segments of memory to be handed back to the worker thread (i.e., the thread executing the web page) during the sweep, which significantly reduces the amount of memory used as part of the working set. Thus, a more incremental reclamation mechanism is disclosed, where such reclamation is desirably performed at a finer granularity.

Concurrent tagging and sweeping for conservative garbage collection

Several problems have arisen when the web browsing experience has begun to evolve from a monotonous presentation of information with minimal interactivity to a richer application or applet experience with many interactivity on the client side. More generally, the web browsing experience has developed into a mix of information display and richer interactivity with objects on the display. A particular challenge with this development is based on adapting the original Document Object Model (DOM), which was originally designed primarily for monotonic presentation of information based on native code on the client, to the experience of smoothly processing script code, such as java script objects.

Improving speed helps to promote a smooth user experience. For example, using the past fly-out menu, the web experience blinks the delay based on the communication with the server. However, scripts allow applets to modify the DOM on the fly without returning to the server. Fast script code execution has become a challenge as one wants to take more actions on the fly-out menu without returning to the server.

Since the user experience can be greatly affected by efficiently scripting the DOM, it is desirable to change the DOM as fast as possible to maximize the interaction response. In the past, communication between the scripting engine and native classes of the DOM was poor due to the use of Object Linking and Embedding (OLE) automation, which includes a set of interfaces (e.g., iDispatch, iactive script, etc.) that make any object scriptable. However, these methods are slow and improvements are therefore desirable. Accordingly, aspects disclosed herein relate to increasing script execution speed by concurrently marking and sweeping objects within a conservative garbage collection algorithm.

FIG. 1 illustrates an exemplary system that facilitates implementing a conservative garbage collection algorithm in accordance with an embodiment. As shown, system 100 may include a memory management unit 110 communicatively coupled to a memory 120. In an aspect, the memory management unit 110 is configured to implement a conservative garbage collection algorithm to manage memory space in the memory 120. Further, the memory management unit 110 is configured to generate a tagged object map 114 associated with execution of the script 112. For example, the script 112 may be a java script that executes against the DOM, where the java script includes various objects that require allocation of memory space in the memory 120. In particular embodiments, to facilitate distinguishing between "reachable" and "unreachable" objects, script objects included in marked object graph 114 are marked according to whether the script objects are reachable by unexecuted portions of script 112.

In one aspect, the memory allocated to script objects includes storing the objects on a heap. Referring next to FIG. 2, a block diagram of an exemplary heap of objects is provided, according to an embodiment. As shown, heap 200 may include available memory 210 and allocated memory corresponding to various objects 220, 230, 240, 250, 260, and 270. For this particular example, objects 240 and 270 correspond to pointer values, while objects 220, 230, 250, and 260 correspond to integer values. That is, object 240 is a pointer value that references the integer value represented by object 230, and object 270 is a pointer value that references the integer value represented by object 260.

It is contemplated that heap objects may be tagged such that reachable objects may be readily distinguished from unreachable objects. Referring next to FIG. 3, a diagram illustrating an exemplary object graph that facilitates mapping reachable/unreachable objects on a heap is provided. As shown, the object graph 300 maps objects included in the unexecuted call stack portion 310 to the marked heap 320. To this end, it should be noted that the marked heap 320 and available memory 330 are generally similar to the heap 200 and available memory 210, respectively.

In one aspect, the object graph 300 is utilized to determine which objects on the marked heap 320 are reachable by the unexecuted call stack portion 310. I.e., to track root objects included in the non-executing call stack portion 310 to corresponding memory locations on the marked heap 320, where those memory locations are deemed reachable. It is then contemplated that subsequent tracking of the root object is performed on the reachable pointer values to identify reachable objects that are referenced by those pointer values. Here, it should be noted that subsequent tracing may be skipped for reachable integer values, since these integer values do not refer to other values. For this particular example, since reachable object 390 is the root object corresponding to the pointer value, subsequent tracking is performed on reachable object 390, which reachable object 390 identifies reachable object 380 that corresponds to an integer value. However, subsequent tracking may be skipped for reachable objects 340 and 370 because these objects are root objects corresponding to integer values.

It should be noted that the object graph 300 may also be utilized to identify objects that are not reachable by the unexecuted call stack portion 310. In this particular example, unreachable objects 350 and 360 are considered unreachable because they do not correspond to root objects in the unexecuted call stack portion 310, and they are not referenced by reachable pointer objects.

After identifying the reachable/unreachable objects, it is contemplated that at least one of the reachable or unreachable objects is marked so that they can be easily distinguished from each other. In one aspect, such marking occurs concurrently with execution of the call stack. For this particular example, reachable object 340, reachable object 370, reachable object 380, and reachable object 390 are marked with a "1", while unreachable object 350 and unreachable object 360 are marked with a "0". Here, one of ordinary skill will appreciate that a markup object can be implemented in any of a variety of ways including, for example, assigning a bit to such a markup within each object representation.

After the object graph has been appropriately marked, memory previously allocated to heap objects identified as unreachable may be purged. In an aspect, the clearing of such memory occurs concurrently with the execution of the call stack. Referring next to FIG. 4, a diagram of an exemplary release of memory is provided, according to an embodiment. As shown, object graph 400 includes a swept heap 420, which is generally similar to heaps 200 and 320, where heap 420 depicts the freeing of memory previously allocated to unreachable objects 350 and 360. I.e., heap 420 now includes freed memory 450 and 460 in addition to available memory 430. However, in one aspect, reachable objects 440, 470, 480, and 490 are saved in their original storage locations (i.e., the swept heap 420 is not corrupted (collapse)).

Referring next to FIG. 5, a block diagram illustrates an exemplary memory management unit configured to implement a conservative garbage collection algorithm in accordance with various aspects. As shown, memory management unit 500 may include a processor component 510, a memory component 520, a heap component 530, a tracking component 540, a marking component 550, and a eviction component 560.

In one aspect, the processor component 510 is configured to execute computer readable instructions related to performing any of a number of functions. The processor component 510 can be a single processor or multiple processors dedicated to analyzing information to be sent from the memory management unit 500 and/or generating information that can be utilized by the memory component 520, the heap component 530, the tracking component 540, the tagging component 550, and/or the reclamation component 560. Additionally or alternatively, processor component 510 may be configured to control one or more components of memory management unit 500.

In another aspect, the memory component 520 is coupled to the processor component 510 and configured to store computer readable instructions executed by the processor component 510. The memory component 520 can also be configured to store any of a variety of other types of data including data generated by any of the heap component 530, the tracking component 540, the tagging component 550, and/or the reclamation component 560. Memory component 520 may be configured in a number of different configurations, including as random access memory, power-backed memory, a hard disk, a tape, and so forth. Various features may also be implemented on the memory component 520, such as compression and automatic backup, such as using a redundant array of independent drives configuration.

As shown, the memory management unit 500 may also include a heap component 530 and a tracking component 540. In this embodiment, the heap component 530 is configured to generate a heap of objects during execution of the script, and the tracking component 540 is configured to track script objects included in the unexecuted portion of the script to a set of corresponding memory locations on the heap.

In another aspect, memory management device 500 further includes a tagging component 550. In this embodiment, the marking component 550 is configured to mark at least a portion of the heap concurrently with execution of the script. For this embodiment, the marked heap includes reachable objects that are reachable by the unexecuted portion of the script, as well as unreachable objects that are considered unreachable by the unexecuted portion of the script.

In other aspects, the memory management device 500 further includes a reclamation component 560. In this embodiment, reclamation component 560 is configured to free memory allocated to each unreachable object concurrently with execution of the script and according to the marked heap. In a particular embodiment, the reclamation component 560 may be configured to reclaim the portion of the memory allocated to each unreachable object before releasing the entire portion of the memory allocated to each unreachable object. In another embodiment, the reclamation component 560 may be configured to save the reachable objects in respective original storage locations of the heap. For example, the reclamation component 560 may be configured to maintain the separation of heap objects according to a fixed set of boundaries within the heap.

For some embodiments, the memory management device 500 may be configured to execute a script that the heap component 530 uses to generate a heap of objects. To this end, it should be understood that the memory management device 500 may be configured to execute any of a variety of script types. For example, in a particular embodiment, the memory management device 500 is configured to compile java scripts. After executing the script, it is contemplated that the memory management device 500 is then further configured to modify the document object model based on the execution of the script.

FIG. 6 is a flow diagram illustrating an exemplary, non-limiting embodiment for implementing a conservative garbage collection algorithm according to an embodiment. At 600, a heap of objects is generated during execution of a script. Next, at 610, the script objects included in the unexecuted portion of the script are tracked to a set of corresponding memory locations on the heap. The heap is then marked, at 620, concurrently with the execution of the script. For this particular embodiment, the marked heap includes reachable objects that are reachable by the unexecuted portion of the script, and unreachable objects that are not reachable by the unexecuted portion of the script. At 640, memory allocated to each unreachable object is then freed based on the marked heap concurrently with execution of the script.

Referring next to FIG. 7, a block diagram of an exemplary resource management unit configured to concurrently mark and sweep objects in accordance with various aspects is illustrated. As shown, resource management unit 700 may include a processor component 710, a memory component 720, a graph generation component 730, a tracking component 740, a marking component 750, and a release component 760.

Similar to processor component 510 in memory management unit 500, processor component 710 is configured to execute computer-readable instructions related to performing any of a number of functions. Processor component 710 can be a single processor or multiple processors dedicated to analyzing information sent from resource management unit 700 and/or generating information that can be utilized by memory component 720, graph generation component 730, tracking component 740, marking component 750, and/or release component 760. Additionally or alternatively, the processor component 710 may be configured to control one or more components of the resource management unit 700.

In another aspect, a memory component 720 is coupled to the processor component 710 and configured to store computer readable instructions for execution by the processor component 710. The memory component 720 may also be configured to store any of a variety of other types of data including data generated by any of the graph generation component 730, the tracking component 740, the tagging component 750, and/or the release component 760. Here, it should be noted that memory component 720 is similar to memory component 520 in memory management unit 500. Thus, it is to be appreciated that any of the aforementioned features/configurations of memory component 520 also apply to memory component 720.

As shown, the resource management unit 700 can also include a graph generation component 730 and a tracking component 740. In this embodiment, the graph generation component 730 is configured to generate an object graph associated with a call stack, and the tracking component 740 is configured to track the object graph such that script objects included in an unexecuted portion of the call stack are tracked to a set of corresponding memory locations on the heap.

In another aspect, resource management unit 700 can further include a tagging component 750. In this embodiment, the marking component 750 is configured to mark heap objects concurrently with execution of the call stack. For this embodiment, the marked heap includes reachable objects that are reachable by the unexecuted portion of the call stack and unreachable objects that are considered unreachable by the unexecuted portion of the call stack.

As shown, the resource management unit 700 may also include a release component 760. In this embodiment, the release component 760 is configured to clear memory allocated to each unreachable object concurrently with execution of the call stack. Here, it is contemplated that the memory can be cleared based upon the marked heap ascertained by marking component 750. In an aspect, the release component 760 may be further configured to save storage of objects reachable by the unexecuted portion of the call stack in their original memory locations within the heap, respectively. In another aspect, the release component 760 can be configured to reclaim portions of memory allocated to each unreachable object. For this particular embodiment, the release component 760 may also be configured to reclaim the portion of memory allocated to each unreachable object prior to releasing the entire portion of memory.

FIG. 8 is a flow diagram illustrating an exemplary non-limiting embodiment for marking and sweeping objects concurrently according to an embodiment. At 800, an object graph associated with a call stack is generated. At 810, the object graph is then traced such that script objects included in the unexecuted portion of the call stack are traced to a set of corresponding memory locations on the heap. Next, at 820, the heap object is marked concurrently with execution of the call stack. For this particular embodiment, the marked heap includes reachable objects that are reachable by the unexecuted portion of the call stack and unreachable objects that are not reachable by the unexecuted portion of the call stack. At 830, memory allocated to each unreachable object is then cleared based on the marked heap concurrently with execution of the call stack.

Exemplary networked and distributed environments

One of ordinary skill in the art will appreciate that the various embodiments described herein for marking and sweeping objects concurrently within a conservative garbage collection algorithm may be implemented in connection with any computer or other client or server device that may be deployed as part of a computer network or in a distributed computing environment, and that may be connected to any kind of data store. In this regard, the embodiments described herein may be implemented in any computer system or environment having any number of memory or storage units, and any number of applications and processes occurring across any number of storage units. This includes, but is not limited to, an environment with server computers and client computers deployed in a network environment or distributed computing environment, having remote or local storage.

FIG. 9 provides a non-limiting schematic diagram of an exemplary networked or distributed computing environment. The distributed computing environment comprises computing objects or devices 910, 912, etc. and computing objects or devices 920, 922, 924, 926, 928, etc., which may include programs, methods, data stores, programmable logic, etc., as represented by applications 930, 932, 934, 936, 938. It is to be appreciated that computing objects or devices 910, 912, etc. and computing objects or devices 920, 922, 924, 926, 928, etc. can comprise different devices such as, for example, PDAs, audio/video devices, mobile phones, MP3 players, laptops, etc.

Each computing object or device 910, 912, etc. and computing objects or devices 920, 922, 924, 926, 928, etc. can communicate with one or more other computing objects or devices 910, 912, etc. and computing objects or devices 920, 922, 926, 928, 940, etc. by way of the communications network 924, either directly or indirectly. Even though illustrated as a single element in FIG. 9, network 940 may comprise other computing objects or computing devices that provide services to the system of FIG. 9, and/or may represent multiple interconnected networks, which are not shown. Each computing object or device 910, 912, etc. or 920, 922, 924, 926, 928, etc. may also contain an application, such as applications 930, 932, 934, 936, 938, which may utilize an API or other object, software, firmware, and/or hardware suitable for communicating with or implementing a memory management system provided in accordance with various embodiments.

There are a variety of systems, components, and network configurations that support distributed computing environments. For example, computing systems may be connected together by wired or wireless systems, by local networks, or by widely distributed networks. Currently, many networks are coupled to the Internet, which provides an infrastructure for widely distributed computing and encompasses many different networks, but any network infrastructure may be used for exemplary communications that become associated with the techniques as described in various embodiments.

Thus, a host of network topologies and network infrastructures, such as client/server, peer-to-peer, or hybrid architectures, can be utilized. In a client/server architecture, particularly a networked system, a client is typically a computer that accesses shared network resources provided by another computer (e.g., a server). In the illustration of FIG. 9, as non-limiting examples, computing objects or devices 920, 922, 924, 926, 928, etc. can be thought of as clients and computing objects or devices 910, 912, etc. can be thought of as servers where computing objects or devices 910, 912, etc. provide data services, such as receiving data from computing objects or devices 920, 922, 924, 926, 928, etc., storing data, processing data, transmitting data to computing objects or devices 920, 922, 924, 926, 928, etc., although any computer can be considered a client, a server, or both, depending on the circumstances. Any of these computing devices may process data, or request services or tasks that may indicate an infrastructure of information, i.e., services, and related techniques from any platform as described herein with reference to one or more embodiments.

A server is typically a remote computer system accessible over a remote or local network, such as the Internet or wireless network infrastructure. A client process may be active in a first computer system and a server process may be active in a second computer system, communicating with each other over a communications medium, thereby providing distributed functionality and allowing multiple clients to take advantage of the information-gathering capabilities of the server. Any software objects utilized pursuant to a user profile can be provided separately or distributed across multiple computing devices or objects.

For example, in a network environment in which the communications network/bus 940 is the Internet, the computing objects or devices 910, 912, etc. can be web servers with which the computing objects or devices 920, 922, 924, 926, 928, etc. communicate via any of a number of known protocols, such as HTTP. As mentioned, computing objects or devices 910, 912, etc. may also serve as computing objects or devices 920, 922, 924, 926, 928, etc. or, conversely, may be characteristic of a distributed computing environment.

Exemplary computing device

As mentioned, the various embodiments described herein are applicable to any device in which it may be desirable to implement an architecture for concurrently marking and sweeping objects within a conservative garbage collection algorithm. It should be understood, therefore, that handheld, portable and other computing devices and computing objects of various kinds are contemplated for use in connection with the various embodiments described herein, i.e., wherever a device may provide some functionality in connection with implementing a conservative garbage collection algorithm with integers labeled. Accordingly, the below general purpose remote computer described below in FIG. 10 is but one example, and embodiments of the disclosed subject matter can be implemented with any client having network/bus interoperability and interaction.

Although not required, any of the various embodiments can be implemented in part via an operating system, for use by a developer of services for a device or object, and/or included within application software that operates in conjunction with operational components. Software may be described in the general context of computer-executable instructions, such as program modules, being executed by one or more computers, such as client workstations, servers or other devices. Those skilled in the art will appreciate that network interactions may be practiced with a variety of computer system configurations and protocols.

FIG. 10 thus illustrates an example of a suitable computing system environment 1000 in which one or more embodiments may be implemented, but as made clear above, the computing system environment 1000 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of any of the embodiments. Neither should the computing environment 1000 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 1000.

With reference to FIG. 10, an exemplary remote device for implementing one or more embodiments herein may include a general purpose computing device in the form of a handheld computer 1010. The components of handheld computer 1010 may include, but are not limited to: a processing unit 1020, a system memory 1030, and a system bus 1021 that couples various system components including the system memory to the processing unit 1020.

Computer 1010 typically includes a variety of computer readable media and can be any available media that can be accessed by computer 1010. The system memory 1030 may include computer storage media in the form of volatile and/or nonvolatile memory such as Read Only Memory (ROM) and/or Random Access Memory (RAM). By way of example, and not limitation, memory 1030 may also include an operating system, application programs, other program modules, and program data.

A user may enter commands and information into the computer 1010 through input device(s) 1040. A monitor or other type of display device is also connected to the system bus 1021 via an interface, such as output interface 1050. In addition to the monitor, computers may also include other peripheral output devices such as speakers and a printer, which may be connected through output interface 1050.

The computer 1010 may operate in a networked or distributed environment using logical connections to one or more other remote computers, such as a remote computer 1070. The remote computer 1070 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, or any other remote media consumption or transmission device, and may include any or all of the elements described above relative to the computer 1010. The logical connections depicted in fig. 10 include a network 1071, such Local Area Network (LAN) or a Wide Area Network (WAN), but may also include other networks/buses. Such networking environments are commonplace in homes, offices, enterprise-wide computer networks, intranets and the Internet.

As mentioned above, while exemplary embodiments have been described in connection with various computing devices, networks, and advertising architectures, the underlying concepts may be applied to any network system and any computing device or system in which it is desirable to manage memory.

There are a number of ways to implement one or more embodiments described herein, e.g., an appropriate API, toolkit, driver code, operating system, control, standalone or downloadable software object, etc., that enables applications and services to use memory management from any platform. Embodiments may be conceived from the standpoint of an API (or other software object), as well as from a software or hardware object that facilitates providing a memory management system in accordance with one or more of the described embodiments. Various implementations and embodiments described herein may have aspects that are wholly in hardware, partly in hardware and partly in software, as well as in software.

The word "exemplary" is used herein to mean serving as an example, instance, or illustration. For the avoidance of doubt, the subject matter disclosed herein is not limited to these examples. Additionally, any aspect or design described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other aspects or designs, nor is it meant to exclude equivalent exemplary structures and techniques known to those of ordinary skill in the art. Furthermore, to the extent that the terms "includes," "has," "includes," and other similar words are used in either the detailed description or the claims, for the avoidance of doubt, such terms are intended to be inclusive in a manner similar to the term "comprising" as an open transition word without precluding any additional or other elements.

As noted, the various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both. As used herein, the terms "component," "system," and the like are likewise intended to refer to a computer-related entity, either hardware, a combination of hardware and software, or software in execution. For example, a component may be, but is not limited to being, a process running on a processor, an object, an executable, a thread of execution, a program, and/or a computer. By way of illustration, both an application running on a computer and the computer can be a component. One or more components can reside within a process and/or thread of execution and a component can be localized on one computer and/or distributed between two or more computers.

The system as described above has been described with reference to interaction between several components. It will be understood that these systems and components may include components or specified sub-components, some specified components or sub-components, and/or additional components, and according to various permutations and combinations of the above. Sub-components can also be implemented as components communicatively coupled to other components rather than included within parent components (hierarchical). Additionally, it is noted that one or more components may also be combined into a single component providing aggregate functionality or divided into multiple separate sub-components, and any one or more middle layers, such as a management layer, may be provided to communicatively couple to such sub-components in order to provide integrated functionality. Any components described herein may also interact with one or more other components not specifically described herein but generally known by those of skill in the art.

In view of the exemplary systems described above, methodologies that may be implemented in accordance with the disclosed subject matter will be understood with reference to the flow charts of the various figures. While, for purposes of simplicity of explanation, the methodologies are shown and described as a series of blocks, it is to be understood and appreciated that the claimed subject matter is not limited by the order of the blocks, as some blocks may occur in different orders and/or concurrently with other blocks from what is depicted and described herein. Although non-sequential or branched flow is illustrated via flowchart, it can be appreciated that various other branches, flow paths, and orders of the blocks, may be implemented which achieve the same or similar result. Moreover, not all illustrated blocks may be required to implement the methodologies described hereinafter.

While in some embodiments, a client-side perspective is illustrated, it is to be understood for the avoidance of doubt that a corresponding server perspective exists, and vice versa. Similarly, where a method is implemented, a corresponding apparatus may be provided having at least one processor storing and configured to implement the method via one or more components.

While the embodiments have been described in connection with the preferred embodiments of the various figures, it is to be understood that other similar embodiments may be used or modifications and additions may be made to the described embodiment for performing the same function without deviating therefrom. Moreover, one or more aspects of the various embodiments described herein may be implemented in or across a plurality of processing chips or devices, and storage may similarly be effected across a plurality of devices. Accordingly, the present invention should not be limited to any single embodiment, but rather should be construed in breadth and scope in accordance with the appended claims.

Claims (15)

1. A conservative garbage collection method, comprising:

generating a heap of objects during execution of the script;

tracking each script object included in an unexecuted portion of the script to a set of corresponding memory locations on the heap;

marking at least a portion of the heap concurrently with execution of the script, wherein the marked heap comprises reachable objects that are reachable by the unexecuted portion of the script, and wherein the marked heap further comprises unreachable objects that are unreachable by the unexecuted portion of the script; and

freeing memory allocated to the unreachable object, wherein the freeing is based on the marker and performed concurrently with execution of the script.

2. The method of claim 1, wherein said marking comprises marking said reachable objects.

3. The method of claim 1, wherein the marking comprises marking the unreachable object.

4. The method of claim 1, wherein the freeing comprises saving the reachable objects in original storage locations of the heap, respectively.

5. The method of claim 4, wherein the saving comprises maintaining a separation of heap objects according to a fixed set of boundaries within the heap.

6. The method of claim 1, further comprising executing the script.

7. A method as defined in claim 6, wherein the executing comprises compiling java script.

8. The method of claim 6, wherein the performing comprises modifying a document object model.

9. A memory management device, comprising:

a memory having computer-executable components stored thereon; and

a processor communicatively coupled to the memory, the processor configured to execute the computer-executable components, the computer-executable components comprising:

a heap component configured to generate a heap of objects during execution of the script;

a tracking component configured to track each script object included in an unexecuted portion of the script to a set of corresponding memory locations on the heap;

a tagging component configured to tag at least a portion of the heap concurrently with execution of the script, wherein the tagged heap comprises reachable objects that are reachable by an unexecuted portion of the script, and wherein the tagged heap further comprises unreachable objects that are unreachable by an unexecuted portion of the script; and

a reclamation component configured to free memory allocated to the unreachable object according to the marked heap, wherein the reclamation component is further configured to free the memory concurrently with execution of the script.

10. The memory management device of claim 9, wherein the tagging component is configured to tag only one of the reachable objects or the unreachable objects.

11. The memory management device of claim 9, wherein the reclamation component is configured to reclaim a portion of memory allocated to the unreachable object prior to releasing an entire portion of memory allocated to the unreachable object.

12. The memory management device of claim 9, wherein the reclamation component is configured to save reachable objects in raw memory locations of a heap, respectively.

13. The memory management device of claim 12, wherein the reclamation component is configured to maintain a separation of heap objects according to a fixed set of boundaries within the heap.

14. The memory management device of claim 9, further comprising an execution component configured to execute the script.

15. The memory management device of claim 14, further comprising a component configured to modify a document object model based on execution of the script.