Mohamed Mohamedin
email: mohamedin@vt.edu

Binoy Ravindran

Roberto Palmieri
email: robertop@vt.edu

ByteSTM: Virtual Machine-level Java Software Transactional Memory

We present ByteSTM, a virtual machine-level Java STM implementation that is built by extending the Jikes RVM. We modify Jikes RVM's optimizing compiler to transparently support implicit transactions. Being implemented at the VM-level, it accesses memory directly, avoids Java garbage collection overhead by manually managing memory for transactional metadata, and provides pluggable support for implementing different STM algorithms to the VM. Our experimental studies reveal throughput improvement over other non-VM STMs by 6-70% on micro-benchmarks and by 7-60% on macro-benchmarks.

Introduction

Transactional Memory (TM) [START_REF] Harris | Transactional Memory, 2nd Edition[END_REF] is an attractive programming model for multicore architectures promising to help the programmer in the implementation of parallel and concurrent applications. The developer can focus the effort on the implementation of the application's business logic, giving the responsibility to managing concurrency to the TM framework. It ensures, in a completely transparent manner, properties difficult to implement manually like atomicity, consistency, deadlock-freedom and livelock-freedom. The programmer simply organizes the code identifying blocks to be executed as transactions (so called atomic blocks). TM overtakes the classical coarse grain lock-based implementation of concurrency, executing transactions optimistically and logging into a private part of the memory the results of read and write operations performed during the execution (respectively on the read-and write-set). Further TM is composable.

