Difference between revisions of "Transforming slice of structs into struct of slices"

From D Wiki
Jump to: navigation, search
(sections)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
=== {{{A simple application of metaprogramming: turning an array/slice of structs into a struct of arrays/slices|}}} ===
+
A simple application of metaprogramming: turning an array/slice of structs into a struct of arrays/slices
  
 
In some applications it is a common requirement to transform an array/slice of structs into a struct of arrays/slices.  This may be for cache efficiency (see data-driven design) or in order to present data to an API that requires a different format than the standard internal representation of client code.  If the struct design is fixed then this can be done in a few lines of code, but in cases where the struct design may change over time, or the struct itself is constructed via metaprogramming or CTFE then it may be helpful to create the new struct definition in code.
 
In some applications it is a common requirement to transform an array/slice of structs into a struct of arrays/slices.  This may be for cache efficiency (see data-driven design) or in order to present data to an API that requires a different format than the standard internal representation of client code.  If the struct design is fixed then this can be done in a few lines of code, but in cases where the struct design may change over time, or the struct itself is constructed via metaprogramming or CTFE then it may be helpful to create the new struct definition in code.
Line 7: Line 7:
 
http://forum.dlang.org/post/mzpwjelelctwvxzbsijh@forum.dlang.org
 
http://forum.dlang.org/post/mzpwjelelctwvxzbsijh@forum.dlang.org
  
Array of structs
+
'''Array of structs:'''
<code>
+
<syntaxhighlight lang="D">
<nowiki>
 
 
struct PriceBar
 
struct PriceBar
 
{
 
{
Line 20: Line 19:
  
 
PriceBar[] priceBar;
 
PriceBar[] priceBar;
</nowiki>
+
</syntaxhighlight>
</code>
 
  
Desired - struct of arrays:
+
'''Desired - struct of arrays:'''
  
<code>
+
<syntaxhighlight lang="D">
<nowiki>
 
 
struct PriceBars
 
struct PriceBars
 
{
 
{
Line 35: Line 32:
 
   double[] closes;
 
   double[] closes;
 
}
 
}
</nowiki>
+
</syntaxhighlight>
</code>
+
=== Solution 1 ===
 
 
 
First solution - from Economic Modeling, a Moscow, Idaho (USA) based company that uses D to support their big data analysis of economic fundamental developments. Code from https://github.com/economicmodeling/soa:
 
First solution - from Economic Modeling, a Moscow, Idaho (USA) based company that uses D to support their big data analysis of economic fundamental developments. Code from https://github.com/economicmodeling/soa:
<code>
+
<syntaxhighlight lang="D">
<nowiki>
 
  
 
struct SOA(A : T[], T) if (is(T == struct))
 
struct SOA(A : T[], T) if (is(T == struct))
Line 81: Line 76:
 
}
 
}
 
}
 
}
</nowiki>
+
</syntaxhighlight>
</code>
+
=== Solution 2 ===
 
 
 
Solution from John Colvin, organizer of the Scientific Computing portal for D, DlangScience:
 
Solution from John Colvin, organizer of the Scientific Computing portal for D, DlangScience:
<code>
+
<syntaxhighlight lang="D">
<nowiki>
 
  
 
import std.typetuple;
 
import std.typetuple;
Line 159: Line 152:
 
   
 
   
 
alias TransformMembers(alias TypeTransform, alias NameTransform, T) = Tuple!(
 
alias TransformMembers(alias TypeTransform, alias NameTransform, T) = Tuple!(
         RoundRobin!(Pack!(staticMap!(TypeTransform, FieldTypeTuple!PriceBar)),
+
         RoundRobin!(Pack!(staticMap!(TypeTransform, FieldTypeTuple!T)),
                     Pack!(staticMap!(NameTransform, FieldNameTuple!PriceBar))));
+
                     Pack!(staticMap!(NameTransform, FieldNameTuple!T))));
 
   
 
   
 
