In Social Deduction Games (SDGs) such as Avalon, Mafia, and Werewolf, players conceal their identities and deliberately mislead others, making hidden-role inference a central and demanding task. Accurate role identification, which forms the basis of an agent's belief state, is therefore the keystone for both human and AI performance. We introduce CSP4SDG, a probabilistic, constraint–satisfaction framework that analyses gameplay objectively. Game events and dialogue are mapped to four linguistically agnostic constraint classes—evidence, phenomena, assertions, and hypotheses. Hard constraints prune impossible role assignments, while weighted soft constraints score the remainder; information-gain weighting links each hypothesis to its expected value under entropy reduction, and a simple closed-form scoring rule guarantees that truthful assertions converge to classical hard logic with minimum error. The resulting posterior over roles is fully interpretable and updates in real time. Experiments on three public datasets show that CSP4SDG (i) outperforms LLM-based baselines in every inference scenario, and (ii) boosts LLMs when supplied as an auxiliary "reasoning tool." Our study validates that principled probabilistic reasoning with information theory is a scalable alternative—or complement—to heavy-weight neural models for SDGs.

Open-world missions often rely on repeated formulas, yet designers lack systematic ways to examine pacing, variation, and experiential balance across large portfolios. We introduce the Mission Action Quality Vector (MAQV), a six-dimensional framework—covering combat, exploration, narrative, emotion, problem-solving, and uniqueness—paired with an action block grammar representing missions as gameplay sequences. Using about 2200 missions from 20 AAA titles, we apply LLM-assisted parsing to convert community walkthroughs into structured action sequences and score them with MAQV. An interactive dashboard enables designers to reveal underlying mission formulas. In a mixed-methods study with experienced players and designers, we validate the pipeline’s fidelity and the tool’s usability, and use thematic analysis to identify recurring design trade-offs, pacing grammars, and systematic differences by quest type and franchise evolution. Our work offers a reproducible analytical workflow, a data-driven visualization tool, and reflective insights to support more balanced, varied mission design at scale.

Large scale control of nonplayer agents is central to modern games, while production systems still struggle to balance several competing goals: locally smooth, natural behavior, and globally coordinated variety across space and time. Prior approaches rely on handcrafted rules or purely stochastic triggers, which either converge to mechanical synchrony or devolve into uncorrelated noise that is hard to tune. Continuous noise signals such as Perlin noise are well suited to this gap because they provide spatially and temporally coherent randomness, and they are already widely used for terrain, biomes, and other procedural assets. We adapt these signals for the first time to large scale AI control and present a general framework that treats continuous noise fields as an AI coordinator. The framework combines three layers of control: behavior parameterization for movement at the agent level, action time scheduling for when behaviors start and stop, and spawn or event type and feature generation for what appears and where. We instantiate the framework reproducibly and evaluate Perlin noise as a representative coordinator across multiple maps, scales, and seeds against random, filtered, deterministic, neighborhood constrained, and physics inspired baselines. Experiments show that coordinated noise fields provide stable activation statistics without lockstep, strong spatial coverage and regional balance, better diversity with controllable polarization, and competitive runtime. We hope this work motivates a broader exploration of coordinated noise in game AI as a practical path to combine efficiency, controllability, and quality.

Roguelike and auto-battler games derive much of their replayability from randomized progression, rewards, and encounter sequencing, yet this randomness rarely extends to genuinely diverse game mechanics and content such as skills or combat units. Existing procedural systems for such content usually depend on fixed rule spaces, hand-authored templates, or proxy spell engines, which limit their ability to produce outputs that are semantically meaningful, valuable in play, and sufficiently expressive. We present Neural Spore Genesis, a browser-based roguelike auto-battler in which players buy elemental cells, arrange them on a 5 × 5 grid, and compile that spatial layout into a combat skill for auto-battle. To support this task, we build a high-expressivity structured skill framework covering a broad range of 2D auto-battler combat behaviors, and evaluate local open-weight language models against deterministic, template-based, random, and calibrated sampler baselines. Across 6 generator conditions and a 105-configuration corpus evaluated with 11 metrics, local LLMs achieve near-perfect element coherence while maintaining high intra-config diversity, a combination the baselines do not match. This work offers a practical evaluation environment for intent-aware procedural mechanic generation and supports future research on semantically grounded content systems for high randomness games.

