Back to Questions
1.7k
views8
comments
Fast Hashing / Equality comparison for Memoization
f#testing

I have some fairly complex data structures (F# Map, in this case) on which I'm performing calculations that I want to memoize and that result in simple data types (say, a float). So far I'm using a closure that contains a Dictionary<Map,float> for this purpose. This works fine.

There's one problem, though: Computing GetHashCode() and equality comparison are fairly expensive on structural F# data types. In my application I know in advance that I won't ever request a memoized function value for a copy of the original object. Thus it would be sufficient to use object identity for computing hash codes and testing for equality in the lookup table. What's the best way to do this? An id(x) -> long function that transforms an object into some sort of unique identifier would seem to do the trick. In C++ land, I'd just use the memory address, of course, but that won't fly in .NET land.

.

Maybe you could wrap the map values in a wrapper class that uses the [<ReferenceEquality>] attribute and then simply use a Dictionary<MapWrapper, float>?

By on 7/11/2009 5:36 AM ()

That might work, but I'd have to cast back to Map every time I use a function from the Map module on it.

By on 7/11/2009 7:11 AM ()

The best approach is probably to construct the dictionary with an IEqualityComparer that uses System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode for the hash code generation. (I just found out about that helper function by looking at the source of F#'s PhysicalHash function. The MSDN docs for Object.GetHashCode don't mention it, of course.)

By on 7/11/2009 8:43 AM ()

Thanks! That was what I needed.

Here's my solution:

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

/// A wrapper for objects that hashes and compares based on physical equality. Useful
/// for memoizing function results.
type PhysicalHashWrapper<'a> (x:'a) =
    let content : System.WeakReference  = new System.WeakReference(x)
    let hashcode = System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(x)


    /// The wrapped object
    member public p.Content
        with get() : Option<'a> = 
            if content.IsAlive then // This test avoids unnecessary try...catch handling
                try
                    Some(content.Target :?> 'a)
                with
                    | :? System.InvalidOperationException -> None
            else
                None        


    override p.GetHashCode() = hashcode
    override p.Equals(y) =
        match y with
        | :? PhysicalHashWrapper<'a> as yph -> 
            match yph.Content with
            | None -> false
            | Some(thatcontent) ->
                match p.Content with
                | None -> false
                | Some(mycontent) -> LanguagePrimitives.PhysicalEquality mycontent thatcontent
        | _ -> false

I can then use a PhysicalHashWrapper(x) as a key to memoize a function result with respect to x.

By on 7/14/2009 12:26 PM ()

Wrapping every object really isn't necessary. All you need is to to provide an IEqualityComparer to the dictionary used for the caching, as in the following example:

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

open System.Collections.Generic


let PhysicalEqualityComparer() =
    { new IEqualityComparer<'a> with
         override t.GetHashCode(x) = LanguagePrimitives.PhysicalHash x
         override t.Equals(x, y) = LanguagePrimitives.PhysicalEquality x y }


let test() =    
    let dict = new Dictionary<string,int>()
    let pdict = new Dictionary<string,int>(PhysicalEqualityComparer())
    let s1 = new string('1', 1)
    let s2 = new string('1', 1)
    dict.[s1] <- 1
    dict.[s2] <- 2
    pdict.[s1] <- 1
    pdict.[s2] <- 2    
    printfn "Key-value pairs in normal dictionary:"
    for kv in dict do
        printfn "Key: %s Value: %i" kv.Key kv.Value
    printfn ""
    printfn "Key-value pairs in dictionary with physical equality:"
    for kv in pdict do
        printfn "Key: %s Value: %i" kv.Key kv.Value
            
test()
By on 7/14/2009 1:11 PM ()

Good idea! Wouldn't we still have to call System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(x), though? The reference for LanguagePrimitives.PhysicalHash says that for value types it hashes on the value, which goes against the idea of forcing a physical hash in all cases, and in particular for unwieldy value types.

By on 7/14/2009 1:37 PM ()

No, calling System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode for structs would be an error. That function takes an obj argument and returns a hash code generated with the object identity. Every time you call the function with a struct, the struct is boxed and gets a new object identity. So you would end up generating different hash codes for the same value, which violates the GetHashCode requirements. Try it out for yourself: repeatedly run "System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(1)" in the fsi console.

Since in your case the Map values are reference types, you don't need to worry about structs. If you want to exclude structs as type arguments for using PhysicalEqualityComparer, you can do this by using a type constraint, as in the following sample:

1
2
3
4

let PhysicalEqualityComparer<'a when 'a : not struct>() =
    { new IEqualityComparer<'a> with
         override t.GetHashCode(x) = LanguagePrimitives.PhysicalHash x
         override t.Equals(x, y) = LanguagePrimitives.PhysicalEquality x y }

If you really need to use structs as keys, you should overwrite GetHashCode or write a special IEqualityComparer. Since GetHashCode can be coarser than Equals, it is usually enough to generate the hash code from one or two frequently changed fields in the struct.

By on 7/14/2009 2:29 PM ()

Ash over my head...of course you're right.

By on 7/14/2009 3:22 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