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.
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
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
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()
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.
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.
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
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
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] )
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
Since all your arrays seem to be of a fixed size, is there any reason a struct type won't do the job?
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
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).
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
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
Topic tags
- f# × 3705
- websharper × 1897
- compiler × 286
- functional × 201
- ui next × 139
- c# × 121
- classes × 97
- web × 97
- .net × 84
- book × 84
- async × 76
- ui.next × 67
- bug × 54
- core × 49
- website × 49
- server × 45
- parallel × 43
- ui × 43
- enhancement × 41
- parsing × 41
- testing × 41
- trywebsharper × 41
- typescript × 37
- html × 35
- javascript × 35
- owin × 35
- asynchronous × 30
- monad × 28
- ocaml × 28
- tutorial × 27
- warp × 27
- haskell × 26
- sitelet × 25
- linq × 22
- workflows × 22
- wpf × 20
- fpish × 19
- introduction × 19
- silverlight × 19
- sitelets × 19
- monodevelop × 17
- rpc × 17
- suave × 17
- piglets × 16
- collections × 15
- feature request × 15
- jquery × 15
- templates × 15
- getting started × 14
- pipeline × 14
- kendoui × 13
- reactive × 12
- 4.1.0.171 × 11
- monads × 11
- opinion × 10
- 4.0.190.100-rc × 9
- deployment × 9
- fixed × 9
- formlets × 9
- in × 9
- json × 9
- plugin × 9
- proposal × 9
- scheme × 9
- solid × 9
- basics × 8
- concurrent × 8
- highcharts × 8
- how-to × 8
- python × 8
- 4.1.1.175 × 7
- complexity × 7
- documentation × 7
- visual studio × 7
- 4.1.2.178 × 6
- lisp × 6
- real-world × 6
- released in 4.0.192.103-rc × 6
- remoting × 6
- resources × 6
- scala × 6
- websharper ui.next × 6
- workshop × 6
- xaml × 6
- 4.0.193.110 × 5
- 4.2.3.236 × 5
- aspnetmvc × 5
- authentication × 5
- azure × 5
- bootstrap × 5
- conference × 5
- dsl × 5
- formlet × 5
- java × 5
- list × 5
- metaprogramming × 5
- ml × 5
- released in Zafir.4.0.188.91-beta10 × 5
- sql × 5
- visualstudio × 5
- websharper.forms × 5
- zafir × 5
- 4.0.192.106 × 4
- 4.0.195.127 × 4
- 4.1.0.38 × 4
- 4.2.1.86 × 4
- 4.2.6.118 × 4
- css × 4
- example × 4
- extensions × 4
- fsi × 4
- fsx × 4
- html5 × 4
- jqueryui × 4
- lift × 4
- reflection × 4
- remote × 4
- rest × 4
- spa × 4
- teaching × 4
- template × 4
- websocket × 4
- wontfix × 4
- 4.0.196.147 × 3
- 4.1.0.34 × 3
- 4.1.6.207 × 3
- 4.2.1.223-beta × 3
- 4.2.11.258 × 3
- 4.2.4.114 × 3
- 4.2.4.247 × 3
- 4.2.5.115 × 3
- 4.2.6.253 × 3
- 4.2.9.256 × 3
- ajax × 3
- alt.net × 3
- aml × 3
- asp.net mvc × 3
- canvas × 3
- cloudsharper × 3
- compilation × 3
- database × 3
- erlang × 3
- events × 3
- extension × 3
- file upload × 3
- forums × 3
- inline × 3
- issue × 3
- kendo × 3
- macro × 3
- mono × 3
- msbuild × 3
- mvc × 3
- pattern × 3
- piglet × 3
- released in Zafir.4.0.187.90-beta10 × 3
- svg × 3
- type provider × 3
- view × 3
- 4.1.1.64 × 2
- 4.1.5.203 × 2
- 4.1.7.232 × 2
- 4.2.10.257 × 2
- 4.2.3.111 × 2
- 4.2.5.249 × 2
- android × 2
- asp.net × 2
- beginner × 2
- blog × 2
- chart × 2
- client × 2
- client server app × 2
- clojure × 2
- computation expressions × 2
- constructor × 2
- corporate × 2
- courses × 2
- cufp × 2
- d3 × 2
- debugging × 2
- direct × 2
- discriminated union × 2
- docs × 2
- elm × 2
- endpoint × 2
- endpoints × 2
- enterprise × 2
- entity framework × 2
- event × 2
- f# interactive × 2
- fable × 2
- flowlet × 2
- formdata × 2
- forms × 2
- fsc × 2
- google maps × 2
- hosting × 2
- http × 2
- https × 2
- iis 8.0 × 2
- install × 2
- interactive × 2
- interface × 2
- iphone × 2
- iteratee × 2
- jobs × 2
- jquery mobile × 2
- keynote × 2
- lens × 2
- lenses × 2
- linux × 2
- listmodel × 2
- mac × 2
- numeric × 2
- oauth × 2
- obfuscation × 2
- offline × 2
- oop × 2
- osx × 2
- packaging × 2
- pattern matching × 2
- performance × 2
- pipelines × 2
- q&a × 2
- quotation × 2
- reference × 2
- released in Zafir.4.0.185.88-beta10 × 2
- rx × 2
- script × 2
- security × 2
- self host × 2
- seq × 2
- sockets × 2
- stm × 2
- tcp × 2
- trie × 2
- tutorials × 2
- type × 2
- url × 2
- var × 2
- websharper.charting × 2
- websharper4 × 2
- websockets × 2
- wig × 2
- xna × 2
- zh × 2
- .net interop × 1
- 2012 × 1
- 4.0.194.126 × 1
- 4.1.3.184 × 1
- 4.1.4.189 × 1
- 4.2.0.214-beta × 1
- 4.2.12.259 × 1
- 4.2.2.231-beta × 1
- 4.2.8.255 × 1
- Canvas Sample Example × 1
- DynamicStyle Animated Style × 1
- Fixed in 4.0.190.100-rc × 1
- Released in Zafir.UI.Next.4.0.169.79-beta10 × 1
- SvgDynamicAttribute × 1
- WebComponent × 1
- abstract class × 1
- accumulator × 1
- active pattern × 1
- actor × 1
- addin × 1
- agents × 1
- aggregation × 1
- agile × 1
- alter session × 1
- animation × 1
- anonymous object × 1
- apache × 1
- api × 1
- appcelerator × 1
- architecture × 1
- array × 1
- arrays × 1
- asp.net 4.5 × 1
- asp.net core × 1
- asp.net integration × 1
- asp.net mvc 4 × 1
- asp.net web api × 1
- aspnet × 1
- ast × 1
- attributes × 1
- authorization × 1
- b-tree × 1
- back button × 1
- badimageformatexception × 1
- bash script × 1
- batching × 1
- binding-vars × 1
- bistro × 1
- body × 1
- bundle × 1
- camtasia studio × 1
- cas protocol × 1
- charts × 1
- clarity × 1
- class × 1
- cli × 1
- clipboard × 1
- clojurescript × 1
- closures × 1
- cloud × 1
- cms × 1
- coding diacritics × 1
- color highlighting × 1
- color zones × 1
- combinator × 1
- combinators × 1
- compile × 1
- compile code on server × 1
- config × 1
- confirm × 1
- content × 1
- context × 1
- context.usersession × 1
- continuation-passing style × 1
- coords × 1
- cordova × 1
- cors × 1
- coursera × 1
- cross-domain × 1
- csla × 1
- current_schema × 1
- custom content × 1
- data × 1
- data grid × 1
- datetime × 1
- debug × 1
- declarative × 1
- delete × 1
- devexpress × 1
- dhtmlx × 1
- dictionary × 1
- directattribute × 1
- disqus × 1
- distance × 1
- do binding × 1
- doc elt ui.next upgrade × 1
- docker × 1
- dojo × 1
- dol × 1
- dom × 1
- domain × 1
- du × 1
- duf-101 × 1
- dynamic × 1
- eastern language × 1
- eclipse × 1
- edsl × 1
- em algorithm × 1
- emacs × 1
- emotion × 1
- enums × 1
- error × 1
- etw × 1
- euclidean × 1
- eventhandlerlist × 1
- examples × 1
- ext js × 1
- extension methods × 1
- extra × 1
- facet pattern × 1
- failed to translate × 1
- fake × 1
- fantomas × 1
- fear × 1
- float × 1
- form × 1
- form-data × 1
- forum × 1
- fp × 1
- frank × 1
- fsdoc × 1
- fsharp × 1
- fsharp.core × 1
- fsharp.powerpack × 1
- fsharpx × 1
- fsunit × 1
- function × 1
- functional style × 1
- game × 1
- games × 1
- gc × 1
- generic × 1
- geometry × 1
- getlastwin32error × 1
- getting-started × 1
- google × 1
- google.maps × 1
- grid × 1
- group × 1
- guide × 1
- hash × 1
- headers × 1
- hello world example × 1
- heroku × 1
- highchart × 1
- history × 1
- how to × 1
- html-templating × 1
- http405 × 1
- httpcontext × 1
- hubfs × 1
- i18n × 1
- ie 8 × 1
- if-doc × 1
- iis × 1
- image × 1
- images × 1
- inheritance × 1
- initialize × 1
- input × 1
- install "visual studio" × 1
- installer × 1
- int64 × 1
- interfaces × 1
- internet explorer × 1
- interop × 1
- interpreter × 1
- io × 1
- iobservable × 1
- ios × 1
- iot × 1
- ipad × 1
- isomorphic × 1
- javascript optimization × 1
- javascript semanticui resources × 1
- jquery-plugin × 1
- jquery-ui × 1
- jquery-ui-datepicker × 1
- js × 1
- kendo datasource × 1
- kendochart × 1
- kendoui compiler × 1
- knockout × 1
- l10n × 1
- learning × 1
- library × 1
- libs × 1
- license × 1
- licensing × 1
- lineserieszonescfg × 1
- local setting × 1
- localization × 1
- logging × 1
- loop × 1
- macros × 1
- mailboxprocessor × 1
- mapping × 1
- maps × 1
- markerclusterer × 1
- markup × 1
- marshal × 1
- math × 1
- mathjax × 1
- message × 1
- message passing × 1
- message-passing × 1
- meta × 1
- metro style × 1
- micro orm × 1
- minimum-requirements × 1
- mix × 1
- mobile installation × 1
- mod_mono × 1
- modal × 1
- module × 1
- mouseevent × 1
- mouseposition × 1
- multidimensional × 1
- multiline × 1
- multithreading × 1
- mysql × 1
- mysqlclient × 1
- nancy × 1
- native × 1
- nested × 1
- nested loops × 1
- node × 1
- nunit × 1
- object relation mapper × 1
- object-oriented × 1
- om × 1
- onboarding × 1
- onclick × 1
- optimization × 1
- option × 1
- orm × 1
- os x × 1
- output-path × 1
- override × 1
- paper × 1
- parameter × 1
- persistence × 1
- persistent data structure × 1
- phonegap × 1
- pola × 1
- post × 1
- powerpack × 1
- prefix tree × 1
- principle of least authority × 1
- privacy × 1
- private × 1
- profile × 1
- programming × 1
- project × 1
- project euler × 1
- projekt_feladat × 1
- protected × 1
- provider × 1
- proxy × 1
- ptvs × 1
- public × 1
- pure f# × 1
- purescript × 1
- qna × 1
- quant × 1
- query sitelet × 1
- question × 1
- quotations × 1
- range × 1
- raphael × 1
- razor × 1
- rc × 1
- reactjs × 1
- real-time × 1
- ref × 1
- region × 1
- released in 4.0.190.100-rc × 1
- reporting × 1
- responsive design × 1
- rest api × 1
- rest sitelet × 1
- restful × 1
- round table × 1
- router × 1
- routing × 1
- rpc reverseproxy × 1
- runtime × 1
- sales × 1
- sample × 1
- sampleapp × 1
- scriptcs × 1
- scripting × 1
- search × 1
- self hosted × 1
- semanticui × 1
- sequence × 1
- serialisation × 1
- service × 1
- session-state × 1
- sharepoint × 1
- signals × 1
- sitelet website × 1
- sitelet.protect × 1
- sitlets × 1
- slickgrid × 1
- source code × 1
- sqlentityconnection × 1
- ssl × 1
- standards × 1
- static content × 1
- stickynotes × 1
- streamreader × 1
- stress × 1
- strong name × 1
- structures × 1
- submitbutton × 1
- subscribe × 1
- svg example html5 websharper.ui.next × 1
- sweetalert × 1
- system.datetime × 1
- system.reflection.targetinvocationexception × 1
- table storage × 1
- targets × 1
- tdd × 1
- templates ui.next × 1
- templating × 1
- text parsing × 1
- three.js × 1
- time travel × 1
- tls × 1
- tooltip × 1
- tracing × 1
- tsunamiide × 1
- turkish × 1
- twitter-bootstrap × 1
- type erasure × 1
- type inference × 1
- type providers × 1
- type-providers × 1
- typeprovider × 1
- ui next forms × 1
- ui-next × 1
- ui.next jqueryui × 1
- ui.next charting × 1
- ui.next formlets × 1
- ui.next forms × 1
- ui.next suave visualstudio × 1
- ui.next templating × 1
- unicode × 1
- unittest client × 1
- upload × 1
- usersession × 1
- validation × 1
- vb × 1
- vb.net × 1
- vector × 1
- view.map × 1
- visal studio × 1
- visual f# × 1
- visual studio 11 × 1
- visual studio 2012 × 1
- visual studio shell × 1
- vs2017 compiler zafir × 1
- vsix × 1
- web api × 1
- web-scraping × 1
- webapi × 1
- webcomponents × 1
- webforms × 1
- webgl × 1
- webrtc × 1
- webshaper × 1
- websharper async × 1
- websharper codemirror × 1
- websharper f# google × 1
- websharper forms × 1
- websharper reactive × 1
- websharper rpc × 1
- websharper sitelets routing × 1
- websharper warp × 1
- websharper-interface-generator × 1
- websharper.chartsjs × 1
- websharper.com × 1
- websharper.exe × 1
- websharper.owin × 1
- websharper.ui.next × 1
- websharper.ui.next jquery × 1
- websockets iis × 1
- why-websharper × 1
- windows 7 × 1
- windows 8 × 1
- windows-phone × 1
- winrt × 1
- www.grabbitmedia.com × 1
- xamarin × 1
- xml × 1
- yeoman × 1
- yield × 1
- zafir beta × 1
- zafir websharper4 × 1
- zarovizsga × 1
![]() |
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 |
I have a puzzle solver app (which is the basis for most of my past questions too!) in which I'm traversing a "game tree" in a recursive walk. The game state is represented by a 16 byte array and a fresh copy is made for each recursive call. These state arrays are of course "discarded" upon exit from the associated recursive call. The calls, in general, are NOT tail recursive.
A consequence of the heap allocation of arrays is that this tree traversal generates LOTS of garbage which must eventually be collected. In fact however, the lifetimes of these state objects are determined exactly by the call structure; thus stack allocation would make for a drastic reduction in GCs. (GCs constitute a significant drain on performance for this app.)
In C# I would have available the "stackalloc" capability, which has the downside of being "unsafe". Is there any such capability in F#? Given the functional style I think this sort of problem will arise frequently since it is so common to synthesize new copies rather than mutating existing ones.
Thanks in advance,
Bill