TM has been proposed in hardware (HTM; e.g., [START_REF] Christie | Evaluation of AMD's advanced synchronization facility within a complete transactional memory stack[END_REF]), in software (STM; e.g., [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF]), and in combination (HybridTM; e.g., [START_REF] Lie | Hardware support for unbounded transactional memory[END_REF]). HTM has the lowest overhead, but transactions are limited in space and time. STM does not have such limitations, but has higher overhead. HybridTM avoids these limitations.

Given STM's hardware-independence, which is a compelling advantage, we focus on STM. STM implementations can be classified into three categories: library-based, compiler-based, and virtual machine-based. Library-based STMs add transactional support without changing the underlying language, and can be classified into those that use explicit transactions [START_REF] Herlihy | A flexible framework for implementing software transactional memory[END_REF][START_REF]ObjectFabric[END_REF][START_REF] Veentjer | Multiverse[END_REF] and those that use implicit transactions [START_REF] Cachopo | Versioned boxes as the basis for memory transactions[END_REF][START_REF] Korland | Noninvasive concurrency with Java STM[END_REF][START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF]. Explicit transactions are difficult to use. They support only transactional objects (i.e., objects that are known to the STM library by implementing a specific interface, being annotated, etc) and hence cannot work with external libraries. Implicit transactions, on the other hand, use modern language features (e.g., Java annotations) to mark code sections as atomic. Instrumentation is used to transparently add transactional code to the atomic sections (e.g., begin, transactional reads/writes, commit). Some implicit transactions work only with transactional objects [START_REF] Cachopo | Versioned boxes as the basis for memory transactions[END_REF][START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF], while others work on any object and support external libraries [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF].

Compiler-based STMs (e.g., [START_REF] Hindman | Atomicity via source-to-source translation[END_REF][START_REF]Intel C++ STM Compiler[END_REF]) support implicit transactions transparently by adding new language constructs (e.g., atomic). The compiler then generates transactional code that calls the underlying STM library. Compiler-based STMs can optimize the generated code and do overall program optimization. On the other hand, compilers need external libraries' source code to instrument it and add transactional support. Usually, external libraries source code is not available. With managed run-time languages, compilers alone do not have full control over the VM. Thus, the generated code will not be optimized and may contradict with some of the VM features like the garbage collector (GC).

VM-based STMs, which have been less studied, include [START_REF] Adl-Tabatabai | The StarJIT compiler: A dynamic compiler for managed runtime environments[END_REF][START_REF] Carlstrom | The Atomos transactional programming language[END_REF][START_REF] Harris | Language support for lightweight transactions[END_REF][START_REF] Welc | Transactional monitors for concurrent objects[END_REF]. [START_REF] Harris | Language support for lightweight transactions[END_REF] is implemented in C inside the JVM to get benefits of the VM-managed environment, and uses an algorithm that does not ensure the opacity correctness property [START_REF] Guerraoui | On the correctness of transactional memory[END_REF]. This means that inconsistent reads may occur before a transaction is aborted, causing unrecoverable errors in an unmanaged environment. Thus, the VM-level implementation choice is to prevent such unrecoverable errors, which are not allowed in a managed environment. [START_REF] Carlstrom | The Atomos transactional programming language[END_REF] presented a new Java-based programming language called Atomos, and a concomitant VM where standard Java synchronization (i.e., synchronized, wait/notify) is replaced with transactions. However, in this work, transactional support relies on HTM.

Library-based STMs are largely based on the premise that it is better not to modify the VM or the compiler, to promote flexibility, backward compatibility with legacy code, and easiness to deploy and use. However, this premise is increasingly violated as many require some VM support or are being directly integrated into the language and thus the VM. Most STM libraries are based on annotations and instrumentation, which are new features in the Java language. For example, the Deuce STM library [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF] uses a non-standard proprietary API (i.e., sun.misc.Unsafe) for performance gains, which is incompatible with other JVMs. Moreover, programming languages routinely add new features in their evolution for a whole host of reasons. Thus, as STM gains traction, it is natural that it will be integrated into the language and the VM.

Implementing STM at the VM-level allows many opportunities for optimization and adding new features. For example, the VM has direct access to memory, which allows faster write-backs to memory. The VM also has full control of the GC, which allows minimizing the GC's degrading effect on STM performance (see Subsection 2.5). Moreover, if TM is supported using hardware (as in [START_REF] Carlstrom | The Atomos transactional programming language[END_REF]), then VM is the only appropriate level of abstraction to exploit that support for obtaining higher performance. (Otherwise, if TM is supported at a higher level, the GC will abort transactions when it interrupts them.) Also, VM memory systems typically use a centralized data structure, which increases conflicts, degrading performance [START_REF] Bradel | The use of hardware transactional memory for the trace-based parallelization of recursive Java programs[END_REF].

Feature

Deuce [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF] JVSTM [START_REF] Cachopo | Versioned boxes as the basis for memory transactions[END_REF] ObjectFabric [START_REF]ObjectFabric[END_REF] AtomJava [START_REF] Hindman | Atomicity via source-to-source translation[END_REF] DSTM2 [START_REF] Herlihy | A flexible framework for implementing software transactional memory[END_REF] Multiverse [START_REF] Veentjer | Multiverse[END_REF] LSA-STM [START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF] Motivated by these observations, we design and implement a VM-level STM: ByteSTM. In ByteSTM, a transaction can surround any block of code, and it is not restricted to methods. Memory bytecode instructions reachable from a transaction are translated so that the resulting native code executes transactionally. ByteSTM uniformly handles all data types (not just transactional objects), using the memory address and number of bytes as an abstraction, and thereby supports external libraries. It uses field-based granularity, which scales better than object-based or word-based granularity, and eliminates the GC overhead, by manually managing (e.g., allocation, deallocation) memory for transactional metadata. It can work without compiler support, which is only required if the new language construct atomic is used. ByteSTM has a modular architecture, which allows different STM algorithms to be easily plugged in (we have implemented three algorithms: TL2 [START_REF] Dice | Transactional Locking II[END_REF], RingSTM [START_REF] Spear | RingSTM: scalable transactions with a single atomic instruction[END_REF], and NOrec [START_REF] Dalessandro | NOrec: Streamlining STM by Abolishing Ownership Records[END_REF]). ByteSTM is open-sourced and is freely available at hydravm.org/bytestm.

Design and Implementation

ByteSTM is built by modifying Jikes RVM [START_REF] Alpern | The Jikes research virtual machine project: building an open-source research community[END_REF] using the optimizing compiler.

Jikes RVM is a Java research virtual machine and it is implemented in Java.

Jikes RVM has two types of compilers: the Optimizing compiler and the Baseline compiler. The Baseline compiler simulates the Java stack machine and has no optimization. The Optimizing compiler does several optimizations (e.g., register allocation, inlining, code reordering). Jikes RVM has no interpreter, and bytecode must be compiled to native code before execution. Building the Jikes RVM with production configuration gives performance comparable to the HotSpot server JIT compiler [START_REF] Paleczny | The Java Hotspot TM Server Compiler[END_REF].

In ByteSTM, bytecode instructions run in two modes: transactional and nontransactional. The visible modifications to VM users are very limited: two new instructions (xBegin and xCommit) are added to the VM bytecode instructions. These two instructions will need compiler modifications to generate the correct bytecode when atomic blocks are translated. Also, the compiler should handle the new keyword atomic correctly. To eliminate the need for a modified compiler, a simpler workaround is used: the method stm.STM.xBegin() is used to begin a transaction and stm.STM.xCommit() is used to commit the transaction. The two methods are defined empty and static in class STM in stm package.

ByteSTM is implicitly transactional: the program only specifies the start and end of a transaction and all memory operations (loads and stores) inside these boundaries are implicitly transactional. This simplifies the code inside the atomic block and also eliminates the need for making a transactional version for each memory load/store instruction, thereby keeping the number of added instructions minimal. When xBegin is executed, the thread enters the transactional mode. In this mode, all writes are isolated and the execution of the instructions proceeds optimistically until xCommit is executed. At that point, the transaction is compared against other concurrent transactions for a conflict. If there is no conflict, the transaction is allowed to commit and, only at this point, all transaction modifications become externally visible to other transactions. If the commit fails, all the modifications are discarded and the transaction restarts from the beginning.

We modified the Jikes optimizing compiler. Each memory load/store instruction (getfield, putfield, getstatic, putstatic, and all array access instructions) is replaced with a call to a corresponding method that adds the transactional behavior to it. The compiler inlines these methods to eliminate the overhead of calling a method with each memory load/store. The resulting behavior is that each instruction checks whether the thread is running in transactional or non-transactional mode. Thus, instruction execution continues transactionally or non-transactionally. The technique is used to translate the new instructions xBegin and xCommit (or replacing calls to stm.STM.xBegin() and stm.STM.xCommit() with the correct method calls).

Modern STMs [START_REF] Cachopo | Versioned boxes as the basis for memory transactions[END_REF][START_REF] Korland | Noninvasive concurrency with Java STM[END_REF][START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF] use automatic instrumentation. Java annotations are used to mark methods as atomic. The instrumentation engine then handles all code inside atomic methods and modifies them to run as transactions. This conversion does not need the source code and can be done offline or online. Instrumentation allows using external libraries -i.e., code inside a transaction can call methods from an external library, which may modify program data [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF].

In ByteSTM, code that is reachable from within a transaction is compiled to native code with transactional support. Classes/packages that will be accessed transactionally are input to the VM by specifying them on the command line. Then, each memory operation in these classes is translated by first checking the thread's mode. If the mode is transactional, the thread runs transactionally; otherwise, it runs regularly. Although doing such a check with every memory load/store operation increases overhead, our results show significant throughput improvement over competitor STMs (see Section 3).

Atomic blocks can be used anywhere (excluding blocks containing irrevocable operations such as I/O). It is not necessary to make a whole method atomic; any block can be atomic. External libraries can be used inside transactions without any change.

Memory access is monitored at the field level, and not at the object level. Field-based granularity scales well and eliminates false conflicts resulting from two transactions changing different fields of the same object [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF].

Metadata

Working at the VM level allows changing the thread header without modifying program code. For each thread that executes transactions, the metadata added includes the read-set, the write-set, and other STM algorithm-specific metadata. Metadata is added to the thread header and is used by all transactions executed in the thread. Since each thread executes one transaction at a time, there is no need to create new data for each transaction, allowing reuse of the metadata. Also, accessing a thread's header is faster than Java's ThreadLocal abstraction.

Memory Model

At the VM-level, the physical memory address of each object's field can be easily obtained. Since ByteSTM is field-based, the address of each field is used to track memory reads and writes. A conflict occurs only if two transactions modified the same field of an object. Since arrays are objects in Java, memory accesses to arrays are tracked at the element level, which eliminates unnecessary aborts.

An object instance's field's absolute address equals the object's base address plus the field's offset. A static object's field's absolute address equals the global static memory space's address plus the field's offset. Finally, an array's element's absolute address equals the array's address plus the element's index in the array (multiplied by the element's size). Thus, our memory model is simplified as: base object plus an offset for all cases.

Using absolute addresses is limited to non-moving GC only (i.e., a GC which releases unreachable objects without moving reachable objects, like the markand-sweep GC). In order to support moving GC, a field is represented by its base object and the field's offset within that object. When the GC moves an object, only the base object's address is changed. All offsets remain the same. ByteSTM's write-set is part of the GC root-set. Thus, the GC automatically changes the saved base objects' addresses as part of its reference updating phase.

To simplify how the read-set and the write-set are handled, we use a unified memory access scheme. At a memory load, the information needed to track the read includes the base object and the offset within that object of the read field. At a memory store, the base object, the field's offset, the new value, and the size of the value are the information used to track the write. When data is written back to memory, the write-set information (base object, offset, value, and length of the location) is used to store the committed values correctly. This abstraction also simplifies the code, as there is now no need to differentiate between different data types, as they are all handled as a sequence of bytes in the memory. The result is simplified code that handles all the data types the same, yielding faster execution.

Write-set Representation

We found that using a complex data structure to represent read-sets and writesets affects performance. Given the simplified raw memory abstraction used in ByteSTM, we decided to use simple arrays of primitive data types. This decision is based on two reasons. First, array access is very fast and has access locality, resulting in better cache usage. Second, with primitive data types, there is no need to allocate a new object for each element in the read/write set. (Recall that an array of objects is allocated as an array of references in Java, and each object needs to be allocated separately. Hence, there is a large overhead for allocating memory for each array element.) Even if object pooling is used, the memory will not be contiguous since each object is allocated independently in the heap.

Using arrays to represent the write-set means that the cost of searching an n-element write-set is O(n). To obtain the benefits of arrays and hashing's speed, open-addressing hashing with linear probing is used. We used an array of size 2 n , which simplifies the modulus calculation.

We used Java's System.identityHashCode standard method and configured Jikes to use the memory address to compute an object's hash code. This method also handles object moving. We then add the field's offset to the returned hash code, and finally remove the upper bits from the result using bitwise and operation (which is equivalent to calculating the modulus): address AND mask = address MOD arraySize, where mask = arraySize -1. For example, if arraySize = 256, then hash(address) = address AND 0xFF. This hashing function is efficient with addresses, as the collision ratio is small. Moreover, as program variables are aligned in memory, when a collision happens, there is always an empty cell

Base Object

Value Size Offset Objects An Object Entry Index after the required index because of the memory alignment gap (so linear probing will give good results). This way, we have a fast and efficient hashing function that adds little overhead to each array access, enabling O(1)-time searching and adding operations on large write-sets.

Iterating over the write-set elements by cycling through the sparse array elements is not efficient. We solve this by keeping a contiguous log of all the used indices, and then iterating on the small contiguous log entries.

Open addressing has two drawbacks: memory overhead and rehashing. These can be mitigated by choosing the array size such that the number of rehashing is reduced, while minimizing memory usage. Figure 1 shows how ByteSTM's write-set is represented using open-addressing. In this figure, the field's memory address is hashed to determine the associated index in the array. Four entries are occupied in the shown array (identified by gray color) and they are scattered by the hashing function into different locations in the array. The index table contains all used indices in the main array contiguously for faster sequential access to the write-set entries. Reference fields (object entries) are handled differently as described in Subsection 2.5.

Atomic Blocks

ByteSTM supports atomic blocks anywhere in the code, excluding I/O operations and JNI native calls. When xBegin is executed, local variables are backed up. If a transaction is aborted, the variables are restored and the transaction can restart as if nothing has changed in the variables. This technique simplifies the handling of local variables since there is no need to monitor them.

ByteSTM has been designed to natively support opacity [START_REF] Guerraoui | On the correctness of transactional memory[END_REF]. In fact, when an inconsistent read is detected in a transaction, the transaction is immediately aborted. Local variables are then restored, and the transaction is restarted by throwing an exception. The exception is caught just before the end of the transaction loop so that the loop continues again. Note that throwing an exception is not expensive if the exception object is preallocated. Preallocating the exception object eliminates the overhead of creating the stack trace every time the exception is thrown. Stack trace is not required for this exception object since it is used only for doing a long jump. The result is similar to setjmp/longjmp in C.

Garbage Collector

One major drawback of building an STM for Java (or any managed language) is the GC [START_REF] Meawad | Collecting transactional garbage[END_REF]. STM uses metadata to keep track of transactional reads and writes. This requires allocating memory for the metadata and then releasing it when not needed. Frequent memory allocation (and implicit deallocation) forces the GC to run more frequently to release unused memory, increasing STM overhead. Some STMs solve this problem by reducing memory allocation and recycling allocated memory. For example, [START_REF] Korland | Noninvasive concurrency with Java STM[END_REF] uses object pooling, wherein objects are allocated from, and recycled back to a pool of objects (with the heap used when the pool is exhausted). However, allocation is still done through the Java memory system and the GC checks if the pooled objects are still referenced.

Since ByteSTM is integrated into the VM, its memory allocation and recycling is done outside the control of the Java memory system: memory is directly allocated and recycled. STM's memory requirement, in general, has a specific lifetime. When a transaction starts, it requires a specific amount of metadata, which remain active for the transaction's duration. When the transaction commits, the metadata is recycled. Thus, manual memory management does not increase the complexity or overhead of the implementation.

The GC causes another problem for ByteSTM, however. ByteSTM stores intermediate changes in a write buffer. Thus, the program's newly allocated objects will not be referenced by the program's variables. The GC scans only the program's stack to find objects that are no longer referenced. Hence, it will not find any reference to the newly allocated objects and will recycle their memory. When ByteSTM commits a transaction, it will therefore be writing a dangling pointer. We solve this problem by modifying the behavior of adding an object to the write-set. Instead of storing the object address in the writeset entry value, the object is added to another array (i.e., an "objects array"). The object's index in the objects array is stored in the write-set entry value (Figure 1). Specifically, if an object contains another object (e.g., a field that is a reference), we cannot save the field value as a primitive type (e.g., the absolute address) since the address can be changed by the GC. The field value is therefore saved as an object in the objects array which is available to the set of roots that the GC scans. The write-set array is another source of roots. So, the write-set contains the base objects and the objects array contains the object fields within the base objects. This prevents the GC from reclaiming the objects. Our approach is compatible with all GC available in Jikes RVM and we believe that this approach is better than modifying a specific GC.

STM Algorithms

ByteSTM's modular architecture allows STM algorithms to be easily "plugged in." We implemented three algorithms: TL2 [START_REF] Dice | Transactional Locking II[END_REF], RingSTM [START_REF] Spear | RingSTM: scalable transactions with a single atomic instruction[END_REF], and NOrec [START_REF] Dalessandro | NOrec: Streamlining STM by Abolishing Ownership Records[END_REF]. Our rationale for selecting these three is that, they are the best performing algorithms reported in the literature. Additionally, they cover different points in the performance/workload tradeoff space: TL2 is effective for long transactions, moderate number of reads, and scales well with large number of writes. RingSTM is effective for transactions with high number of reads and small number of writes. NOrec has a better performance with small number of cores and has no false conflicts since it validates by value.

Plugging a new algorithm in ByteSTM is straight forward. One needs to implement read barriers, write barriers, transaction start, transaction end, and any other algorithm specific helping methods. All these methods are in one class "STM.java". No prior knowledge of Jikes RVM is required and porting a new algorithm to ByteSTM requires only understanding ByteSTM framework.

Experimental Evaluation

To understand how ByteSTM, a VM-level STM, stacks up against non VM-level STMs, we conducted an extensive experimental study. Though a VM-level implementation may help improve STM performance, the underlying STM algorithm used also plays an important role, especially, when that algorithm's performance is known to be workload-dependent (see Subsection 2.6). Thus, the performance study wants also to investigate whether any performance gain from a VM-level implementation is algorithm-independent. It would also be interesting to understand whether some algorithms gained more than others, and if so, why. Thus, we compare ByteSTM against non-VM STMs, with the same algorithm inside the VM versus "outside" it.

Our competitor non-VM STMs include Deuce, ObjectFabric, Multiverse, and JVSTM. Since some of these STMs use different algorithms (e.g., Multiverse uses TL2's modified version; JVSTM uses a multi-version algorithm) or different implementations, a direct comparison between them and ByteSTM has some degree of unfairness. This is because, such a comparison will include many combined factors-e.g., ByteSTM's TL2 implementation is similar to Deuce's TL2 implementation, but the write-set and memory management are different. Therefore, it will be difficult to conclude that ByteSTM's (potential) gain is directly due to VM-level STM implementation. Therefore, we implemented a non-VM version using TL2, RingSTM and NOrec algorithms as Deuce plug-ins. Comparing ByteSTM with such a non-VM implementation reduces the factors in the comparison.

The non-VM implementations were made as close as possible to the VM ones. Offline instrumentation was used to eliminate online instrumentation overhead. The same open-address hashing write set was used. A large read-set and write-set were used so that they were sufficient for the experiments without requiring extra space. The sets were recycled for the next transactions, thereby needing only a single memory allocation and thus minimizing the GC overhead. We used Deuce for the non-VM implementation, since it has many of ByteSTM's features -e.g., it directly accesses memory and uses field granularity. Moreover, it achieved the best performance among all competitors (see results later in this section).

Test Environment

We used a 48-core machine, which has four AMD Opteron TM Processors, each with 12 cores running at 1700 MHz, and 16 GB RAM. The machine runs Ubuntu Linux 10.04 LTS 64-bit. We used Jikes's production configuration (version 3.1.2), which includes the Jikes optimizing compiler and the GenImmix GC [START_REF] Blackburn | Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance[END_REF] (i.e., a two-generation copying GC) and matches ByteSTM configurations. Since Deuce uses a non-standard proprietary API, sun.misc.Unsafe, which is not fully supported by Jikes, to run Deuce atop Jikes RVM, we added the necessary methods to Jikes RVM's sun.misc.Unsafe implementation (e.g., getInt, putInt, etc).

Our test applications include both micro-benchmarks (i.e., data structures) and macro-benchmarks. The micro-benchmarks include Linked-List, Skip-List, Red-Black Tree, and Hash Set. The macro-benchmarks include five applications from the STAMP suite [START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF]: Vacation, KMeans, Genome, Labyrinth, and Intruder. We used Arie Zilberstein's Java implementation of STAMP [START_REF] Zilberstein | Java implementation of STAMP[END_REF].

For the micro-benchmarks, we measured the transactional throughput (i.e., transactions committed per second). Thus, higher is better. For the macrobenchmarks, we measured the core program execution time, which includes transactional execution time. Thus, smaller is better. Each experiment was repeated 10 times, and each time, the VM was "warmed up" (i.e., we let the VM run for some time without logging the results) before taking the measurements. We show the average for each data point. Due to space constraints, we only show results for Linked-List, Red-Black Tree, Vacation, Intruder, and Labyrinth (see [START_REF] Mohamedin | ByteSTM: Virtual Machine-level Java Software Transactional Memory[END_REF] for complete results).

Micro-Benchmarks

We converted the data structures from coarse-grain locks to transactions. The transactions contain all the critical section code in the coarse-grain lock version.

Each data structure is used to implement a sorted integer set interface, with set size 256 and set elements in the range 0 to 65536. Writes represent add and remove operations, and they keep the set size approximately constant during the experiments. Different ratios of writes and reads were used to measure performance under different levels of contention: 20% and 80% writes. We also varied the number of threads in exponential steps (i.e., 1, 2, 4, 8, ...), up to 48.

Linked List. Linked-list operations are characterized by high number of reads (the range is from 70 at low contention to 270 at high contention), due to traversing the list from the head to the required node, and a few writes (about 2 only). This results in long transactions. Moreover, we observed that transactions suffer from high number of aborts (abort ratio is from 45% to 420%), since each transaction keeps all visited nodes in its read-set, and any modification to these nodes by another transaction's add or remove operation will abort the transaction. Figure 2 shows the results. ByteSTM has three curves: RingSTM, TL2, and NOrec. In all cases, ByteSTM/NOrec achieves the best performance since it uses an efficient read-set data structure based on open addressing hashing. ByteST-M/RingSTM comes next since it has no read-set and it uses a bloom filter as a read signature, but the performance is affected by bloom filter's false positives. This is followed by ByteSTM/TL2 which is affected by its sequential read-set. Deuce's performance is the best between other STM libraries. Other STMs perform similarly, and all of them have very low throughput. Non-VM implementation of each algorithm performs in a similar manner but with lower throughput. ByteSTM outperforms non-VM implementations by 15-70%.

Since Deuce/TL2 achieved the best performance among all other STMs, for all further experiments, we use Deuce as a fair competitor against ByteSTM to avoid clutter, along with the non-VM implementations of TL2, RingSTM and NOrec. Accordingly, in the rest of the plots the curves of JVSTM, Multiverse and Object Fabric will be dropped (simplifying also the legibility).

Red-black Tree. Here, operations are characterized by small number of reads (15 to 30), and small number of writes (2 to 9), which result in short transactions.

Figure 3 shows the results. In all cases, ByteSTM/TL2 achieves the best performance and scalability due to the small number of reads. ByteSTM/NOrec does not scale well since it is based on one single global lock. Moreover, the small size of the tree creates a high contention between the threads. RingSTM's performance is similar to NOrec as it is based on a global data structure and has the added overhead of bloom's filter false positives.

In this benchmark, there is no big gap between ByteSTM and non-VM implementation due to the nature of the benchmark, namely very short transactions over a small data structure by large number of threads. ByteSTM outperforms non-VM implementation by 6-17%.

Macro Benchmark

Vacation. Vacation has medium-length transactions, medium read-sets, medium write-sets, and long transaction times (compared with other STAMP benchmarks). We conducted two experiments: low contention and high contention. Figure 4 shows the results. Note that, here, the y-axis represents the time taken to complete the experiment, and the x-axis represents the number of threads. ByteSTM/NOrec has the best performance under both low and high contention conditions. The efficient read-set implementation contributed to its performance. But, it does not scale well. ByteSTM/RingSTM suffers from high number of aborts due to false positives and long transactions so it started with a good performance then degrades quickly. ByteSTM outperforms non-VM implementations by an average of 15.7% in low contention and 18.3% in high contention.

Intruder. The Intruder benchmark [START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF] is characterized by short transaction lengths, medium read-sets, medium write-sets, medium transaction times, and high contention. Figure 5(a) shows the results. We observe that ByteSTM/NOrec achieves best performance but does not scale. ByteSTM/RingSTM suffers from increased aborts due to false positives. ByteSTM/TL2 has a moderate performance. ByteSTM outperforms non-VM implementations by an average of 11%.

Labyrinth. The Labyrinth benchmark [START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF] is characterized by long transaction lengths, large read-sets, large write-sets, long transaction times, and very high contention.

Figure 5(b) shows the results. ByteSTM/NOrec achieves the best performance. ByteSTM/RingSTM suffers from extremely high number of aborts due to false positives and long transactions, and shows no scalability. All algorithms suffered from the high contention and has very low scalability. ByteSTM outperforms non-VM implementation by an average of 18.5%.

Summary

ByteSTM improves over non-VM implementations by an overall average of 30%: on micro-benchmarks, it improves by 6 to 70%; on macro-benchmarks, it improves by 7 to 60%. Moreover, scalability is better. ByteSTM, in general, is better when the abort ratio and contention are high.

RingSTM performs well, irrespective of reads. However, its performance is highly sensitive to false positives when writes increases. TL2 performs well when reads are not large due to its sequential read-set implementation. It also performs and scales well when writes increases. NOrec performs the best with behavior similar to RingSTM as it does not suffer from false positives, but it does not scale.

Algorithms that uses a global data structure and small number of CAS operations (like NOrec and RingSTM) have a bigger gain when implemented at VM-level. TL2 that uses a large number of locks (e.g., Lock table) and hence large number of CAS operations did not gain a lot from VM-level implementation.

Conclusions

Our work shows that implementing an STM at the VM-level can yield significant performance benefits. This is because at the VM-level: i) memory operations are faster; ii) the GC overhead is eliminated; iii) STM operations are embedded in the generated native code; iv) metadata is attached to the thread header.

