The class definitions and class field declarations in the ECMAScript standard suggest that the JavaScript engines could be optimized like class-based static languages. This paper focuses on two well-known optimizations. One is method specialization, using fixed offsets to access properties. The other is prior hidden class construction, which involves creating runtime class-like structures called hidden classes before creating instances of the classes. However, implementing such optimizations into JavaScript faces difficulties because of its dynamic features. We point out three difficulties that must be overcome and propose reasonable solutions. We implemented these optimizations and solutions in QuickJS, a small, practical JavaScript engine, and obtained promising results.

Improving Floating-Point Numbers (IFN) is a numerical computation library for Haskell. It allows the user to directly specify the accuracy of the result, making accurate computation easy. The library's computation process is based on adaptive control of accuracies, which propagates the demands for more accurate values from an expression to its appropriate subexpressions. However, despite its unique features, programs utilizing the IFN library often encounter efficiency issues regarding memory consumption and execution time due to its fine granularity of computations. This paper presents the computational granularity control mechanism through fusion transformation to resolve these problems and proposes two fusion strategies, the maximal fusion and chain fusion. We have successfully implemented a fusion system that automatically applies these strategies through program transformation. Its effectiveness was confirmed through numerical computation programs.

Virtual machine introspection (VMI) is a technique for inspecting a virtual machine from the outside, typically to analyze the operating system (guest OS) running on it. LibVMI is a C library for VMI and provides APIs for accessing guest OS's memory. However, in using LibVMI APIs directly in C, the programmer must compute target addresses in the kernel memory and then access them with their exact bit widths and types. This is an enormous burden for the programmer and is prone to introducing statically undetected but fatal errors. We create HaVMI, a Haskell library that facilitates VMI programming. HaVMI provides meta-functions for compile-time code generation by Template Haskell. These meta-functions make it easy to write safer VMI programs. HaVMI uses Haskell language features to detect the programmer's errors statically.

The emergence of non-volatile memory (NVM) presents opportunities for making in-memory data of application programs persistent at a small cost. An adequate abstraction is required for programming languages to be able to utilize NVM. Here, persistence by reachability is a suitable abstraction for managed languages. In this abstraction, all objects are volatile when they are created and become persistent later depending on their reachability from the predefined roots. The state-of-the-art in the implementations of persistence by reachability creates objects in DRAM and moves them to NVM when they become persistent. This implementation has two inefficiencies. One is the read barriers to get the current location of objects; the other is to read values of persistent objects from NVM, which is slower than DRAM.

Abstract The vertex-centric programming model is now widely used for processing large graphs. User-defined vertex programs are executed in parallel over every vertex of a graph, but the imperative and explicit message-passing style of existing systems makes defining a vertex program unintuitive and difficult. This article presents Fregel, a purely functional domain-specific language for processing large graphs and describes its model, design, and implementation. Fregel is a subset of Haskell, so Haskell tools can be used to test and debug Fregel programs. The vertex-centric computation is abstracted using compositional programming that uses second-order functions on graphs provided by Fregel. A Fregel program can be compiled into imperative programs for use in the Giraph and Pregel+ vertex-centric frameworks. Fregel’s functional nature without side effects enables various transformations and optimizations during the compilation process. Thus, the programmer is freed from the burden of program optimization, which is manually done for existing imperative systems. Experimental results for typical examples demonstrated that the compiled code can be executed with reasonable and promising performance.

Jonkers's threaded compaction is attractive in the context of memory-constrained embedded systems because of its space efficiency. However, it cannot be applied to a heap where ordinary objects and meta-objects are intermingled for the following reason. It requires the object layout information, which is often stored in meta-objects, to update pointer fields inside objects correctly. Because Jonkers's threaded compaction reverses pointer directions during garbage collection (GC), it cannot follow the pointers to obtain the object layout. This paper proposes Fusuma, a double-ended threaded compaction that allows ordinary objects and meta-objects to be allocated in the same heap. Its key idea is to segregate ordinary objects at one end of the monolithic heap and meta-objects at the other to make it possible to separate the phases of threading pointers in ordinary objects and meta-objects. Much like Jonkers's threaded compaction, Fusuma does not require any additional space for each object. We implemented it in eJSVM, a JavaScript virtual machine for embedded systems, and compared its performance with eJSVM using mark-sweep GC. As a result, compaction enabled an IoT-oriented benchmark program to run in a 28-KiB heap, which is 20 KiB smaller than mark-sweep GC. We also confirmed that the GC overhead of Fusuma was less than 2.50x that of mark-sweep GC.

Programs with interactive and/or realtime activities, such as GUI programs, action game programs, network-based programs, and sensor information processing programs, are not suitable for traditional breakpoint-based debugging, in which execution of the target program is suspended, for two reasons. First, since the timings and order of input event occurrences such as user operations are quite important, such programs do not behave as expected if execution is suspended at a breakpoint. Second, suspending a program to observe its internal states significantly degrades the efficiency of debugging. A debugging method is presented that resolves these problems. It keeps track of both the currently executing statement in a program and the changes in value of expressions of interest, and visualizes them in realtime. The proposed method was implemented as SLDSharp, a debugger for C# programs, by means of a program transformation technique. Through a case study of debugging a practical game program created by using the Unity game engine, it is shown in that SLDSharp makes it possible to efficiently debug.

