[swift-evolution] Basic element-wise operator set for Arrays, Arrays of Arrays, etc.

Mon Feb 20 17:41:08 CST 2017

> Once such a library were reasonably mature, it would be reasonable to
propose it for inclusion in swift proper. I expect this process will take a
couple *years*.

Yes, I do not expect this to come very quickly either but if no one gets
started, that is going to last for even longer ;-)

> or the cleaner, with a little sugar:
>
> zip3(A,B,C).map { 3 * $0.0 * $0.1 / ($0.2 ^ 4) }

OK I guess I should have put a few regular matrix multiplications in the
middle to prevent from having such relatively straightforward solutions
(the thread was originally of element-wise but we now are clearly talking
about way more than that). Anyway, it is not worth opening a debate on the
example.

> Well, count me as another +1 for adding a `CoreMath` library (although it
should probably be called something else, unless we can make it work in
Obj-C, too).

Well I was rather thinking of making a Swift-only library (at least at
first) but that would also be available for other platforms e.g Linux or
maybe some day on Windows => also working with reduced performance without
the Accelerator Framework but leveraging it on Apple Platforms (and
possibly leveraging others on the other platforms). This said I am open to
discussion on this... but having a very nice syntax for swift and having an
close to one-to-one equivalent also for Objective-C will probably add quite
some difficulties.

> Consider your example:
>
> 3.0 .* A .* B ./ (C.^ 4.0)
>
> with the most obvious implementation, this generates four calls to vector
functions:
>
> - multiply array by scalar (tmp0 <— 3 .* A)
> - elementwise multiplication (tmp1 <— tmp0 .* B)
> - elementwise exponentiation (tmp2 <— C .^ 4)
> - elementwise division (result <— tmp1 ./ tmp2)
>
> again, with the obvious implementation, this wastes space for temporaries
and results in extraneous passes through the data. It is often *possible*
to solve these issues (at least for some the most common cases) by
producing proxy objects that can fuse loops, but that gets very messy very
fast, and it’s ton of work to support all the interesting cases.

This is clear to me and to be honest with you I am not really sure of the
best strategy to make this.

I don't think that the primary target for the library should be to deliver
the highest performance possible.
  => People who do need that level of performance would still need to
analyze and optimize their code by themselves and/or directly call the
Acceleration Framework or other specialized libraries.

What I would like to reach instead is rather what I would call "the highest
usability possible with decent performance". Some programmers will be
satisfied with the level of performance and will enjoy the readability and
maintainability of the code based of the library, whereas other will go for
more performant libraries (and that is perfectly fine!). Actually, I would
even expect later that some of those who belong to the latter category will
start experimenting with the easy but less performant library (lets call it
here "easy maths library") and optimize their code based on a high
performance library only in a second step.

My idea of a possibly pragmatic roadmap (which can be followed in that
order) to make such a library almost from scratch with the long-term goal
of being quite performant but primarily very easy to use could be:

1) think about the integration to the language, the syntax, the high-level
user documentation, etc. and demonstrate all this based on a relatively low
performance implementation

2) generate a collection a typical operations where the low-level libraries
offer very nice performance or where a clever handling of the temporary
variables is possible

3) implement these cases as specialized functions

4) "somehow" (I am clearly not a compiler guy) teach the compiler how to
analyze a generic expression that is based the defined object to find (if
possible) some identical but more performant substitutes for the "dumb"
successive calls of each operator function causing the generation of all
these possibly unnecessary temporaries.

This roadmap and especially having point #1 at the beginning does not
really follow the citation made earlier in the discussion by Xiaodi Wu on
the _method_ proposed by the core team:
> "... And members of the core team have supported that idea. However, they
have stated that the _method_ to accomplish this is to actually implement a
math library, get people to use it, and then propose its integration."

The main advantage I see for the "easy maths" library as I would like to
propose/contribute to is the easiness of use through a well thought
integration to the swift language... I don't really see people adopting it
massively if it is neither very performant nor very easy to use and this is
the reason why I think that point #1 is a good place to start (as long as
at least an working implementation is available behind each of the
functionalities offered). Even if later on, the whole low-level
implementations would be replaced by code from other libraries, having
defined a good syntax for integration with the rest of the language will
IMO not have been be a waste of time.

Point #1 is something that I have not seen anywhere yet in swift, but I
guess that the issue is that we need to experiment with the grammar to work
on the syntax that programmers using that library would experience (is that
ugly? clear? confusing? overloaded? expressive? compact enough?)
  => I do not know how to experiment with the grammar but would like to
learn how to do that: *can someone point me to things I should read and/or
to the places I should make my changes in order to change the swift grammar
and to begin to experiment with it locally on my install?*

2) and 3) is typically what I could see while looking at Surge / Upsurge on
github. There might be more to do here though but I have not took time to
really check, what definitely seems missing to me are linear algebra
algorithms (I mean beyond algorithmic and the call to the existing
functions of the Accelerate Framework). The good news here is that I could
definitively fill some/most of these gaps (I am just not sure that I should
start by adding this to libraries that are based on the Acceleration
Framework since I am rather interested in a multiplatform "easy maths"
swift library)

4) is where the actual magic would happen: take a super natural and easy to
read code and make it quite fast. This can only be made based on the
results of the other 3 points since the expressions to understand come from
#1 and the options provided for optimization come from #2 and #3.

Quite OT for the current discussion, but I would also want to bring a
collection of optimization algorithms and ODE solvers to the "easy maths"
library. Nothing very complicated actually but it is always appreciable to
have them directly available when you need one to test an idea that
requires one, instead of writing your own or adding a third party library
to your project just for the test.

Nicolas

On Fri, Feb 17, 2017 at 8:25 PM, Stephen Canon via swift-evolution <
swift-evolution at swift.org> wrote:

>
> On Feb 17, 2017, at 10:51 AM, Xiaodi Wu via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> There's nothing, afaik, which stands in the way of that syntax today. The
> proposal is to extend the standard library to add syntax for a math
> library. The idea of having a core math library has already been mentioned
> on this list, to great approval, but it should come in the form of an
> actual library, and not a syntax only!
>
>
> Right. IMO the way to do this is to develop such a library outside of the
> stdlib to the point that it’s useful enough to be employed for real work
> and people can evaluate what works and what doesn’t. That may require small
> language and stdlib changes for support, which should be brought-up here.
>
> Once such a library were reasonably mature, it would be reasonable to
> propose it for inclusion in swift proper. I expect this process will take a
> couple *years*.
>
> FWIW, I personally despise MATLAB .operator notation, though I accept that
> it’s pretty much achieved saturation at this point. It looks reasonably
> nice for simple single-operand expressions, but it imposes a large burden
> on the compiler (and often leads to inefficient code). In this regard, they
> are something of an attractive nuisance. Consider your example:
>
> 3.0 .* A .* B ./ (C.^ 4.0)
>
> with the most obvious implementation, this generates four calls to vector
> functions:
>
> - multiply array by scalar (tmp0 <— 3 .* A)
> - elementwise multiplication (tmp1 <— tmp0 .* B)
> - elementwise exponentiation (tmp2 <— C .^ 4)
> - elementwise division (result <— tmp1 ./ tmp2)
>
> again, with the obvious implementation, this wastes space for temporaries
> and results in extraneous passes through the data. It is often *possible*
> to solve these issues (at least for some the most common cases) by
> producing proxy objects that can fuse loops, but that gets very messy very
> fast, and it’s ton of work to support all the interesting cases.
>
> On the other hand, the stupid obvious loop:
>
> for i in 0 ..< count {
> result[i] = 3*A[i]*B[i]/(C[i]*C[i]*C[i]*C[i])
> }
>
> or the cleaner, with a little sugar:
> zip3(A,B,C).map { 3 * $0.0 * $0.1 / ($0.2 ^ 4) }
>
> requires a tiny bit of boilerplate, but only a single pass through the
> data and allows the compiler to vectorize. Even if the four vector
> functions use by the .operations are perfectly hand-optimized, the multiple
> passes and extra memory traffic they entail often makes it *slower* than
> the stupid for loop.
>
> I don’t mean to be too discouraging; all of these issues are surmountable,
> but I (personally) think there’s a lot of development that should happen
> *outside* of the stdlib before such a feature is considered for inclusion
> in the stdlib.
>
> – Steve
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170221/f1ba2d2a/attachment.html>