For all these reasons the overhead of STM is minimized. Since the VM has full control over all transactional and non-transactional memory operations, features such as strong atomicity and irrevocable operations (not currently supported) can be efficiently supported.

These optimizations are not possible at a library-level. A compiler-level STM for managed languages also cannot support these optimizations. Implementing an STM for a managed language at the VM-level is likely the most performant.

Next steps for ByteSTM are exploring compile time optimization specific for STM (i.e., STM optimization pass). And, modify the thread scheduler so that it will be STM aware and reduces the conflicts rate.

ByteSTM is open-sourced and is freely available at hydravm.org/bytestm. A modified version of ByteSTM is currently used in the HydraVM project [START_REF] Saad | HydraVM: extracting parallelism from legacy sequential code using STM[END_REF], which is exploring automated concurrency refactoring in legacy code using TM.

Fig. 1 .

 1 Fig. 1. ByteSTM's write-set using open address hashing.

Fig. 2 .

 2 Fig. 2. Throughput for Linked-List.

Fig. 3 .

 3 Fig. 3. Throughput of Red-Black Tree.

Fig. 4 .

 4 Fig. 4. Execution time under Vacation.

Fig. 5 .

 5 Fig. 5. Execution time under (a) Intruder, and (b) Labyrinth.

Table 1 .

 1 Comparison of Java STM implementations.