import std.datetime;
 
import std.datetime;
Line 174: Line 167:
 
   
 
   
 
alias PriceBars = TransformMembers!(SliceOf, TemplAppender!"s", PriceBar);
 
alias PriceBars = TransformMembers!(SliceOf, TemplAppender!"s", PriceBar);
</nowiki>
+
</syntaxhighlight>
</code>
+
=== Solution 3 ===
 
 
  
 
Solution from Artur Skawina on the forum:
 
Solution from Artur Skawina on the forum:
 
The simplest solution is something like the following.  You will need to adjust to your requirements (eg drop the '"~LENGTH.stringof~"' part to get a struct-of-slices, which is what your example above shows).
 
The simplest solution is something like the following.  You will need to adjust to your requirements (eg drop the '"~LENGTH.stringof~"' part to get a struct-of-slices, which is what your example above shows).
<code>
+
<syntaxhighlight lang="D">
<nowiki>
 
 
 
  
 +
template SOA(Struct, size_t LENGTH) {
 +
  struct SOA  {
 +
      enum MEMBERNAME(size_t N) = __traits(identifier, Struct.tupleof[N]);
 +
      static __gentypes() {
 +
        string ret;
 +
        foreach (I, TYPE; typeof(Struct.tupleof))
 +
            ret ~= "align(16) typeof(Struct.tupleof["~I.stringof~"])["~LENGTH.stringof~"] "
 +
                    ~ MEMBERNAME!I ~ ";";
 +
        return ret;
 +
      }
 +
      mixin(__gentypes());
 +
  }
 +
}
  
  template SOA(Struct, size_t LENGTH) {
+
alias PriceBars = SOA!(PriceBar, 8);
      struct SOA  {
+
</syntaxhighlight>
        enum MEMBERNAME(size_t N) = __traits(identifier, Struct.tupleof[N]);
 
  
        static __gentypes() {
 
            string ret;
 
            foreach (I, TYPE; typeof(Struct.tupleof))
 
              ret ~= "align(16) typeof(Struct.tupleof["~I.stringof~"])["~LENGTH.stringof~"] "
 
                      ~ MEMBERNAME!I ~ ";";
 
            return ret;
 
        }
 
        mixin(__gentypes());
 
      }
 
  }
 
  
  alias PriceBars = SOA!(PriceBar, 8);
+
[[Category:HowTo]]
</nowiki>
 
</code>
 

Latest revision as of 03:02, 17 February 2018

A simple application of metaprogramming: turning an array/slice of structs into a struct of arrays/slices

In some applications it is a common requirement to transform an array/slice of structs into a struct of arrays/slices. This may be for cache efficiency (see data-driven design) or in order to present data to an API that requires a different format than the standard internal representation of client code. If the struct design is fixed then this can be done in a few lines of code, but in cases where the struct design may change over time, or the struct itself is constructed via metaprogramming or CTFE then it may be helpful to create the new struct definition in code.

This is not intended to be a complete or definitive solution to the problem, but here are three approaches presented by experienced users on the D forum. I hope that this explanation will be filled out by others in time.

http://forum.dlang.org/post/mzpwjelelctwvxzbsijh@forum.dlang.org

Array of structs:

struct PriceBar
{
  DateTime date;
  double open;
  double high;
  double low;
  double close;
}

PriceBar[] priceBar;

Desired - struct of arrays:

struct PriceBars
{
  DateTime[] dates;
  double[] opens;
  double[] highs;
  double[] lows;
  double[] closes;
}

Solution 1

First solution - from Economic Modeling, a Moscow, Idaho (USA) based company that uses D to support their big data analysis of economic fundamental developments. Code from https://github.com/economicmodeling/soa:

struct SOA(A : T[], T) if (is(T == struct))
{
	mixin CommonImpl;

	private static string getMemberDecls() @property pure
	{
		string ret;
		foreach (name; Fields)
			ret ~= `typeof(U.`~name~`)[] `~name~`;`;
		return ret;
	}

