Write a Blog >>
SPLASH 2019
Sun 20 - Fri 25 October 2019 Athens, Greece
Tue 22 Oct 2019 11:30 - 12:00 at Abbey - Session #2 Chair(s): Anthony Canino

We address the problem of dynamically checking if an instance of class S is also an instance of class T. Researchers have designed various strategies to perform constant-time subtype tests. Yet, well-known production implementations degrade to linear search in the worst case, in order to achieve other goals such as constant space and/or efficient dynamic class loading. The fast path is usually optimized for subtype tests that succeed. However, in workloads where dynamic type tests are common, such as Scala’s pattern matching and LLVM compiler passes, we observe that 74%–93% of dynamic subtype tests return a negative result.

We propose a novel scheme for fail-fast dynamic subtype checking. We assign each type a randomly generated type identifier with fixed size and fixed parity. In the compiled version of each class, we store a fixed-width bloom filter, which combines the type identifiers of all its transitive supertypes. At run-time, the bloom filters enable fast refutation of dynamic subtype tests with high probability. If such a refutation cannot be made, the scheme falls back to conventional techniques. This scheme works with multiple inheritance, separate compilation, and dynamic class loading. A prototype implementation of fail-fasts in the JVM provides provides 1.44x–2.74x speedup over HotSpot’s native instanceof, on micro-benchmarks where worst-case behavior is likely.

Tue 22 Oct

Displayed time zone: Beirut change

11:00 - 12:30
Session #2VMIL at Abbey
Chair(s): Anthony Canino SUNY Binghamton
11:00
30m
Full-paper
Which of my Transient Type Checks are not (Almost) Free?
VMIL
Isaac Oscar Gariano Victoria University of Wellington, Richard Roberts Victoria University of Wellington, Stefan Marr University of Kent, Michael Homer Victoria University of Wellington, James Noble Victoria University of Wellington
11:30
30m
Full-paper
Efficient Fail-Fast Dynamic Subtype Checking
VMIL
Rohan Padhye University of California, Berkeley, Koushik Sen University of California, Berkeley
Pre-print
12:00
15m
Talk
Towards Gradual Checking of Reference Capabilities
VMIL
Kiko Fernandez-Reyes Uppsala University, Isaac Oscar Gariano Victoria University of Wellington, James Noble Victoria University of Wellington, Tobias Wrigstad Uppsala University
Pre-print
12:15
15m
Talk
Formal Verification of JIT by Symbolic Execution
VMIL