ExpandCollapse

+ 1 Felix Performance model

Although Felix is billed as a scripting language, you may have realised by now that it generates C++ code which is then fed to a C++ compiler to generate machine code.

You may have guessed from this behind the scenes behaviour that the Felix developers are concerned with performance.

So now it is official: performance matters.

In fact, Felix is specifically designed to be the fasted general purpose high level systems and application programming language on earth. Some fairly unusual design choices have been made to ensure this is possible.

One of the most obvious is the adoption of the C/C++ object model, which not only enables easy binding to C and C++ code, it also ensure such bindings are typically free of executable glue.

Another driving motivation is actually the origin of the project: a requirement to support millions of threads of control to monitor phone calls in a telephony switch. Such threads need to be very lightweight and provide very fast context switching times. Felix uses fibres called fthreads and a channel synchronisation model based on s-channels to meet this requirement.

More unusual is the highly aggressive inlining strategy: Felix inlines almost everything. Inlining not only dispenses with the overhead of function calling, it provide many other optimisation opportunities such as the ability to optimise parallel assignments including those generated by tail recursive call optisation.

Felix also aggressively replaces variables in {val} style with their initialisers.

+ 1.1 Evaluation Strategies

The inlining stratgey Felix uses is based on a new kind of semantics called sloppy evaluation.

All programming languages provide a combination of two evaluation strategies.

+ 1.1.1 Eager Evaluation in C

Eager evaluation is the strategy used by C when calling a function. Eager evaluation means that arguments are calculated and assigned to parameters prior to calling a function.

Sequential evaluation involves executing one statement, then the next, or evaluating one expression, then the next: this is eager evaluation. in particular, variables are initialised as control flows through their initialisers, and in subsequent statements, the value of the variable determined by the prior initialisation is used.

+ 1.1.2 Lazy Evaluation in C

C also has lazy evaluation. Most C programmers know about short-cut evaluation of the conditional operator: C evaluates the condition expression first, then it evaluates either the value of the true or false branch and uses the evaluated value in subsequent computations. This is an example of lazy evaluation: it is not possible to provide a function with the same semantics in C because both branches would be evaluated first and assigned to parameters, then the function would pick one of the parameters to return. The distinction is clear in the common example:

   px ? *px : 42

where a null pointer dereference is avoided by using the short-cut semantics.

What is less understood is that almost all control flow in C is actually lazy evaluation. This is particularly vital in the {switch} statement where only one of several possible branches are executed.

+ 1.1.3 Sloppy Evaluation in C

C also has a very special evaluation evaluation strategy called sloppy evaluation, which is a way of combining eager and lazy evaluation such that it is not entirely determinate which strategy is used.

The ISO C Standard describes this particular strategy for evaluation of expressions in terms of the method by which it is controlled: sequence points. Sequence points allow the compiler to evaluate certain parts of an expression in one of several orders, including concurrently. The notion of a sequence point is handles side-effects from such evaluation by specifying limitations on when memory writes must be completed. A typical interesting example is:

p[i++]=q[i++];

+ 1.2 Combining strategies

Some languages such as Haskell mandate lazy evaluation almost exclusively. Of course, there are is always some eager semantics or no work would ever be done! Lazy evaluation is often implemented by substitution or inlinling. Note that we're not just talking about function calls, but also any variable set to an expression can be inlined by replacing the variable with the expression it is set to. The ability to do this in a language is known as referential transparency.

Now that you understand the difference between eager and lazy evaluation, it is time to understand Felix evaluation strategy. Felix uses sloppy evaluation by default. This means the compiler is free to evaluate expressions either lazily or eagerly. The compiler tries to choose the fasted possible technique.

The problem is that eager and lazy evaluation has different semantics. The null pointer dereference issue illustrated above is one such case. Another famous one in C is division by zero.

However there are much deeper examples. C++ has a technology called expression templates which uses lazy evaluation to optimise calculation of matrix operations. It does this by collecting a symbolic representation of a calculation and then optimising it symbolically before doing the actual calculation.

Other examples of the differences exist. Iterators, for example, are precisely semantics converters between lazy and eager modes: an iterator visiting a data structure is doing nothing more than scanning a lazily constructed list and actually evaluating it. The canonical example is the lazy list, which is a fundamental data structure known as a stream. The simplest case is a function which generates a sequence of integers. It is an infinite, lazily evaluated list of integers.

In Felix, lazy evaluation is usually represented by inlining. The use of a variable can be replaced by its value. So here:

  val x = 1/0;
  println$ if true then 1 else x endif;

if Felix choses lazy evaluation by replacing {x} with {1/0} the code will not crash with a division by zero. If Felix choses eager evaluation the code will crash.

This is the gist of the Felix evaluation strategy. The compiler chooses. Don't write code where the distinction matters!

+ 1.3 Why Felix is Fast

Most compilers use the as if rule coupled with well defined behaviour to do optimisation. This is why they're so slow. Haskell is slow. Even C is slow. By comparison, Felix is fast, because the compiler is not required to prove an optimisation will not change the strictly defined semantics. Instead, the language specifies that the semantics are sloppy to allow the compiler to choose the fastest possible implementation.

Sloppy semantics usually works just fine. Total functions can always be evaluated either eagerly or lazily. Dereference of Felix pointers, for example, can be done eagerly because they cannot be null. C pointers (which Felix also models) might be null and require either a null check before dereference, or a proof that the check is not required. In C, the compiler uses sloppy semantics: it evaluates the dereference anyhow.

See! I didn't invent it, C does it already. Why does C do that when it is unsafe? For performance, of course!

+ 1.4 Controlling evaluation strategy

So, now you understand how Felix semantics operate by default, what happens if you need to choose a particular evaluation strategy?

Felix provides ways to control the evaluation strategies it choses so you can enforce the required semantics when it really matters. Neglecting to do this can lead to subtle bugs, just as it can in C.

+ 1.5 Controlling inlining

Here are some adjectives you can apply to functions or procedures:

  inline fun f(x:int)=>x + 1;
  noinline fun g(x:int)=>x + 1;

The {inline} adjective advises Felix to inline a fuction or procedure. Felix inlines functions are procedures aggressively in most cases. Certain limits apply to the size of functions created by inlining, which can be adjusted by the command line switch {--inline=99} where {99} is a an approximate size limit based on statement count. The {inline} keyword tells the Felix compiler to ignore the limit and try to inline the function or procedure anyhow.

Felix cannot fully inline recursive calls as this would lead to an infinite expansion.

The {noinline} adjective tells Felix not to inline a function or procedure. This can be used to prevent code bloat.

It is important to note that both {inline} and {noinline} are more than just performance hints. They sometimes have real semantics, due to the aggressive way Felix inlines things.

Non-inlining forces Felix to produce a real stack frame object for a function or procedure. A call to such a function or procedure will then create a distinct object for every call. This is essential if, in turn, a function or procedure closure is created inside the target function or procedure which relies on the value of a variable at the time the target function is called. Such closures include the bodies of spawned fthreads or pthreads. The variables involved may include {val}ues since contrary to appearances, values can be modified by re-initialisation inside a loop.

Similarly, {inline} has real semantics. Some operations such as calling the Felix supervisor or exchanging control using schannels can only be performed in a top level procedure. However these operations are permitted in a nested generator function provided it is inlined into a top level procedure directly or indirectly. Non-recursive functions marked inline are always inlined.

+ 1.6 Controlling parameter passing

Felix provides several ways to pass parameters. The following both specify sloppy semantics and are equivalent:

  fun f(x:int)=> 1;
  fun f(val x:int) =>1;

Because of this, the compiler might crash elaborating the following code:

  println$ f (1/0);

if it actually calls f eagerly and evaluates the argument {x} first. To work around this you must enforce lazy evaluation:

  fun f( x: unit -> int ) =>  1;
  println$ f ( fun ()=> 1/0 );
  println$ f { return 1/0; }; // short form of above
  println$ f { 1/0 }; // even shorter form of above

Here, we pass a function to f which is evaluated when needed. Since it isn't needed, it will never be evaluated.

There is another option for parameter passing:

  fun f(var x:int) = { 
    x = 42;
    return x;
  }

Normally {val} parameters are just like {val} variables: they cannot be addressed, and therefore can't be modified. If you want to modify a parameter, you can make is a {var} instead.

The effect of this isn't merely convenience: {var} parameter, just like any {var} variable, forced evaluation of its initialiser and puts that value in a storage location. In other words, {var} variables force eager evaluation.

In subsequent computations, this stored value will be used where the variable name is written. In our division by zero example:

  fun f(val x:int) =>1;
  println$ f (1/0); 

forces a crash.