Benchmarks of Multidimensional Stack Implementations in Julia

By: Christopher Rackauckas

Re-posted from: http://www.stochasticlifestyle.com/233-2/

Datastructures.jl claims it’s fast. How does it do? I wrote some quick codes to check it out. What I wanted to do is find out which algorithm does best for implementing a stack where each element is three integers. I tried filling a pre-allocated array, pushing into three separate vectors, and different implementations of the stack from the DataStructures.jl package.

function baseline()
  stack = Array{Int64,2}(1000000,3)
  for i=1:1000000,j=1:3
    stack[i,j]=i
  end
end 
function baseline2()
  stack = Array{Int64,2}(1000000,3)
  for j=1:3,i=1:1000000
    stack[i,j]=i
  end
end
function f0()
  stack = Array{Int64}(1000000,3)
  for i = 1:1000000
    stack[i,:] = [i,i,i]
  end
end
function f02()
  stack = Array{Int64}(3,1000000)
  for i = 1:1000000
    stack[:,i] = [i;i;i]
  end
end
function f1()
  stack1 = Vector{Int64}(1)
  stack2 = Vector{Int64}(1)
  stack3 = Vector{Int64}(1)
  for i = 1:1000000
    push!(stack1,i)
    push!(stack2,i)
    push!(stack3,i)
  end
end
function f2()
  stack1 = Stack(Int)
  stack2 = Stack(Int)
  stack3 = Stack(Int)
  for i = 1:1000000
    push!(stack1,i)
    push!(stack2,i)
    push!(stack3,i)
  end
end
function f3()
  stack = Stack{}(Tuple{Int64,Int64,Int64})
  for i = 1:1000000
    push!(stack,(i,i,i))
  end
end
function f4()
  stack = Stack{}(Vector{Int64})
  for i = 1:1000000
    push!(stack,[i,i,i])
  end
end
using Benchmark
using DataStructures
base = benchmark(baseline,"baseline",1000)
println(base)
base2 = benchmark(baseline2,"baseline2",1000)
println(base2)
df0 = benchmark(f0,"array",1000)
println(df0)
df02 = benchmark(f02,"arrayTranspose",1000)
println(df02)
df1 = benchmark(f1,"vectorStack",1000)
println(df1)
df2 = benchmark(f2,"dsStacks",1000)
println(df2)
df3 = benchmark(f3,"dsStackTuple",1000)
println(df3)
df4 = benchmark(f4,"dsStackVector",1000)
println(df4)

The results were as follows:

| Row | Category   | Benchmark  | Iterations | TotalWall | AverageWall |
|-----|------------|------------|------------|-----------|-------------|
| 1   | "baseline" | "baseline" | 1000       | 11.7169   | 0.0117169   |
 
| Row | MaxWall   | MinWall    | Timestamp             |
|-----|-----------|------------|-----------------------|
| 1   | 0.0158455 | 0.00978837 | "2016-02-29 23:23:51" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category    | Benchmark   | Iterations | TotalWall | AverageWall |
|-----|-------------|-------------|------------|-----------|-------------|
| 1   | "baseline2" | "baseline2" | 1000       | 9.84362   | 0.00984362  |
 
| Row | MaxWall   | MinWall    | Timestamp             |
|-----|-----------|------------|-----------------------|
| 1   | 0.0126953 | 0.00694176 | "2016-02-29 23:24:01" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category | Benchmark | Iterations | TotalWall | AverageWall | MaxWall  |
|-----|----------|-----------|------------|-----------|-------------|----------|
| 1   | "array"  | "array"   | 1000       | 114.288   | 0.114288    | 0.172499 |
 
| Row | MinWall   | Timestamp             |
|-----|-----------|-----------------------|
| 1   | 0.0775942 | "2016-02-29 22:45:42" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category         | Benchmark        | Iterations | TotalWall |
|-----|------------------|------------------|------------|-----------|
| 1   | "arrayTranspose" | "arrayTranspose" | 1000       | 110.981   |
 
