The issue with stackalloc is that it's not verifiable by the runtime and hence will always be "unsafe" a problem it shares with the (nice but maybe not as generally applicable) jmp instruction.

Also the problem is that if you got a potentially unbounded recursive walk or are creating sufficently large objects on the stack you'll quite quickly eat up the 1-4MB's standard stack frame on Windows making your app crash due to stack exhaustion.

By on 2/6/2009 2:29 AM ()

The issue with stackalloc is that it's not verifiable by the runtime and hence will always be "unsafe" a problem it shares with the (nice but maybe not as generally applicable) jmp instruction. Also the problem is that if you got a potentially unbounded recursive walk or are creating sufficently large objects on the stack you'll quite quickly eat up the 1-4MB's standard stack frame on Windows making your app crash due to stack exhaustion.

I agree that the unsafeness of stackalloc makes its use undesirable. One would hope for a more elegant way to address the problem in F#, one that doesn't suffer the "unsafe" attribute.

As for the unbounded recursion, this is of course a problem whether or not you are stack allocating such objects. In this application (and in most tree search/optimization type problems) the interesting metric is tree depth when considering the problem of exhausting the stack. Obviously for those algorithms where this value is quite large one would be ill advised to stack allocate. OTOH, where depth is limited to a "reasonable" value (say < 100) you're unlikely to have problems. With heap allocation the interesting metric is total number of nodes visited -- which will generally be a *much* larger number. So, you end up stressing the heap (and thus the GC) instead.

In any case, the pooling approach suggested by Brian will (I think) address the problem -- even though it's not an ideal solution.

Regards,

Bill

By on 2/6/2009 6:43 AM ()

F# supports pointer arithmetic and dereferencing through the Nativeptr module. The manual also seems to suggest that you can take pointers via the && operator. So you could define a struct type with the correct size and then when you need a stack allocated array, you could instantiate this type, take a pointer and convert the pointer a byte pointer. I haven't tried this though.

Stephan

By on 2/6/2009 7:05 AM ()