Visual guidance plays a crucial role in level design, while prior work has largely relied on qualitative observations. This study presents a novel quantitative framework for evaluating visual guidance during level transitions in 3D role-playing games. By integrating analyses of depth maps derived from raycast grids with high-resolution RGB image sequences from our primary dataset in Dark Souls III, we quantify metrics such as luminance dynamics, chromatic complexity, and spatial depth distribution. This bimodal analysis separates geometric factors (from depth) and perceptual factors (from color), thereby clarifying how specific visual cues consistent with design principles such as spatial funneling and chromatic contrast-influence player navigation and immersion. Our initial empirical findings, derived from strictly quantitative and numerical analyses, suggest that the synergy between geometric constraints and perceptual cues provides an effective framework for both validating design principles and identifying navigation pitfalls in level transitions. These results not only provide a formal, data-driven understanding of level design but also offer actionable insights for creating more intuitive virtual environments and establishing evaluation criteria for future procedural level generation.

Action windows—spatiotemporal regions enabling player's safe execution of key in-game actions—are foundational to game task planning, yet their automated generation remains underexplored. In stealth games, for example, level designers carefully create guard patrols and environment layouts. However, critical tasks such as planning assassination routes for high-value targets (VIPs) still depend heavily on manual tuning. This work formalizes VIP task planning as the problem of automatically generating a path through a predefined environment with guard patrols, such that VIP's path contains player's safe action windows that are temporally and spatially dispersed, while maintaining coherence and meaningful interactions with environmental elements. We introduce two approaches: (1) an evolutionary optimization approach that is efficient in generating diverse routes by balancing multiple objectives, and (2) a constraint-driven safe-block search method that guarantees optimal sequences under strict design thresholds. Initial experiments validate that the evolutionary method generates diverse, high-dispersion routes with rapid runtimes, whereas the safe-block approach enforces hard constraints with predictable performance. Both methods integrate directly with existing level and patrol data, offering scalable solutions for automated stealth mission generation.

Automating gameplay in a complex environment poses challenges for learning due to the large state and action spaces and the need for long-term planning.This paper presents a Gymnasium environment to allow for reinforcement learning research and experimentation in the video game RollerCoaster Tycoon, a popular amusement park simulation game with complex mechanics.We also present an approach to learn to play and win several game scenarios in this environment.

Procedural Content Generation (PCG) has long enabled efficient and varied game level creation.However, integrating high-level design intentions and game mechanics into complex 3D environments remains challenging.This paper introduces a comprehensive framework that transforms narrative-level descriptions into playable 3D game levels.First, Large Language Models (LLMs) parse natural language descriptions of game environments into a structured Game Level Description Language (GLDL), capturing essential spatial constraints.Next, we model level generation as a Facility Layout Optimization problem, ensuring that facility placements and configurations adhere to specified design criteria.Through comprehensive experiments, including automated constraint evaluations and agent-based simulations, our approach ensures both the feasibility and stability of the constraints extracted from textual descriptions.We confirm that the resulting game levels remain interactive, reasonable, and controllable to their original specifications.

A memory consistency model specifies the allowed behaviors of shared memory concurrent programs. At the language level, these models are known to have a non-trivial impact on the safety of program optimizations. This limits the ability to rearrange/refactor code without introducing new behaviors. Existing programming language memory models try to address this by permitting more ( relaxed/weak ) concurrent behaviors, but are still unable to allow all the desired optimizations. A core problem is that weaker consistency models may also render optimizations unsafe, a conclusion that goes against the intuition of them allowing more behaviors. This exposes an open problem of the compositional interaction between memory consistency semantics and optimizations; which parts of the semantics correspond to allowing/disallowing which set of optimizations is unclear. In this work, we establish a formal foundation suitable enough to understand this compositional nature. We decompose optimizations into a finite set of elementary effects , over which aspects of safety can be assessed. We use this decomposition to identify a desirable compositional property ( complete ) that would guarantee the safety of optimizations from one memory model to another. We showcase its practicality by proving such a property between Sequential Consistency (SC) and SC RR , the latter allowing independent read-read reordering over SC . Our work potentially paves way to a new design methodology of programming-language memory models, one that places emphasis on the optimizations desired to be performed.