The vertex-centric programming model, known as “think like a vertex”, is being used more and more to support various big graph processing methods through iterative supersteps that execute in parallel a user-defined vertex program over each vertex of a graph. However, the imperative and message-passing style of existing systems makes defining a vertex program unintuitive. In this paper, we show that one can benefit more from “Thinking like a vertex” by “Behaving like a function” rather than “Acting like a procedure” with full use of side effects and explicit control of message passing, state, and termination. We propose a functional approach to vertex-centric graph processing in which the computation at every vertex is abstracted as a higher-order function and present Fregel, a new domain-specific language. Fregel has clear functional semantics, supports declarative description of vertex computation, and can be automatically translated into Pregel, an emerging imperative-style distributed graph processing framework, and thereby achieve promising performance. Experimental results for several typical examples show the promise of this functional approach.

Efficient transactional executions are desirable for parallel implementations of algorithms with graph refinements. Hardware transactional memory (HTM) is promising for easy yet efficient transactional executions. Long HTM transactions, however, abort with high probability because of hardware limitations. Unfortunately, Delaunay mesh refinement (DMR), which is an algorithm with graph refinements for mesh generation, causes long transactions. Its parallel implementation naively based on HTM therefore leads to poor performance. To utilize HTM efficiently for parallel implementation of DMR, we present an approach to shortening transactions. Our HTM based implementations of DMR achieved significantly higher throughput and better scalability than a naive HTM-based one and lock-based ones. On a quad-core Has well processor, the absolute speedup of one of our implementations was up to 2.64 with 16 threads.

This paper presents a library called LibDSL that helps the implementer of an embedded domain specific language (EDSL) effectively develop it in D language. The LibDSL library accepts as input some kinds of ``specifications'' of the EDSL that the implementer is going to develop and a D program within which an EDSL source program written by the user is embedded. It produces the front-end code of an LALR parser for the EDSL program and back-end code of the execution engine. LibDSL is able to produce two kinds of execution engines, namely compiler-based and interpreter-based engines, either of which the user can properly choose depending on whether an EDSL program is known at compile time or not. We have implemented the LibDSL system by using template metaprogramming and other advanced facilities such as compile-time function execution of D language. EDSL programs developed by means of LibDSL have a nice integrativeness with the host language.

Streaming of XML transformations is a challenging task and only a few existing systems support streaming. Research approaches generally define custom fragments of XQuery and XPath that are amenable to streaming, and then design custom algorithms for each fragment. These languages have several shortcomings. Here we take a more principled approach to the problem of streaming XQuery-based transformations. We start with an elegant transducer model for which many static analysis problems are well-understood: the Macro Forest Transducer (MFT). We show that a large fragment of XQuery can be translated into MFTs - indeed, a fragment of XQuery, that can express important features that are missing from other XQuery stream engines, such as GCX: our fragment of XQuery supports XPath predicates and let-statements. We then use an existing streaming engine for MFTs and apply a well-founded set of optimizations from functional programming such as strictness analysis and deforestation. Our prototype achieves time and memory efficiency comparable to the fastest known engine for XQuery streaming, GCX. This is surprising because our engine relies on the OCaml built in garbage collector and does not use any specialized buffer management, while GCX's efficiency is due to clever and explicit buffer management.

Mark-compact garbage collection helps long-running programs avoid fragmentation. The Lisp2 mark-compact collector is a classic but still widely-used compaction algorithm. It sequentially scans the entire heap to compact all live objects at one end of the heap while preserving their order of addresses. Since the heap is generally large, this scanning takes a long time. Although some collectors adopt a separate bitmap into which mark bits of objects are stored to reduce the scanning time, we observed that scanning the bitmap can take longer than scanning the heap if objects are densely located. We propose a new scanning method from this observation, which adaptively alternates methods of scanning depending on heap usage; it scans those parts of the heap where live objects are densely located whereas it scans the bitmap for the remaining parts. We implemented this scanning method in the Lisp2 collector of Jikes RVM.

To rewrite a sequential program into a concurrent one, the programmer has to enforce atomic execution of a sequence of accesses to shared memory to avoid unexpected inconsistency. There are two means of enforcing this atomicity: one is the use of lock-based synchronization and the other is the use of software transactional memory (STM). However, it is difficult to predict which one is more suitable for an application than the other without trying both mechanisms because their performance heavily depends on the application. We have developed a system named SAW that decouples the synchronization mechanism from the application logic of a Java program and enables the programmer to statically select a suitable synchronization mechanism from a lock or an STM. We introduce annotations to specify critical sections and shared objects. In accordance with the annotated source program and the programmer's choice of a synchronization mechanism, SAW generates aspects representing the synchronization processing. By comparing the rewriting cost using SAW and that using individual synchronization mechanism directly, we show that SAW relieves the programmer's burden. Through several benchmarks, we demonstrate that SAW is an effective way of switching synchronization mechanisms according to the characteristics of each application.