Table 1 distinguishes

 1 ByteSTM from other STM implementations. The current release of ByteSTM does not support closed/open nesting, strong atomicity, or conditional variables. However, features like these are in the implementation roadmap.

No GC overhead √ 5 X X X X X X √ √ X √ Compiler support X X X √ X X X √ √ √ √ & X 6 Strong atomicity X X √ √ X X X X √ X X Closed/Open nesting X √ √ X X X X X √ X X Conditional variables X X X X X X X X √ X X 1Is a HybridTM, but software part is implemented inside a VM.[START_REF] Alpern | The Jikes research virtual machine project: building an open-source research community[END_REF] Only if source code is available.[START_REF] Blackburn | Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance[END_REF] It is a new language, thus no Java code is supported.[START_REF] Bradel | The use of hardware transactional memory for the trace-based parallelization of recursive Java programs[END_REF] Uses non-standard library.[START_REF] Cachopo | Versioned boxes as the basis for memory transactions[END_REF] Uses object pooling, which partially solves the problem.[START_REF] Cao Minh | STAMP: Stanford transactional applications for multi-processing[END_REF] ByteSTM can work with or without compiler support.

Acknowledgments. This work is supported in part by US National Science Foundation under grants CNS 0915895, CNS 1116190, CNS 1130180, and CNS 1217385. A short version of this paper appeared as Brief Announcement at 2013 TRANSACT workshop. TRANSACT does not have archival proceedings and explicitly encourages resubmissions to formal venues.