Even though many games feature complex 3D environments, 3D pathfinding remains a challenging problem. Representing large 3D maps can require a lot of memory, and pathfinding instances must be solved very quickly while the game is running. In this work we develop an efficient solution to 3D pathfinding by building a reduced, hierarchical grid representation within which we can extend traditional 2D navigation mesh (navmesh) pathing. Starting from an octree representation, we merge adjacent cells while preserving their convexity to obtain a coarser representation that greatly reduces path computation costs. We then build a navigation graph from this octree within which we can search for paths using the popular A* search algorithm. To increase the quality of the paths we obtain we implemented two forms of path refinement: a visibilitybased path pruning heuristic, and a 3D extension of the classic “funnel” algorithm that computes minimal homotopic paths. We further extend our work to handle dynamic environments with local and efficient updates to the octree and the movement graph. Experiments on a variety of scenarios show that our approach remains fast and efficient even for very large 3D maps and could be used for real-time pathfinding in video games. A detailed comparison with the state-of-the-art JPS-3D algorithm shows that our approach produces shorter path lengths while being faster on long path instances. We implemented our work in Unity, one of the most popular game engines, as an effort to make pathfinding in 3D environments accessible to game developers.

The “RollerCoaster Tycoon” video game involves creating rollercoaster tracks that optimize for various game metrics while also being constrained by the need to ensure a feasible structure in terms of physical and spatial bounds. Creating these procedurally is thus a challenge. In this work, we explore multiple approaches to rollercoaster track generation through the use of Markov chains and various deep learning methods. We show that we can achieve relatively good tracks in terms of the game's measurement of success, and that reinforcement learning allows for more control of the generated tracks and for different rider experiences. A focus on multiple measures allows our work to extend to other track properties drawn from real-world research. This paper extends a previous publication by adding a new reward function for our reinforcement learning agent as well as further analyses of the generated tracks, including a metric measuring rider excitement over time, a revised novelty metric and an analysis of controllability.

The "RollerCoaster Tycoon" video game involves creating rollercoasters that optimize for various in-game metrics, while also being constrained by the need to ensure a feasible structure in terms of physical and spatial bounds. Creating these procedurally is thus a challenge. In this work, we explore multiple approaches to rollercoaster generation, including Markov chains and machine learning and reinforcement learning algorithms. We show that we can achieve relatively good tracks in terms of the game’s measurement of success, and that reinforcement learning may give more control over other factors of potential interest. A focus on multiple measures allows our work to extend to other factors that also mimic actual player constructions.

Memory consistency models traditionally specify the behavior of shared memory concurrent hardware. Hardware behavior drifts away from traditional sequential reasoning, thus exhibiting behaviors that are termed as "weak". Weaker consistency models allow for more concurrent behaviors, thus justifying hardware optimizations such as read/write buffers. In parallel, weaker memory models for software allow more compiler optimizations (transformations). However, this "more" may not be strict: certain safe optimizations in stronger models are rendered unsafe in ones weaker than them. We identify properties that must hold among a pair of weak and strong memory models to guarantee this. We propose a framework using which we could build such models, showcasing our results in allowing Read Read reordering over Sequential Consistency (SC). We also show how to partially retain our desired property for a pair of models, placing constraints on the set of transformations or equivalently, on program structure. Lastly, we discuss the potential advantage of designing models satisfying such properties.

GPU database systems are an effective solution to query optimization, particularly with compilation and data caching. They fall short, however, in end-to-end workloads, as existing compiler toolchains are too expensive for use with short-running queries. In this work, we define and evaluate a runtime-suitable query compilation pipeline for NVIDIA GPUs that extracts high performance with only minimal optimization. In particular, our balanced approach successfully trades minor slowdowns in execution for major speedups in compilation, even as data sizes increase. We demonstrate performance benefits compared to both CPU and GPU database systems using interpreters and compilers, extending query compilation for GPUs beyond cached use cases.

