Java Newsletter by Glen McCluskey - Issue 5
Issue #005
May, 1996
Contents
- Comparing C/C++ with Java Part 5 - Multiple Inheritance
- Sorting in Java
- Java Program Packaging Part 3 - Protected/Default
- Performance - Method Call Overhead
COMPARING C/C++ WITH JAVA PART 5 - MULTIPLE INHERITANCE
Suppose that you have two C++ classes:
class A {
public:
int x;
void f();
};
class B {
public:
int y;
void g();
};
and a third class that derives or inherits ("extends") from both of these:
class C : public A, public B {
// stuff
};
Inheriting from multiple base classes is called "multiple inheritance" or MI for short.
Like templates that we discussed in issue #004, multiple inheritance adds to the complexity of C++, while offering a solution to some particular kinds of programming problems. One type of issue with programming using MI is in deciding which of a set of conflicting inherited names "wins".
Java does not have multiple inheritance. It does, however, have a way of doing some of what MI is intended for, relative to inheriting attributes. In Java there is a language feature called an interface, which looks like this:
public interface Orderable {
// return < 0 if p1 < p2, 0 if equal, > 0 if p1 > p2
public int compareTo(Object p1, Object p2);
}
This looks somewhat like a class, except that all the methods are abstract, that is, are not implemented immediately but serve as placeholders.
What is an interface used for? Suppose that you want to ensure that a particular class has certain properties, in the present case that it defines the method compareTo() to order objects. You can enforce this by requiring that the class implement interface Orderable:
public class xxx implements Orderable {
public int compareTo(Object p1, Object p2)
{
int n1 = ((Integer)p1).intValue();
int n2 = ((Integer)p2).intValue();
return n1 - n2;
}
}
Why do we care about this? In the next section we will talk about sorting in Java. To write a semi-general sort method, it's necessary to assume that the objects within a Vector of objects to be sorted have some ordering method available to rank them. Java by default has no way of ordering two arbitrary objects.
By defining an Orderable interface, and either sorting a vector of Orderables (that is, a vector of object types where the type is defined to implement Orderable), or sorting a Vector of Objects with a compareTo() method passed to the sort routine via a method wrapper (see next section), we can ensure that a compareTo() method is available.
An interface is sort of like a base class for a class. If you have an Orderable reference:
Orderable or = null;
it's possible to assign to it a reference to an object type that implements Orderable:
xxx x = new xxx();
or = x;
Again, if we have an Orderable object reference, we can be sure that a method call like:
or.compareTo(p1, p2)
will be valid.
SORTING IN JAVA
In the last issue we talked about sorting in Java and said that there's no approach to sorting that's really similar to qsort() in C/C++. A couple of people wrote to me about this and suggested a technique that does in fact have some similarities.
The idea is to write a sort method that accepts a Vector of Object references, along with a class object instance that is a wrapper for a compareTo() method as illustrated above. The sort routine will iterate over the vector and call out to the compare method to determine the ordering of any two objects. Specifically, this would look like:
import java.util.Vector;
// Orderable interface
interface Orderable {
// return < 0 if p1 < p2, 0 if equal, > 0 if p1 > p2
public int compareTo(Object p1, Object p2);
};
// wrapper for a compareTo() method for ordering Strings
class Ord implements Orderable {
public int compareTo(Object p1, Object p2)
{
return ((String)p1).compareTo(((String)p2));
}
}
public class Sort {
public static void sort(Vector v, Orderable or)
{
if (v == null || or == null)
; // give error of some kind
// get vector size
int n = v.size();
// sort
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// do comparison
if (or.compareTo(v.elementAt(i),
v.elementAt(j)) > 0) {
Object ti = v.elementAt(i);
Object tj = v.elementAt(j);
v.setElementAt(tj, i);
v.setElementAt(ti, j);
}
}
}
}
// driver program
public static void main(String args[])
{
Vector v = new Vector();
int N = 100;
int i = 0;
// add some strings
for (i = 0; i < N; i++)
v.addElement("xxx" + i);
// sort them
Sort.sort(v, new Ord());
// display the sorted list
for (i = 0; i < N; i++)
System.out.println((String)v.elementAt(i));
}
}
This code can be tuned in various ways (starting with the sort algorithm) but is illustrative of the technique. We can implement any sort strategy we want on a Vector of objects simply by changing the ordering method. For example, saying:
class Ordrev implements Orderable {
public int compareTo(Object p1, Object p2)
{
return -((String)p1).compareTo(((String)p2));
}
}
...
Sort.sort(v, new Ordrev());
will reverse the sorting order for Strings. In this particular example, Strings have a compareTo() method already defined, and we simply cast the Object references to Strings and call this method. Note that if the wrong compareTo() wrapper instance is used, then an illegal cast will be attempted, resulting in an exception being thrown. For example, the above case expects a String, and will generate an exception ("ClassCastException") if the objects we pass in are actually Integers. The "instanceof" operator can be used to help sort things out.
In production code we'd have Orderable defined in a separate source file. Ord might or might not be in its own file, depending on stylistic preferences. Ord is simply a wrapper for a particular compareTo() method. In C or C++ we would pass in a function pointer directly, but Java has no user-visible pointers and no global functions.
If we critique this approach and compare it to qsort(), there are some notable differences and some similarities:
- This approach is higher-level than qsort(), because it doesn't fool with pointers and sizes of objects and so on.
- This approach cannot be used to directly sort vectors of fundamental data types like int or double. They must be sorted using object wrappers.
- Both approaches require calling out to a function or method that is used to order elements. Such calls are expensive.
- This approach has some overhead in accessing and setting Vector element slots. There is method call overhead, as well as the subscript range checking done each time within a method like elementAt().
It's possible to write a similar type of method for doing binary searches, kind of like bsearch() in the C library.
JAVA PROGRAM PACKAGING PART 3 - PROTECTED/DEFAULT
In issue #004 we talked about public and private fields. When public is applied to a method or variable:
public int x = 37;
public void f() {}
it means that the method or variable is visible everywhere, while a private method or variable:
private int x = 37;
private void f() {}
is visible only within the class where it is defined.
Two other levels of visibility are protected:
protected int x = 37;
and the default when no keyword is specified:
void f() {}
These are identical except in one case. For both of these levels, the method or variable is visible in the class where it's defined and to subclasses and non-subclasses from the same package. For example:
// file pack1/A.java
package pack1;
public class A {
protected int x = 0;
int f() {return x;}
public static void main(String args[]) {}
}
class B extends A {
void g()
{
A p = new A();
int i = p.x + p.f();
}
}
class C {
void g()
{
A p = new A();
int i = p.x + p.f();
}
}
while not being accessible from other packages:
// file pack1/AA.java
package pack1;
public class AA {
protected int x = 0;
int f() {return x;}
public static void main(String args[]) {}
}
// file pack2/BB.java
package pack2;
import pack1.AA;
class BB extends AA {
void g()
{
AA p = new AA();
int i = p.x + p.f(); // error here
}
}
class CC {
void g()
{
AA p = new AA();
int i = p.x + p.f(); // error here
}
}
Where protected and the default differ is in whether they are inherited by a subclass in a different package. For example:
// file pack1/D.java
package pack1;
public class D {
int x = 37;
protected int y = 47;
public static void main(String args[]) {}
}
// file pack2/E.java
package pack2;
import pack1.D;
class E extends D {
void f()
{
int i = x; // error here
int j = y; // OK here
}
}
There are a couple more issues with packaging that we will explore in future issues.
PERFORMANCE - METHOD CALL OVERHEAD
In a language such as C or C++ you may have encountered the idea that calling a function ("method" in Java) has some time overhead associated with it beyond the actual processing done by the function. For example, with this code:
int max(int a, int b)
{
return (a > b ? a : b);
}
int main()
{
int i = 0;
int j = 0;
int k = 0;
long n = 50000000L;
while (n-- > 0)
//k = max(i, j);
k = (i > j ? i : j);
return 0;
}
coding the actual calculation of the maximum of two ints is about three times as fast when done inline as when done via a call to max(). In C++ there is an "inline" specifier that can be used to specify that a function should be expanded inline if possible.
Function call overhead is caused by various factors, including time spent in setting up stack frames, actual transfer of control to the called function, and so on.
Java also has overhead with calling methods. For example, in this code:
public class xx {
public /*final*/ int max(int a, int b)
{
return (a > b ? a : b);
}
public static void main(String args[])
{
int i = 0;
int j = 0;
int k = 0;
int n = 1000000;
xx p = new xx();
while (n-- > 0)
//k = p.max(i, j);
k = (i > j ? i : j);
}
}
doing the max computation inline is about twice as fast as calling the method max().
In Java one reason for overhead is that methods are virtual by default, that is, the actual method that is called is determined at run time by considering the actual object type. For example, the Object class, from which all other class types derive, has a method hashCode() defined in it. A class that extends from Object may also have a hashCode() method. If in a program you have an Object reference, and wish to call hashCode():
public void f(Object p)
{
int h = p.hashCode();
}
then the actual version of hashCode() that is called depends on whether p is "really" an Object or refers to an instance of a class derived from Object.
So, because a method is virtual by default, it is difficult or impossible to expand it as inline (in C++ there have been some clever optimizations that have been used to make virtual functions inline, but this is a hard problem).
The keyword "final" can be used to say "this method cannot be overridden" by another method in a derived class. With JDK 1.0 this optimization has no effect, but over the long term specifying "final" is likely to be an important optimization. Note that "final" has various other meanings, for example saying:
final int N = 10;
marks N as unchangeable, and a final class cannot be extended from.
Should you worry about method call overhead? Most of the time, no. It's only when you have a method that's called very heavily in a loop that this overhead matters.
ACKNOWLEDGEMENTS
Thanks to Thierry Ciot, Irv Kanode, Mike Paluka, and Alan Saldanha for help with proofreading.
SUBSCRIPTION INFORMATION / BACK ISSUES
To subscribe to the newsletter, send mail to majordomo@world.std.com with this line as its message body:
subscribe java_letter
Back issues are available via FTP from:
rmii.com /pub2/glenm/javalett
or on the Web at:
There is also a C++ newsletter. To subscribe to it, say:
subscribe c_plus_plus
using the same majordomo@world.std.com address.
-------------------------
Copyright (c) 1996 Glen McCluskey. All Rights Reserved.
This newsletter may be further distributed provided that it is copied in its entirety, including the newsletter number at the top and the copyright and contact information at the bottom.
Glen McCluskey & Associates
Professional Computer Consulting
Internet: glenm@glenmccl.com
Phone: (800) 722-1613 or (970) 490-2462
Fax: (970) 490-2463
FTP: rmii.com /pub2/glenm/javalett (for back issues)
Web: http://www.rmii.com/~glenm