Dries Harnie Laure Philips
email: lphilips@vub.ac.be

Kevin Pinte
email: kpinte@vub.ac.be

Wolfgang De Meuter
email: wdmeuter@vub.ac.be

Event Loop Coordination Using Meta-programming

Keywords: Event loops, Coordination model, Mobile platforms, Ambientoriented programming

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In traditional programming the control flow of a program is determined by its structure. To allow the program to react upon input in the of form events, the event-based programming paradigm can be used. The programmer registers observers or event handlers for different types of events and the event loop is responsible for detecting events and dispatching it to the observers. This programming paradigm is popular for developing user interfaces, where the program reacts upon input from the user. Event-based programming proves to be useful in distributed programming, where the source of an event and the matching event handler can live on different devices. When developing a larger software system, composed out of different event-based subsystems, the programmer needs to manually coordinate these event loops. Because the event loops have different characteristics, take for example the start-up time, it is up to the programmer to take care of the mismatch between the event loops. Current systems only address this issue partially; they do not take into account the lifecycle of event loops. Some event loops are prey to lifecycle state changes, meaning that an event loop can be shut down at any moment in time and maybe restarted afterwards. For example, mobile applications, which often use event loops, can be shut down when running in the background. Typically, the programmer can react upon lifecycle state changes, e.g. pause a playing video when the application is no longer visible to the user. These changes have consequences: a destroyed event loop is no longer accessible and other event loops in the system thus must be aware of the lifecycle state of that event loop. In this paper, we introduce a coordination model called "Elector", which allows different types of event loops to be coordinated. The model enables programmers to concentrate on the logic of the program, instead of writing glue code for the event loops. The main concept behind Elector are its undead references, which transparently handle these lifecycle problems. We contribute the design and implementation of Elector, as a framework for the AmbientTalk language. We also provide a validation of our approach by comparing the code complexity of different versions of a representative application. Finally, we present a validation of Elector's performance measurements. This paper is organised as follows: we first discuss related work in section 2 after which we introduce a motivating example (section 3). Afterwards we discuss the problems that arise when implementing this case study in section 4. In section 5 we present "Elector", together with a concrete implementation for Android and AmbientTalk. Section 6 evaluates the Elector model by comparing the different implementations of our motivating example. Finally we conclude this paper and present future work.

Related Work

In this section we discuss related work: other models that encapsulate one of the event loops and component-based software architectures, which are tailored towards systems with different sub-components.

Event Loop Encapsulation

Often when integrating different subsystems into a new and larger system, one ends up with excessive code size. This is because the subsystems make certain assumptions about the system in which they are used [START_REF] Garlan | Architectural Mismatch, or, Why its hard to build systems out of existing parts[END_REF]. For example, when combining different event-based systems that are not compatible with each other, the programmer must adapt one or more event loops. The models we discuss allow the coordination of event loops, by encapsulating their own native event loop inside an external one and allowing the native event loop to handle its events at a regular basis. As a consequence, when an event handler does not end immediately or not at all, the entire application is blocked and not only one of the subparts. These models solve the communication issues related to combining event loops, but do not take into account the possible lifecycle state changes of these event loops. POE (Perl Object Environment) [1] is an event-based Perl framework for reactive systems, cooperative multitasking and network applications. POE provides bridges for other event loops that normally need complete control, for example GTK. Such a bridge between an external event loop and the POE event loop runs the external event loop and uses timer functions to allow the POE event loop to handle its events periodically.

Tcl (Tool Command Language) [START_REF] Brent | Practical programming in Tcl and TK[END_REF] is a cross platform programming language that can be used in different domains: web applications, desktop applications, etc. The Tcl event loops provides mechanisms that allow the programmer to have a more fine-grained control over the event mechanism. This way, one can embed a Tcl event loop inside applications that have their own event loop.

Component-based Software Architectures

ROS (Robot Operating System) [START_REF] Quigley | ROS: an open-source Robot Operating System[END_REF] uses topics to exchange messages between nodes in a publish/subscribe manner. More concretely, nodes subscribe to a certain topic, while other nodes publish data on this relevant topic. ROS allows newly connected nodes to subscribe dynamically. While this decouples the subscribers and publishers, the nodes need to be running at the same time to send data to each other. This means that ROS supports decoupling in space , because it decouples the publishers and subscribers, but not decoupling in time, because the nodes need to be active at the same time in order to communicate [START_REF] Van Cutsem | AmbientTalk: Object-oriented Event-driven Programming in Mobile Ad hoc Networks[END_REF]. This is necessary when taking into account that components in a system can have a different lifetime. In the case of event loops, Elector does not require one event loop to wait for the other event loop to be (re)started. Elector allows event loops to send messages to an event loop that is not available upon the time of sending, but guarantees that the message will be delivered when that event loop becomes available.

