On Sunday, 3 September 2017 at 14:19:19 UTC, Ilya Yaroshenko
wrote:
On Sunday, 3 September 2017 at 12:35:16 UTC, Moritz Maxeiner
wrote:
On Sunday, 3 September 2017 at 09:24:03 UTC, Ilya Yaroshenko
wrote:
On Sunday, 3 September 2017 at 02:43:51 UTC, Moritz Maxeiner
wrote:
On Sunday, 3 September 2017 at 02:08:20 UTC, Ilya Yaroshenko
wrote:
On Tuesday, 29 August 2017 at 12:50:08 UTC, Robert M. Münch
wrote:
Maybe of interest:
https://www.think-cell.com/en/career/talks/iterators/#1
I haven't read everything, so not sure if it worth to take
a look.
Iterators has no proper alternative when one need to
implement generic tensor library like Mir Algorithm [1].
Out of curiosity: Could you elaborate on what the issues are
with using a range based API internally (if it's
performance, the "why")?
There are three general kinds of dynamic dense tensors. Mir
implements all of them:
1. Contiguous tensors. Their data is located contiguously in
memory. Single dense memory chunk. All strides between
subs-tensors can be computed from lengths.
2. Canonical tensors. Only data for one dimension is dense,
other dimensions has strides that can not be computed from
lengths. BLAS matrixes are canonical tensors: they have two
lengths and one stride.
3. Universal tensors. Each dimension has a stride. Numpy
ndarrays are universal tensors.
Finite random access range Issues:
1. Main API issue is that full featured random access range
(RAR) API (with slicing, and all opIndex* operators like
`[]*=` ) is much larger comparing with unbounded random
access iterator (the same API as pointer).
Won't you have to implement opIndex* operators either way in
order to use the `a[]` syntax? The main difference I can see
should be that you'd also have to implement the InputRange
(front,popFront,empty), ForwardRange (save), and
BidirectionalRange (back,popBack) members, which if you don't
need them, is indeed understandably too much?
front,
popFront,
empty,
save,
back,
popBack,
opIndexOpAssign,
2 x opIndex(.opSlice) for rhs scalars and ranges
2 x opIndexAssign(.opSlice) for rhs scalars and ranges
2 x opIndexOpAssign(.opSlice) for rhs scalars and ranges
Plus, because of range topology slicing may be slower good to
add this ones:
popFrontN
popFrontExactly,
popBackN
popBackExactly,
and maybe i forgot something ...
Didn't know about the *N *Exactly ones, but yeah, it's a lot.
Though unless you aren't interesting in the `a[]` syntax, you
can't avoid opIndex*.
2. Random access range holds its length. Yes, Phobos has
infinity ranges (mir hasn't), but the practice is that almost
any RAR constructed using Phobos has length and you can not
strip when type is constructed. Anyway, infinity RAR is just
a pointer/iterator that can move forward but can not move
backward. Tensors hold their own lengths for each dimensions,
so range's length is just a useless payload.
I'm not sure what you mean here. Is this still about accessing
the elements of one tensor? If so, what do Phobos' ranges have
to do with your tensor type's API?
ndslice is:
1. Slice structure with a huge amount of features from mir
algorithm
2. multidimensional RAR: .front!0, front!1, .front!(N - 1) and
all other generalized RAR primitves including multidimensional
index [1, 2, 3, ...] and slicing [1 .. 4, 3 .. $].
3. Common one dimensional RAR on top of outer most dimension.
So one can use Phobos funcitons for Slice structure. For
example, a matrix will be iterated row-by-row.
But this paragraph was about another issue:
struct BLASMatrixTypeBasedOnRanges
{
double[] _data; // arrays is the simplest RAR
size_t rows, cols;
size_t stride;
}
Now I get what you mean, you were talking about not using the
dynamic arrays built into the language (which indeed carry their
length for safety purposes), not about exposing range API here;
you're right, you don't need to use a dynamic array here, as you
already have the length encoded another way (it would be
wasteful), but strictly speaking D's builtin dynamic arrays are
not ranges (as they are neither aggregate types nor do they have
the range functions baked into the language). They only become
ranges when you import the appropriate free functions from Phobos
(or define some yourself).
sizeof(YourBLASMatrixTypeBasedOnRanges) == size_t.sizeof * 5;
in other hand:
sizeof(Slice!(Canonical, [2], double*)) == size_t.sizeof * 4;
Ranges requires for 25% more space for canonical matrixes then
iterators.
We do have to differentiate between a container and the API with
which to iterate over its elements.
D's dynamic arrays (a pointer+length) require more space then
using only a raw pointer, of course. If that's more than an
iterator depends on the type of iterator you use. Most common
iterator implementations I know consist of a begin and an end
pointer, essentially requiring the same space as D's dynamic
arrays.
In the case you describe, though, we aren't talking about the
iteration API, we are talking about what's used internally for
storage.