I was curious whether my suggestion from above actually worked. Turns out it does, as the following sample demonstrates. (Although I'm not sure whether the language designers will continue to allow this use of the &&-operator in future versions of the F# compiler.)

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
open Microsoft.FSharp.NativeInterop

[<Struct>]
type SixteenByteStruct =
    val i64_0: int64
    val i64_1: int64    

#nowarn "9"

let test() =
    // allocate array
    let mutable a = SixteenByteStruct()    
    // get uint8 pointer to beginning of struct
    let p : nativeptr<uint8> = 
        NativePtr.of_nativeint (NativePtr.to_nativeint (&&a)) 
    // convenient (unchecked) accessor functions    
    let inline get i   = NativePtr.get p i
    let inline set i v = NativePtr.set p i v
    // iterate over array
    for i = 0 to 15 do
        set i (byte i)
    for i = 0 to 15 do
        printfn "%i" (get i)

test()
By on 2/6/2009 11:23 AM ()

Since your array is of a fixed size, you can allocate it on the stack using a struct. You can provide a 2-dimensional accessor to the values in the struct (as you require) and you don't need unsafe code to do this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[<Struct>]
[<StructLayout(LayoutKind.Sequential, Pack=1)>]
type GameState =
  val a00 : byte
  val a01 : byte
  val a10 : byte
  ...
  
  member x.Get (i, j) =
    match i, j with 
    | 0, 0 -> x.a00
    | 0, 1 -> x.a01
    | 1, 0 -> x.a10
    | ...
    | _ -> raise (IndexOutOfRangeException ())

When performance is important you can use F#. Both F# and C# compile to the same intermediate language, so neither language is necessarily more performant than the other.

By on 2/7/2009 2:42 PM ()

Gneverov, your solution will probably be considerably slower than a stack allocated array. If Bill only worked with indices known at compile time and if you forced the F# compiler to inline Get then both versions might compile down to comparable code. However, Bill seems to need computed indices and the JIT is not capable of reducing the nested switch statement into a memory fetch with offset.

By on 2/8/2009 2:31 AM ()

PS: If you have an upper limit for the number of arrays, you could also allocate one big array on the heap and then use NativePtr.of_array to get a pointer (if you don't want to pay for the bounds checking associated with normal array access).

Stephan

By on 2/6/2009 7:22 AM ()

PS: If you have an upper limit for the number of arrays, you could also allocate one big array on the heap and then use NativePtr.of_array to get a pointer (if you don't want to pay for the bounds checking associated with normal array access).
...

Stephan

Yes, this could work; however I don't see it as any less "trouble" than doing a pooling of "real" arrays and the latter is certainly more within the spirit of the language. Thanks for the suggestion in any case.

Regards,

Bill

By on 2/6/2009 7:47 AM ()

well I think the problem might be, that this is exactly those problems where you indroduce side-effects to improve performance.

And I think you should do this in an imperative language like C# - IMHO F# should never give you access to horrors like "stackalloc" or pointers - it just don't fit into the functional world (it's worse enough that you can do OO [:D] )

By on 2/6/2009 1:24 AM ()

well I think the problem might be, that this is exactly those problems where you indroduce side-effects to improve performance.

And I think you should do this in an imperative language like C# - IMHO F# should never give you access to horrors like "stackalloc" or pointers - it just don't fit into the functional world (it's worse enough that you can do OO [:D] )

So, it appears that you are saying that when performance is important don't do F#? That's a disappointing state of affairs.

BTW, the purpose of implementing this puzzle algorithm is to benchmark F# against C# as well as a (little known) parallel language. If the solution to solving performance problems in F# is "don't use F#" then I think the language will not see "widespread" adoption.

Regards,

Bill

By on 2/6/2009 6:32 AM ()

Since all your arrays seem to be of a fixed size, is there any reason a struct type won't do the job?

By on 2/5/2009 9:58 PM ()

Since all your arrays seem to be of a fixed size, is there any reason a struct type won't do the job?

The array represents an n x n board (n=4 in this case). I don't know how to reasonably iterate over elements of a struct, particularly where adjacencies in 2 dimensions are significant.

Bill

By on 2/6/2009 6:28 AM ()

I don't know of any way to do this in F# (though I an not certain there's not a way).

You can probably devise your own simple pooling of arrays to mitigate the garbage. When you are 'done' with an array, give it to the 'pool' to be reused; when you need a fresh array, see if the pool has any and if so grab one of those rather than allocating a new one. Depending on exactly what your code is doing, this may not be very invasive (a small bit of refactoring to redirect arrays through the pool may be a big easy win). Anyway, an idea to try.

See also

[link:lorgonblog.spaces.live.com]

for some possible inspiration (and subsequent entries that deal with errata).

By on 2/5/2009 3:01 PM ()

I don't know of any way to do this in F# (though I an not certain there's not a way).

...

Brian

After thinking about this a bit (and after digesting all of the suggested solution approaches posted here) it appears that the Right Solution would be to provide strong typing support for "stack allocated" arrays (and other types as well).

After all, the use of structs is not "unsafe" and they are stack allocated. Of course this follows from copy semantics; i.e., they are "value" types. I assume that a stack allocated array (via stackalloc or something similar) is unsafe only because of the possibility of a pointer escaping to storage that goes away with the stack frame. With value semantics there is no such possibility because there are no pointers.

I'm not necessarily suggesting that F# should provide such support, but from a general language design point of view I think it's an interesting idea. A language can simply provide a way to specify value vs. reference semantics; thus handling the problem at a much higher level of abstraction. That value types are stack allocated then becomes "an optimization" and something not visible to the disinterested observer.

Bill

By on 2/6/2009 7:56 AM ()

I don't know of any way to do this in F# (though I an not certain there's not a way).

You can probably devise your own simple pooling of arrays to mitigate the garbage. ...

Brian

Thanks for the suggestion. The pooling approach is in fact what I had planned; however that's simply a workaround for something that (ideally) should be easy to do directly in the language. On the one hand developers shouldn't be specifying *where* objects are stored; on the other hand implementing pooling is motivated by precisely the need for such specification.

Regards,

Bill

By on 2/6/2009 6:25 AM ()
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