redesign of TensorView

[evaleev]

Discussion items:

1) do we need to support views with value_type != storage::value_type, i.e. TensorView<T,Range,Storage> where T != Storage::value_type?

2) proposed change: TensorView<T,Range,Storage> -> TensorView<T,Range,StorageIterator> (or, perhaps TensorView<T,StorageIterator,Range>)

rationale for item 2 to follow.

p.s. To explore the latter I re-engineered TensorView on my fork (evaleev/BTAS).

[justusc]

I do not think it makes sense to have a tensor view where the value_type does not match that of the base tensor. The name implies that it is a subsection of another tensor. I think it would be surprising if the types did not match. In addition, changing the type of elements could have significant performance impacts that are not obvious to the user.

A better approach would be a type conversion constructor and assignment operator for tensor and a type conversion assignment operator for tensor view. These operations would only be valid if the value_type of the argument is implicitly convertible to the value_type of the destination object. This would make it more obvious to the user that a type conversion is being used and make them aware of the possible performance impact.

[shiozaki]

Ed - can you spell out 2) with escape sequences for < and >?

[emstoudenmire]

Just for the sake of argument, one case for a TensorView with a different value_type from its storage could be the real part (or imaginary part) of a Tensorstd::complex. Then one could work with the real/imag part without copying the underlying Tensor. This is probably more complicated than we want to go, because the TensorView would have to know to call .real() or .imag() when accessing a storage element (could this be handled by the policy template argument already in place?).

[justusc]

@emstoudenmire This is an excellent use case example. However, there will probably be use cases where this will work as expected and other use cases were a copy is required (e.g. anything that involves a BLAS call). Also, the performance of such an object would be lower due to increased memory bandwidth demands, relative to a tensor of simple doubles. If you only use the real/imag tensor view once, then the performance of the view you described is probably better than a copy. On the other hand, if you use a real/imag tensor view many times inside a loop, then it is probably faster to use a copy. Again, I think these performance differences may be surprising to users, and thus undesirable.

If you really want an non-uniformly typed tensor view, one possibility is to provide another object that supports different types in the view. This way the type of the object makes the difference obvious to the user, and they can expect a certain level of performance from a uniformly typed tensor view and a different level of performance for a non-uniformly typed tensor view. Furthermore, it makes it easier for users to understand argument requirements. This also makes it easier selection optimized vs general algorithms at compile time.

Another option, is to use a transform iterator in your algorithm where you require only the real/imaginary components. This avoids the need to have a separate object and allows view to use a uniform value_type. Here again, the user should expect a different level of performance when using a transform iterator vs a tensor view.

Of course I am making the assumption that the inner index of your tensor view has unit-stride memory access. If that is not true then, the performance difference would likely be close to zero.

[shiozaki]

@justusc My application is often memory-limited (so at least I insist that BTAS should support both copying and no-copying solutions), and what Miles wrote is very useful for BAGEL's relativistic code.

[shiozaki]

@evaleev What is the consequence of this change 2 (other than internal implementation and typename of the views)?

[evaleev]

Some background: TensorView's template params look like params of Tensor due to historical reasons. I tried to design TensorView as a Tensor (potentially completely merging the two; the main two differences between the two is ownership of data and how iteration over data happens).

For Tensor there is no need to differentiate between the value_type of Storage and value_type of Tensor. The reason Tensor<T,Range,Storage> uses T is for syntactic convenience, so that Range and Storage can be deduced (e.g. to make Tensor possible). We can/should use template alias to eliminate T: rename Tensor<T,Range,Storage> to BaseTensor<Storage,Range> and define Tensor = BaseTensor<default_storage, default_range>.

One can imagine reasons for TensorView::value_type to be different from Storage::value_type (type-mutating views): see @emstoudenmire 's comment above. See also comments by @justusc . The performance issues in my opinion go both ways: positive (no need to copy memory just to view its elements as different type) and negative (conversion is not free; not possible to implement most useful algorithms efficiently, even if the view is contiguous). The biggest issues are two: 1) maintenance/programming cost: type-mutating views must be handled as a special case of TensorView since they must be const and moreover the type systems says that for example TensorView::operator() for a type-mutating view must return T, not const T& (see the code). 2) little composable value: iterator adaptor/transform pattern is better suited for providing composable ways to process elements.

[shiozaki]

@evaleev Just as a side note on the use of aliases, they make explicit instantiation ugly at the user side as one cannot use aliases. I can live with it, but it should be noted explicitly in the document.

[emstoudenmire]

Even though I suggested that real/imag part use case, I'm in favor of assuming TensorView value_type is the same as that of storage. Having simple components that can be composed is ideal for keeping the code maintainable and making the costs clear to the user.

[emstoudenmire]

About proposal (2) to change the template argument to StorageIterator: based on the current implementation of TensorView this seems like an ok thing to do because the only methods referring to storage_ are the element access methods. (Only change I see is having to get rid of the storage() accessor.)

[evaleev]