In virtual environments, research into the problem of stealthy or covert path planning has either assumed fixed and static motion of observers or has used relatively simple probabilistic models that statically summarize potential behavior. In this paper, we introduce a method that dynamically estimates enemy motion in order to plan covert paths in a prototype game environment. We compare our results to other baseline pathfinding methods and conduct an extensive exploration of the many parameters and design choices involved to better understand the impact of different settings on the success of covert path planning in virtual environments. Our design provides a more flexible approach to covert pathfinding problems, and our analysis provides useful insights into the relative weighting of the different factors that can improve design choices in building stealth scenarios.

The following topics are dealt with: program compilers; multiprocessing systems; parallel processing; graphics processing units; optimisation; optimising compilers; microprocessor chips; program diagnostics; storage management; parallel architectures.

In many games, players may run away and hide from NPC enemies that have previously observed them, either to avoid combat or as part of pursuing a stealth-based solution. Rational NPC response then requires searching for the hidden player, which for maximal realism should build on the last known location, and consider the relative likelihood of a player hiding or reaching each searched location. Unfortunately, search behavior is not usually systematic, and in practice is either limited to randomized goals within a small region, or exploits global information on the player position that should be unknown. In this work, we introduce a real-time method for directing a multi-agent search utilizing the environment's topology. This approach allows for more natural and wider-scoped search behavior. Experimental results show that this method scales to relatively large game maps, and performs better than or close to a naïve team of agents fully aware of the player's position.

Emergent narratives provide a unique and compelling approach to interactive storytelling through simulation, and have applications in games, narrative generation, and virtual agents. However, the inherent complexity of simulation makes understanding the expressive potential of emergent narratives difficult, particularly at the design phase of development. In this article, we present a novel approach to emergent narrative using the narratological theory of possible worlds and demonstrate how the design of works in such a system can be understood through a formal means of analysis inspired by expressive range analysis. Last, we propose a novel way through which content may be authored for the emergent narrative system using a sketch-based interface.

Array-based programming languages have shown significant promise for improving performance of column-based in-memory database systems, allowing elegant representation of query execution plans that are also amenable to standard compiler optimization techniques. Use of loop fusion, however, is not straightforward, due to the complexity of built-in functions for implementing complex database operators. In this work, we apply a compiler approach to optimize SQL query execution plans that are expressed in an array-based intermediate representation. We analyze this code to determine shape properties of the data being processed, and use a subsequent optimization phase to fuse multiple database operators into single, compound operations, reducing the need for separate computation and storage of intermediate values. Experimental results on a range of TPC-H queries show that our fusion technique is effective in generating efficient code, improving query time over a baseline system.

Sparse matrix-vector multiplication (SpMV) is an important kernel in many scientific, machine-learning, and other compute-intensive applications. Performance characteristics, however, depend on a complex combination of storage format, machine capabilities, and choices in code-generation. A deep understanding of the relative impact of these properties is important in itself, and also to better understanding the performance potential of alternative execution contexts such as web-based scientific computing, where the recent introduction ofWebAssembly offers the potential for low-level, near-native performance within a web browser. In this work we characterize the performance of SpMV operations for different sparse storage formats based on the sparse matrix structure and the machine architecture. We extract structural properties from 2000 real-life sparse matrices to understand their impact on the choice of storage format and also on the performance within those storage formats for both WebAssembly and native C. We extend this with new matrix features based on a "reuse-distance" concept to identify performance bottlenecks, and evaluate the effect of interaction between the matrix structure and hardware characteristics on SpMV performance. Our study provides valuable insights to scientific programmers and library developers to apply best practices and guide future optimization for SpMV in general, and in particular for web-based contexts with abstracted hardware and storage models.

Roguelike games generally feature exploration problems as a critical yet often repetitive element of gameplay. Automated approaches, however, face challenges in terms of optimality, as well as due to incomplete information, such as from the presence of secret doors. This paper presents an algorithmic approach to exploration of roguelike dungeon environments. Our design aims to minimize exploration time, balancing coverage and discovery of secret areas with resource cost. Our algorithm is based on the concept of occupancy maps popular in robotics, adapted to encourage efficient discovery of secret access points. Through extensive experimentation on NetHack maps, we show that this technique is significantly more efficient than simpler greedy approaches and an existing automated player. We further investigate optimized parameterization for the algorithm through a comprehensive data analysis. These results point toward better automation for players, as well as heuristics applicable to fully automated gameplay.

