[julia-users] A common idiom

[Stefan Schwarz]

Lately I was interested in the switch from *O(n) *to *O(log n)* algorithm 
in *dequeue!(pq, key) *(PriorityQueue).
Issue: #8011

What I encountered there is some piece of code, which I see very often. 
Here it is 
the definition of an immutable type *Pair*:

    import Base.hash

    immutable Pair{A, B}
           a::A
           b::B
    end

    function hash(p::Pair, h::Uint)
           h = hash(p.a, h)
           hash(p.b, h)
    end

    hash(p::Pair) = hash(p, zero(Uint))

Now this is very obvious what it does define. So I asked myself why write 
it like that?
Why not write a generic dispatch hash function for type Pair?

    function hash{A,B}(p::Pair{A,B}, h::Uint=zero(Uint))
           h = hash(p.a, h)
           hash(p.b, h)
    end

This does exactly the same. About its readability is on others to decide. 
This is not my point.
My point is. I was interested in the generated code. The first common 
implementation yields 
this on my machine:

@code_llvm hash(p)


define %jl_value_t* @"julia_hash;98714"(%jl_value_t*, %jl_value_t**, i32) {
top:
  %3 = alloca [4 x %jl_value_t*], align 8
  %.sub = getelementptr inbounds [4 x %jl_value_t*]* %3, i64 0, i64 0
  %4 = getelementptr [4 x %jl_value_t*]* %3, i64 0, i64 2, !dbg !1353
  store %jl_value_t* inttoptr (i64 4 to %jl_value_t*), %jl_value_t** %.sub, 
align 8
  %5 = load %jl_value_t*** @jl_pgcstack, align 8, !dbg !1353
  %6 = getelementptr [4 x %jl_value_t*]* %3, i64 0, i64 1, !dbg !1353
  %.c = bitcast %jl_value_t** %5 to %jl_value_t*, !dbg !1353
  store %jl_value_t* %.c, %jl_value_t** %6, align 8, !dbg !1353
  store %jl_value_t** %.sub, %jl_value_t*** @jl_pgcstack, align 8, !dbg 
!1353
  store %jl_value_t* null, %jl_value_t** %4, align 8
  %7 = getelementptr [4 x %jl_value_t*]* %3, i64 0, i64 3
  store %jl_value_t* null, %jl_value_t** %7, align 8
  %8 = load %jl_value_t** %1, align 8, !dbg !1353
  store %jl_value_t* %8, %jl_value_t** %4, align 8, !dbg !1354
  %9 = call %jl_value_t* @jl_box_uint64(i64 0), !dbg !1354
  store %jl_value_t* %9, %jl_value_t** %7, align 8, !dbg !1354
  %10 = call %jl_value_t* @jl_apply_generic(%jl_value_t* inttoptr (i64 
140372045145152 to %jl_value_t*), %jl_value_t** %4, i32 2), !dbg !1354
  %11 = load %jl_value_t** %6, align 8, !dbg !1354
  %12 = getelementptr inbounds %jl_value_t* %11, i64 0, i32 0, !dbg !1354
  store %jl_value_t** %12, %jl_value_t*** @jl_pgcstack, align 8, !dbg !1354
  ret %jl_value_t* %10, !dbg !1354
}


(p here is Pair("Hello", 1))

Now the second implementation yields this:

@code_llvm hash(p)

define i64 @"julia_hash;98673"(%jl_value_t*) {
top:
  %1 = call i64 @"julia_hash;98654"(%jl_value_t* %0, i64 0), !dbg !1231, 
!julia_type !1233
  ret i64 %1, !dbg !1231
} 


The first one may be considered as quite a mouth full.

Now more code is not necessarily slow code, but this result came at a 
rather surprise to me.
It is obvious that the dispatching happens quite directly.

Why is this?

Here's my versioninfo:

Julia Version 0.4.0-dev+410
Commit 0e55472* (2014-08-28 03:59 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin13.3.0)
  CPU: Intel(R) Core(TM) i7-2635QM CPU @ 2.00GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
  LAPACK: libopenblas
  LIBM: libopenlibm
  LLVM: libLLVM-3.3


(I deleted my bank-account information, because it's of no interest here ;) 
)

Greetings

Stefan