Interpreters & VMs
Language interpreters, virtual machines, and runtime systems
Repositories
(8)bytecodealliance/wasmtime
dotnet/runtime
erlang/otp
nodejs/node
openjdk/jdk
python/cpython
ruby/ruby
v8/v8
Papers
(53)Accurate Sum and Dot Product
Algorithms for summation and dot product of floating-point numbers are presented which are fast in terms of measured computing time. We show that the computed results are as accurate as if computed in twice or K-fold working precision, $K\ge 3$. For ...
A monotonic superclass linearization for Dylan
Object-oriented languages with multiple inheritance and automatic conflict resolution typically use a linearization of superclasses to determine which version of a property to inherit when several superclasses provide definitions. Recent work has def...
An Improved Algorithm for hypot(a,b)
We develop a fast and accurate algorithm for evaluating $\sqrt{a^2+b^2}$ for two floating point numbers $a$ and $b$. Library functions that perform this computation are generally named {\tt hypot(a,b)}. We will compare four approaches that we will de...
Applications of Finite Automata Representing Large Vocabularies.
Abstract The construction of minimal acyclic deterministic partial finite automata to represent large natural language vocabularies is described. Applications of such automata include spelling checkers and advisers, multilanguage dictionaries, thesau...
Copy-and-patch compilation: a fast compilation algorithm for high-level languages and bytecode
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers. We present copy-and-patch, an extremely fast compilation technique that also pro...
Euclidean Affine Functions and Applications to Calendar Algorithms
We study properties of Euclidean affine functions (EAFs), namely those of the form $f(r) = (α\cdot r + β)/δ$, and their closely related expression $\mathring{f}(r) = (α\cdot r + β)\%δ$, where $r$, $α$, $β$ and $δ$ are integers, and where $/$ and $\%$...
Fast and Robust Vectorized In-Place Sorting of Primitive Types.
Modern CPUs provide single instruction-multiple data (SIMD) instructions. SIMD instructions process several elements of a primitive data type simultaneously in fixed-size vectors. Classical sorting algorithms are not directly expressible in SIMD inst...
Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm
The Sch\"onhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For $N$-bit numbers it has a time bound of $O(N \cdot \log N \cdot \log \log N)$. De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotical...
Fast Random Integer Generation in an Interval
In simulations, probabilistic algorithms and statistical tests, we often generate random integers in an interval (e.g., [0,s)). For example, random integers in an interval are essential to the Fisher-Yates random shuffle. Consequently, popular langua...
Fast recursive division
We present a new recursive method for division with remainder of integers. Its running time is $2K(n)+O(n \\log n)$ for division of a $2n$-digit number by an $n$-digit number where $K(n)$ is the Karatsuba multiplication time. It pays in p ractice for...
How to read floating point numbers accurately
Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the I...
Left Recursion in Parsing Expression Grammars
Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PE...
Number Parsing at a Gigabyte per Second
With disks and networks providing gigabytes per second, parsing decimal numbers from strings becomes a bottleneck. We consider the problem of parsing decimal numbers to the nearest binary floating-point value. The general problem requires variable-pr...
Packrat parsers can support left recursion.
Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead. Unfortunately, the limited support for left recursion in packrat parser imple...
Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen
Abstract Der bei einer Summation auftretende Rundungsfehler kann als Maß für die Güte des verwendeten Verfahrens gelten. Im folgenden werden für mehrere Summierungsverfahren, unter anderem für das übliche und das Kahan‐Babuška‐Verfahren, a‐priori‐Sch...
Two-way string-matching
article Free Access Share on Two-way string-matching Authors: Maxime Crochemore Univ. Paris, Paris, France Univ. Paris, Paris, FranceView Profile , Dominique Perrin Univ. Paris, Paris, France Univ. Paris, Paris, FranceView Profile Authors Info & Clai...