Back to Questions
1.6k
views9
comments
A question about the implementation of discriminated unions
f#

Hello,

I hope I've got the right forum for this kind of question. It's a repeat of something I asked on comp.lang.functional, but it seems noone knows the answer. I've been playing about with translating my AVL code to F# and so have a data type looking like this..

1
2
3
4
5
6

/// An AVL tree based map from keys to values
type AVLmap<'k,'v> =
   E                                            // Empty
 | N of AVLmap<'k,'v> * 'k * 'v * AVLmap<'k,'v> // BF=-1
 | Z of AVLmap<'k,'v> * 'k * 'v * AVLmap<'k,'v> // BF= 0
 | P of AVLmap<'k,'v> * 'k * 'v * AVLmap<'k,'v> // BF=+1I.E. Balance factor is encoded in the tag.

What I've been wondering is if there any kind of indirection overhead between the tag part and the tuple part of each tree node? In other words, if we assume the keys are unboxed, will visiting a leaf of a tree of height h involve traversing just h heap records or 2*h heap records (or maybe something else)?

The syntax for the type declaration and pattern matching seem (to me) to suggest that the tag part and tuple part are actually separate records on the heap, but I know I may be quite wrong about this as I don't really understand anything about the underlying implementation.

Thanks

.

I beleive each case is a sub-class - there are no extra objects involved - so you're getting 1:1 AVLmap to objects. (Hope that answers your question.)

By on 6/15/2010 7:26 AM ()

I beleive each case is a sub-class - there are no extra objects involved - so you're getting 1:1 AVLmap to objects. (Hope that answers your question.)

Ah yes, objects not heap records! Thanks. That does help if what you say is correct. Excuse me for asking, but how confident are you about that? It's just that if the approach I'm using potentially means taking a *2 performance hit (at least if we assume fetching this stuff from main memory is where the time goes), then I'd rather stop now and try something else (not sure what :-)

I see Chris Smiths book "Programming F#" has an example of translating this kind of thing to C# on page 358. I don't really understand it fully but AFAICT it is consistent with what you say. 4 lines of F# becomes 3 pages of C#!! Also I find I can pattern match against an entire tuple part using a single _, but F# won't actually let me extract the tuple part in isolation that way, which does tend to suggest that both tag and tuple are part of the same object (heap record).

By on 6/15/2010 9:32 AM ()

>Ah yes, objects not heap records

Not sure what you're saying here - but objects (reference types / instances of classes) are certainly generally stored on the heap. (Records and other value types are on the stack, unless of course they're inside another objects that are stored on the heap.)

>I'm using potentially means taking a *2 performance hit

Sounds like pre-mature optimization... If you're really worried about the hit this representation may or may not give you (you're predicting the weather or something) then you have many other things to consider bofore worrying about how this DU gets stored - once the ccode is working, and if it's not fast enuf, then you can profile and try some other solutions.

FWIW, I just googled "F# AVL tree" and found this cool silverlight demo: [link:www.avltutorial.info]#

By on 6/15/2010 11:37 AM ()

>Ah yes, objects not heap records

Not sure what you're saying here - but objects (reference types / instances of classes) are certainly generally stored on the heap. (Records and other value types are on the stack, unless of course they're inside another objects that are stored on the heap.)

I'm not saying much really, just trying to get up to speed on correct F#/.NET terminology. BTW, I thought "records" were reference types and that the correct term for records that are value types is "struct". But what do I know :-)

>I'm using potentially means taking a *2 performance hit

Sounds like pre-mature optimization... If you're really worried about the hit this representation may or may not give you (you're predicting the weather or something) then you have many other things to consider bofore worrying about how this DU gets stored - once the ccode is working, and if it's not fast enuf, then you can profile and try some other solutions.

Mistaken optimization perhaps, but not premature :-) For me any changes to the data structure will mean a substantial re-write of a large and subtly complex library. So I'd rather not do that if I can avoid it.