Java Beans [START_REF] Englander | Developing Java beans[END_REF] are reusable components that can be composed using a visual composition tool. It is made for reusability by supporting persistence, introspection, customisation through property editors, etc. Beans communicate through events, where a bean can be the source or the target of the event. Beans register their interest as a listener at another bean. This also reduces the inter-component coupling, but they are not decoupled in time, so beans need to be running at the same time to communicate.

Motivating Example

In this section we introduce an example scenario, which is used to abstract the problems that arise when combining event loops. Our case study is a clicker application, a so-called personal response system that is used as a communication system during lectures. Every student receives a remote control, also called zapper or clicker, that allows them to select an answer when the teacher asks a question. The software on the teacher's computer collects the answers and the results are shown to the class by representing them in a graph. Such a clicker application increases the interactivity and feedback during lectures [START_REF] Ray Dinverno | Using a Personal Response System for Promoting Student Interaction[END_REF], involving all students and ensuring anonymity. Nowadays, all students are equipped with smart phones, tablets, . . . Therefore we use these mobile devices as a clicker device and use a mobile network to communicate between the students and the teacher. Our clicker application can be started for a teacher or for students, so first of all the user has to choose one of these roles. The teacher can send questions to the students, together with possible answers (shown in figures 1(a) and 1(b)). The student receives these questions and can send a selected answer to the teacher (shown in figure 1(c)). We will implement this application on the Android mobile platform using the AmbientTalk programming language [START_REF] Van Cutsem | AmbientTalk: Object-oriented Event-driven Programming in Mobile Ad hoc Networks[END_REF]. In the following sections we introduce AmbientTalk and Android and how they use event loops.

AmbientTalk

AmbientTalk [START_REF] Dedecker | Ambient-Oriented Programming in AmbientTalk[END_REF][START_REF] Van Cutsem | AmbientTalk: Object-oriented Event-driven Programming in Mobile Ad hoc Networks[END_REF] is a distributed programming language that is designed to solve the typical problems in mobile ad-hoc networks. A mobile ad-hoc network has no central infrastructure and the mobile devices that communicate with each other can move out of range. Moreover, the communicating parties can reconnect after a disconnection. AmbientTalk is based on the actor model [START_REF] Agha | Actors: a model of concurrent computation in distributed systems[END_REF], where every actor is represented by an event loop that communicates with the other event loops. AmbientTalk's communicating event loop model is tailored towards mobile ad-hoc networks: every event loop is independent, maintains its own state and communicates with other event loops by sending messages, thus events, to it. Moreover, network events like the discovery of actors are also handled by the event loop.

Android

An Android application is typically composed of different activities, where each activity represents the screen the user sees. An activity is the most important component of an Android application. Because the user can only see one screen at the time, only one activity can be active or in the foreground. Figure 1 shows the different screens the application consists of, each thus implemented by an activity. The application components that run in the background can be either still running, but not visible, or can be destroyed. The programmer thus needs to take into account that an application running in the background can be destroyed, meaning all its state is lost. This is not only so for the Android platform, it is a characteristic shared by other mobile platforms like Apple iOS, BlackBerry OS, Windows Phone, etc. These mobile platforms define at least three lifecycle states for applications: active or running in the foreground, suspended or running the background and not running or destroyed. Thus, mobile applications are subject to lifecycle state changes, which are caused by the system or by the user navigating between applications. When the lifecycle changes, the programmer can react by using callback methods. When for example an application that plays videos is suspended, the "pause" callback method can pause the video. When this application is destroyed, the programmer can store which video the user was watching. If we take for example the student activity of the clicker application, we need to take into account that the reference to the corresponding AmbientTalk actor can be lost when the activity is restarted. Both event loops establish these references by implementing a registering method. In case the user is a student, the student activity starts the student actor at the beginning of the application. The actor retrieves a reference to the activity by calling its registerAT method and passing a reference to the student actor (shown in listing 1.2). Inside this registering method, the activity saves this reference to the actor and returns a reference to itself, as can be seen on line 1 of listing 1.1. On line 5 we see a simplified example of an event listener that gets called when the "send" button gets clicked. As can be seen on line 7, we need to check if the reference to the student actor is still valid. When the activity is restarted, we cannot restart the student actor, because the previous started one is still running. Each application has a main thread, also called the UI thread, which cannot be blocked because it is responsible for processing lifecycle and user interaction events. Only the UI thread can alter view components, hence its name. When an event handler has a long running task to perform, it is up to the programmer to perform this task on a background or worker thread. As mentioned, these worker threads cannot update the user interface of the activity. To solve this, background threads have to use the runOnUIThread method for this purpose.

Problems

Using the building components of the AmbientTalk language and the Android platform we implemented a first version of the clicker application. The language integration is solved because AmbientTalk is implemented in Java (Android applications are implemented in Java) and the languages live in symbiosis with each other [START_REF] Van Cutsem | Linguistic Symbiosis between Event Loop Actors and Threads[END_REF]. Therefore our solution does not take language integration into account, but focuses on the event loops. Several state-of-the art mechanisms exist to let code written in different languages interoperate, for example Mono, a framework for building cross-platform applications, integrates Java with languages of the .NET framework. We give an overview of the problems that are encountered when combining different types of event loops. We can categorise these problems into lifecycle and communication problems. Lifecycle problems are caused by the different lifecycle of the event loops, while communication problems arise when the event loops send messages to one another.

Lifecycle Problems

Different startup time. When using two different event loops, chances are small that they have the same startup time. Because of this, one of the event loops needs to wait before communication between the two event loops can start. Therefore, it is up to the event loop that started later to initialise the communication, or to let the other event loop know it has started.

When programming an application on Android using AmbientTalk, it is the task of the programmer to manually start up AmbientTalk and evaluate AmbientTalk actors. The mutual discovery is hard-coded by implementing registering methods in every event loop to establish references, as showed earlier in section 3.2. Lifecycle state changes. Event loops that suffer from lifecycle state changes can be destroyed, which means that events or messages sent to them are not processed. For instance, Android activities can be killed when the user navigates to another activity or when memory is low. But in our clicker application we need to take into account that actors and activities refer to each other. When an activity is killed, all state is lost, including the reference to the actor and maybe the AmbientTalk interpreter. When the activity is restarted, the programmer needs to check if AmbientTalk is still running, if the actors are still alive, etc. If so, the programmer must establish a way to reconnect the new instance of the activity and the actor. If not, the actor needs to be restarted. There is currently no trivial way to handle this problem and the programmer must implement ad-hoc solutions for handling these lifecycle state changes.

References can become invalid. Because of the lifecycle state changes, the references to an event loop can become invalid when it is destroyed. The other event loop does not know the reference has become invalid. In the case of AmbientTalk and Android event loops, we have seen that the references between them cannot be restored, when the activity is recreated. A restarted activity is actually a new instance of that activity, so upon creation of an activity, we need a way to make actors point to the newly started activity.

Communication sent to a destroyed activity is lost, which brings us to the communication problems.

Communication Problems

Communication can be lost. This problem can arise in two different situations; when both event loops are not started yet, or when a reference to an event loop has become invalid. When a reference to an event loop is invalid, all messages sent to it are lost. When one of the event loops has not been started yet, the already started event loop has to wait before it can start to communicate with the other event loop. This is a consequence of the first problem. In case of Android and AmbientTalk event loops this means that Android's activities must wait when all the actors are started before they can send messages to it. Actors on their turn must be careful when sending messages to an activity, because it can be destroyed.

It is up to the programmer to establish a way for these event loops to communicate and handle each others lifecycle state changes. This leads to a lot of boilerplate code, which can be avoided as we discuss in the next section.

Elector

In this section we introduce the Elector (an acronym of Event Loop Coordination) model together with its implementation for the Android and AmbientTalk event loops. In Elector, references between different event loops are managed by undead references, which revive when a new event loop of the same type is started, hence their naming. On top of that, Elector wraps one of the event loops inside an event loop of the other type. The wrapped and wrapping event loop share the same lifecycle: when the wrapped one is killed, the wrapping is killed too. When the wrapped event loop becomes available again, so is its wrapper. Moreover, the wrapping event loop is the only one that has access to the wrapped event loop. The wrapping event loop thus routes incoming events directly to the wrapped event loop. Concretely, the wrapped and wrapping event loop refer directly to each other. Because they share the same lifecycle, this does not introduce the problems discussed before.

Model

Figure 2 shows how two different event loops are coordinated in Elector. We used AmbientTalk and Android event loops, but the model can be used for other types of event loops as well. Elector wraps the Android event loop inside an AmbientTalk event loop, which we call from now on the wrapped and wrapping event loops respectively. As we can see, the wrapping event loop refers to the Return immediately. When the coordinator is asked for an undead reference to a certain event loop, it returns one immediately, even when the referred event loop has not started yet. This way, event loops don't have to wait for the initialisation of the other event loop. In our example, the student actor retrieves an undead reference to the wrapping actor of the student activity, even when that activity is not started yet. Remain accessible. Elector hides the state changes of an event loop behind undead references. Event loops that have an undead reference to an event loop that is hampered by lifecycle state changes, are not informed of this change and can keep communicating with the event loop as if it is still available. The student actor for example can continue using the undead reference it retrieved to the student activity, even when the activity is destroyed. Rebind automatically. When an event loop is killed and subsequently restarted by the system, it is actually a new instance of that event loop. Undead references will rebind automatically to the new event loop. For example, after restarting the student activity all undead references to it transparently rebind with the new instance. Buffer communication. Undead references route the communication to the actual event loop. When that event loop is inaccessible, the communication to it is buffered. When the event loop returns to a state that it can process messages, all the buffered ones are sent to it in the same order they were received. In case of the clicker example, all messages sent to a wrapping actor for updating the user interface (e.g. displaying a question from the teacher) are sent when the wrapping actor and its wrapped activity are restarted.

By wrapping an event loop inside an event loop of another type, we can make use of the communication abstractions of that type of event loops. This results in an asynchronous way of communication between the event loops, which allows both of them to keep processing events, which is not the case of the models we discussed in section 2. The coordinator creates the undead references, keeps track of them and also discovers all the event loops in the system. When an event loop is killed, the coordinator is informed and all undead references to that event loop start to buffer communication until a replacement event loop of the same type becomes available again. As we will see in the instantiation of Elector for Android and AmbientTalk, the coordinator should provide some guarantees that it is less likely to be killed. In our implementation, the coordinator is only killed when the whole application is destroyed, and thus all its subcomponents too.

Instantiation for Android and AmbientTalk

We implemented Elector for the Android and AmbientTalk event loops, where we choose to wrap the Android event loop inside an AmbientTalk event loop, being an AmbientTalk actor. There are several reasons for this choice: first of all, we can use the AmbientTalk discovery mechanism, which we discuss further on. Secondly, AmbientTalk allows event loops to communicate in an asynchronous and non-blocking way. Finally, AmbientTalk event loops don't suffer lifecycle state changes as much as Android event loops.

Coordinator The coordinator is in this case an AmbientTalk actor that discovers all wrapping actors, together with an Android service that orchestrates all the activities of the application. In our case, the activities of the application connect with the service. When the state of an activity changes, it must inform the service of this state change. Other than keeping track of the lifecycle of the activities, we use this service to automatically start an AmbientTalk interpreter in the background and to load code in this interpreter. Each Android activity thus has an associated AmbientTalk actor, and the programmer has to follow a naming convention in order for the evaluation of the actors to be done transparently. When an Android application uses an Android service, it retrieves a higher priority and it is less likely that the application is destroyed. Should it happen that the service is killed under extreme memory pressure, the AmbientTalk interpreter is destroyed too, together with the coordinator actor and all other running actors. When the service is restarted, the AmbientTalk interpreter is restarted too and the required actors will be re-evaluated.

For the discovery we use AmbientTalk's discovery mechanism, as illustrated in the following code snippets. On line 2 of listing 1.3 we see how the coordinator actor discovers all actors that are categorised in the network as (subtypes of) the Activity tag. The construct whenever:discovered: is used for this purpose. When an actor with that tag is discovered, the coordinator actor receives a far reference to the discovered actor. The other code snippet (1.4) shows the other side: inside a wrapping actor, we can export its behaviour in the network using export:as:. Tags are made with the deftype keyword. On line 1 we create a tag Student-GUI, that is a subtype of the Activity tag. The StudentGUI tag is defined by the wrapping actor of the activity StudentActivity. We now discuss how these wrapping actors behave.

Wrapping actors Wrapping actors share the same lifecycle as their wrapped activity. More concretely, the wrapping actor is taken offline when the corresponding activity is destroyed, and taken back online when the activity restarts. The coordinator can react upon these network events and inform all undead references to that particular wrapping actor. Next to sharing the same lifecycle with its Android activity, the wrapping actor communicates with that activity and also allows us to write most of the user interface code inside these wrapping actors instead of the activities. The communication between a wrapping actor and its wrapped activity can easily be achieved because of the symbiosis [START_REF] Van Cutsem | Linguistic Symbiosis between Event Loop Actors and Threads[END_REF] between the AmbientTalk and Java language. When executing a method call inside an AmbientTalk actor, this method gets executed on the thread of that actor. Recall from section 3.2 that only the UI thread may update Android views and as a consequence we cannot directly update the view from AmbientTalk. Therefore, we introduce a new kind of actor: the UI Thread actor. This actor is responsible for the communication between actors and its activities, by allowing actors to post Runnables on the Android event loop. The wrapping actors can ship off their messages to this actor, which guarantees that they are executed on the right thread. The following code shows how the student's wrapping actor defines a method that shows whether the student is currently connected to the teacher. This code sends an asynchronous message to the UIThreadActor, denoted by the left arrow. The first argument of runOnUIThread (line 2) message selects the correct Android activity. As a second argument, we pass the name of the view we want to alter and lastly, we pass the AmbientTalk equivalent of a Java Runnable, denoted by the runnable keyword. It defines a method run on line 3, that takes the Android view as an argument. This way of changing Android views is only the first step: we discuss an improvement in the next section.

Undead references

