abstract classes and dynamic binding

Discussion in 'Java' started by conrad, Jul 29, 2008.

  1. conrad

    conrad Guest

    Suppose I have an abstract class GeometricObject
    whose methods getArea and getPerimeter are
    abstract. Then two classes of a specific
    GeometricObject, say, Circle and Square
    implement the two abstract methods.

    Now imagine I have the following:
    GeometricObject obj1 = new Circle(3);
    GeometricObject obj2 = new Square(10);

    How does the JVM know that
    obj1's getArea method is the one
    implemented by the Circle class?

    --
    conrad
    conrad, Jul 29, 2008
    #1
    1. Advertising

  2. conrad

    Stefan Ram Guest

    conrad <> writes:
    >How does the JVM know that
    >obj1's getArea method is the one
    >implemented by the Circle class?


    The type of objects is stored with
    them, and can be accessed at run-time.
    So it can be used by the JVM at run-time.

    Actually, this is the most elementar
    meaning of »object-oriented programming«:
    Dealing with entities with run-time type
    information (by polymorphism).
    Stefan Ram, Jul 29, 2008
    #2
    1. Advertising

  3. conrad

    conrad Guest

    On Jul 28, 9:35 pm, -berlin.de (Stefan Ram) wrote:
    > conrad <> writes:
    > >How does the JVM know that
    > >obj1's getArea method is the one
    > >implemented by the Circle class?

    >
    >   The type of objects is stored with
    >   them, and can be accessed at run-time.
    >   So it can be used by the JVM at run-time.
    >
    >   Actually, this is the most elementar
    >   meaning of »object-oriented programming«:
    >   Dealing with entities with run-time type
    >   information (by polymorphism).


    Makes sense. Thanks.

    --
    conrad
    conrad, Jul 29, 2008
    #3
  4. conrad

    Tom Anderson Guest

    On Mon, 28 Jul 2008, Peter Duniho wrote:

    > On Mon, 28 Jul 2008 19:35:55 -0700, Stefan Ram <-berlin.de>
    > wrote:
    >
    >> conrad <> writes:
    >>
    >>> How does the JVM know that obj1's getArea method is the one
    >>> implemented by the Circle class?

    >>
    >> The type of objects is stored with them, and can be accessed at
    >> run-time. So it can be used by the JVM at run-time.

    >
    > That's all true, but isn't actually how "the JVM knows that obj1's
    > getArea method is the one implemented by the Circle class".
    >
    >> Actually, this is the most elementar meaning of »object-oriented
    >> programming«: Dealing with entities with run-time type information (by
    >> polymorphism).

    >
    > Unless specifically compiled with run-time type information (RTTI), C++
    > has no RTTI.


    A vtable is run-time type information. It isn't RTTI, but it is undeniably
    information about a type that is available at runtime.

    The point i'm making is that i don't think Stefan was using the phrase
    "run-time type information" in the specific C++ sense, but more generally,
    to mean information which the VM can use to resolve virtual method calls
    at runtime. Since this isn't a C++ newsgroup, i'd say that was was
    acceptable use, if perhaps prone to lead to confusion amongst C++
    programmers.

    Anyway, Peter, for completeness, now explain how virtual dispatch works
    when the variable is of interface, not class, type ... :)

    tom

    --
    The glass is twice as big as it needs to be.
    Tom Anderson, Jul 29, 2008
    #4
  5. conrad

    Mark Space Guest

    Peter Duniho wrote:
    > On Mon, 28 Jul 2008 19:35:55 -0700, Stefan Ram <-berlin.de>
    > wrote:
    >
    >> conrad <> writes:
    >>> How does the JVM know that


    >
    > Unless specifically compiled with run-time type information (RTTI), C++
    > has no RTTI. And yet, it handles abstract classes just fine.


    Well, the OP's question was specifically about the JVM. I think that's
    what Stefan was answering. The Java (spec? byte code spec?) system does
    store the type of all objects in their .class files. (Notice Stefan
    never said "RTTI."). And that is how a JVM does it's virtual dispatch.

    I don't think a JVM uses virtual method tables. I guess it might, post
    JIT compilation, but it derives that info from the class types, so
    ultimately I think Stefan's answer is right on.

    Other languages of course may implement polymorphism differently....
    Mark Space, Jul 29, 2008
    #5
  6. conrad

    Tom Anderson Guest

    On Tue, 29 Jul 2008, Peter Duniho wrote:

    > On Tue, 29 Jul 2008 11:51:59 -0700, Mark Space <>
    > wrote:
    >
    >> Peter Duniho wrote:
    >>> On Mon, 28 Jul 2008 19:35:55 -0700, Stefan Ram <-berlin.de>
    >>> wrote:
    >>>
    >>>> conrad <> writes:
    >>>>> How does the JVM know that
    >>>
    >>> Unless specifically compiled with run-time type information (RTTI), C++
    >>> has no RTTI. And yet, it handles abstract classes just fine.

    >>
    >> Well, the OP's question was specifically about the JVM. I think that's
    >> what Stefan was answering. The Java (spec? byte code spec?) system
    >> does store the type of all objects in their .class files. (Notice
    >> Stefan never said "RTTI.").

    >
    > I'm aware that all that information is available, and even said so in my
    > reply.
    >
    >> And that is how a JVM does it's virtual dispatch.

    >
    > "What" is "how"?
    >
    >> I don't think a JVM uses virtual method tables. I guess it might, post
    >> JIT compilation,


    Tangentially, i find this a slightly odd way of looking at things: "A JVM
    does such-and-such. Except after JIT compilation.". That implies that
    before compilation is in some sense the 'normal' situation, and after
    compilation is a special case, whereas i'd say it was the other round.

    Indeed, i believe that the IBM VM doesn't do interpretation at all, and is
    all-compiled - they have two compilers, the full-on one that's the
    equivalent of Sun's compiler, and then a special one which produces crappy
    code but runs really fast, which is used for initial compilation. The idea
    is that the initial compiler is fast enough that compiling a method and
    then running the compiled code is as fast as interpreting it. Doing this
    simplifies their execution model a lot.

    So, anyway, i'd say that JVMs do (AFAIK) use vtables, but might not, pre
    compilation. But ultimately, this is just a terminological difference.

    >> but it derives that info from the class types, so ultimately I think
    >> Stefan's answer is right on.

    >
    > I can't imagine _not_ using v-tables for the JIT-ed code. Looking things up
    > in the type itself would be comparatively so slow, it hardly seems like the
    > right approach. I can see how when the byte code is being interpreted, that
    > might be a more viable solution though.


    Right. But the point Mark and i are making is that a vtable *is* run-time
    type information.

    > If Stefan has some specific knowledge about every JVM that means that
    > they cannot use v-tables either during interpreted execution or in the
    > JIT-ed code, I'd love to know about it. It would be a good learning
    > experience for me. But I find it difficult to believe that Java is
    > sifting through the actual type information just to dispatch virtual
    > function calls, at least when executing JIT-ed code.


    I'm not aware of a JVM that doesn't use vtables in compiled code. However,
    i believe there are/were Smalltalk VMs that didn't. Smalltalk is an
    untyped ('dynamically typed' in modern jargon) language, so, in the
    absence of type inference, nothing about the type of a receiver is known
    at a call site, and that means you can't use vtables. Vtables are based on
    the idea that whatever the receiver is, it must be a subclass of the
    declared class of the variable, and thus the part of its vtable that the
    call site might use is laid out in a predictable way. So, no types, no
    vtables. The general mechanism that these VMs used was, i believe, a
    lookup in the class data structure - even in compiled code.

    However, since this is quite slow, there was a cunning trick: inline
    caches, and for the truly wizardly, polymorphic inline caches. Basically,
    the idea is that the call site stores two bits of information: a pointer
    to a class, and a pointer to the right method in that class. So, if you
    have a call site that does foo.bar(), you might have pointers to the class
    Baz and the method Baz.bar. Then, when execution reached the call site,
    the machine code does the equivalent of:

    fooClass = CLASS OF foo
    IF (fooClass == Baz):
    INVOKE Baz.bar WITH RECEIVER foo
    ELSE:
    barMethod = LOOKUP "bar" IN fooClass
    INVOKE barMethod WITH RECEIVER foo

    Which is pretty quick. Also, it gives the compiler the opportunity to
    inline the Baz.bar call.

    If your compiler is smart enough to accurately predict the receiver type
    at compile time, this is straightforward and effective. If it can't, then
    you need to manage this cache at runtime, and this is where it gets hairy.
    You could do it easily by storing the class and method pointers in
    variables somewhere, and updating them on cache misses. However, what was
    actually done was to write them into the code, and to recompile on cache
    misses!

    This approach could then be extended to handle polymorphic call sites,
    where the receiver type varies enough to defeat the above strategy. There,
    you use a polymorphic inline cache: a series of if-then constructs that
    check for various possible types. If you get a cache miss, you recompile
    to add another one to the list. You have a limit on how many options you
    have, to prevent ballooning of the code at call sites which range over a
    vast number of receiver types, eg obj.toString() in
    PrintStream.print(Object obj).

    Clever, eh?

    tom

    --
    A military-industrial illusion of democracy
    Tom Anderson, Jul 30, 2008
    #6
  7. conrad

    Mark Space Guest

    Tom Anderson wrote:

    > Tangentially, i find this a slightly odd way of looking at things: "A
    > JVM does such-and-such. Except after JIT compilation.". That implies
    > that before compilation is in some sense the 'normal' situation, and
    > after compilation is a special case, whereas i'd say it was the other
    > round.


    Yes, I'm definitely thinking that executing the byte codes directly is
    the "normal" way of doing things. I haven't poked around any JVM
    internals, but I understand that Sun's JVM (surely the most common by
    far) doesn't do JIT compilation until the byte codes are determined to
    be executed frequently. So direct execution of the byte codes is
    certainly the normal case for all code until the JVM decides to do
    something different.

    And yes, I believe/understand that the -server option will precompile
    everything by default, but I'm not considering that "normal" either.
    It's a special option, at least for client machines.
    Mark Space, Jul 31, 2008
    #7
  8. conrad

    Mark Space Guest

    Peter Duniho wrote:

    > I'm aware that all that information is available, and even said so in my
    > reply.


    I think what I was focusing on was this:


    Peter Duniho quoting conrad:
    >> The type of objects is stored with
    >> them, and can be accessed at run-time.
    >> So it can be used by the JVM at run-time.>

    >
    > That's all true, but isn't actually how "the JVM knows that obj1's
    > getArea method is the one implemented by the Circle class".


    "isn't actually how "the JVM [implements polymorphism] ... "

    It's the "isn't" that was bugging me, because I think it is. Maybe you
    meant "isn't the whole story" or something to that effect.


    >
    >> And that is how a JVM does it's virtual dispatch.

    >
    > "What" is "how"?


    Right, it's hidden, and implemented differently depending on what the
    JVM thinks is applicable. We don't know (unlike C++ where I think it's
    more baked into the spec) and that's a good thing.

    Do you really think there's only one way that all JVMs implement
    polymorphism? I assume all JVMs are different, and indeed the
    implementation might change with each version even from the same vendor.
    Knowing the details of one implementation is largely of academic
    interest, imo.

    I try to write good, clear Java and let the compiler and JVM worry about
    the rest.....

    >
    >> I don't think a JVM uses virtual method tables. I guess it might,
    >> post JIT compilation, but it derives that info from the class types,
    >> so ultimately I think Stefan's answer is right on.

    >
    > I can't imagine _not_ using v-tables for the JIT-ed code. Looking


    As Tom mentions, the JVM has a few more tricks than v-tables. Guessing,
    or just knowing, a reference's runtime type, is one. The JVM will
    completely eliminate, or at least abbreviate, v-table dispatch in those
    cases. That's specifically what I was thinking of when I say that post
    JIT the compiler "may" use v-tables. It may use some other method too.
    Mark Space, Jul 31, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. DaKoadMunky
    Replies:
    4
    Views:
    537
    Lee Weiner
    Apr 20, 2004
  2. Matthias Kaeppler
    Replies:
    1
    Views:
    418
    R.F. Pels
    May 22, 2005
  3. Sameer
    Replies:
    4
    Views:
    573
    Roedy Green
    Aug 31, 2005
  4. Manuel
    Replies:
    8
    Views:
    623
    Manuel
    Jan 5, 2006
  5. Replies:
    4
    Views:
    800
    Rolf Magnus
    May 17, 2006
Loading...

Share This Page