Difference between revisions of "Template:Article Group"

From D Wiki
Jump to: navigation, search
(article template)
 
({{{Name|}}})
Line 1: Line 1:
=== {{{Name|}}} ===
+
=== {{{A simple application of metaprogramming: turning an array/slice of structs into a struct of arrays/slices|}}} ===
{{{Articles|}}}
+
 
 +
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
 +
 
 +
<code>Array of structs
 +
<nowiki>
 +
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;
 +
}
 +
</nowiki>
 +
</code>
 +
 
 +
<code>First solution - from Economic Modeling, a Moscow, Idaho (USA) based company that uses D to support their big data analysis of economic fundamental developments:
 +
<nowiki>
 +
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);
 +
}
 +
}
 +
}
 +
}
 +
</nowiki>
 +
</code>
 +
 
 +
<code>Solution from John Colvin, organizer of the Scientific Computing portal for D:
 +
<nowiki>
 +
 
 +
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!PriceBar)),
 +
                    Pack!(staticMap!(NameTransform, FieldNameTuple!PriceBar))));
 +
 +
import std.datetime;
 +
 +
struct PriceBar
 +
{
 +
    DateTime date;
 +
    double open;
 +
    double high;
 +
    double low;
 +
    double close;
 +
}
 +
 +
alias PriceBars = TransformMembers!(SliceOf, TemplAppender!"s", PriceBar);
 +
</nowiki>
 +
</code>
 +
 
 +
<code>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).
 +
<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());
 +
      }
 +
  }
 +
 
 +
  alias PriceBars = SOA!(PriceBar, 8);
 +
</nowiki>
 +
</code>

Revision as of 23:59, 4 July 2015

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;
}
 

First solution - from Economic Modeling, a Moscow, Idaho (USA) based company that uses D to support their big data analysis of economic fundamental developments:

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 from John Colvin, organizer of the Scientific Computing portal for D:


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!PriceBar)),
                    Pack!(staticMap!(NameTransform, FieldNameTuple!PriceBar))));
 
import std.datetime;
 
struct PriceBar
{
    DateTime date;
    double open;
    double high;
    double low;
    double close;
}
 
alias PriceBars = TransformMembers!(SliceOf, TemplAppender!"s", PriceBar);
 

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);