3 ms·

What does 'faster with OO' mean? Is there some implementation detail that is tied to, or heavily associated with, OO?

by Dewie 12y ago

lostcolony 12y ago
I assume it's based on (this is a bit hand wavy) the fact that in an OO language, calling the method merely needs to resolve the address space of the method. With pattern matching, you first have to perform the pattern match to figure out what instruction to execute, and then that resolves to an address. That is, because your data and function are bundled together, having the data means you also know what function to call. Decoupling them, as in a functional paradigm, and passing the data into a pattern match, you have to perform some logic upon the data to figure out what function to apply to it.
- noblethrasher 12y ago
  But, a series of pattern matching expressions can compile down to a bunch of sealed/final classes that descend from a common base class. In that case, it would still end up using a vtable[1]. I think this is how it works in F# and Scala. [1] I think that the JITs for the CLR and JVM can do better than vtables in the cases of sealed/final classes.
  - seanmcdirmid 12y ago
    I am sure it doesn't work with way in either scala or F#. You can use classes to represent structure, but the matching is still extrinsic and can't use a table given the flexibility of both languages (you don't just match on class).
    - noblethrasher 12y ago
      Just curious… why not? Isn't a class definition just a type constructor? For instance, if I have a class, Foo, with three types of fields: int, bool, and string, isn't that the same as: Foo of int * bool * string I don't have a full PC handy, but, while learning F# a few years ago, I remember using Reflector to analyze an assembly generated by FSC.exe and the pattern match turned into a class hierarchy. It may not work for all kinds of pattern matching, but that seems like the most straightforward way of handling sum types. What am I missing?
      - seanmcdirmid 12y ago
        I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely. OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.
        noblethrasher 12y ago
        Looks like you're correct; I just examined some F# code in LINQPad 4, and the IL has a bunch of `isinst` instructions to check the type at runtime, and no `callvirts` to the one pattern matching expression that I created. https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd
tomp 12y ago
Method dispatch using a vtable (a pointer, embedded in the object, pointing to a record of methods) is way faster than practically any other form of dynamic dispatch (except calls of known functions, of course). To support it, you pretty much need some form of single inheritance/subtyping (C++ does support multiple inheritance, but it significantly complicates the implementation). Rust's single-dispatch type-classes and Go's interfaces are dispatched in a similar way, but the record of functions is passed along the pointer to object as a "fat pointer". Servo people figured out that that is too wasteful/slow compared to C++-style vtable approach.

What does 'faster with OO' mean? Is there some implementation detail that is tied to, or heavily associated with, OO?

by Dewie 12y ago

What does 'faster with OO' mean? Is there some implementation detail that is tied to, or heavily associated with, OO?

I assume it's based on (this is a bit hand wavy) the fact that in an OO language, calling the method merely needs to resolve the address space of the method. With pattern matching, you first have to perform the pattern match to figure out what instruction to execute, and then that resolves to an address. That is, because your data and function are bundled together, having the data means you also know what function to call. Decoupling them, as in a functional paradigm, and passing the data into a pattern match, you have to perform some logic upon the data to figure out what function to apply to it.

noblethrasher 12y ago
But, a series of pattern matching expressions can compile down to a bunch of sealed/final classes that descend from a common base class. In that case, it would still end up using a vtable[1]. I think this is how it works in F# and Scala. [1] I think that the JITs for the CLR and JVM can do better than vtables in the cases of sealed/final classes.
- seanmcdirmid 12y ago
  I am sure it doesn't work with way in either scala or F#. You can use classes to represent structure, but the matching is still extrinsic and can't use a table given the flexibility of both languages (you don't just match on class).
  - noblethrasher 12y ago
    Just curious… why not? Isn't a class definition just a type constructor? For instance, if I have a class, Foo, with three types of fields: int, bool, and string, isn't that the same as: Foo of int * bool * string I don't have a full PC handy, but, while learning F# a few years ago, I remember using Reflector to analyze an assembly generated by FSC.exe and the pattern match turned into a class hierarchy. It may not work for all kinds of pattern matching, but that seems like the most straightforward way of handling sum types. What am I missing?
    - seanmcdirmid 12y ago
      I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely. OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.
      - noblethrasher 12y ago
        Looks like you're correct; I just examined some F# code in LINQPad 4, and the IL has a bunch of `isinst` instructions to check the type at runtime, and no `callvirts` to the one pattern matching expression that I created. https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd

tomp 12y ago

Method dispatch using a vtable (a pointer, embedded in the object, pointing to a record of methods) is way faster than practically any other form of dynamic dispatch (except calls of known functions, of course). To support it, you pretty much need some form of single inheritance/subtyping (C++ does support multiple inheritance, but it significantly complicates the implementation). Rust's single-dispatch type-classes and Go's interfaces are dispatched in a similar way, but the record of functions is passed along the pointer to object as a "fat pointer". Servo people figured out that that is too wasteful/slow compared to C++-style vtable approach.