FWIW, I just googled "F# AVL tree" and found this cool silverlight demo: [link:www.avltutorial.info]#

Cool! that's the best AVL demo I've seen. You can see why AVL trees perform so well with "accidentally" sorted data sets. If you try sorted insertions you always seem to get a perfectly balanced tree for (2^N)-1 elements. (I'm not aware of any proof of this assertion, it just seems to be an "empirical fact".)

By on 6/15/2010 1:42 PM ()


FWIW, I just googled "F# AVL tree" and found this cool silverlight demo: [link:www.avltutorial.info]#

Cool! that's the best AVL demo I've seen. You can see why AVL trees perform so well with "accidentally" sorted data sets. If you try sorted insertions you always seem to get a perfectly balanced tree for (2^N)-1 elements. (I'm not aware of any proof of this assertion, it just seems to be an "empirical fact".)
</quote> FWIW I've done some preliminary benchmarking, just growing a tree of 10,000,000 int keys in ascending order. On my machine with Collections.Map this takes 62 seconds but with AVL this takes only 33 seconds. So not too bad, or surprising really (considering the above observation) as AVL trees are already known to perform quite well under this particular stress test. If I simplify things a bit to implement a Set instead of a Map the execution time drops to 21 seconds, but the Haskell (ghc) version only takes 12 seconds. So that's a little disappointing. But I guess ghc compiler and runtime are tuned to work well together for FP whereas F# is probably much more of an exercise in square pegs and round holes [:(].

By on 7/11/2010 5:59 AM ()

Re: "records" -- brain thought structs and typed something else - something relapsed 25 years to Pascal. (That's what I get for listening to the oldies on XM on the way to work...)

By on 6/15/2010 6:04 PM ()


get up to speed on correct F#/.NET terminology. BTW, I thought "records" were reference types and that the correct term for records that are value types is "struct". But what do I know :-)

(you're right)

For me any changes to the data structure will mean a substantial re-write of a large and subtly complex library. So I'd rather not do that if I can avoid it.

If this is a concern, you might consider writing something tiny/easy and benchmarking it, to learn about F# and .NET runtime, before jumping right into AVL trees.

By on 6/15/2010 2:36 PM ()

It sounds like you are being speculative about 'where the time goes' and that you should be measuring.

(If you use [<CompilationRepresentation(UseNullAsTrueValue)>] you can encode 'E' as null rather than an object, by the way.)

[link:research.microsoft.com]

says a little about how unions are compiled, but I think it's left underspecified so the compiler can do various optimization tricks.

You can use a tool like .NET Reflector or the debugger to see how your code is being compiled.

But again, I think you need to measure.

By on 6/15/2010 9:49 AM ()

(If you use [<CompilationRepresentation(UseNullAsTrueValue)>] you can encode 'E' as null rather than an object, by the way.)

Thanks for the tip. I guess that will save a bit at the leaves.

[link:research.microsoft.com]

says a little about how unions are compiled, but I think it's left underspecified so the compiler can do various optimization tricks.

I really should try to read that some time :-)

You can use a tool like .NET Reflector or the debugger to see how your code is being compiled.But again, I think you need to measure.

Yes, but before I can do that I need some working code and choice of basic data structure representation has a big impact on that. Just trying to be sure I'm not chosing something that's doomed to "suck" right from the start. The obvious thing to benchmark against would be the standard Collections.Map module. In Haskell this data structure out performs every other balanced tree Map implementation it's ever been tested against (including Haskell Data.Map). The same may not be true for F#/.NET though.

I don't think my speculation about the (hypothetical) indirection cost is too wild. Every benchmark I've ever run indicates that following a pointer to some "random" place in memory is a relatively expensive thing to do. In this case though the indirection (if there was any) may not be so random at all (if the allocator works the way I think I would expect good spatial locality).

Anyway I think I'll go with what I posted for now, so time will tell...

By on 6/15/2010 1:25 PM ()

    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