| Row | AverageWall | MaxWall  | MinWall   | Timestamp             |
|-----|-------------|----------|-----------|-----------------------|
| 1   | 0.110981    | 0.183495 | 0.0741138 | "2016-02-29 22:47:34" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category      | Benchmark     | Iterations | TotalWall | AverageWall |
|-----|---------------|---------------|------------|-----------|-------------|
| 1   | "vectorStack" | "vectorStack" | 1000       | 34.4623   | 0.0344623   |
 
| Row | MaxWall   | MinWall   | Timestamp             |
|-----|-----------|-----------|-----------------------|
| 1   | 0.0455326 | 0.0285367 | "2016-02-29 22:48:09" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category   | Benchmark  | Iterations | TotalWall | AverageWall |
|-----|------------|------------|------------|-----------|-------------|
| 1   | "dsStacks" | "dsStacks" | 1000       | 38.0762   | 0.0380762   |
 
| Row | MaxWall   | MinWall   | Timestamp             |
|-----|-----------|-----------|-----------------------|
| 1   | 0.0508213 | 0.0303853 | "2016-02-29 22:48:47" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category       | Benchmark      | Iterations | TotalWall | AverageWall |
|-----|----------------|----------------|------------|-----------|-------------|
| 1   | "dsStackTuple" | "dsStackTuple" | 1000       | 19.3516   | 0.0193516   |
 
| Row | MaxWall   | MinWall   | Timestamp             |
|-----|-----------|-----------|-----------------------|
| 1   | 0.0296347 | 0.0140451 | "2016-02-29 22:49:06" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category        | Benchmark       | Iterations | TotalWall |
|-----|-----------------|-----------------|------------|-----------|
| 1   | "dsStackVector" | "dsStackVector" | 1000       | 184.126   |
 
| Row | AverageWall | MaxWall  | MinWall | Timestamp             |
|-----|-------------|----------|---------|-----------------------|
| 1   | 0.184126    | 0.227575 | 0.16454 | "2016-02-29 22:52:11" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |
1x12 DataFrames.DataFrame
| Row | Category      | Benchmark     | Iterations | TotalWall | AverageWall |
|-----|---------------|---------------|------------|-----------|-------------|
| 1   | "vectorTuple" | "vectorTuple" | 1000       | 23.65     | 0.02365     |
 
| Row | MaxWall   | MinWall   | Timestamp             |
|-----|-----------|-----------|-----------------------|
| 1   | 0.0375346 | 0.0200302 | "2016-02-29 23:29:45" |
 
| Row | JuliaHash                                  | CodeHash | OS        |
|-----|--------------------------------------------|----------|-----------|
| 1   | "a2f713dea5ac6320d8dcf2835ac4a37ea751af05" | NA       | "Windows" |
 
| Row | CPUCores |
|-----|----------|
| 1   | 8        |

Things to learn from this are:

  • Using a tuple is by far the fastest.
  • Datastructures.jl does beat out all except the pre-allocated array
  • The standard vector is pretty close to the DataStructures.jl result

The end result is: use arrays when you can pre-allocate and need mutability, but if you want to throw and retrieve things from a dynamic data structure, using tuples is key. Datastructures.jl has some nice features and (obviously) implementations of data structures, and although they are slightly faster than the native implementation, don’t expect a massive speedup. Still, it’s a well-made package you should try out.

The post Benchmarks of Multidimensional Stack Implementations in Julia appeared first on Stochastic Lifestyle.

Test Driven Development in Julia

By: julia on Abel Soares Siqueira

Re-posted from: https://abelsiqueira.com/blog/2016-03-13-test-driven-development-in-julia/

First, what is Test Driven Development (TDD)?
Well, I’m not an expert, so don’t quote me, but in practice it means that you
develop your code to fulfill tests that you define prior to beginning your work.
You do not define all your tests first, though. You define a single test,
and produce code to pass it. Then you define another code, and produce code to
pass both. And so forth until you complete your specification.

Test Driven Development in Julia

By: julia on Abel Soares Siqueira

Re-posted from: https://abelsiqueira.com/blog/2016-03-13-test-driven-development-in-julia/

First, what is Test Driven Development (TDD)? Well, I’m not an expert, so don’t quote me, but in practice it means that you develop your code to fulfill tests that you define prior to beginning your work. You do not define all your tests first, though. You define a single test, and produce code to pass it. Then you define another code, and produce code to pass both. And so forth until you complete your specification.