@Misc{ ss11:eval,
  author = {Serpette, B. and Serrano, M.},
  title = {Hop Server Side Interpreter},
  category = {programming language},
  year = 2011,
  month = jun,
  url = http://foo/bar.pdf;
}

1Introduction

Hop is a Scheme based multi-tier programming language for the Web. We have implemented a new interpreter (HopE₁) for executing server-side parts of Hop programs1. By adapting techniques developed in other compiling contexts , we have accelerated the former HopE₀ interpreter by a factor of more than two, making HopE₁ one of the fastest interpreters we have measured.

HopE₀ accepted as input a tree structure close to the input source, which was obtained by parsing the source code, macro-expanding it, and resolving local variable references. These were interpreted as indexes into a heap-allocated lexical environment. In HopE₁, we significantly improve the interpreter efficiency by allocating local variables in a stack, as done in traditional compilation technique.

The HopE₁ interpreter is written in Hop and it is compiled to native code via C code generation. C is not properly tail recursive, i.e., calling a C function in a tail position allocates a stack frame. Hence, lacking special treatment, HopE₁ is not tail-recursive either. This is a critical problem because loops are traditionally implemented in Hop as tail recursive functions. In order to fix that problem, HopE₁ relies on a trampoline machinery2. A contribution of this paper is to show that a trampoline solves the tail recursion problem for interpreters such as HopE₁ without degrading performance.

There are various sorts of interpreters. Some evaluate the source code directly. Others construct a memory representation of the programs and apply simple transformations; HopE₀ falls into this category. Some interpreters pre-compile the program into an abstract structure that is interpreted by a dedicated virtual machine. HopE₁ leans toward a pre-compilation schema by deploying simple optimizations not implemented in HopE₀. A last contribution of this paper is to precisely evaluate the impacts of classical compile-time optimizations when applied to an interpreter.

The paper is organized as follows. Section 2 briefly introduces Hop and the context in which its interpreter is used. Section 3 presents the HopE₁ implementation techniques. Section 4 highlights some specific issues that impact the performance. Section 5 presents experimental performance results, comparing the new HopE₁ interpreter to interpreters for Scheme and other dynamic languages.

2Background

Unlike traditional solutions for developing web applications, Hop 19 is a multi-tier programming language that makes it possible to write entire applications using a single formalism. With Hop, a web application is no longer a set of more or less loosely related components, such as PHP scripts on the server side and HTML+JavaScript on the client side. It is a single program written in a single programming language. Hop is largely inspired by the Scheme R5RS programming language 12, which it extends in several directions. It supports many modern features such as modules, objects, exceptions, and threads, coupled with a vast set of libraries. It also supports web-dedicated features: Html elements are first class values; client-side programs are first class values of the server-side programs 20, 3; and bidirectional communication between servers and clients is supported.

A Hop program is organized in modules which describe the server and client computations. The runtime environment of a Hop application is thus twofold. The program is first installed on the server. Then, the clients, i.e., the web browsers, receive their parts of the application and communicate with their server. Figure 1 illustrates this multi-tier architecture.

The Hop web server is bootstrapped. It is itself written in Hop 17 and compiled by HopC, a native compiler built on top the Bigloo optimizing Scheme-to-C compiler 18. The server embeds the Hop-to-JavaScript compiler 14 which compiles the client-side on-the-fly, and an interpreter which handles non-natively compiled code on the server. The server-side parts of an application are thus composed of a blend of natively compiled code and interpreted code.

Resorting on interpreted code is optional as server-side parts can be statically compiled if needed. For CPU-demanding applications, this approach is recommended. However, it comes with an extra complexity because it requires the programmers to generate dynamic libraries for each Hop-supported architecture. For desktops that are equipped with full-fledged development kits, this is probably not too heavy a burden. On constrained platforms such as SmartPhones and single board computers that generally lack a on-device C toolchain, heavyweight cross-compilation techniques must be used.