Roguelike games generally feature exploration problems as a critical, yet often repetitive element of gameplay. Automated approaches, however, face challenges in terms of optimality. This paper presents an approach to exploration of roguelike dungeon environments. Our design, based on the concept of occupancy maps popular in robotics, aims to minimize exploration time, balancing coverage with resource cost. Through extensive experimentation on NetHack maps we show that this technique is significantly more efficient than simpler greedy approaches. Results point towards better automation for players as well as heuristics for fully automated gameplay.

Software-based, automatic parallelization through Thread-Level Speculation (TLS) has significant practical potential, but also high overhead costs. Traditional "lazy" buffering mechanisms enable strong isolation of speculative threads, but imply large memory overheads, while more recent "eager" mechanisms improve scalability, but are more sensitive to data dependencies and have higher rollback costs. We here describe an integrated system that incorporates the best of both designs, automatically selecting the best buffering mechanism. Our approach builds on well-optimized designs for both techniques, and we describe specific optimizations that improve both lazy and eager buffer management as well. We implement our design within MUTLS, a software-TLS system based on the LLVM compiler framework. Results show that we can get 75% geometric mean performance of OpenMP versions on 9 memory intensive benchmarks. Application of these optimizations is thus a useful part of the optimization stack needed for effective and practical software TLS.

Using procedural narrative generation in video games provides a flexible way to extend game play and provide more depth to the game world at low cost to the developers. Current examples of narrative generation in commercial games, however, tend to be simplistic, resulting in repetitive and uninteresting stories. In this paper, we develop a system for narrative generation using a context-aware graph-rewriting framework. We use a graph representation of the game world to create narratives which reflect and modify the current world state. Using a novel set of metrics to evaluate narrative quality, we validate our approach by comparing our generated narratives to other procedurally generated stories, as well as to authored narratives from commercially successful and critically praised games. The results show that our narratives compare favorably to the authored narratives. Our metrics provide a new approach to narrative analysis, and our system provides a unique and practical approach to story generation.

Software approaches to Thread-Level Speculation (TLS) have been recently explored, bypassing the need for specialized hardware designs. These approaches, however, tend to focus on source or VM-level implementations aimed at specific language and runtime environments. In addition, previous software approaches tend to make use of a simple thread forking model, reducing their ability to extract substantial parallelism from tree-form recursion programs such as depth-first search and divide-and-conquer. This paper proposes a Mixed forking model Universal software-TLS (MUTLS) system to overcome these limitations. MUTLS is purely based on the LLVM intermediate representation (IR), a language and architecture independent IR that supports more than 10 source languages and target architectures by many projects. MUTLS maximizes parallel coverage by applying a mixed forking model that allows all threads to speculate, forming a tree of threads. We evaluate MUTLS using several C/C++ and Fortran benchmarks on a 64-core machine. On 3 computation intensive applications we achieve speedups of 30 to 50 and 20 to 50 for the C and Fortran versions, respectively. We also observe speedups of 2 to 7 for memory intensive applications. Our experiments indicate that a mixed model is preferable for parallelization of tree-form recursion applications over the simple forking models used by previous software-TLS approaches. Our work also demonstrates that actual speedup is achievable on existing, commodity multi-core processors while maintaining the flexibility of a highly generic implementation context.

Designing video game scenarios that will stimulate the player with an engaging and properly paced level of difficulty is a non-trivial issue, one which can fundamentally impact the playability and popularity of a game. World of Warcraft, like many MMORPGs, suffers noticeably from the less challenging pacing of its later-game scenarios compared to its earlier-game content. To examine this observation in detail, a World of Warcraft client-side plugin was created to record data about the players' progress throughout a cooperative scenario, including health, power, map position, class, and role. This data was analyzed to measure the pacing of each session. The results showed a drop in difficulty between late-game level 80 five-person group content and level 70 five-person group content. Using this basic metric to quantify the level of difficulty is a step forward in designing scalable and adaptable scenarios that can continue to challenge players of all experience levels.

