Write a Blog >>
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
Times are displayed in time zone: (GMT+03:00) Beirut change

11:00 - 12:30: VMIL 2019 - Session #2 at Abbey
Chair(s): Anthony CaninoSUNY Binghamton
vmil-2019-papers11:00 - 11:30
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
Rohan PadhyeUniversity of California, Berkeley, Koushik SenUniversity of California, Berkeley
vmil-2019-papers12:00 - 12:15
Kiko Fernandez-ReyesUppsala University, Isaac Oscar GarianoVictoria University of Wellington, James NobleVictoria University of Wellington, Tobias WrigstadUppsala University
vmil-2019-papers12:15 - 12:30