	// Actual storage
	mixin(getMemberDecls);

	/// Array lengths
	auto length() @property const
	{
		// We expect all arrays to have the same length
		static enum FirstMember = Fields[0];
		return __traits(getMember, this, FirstMember).length;
	}

	///
	void length(size_t newLen) @property
	{
		auto oldLen = length;
		foreach (Name; Fields)
		{
			__traits(getMember, this, Name).length = newLen;
			if (oldLen < newLen)
			{
				// initialize new values
				foreach (ref e; __traits(getMember, this, Name)[oldLen .. newLen])
					e = __traits(getMember, initValues, Name);
			}
		}
	}
}

Solution 2

Solution from John Colvin, organizer of the Scientific Computing portal for D, DlangScience:

import std.typetuple;
import std.typecons;
import std.traits;
 
struct Pack(TL...)
{
    alias expand = TL;
    enum length = TL.length;
    @disable this();
}
 
enum isPack(T) = is(T == Pack!Args, Args...);
    
template EqualLength(Packs ...)
if(allSatisfy!(isPack, Packs) && Packs.length != 0)
{
    static if (Packs.length == 1) enum EqualLength = true;
    else
    {
        template EqualLengthTo(size_t len)
        {
            enum EqualLengthTo(T) = len == T.length;
        }
        enum EqualLength = Filter!(EqualLengthTo!(Packs[0].length), Packs[1 .. $]).length == Packs.length - 1;
    }
}
    
template Alias(alias a)
{
    static if (__traits(compiles, { alias x = a; }))
        alias Alias = a;
    else static if (__traits(compiles, { enum x = a; }))
        enum Alias = a;
    else
        static assert(0, "Cannot alias " ~ a.stringof);
}
 
template Alias(a...)
{
    alias Alias = a;
}
    
template Head(Pack)
if(isPack!Pack)
{
    alias Head = Alias!(Pack.expand[0]);
}
    
template Tail(Pack)
if(isPack!Pack)
{
    alias Tail = Pack!(Pack.expand[1 .. $]);
}
    
template TemplAppender(string suffix)
{
    enum TemplAppender(string s) = s ~ suffix;
}
    
template RoundRobin(Args ...)
if(Args.length >= 2 && allSatisfy!(isPack, Args) && EqualLength!Args)
{
    static if (Args[0].length == 0)
        alias RoundRobin = TypeTuple!();
    else
        alias RoundRobin = TypeTuple!(staticMap!(Head, Args), RoundRobin!(staticMap!(Tail, Args)));
}
 
alias SliceOf(T) = T[];
 
alias TransformMembers(alias TypeTransform, alias NameTransform, T) = Tuple!(
        RoundRobin!(Pack!(staticMap!(TypeTransform, FieldTypeTuple!T)),
                    Pack!(staticMap!(NameTransform, FieldNameTuple!T))));
 
import std.datetime;
 
struct PriceBar
{
    DateTime date;
    double open;
    double high;
    double low;
    double close;
}
 
alias PriceBars = TransformMembers!(SliceOf, TemplAppender!"s", PriceBar);

Solution 3

Solution from Artur Skawina on the forum: The simplest solution is something like the following. You will need to adjust to your requirements (eg drop the '"~LENGTH.stringof~"' part to get a struct-of-slices, which is what your example above shows).

template SOA(Struct, size_t LENGTH) {
   struct SOA  {
      enum MEMBERNAME(size_t N) = __traits(identifier, Struct.tupleof[N]);
       static __gentypes() {
         string ret;
         foreach (I, TYPE; typeof(Struct.tupleof))
            ret ~= "align(16) typeof(Struct.tupleof["~I.stringof~"])["~LENGTH.stringof~"] "
                    ~ MEMBERNAME!I ~ ";";
         return ret;
      }
      mixin(__gentypes());
   }
}

alias PriceBars = SOA!(PriceBar, 8);