This paper presents Mammoth, a massively multiplayer game research framework designed for experimentation in an academic setting. Mammoth provides a modular architecture where different components, such as the network engine, the replication engine, or interest management, can easily be replaced. Subgames allow a researcher to define different game goals, for instance, in order to evaluate the effects of different team-play tactics on the game performance. Mammoth also offers a modular and flexible infrastructure for the definition of non-player characters with behavior controlled by complex artificial intelligence algorithms. This paper focuses on the Mammoth architecture, demonstrating how good design practices can be used to create a modular framework where researchers from different research domains can conduct their experiments. The effectiveness of the architecture is demonstrated by several successful research projects accomplished using the Mammoth framework.

Virtual Machine authors face a difficult choice between low performance, cheap interpreters, or specialized and costly compilers. A method able to bridge this wide gap is the existing code-copying technique that reuses chunks of the VM’s binary code to create a simple JIT. This technique is not reliable without a compiler guaranteeing that copied chunks are still functionally equivalent despite aggressive optimizations. We present a proof-of-concept, minimal-impact modification of a highly optimizing compiler, GCC. A VM programmer marks chunks of VM source code as copyable. The chunks of native code resulting from compilation of the marked source become addressable and self-contained. Chunks can be safely copied at VM runtime, concatenated and executed together. This allows code-copying VMs to safely achieve speedup up to 3 times, 1.67 on average, over the direct interpretation. This maintainable enhancement makes the code-copying technique reliable and thus practically usable.

Modern JIT compilers often employ multi-level recompilation strategies as a means of ensuring the most used code is also the most highly optimized, balancing optimization costs and expected future performance. Accurate selection of code to compile and level of optimization to apply is thus important to performance. In this paper we investigate the effect of an improved recompilation strategy for a Java virtual machine. Our design makes use of a lightweight, low-level profiling mechanism to detect high-level, variable length phases in program execution. Phases are then used to guide adaptive recompilation choices, improving performance. We develop both an offline implementation based on trace data and a self-contained online version. Our offline study shows an average speedup of 8.7% and up to 21%, and our online system achieves an average speedup of 4.4%, up to 18%. We subject our results to extensive analysis and show that our design achieves good overall performance with high consistency despite the existence of many complex and interacting factors in such an environment.

Many popular programming languages use interpreter-based execution for portability, supporting dynamic or reflective properties, and ease of implementation. Code-copying is an optimization technique for interpreters that reduces the performance gap between interpretation and JIT compilation, offering significant speedups over direct-threading interpretation. Due to varying language features and virtual machine design, however, not all languages benefit from codecopying to the same extent. We consider here properties of interpreted languages, and in particular bytecode and virtual machine construction that enhance or reduce the impact of code-copying. We implemented code-copying and compared performance with the original direct-threading virtual machines for three languages, Java (SableVM), OCaml, and Ruby (Yarv), examining performance on three different architectures, ia32 (Pentium 4), x86_64 (AMD64) and PowerPC (G5). Best speedups are achieved on ia32 by OCaml (maximum 4.88 times, 2.81 times on average), where a small and simple bytecode design facilitates improvements to branch prediction brought by code-copying. Yarv only slightly improves over direct-threading; large working sizes of bytecodes, and a relatively small fraction of time spent in the actual interpreter loop both limit the application of codecopying and its overall net effect. We are able to show that simple ahead of time analysis of VM and execution properties can help determine the suitability of code-copying for a particular VM before an implementation of code-copying is even attempted.

The pure methods in a program are those that exhibit functional or side effect free behaviour, a useful property in many contexts. However, existing purity investigations present primarily staticresults. We perform a detailed examination of dynamic method purityin Java programs using a JVM-based analysis. We evaluate multiple purity definitions that range from strong to weak, consider purity forms specific to dynamic execution, and accomodate constraintsimposed by an example consumer application, memoization. We show that while dynamic method purity is actually fairly consistent between programs, examining pure invocation counts and the percentage of the byte code instruction stream contained within some pure method reveals great variation. We also show that while weakening purity definitions exposes considerable dynamic purity, consumer requirements can limitthe actual utility of this information.

Analysis of dynamic data structure usage is useful for both program understanding and for improving the accuracy of other program analyses. Static analysis techniques, however, suffer from reduced accuracy in complex situations, and do not necessarily give a clear picture of runtime heap activity. We have designed and implemented a dynamic heap analysis system that allows one to examine and analyze how Java programs build and modify data structures. Using a complete execution trace from a profiled run of the program, we build an internal representation that mirrors the evolving runtime data structures. The resulting series of representations can then be analyzed and visualized, and we show how to use our approach to help understand how programs use data structures, the precise effect of garbage collection, and to establish limits on static data structure analysis. A deep understanding of dynamic data structures is particularly important for modern, object-oriented languages that make extensive use of heapbased data structures.