At first, Hop applications were not CPU nor memory demanding. The interpreter was mostly used for expansing macros contained in the program source code and for running some hundred-lines long scripts on the server side. The HopE₀ server-side interpretation was accomplished by an hybrid engine that used tree structures and a mix of native stack and separate heap-allocated lexical environment. This interpreter offered acceptable CPU performance, but, when Hop applications became larger and more complex, its performance became unacceptable for three reasons:

• the heap allocation of the lexical environment stressed the garbage collector too much;
• closures captured their whole lexical environment, making the memory footprint unnecessarily large;
• loops where implemented using an ad hoc tail-recursive interpretation technique that significantly enlarged the size of each native stack frame for non tail-recursive calls. This problem was exacerbated by the Hop implementation of concurrency, which relies on the Posix Threads where each thread stack is small since pre-allocated at creation time.

The design and implementation of HopE₁ has been motivated by the elimination of these HopE₀ drawbacks.

3Interpreter Architecture

The implementation of HopE₁ has been guided by five main constraints:

1. Hop is composed of a full-fledged web server, an optimizing native compiler, an optimizing JavaScript client-code compiler, a server-side interpreter, and a vast set of libraries. All this constitutes a large and complex system, whose size is close to 500 Hop KLOC. Because of limited manpower, we could not afford creating a new complex module for the server-side interpretation. We had to keep HopE₁ as simple as HopE₀. To satisfy this constraint, HopE₁ is meta-circular, i.e., entirely implemented in Hop, and it does not resort on any JIT compilation technique nor specific virtual machine.
2. The Hop server-side environment is multi-threaded 17. The server handles each request in a dedicated Posix thread. Since Posix threads pre-allocate fixed-size stacks, the interpreter should not not consume large stack frames for its own execution.
3. The Hop server is executed on all sorts of platforms, ranging from standard desktop computers to single board computers or embedded devices, which are generally not equipped with a lot of memory. Avoiding unnecessary memory allocation and memory retention is particularly important on such platforms.
4. Loops in Hop are expanded into tail-recursive calls. If not implemented in this way, they these will raise stack overflows.
5. The HopC compiler is used to build the server-side runtime environment that contains the server-side Hop libraries. Library functions are extensively used by interpreted code. For our benchmark suite, more than 75% of the dynamic function calls executed by the interpreter concern compiled native functions3. A fast connection between interpreted code and compiled code is of premium importance for the overall performance.

The HopE₀ interpreter was satisfying the last two requirements. The HopE₁ satisfies them all. In the rest of this section we present its general architecture.

31An Academic Interpreter

Which implementation language should be used for the interpreter? Low-level languages such as assembly or C look most suitable because they offer fine-grain control over low-level operations on registers, stack, signals, etc. However, since the interpreted code interacts with compiled code, it might be sensible to implement the interpreter in the language compiled by the native compiler and to compile it. This is the option we have chosen for Hop. It is validated by the overall performance reported in Section 5.

We gradually present the interpreter architecture, starting with the simple λ-calculus interpreter presented in Figure 2.

In such a denotational semantics based academic interpreter, the lexical environment ε could be simply represented by a function mapping variables to values. However we use a standard association list to show explicitly that each abstraction invocation allocates two memory cells (line 9).

The evaluation of an abstraction (line 8) returns an abstraction of the meta-language (line 9), making it possible for the meta-language to directly invoke evaluated functions. Using a different data-type would slow down the calls to interpreted functions executed by compiled code. Such calls typically occur when the interpreter calls the map library function.

32A More Realistic Interpreter

Our first interpreter does not use any pre-compilation stage to save execution time. In the spirit of partial evaluation techniques, some computations may obviously be executed once and for all before the actual evaluation stage. For instance, the pattern matching that discriminates expressions can be statically performed once and for all before their evaluation takes place. This requires splitting the interpreter in two phases. First, a pre-compilation phase through the source code extracts simple static information. Then, a run phase computes the actual values.

The first phase, named Π and pictured in Figure 3, receives the same arguments as the previous eval function. It returns values of type compiledExpr, whose constructor is named Λ. Henceforth, we will note (Λ (...v...) expr) a compiledExpr, where each v is a variable to be be bound at run time and expr is the run time code to be executed. The second phase, named Ω, takes as first argument a compiledExpr.

Π only manipulates the symbolic part of the environment. The compile-time and run-time lexical environments have the same shape. Therefore, Π can pre-compute indexes to be used by itself and Ω. These indexes correspond to De Bruijn indexes 7. Thus, we can change the implementation of environments to a more compact and efficient representation: the compile-time environment becomes a list of symbols and the run-time environment becomes a list of values. The benefits are twofold. First, the new environment representations save memory space. Second, at run time, lookups over variable names are replaced with indexed accesses to lists. This second version of Π is shown in Figure 4. It has been first proposed by Feeley and Lapalme 9.

33Tree Interpretation

The representation of compiledExpr deeply impacts the implementation of Λ. We have tried two options: a tree structure; and a functional structure. The former, used by HopE₀, is described in this section.

A value, (Λ (...v...) expr), is represented by an index and a heap-allocated data structure containing the values of the free variables occurring in expr and pointers to its sub-expressions. The whole Ω function is built by merging all the Λ expressions into an indexed switch as for a byte-code interpreter. An excerpt of the implementation of Π can be found in Figure 5. An excerpt of the runtime evaluator Ω is given in Figure 6. In both cases, the integer 9 is the index of the function application.

The meta-language of the interpreter, i.e., Hop itself, is simply tail recursive. That is, only syntactic self tail recursive calls are implemented without stack allocation. All other calls allocate stack frames whatever their context is. Thus, the recursive call for evaluating the body of a function allocates a stack frame, although it is in tail position. To get rid of this allocation, it is enough for the interpreter to recognize that the invoked function is interpreted, and thus to inline the call. The result of this transformation is given in Figure 7. It merely puts the recursive call to Ω in a simple tail position that is immediately compiled by HopC as a simple goto.

The library predicate eval-procedure? returns true if and only if its argument is a procedure created by the interpreter. This predicate relies on a special HopC feature that allows attributes to be associated with closures.

This version of the interpreter corresponds to HopE₀, except for some optimizations that are not shown here. It satisfies the criteria 1, 4, and 5 of the introduction of Section 3, but it fails criteria 2 and 3. First, some programs have an unnecessarily large memory footprint because closures capture the whole lexical environment instead of a subset containing only their free variables. Second, the interpreter is properly tail-recursive, but each regular function call allocates a very large stack frame. This is due to an artifact of the HopC native compiler that we explain now.

The function Ω is mainly composed of a large switch, of which each branch corresponds to the execution of one type of expression. Some branches contain simple expressions such as literals or variable references. Other branches require complex computations. For example, for the sake of performance, the let forms are not macro-expanded in the branch that handles them, but are represented by and ad-hoc expression. Such a branch requires the introduction a lot of temporary variables. These variables will end up being allocated in the stack frame for Ω whatever branch is selected at runtime. Obviously, this wastes a lot of stack space. Unfortunately, there is no easy way out. First, because our tail recursion technique requires that all recursive calls to Ω are self recursive. Second, because HopC actually compiles to C and relies on regular C compilers for producing binary code. Actual stack frame allocation depends on C compilers we do not control4. We have explored a different strategy that uses an additional stack. It will be presented in Section 35.

34Functional Interpretation

The tree structure presented in the previous section can be considered as an ad hoc representation for closures. Each expression contains a code pointer denoted by an index and some closed values. The Λ constructor acts as an abstraction and can be replaced by a true closure. This transformation is shown in Figure 8.

With this representation, the runtime interpreter is a mere function application, as shown in Figure 9.

The new interpreter solves the large stack frames problem that plagues the tree interpreter, but it does not support proper tail-recursive calls. To avoid allocating stack frames, we will modify Ω to use a trampoline 21. This transformation will be presented in Section 42.

35A Second Stack

In all the interpreters presented so far, closures capture the entire lexical environment represented by a list (see Figure 4, line 12). The next step consists in replacing the heap allocation of the lexical environment with a stack allocation. After this modification, the interpreter will use two stacks: the implicit native stack used each time Ω is called and a new explicit interpreter stack used to allocate frames of interpreted functions.

