Back to Questions
2.2k
views9
comments
F# for planning
f#functional

I am undertaking a project to implement a planning algorithm. For this purpose I have considered using a functional programming language. The planning algorithm will be used for real-time planning/replanning, eg. in games, and needs to be integrated with a C# library. As such, F# seems like an attractive choice. My primary concern is whether F# offers the performance required for this task. I have no experience with F#, and limited with .NET. Any input would be greatly appreciated.

.

To ground your question a little better, do you already have your planning algorithm, and is it implemented in something where it has acceptable performance?

As a general observation, F# may be a great way to prototype your algorithm and also elements of your game system. Access to the .NET libraries, including DirectX and the .NET 3.0 WinFX capabilities should give you a further boost, along with the VS 2005 integration. And, for isolatable performance-critical elements, there are ways to bridge to lower-level custom implementations (in C or C++, and even assembler) without losing your overall flexibility.

If your game will be commercial, one risk to consider will be the absence of commercial support for F#, since it is presently a closed-source research language. I would prototype with it anyhow for the purchase it will give you on rapid confirmation and access to .NET. You should learn quickly enough whether there are barriers that require you to pursue an alternative.

By on 10/6/2006 9:33 AM ()

Let me elaborate a bit on the project at hand, as I will be working on the project with initial the poster.

The project is entirely academic, and we currently have no implementation of the planner. Potential uses for the planner are planning in an FPS (UT2004 with the GameBots extension), and possibly Lego Mindstorm Robots (both of which have libraries written/being written in C#).

Reading the response (thanks all!), it seems like F# is a great candidate with regards to performance. Unless any serious issues arise, I think F# will be our initial language of choice.

By on 10/6/2006 10:09 AM ()

On performance, yes, absolutely go with F# !!

F# and C# both compile to IL code, so you can often get F# and C# code to run at comparable speeds.

Here are a couple of perf. tips:

a) Avoid using exceptions for control flow (.NET exceptions are costly).

b) If you use local state, note that local mutables will be represented as method locals, so are preferable to local reference cells.

c) Use .NET 2.0 which has generics (for fast polymorphic code).

You mention games, what is your target platform? PC? CompactFramework? XBox?

By on 10/6/2006 4:59 AM ()

@jamarg: Why would you say F# for speed? Any proof of that or why it's faster then C#?

I'm simply curious

By on 10/6/2006 1:50 PM ()

I think jamarg said "comparable." My sense from the analysis that was posted somewhere is that there is a modest F# penalty (around 10-15%) and that may change as the compiler is improved and as people learn the best idioms for clean F#. Choice of good algorithmic approaches can provide far more benefit than changing to a more verbose language for development and maintenance.

The fact that F# allows one to work easily at higher functional+object levels of abstraction is the important advantage, I'd say, especially during early development. That it is always compiled is the second benefit, along with the nice handling of types.

Finally, the more that an F# applications relies on the Common Language Infrastructure and uses well-crafted components from other sources, the less important the F# overhead will be.

Where that economy of F# usage appeals to me is that I can avoid premature optimization and then, after I know where the pain is, only optimize where it is necessary and does the most good.

By on 10/6/2006 3:04 PM ()

There is no intrinsic performance penalty for F# code vis a vis C# code - if we entered F# in a language shootout (anyone care to do that?) I reckon we'd be on par, without contorting the F# code. Certain constructs in both C# and F# are cheap, e.g. generic data structures using floating point numbers are unboxed. The use of certain constructs imposes micro costs, e.g. an indirect call to a function value is cheap, but not as cheap as a direct call. The same story can be repeated for constructs in both languages. F# uses peep-hole and inlining optimizations to eliminate these costs when the information is there to do so.