Many new Java runtime optimizations report relatively small, single-digit performance improvements. On modern virtual and actual hardware, however, the performance impact of an optimization can be influenced by a variety of factors in the underlying systems. Using a case study of a new garbage collection optimization in two different Java virtual machines, we show the relative effects of issues that must be taken into consideration when claiming an improvement. We examine the specific and overall performance changes due to our optimization and show how unintended side-effects can contribute to, and distort the final assessment. Our experience shows that VM and hardware concerns can generate variances of up to 9.5% in whole program execution time. Consideration of these confounding effects is critical to a good, objective understanding of Java performance and optimization.

Speculative multithreading (SpMT) is a promising optimisation technique for achieving faster execution of sequential programs on multiprocessor hardware. Analysis of and data acquisition from such systems is however difficult and complex, and is typically limited to a specific hardware design and simulation environment. We have implemented a flexible, software-based speculative multithreading architecture within the context of a full-featured Java virtual machine. We consider the entire Java language and provide a complete set of support features for speculative execution, including return value prediction. Using our system we are able to generate extensive dynamic analysis information, analyse the effects of runtime feedback, and determine the impact of incorporating static, offline information. Our approach allows for accurate analysis of Java SpMT on existing, commodity multiprocessor hardware, and provides a vehicle for further experimentation with speculative approaches and optimisations.

The report summarizes the results of the Workshop on Middleware Benchmarking held during OOPSLA 2003. The goal of the workshop was to help advance the current practice of gathering performance characteristics of middleware implementations through benchmarking. The participants of the workshop have focused on identifying requirements of and obstacles to middleware benchmarking and forming a position on the related issues. Selected requirements and obstacles are presented, together with guidelines to adhere to when benchmarking, open issues of current practice, and perspectives on further research. Copyright © 2005 John Wiley & Sons, Ltd.

This paper proposes and implements a rigorous method for studying the dynamic behaviour of AspectJ programs. As part of this methodology several new metrics specific to AspectJ programs are proposed and tools for collecting the relevant metrics are presented. The major tools consist of: (1) a modified version of the AspectJ compiler that tags bytecode instructions with an indication of the cause of their generation, such as a particular feature of AspectJ; and (2) a modified version of the *J dynamic metrics collection tool which is composed of a JVMPI-based trace generator and an analyzer which propagates tags and computes the proposed metrics. This dynamic propagation is essential, and thus this paper contributes not only new metrics, but also non-trivial ways of computing them.

In order to perform meaningful experiments in optimizing compilation and run-time system design, researchers usually rely on a suite of benchmark programs of interest to the optimization technique under consideration. Programs are described as numeric, memory-intensive, concurrent, or object-oriented, based on a qualitative appraisal, in some cases with little justification. We believe it is beneficial to quantify the behaviour of programs with a concise and precisely defined set of metrics, in order to make these intuitive notions of program behaviour more concrete and subject to experimental validation. We therefore define and measure a set of unambiguous, dynamic, robust and architecture-independent metrics that can be used to categorize programs according to their dynamic behaviour in five areas: size, data structure, memory use, concurrency, and polymorphism. A framework computing some of these metrics for Java programs is presented along with specific results demonstrating how to use metric data to understand a program's behaviour, and both guide and evaluate compiler optimizations.

Traditional tracing systems are often limited to recording a fixed set of basic program events. This limitation can frustrate an application or compiler developer who is trying to understand and characterize the complex behavior of software systems such as a Java program running on a Java Virtual Machine. In the past, many developers have resorted to specialized tracing systems that target a particular type of program event. This approach often results in an obscure and poorly documented encoding format which can limit the reuse and sharing of potentially valuable information. To address this problem, we present STEP, a system designed to provide profiler developers with a standard method for encoding general program trace data in a flexible and compact format. The system consists of a trace data definition language along with a compiler and an architecture that simplifies the client interface by encapsulating the details of encoding and interpretation.