Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

P1385 A proposal to add linear algebra support to the C++ standard library #169

Open
jensmaurer opened this issue Jan 26, 2019 · 12 comments
Open

Comments

@jensmaurer
Copy link
Member

@jensmaurer jensmaurer commented Jan 26, 2019

P1385R0 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Mar 20, 2019

P1385R1 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@wg21bot wg21bot removed this from the 2019-02 milestone Mar 20, 2019
@wg21bot wg21bot added this to the 2019-07 milestone Mar 20, 2019
@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Jun 23, 2019

P1385R2 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Jul 12, 2019

Kona 2019-02 LEWGI Minutes

P1385R1 Linear Algebra

Champion: Bob Steagall

Minute Taker: Davis Herring

Start Overview: 14:00

Break: 15:00

Resume after Break: 15:15

Start Polling: 16:20

POLL: We want 0-based indexing as opposed to 1-based indexing.

NO OBJECTION TO UNANIMOUS CONSENT

Attendance: 20

POLL: We like having separate row_vector and column_vector types in addition to matrix.

Strongly For Weakly For Neutral Weakly Against Strongly Against
3 0 5 4 4

Attendance: 21

That has no consensus.

POLL: We want explicitly named operations (e.g. dot, outer) in addition to operators.

Strongly For Weakly For Neutral Weakly Against Strongly Against
8 5 2 1 0

Attendance: 21

That has consensus.

POLL: Define engine/matrix classes in terms of mdspan + storage and mdspan concepts (e.g. extents), and expose an mdspan-esque interface. This implies that fs_ and dyn_ are combined into one template parameterized on extents (which are either static or dynamic).

Strongly For Weakly For Neutral Weakly Against Strongly Against
6 2 7 0 0

Attendance: 22

That has strong consensus.

End: 16:30

@jensmaurer
Copy link
Member Author

@jensmaurer jensmaurer commented Aug 26, 2019

@jensmaurer jensmaurer removed this from the 2019-07 milestone Aug 26, 2019
@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Oct 15, 2019

P1385R3 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@wg21bot wg21bot added this to the 2019-11 milestone Oct 15, 2019
@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Nov 8, 2019

Kona 2019-02 LEWGI Minutes

POLL: We want explicitly named operations (e.g. dot, outer) in addition to operators.

Strongly For Weakly For Neutral Weakly Against Strongly Against
8 5 2 1 0
Attendance: 21

That has consensus.

POLL: Define engine/matrix classes in terms of mdspan + storage and mdspan concepts (e.g. extents), and expose an mdspan-esque interface. This implies that fs_ and dyn_ are combined into one template parameterized on extents (which are either static or dynamic).

Strongly For Weakly For Neutral Weakly Against Strongly Against
6 2 7 0 0
Attendance: 22

That has strong consensus.

End: 16:30

The above two pieces of guidance seem to not have been addressed. Please address them in the next revision of the paper.

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Nov 8, 2019

Belfast 2019-11 LEWGI Minutes

P1385R3 DSL Linear Algebra Library: Design Review

Chair: Bryce Adelstein Lelbach

Champion: Bob Steagall

Minute Taker: Mark Hoemmen

Start Review: 11-06 16:09

POLL: We want to be able to modify elements through matrix_*_views (similar to span).

Strongly For Weakly For Neutral Weakly Against Strongly Against
8 8 0 0 0

Attendance: 20

This has unanimous consent.

POLL: For matrix types with overloaded operators, we are comfortable with supporting hooks for expression templates but having no expression templates by default in the standard library.

Strongly For Weakly For Neutral Weakly Against Strongly Against
2 4 4 2 0

Attendance: 21

POLL: Given what we've seen so far, we are comfortable with the customization mechanisms for overloaded operators on matrices.

Strongly For Weakly For Neutral Weakly Against Strongly Against
2 4 7 0 2

Attendance: 21

End: 17:40

Kona 2019-02 LEWGI Minutes

POLL: We want explicitly named operations (e.g. dot, outer) in addition to operators.

Strongly For Weakly For Neutral Weakly Against Strongly Against
8 5 2 1 0
Attendance: 21

That has consensus.

POLL: Define engine/matrix classes in terms of mdspan + storage and mdspan concepts (e.g. extents), and expose an mdspan-esque interface. This implies that fs_ and dyn_ are combined into one template parameterized on extents (which are either static or dynamic).

Strongly For Weakly For Neutral Weakly Against Strongly Against
6 2 7 0 0
Attendance: 22

That has strong consensus.

End: 16:30

CONSENSUS: Bring a revision of P1385R3 (a proposal to add linear algebra support to the C++ standard library), with the guidance below, to LEWGI for further design review.

  • These pieces of guidance from Kona (see polls above) have seem to not have been addressed. Please address them in the next revision of the paper.
    • Define engine/matrix classes in terms of mdspan + storage and mdspan concepts (e.g. extents), and expose an mdspan-esque interface. This implies that fs_ and dyn_ are combined into one template parameterized on extents (which are either static or dynamic).
    • Add explicitly named operations (e.g. dot, outer) in addition to operators.
  • Ask SG6 to formulate a precise definition of is_field, is_nc_ring and is_ring, and consider what the answers should be for builtin types (e.g. signed integers, unsigned integers, and floating point types).
  • Make numeric_traits non-implementation-defined; for non-builtin/non-std types, assume the properties are false.
  • Separate is_complex or is_specialization_of into a separate paper.
  • Remove the numeric_traits helper traits (is_field, is_nc_ring, etc).
  • Make matrix_*_view's copy constructor and copy assignment methods noexcept.
  • Add non-const begin and end to matrix_*_view.
  • Remove assign method from matrix_*_view.
  • Provide a way to modify elements through matrix_*_view types: one option is to add matrix_*_ref types that allow modification of the underlying elements.
  • Explore adding a submatrix view.
  • Make index_type ptrdiff_t and size_type size_t.
  • Develop a clear plan for is_rectangular == false.
  • Add data to engine types.
  • is_fixed_size and is_resizable are inverses of each other; explore combining.
  • Explore different designs for numeric_traits: either looking for embedded type aliases in the classes instead of a trait, or granular traits a la P1370.

@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Dec 11, 2019

P1385R4 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@wg21bot wg21bot removed this from the 2019-11 milestone Dec 11, 2019
@wg21bot wg21bot added this to the 2020-02 milestone Dec 11, 2019
@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Jan 18, 2020

P1385R5 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Feb 18, 2020

Prague 2020-02 LEWGI Minutes

D1385R6 DSL Linear Algebra Library: Design Review

Chair: Bryce Adelstein Lelbach

Champion: Bob Steagall

Minute Taker: Ben Craig

Start Review: 2020-02-11 11:01

Do we really need this feature to support user defined engines? This is an open extensible system; those are harder to build.

In the past we've said to just define matrix/engines in terms of mdspan, and not have fixed size and dynamic owning engines; what we have now is the addition of view matrix/engines, but we still have the fixed size and dynamic owning engines.

Are we okay with using operator overloading for matrix operations, given that what operators map to may be ambiguous (for example operator*).

Look at the relationship between mdarray and mdspan; that's the relationship that the fixed sized/dynamic owning matrix/engines and the view matrix/engines should have.

Do the customization mechanisms make it possible for some matrix/engine systems to define operator*(std::math::vector, std::math::vector) as inner_product and others to define it as outer_product? Answer: Yes

Is this true for all the overloaded operators in this proposal? Answer: Yes

Can we add the overloaded operators in a "version 2" if we don't include them in "version 1"? Answer: Maybe? (but if users add their own overloads, it would break them)

POLL: We want operator*(std::math::vector, std::math::vector) in the standard library, even though some believe it is ambiguous.

Strongly For Weakly For Neutral Weakly Against Strongly Against
5 6 2 1 6

Attendance: 25

# of Authors: 2

Author Position: SF

That has no consensus.

POLL: We want operator*(matrix, vector) and operator*(matrix, matrix) in the standard library even if we won't have operator*(vector, vector).

Strongly For Weakly For Neutral Weakly Against Strongly Against
10 4 2 3 2

Attendance: 25

# of Authors: 2

Author Position: SF

That has consensus.

POLL: We want overloaded operators (e.g. operator*, operator+, etc) for matrix/vector operations in the standard library.

Strongly For Weakly For Neutral Weakly Against Strongly Against
10 4 3 2 2

Attendance: 25

# of Authors: 2

Author Position: SF

That has consensus.

POLL: Assuming we have overloaded operators (e.g. operator*, operator+, etc) for matrix/vector operations in the standard library, we want their semantics to be customizable by users.

Strongly For Weakly For Neutral Weakly Against Strongly Against
5 4 8 1 3

Attendance: 25

# of Authors: 2

Author Position: SF

That has no consensus.

