7 ms·

Also: polymorphic dispatch is faster with OO (which is what Rust/Servo people have been figuring out recently).

by tomp 12y ago

Dewie 12y ago
What does 'faster with OO' mean? Is there some implementation detail that is tied to, or heavily associated with, OO?
- 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.
vardump 12y ago
Yes. If you can generate code on the fly [1], you can handle a subset of cases very efficiently. [1]: JIT. Just in case some people confuse concepts, I'm not talking about JVM, virtual machines and such. Just plain runtime machine language generation.
- tomp 12y ago
  The problem with JIT is that it's not very simple. Sure, you can write your own single-purpose runtime-code-generating routine. But the beauty of OO is that it's widely applicable. If you want to achieve comparable speeds with JIT, you pretty much need some sort of a virtual machine; in particular, simple method-at-a-time JITs are not very efficient; you need some sort of measuring or tracing, so that you know what code to compile and how to optimize it.
  - vardump 12y ago
    Sure high performance generic JITs are not simple. NOTE: Following is meant for dynamically dispatched lightweight methods, like those that just read (or compare) or store (or modify) some simple field value or do other simple operations where dispatch and call frame setup costs dominate. In inner loops which are executed enough many times that the codegen overhead is less. The rationale is that branches are very expensive on modern CPUs, especially indirect subroutine (= method or function) calls. Consistently 14-20 clock cycles lost in addition to whatever time call frame setup takes, pushing and popping registers from stack. If inner loop cost is otherwise just a cycle or two and the dispatched method is trivial, it's easy to see how branch mispredict and call setup costs can dominate. In some cases some unrolling and prefetching could be done in addition. In this case I envision routines that fuse (inline) dynamically dispatched (function pointer, message passing, pattern recognition) method inside a loop. A compiler could generate the rules and runtime system can do the actual composition. The method would then be dynamically inlined within the loop. No call, no function pointer call (=vtable), no full pattern recognition, no message dispatch, etc. Just fused, inlined code. Pattern match can't be completely resolved early? Just generate code inside the loop that does the rest of the work with tests and branches. Try the most likely case always first (may require some profiling). Same with other dynamic dispatch. Many cases, but known exponential distribution of probabilities? Inline some most likely cases, dynamically dispatch the rest. Like before, most likely first and some profiling may be required. This way very expensive (data dependent) indirect function call is avoided. Call frame setup and teardown is avoided. The savings can be an order of magnitude for short dispatched methods. Definitely no complete virtual machine needed. Note: Edited multiple times.
Jweb_Guru 12y ago
Not really. At best, dynamic dispatch might be faster with inheritance, but even that's kind of a stretch. Most of the slowness with using trait objects in Rust has little to do with the dispatch itself, but with casting between the types being relatively inefficient and/or unsafe (for a whole host of reasons which also affect other parts of the language). In any case, dynamic dispatch, polymorphic or not, is considerably slower than static polymorphic dispatch, which Rust excels at. Servo's biggest performance wins over Gecko (outside of pervasive parallelism) have come by greatly reducing dynamic dispatch.
- tomp 12y ago
  But, how often is it that dynamic dispatch can be optimized into static dispatch? I imagine it probably cannot be done with most of DOM handling... Isn't Rust's static polymorphic dispatch more-or-less equivalent to what you can do in C++ with templates?
  - kibwen 12y ago
    For a long time there were Servo devs pushing for Rust to feature struct inheritance in order to safely and efficiently implement the DOM. Various proposals were written and prototypes implemented, but they all received criticism from the community (often of the form "this seems like a feature that solves a problem that only Servo will ever have") and no single proposal was a clear winner over the others. Today the Servo devs hack around the issue via `unsafe` blocks and transmuting things willy-nilly, but they're still dissatisfied with it. I expect the issue to be revisited post-1.0. In the meantime, if you'd like to familiarize yourself with some of the proposals, here's a recent-ish summary and discussion: http://discuss.rust-lang.org/t/summary-of-efficient-inheritance-rfcs/494 http://discuss.rust-lang.org/t/summary-of-efficient-inherita...
    - tomp 12y ago
      Right... I'm partially familiar with the development, but AFAIK, the basic goals are basically thin pointers and cheap dynamic dispatch using v-tables, not elimination of dynamic dispatch in favor of static dispatch.

Also: polymorphic dispatch is faster with OO (which is what Rust/Servo people have been figuring out recently).

by tomp 12y ago

Also: polymorphic dispatch is faster with OO (which is what Rust/Servo people have been figuring out recently).

Dewie 12y ago

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

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.

vardump 12y ago

Yes. If you can generate code on the fly [1], you can handle a subset of cases very efficiently. [1]: JIT. Just in case some people confuse concepts, I'm not talking about JVM, virtual machines and such. Just plain runtime machine language generation.

tomp 12y ago
The problem with JIT is that it's not very simple. Sure, you can write your own single-purpose runtime-code-generating routine. But the beauty of OO is that it's widely applicable. If you want to achieve comparable speeds with JIT, you pretty much need some sort of a virtual machine; in particular, simple method-at-a-time JITs are not very efficient; you need some sort of measuring or tracing, so that you know what code to compile and how to optimize it.
- vardump 12y ago
  Sure high performance generic JITs are not simple. NOTE: Following is meant for dynamically dispatched lightweight methods, like those that just read (or compare) or store (or modify) some simple field value or do other simple operations where dispatch and call frame setup costs dominate. In inner loops which are executed enough many times that the codegen overhead is less. The rationale is that branches are very expensive on modern CPUs, especially indirect subroutine (= method or function) calls. Consistently 14-20 clock cycles lost in addition to whatever time call frame setup takes, pushing and popping registers from stack. If inner loop cost is otherwise just a cycle or two and the dispatched method is trivial, it's easy to see how branch mispredict and call setup costs can dominate. In some cases some unrolling and prefetching could be done in addition. In this case I envision routines that fuse (inline) dynamically dispatched (function pointer, message passing, pattern recognition) method inside a loop. A compiler could generate the rules and runtime system can do the actual composition. The method would then be dynamically inlined within the loop. No call, no function pointer call (=vtable), no full pattern recognition, no message dispatch, etc. Just fused, inlined code. Pattern match can't be completely resolved early? Just generate code inside the loop that does the rest of the work with tests and branches. Try the most likely case always first (may require some profiling). Same with other dynamic dispatch. Many cases, but known exponential distribution of probabilities? Inline some most likely cases, dynamically dispatch the rest. Like before, most likely first and some profiling may be required. This way very expensive (data dependent) indirect function call is avoided. Call frame setup and teardown is avoided. The savings can be an order of magnitude for short dispatched methods. Definitely no complete virtual machine needed. Note: Edited multiple times.

Jweb_Guru 12y ago

Not really. At best, dynamic dispatch might be faster with inheritance, but even that's kind of a stretch. Most of the slowness with using trait objects in Rust has little to do with the dispatch itself, but with casting between the types being relatively inefficient and/or unsafe (for a whole host of reasons which also affect other parts of the language). In any case, dynamic dispatch, polymorphic or not, is considerably slower than static polymorphic dispatch, which Rust excels at. Servo's biggest performance wins over Gecko (outside of pervasive parallelism) have come by greatly reducing dynamic dispatch.

tomp 12y ago
But, how often is it that dynamic dispatch can be optimized into static dispatch? I imagine it probably cannot be done with most of DOM handling... Isn't Rust's static polymorphic dispatch more-or-less equivalent to what you can do in C++ with templates?
- kibwen 12y ago
  For a long time there were Servo devs pushing for Rust to feature struct inheritance in order to safely and efficiently implement the DOM. Various proposals were written and prototypes implemented, but they all received criticism from the community (often of the form "this seems like a feature that solves a problem that only Servo will ever have") and no single proposal was a clear winner over the others. Today the Servo devs hack around the issue via `unsafe` blocks and transmuting things willy-nilly, but they're still dissatisfied with it. I expect the issue to be revisited post-1.0. In the meantime, if you'd like to familiarize yourself with some of the proposals, here's a recent-ish summary and discussion: http://discuss.rust-lang.org/t/summary-of-efficient-inheritance-rfcs/494 http://discuss.rust-lang.org/t/summary-of-efficient-inherita...
  - tomp 12y ago
    Right... I'm partially familiar with the development, but AFAIK, the basic goals are basically thin pointers and cheap dynamic dispatch using v-tables, not elimination of dynamic dispatch in favor of static dispatch.