The new version of the interpreter uses a global stack accessible by two library functions: stack-ref and stack-push!. The reference to a variable is thus an indexed read from the stack as shown in Figure 10.

Closures now need an additional heap-allocated structure to store their free variables. This is shown in line 13 in Figure 11. When the function is invoked, before its body is evaluated, an interpreted stack frame is allocated (see line 15 and line 16 in Figure 11).

In the previous version of Π (Figure 8), the function calls were fast but closures did capture their entire lexical stack, which made accessing a variable was linear in its nesting level. With the new version (Figure 11), only the free variables are stored in the heap-allocated structure that is pushed on the stack each time the function is invoked. Accessing a variable becomes a constant-time operation. Whether one version of the interpreter is faster than the other depends on the nature of the source language to be interpreted. For a pure λ-calculus where each term has many free variables, the first strategy will probably be more efficient. The latter strategy is significantly more efficient for languages such as Scheme that propose a let form based on stack frames instead of heap-allocated environments. This is demonstrated by the experimental report presented in Section 5.

Several optimizations presented in Section 4 need a fine-grain control over the function call protocol. We decompose each evaluated function into two sub-functions: external and runner. The former is used by the compiler to invoke interpreted functions. The latter is used by the interpreter itself. The protocol to call external belongs to the compiler. The protocol to call runner uses the interpreter stack. Figure 12 shows the new version of the interpreter with these two functions.

4Optimizations

In this section, we present the various details of the implementation of HopE₁ and the main optimizations we have deployed.

41Stack pointer vs Frame pointer

Stacks are generally accessed via a stack pointer, which is an index in a vector of values that points to the top of the stack. The distance between the stack pointer and a variable in the stack is precisely the value of the variable's De Bruijn index. For example, in the expression (λ (x) ...(let ((y ...)) ... x)) the De Brujin index of x is 1 inside the let, which means that its value is stored one memory cell above the stack pointer.

Alternatively, a frame pointer can be preferred to a stack pointer. The frame pointer is constant during a function invocation, pointing to the first value pushed on the stack by the function call. Using a frame pointer is more efficient than using a stack pointer because it eliminates the need for incrementing and restoring the pointer each time a let form is evaluated (see in Figure 13).

With a frame pointer, the distance between that pointer and the cell reserved for a variable value is known at compile-time. However it must be transmitted to the runtime interpreter.

42Trampoline

The version of the interpreter presented in Figure 12 does not support proper tail recursion because the evaluation of the body of a function is embedded inside a λ-abstraction. To solve this problem, we have setup a trampoline 21 in HopE₁. When the interpreter calls another interpreted function in a tail position it returns it to the current trampoline instead of calling the runner. A trampoline is installed when the interpreter calls another interpreted function in a non-tail position and when a compiled code calls an interpreted function. A trampoline invokes the function value it intercepts if and only if it corresponds to a runner. Otherwise, it returns it by to its caller. Trampolines recognize runners by checking a dedicated closure attribute, a HopC-supported feature we briefly presented in Section 33. The code snippet in Figure 15 shows the trampolined version of the function call.

Since the value of the argument tail? is known at compile time, the test used to either return a continuation value or install a new trampoline can be lifted out of the Λ form, which leads to two specialized versions of runtime function calls: one for tail recursive calls and one for the other calls.

Figure 16 shows the impact of trampolines on CPU performance. Each black dot represents one test of the Bglstone benchmark suite that contains 19 tests exercizing different features of the Hop5. The dots are positioned on a single axis that represents the time ratio of the trampolined vs. non-trampolined versions. For instance, a dot located at position 0.90 means that for the associated test the execution with trampoline is faster and takes 90% of the time of the non-trampolined version. Surprisingly, there is a small speedup for most tests when trampolining is used. We suspect that this is due to a better cache locality of stack. One should note ratios less than 95% are insignificant because they are out of the range of uncertainty caused by memory cache and branch prediction effects.

