Home

Java Subtype Tests in Real-Time

Java Subtype Tests in Real-Time. Krzysztof Palacz and Jan Vitek.

Dynamic subtype tests are frequent operations in Java programs. Naive implementations can be costly in space and running time. The techniques that have been proposed to reduce these costs are either restricted in their ability to cope with dynamic class loading or may suffer from pathological performance degradation penalizing certain programming styles. We present R&B, a subtype test algorithm designed for time and space constrained environments such as Real-Time Java which require predictable running times, low space overheads and dynamic class loading. Our algorithm is constant-time, requires an average of 10.8 bytes per class of memory and has been shown to yield an average 2.5% speedup on a production virtual machine. The Real-Time Specification for Java requires dynamic scoped memory access checks on every reference assignment. We extend R&B to perform memory access checks in constant-time.

I don't recall this paper or this subject being discussed here.

Also see this paper and this presentation.

By Ehud Lamm at 2006-01-07 11:21 | Implementation | OOP | other blogs | 9686 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Jonathan Bachrach's Simple an

Jonathan Bachrach's Simple and Efficient Subclass Test paper includes a comparison with PQE.

By Manuel J. Simoni at Mon, 2006-01-09 23:23 | login or register to post comments

Thanks

I knew I should also check what Bachrach had to offer...

By Ehud Lamm at Tue, 2006-01-10 08:13 | login or register to post comments

Thread safe?

I don't know if anyone still reads this but it doesn't hurt to try.

I've spent an entire afternoon thinking about the thread safety of the range based algorithm (section 5). I have no idea how they come to the conclusion that it is thread-safe. Maybe they interpret the term "thread-safe" differently than I do...

By Ringdingcoder at Thu, 2008-05-08 14:35 | login or register to post comments

Apparently, we do indeed

Apparently, we do indeed interpret it differently. They only seem to imply that the tree is in a consistent state at all times. This is fine by itself but it's not enough for the extends function in Fig. 9 unless there is some external synchronization going on. There can be no way for extends() to read all of pr.low, pr.high and cl.low atomically. Because of this, a thread might see a mixture of values from different generations and produce the wrong answer as a result.

By Ringdingcoder at Thu, 2008-05-08 16:42 | login or register to post comments