On item 2: change in parametrization from Storage to StorageIterator.

The driving force for this is design improvement that allows to define concepts more correctly and precisely. The existing design does everything needed, but with somewhat painful/ugly details.

To refresh: currently TensorView is parametrized by Storage. To construct it one must provide a reference (const or non-const) to Storage. TensorView holds the reference using std::reference_wrapper. Having the reference allows for TensorView to provide TensorView::storage(), and other attributed that Tensor has. This is the reason why Tensor and TensorView both pass btas::is_boxtensor concept check.

There were problems with this design. Storage is a sequence container type, but I wanted to be able to create TensorViews into data specified by a pointer. Hence need to wrap pointers into sequence proxies, etc. I realized that a lot of ugliness goes away if we parametrize by StorageIterator directly. The only requirement on the iterator is that it must be random-access (see for example http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators). This type of design has been suggested before, by @naokin and perhaps others, to solve the common base problem that in the end was not pursued. This solution has pros and cons, and some changes can be viewed as either ...

"+" 1) Much cleaner/more correct design overall. No need for acrobatics with referencewrapper. TensorMap is TensorView<T,Range,T>, not TensorView<T,Range,sequenceadapter<T>>. Easier to explain the requirements on StorageIterator to be usable by TensorView than the corresponding subset of requirements of Storage. 2) No space or performance overhead (in fact one less indirection to get begin storage iterator). 3) util/sequence_adaptor.h is gone

"~" 1) TensorView will not meet the current BoxTensor concept spec because it does not have storage_type, not ::storage() method. I think many design issues we have run into and will run into are complicated by trying to write generic code that can handle Tensors and TensorViews. Some operations, such as printing, can be supported (they are both sequence containers after all), but more complex operations must distinguish the two types anyway. 2) make_view, make_cview, and make_rwview can be mostly left alone i.e. they can still access storage objects, not the iterators. Perhaps cleaner, however, to require them to take iterators, i.e. instead of auto t0v = make_view(tensor.range(), tensor.storage()); do auto t0v = make_view(tensor.range(), tensor.cbegin()); NOT SURE. 3) must implement std::iterator_traits in order to work.

"-" 1) current design works, hence this is more work (but much of it is done). 2) Less sanity checking: TensorView::at() methods cannot check that ordinal values are within storage bounds. 3) Some acrobatics required to work around the type system ... for example, there is no robust way to convert const_iterator to iterator (types or objects) without having access to the container.

The most serious change I see is "~".1, i.e. that TensorView no longer meets same concept as Tensor. We can introduce a weaker concept spec that covers both Tensor and TensorView. My guess is that this is actually a plus long term, but a bit painful now.

Thoughts?

[evaleev]

while at this: thoughts on renaming btas::TensorView -> btas::View?

[emstoudenmire]

Maybe ~1 is not such a concern, because if I recall correctly, isn't the concept spec really geared around a dense tensor with contiguous-in-memory elements? It makes sense to me for there to be a heirarchy of specifications, with increasingly strict requirements, similar to how a random-access iterator is also a forward iterator etc.

I like TensorView better than just View because TensorView is more self-documenting.

[evaleev]

I agree. I think it makes sense to make TWG.Tensor a refinement of TWG.TensorView. Tensor can always be considered a TensorView, but not the other way around.

BTW, as of now the TWG.Tensor concept spec does not say anything about the data layout since that's hidden in storage, and TWG.Storage is not explained at all (see #50 ; this issue started when I tried to address #50). We can only suggest that Storage should be contiguous, but as long as the user provides a container with random-access iterators Tensor will work ... perhaps not efficiently. Of course concept checks is_boxtensor and is_tensor can't check efficiency even if the spec says something about it.

[shiozaki]

I think as long as a weaker concept that include both Tensor and TensorView and associated traits are provided and there is no side effect, I am fine with the new design (because my TensorViews are dense, and I want to use them on a same footing).

Perhaps not efficiently

What do you exactly mean? (my brain is not functioning now)

[evaleev]

Perhaps not efficiently

What do you exactly mean? (my brain is not functioning now)

The user could provide a Storage type whose iterator is random-access, but access cost is not O(1), but O(logN) (e.g. a std::map) or some stupid implementation with O(N) cost.

random but related rant: An interesting question is how to store the data of an element-sparse tensor. I don't think the current design will allow is since we are assuming container semantics of Storage, hence even if element is 0 we have to be able to return reference to it.

— Reply to this email directly or view it on GitHub https://github.com/BTAS/BTAS/issues/68#issuecomment-50684995.

web: valeyev.net

[evaleev]

Closing #68 without merging in the proposed (and implemented) changes (for the posterity see branch view_using_storageiterator)

the rationale for sticking with View< ... Storage> in favor of View< ... StorageIterator>: 1) type system (i.e. getting from StorageIterator to StorageConstIterator is impossible without doing non-portable things) 2) efficiency (StorageIterator does not provide same level of insight that Storage does to be able to optimize things)