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

[Tortar]

I’m happy to announce MixedStructTypes.jl which allows to compactify multiple mutable and immutable types in a single one with a similar syntax to the one of structs. They work identical to structs for many operations because many Base functions are implemented to match the interface for normal structs. The point of working with a unique type instead of many is to avoid dynamic dispatch and abstract containers which have big performance hits.

Two different macros are available, having different memory and speed performance characteristics. The macro based on SumTypes.jl is also a bit more general because it allows to mix mutable and immutable structs where fields belonging to different structs can also have different types. Nonetheless, both already can contain parametric types and allow default values for fields. I think that the fact that the syntax is so similar to the one of structs should help integrate this package into other ones.

An example of usage and a little performance comparison between the two macros are already present in the ReadMe.

Let’s also explore here how do these two macros compare with the one from Unityper.jl. While these macros have also more features than Unityper because they allow for parametric mutable and immutable structs, while Unityper only allows for non-parametric immutable structs, they are also good performance-wise, to show that I repeat the benchmark on the ReadMe but with fewer types for the sake of brevity:

using MixedStructTypes, Unityper, BenchmarkTools

@compactify begin
    @abstract struct AT end
    struct A <: AT 
        a::Int = 1 
    end
    struct B <: AT 
        a::Int = 2
        b::Complex = 1 + 1im
    end
end

@compact_struct_type @kwdef CT begin
    struct C 
        a::Int = 1 
    end
    struct D 
        a::Int = 2
        b::Complex = 1 + 1im 
    end
end

@sum_struct_type @kwdef ET begin
    struct E 
        a::Int = 1 
    end
    struct F 
        a::Int = 2
        b::Complex = 1 + 1im 
    end
end

vec_a = AT[rand((A,B))() for _ in 1:10^6];
vec_c = CT[rand((C,D))() for _ in 1:10^6];
vec_e = ET[rand((E,F))() for _ in 1:10^6];

We look both to time and memory:

julia> @btime sum(x.a for x in $vec_a);
  937.911 μs (0 allocations: 0 bytes)

julia> @btime sum(x.a for x in $vec_c);
  715.359 μs (0 allocations: 0 bytes)

julia> @btime sum(x.a for x in $vec_e);
  3.936 ms (0 allocations: 0 bytes)

julia> Base.summarysize(vec_a)
35791632

julia> Base.summarysize(vec_c)
35487008

julia> Base.summarysize(vec_e)
12820240

As you can see, in this very simple (and so not too informative) benchmark @compact_sum_type is both faster and nearly as memory efficient, while @sum_struct_type is much more memory efficient that the other two macros.

For those interested, the package is already available in the general registry. Issues and PRs are really welcomed

[Tortar]

MixedStructTypes.jl reached version 0.2 with an improved syntax e.g. in the example above:

@compact_structs CT begin
    @kwdef struct C 
        a::Int = 1 
    end
    @kwdef struct D 
        a::Int = 2
        b::Complex = 1 + 1im 
    end
end

I also fixed and tested many edge cases, and made some new enhancements like the ability to constrain type parameters. Let me know if you have suggestions on new functionalities!

[Tortar]

I released a new major version of the package which now includes a feature I conceived some time ago: you can now dispatch on the variants of the type! I’m still working on making it possible to dispatch on the overall type when one wants a default function for a subset of the variants (or kinds in the gergo of the package), for now it is needed to specify a function for all kinds. But let me give a little example:

using DynamicSumTypes
abstract type AbstractShape end
@sum_structs Shape <: AbstractShape begin
    @kwdef struct Square
        side::Float64 = rand()
    end   
    @kwdef struct Rectangle
        width::Float64 = rand()
        height::Float64 = rand()
    end
    @kwdef struct Triangle
        base::Float64 = rand()
        height::Float64 = rand()
    end
    @kwdef struct Circle
        radius::Float64 = rand()
    end
end
@pattern area(s::Shape'.Square) = s.side * s.side
@pattern area(r::Shape'.Rectangle) = r.width * r.height
@pattern area(t::Shape'.Triangle) = 1.0/2.0 * t.base * t.height
@pattern area(c::Shape'.Circle) = π * c.radius^2

here with the macro @pattern we support the usual syntax for functions definitions, it is also good performance-wise:

julia> using BenchmarkTools

julia> count = 1_000_000;

julia> shapes = [rand((Shape'.Square, Shape'.Rectangle, Shape'.Triangle, Shape'.Circle))() for _ in 1:count];

julia> @benchmark sum(area(s) for s in $shapes)
BenchmarkTools.Trial: 966 samples with 1 evaluation.
 Range (min … max):  5.131 ms …  5.423 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     5.158 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   5.171 ms ± 37.811 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

    ▁▄▆███▇▅▄▂▁        ▁ ▁                                    
  ▄▆███████████▇▅▇██████████▆█▇▆█▅█▆▅▆▆▅▆▄▄▅▅▅▅▄▁▄▄▁▁▅▅▁▁▁▄▄ █
  5.13 ms      Histogram: log(frequency) by time     5.34 ms <

 Memory estimate: 0 bytes, allocs estimate: 0.

Before you would have needed to write

function area(sh)
    if kindof(sh) === :Square
        return area_square(sh)
    elseif kindof(sh) === :Rectangle
        return area_rectangle(sh)
    elseif kindof(sh) === :Triangle
        return area_triangle(sh)
    elseif kindof(sh) === :Circle
        return area_circle(sh)
    end
    error()
end
   
area_square(s) = s.side * s.side
area_rectangle(r) = r.width * r.height
area_triangle(t) = 1.0/2.0 * t.base * t.height
area_circle(c) = π * c.radius^2

and in some more advanced cases it would have been even more verbose to do it manually e.g. when you have multiple variants in the arguments.

Even if I’m still working on it, the macro is already fairly general:

• it can dispatch on any type + (possibly parametrized) variants
• variants can be at any position in the arguments of @pattern
• it supports keyword arguments, parameters in where declarations and macros before the function definition

In the process I also renamed the package to DynamicSumTypes, because I think it’s a better name, and I’m always undecided about names

[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:

[Tortar]

I just released version 2.0 which ships some new features and improves the @pattern macro significantly.

Variants are now enclosed in the type, so one need to use Type'.Variant by default to refer to them, so that different types can have the same variants names without clashing. To re-establish the previous behaviour one can use export_variants(Type) and then also the variants names alone will be available. I also changed the name of the versions of the macro, they now are refering to what the macro actually does (@sum_structs :on_fields and @sum_structs :on_types).

The @pattern macro now requires from the user to call @finalize_pattern to register the functions it is applied to when used in a module (usually a module needs only one call to it at the end). This is better than before, because the new mechanism doesn’t have some subtle precompilation problems @pattern had.

Overall, I think DynamicSumTypes is now in a pretty good shape, all features I initially conceived are now implemented. I think it reached a good steady state where no breaking releases should happen for a long time

[Tortar]

Life is tough.

I found a much much much simpler methodology which works very well. Which is both very cool and very sad because I spent so much time on the other approach. So I proceeded to totally change the interface, and I will release a new major version soon. If interested, look at the repository…in any case I will probably do a new announcement post for v3 since it is totally different now.