Transcript Optimization of Point Selection on Digital Ink Curves

Lightweight Abstraction
for Mathematical Computation
in Java
Pavel Bourdykine and Stephen M. Watt
Department of Computer Science
Western University
London Ontario, Canada
CASC 2012
Maribor, Slovenia
3-6 September 2012
1
The Context

Modern programming languages allow the
creation of new abstractions
◦ Hide implementation details
◦ Eliminate programming errors
◦ Allow future changes
Z/5Z
is different from
Z/5Z [x] is different from
int
int[ ]
2
The Problem

In the popular scientific programming languages,
these mechanisms aren’t good enough.

In C++,
typedef doesn’t create a distinct type.

In Java,
adding a class abstraction is very costly.
3
The Problem

In symbolic mathematical computing,
we often have a great many small values.

E.g.
◦ Poly coeffs in Z mod small prime
◦ Packed exponent vectors

Extra storage allocation.
Several 100% overhead.
4
The Problem
So libraries writers cheat….
 Compromise abstractions….
 Circumvent the system ….


The standard Java libraries use int
and long values to represent
◦ Colours, Layout strategies, Border types, etc
instead of abstract types.

I.e. language features aren’t good enough.
5
Swing, undermining abstraction
static Integers
representing different
properties
ints representing
different parameters
Swing, undermining abstraction
legal, but does not
necessarily make sense
same arguments,
different meanings
Would like to DISTINGUISH
between layer and position!
Why?

Machine-supported data types, such as singleand double-word integers and floating point
numbers are primitive types in Java, and specially
handled.
◦ No storage allocation
◦ No “object” overhead (synchronization, etc)

User-defined types must be classes inheriting
from “Object”, with all the associated overhead.
8
Why?
Primitive type:
127
Defined Java type:
0xFFEA2038
Class 348 | VTable | Locks |
GC Info | Blah |Blah | Blah |
127
Problem multiplies with vectors of these things.
Idea!
Use the Java type system for correctness,
then
 Compile using primitive types.

10
Approach: Objectives
Combine type-safety and low cost
 Improve performance without crippling safety
and expressive power
 It is about opacity
 Framework for a straight forward construction

◦ easy to use
◦ noticeable benefits
Approach: Practice

Want: objects that perform like primitive types
◦ combine the two!

Allow class derivation, inheritance, virtualization
◦ i.e. object properties
◦ WITHOUT the heavy overhead
Want to avoid allocation but keep the type safety
 Works with ANY underlying type!
 This layer of abstraction does not require its own
inheritance structure!

What we would like
new objects
method arguments no
longer ambiguous
But achieve this without losing performance and
rewriting library functions!
Approach: Rules and Restrictions

To keep object properties need to
◦ keep representation field protected
◦ follow Object-Oriented guidelines
Result: Type-check the objects by name

To boost performance and eliminate overhead
◦ keep constructor(s) private
◦ make methods public static
Result: Implement using underlying type
Approach: Rules and Restrictions
Summary:
 Rule 1 Object must have a single protected field
of the underlying type, unless it is a subclass of
an opaque type (and then must have no fields).

Rule 2 Any object constructors must be
declared private.

Rule 3 All methods accessing or modifying the
underlying type field representation must be
declared static.
Approach: Implementation

Annotate opaque classes
◦ @Opaque(“type”) annotation
Type-check regular objects
 Convert annotated classes to use underlying
type representation
 Compile the fast versions

Converter implemented in Java
 Building process automated by Ant

Code Transformation
Annotated opaque class
Code Transformation
Converted opaque class
Compilation Process
Annotated code is analyzed and types recorded.
 All occurrences of opaque types are
substituted with the underlying representation.
 New code is compiled.


Process is automated using Ant.
◦ Compiles original code for type checking.
◦ Backs up the original code, converts it.
◦ Calls compiler again on converted code.
19
Performance
Test performance in terms of execution speed
& memory use
 Test a variety of uses and declarations
◦ cover a wide range of possible applications
 Measure:

regular code
vs.
opaque annotated code
vs.
converted code
Performance: Example I
Usual Definition:
Usage:
Performance: Example I
Opaque Definition:
Usage:
Performance: Example I (time)

Opaque types execute about twice as fast
Performance: Example I (space)

Opaque types are able to reside entirely on the stack,
i.e. no allocation is needed
Performance: Example II
Regular class:
Performance: Example II
Opaque class:
Performance: Example II
Regular class usage:
Opaque class usage:
Performance: Example II (time)

Opaque objects execute 12-15 times faster
Performance: Example II (space)

Even before conversion to underlying type opaque
types use 10-12 times less memory
Performance: Example II
Opaque class:
Performance: Example II
Converted opaque class:
Performance: Example II (time)

Converted (to long[]) opaque types execute 20-25 times faster
Performance: Example II (space)

Converted (to long[]) opaque types use over 15 times less memory
Conclusions
Performance – native levels achieved.
Safety – maintained.
Successfully implemented structures that are
type safe and perform as machine types.
 Code conversion and build process are
automated.
 Performance is well worth the restrictions.
 Sufficient for computer algebra.

Future work

Implement Java generics
◦ Cover all Java language features

Algebra library using opaque types

Native implementation?