[Ann] LightSumTypes.jl - Combine multiple types in a single one

[Tortar]

For who is interested, I did some performance comparisons: first I tried to adapt the code in the post

Union splitting vs C++

This is a continuation from this thread: Performance drawback with subtyping - #31 by paulmelis Here we have two codes, which compute someting simple (the sum of the values of a field of a type in an array of mixed types of objects). Typical case where it is hard to be type-stable and avoid run-time dispatch. With 2 different types in the list of types, union splitting kicks in in Julia and the code is fast. With more (in the present example 5 types), it does not. In the C++ code clearly it do…

where it was shown that the natural Julia version (Runtime Dispatch in the results) was much faster than the natural C++ version. I added two version using DynamicSumTypes instead, and the results are really good, in particular even with an abstract container we achieve the speed of the optimal Julia version. With a concrete vector it also beats the C++ version!

C++

// g++ -o disp -O3 -march=native -W -Wall disp.cpp
#include <sys/time.h>
#include
#include <stdlib.h>
#include

struct LineAbstract
{
virtual double paint() =0;
};

struct LineA : public LineAbstract
{
LineA(double l) { length = l; }
virtual double paint() { return length; }
double length;
};

struct LineB : public LineAbstract
{
LineB(double l) { length = l; }
virtual double paint() { return length; }
double length;
};

struct LineC : public LineAbstract
{
LineC(double l) { length = l; }
virtual double paint() { return length; }
double length;
};

struct LineD : public LineAbstract
{
LineD(double l) { length = l; }
virtual double paint() { return length; }
double length;
};

struct LineE : public LineAbstract
{
LineE(double l) { length = l; }
virtual double paint() { return length; }
double length;
};

struct Picture
{
Picture(std::vector<LineAbstract*> l) { lines = l; }
std::vector<LineAbstract*> lines;
};

// Dynamic dispatch at runtime
double paint(Picture& p)
{
double s = 0.0;

for (auto l : p.lines)
    s += l->paint();

return s;

}

double tdiff(struct timeval t0, struct timeval t1)
{
return (t1.tv_sec - t0.tv_sec) + (t1.tv_usec - t0.tv_usec)/1000000.0;
}

int main()
{
int n = 1000000;
printf(“n = %i \n”,n);

std::vector<LineAbstract*> lines;
for (int i = 0; i < n; i++)
{        
    double r = ((double) rand() / (RAND_MAX));
    if (r <= 0.2)
      lines.push_back((LineAbstract*)new LineA(r));
    else if (r <= 0.4)
      lines.push_back((LineAbstract*)new LineB(r)); 
    else if (r <= 0.6)
      lines.push_back((LineAbstract*)new LineC(r)); 
    else if (r <= 0.8)
      lines.push_back((LineAbstract*)new LineD(r)); 
    else if (r <= 1.0)
      lines.push_back((LineAbstract*)new LineE(r)); 
}

Picture p(lines);

struct timeval t0, t1;
double t, res;

// Store resulting sum, to make sure the calls aren't erased
gettimeofday(&t0, NULL);
res = paint(p);
gettimeofday(&t1, NULL);
t = tdiff(t0,t1);
printf("dynamic dispatch : %.6f us per iteration (%.6f ms total) [%.6f]\n", t/n*1000000, t*1000, res);

}

Julia

module Lines

using BenchmarkTools
using Test

abstract type LineAbstract end

struct Line1 <: LineAbstract length::Float64 end
struct Line2 <: LineAbstract length::Float64 end
struct Line3 <: LineAbstract length::Float64 end
struct Line4 <: LineAbstract length::Float64 end
struct Line5 <: LineAbstract length::Float64 end

struct Picture{T<:LineAbstract}
       lines::Vector{T}
end 

paint(l :: Line1) = l.length
paint(l :: Line2) = l.length
paint(l :: Line3) = l.length
paint(l :: Line4) = l.length
paint(l :: Line5) = l.length

# Dynamical dispatch at runtime

function paint1(p)
  s = 0.
  for l in p.lines
    s += paint(l)
  end
  s
end

# Union splitting

function paint2(p)
  s = 0.
  for l in p.lines
    if l isa Line1
      s += paint(l)
    elseif l isa Line2
      s += paint(l)
    elseif l isa Line3
      s += paint(l)
    elseif l isa Line4
      s += paint(l)
    elseif l isa Line5
      s += paint(l)
    end
  end
  s
end

function run(n)

  line_types = [ Line1, Line2, Line3, Line4, Line5 ]
  p = Picture([line_types[rand(1:5)](rand()) for i in 1:n])

  @test paint1(p) ≈ paint2(p)
  println("result = ", paint1(p))

  print(" Runtime Dispatch: "); @btime paint1($p) 
  print(" Manual Splitting: "); @btime paint2($p) 
end

end

module Lines2

using DynamicSumTypes
using BenchmarkTools
using Test

abstract type LineAbstract end

@sum_structs Line <: LineAbstract begin
    struct Line1 length::Float64 end
    struct Line2 length::Float64 end
    struct Line3 length::Float64 end
    struct Line4 length::Float64 end
    struct Line5 length::Float64 end
end
export_variants(Line)

struct Picture{T<:LineAbstract}
       lines::Vector{T}
end 

@pattern paint(l::Line1) = l.length
@pattern paint(l::Line2) = l.length
@pattern paint(l::Line3) = l.length
@pattern paint(l::Line4) = l.length
@pattern paint(l::Line5) = l.length

function paint1(p)
  s = 0.
  for l in p.lines
    s += paint(l)
  end
  s
end

function run(n)

  line_types = [ Line1, Line2, Line3, Line4, Line5]
  
  p1 = Picture(Line[line_types[rand(1:5)](rand()) for i in 1:n])
  p2 = Picture(LineAbstract[line_types[rand(1:5)](rand()) for i in 1:n])
  
  print("Concrete Vector with DynamicSumTypes: "); @btime paint1($p1) 
  print("Abstract Vector with DynamicSumTypes: "); @btime paint1($p2) 
end

@finalize_patterns
end

# running
Lines.run(1_000_000)
Lines2.run(1_000_000)

C++ Version: 6.951 ms
Runtime Dispatch:   49.216 ms (2000000 allocations: 30.52 MiB)
Manual Splitting:   7.267 ms (0 allocations: 0 bytes)
Concrete Vector with DynamicSumTypes:   4.659 ms (0 allocations: 0 bytes)
Abstract Vector with DynamicSumTypes:   8.003 ms (0 allocations: 0 bytes)

For another data point on the performance of this approach, the docs of Agents.jl at https://juliadynamics.github.io/Agents.jl/stable/performance_tips/#multi_vs_union can be useful (the @multiagent macro has at its base this package). There a simple model is run, and Unions are much slower in comparison: