Garbage Collection is Fast, But a Stack is Faster

Prompted by claims that garbage collection can outperform stack allocation when sufficient physical memory is available, we present a careful analysis and set of cross-architecture measurements comparing these two approaches for the implementation of continuation (procedure call) frames. When the frames are allocated on a heap they require additional space, increase the amount of data transferred between memory and registers, and, on current architectures, require more instructions. We find that stack allocation of continuation frames outperforms heap allocation in some cases by almost a factor of three. Thus, stacks remain an important implementation technique for procedure calls, even in the presence of an efficient, compacting garbage collector and large amounts of memory.

Sparsely Faceted Arrays: A Mechanism Supporting Parallel Allocation, Communication, and Garbage Collection

Conventional parallel computer architectures do not provide support for non-uniformly distributed objects. In this thesis, I introduce sparsely faceted arrays (SFAs), a new low-level mechanism for naming regions of memory, or facets, on different processors in a distributed, shared memory parallel processing system. Sparsely faceted arrays address the disconnect between the global distributed arrays provided by conventional architectures (e.g. the Cray T3 series), and the requirements of high-level parallel programming methods that wish to use objects that are distributed over only a subset of processing elements. A sparsely faceted array names a virtual globally-distributed array, but actual facets are lazily allocated. By providing simple semantics and making efficient use of memory, SFAs enable efficient implementation of a variety of non-uniformly distributed data structures and related algorithms. I present example applications which use SFAs, and describe and evaluate simple hardware mechanisms for implementing SFAs. Keeping track of which nodes have allocated facets for a particular SFA is an important task that suggests the need for automatic memory management, including garbage collection. To address this need, I first argue that conventional tracing techniques such as mark/sweep and copying GC are inherently unscalable in parallel systems. I then present a parallel memory-management strategy, based on reference-counting, that is capable of garbage collecting sparsely faceted arrays. I also discuss opportunities for hardware support of this garbage collection strategy. I have implemented a high-level hardware/OS simulator featuring hardware support for sparsely faceted arrays and automatic garbage collection. I describe the simulator and outline a few of the numerous details associated with a "real" implementation of SFAs and SFA-aware garbage collection. Simulation results are used throughout this thesis in the evaluation of hardware support mechanisms.

Volume-based garbage collection fees : the Illinois experience /

"Presented at the ASTSWMO 1992 National Solid Waste Forum July 20-22, 1992, Portland, OR."

Garbage collection optimization for non uniform memory access architectures

Cache-coherent non uniform memory access (ccNUMA) architecture is a standard design pattern for contemporary multicore processors, and future generations of architectures are likely to be NUMA. NUMA architectures create new challenges for managed runtime systems. Memory-intensive applications use the system’s distributed memory banks to allocate data, and the automatic memory manager collects garbage left in these memory banks. The garbage collector may need to access remote memory banks, which entails access latency overhead and potential bandwidth saturation for the interconnection between memory banks. This dissertation makes five significant contributions to garbage collection on NUMA systems, with a case study implementation using the Hotspot Java Virtual Machine. It empirically studies data locality for a Stop-The-World garbage collector when tracing connected objects in NUMA heaps. First, it identifies a locality richness which exists naturally in connected objects that contain a root object and its reachable set— ‘rooted sub-graphs’. Second, this dissertation leverages the locality characteristic of rooted sub-graphs to develop a new NUMA-aware garbage collection mechanism. A garbage collector thread processes a local root and its reachable set, which is likely to have a large number of objects in the same NUMA node. Third, a garbage collector thread steals references from sibling threads that run on the same NUMA node to improve data locality. This research evaluates the new NUMA-aware garbage collector using seven benchmarks of an established real-world DaCapo benchmark suite. In addition, evaluation involves a widely used SPECjbb benchmark and Neo4J graph database Java benchmark, as well as an artificial benchmark. The results of the NUMA-aware garbage collector on a multi-hop NUMA architecture show an average of 15% performance improvement. Furthermore, this performance gain is shown to be as a result of an improved NUMA memory access in a ccNUMA system. Fourth, the existing Hotspot JVM adaptive policy for configuring the number of garbage collection threads is shown to be suboptimal for current NUMA machines. The policy uses outdated assumptions and it generates a constant thread count. In fact, the Hotspot JVM still uses this policy in the production version. This research shows that the optimal number of garbage collection threads is application-specific and configuring the optimal number of garbage collection threads yields better collection throughput than the default policy. Fifth, this dissertation designs and implements a runtime technique, which involves heuristics from dynamic collection behavior to calculate an optimal number of garbage collector threads for each collection cycle. The results show an average of 21% improvements to the garbage collection performance for DaCapo benchmarks.

A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers

Garbage collector performance in LISP systems on custom hardware has been substantially improved by the adoption of lifetime-based garbage collection techniques. To date, however, successful lifetime-based garbage collectors have required special-purpose hardware, or at least privileged access to data structures maintained by the virtual memory system. I present here a lifetime-based garbage collector requiring no special-purpose hardware or virtual memory system support, and discuss its performance.

Experiences with an Object-Oriented, Multi-Stage Language

Metaphor is a multi-stage programming language extension to an imperative, object-oriented language in the style of C# or Java. This paper discusses some issues we faced when applying multi-stage language design concepts to an imperative base language and run-time environment. The issues range from dealing with pervasive references and open code to garbage collection and implementing cross-stage persistence.

Demo Abstract: A Java compatible virtual machine for wireless sensor nodes

The Java programming language has potentially significant advantages for wireless sensor nodes but there is currently no feature-rich, open source virtual machine available. In this paper we present Darjeeling, a system comprising offline tools and a memory efficient run-time. The offline post-compiler tool analyzes, links and consolidates Java class files into loadable modules. The runtime implements a modified Java VM that supports multithreading and is designed specifically to operate in constrained execution environments such as wireless sensor network nodes and supports inheritance, threads, garbage collection, and loadable modules. We have demonstrated Java running on AVR128 and MSP430 microcontrollers at speeds of up to 70,000 JVM instructions per second.

Darjeeling, a Java compatible virtual machine for microcontrollers

The Java programming language enjoys widespread popularity on platforms ranging from servers to mobile phones. While efforts have been made to run Java on microcontroller platforms, there is currently no feature-rich, open source virtual machine available. In this paper we present Darjeeling, a system comprising offline tools and a memory efficient runtime. The offline post-compiler tool analyzes, links and consolidates Java class files into loadable modules. The runtime implements a modified Java VM that supports multithreading and is designed specifically to operate in constrained execution environments such as wireless sensor network nodes. Darjeeling improves upon existing work by supporting inheritance, threads, garbage collection, and loadable modules while keeping memory usage to a minimum. We have demonstrated Java running on AVR128 and MSP430 micro-controllers at speeds of up to 70,000 JVM instructions per second.

Information and Decision Technologies

Production scheduling in a flexible manufacturing system (FMS) is a real-time combinatorial optimization problem that has been proved to be NP-complete. Solving this problem needs on-line monitoring of plan execution and requires real-time decision-making in selecting alternative routings, assigning required resources, and rescheduling when failures occur in the system. Expert systems provide a natural framework for solving this kind of NP-complete problems.In this paper an expert system with a novel parallel heuristic approach is implemented for automatic short-term dynamic scheduling of FMS. The principal features of the expert system presented in this paper include easy rescheduling, on-line plan execution, load balancing, an on-line garbage collection process, and the use of advanced knowledge representational schemes. Its effectiveness is demonstrated with two examples.

Cidades secas, vidas secas: A trajetória das águas e sua regulamentação no Rio de Janeiro sob uma perspectiva urbano-ambiental

Esta tese analisará a distribuição das águas na cidade do Rio de Janeiro considerando os elementos sociais, jurídicos, políticos, e seus reflexos no direito urbano e ambiental. Nesse aspecto referenciará as medidas de regulação e de organização da estrutura urbana, desde a formação da cidade até os dias atuais, assim como as consequências da exclusão e da ausência das políticas urbanas equitativas. No início, as ocupações irregulares, se distantes do centro e dos bairros elitizados, não despertavam maiores demandas do poder público, porém com o aumento das periferias e as ocupações próximas aos bairros formais, inúmeras medidas adotadas optaram pela remoção, contenção e a destruição dos espaços sem apresentar uma solução, agravando os problemas urbanos. Tais problemas, reconhecidamente sociais, passam a ser denominados urbanos e ambientais, gerando uma complexa criminalização dos moradores das periferias. As intervenções nos espaços são legalizadas pelo instrumento jurídico, as residências suburbanas são classificadas como ilegais e, por consequência, os recursos que deveriam atender a todos na cidade são direcionados apenas para cidade legalizada, criando a celeuma da desigualdade. Assim, amontoados em barracos precários, sem abastecimento de água, energia, esgoto e coleta de lixo, as periferias multiplicam as diversas formas de violência, uma vez que o direito não socorre esses moradores que, abandonados pela lei, vivem a escassez das águas e a especulação dos serviços ilegais de abastecimento. A crise do abastecimento não é causada pelas populações mais empobrecidas, mas pelo mercado que se apropria da maior parte desses recursos, dentro do sistema de uma lógica capitalista, e exclui aqueles que não podem pagar pelo abastecimento regular. Nesse sentido, este trabalho entende que o direito, ainda que tenha se tornado regulatório pode assumir um caráter revolucionário e transformador em que o direito das águas seja um direito da comunidade, por isso, um bem público não estatal, por fim objetiva esse trabalho estudar as leis das águas dentro do paradigma da solidariedade hídrica.

Atlas digital: uma contribuição para o sistema de informação do município de São João de Meriti-RJ

Um Atlas Digital é um atlas que foi concebido através de técnicas computacionais e que, consequentemente, pode ser acessado através de um computador. Estruturado em um ambiente gráfico, além dos mapas, pode-se contar também com textos, fotografias, dados estatísticos, gráficos e tabelas. Por estar em meio digital existe a possibilidade de utilização de uma expressiva gama de temas, formatos e escalas. Nesta dissertação apresenta-se um protótipo de Atlas Digital como uma colaboração ao Sistema de Informação Municipal SIM, para o município de São João de Meriti, RJ. O referido SIM, que tem como meta os serviços municipais, visa atender ao próprio município, ao cidadão e a outros interessados na cidade, sendo as suas informações fundamentais para a melhoria da gestão das prefeituras. A pesquisa foi direcionada para o tema da habitabilidade, que consiste num conjunto de condições voltadas para a construção de habitat saudável, abrangendo temas físicos, psicológicos, sociais, culturais e ambientais. Dentro do tema habitabilidade, foram trabalhados os subtemas relativos a infraestrutura de abastecimento de água, esgoto, coleta de lixo, saúde e educação, esses subtemas foram confrontados entre si para uma comparação entre os bairros do município. O SIM e a habitabilidade são contemplados no plano diretor da cidade e representa uma grande parte da sustentação teórica da dissertação. A modelagem e implementação do protótipo do Atlas Digital foram feitas com auxílio de softwares gratuitos, sendo possível acessar mapas temáticos e outras informações sobre São João de Meriti

Análise socioambiental das sub-bacias do Rio Morto e do Rio Maracanã, Rio de Janeiro, a partir de indicadores ambientais e da percepção da comunidade do entorno.

O presente trabalho aborda duas sub-bacias hidrográficas do município do Rio de Janeiro através da apresentação de indicadores ambientais e da percepção de seus moradores. Destaca-se que a interação/utilização dos recursos no meio urbano em um município de alta densidade demográfica sofre reflexos principalmente do padrão de ocupação do território. As duas sub-bacias aqui analisadas, do rio Morto e do rio Maracanã, representam, respectivamente, bacias periurbanas e urbanas. Como indicadores ambientais são apresentados dados secundários, majoritariamente de órgãos públicos, como IBGE e INEA. A percepção dos moradores é representada pelas respostas a 210 questionários aplicados nas áreas das sub-bacias. Os principais resultados são apresentados ao longo do texto em mapas temáticos. Tanto entre os indicadores, quanto em relação à percepção, os serviços de saneamento demonstraram ter papel fundamental nas condições dos rios. Pequenos trechos mais carentes de cobertura de esgoto nas sub-bacias resultam em deterioração da qualidade da água, embora a cobertura de coleta geral apresente altos percentuais. Um ponto de destaque entre os problemas levantados através dos questionários é a ocorrência de enchentes. Dentre resultados positivos cita-se a cobertura de coleta de lixo, próxima a 100% nas sub-bacias. Uma matriz PEIR (pressão-estado-impacto-resposta) condensou as informações obtidas pelos indicadores e sinalizou os fatores associados. A matriz destacou para a sub-bacia do rio Morto o menor acesso ao abastecimento de água e à rede de esgoto, e para sub-bacia do rio Maracanã a degradação da qualidade da água, representada pelas baixas concentrações de oxigênio. Áreas com mais alta densidade populacional representaram a principal pressão exercida nas sub-bacias.

Logging and Recovery in a Highly Concurrent Database

This report addresses the problem of fault tolerance to system failures for database systems that are to run on highly concurrent computers. It assumes that, in general, an application may have a wide distribution in the lifetimes of its transactions. Logging remains the method of choice for ensuring fault tolerance. Generational garbage collection techniques manage the limited disk space reserved for log information; this technique does not require periodic checkpoints and is well suited for applications with a broad range of transaction lifetimes. An arbitrarily large collection of parallel log streams provide the necessary disk bandwidth.

Some Considerations on a Calculus with Weak References

Weak references are references that do not prevent the object they point to from being garbage collected. Most realistic languages, including Java, SML/NJ, and OCaml to name a few, have some facility for programming with weak references. Weak references are used in implementing idioms like memoizing functions and hash-consing in order to avoid potential memory leaks. However, the semantics of weak references in many languages are not clearly specified. Without a formal semantics for weak references it becomes impossible to prove the correctness of implementations making use of this feature. Previous work by Hallett and Kfoury extends λgc, a language for modeling garbage collection, to λweak, a similar language with weak references. Using this previously formalized semantics for weak references, we consider two issues related to well-behavedness of programs. Firstly, we provide a new, simpler proof of the well-behavedness of the syntactically restricted fragment of λweak defined previously. Secondly, we give a natural semantic criterion for well-behavedness much broader than the syntactic restriction, which is useful as principle for programming with weak references. Furthermore we extend the result, proved in previously of λgc, which allows one to use type-inference to collect some reachable objects that are never used. We prove that this result holds of our language, and we extend this result to allow the collection of weakly-referenced reachable garbage without incurring the computational overhead sometimes associated with collecting weak bindings (e.g. the need to recompute a memoized function). Lastly we use extend the semantic framework to model the key/value weak references found in Haskell and we prove the Haskell is semantics equivalent to a simpler semantics due to the lack of side-effects in our language.