Existing work that deals with parallelization of complicated reductions and scans focuses only on formalism and hardly dealt with implementation. To bridge the gap between formalism and implementation, we have integrated parallelization via matrix multiplication into compiler construction. Our framework can deal with complicated loops that existing techniques in compilers cannot parallelize. Moreover, we have sophisticated our framework by developing two sets of techniques. One enhances its capability for parallelization by extracting max-operators automatically, and the other improves the performance of parallelized programs by eliminating redundancy. We have also implemented our framework and techniques as a parallelizer in a compiler. Experiments on examples that existing compilers cannot parallelize have demonstrated the scalability of programs parallelized by our implementation.

We have developed an incremental compacting garbage collector for embedded Java systems. The collector divides the heap into equal sized pages and uses the segregated free lists for fast allocation. Collectors that have such a heap layout have a problem of fragmentation in allocating objects larger than the page size. We solve this problem by using the replication-based incremental compaction. The compactor evacuates all objects in one area, the evacuation area, of the heap, thereby creating a large chunk of free space. We developed an algorithm for choosing the evacuation area that effectively cures fragmentation. The compactor does not use any read-barriers. Instead, it uses a technique similar to the replication-based incremental copying collection. This needs forwarding pointers for all evacuated objects. Rather than introducing an extra field for each object, we use a hash table to store forwarding pointers.

A parallel skeleton library is a collection of parallel computations that abstract generic and recurring patterns within parallel programs and conceal parallel behaviors as skeletons. It enables users to develop parallel programs as if they were sequential ones by composing suitable skeletons. However, many existing parallel skeleton libraries for distributed environments do not take into account the potential performance of multi-core CPUs, because they operate under the premise that each node (computer) has a single-core CPU. To resolve this problem, this paper proposes the design and implementation of a parallel skeleton library for multi-core clusters. The proposed library adopts a two-stage dynamic task scheduling strategy; the first is among nodes and the second is among cores. This scheduling strategy enables the library to appropriately balance the load both between nodes and cores. The library also dynamically fuses successive skeleton calls to reduce the cost of control flows and increase the locality of data. The proposed skeletons are implemented from scratch for matrices within a parallel skeleton library called SkeTo by using the template techniques in C++ language. We confirmed that our implementation was efficient through various benchmarks.

Abstract Apache web servers are widely used as stand‐alone servers or front‐ends in multi‐tiered web servers. Despite the wide availability of software, it is quite difficult for many administrators to properly configure their web servers. In particular, setting the performance‐related parameters is an error‐prone and time‐consuming task because their values heavily depend on the server environment. In this paper, two mechanisms are described for automatically tuning two performance‐related parameters of Apache web servers:KeepAliveTimeoutandMaxClients. These mechanisms are easy to deploy because no modifications to the server or the operating system are required. Moreover, they are parameter specific. Although interference betweenKeepAliveTimeoutandMaxClientsis inevitable, the tuning mechanisms minimize the correlation by using almost completely independent metrics. Experimental results show that these mechanisms work well for two different workloads; the parameter values are close to optimal and can adapt to workload changes. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract TEX allows users to define a macro that abstracts a sequence of typesetting commands. However, defining macros is not easy for most users, because the mechanism of macro expansion in TEX is complicated. As a remedy for this situation, a new system that enables users to define macros for TEX documents as Lisp programs has been developed. The system acts as a preprocessor for TEX; given a document that contains Lisp programs as S‐expressions, the system expands each S‐expression on the basis of Lisp's evaluation rules, thus generating an ordinary TEX document. The system is very flexible and easy‐to‐use, thanks to the underlying language's general‐purpose data structure, i.e. the S‐expression, applicative order evaluation, and rich set of predefined functions. This paper also demonstrates that the proposed system is really effective for practical use by giving some concrete examples of Lisp macros, some of which are difficult to define in terms of TEX commands. The system is currently implemented on the Emacs Lisp, and a user‐friendly environment is thus available in the Emacs text editor. Copyright © 2002 John Wiley & Sons, Ltd.

Tupling is a well-known transformation tactic to obtain new efficient recursive functions by grouping some recursive functions into a tuple. It may be applied to eliminate multiple traversals over the common data structure. The major difficulty in tupling transformation is to find what functions are to be tupled and how to transform the tupled function into an efficient one. Previous approaches to tupling transformation are essentially based on fold/unfold transformation. Though general, they suffer from the high cost of keeping track of function calls to avoid infinite unfolding, which prevents them from being used in a compiler.To remedy this situation, we propose a new method to expose recursive structures in recursive definitions and show how this structural information can be explored for calculating out efficient programs by means of tupling. Our new tupling calculation algorithm can eliminate most of multiple data traversals and is easy to be implemented.

It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm. However, they have been usually treated rather informally and ad hoc in the development of efficient parallel programs. What is worse is that some interesting functions, e.g., the maximum segment sum problem, are basically not list homomorphisms. In this article, we propose a systematic and formal way for the construction of a list homomorphism for a given problem so that an efficient parallel program is derived. We show, with several well-known but nontrivial problems, how a straightforward, and “obviously” correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent “almost list homomorphism.” The derivation is based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.

... this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.