That's performance of code and memory use. Macro-performance is another game, where what Dennis (orcmid) says is spot on: this involves techniques such as:

  • good choices of data structures (yes, arrays are better than F# lists in some cases [:)])
  • good choices of algorithms
  • avoiding premature optimization
  • rapid prototyping with F# Interactive
  • dynamic investigation of object graphs using F# Interactive (e.g. see the TermWalker sample - I've been using a modified version of this recently to analyze the memory usage of the F# compiler)
  • the use of tools such as CPU and memory profilers
  • the use of native code in exceptional circumstances (e.g. the Intel MKL or the AMD ACML)
  • the use of multiple CPUs and clusters
  • the correct use of well-engineered efficient I/O, database, networking and graphics libraries

In some cases the aim is simply to make sure your computation is bounded by some other computing resource than CPU, e.g. the systems group at MSR Cambridge have been happy to code in F# rather than Python since "now we're disk bound". In general, .NET languages excel at creating high-performance applications that involve a number of computing resources, but the added value of the succinct language and F# Interactive make F# particularly strong in this regard.

One exception on the code/memory front is that F# code does not support the authoring of structs. This is a useful tool for improving memory use, though can easily be abused. This is something we plan to address.

Finally, I would expect a fully productized version of F# (should it ever happen [:)]) to include a whole assembly optimizing compiler (ala MLton and SML.NET, but whole-assembly, not whole-program). This is well known to give useful additional performance gains for some programs in this class of languages. But that's just plans.[;)]

Don

By on 10/6/2006 3:52 PM ()

Is this still in the plans? ;)

Finally, I would expect a fully productized version of F# (should it ever happen [:)])  to include a whole assembly optimizing compiler (ala MLton and SML.NET, but whole-assembly, not whole-program). This is well known to give useful additional performance gains for some programs in this class of languages.  But that's just plans.[;)]

Don

By on 2/5/2010 9:55 PM ()

Mark asked @jamarg:

> Why would you say F# for speed?
> Any proof of that or why it's faster then C#?
> I'm simply curious.

In 2005, using some shootout benchmarks, I did performance comparisons including F#, C# and C++. The timings were done on .NET 2.0 (which was still in beta back then).
I found that F# and C# had comparable speeds, which is to be expected, since both compile to IL code and should produce good enough IL code for the JIT. Since those tests there have been various improvements to the IL code generated from F#, e.g. reduced locals, enabling loop bound optimisations etc..
The basic timings are included below.
The micro benchmarks were focused on numerical calculations. I've found that .NET does very well on such calculations. Combine that performance with the clarity you can get writing such code in an ML-like language then you begin to see why people get so excited when they "discover" it!
James.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---
C:\perftalk>utime nbody-cpp-win32-p4.exe   5000000
real: 0:00:03.249
user: 0:00:03.234
sys: 0:00:00.000
 
C:\perftalk>utime nbody-cs-win32-p4.exe  5000000
real: 0:00:03.140
user: 0:00:03.031
sys: 0:00:00.000
 
C:\perftalk>utime nbody-fsc20b2-win32-p4.exe   5000000
real: 0:00:03.859
user: 0:00:03.765
sys: 0:00:00.078
---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---
C:\perftalk>utime harmonic-cpp-win32-p4.exe 200000000
real: 0:00:03.312
user: 0:00:03.312
sys: 0:00:00.015
 
C:\perftalk>utime harmonic-cs-win32-p4.exe 200000000
real: 0:00:03.390
user: 0:00:03.312
sys: 0:00:00.031
 
C:\perftalk>utime harmonic-fsc20b2-win32-p4.exe  200000000
real: 0:00:03.406
user: 0:00:03.375
sys: 0:00:00.031
---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---
c:\perftalk>utime spectral-cpp-win32-p4.exe 2000
real: 0:00:03.843
user: 0:00:03.812
sys: 0:00:00.000
 
c:\perftalk>utime spectral-cs-win32-p4.exe 2000
real: 0:00:02.734
user: 0:00:02.656
sys: 0:00:00.031
 
c:\perftalk>utime spectral-fsc20b2-win32-p4.exe 2000
real: 0:00:02.765
user: 0:00:02.703
sys: 0:00:00.046
---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---x---
By on 10/12/2006 4:43 AM ()

PS. Remember threads...

.NET is multi-threaded, making use of hardware when available, e.g. dual-processor, or dual-core, or hyper-threading. If your planning can be split into disjoint search tasks, then you could make significant gains if your hardware supports it.

[based on recent tests computing fractals].

By on 10/6/2006 5:14 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper