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)A modified ziggurat algorithm for generating exponentially- and normally-distributed pseudorandom numbers
The Ziggurat Algorithm is a very fast rejection sampling method for generating PseudoRandom Numbers (PRNs) from common statistical distributions. The algorithm divides a distribution into rectangular layers that stack on top of each other (resembling...
An Efficient Method for Generating Discrete Random Variables with General Distributions
article Free Access Share on An Efficient Method for Generating Discrete Random Variables with General Distributions Author: Alastair J. Walker Department of Electrical Engineering, University of Witwatersrand, 1 Jan Smuts Ave., Johnnesburg 2001, Sou...
An Extension of the String-to-String Correction Problem
article Free Access Share on An Extension of the String-to-String Correction Problem Authors: Robert A. Wagner Department of Systems and Information Sciences, Vanderbilt University, Nashville, TN Department of Systems and Information Sciences, Vander...
A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake
The modern CPU's design, which is composed of hierarchical memory and SIMD/vectorization capability, governs the potential for algorithms to be transformed into efficient implementations. The release of the AVX-512 changed things radically, and motiv...
Base64 encoding and decoding at almost the speed of a memory copy
Many common document formats on the Internet are text-only such as email (MIME) and the Web (HTML, JavaScript, JSON and XML). To include images or executable code in these documents, we first encode them as text using base64. Standard base64 encoding...
Computationally easy, spectrally good multipliers for congruential pseudorandom number generators
Congruential pseudorandom number generators rely on good multipliers, that is, integers that have good performance with respect to the spectral test. We provide lists of multipliers with a good lattice structure up to dimension eight and up to lag ei...
Faster Base64 Encoding and Decoding Using AVX2 Instructions
Web developers use base64 formats to include images, fonts, sounds, and other resources directly inside HTML, JavaScript, JSON, and XML files. We estimate that billions of base64 messages are decoded every day. We are motivated to improve the efficie...
Gaussian random number generators
Rapid generation of high quality Gaussian random numbers is a key capability for simulations across a wide range of disciplines. Advances in computing have brought the power to conduct simulations with very large numbers of random numbers and with it...
Implementing the complex arcsine and arccosine functions using exception handling
We develop efficient algorithms for reliable and accurate evaluatins of the complex arcsine and arccosine functions. A tight error bound is derived for each algorithm; the results are valid for all machine-representable points in the complex plane. T...
LXM: better splittable pseudorandom number generators (and almost as fast)
In 2014, Steele, Lea, and Flood presented SplitMix, an object-oriented pseudorandom number generator (prng) that is quite fast (9 64-bit arithmetic/logical operations per 64 bits generated) and also splittable . A conventional prng object provides a ...
Optimally profiling and tracing programs
This paper presents algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs. Profiling counts the number of times each basic block in a program executes and has a variety ...
Printing floating-point numbers quickly and accurately
This paper presents a fast and accurate algorithm for printing floating-point numbers in both free- and fixed-format modes. In free-format mode, the algorithm generates the shortest, correctly rounded output string that converts to the same number wh...
Scalable statistics counters
Statistics counters are important for purposes such as detecting excessively high rates of various system events, or for mechanisms that adapt based on event frequency. As systems grow and become increasingly NUMA, commonly used naive counters impose...
ScissorGC: scalable and efficient compaction for Java full garbage collection
Java runtime frees applications from manual memory management through automatic garbage collection (GC). This, however, is usually at the cost of stop-the-world pauses. State-of-the-art collectors leverage multiple generations, which will inevitably ...
SLEEF: A Portable Vectorized Library of C Standard Mathematical Functions
In this paper, we present techniques used to implement our portable\nvectorized library of C standard mathematical functions written entirely in C\nlanguage. In order to make the library portable while maintaining good\nperformance, intrinsic functio...
The Monty Python method for generating random variables
We suggest an interesting and fast method for generating normal, exponential, t, von Mises, and certain other important random variables used in Monte Carlo studies. The right half of a symmetric density is cut into pieces, then, using simple area-pr...
Topological sorting of large networks
Topological Sorting is a procedure required for many problems involving analysis of networks. An example of one such problem is PERT. The present paper presents a very general method for obtaining topological order. It permits treatment of larger net...
Understanding and improving JVM GC work stealing at the data center scale
Garbage collection (GC) is a critical part of performance in managed run-time systems such as the OpenJDK Java Virtual Machine (JVM). With a large number of latency sensitive applications written in Java the performance of the JVM is essential. Java ...
User-level Threading
An important class of computer software, such as network servers, exhibits concurrency through many loosely coupled and potentially long-running communication sessions. For these applications, a long-standing open question is whether thread-per-sessi...
When is double rounding innocuous?
Double rounding is the phenomenon that occurs when the result of an operation is rounded to fit some intermediate destination, and then again when delivered to its final destination. This can be a common occurrence when using some floating-point arit...