Open daniel-vainsencher opened 8 years ago
Thanks a lot for all your feedback. I'll try to answer each point and open an individual issue for those that can be quickly addressed. I think we can have the discussion as issues here, since it's a good way to keep track of each individual point.
zeros, ones etc ask for StorageOrder, and default to C if given Unordered. Having to always specify order is a pretty serious inconvenience, I would much prefer the library chooses a default that allows me to not pass StorageOrder at all.
Put in issue #2
in fn strides why not return &DimArray? anyone else can clone, so no need for strides_ref that I see. Same for fn shape. Probably missing a subtlety.
There is fn strides_ref() to get a reference. But probably this feels weird. Do you have any naming idea for the reverse approach (ie strides() returns a reference, the other for a copy?)
ordering returns F,C even if inner_stride is not 1, so that data is not contiguous, that is pretty surprising to me.
Here I think we have two overlapping informations. Maybe an fn is_contiguous() should return one if the inner_stride is 1, because some algorithms want to know if we're in C or F order to choose the most efficient path, even without contiguous data. An other solution would be to have a more detailed enum for ordering. Let's continue that discussion in issue #3.
outer_block_iter is an interesting choice of iterator to have. I think the block_size=1 version whose items are of order smaller by one is the important one, so we can have nested loops that eventually consider elements. The general case is iter_subarrays(along: Axis), I think.
outer_block_iter is mainly there for products implementations, as it's always more cache-friendly to perform matrix products blockwise. But clearly users would need some friendlier API, like your proposed iter_subarrays. That was one of the features I was planning to add soon (I landed a slice_dim(axis: Axis, index: usize) yesterday that will enable that iterator).
data_index does not do the bounds checking. I'm not saying that is suboptimal, but I wonder.
I don't know whether it's the proper place to perform bounds checking, it does not actually access the data array. I think the out of bounds access needs to either happen later when actually indexing the data sllce, or earlier when this method is used to compute an index for unsafe unchecked indexing.
rows stands for number of rows, but could also stand for an iterator over rows or the Range of legal row indices (with the number as n_rows etc). I think we should prefer the language of the API to use higher level objects than usize as often as possible.
Good point for the naming, I feel there are 3 possible naming strategies:
Using arrays as indices is a bit of a pain in the butt: let first = myarr[vec!(0,0,0)]; is kind of unwieldy. Wish Rust had nicer array syntax, but have to admit the bar of being about as lightweight as [] is high. Of course the matrix and vector special cases can be provided with 2-tuple and number instances of Index mostly solving the problem.
Actually indexing looks like:
let first = myarr[[0,0,0]];
Getting a tuple instead of an array would mean the same amount of typing, but perhaps a nicer readability.
I think that supporting generally strided tensors is very important for interoperability with external ecosystem including numpy. That said, in my usage I expect the contiguous dimension to be part of the type, so that I know that my innermost loops are cache friendly. If we have such types, we can simply convert to them (testing the stride and returning None if incompatible, and creating a contiguous copy are both reasonable options).
Good point, though I don't know yet how to include it in the type. If possible I'd like to have such information as some kind of phantom data marker. Let's discuss that some more in issue #4.
This returns us to the question of writing algorithms abstractly over (most aspects of) tensor representation. I wonder if we need something like IntoTensor and FromTensor (as in IntoIterator, FromIterator), which allows a thing to be accessed with an appropriately sized array. Then binops can be implemented once in terms of IntoTensor, with return value organization determined externally. I am guessing the following: let c: RowMajorMatrix = a + b;
While this looks appealing as a feature, I can't figure out yet how this would work in practice. Though from an API point of view I think it will need to look like
let c: RowMajorMatrix = (a + b).collect();
as it seems to be needed in std.
For general strided arrays, it seems natural to provide also Index<(usize,Axis)> and iter_subarrays(along: Axis).
Yes definitely needed. Issue tracked as #5
let first = myarr[[0,0,0]];
Really! cool. I guess that's a static Array. Been using slices and Vec's but mostly forgot about those. Given this, not at all sure a tuple is better, might be better to reserve tuples for other uses.
About .collect(), I think this is a very reasonable level of explicitness for a layout change, as long as a mere + (defined directly, not through IntoTensor) is enough when layouts are consistent. I wouldn't call it collect in this case, maybe re_layout() or something like that, to make clear that we are preserving more than just the contents.
Just sketching a trait for it:
trait FromTensor { fn index(DimArray) -> N; fn main_dimension -> Axis; }
The first allows us to completely ignore representation, by just accessing what we need. The second tells us that if some dimension needs to be the inner loop, this structure prefers to use this one (I am guessing that's the most significant hint, performance-wise). Then if both structures agree on the dimension, we make sure to use it, if they disagree its not obvious what to do (panic, log a warning, just do with some heuristic about accepting the dimension requested by the larger structure).
Ok, talk more later.
That's indeed a static array. In fact the whole Tensor type is based on static arrays, which makes it possible to statically know the tensor dimension.
And I start seeing how this IntoTensor feature would work. However I wonder if it would not be simpler to ask for C-order iteration, F-order iteration, and a preferred way of iteration? That would avoid all these bounds checking from repeated Index calls. And I suppose C and F ordering are the most common so that would be quite generic.
About arrays everywhere: yeah, got that by now, my mind had glossed over it before :)
About C, F, preferred iterators: I guess you mean as the basis for FromTensor? Asking for iterators is probably going to be more efficient, yes. OTOH (and this seems a global design issue) I am not sure it is reasonable for tensors (as opposed to matrices) to give special considerations to the first and second Axes. In principle, any of the axes could be the "most contiguous".
So maybe the requirements should be:
and then the algorithm is to use as much of the preferred ordering as they agree on (hopefully at least the fastest changing axis is agreed).
Speaking of bounds checking, how about we open an issue for smart index types? I'm not at all sure what the best design is for those, but I am fighting plenty of bugs that those could prevent, and I don't like the unwraps littered in my code.
On Mon, Sep 21, 2015 at 12:32 PM, Vincent Barrielle < notifications@github.com> wrote:
That's indeed a static array. In fact the whole Tensor type is based on static arrays, which makes it possible to statically know the tensor dimension.
And I start seeing how this IntoTensor feature would work. However I wonder if it would not be simpler to ask for C-order iteration, F-order iteration, and a preferred way of iteration? That would avoid all these bounds checking from repeated Index calls. And I suppose C and F ordering are the most common so that would be quite generic.
— Reply to this email directly or view it on GitHub https://github.com/vbarrielle/dense_mats/issues/1#issuecomment-142035949 .
Daniel Vainsencher
I am not sure it is reasonable for tensors (as opposed to matrices) to give special considerations to the first and second Axes. In principle, any of the axes could be the "most contiguous".
Looks like I'm mistaken in my definition of C order / F order. To me it was related to the ordering of the strides, not only to the location of the fastest varying dimension. But after reading some numpy references it looks like I was assuming too much. I think a preferred iteration order would be a nice API.
Speaking of bounds checking, how about we open an issue for smart index types? I'm not at all sure what the best design is for those, but I am fighting plenty of bugs that those could prevent, and I don't like the unwraps littered in my code.
I'm not sure we can get much benefits with smart index types. The way I see it, a smart index would mean that it's statically guaranteed to be in bounds for a given array, but I don't see how rust's type system could reflect that.
Smart index types: what do you think about something like [1]? that's on a Vec, I am deferring Tensors for complexity budget management purposes. Using the right types does not statically prove lack of bounds errors, but it does make those as well as 'merely' using the wrong kind of index, extremely unlikely. There is a weird technical issue where currently the Range there is non-copyable despite deriving Copy, please ignore that, I'm sure we can fix that somehow.
[1] https://play.rust-lang.org/?gist=a88ee7f64b3efb38bb90&version=stable
I see, this enables distinction between different "kinds" of indexes. That's a nice feature indeed, but I think there would need to be an easy path for people not wanting to use it as it is quite verbose (though very useful I guess on complicated code).
As for your Copy derivation not working, it's probably because the T
in struct Range<T>
is not Copy, it should probably be added as a bound on the struct definition. OTOH I don't think that would work, because your implementation relies on the compiler creating a newtype for each ||()
closure, but I don't think these closures are copy.
I certainly agree that tensors indexed by simple number should also be easily available. The point is that identified indices (still fishing for the right terminology...) should be first class citizens, and I think they can be almost as concise as the usual types. Some ideas in this direction:
One interaction with tensors is that then indices might have to be tuples instead of arrays, since the different indices are (potentially) not of the same type. You would know better than me how much trouble that might be.
Ok, worked around the closure ownership issues with Rc Range, which makes reasonable sense to me.
https://play.rust-lang.org/?gist=e0d8f43562b6ae14f594&version=stable
A couple of important improvements:
https://play.rust-lang.org/?gist=385ccc07836f5428244a&version=stable
Ha! removed the Rc hack by fixing the Copy with a manual implementation. Sorry about the noise. Now I'm reasonably happy with the basic abstractions. What do you think? detailed criticism welcome.
https://play.rust-lang.org/?gist=b22fdd0a025447d7b664&version=stable
Yes it looks better without the Rc.
My thoughts on it:
I agree the main question is the price of the marker types. I think we need to experiment with those carefully, this is one of the reasons I am developing the examples right along with the implementation; if the API is too ugly it won't be used. BTW, I think we should add examples to dense_mats also sometime soon, to keep track of how features interact in use.
For zeros, I added that functionality in [1]. That use seems pretty close to optimal. Note that in the approach I'm proposing, almost none of the APIs will actually specify the tags explicitly. So we would have signatures like
fn read_samples_from_file(fn: &str) -> RangedVec<T>
not
fn read_samples_from_file(fn: &str) -> RangedVec<sample_index>
as we might in an approach where the usize-wrappers are user defined. There is less documentation, but maybe it will be less verbose. Where else could the markers be too annoying?
For matrix, this would be something like
fn read_samples_from_file(fn: &str) -> RangedVec<M,N>
and for Tensors it might get even more hairy, but I haven't put too much thought into how this can fit with Tensors. I'm not sure in merging this with your design, whether there would be multiple type parameters or just one array/tuple parameter. Any thoughts?
[1] https://play.rust-lang.org/?gist=4135d7ce4f1663380609&version=stable
On Wed, Sep 23, 2015 at 12:54 PM, Vincent Barrielle < notifications@github.com> wrote:
Yes it looks better without the Rc.
My thoughts on it:
- I find the examples quite nice
- I'd like to see how this can mix up with normal indexing, maybe something like the default constructor for the tensor defaults to a static index set, and there's a special constructor if you want.
- however, I'm a bit scared by the implications of the marker types, basically this type has to exist for everyone, and makes type annotations more annoying when they're needed (and they are needed when eg calling zeros() or ones() or eye() because there's no data to infer the type from).
— Reply to this email directly or view it on GitHub https://github.com/vbarrielle/dense_mats/issues/1#issuecomment-142660838 .
Daniel Vainsencher
It's been enlightening to peek at this discussion. :smile:
I'm mixing multiple issues here for discussion, we can break out things that need real change and close this later. We can move a discussion elsewhere, like the subreddit, as you wish.
zeros, ones etc ask for StorageOrder, and default to C if given Unordered. Having to always specify order is a pretty serious inconvenience, I would much prefer the library chooses a default that allows me to not pass StorageOrder at all.
in fn strides why not return &DimArray? anyone else can clone, so no need for strides_ref that I see. Same for fn shape. Probably missing a subtlety.
ordering returns F,C even if inner_stride is not 1, so that data is not contiguous, that is pretty surprising to me.
outer_block_iter is an interesting choice of iterator to have. I think the block_size=1 version whose items are of order smaller by one is the important one, so we can have nested loops that eventually consider elements. The general case is iter_subarrays(along: Axis), I think.
data_index does not do the bounds checking. I'm not saying that is suboptimal, but I wonder.
rows stands for number of rows, but could also stand for an iterator over rows or the Range of legal row indices (with the number as n_rows etc). I think we should prefer the language of the API to use higher level objects than usize as often as possible.
Anyway, this is clearly a sketch, most of the above will get fixed while adding stuff to flesh it out. Some larger issues:
Using arrays as indices is a bit of a pain in the butt:
let first = myarr[vec!(0,0,0)];
is kind of unwieldy. Wish Rust had nicer array syntax, but have to admit the bar of being about as lightweight as [] is high. Of course the matrix and vector special cases can be provided with 2-tuple and number instances of Index mostly solving the problem.
This returns us to the question of writing algorithms abstractly over (most aspects of) tensor representation. I wonder if we need something like IntoTensor and FromTensor (as in IntoIterator, FromIterator), which allows a thing to be accessed with an appropriately sized array. Then binops can be implemented once in terms of IntoTensor, with return value organization determined externally. I am guessing the following:
let c: RowMajorMatrix = a + b;
can be made to work even when a, b, c have different organizations, and efficiently when they do.