Re: Deciding on tensor parameters
Stefan Seefeld via ublas <[email protected]> Thu, 13 Sep 2018 12:10:54 -0400
| Newsgroups | gmane.comp.lib.boost.ublas |
|---|---|
| Message-ID | <[email protected]> |
This is a multi-part message in MIME format.
--===============4591603692404225328==
Content-Type: multipart/alternative;
boundary="------------FDF0BDD9D801D2021DF35CA1"
Content-Language: en-US
This is a multi-part message in MIME format.
--------------FDF0BDD9D801D2021DF35CA1
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Hi Cem,
thanks for sending this out !
On 2018-09-13 11:34 AM, Cem Bassoy via ublas wrote:
> The GSOC 2018 project with the title "Adding tensor support " has been
> succefully completed. Boost.uBlas may support tensors in future. The
> code, project and documentation can be found here
> <https://github.com/BoostGSoC18/tensor> and here
> <https://github.com/BoostGSoC18/tensor/wiki/Documentation>.
>
> The tensor template class is parametrized in terms of data
> type,storage format (first- or last-order), storage type (e.g.
> std::vector or std::array):
(Minor nit-pick: it's a class template. There is no such thing as
"template classes" in C++ :-). I know the existing ublas docs are full
of that spelling...)
> template<class T, class F=first_order, class
> A=std::vector<T,std::allocator<T>>>
> class tensor;
>
> An instance of a tensor template class has dynamic rank (number of
> dimensions) and dimensions using a shape class that holds the data.
> It is a adaptor of std::vector where the rank is the size of it:
>
> // {3,4,2} could be runtime variables of an integer type.
> auto A = tensor<float>{make_shape(3,4,2)}; ---------------------
> ---------------------
> I am thinking to redesign the tensor template class where the rank is
> a compile time parameter:
>
> template<class T, std::size_t N, class F=first_order<N>, class
> A=std::vector<T,std::allocator<T>>> class tensor;
> An instance of a tensor template class could be generated as follows:
> // {3,4,2} could be runtime variables of an integer type. auto A =
> tensor<float,3>(make_shape(3,4,2));
>
> This instantiation could be definitely improved. However, having a
> static rank has the following advantages and disadvantages:
>
> -------------
>
> *Advantages*:
>
> 1. improving runtime behavior about 30% to 5 % of basic tensor
> operations ( depends according to my findings on the length of the
> inner most loop ).
> 2. ability to statically distinguish between different tensor types
> at compile time. tensor<float,3> is a different type than
> tensor<float,4>. If so, why not setting matrix as an alias:
>
>
> template <class type, class format, class storage>
> using matrix = tensor<type,2,format,storage>.
>
> We would only need to specify and implement one data structure '
> tensor ' and if needed provide optimized functions for matrices. This
> simplifies the maintenance.
A big advantage (which has been my main motivation for pushing for this
solution) is that such a scenario would be fully in line with the
existing Boost.uBLAS API, so your work becomes a natural extension of
what we already have.
Alternatively, if you keep the rank a runtime parameter, you are
basically proposing an entirely new API, which means that Boost.uBLAS
users will have to decide whether to use the old or the new API, which
I'm afraid will result in a fragmentation of the community. Likewise,
many existing operations only support existing vector and matrix types,
so maintainers will have more work to do to support both APIs.
That, to me as library maintainer, is a very high cost, so I'm reluctant
to such a change, even if the proposed API with runtime ranks is
otherwise sound.
> Also there might be advantages in terms of subtensor and iterator
> support. However implementing them will be harder.
>
> ---------
> *Disadvantages*:
>
> 1. The implementations become more complicated especially for tensor
> multiplications and tensor reshaping.
>
I have worked on a BLAS library with compile-time constant ranks. And
while capturing parameters such as ranks in the type system itself can
indeed be a bit of a challenge, I think it's definitely doable, and may
even lead to clearer code down the road.
> 1.
>
>
>
> 2. With static rank the interfaces are harder to use (setting the
> rank as a template parameter).
>
That depends on the use case. It simply means that you have to think
about the rank slightly differently, while writing code.
(It could simply mean that you have to drag along an additional template
parameter, if you want to write generic code. But as I mentioned above,
this could arguably lead to clearer code, so I consider this a feature,
not a bug. :-) )
> 1. The number of contracted dimensions must be known at compile time.
> Therefore, implementing some tensor algorithms would only be
> possible with template specialization instead of simple for loops.
> Making algorithms becomes more difficult.
>
Right.
> Although Eigen and Boost.MultiArray decided for compile time, it
> might be a critical point for uBLAS.
>
> I am working on this right now and also I am trying to suppprt p!
> number of linear storage formats as a compile time parameter if p is
> the rank of the tensor. Actually unit-testing becomes very hard as I
> am not able to use fixtures so easily. Supporting static and dynamic
> rank will be a maintenance nightmare.
Yeah, the parameter space to cover grows exponentially. But that is true
no matter whether the rank is determined at compile-time or at runtime.
The difference is only in whether you use normal functions or
meta-functions to compute derived ranks, storage formats, et al.
Stefan
--
...ich hab' noch einen Koffer in Berlin...
--------------FDF0BDD9D801D2021DF35CA1
Content-Type: multipart/related;
boundary="------------23D230D7EC054D3C0400003D"
--------------23D230D7EC054D3C0400003D
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: 8bit
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Hi Cem,</p>
<p>thanks for sending this out !<br>
</p>
<br>
<div class="moz-cite-prefix">On 2018-09-13 11:34 AM, Cem Bassoy via
ublas wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CADrR+Fsgi2KQw8PVpKeZ8FezWYn6GWKigJZEebkXExeoj3-AbA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<div dir="ltr">
<div><font size="2">The GSOC 2018 project with the title "Adding
tensor support " has been succefully completed. <font
size="2"><font size="2">Boost.uBlas may support tensors in
future.</font></font> The code, project and
documentation can be found <a
href="https://github.com/BoostGSoC18/tensor"
moz-do-not-send="true">here</a> and <a
href="https://github.com/BoostGSoC18/tensor/wiki/Documentation"
moz-do-not-send="true">here</a>.<br>
</font></div>
<div><font size="2"><br>
</font></div>
<div><font size="2">The tensor template class is parametrized in
terms of d</font><font size="2">ata type,</font><font
size="2"> storage format (first- or last-order)</font><font
size="2">, storage type (e.g. std::vector or std::array):</font></div>
</div>
</blockquote>
<br>
(Minor nit-pick: it's a class template. There is no such thing as
"template classes" in C++ :-). I know the existing ublas docs are
full of that spelling...)<br>
<br>
<blockquote type="cite"
cite="mid:CADrR+Fsgi2KQw8PVpKeZ8FezWYn6GWKigJZEebkXExeoj3-AbA@mail.gmail.com">
<div dir="ltr">
<div><span style="font-family:monospace,monospace"><span
class="gmail-pl-k">template</span><<span
class="gmail-pl-k">class</span> <span class="gmail-pl-en">T</span>,
<span class="gmail-pl-k">class</span> <span
class="gmail-pl-en">F</span>=first_order, <span
class="gmail-pl-k">class</span> <span class="gmail-pl-en">A</span>=std::vector<T,std::allocator<T>>>
</span></div>
<div>
<pre><span style="font-family:monospace,monospace"><span class="gmail-pl-k">class</span> <span class="gmail-pl-en">tensor</span>;</span></pre>
</div>
<div><font size="2"><br>
</font></div>
<div><font size="2">An instance of a tensor template class has </font><font
size="2">dynamic rank (number of dimensions) and dimensions
using a shape class that </font>holds the data. It is a
adaptor of std::vector where the rank is the size of it: <br>
</div>
<div><br>
</div>
<div>
<pre><span style="font-family:monospace,monospace"><font size="2"><span class="gmail-pl-k">// {3,4,2} could be runtime variables of an integer type.
</span></font></span></pre>
<pre><span style="font-family:monospace,monospace"><font size="2"><span class="gmail-pl-k">auto</span> A = tensor<<span class="gmail-pl-k">float</span>>{<span class="gmail-pl-c1">make_shape(3</span>,<span class="gmail-pl-c1">4</span>,<span class="gmail-pl-c1">2</span>)};
</font></span><span style="font-family:arial,helvetica,sans-serif"><font size="2">---------------------
<font size="2">---------------------</font></font></span><span style="font-family:monospace,monospace"><font size="2">
</font></span></pre>
</div>
<div><font size="2">I am thinking to redesign the tensor
template class where the rank is a compile time parameter:<br>
</font></div>
<div><font size="2"><br>
</font></div>
<div>
<pre><span style="font-family:monospace,monospace"><span class="gmail-pl-k">template</span><<span class="gmail-pl-k">class</span> <span class="gmail-pl-en">T</span>, std::size_t N, <span class="gmail-pl-k">class</span> <span class="gmail-pl-en">F</span>=first_order<N>, <span class="gmail-pl-k">class</span> <span class="gmail-pl-en">A</span>=std::vector<T,std::allocator<T>>>
<span class="gmail-pl-k">class</span> <span class="gmail-pl-en">tensor</span>;
</span></pre>
<pre><span style="font-family:arial,helvetica,sans-serif">An instance of a tensor template class could be generated as follows:</span><span style="font-family:monospace,monospace">
</span></pre>
<pre><span style="font-family:monospace,monospace"><span style="font-family:monospace,monospace"><font size="2"><span class="gmail-pl-k">// {3,4,2} could be runtime variables of an integer type.
</span></font></span><span style="font-family:monospace,monospace"><font size="2"><span class="gmail-pl-k">auto</span> A = tensor<<span class="gmail-pl-k">float</span>,3>(make_shape(<span class="gmail-pl-c1">3</span>,<span class="gmail-pl-c1">4</span>,<span class="gmail-pl-c1">2))</span>;</font></span></span></pre>
</div>
<div dir="auto"><font size="2"><br>
</font> </div>
<div><font size="2">This instantiation could be definitely
improved. However, having a static rank has the following
advantages and disadvantages:<br>
</font></div>
<div><font size="2"><br>
</font></div>
<div dir="auto"><font size="2">-------------</font></div>
<div dir="auto"><font size="2"><br>
</font> </div>
<div dir="auto"><font size="2"><b>Advantages</b>:</font></div>
<div dir="auto">
<ol>
<li><font size="2">improving runtime behavior about 30% to 5
% of basic tensor operations ( depends according to my
findings on the length of the inner most loop ).</font></li>
<li><font size="2">ability to statically distinguish between
different tensor types at compile time.
tensor<float,3> is a different type than
tensor<float,4>. If so, why not setting matrix as
an alias:</font> </li>
</ol>
</div>
<div dir="auto"><span style="font-family:monospace,monospace"><font
size="2"><br>
</font></span> </div>
<span style="font-family:monospace,monospace"> </span>
<div dir="auto"><span style="font-family:monospace,monospace"><font
size="2">template <class type, class format, class
storage></font></span></div>
<span style="font-family:monospace,monospace"> </span>
<div dir="auto"><span style="font-family:monospace,monospace"><font
size="2">using matrix =
tensor<type,2,format,storage>.</font></span></div>
<div dir="auto"><font size="2"><br>
</font> </div>
<div dir="auto"><font size="2">We would only need to specify and
implement one data structure ' tensor ' and if needed
provide optimized functions for matrices. This simplifies
the maintenance. <br>
</font></div>
</div>
</blockquote>
<br>
A big advantage (which has been my main motivation for pushing for
this solution) is that such a scenario would be fully in line with
the existing Boost.uBLAS API, so your work becomes a natural
extension of what we already have.<br>
<br>
Alternatively, if you keep the rank a runtime parameter, you are
basically proposing an entirely new API, which means that
Boost.uBLAS users will have to decide whether to use the old or the
new API, which I'm afraid will result in a fragmentation of the
community. Likewise, many existing operations only support existing
vector and matrix types, so maintainers will have more work to do to
support both APIs.<br>
<br>
That, to me as library maintainer, is a very high cost, so I'm
reluctant to such a change, even if the proposed API with runtime
ranks is otherwise sound.<br>
<br>
<blockquote type="cite"
cite="mid:CADrR+Fsgi2KQw8PVpKeZ8FezWYn6GWKigJZEebkXExeoj3-AbA@mail.gmail.com">
<div dir="ltr">
<div dir="auto"><font size="2">Also there might be advantages in
terms of subtensor and iterator support. However
implementing them will be harder. </font></div>
<div dir="auto"><font size="2"><br>
</font> </div>
<div dir="auto"><font size="2">---------</font></div>
<div dir="auto"><font size="2"><b>Disadvantages</b>:</font></div>
<div dir="auto">
<ol>
<li><font size="2">The implementations become more
complicated especially for tensor multiplications and
tensor reshaping.</font></li>
</ol>
</div>
</div>
</blockquote>
<br>
I have worked on a BLAS library with compile-time constant ranks.
And while capturing parameters such as ranks in the type system
itself can indeed be a bit of a challenge, I think it's definitely
doable, and may even lead to clearer code down the road.<br>
<br>
<br>
<blockquote type="cite"
cite="mid:CADrR+Fsgi2KQw8PVpKeZ8FezWYn6GWKigJZEebkXExeoj3-AbA@mail.gmail.com">
<div dir="ltr">
<div dir="auto">
<ol>
<li><font size="2"> <br>
</font></li>
<li><font size="2">With static rank the interfaces are
harder to use (setting the rank as a template
parameter). <br>
</font></li>
</ol>
</div>
</div>
</blockquote>
<br>
That depends on the use case. It simply means that you have to think
about the rank slightly differently, while writing code.<br>
(It could simply mean that you have to drag along an additional
template parameter, if you want to write generic code. But as I
mentioned above, this could arguably lead to clearer code, so I
consider this a feature, not a bug. :-) )<br>
<br>
<blockquote type="cite"
cite="mid:CADrR+Fsgi2KQw8PVpKeZ8FezWYn6GWKigJZEebkXExeoj3-AbA@mail.gmail.com">
<div dir="ltr">
<div dir="auto">
<ol>
<li><font size="2">The number of contracted dimensions must
be known at compile time. Therefore, implementing some
tensor algorithms would only be possible with template
specialization instead of simple for loops. Making
algorithms becomes more difficult.<br>
</font></li>
</ol>
</div>
</div>
</blockquote>
<br>
Right.<br>
<br>
<blockquote type="cite"
cite="mid:CADrR+Fsgi2KQw8PVpKeZ8FezWYn6GWKigJZEebkXExeoj3-AbA@mail.gmail.com">
<div dir="ltr">
<div dir="auto">
<div><font size="2">Although Eigen and Boost.MultiArray
decided for compile time, it might be a critical point
for uBLAS.</font><font size="2"> <br>
</font></div>
<div><font size="2"><br>
</font></div>
<div><font size="2">I am working on this right now and also I
am trying to suppprt p! number of linear storage formats
as a compile time parameter if p is the rank of the
tensor. Actually unit-testing becomes very hard as I am
not able to use fixtures so easily. Supporting static and
dynamic rank will be a maintenance nightmare.</font></div>
</div>
</div>
</blockquote>
<br>
Yeah, the parameter space to cover grows exponentially. But that is
true no matter whether the rank is determined at compile-time or at
runtime. The difference is only in whether you use normal functions
or meta-functions to compute derived ranks, storage formats, et al.<br>
<br>
<div class="moz-signature"><br>
<div class="moz-signature"><img moz-do-not-send="false"
src="cid:[email protected]" alt="Stefan"
width="73" height="45"><br>
<pre>--
...ich hab' noch einen Koffer in Berlin...
</pre>
</div>
</div>
</body>
</html>
--------------23D230D7EC054D3C0400003D
Content-Type: image/png;
name="signature.png"
Content-Transfer-Encoding: base64
Content-ID: <[email protected]>
Content-Disposition: inline;
filename="signature.png"
iVBORw0KGgoAAAANSUhEUgAAAEkAAAAtCAYAAADiFkaQAAAABHNCSVQICAgIfAhkiAAAAAlw
SFlzAAAVhwAAFYcBshnuugAAABl0RVh0U29mdHdhcmUAd3d3Lmlua3NjYXBlLm9yZ5vuPBoA
AAVDSURBVGiB5dpprF1TFMDx33u0iqpWW6LmqWpIVUkoNVbM81ShiJifIakgxAc1VEzxwRiC
8EHwgaAilBhCg6BClJIYaqohSM1t6fVh7afXfffcd+55d8I/uXnvnL3PWuvus/daa699+e8x
CFfhlnYb0qkMw40o4dA229KRDMLL+AnvYYX2mtOZXIj5+B4HttmWjmQkfsCreLDNtnQsV+Er
fIsxbbalI1kDi/AnTm6zLR3LpSKazUJXm23JRauNHIyF+ByjWqy7boagB59gGR4QIbnZHCeW
2Z4t0DUgNsXh4k2Owxti+l/eAt0vt0jPgNgUn2FC2b2NsFjkK81M6E4UDntYE3UMmC6Rl9xU
pW2WmE2bNUn3OPzsX7A/OxC/q+4wrxGDtE3GszvgmIJ6h+CtJH/7gjJaxiO4P6PtSvEltqjS
tifmYXhBvXeJAPF2wedbxmgswd4Z7bfgR30j3Dr4FFsV1HsmZmMOpheU0TJ6hE9YKaN9Hm6v
uNeF53F+QZ2T8IFYYouxZkE5LeNhPJHRNgXfiVlTzikiPeguoG8UFmBXkWE/WkBGS+kWg1Bt
uo/AXOxRcX8kvhFfsl668BhmpusPMK2AnJaytXDKk7EyrhNlihfFbnztKs/chocK6jsbLwn/
Nl5E1NULymoZ08RWYDUMxUE4UiSR1dhQVAuL5EwrieDQu0QvEzlYx3M93q+j/724oUG638UJ
DZLVVJ4SPiIPY8XWYa0G6N1cpB0jGiCrLsojTVY4r2QTEWnyMBN34Ot6jKqgt/xyFF4Q/i8v
Q3EA9jHAMs5kkaCtmqNvt8hRLsjRdwJ+U92R52VHvCPqRq/In0CuhRl4Uszk0gDt8Jr8kWdM
Unh0P/0GiS3LPem6W/6Z2st2+CPpW08Ei81z6D1HnLn16pulAc5+cR1CJgmjd8honyAG/Qvh
P8aLrcSjWLFOuw5PuhYLZ/1hP/3XFfWliWX3dhKuoTKxrYsVxQnDdmLNlvrpv376+1VG+0TL
d+ZLcRZOFVP/jzpt+65MzvH+meEPFynHJtg2fcaLlzM39dkYV4sN9Rd16u7DfWJwds/R99zU
d5WM9mmpvYTTsH/6v6eAXd2Wl0RK4mXOw0d4M9k9XfjU4cKhl8SW6XSRgBbdSPdhryR8do6+
M/FLjfapSdYPIhs/IF3fnUN2t76llddFhr1ELPWRNZ7fUpRRFogl2ju4S8TJ7tQcNtTkpSRw
t3763SlqOVkcmeTcmq5HikH9DTvXeG6UOL+vjJofJ3lz+rGrl/KUZpQo+l2UZCxUvIYFdhGn
HO+Jyl8Wj4m3m8WpyaD9yu71pHuLxCBUJoMjhO86Xd/606/p2Stqm98vTyc5P+FxcXjQgyPE
pnuc2t/7b25Pgq6t0efVpCSLGUnG1hX3DxP5Tkk48Hl4VuQ+9wunW8kIy5fMQI+MBos95hUi
LXlCROEFYpaXRIrxsUiHTpZxjjcsdVomsttqfCky6CzmiEHIeisbill2lCin1DpQ3CoZv1S+
RLcoXdgA+4qKxvyk92dR1egTpCakxl+EoyxniBjt8zKUjU7t8xtgOLGVKKm9vJtBFw62fLAq
K6yIJG6pWL97ld3fMT00JUP4viJMZ7XXy0lJX7Ujq1YwRHYNH+HQlojwe7FwqOeJyDY445nR
4hcejeISMUjHNlBmw9ldnM6WROn1OdUdbLO4WXMPOBvGajgDh2j9L0YeFr6xyMHB/4bX0qft
dPJb2kjkU22nUwdpmNjS5K2ANpVOHaSx6e/CtlqR6NRB6q0GfN5WKxKdOkhjRF72TLsNgb8A
ty4jMPtjABcAAAAASUVORK5CYII=
--------------23D230D7EC054D3C0400003D--
--------------FDF0BDD9D801D2021DF35CA1--
--===============4591603692404225328==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline