in reply to Re^6: rough approximation to pattern matching using local (Multi Subs)
in thread rough approximation to pattern matching using local

The extra caret was indeed bogus. Fixed below.

Afaict, Rakudo is doing compile time resolution of the dispatch target for almost all calls to multisubs found in existing code. Aiui, if the leading candidates for a dispatch only use static nominal typing (specifying types like int, Int, Str, a class, role, etc. for their parameters) then resolution of which to finally pick is done at compile-time.

(Operators are multisubs so it's a good job that their dispatch target is being resolved at compile time or current Rakudo would be even slower!)

The code I wrote led to run-time resolution because A) Rakudo is currently converting a literal as a parameter (eg the 1 in `multi sub c (1) {}`) in to a 'where' constraint (`multi sub c ($ where 1) {}`) and B) there's no static analysis in place to reduce this simple 'where' constraint to a finite set of values (which is what would enable compile-time resolution despite use of a `where` constraint).

If Rakudo treated a literal parameter as a singleton value (i.e.not doing the shortcut A), or did basic analysis of simple `where` constraints to extract finite sets of values when possible (i.e. fixing B), then use of literals in a leading multisub candidate would no longer disable compile-time resolution.

Here's a hack workaround just to demonstrate that this can actually work in principle: 

my $t;

sub a { }; 
sub b { }; 

enum A <0>;
enum B <1>;
multi sub c (A) { }; 
multi sub c (B) { }; 

for ^7 {
  my $iterations = 10 ** $_;
  say $iterations ~ " calls";
  $t = now;
  for ^$iterations { $_ %% 2 ?? a() !! b() };
  say "regular: {now - $t}";
  $t = now;
  for ^$iterations { c($_ %% 2 ?? A !! B) };
  say "multi:   {now - $t}";
}

[download]

This yields: 

1 calls
regular: 0.00633665
multi:   0.0044097
....
1000000 calls
regular: 5.3146894
multi:   5.2373117

[download]

So, using this enum trick, the times for these multisubs have basically caught up with the times for the plain subs. Resolution is compile-time with enums because Rakudo treats them as a finite set of values (as it should, because that's exactly what they are) and that theoretically enables (and in this case Rakudo actually implements) compile-time resolution.

Some relevant excerpts from the relevant design doc include:

The set of constraints for a parameter creates a subset type that implies some set of allowed values for the parameter. The set of allowed values may or may not be determinable at compile time. When the set of allowed values is determinable at compile time, we call it a static subtype.

... Note that all values such as 0 or "foo" are considered singleton static subtypes. ...

As a first approximation for 6.0.0, subsets of enums are static, and other subsets are dynamic. We may refine this in subsequent versions of Perl.

Of course, this still leaves the gulf (an order of magnitude? two?) between the basic sub call performance of Rakudo and of perl.

Aiui there are tons of bog standard optimization techniques (speed and RAM usage) that still haven't yet been applied to Rakudo, NQP, and MoarVM. Aiui more of these optimizations are supposed to arrive this year but most will come in later years.

I plan to update this thread if I find out any useful info about whether or not Rakudo sub calls might reasonably be expected to one day (year) eventually catch up with (maybe even overtake?) perl's performance.

»ö« . o O ( "the celebrity tell-all of the Perl-6 cult?" )

Replies are listed 'Best First'.
Re^8: rough approximation to pattern matching using local (Multi Subs)
by BrowserUk (Patriarch) on Feb 04, 2015 at 19:53 UTC

    First. Thankyou for taking the time to respond to this. It is appreciated.

    Aiui, if the leading candidates for a dispatch only use static nominal typing (specifying types like int, Int, Str, a class, role, etc. for their parameters) then resolution of which to finally pick is done at compile-time.

    That implies that if I call a multi-sub defined to take (say) two Int vars; but I pass it integers embedded in ordinary scalars; then it will fail? What if the integers are being stored as strings in the PV of the scalar?

    If Perl6 is to retain scalars; but people write their modules using Ints & Strs etc. for efficiency; then it either forces their users to also use Ints & Strs etc. or multi-subs will have to use runtime resolution.

    Alternatively, I guess the programmers could add more multi-subs for each of the permutations of combinations of subscalar types and defined types; but that is a combinatorial nightmare.

    Of course, this still leaves the gulf (an order of magnitude? two?) between the basic sub call performance of Rakudo and of perl.

    Aiui there are tons of bog standard optimization techniques (speed and RAM usage) that still haven't yet been applied to Rakudo, NQP, and MoarVM. Aiui more of these optimizations are supposed to arrive this year but most will come in later years.

    That's understandable, it took Java many years and iterations to sort out their performance problems; and they basically had to invent(*) (or at least, radically refine and generalise) JIT compilation to do it.

    But my gut feel is that there are several Perl6 design elements Multi-subs, junctions, autothreading, to name but 3 -- that individually make writing an efficient runtime implementation exceedingly hard.

    And writing a single VM to deal with all of those; plus the ability to introspect and reflect on everything including the kitchen sink; the neighbours dog; uncle Tom Cobbly an'all; makes for ... well, what we've seen till now.

    I am aware smalltalk had a form of JIT before Java; and of course, LISP did it first; but Java refined it, generalised it, popularised it, and brought it to the main stream.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
    In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
      Quick reminder for any visitors reading this:

      »»» This post is about the immature Perl 6, not the rock solid Perl 5 «««

      If Perl6 is to retain scalars; but people write their modules using Ints & Strs etc. for efficiency; then it either forces their users to also use Ints & Strs etc. or multi-subs will have to use runtime resolution.

      No. (Or, rather, the user doesn't need to know they're using Ints, Strs, etc.) 

      multi sub a ( Int $, Int $ ) {}
my ($foo, $bar) = 1, 2;
say $foo.VAR; says 'Any'
say $foo.WHAT; # says '(Int)'
a($foo, $bar); # call is resolved at compile time

      [download]

      No type is declared for the container $foo. So it's `of` type defaults to Any. This serves as a constraint on what can be assigned to $foo -- anything that is of type Any or a subtype (anything but Junction or Mu).

      The type of the contained value is distinct. In this case the compiler infers that it's an Int. An Int is a subtype of Any so the assignment is OK.

      Both of these types are known at compile time.

      The type info available at compile-time includes:

      • The types inferred by the compiler for literals;
      • The types defaulted to for multisub parameters for which no type is explicitly specified;
      • The types explicitly specified for multisub parameters, if any;
      • The types defaulted to for call args for which no type is explicitly specified;
      • The types explicitly specified by the caller, if any.

      Even if the coder calls multisubs without adding type info to their args the call will still be resolved at compile-time if there's enough type info available at compile-time.

      »ö« . o O ( "the celebrity tell-all of the Perl-6 cult?" )

[reply]
[d/l]

        Warning: Pseudo-P6 :) 

        multi sub a ( Int $, Int $ ) {}
multi sub a ( Int $, Str $ ) {}
multi sub a ( Str $, Int $ ) {}
multi sub a ( Str $, Str $ ) {}

my( $x, $y ) = <>.split' ';

a( $x, $y ); ## How do you determine which multi-sub to invoke at comp
+ile time?

        [download]
        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
        In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
[d/l]

In Section Seekers of Perl Wisdom