1CS553 Lecture Compiling Object Oriented Languages 3Compiling Object Oriented Languages Last time– Dynamic compilation Today– Introduction to compiling object oriented languages– What are the issues?CS553 Lecture Compiling Object Oriented Languages 4What is an Object-Oriented Programming Language? Objects– Encapsulate code and data Inheritance– Supports code reuse and softwareevolution Subtype polymorphism– Can use a subclass wherever a parentclass is expected Dynamic binding (message sends)– Binding of method name to code is donedynamically based on the dynamic typeof the (receiver) objectPersonStudent TeacherPerson p = new Person;Student s = new Student;PrintName(p);PrintName(s);PrintName(Person p);p.reprimand();CS553 Lecture Compiling Object Oriented Languages 5Implementation: Inheritance of Instance Variables Goal– Lay out object for type-independent instance variable access Solution (single inheritance)– Prefixing: super-class fields are at beginning of object ExampleStudentNameIDPersonNameTeacherNameSalaryCS553 Lecture Compiling Object Oriented Languages 6Implementation: Dynamic Binding Problem– The appropriate method depends on the dynamic type of the objecte.g., p.reprimand() Solution– Create descriptor for each class (not object) encoding available methods– Encode pointer to class descriptor in each object– Lay out methods in class descriptor just like instance variables Usage summary– Load class descriptor pointer from object– Load method address from descriptor– Jump to methodStudentgetNamereprimandworkhardPersongetNameTeachergetNamereprimandparty2CS553 Lecture Compiling Object Oriented Languages 7Why are Object-Oriented Languages Slow? Dynamism– Code– Data Style– Granularity (lots of small objects)– Exploit dynamism Other reasons– High-level (modern) features such as safety– Garbage collectionCS553 Lecture Compiling Object Oriented Languages 8Dynamism: Code Dynamic binding– What code gets executed at a particular static message send?– It depends, and it may change Example class rectangle extends shape { int length() { ... } int width() { ... } int area() { return (length() * width()); } } class square extends rectangle { int size; int length() { return(size); } int width() { return(size); } }? ?rect.area();sq.area();CS553 Lecture Compiling Object Oriented Languages 9Cost of Dynamic Binding Direct cost– Overhead of performing dynamic method invocation Indirect cost– Inhibits static analysis of the code Example class rectangle:shape { int length() { ... } int width() { ... } int area() { return (length() * width()); } } Driessen and Holzle (OOPSLA 96), on C++ programs median of 5.2%total execution time spent on dynamic dispatchWant to inline and assign to registers, etc.CS553 Lecture Compiling Object Oriented Languages 10Dynamism: Data Object instance types are not statically apparent– Need to be able to manipulate uniformly– Boxing: wrap up all data and reference it with a pointer Example Integer n = new Integer(33);type descriptordata (int)pointern3CS553 Lecture Compiling Object Oriented Languages 11Cost of Dynamism: Data Direct cost– Overhead of actually extracting data– e.g., 2 loads versus 0 (if data already in a register) Indirect cost– More difficult to statically reason about dataCS553 Lecture Compiling Object Oriented Languages 12Style Sometimes programmers write C-style code in OO languages– Easy: just “optimize” it away Sometimes programmers actually exploit dynamism– Hard: it can’t just be “optimized away” Programmers create many small objects– Thwarts local analysis– Exacerbates dynamism problem– Huge problem for pure OO languages Programmers create many small methods– Methods to encapsulate data– e.g. Methods to get and set member fieldsCS553 Lecture Compiling Object Oriented Languages 13A Concrete Example: Java High-level and modern– Object-oriented– Mobile/portable (standard bytecode IL)– Multithreaded (great for structuring distributed and UI programs)– Garbage collected– Dynamic class loading– Reasonable exception system– Rich standard librariesCS553 Lecture Compiling Object Oriented Languages 14Approaches to Implementing Java Interpretation– Extremely portable– Simple stack machine– Performance suffers– Interpretation overhead– Stack machine (no registers) Direct compilation– Compile the source or bytecodes to native code– Sacrifices portability– Can have very good performance4CS553 Lecture Compiling Object Oriented Languages 15Why is Java Slow? Bytecode interpretation?– Not a good answerCS553 Lecture Compiling Object Oriented Languages 16Why is Java Slow? Impediments to performance– Flexible array semantics– Run-time checks (null pointers, array bounds, types)– Precise exception semantics thwart optimization– Dynamic class loading thwarts optimization– Even the class hierarchy is dynamic– Multithreading introduces synchronization overhead– Lots of memory references (poor cache performance). . . and all the usual OO challengesCS553 Lecture Compiling Object Oriented Languages 17 Consider matrix multiplicationfor (i=0; i<m; i++) for (j=0; j<p; j++) for (k=0; k<n; k++) C[i][j] += A[i][k] * B[k][j]; Costs– 6 null pointer checks (with just 2 floating point operations!)– 6 index checks Can we optimize this code?– Precise exception model– Exception semantics inhibit removal or reordering– No multidimensional arrays– Rows may aliasScientific Programming and JavaCS553 Lecture Compiling Object Oriented Languages 18More on Matrix MultiplicationWhy can’t we just do this. . . ?if (m <= C.size(0) && p <= C.size(1) && m <= A.size(0) && n <= A.size(1) && n <= B.size(0) && p <= B.size(1)) {for (i=0; i<m; i++) for (j=0; j<p; j++) for (k=0; k<n; k++) C[i][j] += A[i][k] * B[k][j]; } else { raise exception } No out-of-bounds checks, right?5CS553 Lecture Compiling Object Oriented Languages 19Exceptions in Java Exceptions in Java are precise– The effects of all statements and expressions before a thrown exceptionmust appear to have taken place, and– The effects of all statements or expressions after a thrown exception mustappear not to have taken place Implications– Must be very careful or clever when– Eliminating checks or– Reordering statementsCS553 Lecture Compiling Object Oriented Languages 20 Idea– Create two versions of a block of code– One is guaranteed not to except and is optimized