kmsquire

Timing comparison (left = original, right= ranked)

LRU (original)                                        LRU (ranked)                                                     
  UnboundedLRU(), 50 items                              UnboundedLRU(), 50 items                            
    Assignment:                                           Assignment:                                       
        elapsed time: 0.08705282211303711 seconds             elapsed time: 0.0904841423034668 seconds      
    Lookup, random access:                                Lookup, random access:                            
        elapsed time: 0.02248096466064453 seconds             elapsed time: 0.029716014862060547 seconds    
    Random mixed workload:                                Random mixed workload:                            
        elapsed time: 0.0009319782257080078 seconds           elapsed time: 0.0009610652923583984 seconds   

kmsquire

size=1000
  Naive sum min: 0.9999999999999952 (error: 4.7739590058881731e-15)
  Naive sum max: 1.0000000000000056 (error: 5.5511151231257827e-15)
  KBN sum min  : 0.9999999999999999 (error: 1.1102230246251565e-16)
  KBN sum max  : 1.0000000000000000 (error: 0.0000000000000000e+00)
  Min p        : 0.0000000017882931 (       1.7882930846464359e-09)

size=10000
  Naive sum min: 0.9999999999999883 (error: 1.1657341758564144e-14)
  Naive sum max: 1.0000000000000142 (error: 1.4210854715202004e-14)

kmsquire

# Generate sort$n(vs), sortk(n1,...,nk) functions
function gen_sort(n)
    # Generate n symbols to manipulate
    vs = [gensym("v") for i=1:n]
    
    ## These two lines are setup for the sort$n functions

    # Set each symbol equal to an element of the input list
    vss = {:($v = vs[$i]) for (v,i) in enumerate(vs)}

kmsquire

function _julia_re(name, re)
    sym = symbol("julia_$(string(name))")
    quote
        $(esc(sym)) = $re
        $(esc(sym)) = "(?<"*$(string(name))*">"*$(esc(sym))*")"
    end
end

macro julia_re(name, re)
   _julia_re(name, re)

kmsquire

## modeled after sort tests in python's sortperf.py
##
## Note: as written, it requires DataFrames + https://github.com/HarlanH/DataFrames.jl/pull/83
##
## Kevin Squire
##
##
#
# julia> load("timsort")
#

kmsquire

Here are 3 implemenations of an `OrderedDict` for julia.  The first
creates a `DictItem` class, which is stored as the value in a wrapped
Dict.  The second only stores a vector of keys, and the third
reimplements the standard julia hash-based dictionary inline, and adds
just enough information to maintain key-value order.  

I had other, similar versions along the way, with minor tweaks that 
didn't change the timings much.  This includes a version where
DictItem was immutable.

kmsquire

macro memoize(ex)
    local f, u, g
    g = randstring(6)
    if isa(ex,Expr) && (ex.head == :function || ex.head == symbol("=")) &&
       !isempty(ex.args) && ex.args[1].head == :call && !isempty(ex.args[1].args)
        f = ex.args[1].args[1]
        ex.args[1].args[1] = u = symbol(string(f,"_unmemoized"))
    else
        error("@memoize must be applied to a method definition")
    end

kmsquire

module sp

export sortperf, std_sort_tests

import Base.Sort: InsertionSort, QuickSort, MergeSort, TimSort, Algorithm, Ordering

using DataFrames

# rand functions for testing
randstr(n::Int) = [randstring() for i = 1:n]

kmsquire

# To test pre-patch Dict performance

n = 100000
srand(0x123456)
strs = [randstring(10) for i = 1:n];
nums = rand(Int, n);

# regular map

function dict_insertion_test(d::Dict)

kmsquire

julia> func(0,.1,.1); @time func(0,.1,10000)
elapsed time: 1.43696256 seconds (800264048 bytes allocated)

julia> func3(0,.1,.1); @time func3(0,.1,10000)
elapsed time: 0.838369673 seconds (800264048 bytes allocated)

julia> func5(0,.1,.1); @time func5(0,.1,10000)
elapsed time: 0.409506126 seconds (1000312 bytes allocated)