Areas for further LEWGI review:

  • Would we be okay with customization if customizations were required to have the same preconditions/postconditions/semantics (Walter's idea).
  • Should this be an open or closed system?
    • Discuss implications of a closed system on non-expression template operator overloading performance.
      • With a closed system, either we'd have to use expression templates, or we'd have performance issues with temporaries (a la std::valarray).
  • Non-expression template operator overloading temporaries performance impact.
  • mdspan/view usage.
  • Engine category mechanism.
    • Are iterator-style tag types the best way to do this?
    • The motivation for all this machinery is to allow people to write their own engine types?

End: 12:04

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Feb 18, 2020

Prague 2020-02 LEWGI Minutes

D1385R6 DSL Linear Algebra Library: Design Review

Chair: Bryce Adelstein Lelbach

Champion: Bob Steagall

Minute Taker: Ben Craig

Start Review: 2020-02-13 10:45

Areas for further LEWGI review:

  • Would we be okay with customization if customizations were required to have the same preconditions/postconditions/semantics (Walter's idea).
  • Should this be an open or closed system?
    • Discuss implications of a closed system on non-expression template operator overloading performance.
      • With a closed system, either we'd have to use expression templates, or we'd have performance issues with temporaries (a la std::valarray).
  • Non-expression template operator overloading temporaries performance impact.
  • mdspan/view usage.
  • Engine category mechanism.
    • Are iterator-style tag types the best way to do this?
    • The motivation for all this machinery is to allow people to write their own engine types?

Why is *_matrix_engine using a tuple<size_type, size_type> instead of mdspan's extents?

Are there any engines that are not initable? Answer: The views are not initable.

Should indexing/sizes be signed or unsigned? Answer: We shouldn't revisit this discussion. Continue with the std status quo of unsigned sizes/indexing + ssize (or whatever we're calling it now).

swap on engines should be noexcept.

Engines and matrices has span-style const propagation, not string_view-style const propagation.

Pick any word other than view.

Right now the paper uses initializer_list<initializer_list<>>; all of the inner initializer_lists must have the same size.

  • Can we always catch this at compile time?
  • Answer: Today, in the reference implementation, this is caught at compile time if the initializer is constant evaluated, otherwise its checked at run time.
  • Maybe use initializer_list<array<T, N>>

Dangling reference semantics with views: should we allow this, given it's a beginner interface?

Alternatives to having non-owning sub-views:

  • Just remove them.
  • Subviews share ownership (a la std::shared_ptr).
  • Subviews diagnosis when the owner is destroyed (a la std::weak_ptr / safe_range).

POLL: We are okay with only providing submatrices/slices with non-owning semantics in the first version we ship.

Strongly For Weakly For Neutral Weakly Against Strongly Against
8 4 2 2 0

Attendance: 17

# of Authors: 2

Author Position: SF

That has consensus.

Discuss names for this proposal on the LEWG mailing list before Varna.

Having members called t and h is probably not going to fly.

Explore whether the subvector selection functions should use first + length vs first + last; look at prior art and usage experience in the wild.

Should is_resizable be a constexpr function or a constexpr inline variable?

  • Look at library features in C++20 to try and determine the prior art/best practice now that we have inline variables.
  • constexpr functions are known to have a compile time performance impact over constepxr inline variables.
  • Change is_resizable to be a constexpr inline variable in the next revision.

Are iterator tags the right model to use for engine categories?

Challenges with iterator tags:

  • Difficult to extend later; may not be ABI stable.
  • Compile time performance issues.

Why not use concepts or named type requirements for engine categories?

Motivation for customization, instead of just focusing on a high-level simple interface that is not user-extensible.

Are the engine category tags convertible?

How would you write a function that takes a writeable matrix, but should also accept initable and resizable matrices? Can you write it to take any of those three, but not a readable? Answer: Not easily, not without some complicated SFINAE.

Gaspar volunteers to show the authors the use case for writing functions that accept different categories of matrices.

End: 12:02

CONSENSUS: Bring a revision of D1385R6 (DSL Linear Algebra Library), with the guidance below, to LEWGI for further design review.

  • Add further justification for why matrix operations need to be customizable by users; this should be a focus of the next discussion in an effort to increase consensus.
  • Remove operator*(std::math::vector, std::math::vector).
  • swap on engines should be noexcept.
  • Bikeshed "view" in this paper on the LEWG mailing list.
  • Bikeshed the t and h member functions on the LEWG mailing list.
  • Make is_resizable a constexpr inline variable instead of a constepxr static function.
  • Use extents instead of size_tuple.
  • Explore alternatives to initializer_list<initializer_list<>> that enforce that the dimensions of all the inner lists are identical (follow-up with Eric Fiselier).
  • Demonstrate and clarify how the engine categories work and how you could use them to write generic functions that accept matrices of certain categories (follow up with Gašper Ažman).

@jensmaurer jensmaurer removed this from the 2020-02 milestone Feb 18, 2020
@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Mar 24, 2020

P1385R6 A proposal to add linear algebra support to the C++ standard library (Guy Davidson, Bob Steagall)

@wg21bot wg21bot added this to the 2020-telecon milestone Mar 24, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
No open projects
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
@brycelelbach @jensmaurer @wg21bot and others