Write a Blog >>
SPLASH 2019
Sun 20 - Fri 25 October 2019 Athens, Greece
Tue 22 Oct 2019 11:30 - 12:00 at Room 3A - Session #2

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.

This program is tentative and subject to change.

Tue 22 Oct

vmil-2019-papers
11:00 - 12:30: VMIL 2019 - Session #2 at Room 3A
vmil-2019-papers11:00 - 11:30
Full-paper
Isaac Oscar GarianoVictoria University of Wellington, Richard RobertsVictoria University of Wellington, Stefan MarrUniversity of Kent, Michael HomerVictoria University of Wellington, James NobleVictoria University of Wellington
vmil-2019-papers11:30 - 12:00
Full-paper
Rohan PadhyeUniversity of California, Berkeley, Koushik SenUniversity of California, Berkeley
vmil-2019-papers12:00 - 12:15
Talk
Kiko Fernandez-ReyesUppsala University, Isaac Oscar GarianoVictoria University of Wellington, James NobleVictoria University of Wellington, Tobias WrigstadUppsala University
vmil-2019-papers12:15 - 12:30
Talk