43Loops

In Hop, loops are implemented by local recursive functions, generally introduced by the general letrec special form, as in Figure 17. In this section, we show that although the trampoline presented in Section 42 avoids allocating stack for loops a special treatment of loops generally speeds up the execution.

When all the variables defined in a letrec are bound to functions and when they are exclusively used in tail-recursive calls and not closed under a lambda, the letrec is treated as a loop by the interpreter. Π is modified to detect such loops and to use an ad hoc interpretation schema. Π saves the symbolic environment at the entry point of the loop. This environment is a compile-time data structure that contains the names of the bound variables for each program point. In our example, when the loop is entered, the symbolic stack contains the identifier n. In the function odd?, it contains n and y. For each bound variable, the interpreter creates a function similar to the runner function presented in Section 42. This is a special case of a more general optimization found in several optimizing compilers, which consists in treating specially the variables bound to functions in a letrec. A complete study of this popular transformation can be found in 22.

When a tail call to a loop is encountered, the interpreter statically knows how many values must be dropped from the stack to adjust the stack at loop entry. For example, for the (even? tmp) call, the symbolic stack is (n tmp) and one value must be dropped. Arguments of the call are evaluted and saved in the stack. Finally, the runner associated with the local function is returned, the body of the letrec being evaluated as a trampoline.

Of the 391 letrec used in all the Bglstone suite, 144 are used to implement loops. The Figure 18 shows the impact of the loop detection on execution times. The optimization reduces execution times because it avoids allocating closures and references for captured variables.

44Inlining

Inlining is a well known technique that replaces a function call with a specialized version of the function body. Inlining is particularly important for functional languages that extensively use small functions. Hence, we have added inlining to HopE₁, keeping it simple enough to avoid significantly increasing the compilation time. We merely inline the body of a pre-defined set of frequent functions such as the fixnum arithmetic operators or the usual list accessors. Implementing this optimization consists in extending the Π function with some extra cases as shown in Figure 19.

Figure 20 presents the impact of the inlining optimization on the Bglstone benchmarks suite. It has a dramatic impact. For instance, it almost divides by 2 the execution time of tests such as fib.

45N-ary functions

For the sake of simplicity, the interpreters presented in Section 3 assumed functions with exactly one argument. Extension to n-argument calls is straightforward. While the protocol used by the interpreter to call an interpreted function is independent of the number of actual values (see the runner function presented in Section 42), the protocol used for invoking a compiled function from the interpreter depends on the number of arguments. This protocol consists in apply-ing compiled functions to a list of packed arguments, allocating lists from which the compiled code extracts the actual values. This method is presented in Figure 21.

To avoid packing the arguments in lists, the interpreter treats specially function calls with 0 up to N arguments. What should be the value of N for improving the performance? We have conducted another experiment reported in Figure 22. We have measured the execution times of each benchmark for N in the range [1...6], comparing it to the execution time of the same benchmark with N=4. This experiment shows that a special handling of 1 to 4 arguments is beneficial. We excluded functions with 0 argument because these functions are always compiled specially.

As shown in Figure 10, when the interpreter pre-compiles a user function, it generates two functions: the runner and external. The latter is used when the compiled code calls back the interpreter, for instance, when a compiled library function such as map calls its first argument. We have measured the impact of compiling the external function. It is reported in Figure 23, which shows that the protocol used to invoke an interpreted function from compiled code does not impact the overall performance. So, the interpreter always uses a single external function for all cases.

46Debugging

For the sake of debugging, the interpreter computes a symbolic stack of called functions at any program point. Figure 25 shows the overhead imposed by computing that information on the benchmark tests. The maximal overhead is about 40% with a mean smaller than 15%. We have considered this overhead as affordable. Thus we keep debugging enabled. For a similar reason, the interpreted code always checks the dynamic type of values before accessing any data structure.

47Extensible Stacks