The final component of Elector are the undead references between an actor and a wrapping actor. AmbientTalk actors ask the coordinator for an undead reference to a wrapping actor using a tag, e.g. StudentGUI. The first time, the coordinator object makes a new one. When another actor already asked for an undead reference to that wrapping actor, the coordinator does not need to make a new reference, but reuses it. Figure 3 shows how an undead reference switches between two states: "forwarding" indicates the corresponding wrapping actor is available and in the "buffering" state the undead reference starts buffering all messages sent to it. Since the coordinator is informed of the availability of the wrapping actor, it is the task of the coordinator to switch the undead references between these states. An undead reference is entirely programmed using AmbientTalk's reflective layer [START_REF] Mostinckx | Mirages: behavioral intercession in a mirror-based architecture[END_REF]. This layer allows us to catch asynchronous method calls on this reference and decide whether they need to be buffered (in case the corresponding wrapping actor is not available) or can be sent to the wrapping actor. For example, the student actor can alter the text of the status view of the previous code snippet to "Not connected to teacher" when the student actor is started in the following way: On line 4 we send an asynchronous message to the undead reference we retrieved on line 3. When the wrapping actor is already started, the message is immediately forwarded to the wrapping actor. If not, the message is buffered and guaranteed to be delivered when the wrapping actor becomes available (again).

Preliminary Results

In this section we show the merits of the Elector model by comparing the adhoc implementation of the clicker application and the versions using the Elector model. But first of all, we validate the implementation of the Elector model by showing how it offers a base for a more polished version, adding more constructs that make it easier for the programmer.

Specific improvements to Elector for Android and AmbientTalk

The implementation of the Elector model as presented in the previous section is a direct translation of the general model. This implementation solves all the problems that arise when combining two different event loops. Because the user interface code has shifted to the wrapping actors, the Android part of the application contains less code. Therefore, we introduce new constructs that ease the writing of the wrapping actors.

First of all, we introduce a run: construct that takes a block of code as an argument. Behind the scenes, this code is sent to the Android UI thread, hiding the UI Thread actor from the programmer. Similarly, the listener: construct can be used to create an event handler for Android views. Most of the UI code for an Android application are operations like setText, setColor, setVisibility,... on an Android view. These methods alter the user interface, thus they must be executed on the UI thread of the application. We introduce the getView method that returns a reference to an Android View object. All setters on this reference are automatically forwarded to the UI Thread actor. The following code snippet shows how getView can be used by the student wrapping actor to display a question and possible answers from the teacher. This way, the programmer can get attributes of the view and alter them inside AmbientTalk, without worrying about thread-safety. The final extension is the support for futures [START_REF] Dedecker | Ambient-Oriented Programming in AmbientTalk[END_REF]. AmbientTalk's event loops communicate in a non-blocking, asynchronous way, meaning that an asynchronous message send between event loops immediately returns. AmbientTalk's futures are placeholders for the actual result of a message execution. When the actual result is computed, the future is resolved and other actors can receive this result by installing an event handler on that future. A common task in applications is to ask the user for some kind of input, and this is where futures are helpful. We extended Elector in such a way that futures can be resolved inside the code of a run: or listener: construct. This way, an AmbientTalk future can be resolved when e.g. a button is clicked. Vice versa, a text view can be linked to a future, filling in the view when the future becomes resolved.

Comparison of the clicker applications

We ended up with three versions of the clicker application: one without Elector, one that uses Elector and a final one that uses the extensions from previous section. The final version of the application spends less code on the mismatching concerns and contains less code overall. The first clicker version contains 512 lines of code, the second one 430 lines and the final version 367 lines of code, which is a decrease of 28% between the first and final one. Therefore, we measured the latency between registering an event (clicking on a button) and the actual update of the GUI (in the Android UI code) (Scenario 1). We also measured the latency between registering the event and executing the listener: construct and from this point to the updating of the Android View (Scenario 2). From these experiments we obtained the following results (average and standard deviation of 200 experiments) in milliseconds: Elector is a proof-of-concept implementation as a framework for AmbientTalk which we use to illustrate that our model eases the coordination of different event loops. When absolute performance is a necessity, Elector could be implemented in the AmbientTalk interpreter itself. We can conclude that Elector had an impact on the clicker application: the programmer is freed from manually coordinating the event loops. As a side-effect, this has an impact on the code size and complexity, but moreover, more of the code now focuses on the logic of the program. This initial result is promising, but more studies are needed to further gauge the impact of Elector.

Conclusion and Future Work

We introduced a coordination model called Elector, that tackles the problems that arise when coordinating different event loops. Elector is targeted towards event loops that suffer from lifecycle changes (e.g. the event loops can be killed and restarted) but the model is suited for all sorts of event loops. In contrast to existing libraries, Elector allows the event loops to run separately, instead of letting one event loop take control over the other. Elector also does not change the source code of the event loops, but provides a bridge between them. The main component of the Elector model are its undead references, the other components of the model manage these references. The undead references solve all the problems encountered when combining different event loops, namely the lifecycle and communication problems. Using the implementation of the Elector model for the Android and AmbientTalk event loops, we evaluated the model by implementing a concrete case study: a clicker application. We compared the different versions of that application and concluded that Elector relieves the programmer from manually coordinating the event loops. The Elector implementation is targeted towards event loops on one device, but we could extend Elector with distributed undead references. This way, a teacher could for example first demonstrate how the clicker application works by retrieving an undead reference to the user interfaces of the students. The other way around is also possible: several people can retrieve an undead reference to one and the same user interface, e.g. for a brainstorming session. An important task of the undead references of Elector is to buffer communication between event loops when one of them is not available (yet). The current implementation of Elector does not take duplication of messages into account, but we could easily support smart buffering. In order to achieve this, an annotation could be used, that allows the programmer to define the behaviour of messages in the buffer. So not only does Elector solve the problems that arise when combining different types of event loops, its undead references can be applied in other domains as well.

Fig. 1 .

 1 Fig. 1. Android views of the clicker application

1 2 StudentActivity 8 // send answer to teacher 9 }}}Listing 1 . 1 .Listing 1 . 2 .

 2891112 StudentActivity registerAT(Student s) { Registering an actor (Java) 1 def gui := Android.registerAT(self) Registering an activity (AmbientTalk)

Fig. 2 .

 2 Fig. 2. Elector: the basic idea

1 def 2 whenever: 3 /Listing 1 . 4 .

 12314 CoordinatorActor := actor: { Activity discovered: { |e| Publishing an actor

1 def

 1 teacherStatus(status) { 2 UIThreadActor←runOnUIThread(getTypeTag(), "connection_state", runnable: { 3 def run(v) { // method to be executed on UI Thread

Fig. 3 .

 3 Fig. 3. State diagram for an undead reference

1 2 deftype

 2 import /.at.android.undead_references; StudentGUI; // tag we want to retrieve 3 def guiRef := undeadRef(StudentGUI); // ask undead reference from coordinator 4 guiRef←teacherStatus("Not connected to teacher"); // send asynchronous message

1

  import jlobby.android.view: 2 def askQuestion(question, answers) { 3 def question_v := getView("question"); 4 def previous := question_v.getText(); // retrieve current text of view 5 question_v.setText(question); // alter text 6 question_v.setVisibility(View.VISIBLE); // show the text 7 }

Fig. 4 .

 4 Fig. 4. Graph comparison for the first and final version of clicker

  Scenario 1 Scenario 2 click → listener listener → update AVG +-STDEV 285.8 +-39.73 4.55 +-2.28 278.29 +-47.57

Funded by a doctoral scholarship of the "Institute for the Promotion of Innovation through Science and Technology in Flanders" (IWT Vlaanderen). Prospective research for Brussels, Innoviris