The interpreter stack is allocated in the heap and represented as a list of Hop vectors. When an interpreted function is called, the free space remaining on the stack is checked. When it is too small, a new vector is allocated and added to the list. The stack is then accessed using unsafe library functions that do not check the vectors bounds. Figure 26 presents the overhead imposed by checking the stack size when functions are entered.

We have measured the impact of the vector sizes on the performance of the interpreter. This is presented in Figure 27. It shows that the maximal performance is reached from 8KB vectors, which is large enough to run all the benchmarks without extending the stack.

48Arithmetic expressions

Hop uses 64 bit allocated floating point numbers. Therefore, floating point operators have to unbox, compute, and box. Boxing and unboxing dramatically slows down execution. So, we have added a simple optimization that consists in using a dedicated interpreter for floating point expressions. When the standard Π interpreter parses a floating point operator, it generates a specific function that invokes the dedicated interpreter. This interpreter benefits from the HopC optimization that unboxes floating point numbers. Such a floating point optimization avoids allocating numbers for temporary results, but it still requires to allocate one fresh number per arithmetic expression for the result. Figure 28 shows the impact of this optimization on the Bglstone tests. The highest speedup is observed for the nucleic test, whose execution is about 30% faster when the optimization is enabled.

5Evaluation

In this section, we compare the performance of HopE₁ with other implementations of dynamic languages. First, we compare it to various implementations of Scheme, the language on top of which Hop is built. Then, we compare it with a broader spectrum of languages.

The experimental values are collected on two platforms: an Intel x86/32 Xeon W3570 3.2Ghz running Linux-2.6.39 and a Samsung S3C2440 Arm9 400Mhz running Linux-2.6.32. To measure the execution times, each program is executed three times and the minimal system+user sum is collected. When possible, benchmarks have been configured for the execution times of the new interpreter to be approximatively 10 seconds on the x86 platform. Using a long enough execution minimizes the impact of the boot-time of each system. This corresponds to the way HopE₁ is used in Hop because there is no real boot-time where the server is already fully initialized and the program loaded and compiled. But systems which optimize start times versus run times may be penalized in this measurement.

51Hop vs Scheme Implementations

To estimate the efficiency of the new Hop interpreter, we have first compared it to other implementations of Scheme. The implementations we have used are the following.

• Bigloo 3.6b and Racket 5.1.1: Bigloo is the native of Hop via C. Racket is a JIT compiler for Scheme. This comparison shows that interpreters cannot compete with true compilers and that native compilation is unavoidable when performance is really needed.
• HopE₀ and HopE₁ are the two Hop interpreters. Although an important speedup is unsurprising because HopE₀ was not optimized for speed, this comparison is important because it let us measure to which extend our primary goal has been reached.
• Gambit-C 4.6.1. Gambit is a Scheme implementation that contains a C code compiler and a meta-circular interpreter which uses explicit closures as for HopE₁. However, in Gambit-C, closures are encoded with Scheme vectors instead of Scheme procedures. Gambit-C is configured with --enable-single­host to improve its performance. We only measure the execution times of the Gambit-C interpreter that is started with a 4MB heap.
• Guile 2.0.2 is the GNU extension language. It is a popular Scheme implementation with a byte-code interpreter written in C.
• STklos 1.01+ is a byte code interpreter implemented in C.

Comparing various implementations is complex because it is difficult to configure and use them similarly enough. Some systems can only partially disable the debugging support, some support specialized arithmetic while others don't, etc. Therefore, the feature difference between two systems may impact their overall performance more than the quality of their implementation. For instance, Hop does not support Scheme's call/cc. Lacking this feature enables optimizations that are forbidden for pure Scheme implementations. So, only the comparison of the execution times of HopE₀ and HopE₁ is totally meaningful: their execution times are measured on two systems differing only by the interpreters. As far as the comparison with other systems is concerned, we think that only big enough ratios (greater than 50%) are meaningful.

The Scheme benchmarks use specific arithmetic operators when available (for instance, Hop uses +fx, Gambit ##fixnum.+, and STKlos and Racket fx+). All the Scheme implementations benefit from this specialization except Guile, which only supports generic operators. Operators are inlined by systems that support modules, e.g., Bigloo and Racket, because they use module boundaries to detect that the operators are constant functions. Execution is safe since the types are checked at runtime. All systems but Bigloo, Guile, and probably Racket offer some debugging facilities (see Section 46).

The benchmarks timings of the Bglstone suite are reported in Figures 29 and 30. The first observation is that no interpreter can compete with compiled code. Bigloo is the faster compiler tested here. It is one or two orders of magnitude faster than Guile and HopE₁, the faster interpreters. Guile is slightly faster that HopE₁ but their execution environments are not totally equivalent. In particular, Guile does not support specific arithmetic operations; adding such functions could significantly increase its performance. Another observation is that HopE₁ is more than twice faster than HopE₀. HopE₁ satisfies its general goal to eliminate the drawbacks of HopE₀ without jeopardizing the overall performance. The last observation is that Guile and HopE₁ are roughly two or three times faster than Gambit and STklos. This indicates that the implementation language of the interpreter might not be crucial for the performance, since Guile is implemented in C and HopE₁ in Hop.

We have compared the memory allocations of HopE₁ and HopE₀. The result is presented Figure 31. Note that for this experiment we have executed the tests with smaller input values for the tests. HopE₁ reduces significantly the allocated memory, benefiting from its stack structure (see Section 35). Greater amounts of allocated memory for HopE₀ do not necessarily imply that it has a larger memory footprint, because most of the allocated stack frames have a very short life time and are reclaimed at each collection. This is why the ratios between the memory allocated and number of executed collections differ. Surprisingly, for some tests, the CPU time ratio and the allocated memory ratio seem unrelated. For instance HopE₀ allocates 350 times more memory than HopE₁ for fib and runs 478 times more collections, while its execution is only 1.6 times slower. We have no explanation to propose to that surprising result. On the other hand, both interpreters consumes the same amount of memory for fft but HopE₁ executes it twice faster. Other tests such as puzzle or leval are more conform to the intuition that the execution time is strongly related to the amount of allocated memory.

52Hop vs Dynamic Languages

In this section, we compare the performances of the two Hop interpreters to the performances of other dynamic languages. The methodology differs from the previous section. Each system comes with its own implementation of each benchmark, reflecting the idiosyncrasies of both the language and the evaluation engine. This section is not a fine grain comparison. It merely gives a general idea of the maximal performance each system may deliver. A difference of 20% or 30% is not significant here, only the orders of magnitude mattering. If one system is 10 times slower than the others for all the benchmarks, it tells us something about the complexity limitation of the problems that its language can address. Jumping to conclusions when the difference are smaller would probably be misleading.

For that experiment, we consider seven programming languages: JavaScript v8 3.2.10, Lua 5.1.4, Perl 5.12.3, PHP 5.3.6, Python 3.2, Ruby 1.9.2, and Hop. We have used 5 test programs. First, fib because it is simple enough to be implemented as is in all languages and because it is a good test for measuring the raw performance of function invocation and the exact arithmetic. Then, we have used four tests adapted from the Computer Language Benchmarks Game, aka Shoothout.

The Computer Language Benchmarks Game aims at comparing the best possible performance delivered by of all sort of implementations of all sort of programming languages. All implementations are free to use any technique or trick as long as they implement the same algorithm. A permissive understanding of this sentence gives a lot of freedom to the implementors. For instance, the PHP implementation of the spectral-norm uses two threads while all the other languages only use one. The idea of the Shootout game is to answer the following question: for each considered problem, what is the fastest implementation possible for each tested system? The Figure 32 presents the results on x86. Figure 33 presents them on Arm.

As a confirmation of the Bglstone experiment, interpreted code cannot compete with compiled code. Bigloo and JavaScript V8 are one or two orders of magnitude faster than interpreters. Within interpreters, HopE₁ delivers good performances for fib, btrees, and snorm, but poor performances for fasta and mbrot. These two tests are floating-point intensive. For instance, the whole execution time of mbrot is spent executing the following sequence that is constantly repeated:

(let loop ((i 0)) (set! Zi (+fl (*fl 2.0 (*fl Zr Zi)) Ci)) (set! Zr (+fl (-fl Tr Ti) Cr)) (set! Tr (*fl Zr Zr)) (set! Ti (*fl Zi Zi)) (set! k (+fx k 5)) (when (<=fl (+fl Tr Ti) 4.0) (loop (+fx i 1))))

Although the floating optimization presented Section 48 unboxes numbers for subexpressions, the execution time of this test is still largely dominated by the time required to allocate and collect the numbers stored in the Zi, Zr, Tr, and Ti variables. The whole execution allocates about 600MB of floating numbers and runs 76 collections to reclaim them. Improving the performance of HopE₁ for this kind of test will require a new optimization for numbers. The compiled code does not suffer the same problem because its static analysis eliminates all boxing operations at compile time.

6Related Work

Implementing efficient interpreters seems to be almost as old as computer science. For instance a paper by Klint from 1981 13 contains a comparison of compilation and interpretation. A long debate opposes byte-code switch to threaded code 1, 8, 5, 15. The function operators of HopE₁ might be considered as a variant of threaded code. Our experiment is yet another example where threaded code delivers faster code then byte-code switches. Another paper by Brunthaler 4 studies the impact of low level code representation and presents some general optimization such as caching interpreted local variables that could be used in HopE₁.

As for Javascript, the Lua programming language is designed for simplicity. It only supports floating-point numbers. It emulates arrays with association tables and supports only few constructs with a limited syntax. Its implementation is based on a remarkably efficient and compact byte-code interpreter. The whole implementation fits in less than 17 KLOC of C code. Instead of using a stack as for the seminal Pascal's P-machine 16, it uses a register-based architecture 11. This architecture avoids many pop and push instructions that stack-based code needs to move values around the stack. Since it avoids boxing temporary results, it is particularly efficient for dealing with floating point numbers. This is reflected by the good performance of the Lua interpreter on the all floating point intensive Shootout tests fasta, mbrot, and snorm.

Python is a byte-code interpreter implemented in C. It uses threaded code instead of a byte-code switches; accordingly to a comment located inside the source code, this improves the performance by 15-20% 6. Alternative systems for executing Python are under investigations. In particular, the PyPy experiment consists in implementing a meta-circular Python JIT. This work concludes that high-level languages are suitable for implementing dynamic languages 2. We have reached the same conclusion.

Mainstream JavaScript implementations such as Firefox TraceMonkey 10 or Google Chrome V8 use JIT compilers to improve performance. As shown in this section, this technique significantly outperforms interpreters at the price of a higher complexity, but developing such compilers is much more complex than developing interpreters. Unsurprisingly, they are also less portable. This probably explains why some of them are only available on x86 architectures.

PHP has a threaded code interpreter for a dynamic typed virtual machine called Zend. The interpreter is written in C. PHP relies on reference-count garbage collection. Allocating the results of arithmetic operations is carefully avoided. For example, the virtual machine proposes 16 different operators for implementing multiplications.

7Conclusion

We have presented HopE₁ the new Hop interpreter that works hand-in-hand with native compiled code to execute the server-side parts of Hop programs. This new interpreter is meta-circular and implemented in Hop. Its source code is no more than 2.5 KLOC. This compactness made it simple to develop and now makes it easy to maintain.

HopE₁ has fulfilled its primary goal, which was to eliminate the major weaknesses of the former HopE₀ interpreter. As demonstrated in Section 5, HopE₁ has significantly exceeded that goal. It is one of the fastest Scheme interpreters we have tested. HopE₁ is between two and three times faster than HopE₀. Although performance still lags far behind compiled code, such a speedup is important for Hop. A two-fold speedup greatly reduces electricity consumption and heat emission, which is critical for portable devices or for future fan-less computers. This is an important property for application domains such as multimedia, which are primary targets for Hop.

8Acknowledgements

Many thanks to Ludovic Courtès, Eric Gallesio, Marc Feeley, and Gérard Berry for their helpful feedback on this work.

9References