Multidimensional arrays for Go. It's time.

[John Nagle]

Is there any progress on multidimensional arrays for Go? Not
arrays of arrays, but real multidimensional arrays and slices
as part of the language.

This has been discussed in the number-crunching community,
back to 2009. The arguments for language level multidimensional
arrays are:

1) Multiple packages with different array representations result in
a huge headache when the same program pulls in multiple packages.
Conversion code has to be written and called. This is a headache
in Python, C, and C++, but not FORTRAN or Matlab. This is one
of the reasons so much number crunching still takes place in
FORTRAN and Matlab. It's more compatible if there's one way to
do it, built into the language.

Go is currently headed towards a diverse set of representations:
Compare:

https://github.com/Jragonmiris/mathgl/blob/master/matrixd.go
https://github.com/skelterjohn/go.matrix
https://github.com/eadf/math3d/blob/master/math3d64/matrix3.go
https://github.com/spate/vectormath/blob/master/mat_aos.go

each of which represents 2D matrices in its own way. Code
built on top of those libraries will not interoperate properly.
This discourages the use of Go for numeric work.

2) All the subscript checking for FOR loops can be lifted out
of inner loops. Performance can reach or exceed the levels
of languages that don't have subscript checking. Also, if
you allocate a real multidimensional array as one allocation,
it's contiguous for caching purposes. Not so an array of arrays.

John Nagle

[Kyle Lemons]

On Mon, Aug 26, 2013 at 9:38 PM, John Nagle <na...@animats.com> wrote:

  Is there any progress on multidimensional arrays for Go?  Not
arrays of arrays, but real multidimensional arrays and slices
as part of the language.

I've never seen a proposal for it.

 

                                John Nagle


--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Rob Pike]

Your tone makes it sound critical, but there isn't even an issue on
the tracker about this as far as I can detect. Please add an issue so
it's on our radar.

-rob

[John Nagle]

It's come up a few times, but the number-crunching community doesn't
seem too excited about Go any more. The quants have gone back to
R, Matlab, C++, and when really desperate for speed, VHDL. (Yes,
there are people doing high-frequency trading with FPGAs.) Nobody
in robotics is using Go, as far as I know. There might be a little
gaming work. It may be too late for Go in this area.

The general idea is to support at least the basics:

var arr [4,4]float64;

and

x := arr[i,j]

and

func multiply(a [,]float64, b[,]float64) [,]float64 {...}

which implies array to slice conversion.

A good way to define the goal is to be able to write the
standard algorithms in Numerical Recipes in Go without having
to define a special set of types for matrices, or explicitly
calculating subscripts.

How fancy to get with conversions and reslicing is an issue.
I'd suggest looking at Python's NumPy for guidance there.

John Nagle

[Rob Pike]

As I said, please file an issue.

-rob

[luz...@gmail.com]

On Tuesday, August 27, 2013 7:29:52 AM UTC+2, John Nagle wrote:

    The general idea is to support at least the basics:

        var arr [4,4]float64;

What would be the difference to

var arr [4][4]float64

?

fmt.Println(unsafe.Sizeof(arr))

gives me 128 bytes, one block of memory.

[Andrew Gerrand]

I'd like to head this thread off before it turns into yet another lengthy discussion of whether this vaguely-defined language feature (and I use the word "defined" loosely) is necessary. 

As Kyle pointed out, there is no proposal on the table.

As Rob pointed out, there isn't even a feature request on the issue tracker.

John, I appreciate your enthusiasm, but to get features added to the language you need a solid proposal that covers all the bases. Producing such a proposal is a lot of work and you will need help and feedback to get it right. However, history has shown that mailing lists are terrible places to do this kind of design work.

If you're serious about this, file an issue (http://golang.org/issue/new) and put together a document (Google Docs is a convenient way to collaborate) with a rough proposal and circulate it with the community to see if anyone is interested in collaborating with you to refine it. Try to keep discussion of the feature to the specific issue on the tracker and the document, that way the current state of things should always be obvious.

Andrew

[John Nagle]

On 8/27/2013 12:32 AM, Andrew Gerrand wrote:> I'd like to head this

thread off before it turns into yet another lengthy
> discussion of whether this vaguely-defined language feature (and I use the
> word "defined" loosely) is necessary.
>
> As Kyle pointed out, there is no proposal on the table.
> As Rob pointed out, there isn't even a feature request on the issue
tracker.
>
> John, I appreciate your enthusiasm, but to get features added to the
> language you need a solid proposal that covers all the bases. Producing
> such a proposal is a lot of work and you will need help and feedback
to get
> it right. However, history has shown that mailing lists are terrible
places
> to do this kind of design work.

I'm not seeing any serious number-crunching work going on in Go.
There was some enthusiasm for it a few years ago, but most of the
packages written then were abandoned. Looking at the list under
"Math" in "http://golang.cat-v.org/pure-go-libs":

gomatrix - no updates in the last year, no releases.
gocomplex - 99 lines of code, no docs.
mudlark-go-pkgs - not much math
gostat - bug reports indicate it gets totally wrong answers
gofract - untouched in three years
s3dm-go - dead link
geom - 2D geometry library. Useful, but trivial.
blas - basic linear algebra - looks OK
go-fn - some basic scalar math functions
go-gt - graph algorithms, non-numeric
vectormath - tools for graphics programming

Only one of those, "blas", is a usable numerics library.

The machine learning community is ignoring Go. Andrew Ng says
to use Octave/Matlab, and the quant community uses R and C++.
Even though it's slow, much serious numeric work is done in Python.

> If you're serious about this...

It looks like Go is dead in the water for number-crunching. If
numerics had been taken seriously in the design phase, it might have
been different. But Go has clearly been rejected by the numerical
community. It's too late for this language. Sorry.

John Nagle

[Jan Mercl]

I cannot agree with this point of view. IMO it represents a valid opinion, but not the state of the affairs. Sorry.

-j

[Stephen Gutekanst]

If you intend to say that there are members of a scientific community out there who reject new languages:

• Where number crunching is a after-thought or not yet implemented well.
• While not actively working towards contributing to the design of the mentioned language or improving the lacking features.
• Does not consider new, useful features a language could bring to their projects.

Then I would probably say it does indeed sound like Go is not a good match in my opinion for this community.

If Go lacks serious features for specific projects which cannot be implemented without modifying the language itself, those features should be proposed in a clear and concise way. I read over your 'proposal' if you will for multidimensional arrays in Go and there are many things that where not clear to me.

Your emails sound more like a rant about the current state of Go and do not provide clear suggestions to the language, and you have blatantly ignored suggestions from Rob, Kyle, and Andrew on how to and how not to propose said features.

Stephen

[Kamil Kisiel]

Most of the development of numerical and scientific packages in Go has been consolidated here:

https://github.com/gonum

Though not all of the code from Dan Kortschak's biogo project has been migrated there and I'm not up to speed what the plan is with that.

There's also a corresponding mailing list which is quite active:

https://groups.google.com/forum/#!forum/gonum-dev

You may want to discuss the state of things there.

[Brad Fitzpatrick]

You ignored everything that Rob and Andrew said.

You keep repeating yourself.

This is not productive.

[John Nagle]

On 8/27/2013 9:25 AM, Kamil Kisiel wrote:
> Most of the development of numerical and scientific packages in Go has been
> consolidated here:
>
> https://github.com/gonum
>
> Though not all of the code from Dan Kortschak's biogo project has been
> migrated there and I'm not up to speed what the plan is with that.

That's mostly BLAS again, which is just glue code for
a C library, plus a few trivial functions.

It's worth looking at their matrix package:

https://github.com/gonum/matrix/blob/master/mat64/matrix.go

Look at the errors defined starting at line 327, such as
"row length mismatch" and "illegal stride". Most of those
reflect that they're building multidimensional arrays on top
of one-dimensional arrays, and have to make run-time checks
for things that could have been done at compile time. They
have to work very hard just to get matrices to work at all.
The result is a representation so specific to their code
that it won't interoperate with anything else.

There doesn't seem to be much there that uses that matrix
package.

> There's also a corresponding mailing list which is quite active:
>
> https://groups.google.com/forum/#!forum/gonum-dev

They're trying, which is good. But they just started three
months ago and it's all uphill. Read this:

https://groups.google.com/forum/#!topic/gonum-dev/s_kcMawkVSA

Amusingly, a complaint there is that it's so hard to find
their group. They need something more than Google Groups.

The one good thing about this is that there's no huge
code base already using some agreed-upon matrix implementation.
So language level matrix support in Go wouldn't break much
existing code.

Number-crunching support in Go is about where web support would
be if there were no standard packages for HTTP or HTML.
Is it worth doing? Or should we just accept that Go is a
"web language", like PHP?

John Nagle

[Sebastien Binet]

right. but, at least if we were to follow python's lead, the advantage
is that you can then have multiple views of that piece of memory, w/o
having to copy anything.
how would you, e.g., get at the second column of data in:
ndarr := [3,3]float64{{1,2,3}, {4,5,6}, {7,8,9}}
col2 := ndarr[:,1]
col2[2] = 666

fmt.Println(ndarr)
// ([[ 1, 2, 3],
// [ 4, 5, 6],
// [ 7, 666, 9]])

also, you have the notion of an n-dimensional index, which you can
carry around and address the element in one go:
idx := [2]int{2,1}
ndarr[idx] = 666

of course, nothing which cannot be done w/o the nice n-dim syntax, but
that syntax allows for interesting (multidim) slicing and dicing.

one thing though: (which may indeed tell gonum comes late into the
party) go-1.2 may prevent the "natural" syntax for strides to be used
(as it is currently used for the setcap operation)
in a gonum-ndarray world:

arr := [10]int{1,2,3,4,5,6,7,8,9,10}
fmt.Println(arr[::2])
// [1, 3, 5, 7, 9]

combine that with n-dim arrays and you can do many things with "blobs"
of data, w/o doing to much copying.

for python, this meant efficiently passing around data from, e.g. mmap
blobs to database drivers and back to a "scientific" algorithm.
see:
http://www.python.org/dev/peps/pep-3118/

for the rationale.

I'll try to spark something on the gonum list and get something on the
issue tracker.

-s

[Brendan Tracey]

Thank you for responding Brad and Andrew. Honestly, I didn't realize it was a possibility to add it to the language. A number of places in my code would benefit from being able to call for a true "table" of data rather than a slice of slices. 

I for one, and I think many in the scientific community are in the same boat, do not know a lot about compilers and low-level implementation. Would a document that provides an API be sufficient to get the discussion started? Are there any things that are non-starters (for example, syntax that the current development team would like to reserve)? Is it possible that there would be additions to the built-in functions to the language as a result of this, or should our proposal have none of those? 

Thanks.

[Nico]

for example, are operators off-limits?

What are the cons of something like this?

a := []float64 {1, 2, 3}
b := []float64 {10, 20, 30}
c := []float64 {10, 20, 30, 40}
d := a + b
e := a + c // panic

[luz...@gmail.com]

On Tuesday, August 27, 2013 9:00:46 PM UTC+2, Sebastien Binet wrote:

right. but, at least if we were to follow python's lead, the advantage
is that you can then have multiple views of that piece of memory, w/o
having to copy anything.  

Yes, there's no slicing yet. But he didn't seem to be aware that Go's arrays of arrays actually are contiguous memory blocks, unlike arrays of arrays in Java. At least that's how I interpreted his words:

"Also, if you allocate a real multidimensional array as one allocation, it's contiguous for caching purposes. Not so an array of arrays."

So half of his rant seems to be based on wrong assumptions.

[Jsor]

Arrays of arrays are contiguous, but not slices of slices. To ensure they're dense you have to allocate a slice of size M x N and and then do extra checking and math to get the right row and column and make sure the row/col requested are correct (for instance a 4x1 and a 2x2 are both [4], but asking for 3,0 is only valid in one of them).

IMO, the real reason to have matrices built in is because matrices are a numeric type just as real as floats and ints. At least +, -, and * are well defined and should be implemented at the language level because it makes math (much, much) more readable and follows the well established conventions for dealing with matrices. I mean, unless you've been doing polish notation all your life, I guess.

[John Nagle]

On 8/27/2013 1:03 PM, Jsor wrote:
> Arrays of arrays are contiguous, but not slices of slices.

That's true in C, and it's probably true in Go implementations,
but the language reference for Go does not guarantee it. From
within Go, you can't tell - it's a subscript error if you try.
In C, you can use "memcpy" on an entire array, and that's considered
valid.

> IMO, the real reason to have matrices built in is because matrices are a
> numeric type just as real as floats and ints. At least +, -, and * are
well
> defined and should be implemented at the language level because it makes
> math (much, much) more readable and follows the well established
> conventions for dealing with matrices. I mean, unless you've been doing
> polish notation all your life, I guess.

That's going to be a big point of controversy. How general should
"*" be? N-dimensional array and slice multiplication? That's a lot
of code in the general case. It's a form of built-in operator
overloading. And there's no way for an operator to return an error,
short of "panic".

On the other hand, the only things that can go wrong for +, -, and
* are size mismatches, which are a form of subscript error. Go already
generates subscript error aborts. The expected behavior of these
operators is well-understood. We don't have the Python problem that
"+" is considered concatenation for built-in arrays, but addition for
NumPy arrays. Go doesn't have legacy overloads like that to cause
trouble.

Painful though it is, the big advantage of supporting those
operators is that you get to transliterate libraries of
debugged Matlab code to Go without much effort. That gets Go good
math libraries, fast. Which is what Go needs to be useful for
numerical work.

These are operations that compile well. When size information
is available at compile time, the code can be very efficient. Most
modern processors (everything bigger than an ARM) have hardware that
is specifically designed for array operations. The user can't
generate MMX instructions, but the compiler can.

John Nagle

[Andrew Gerrand]

[Replying to the list]

On 28 Aug 2013 01:50, "John Nagle" <na...@animats.com> wrote:
>    It looks like Go is dead in the water for number-crunching.  If
> numerics had been taken seriously in the design phase, it might have
> been different.  But Go has clearly been rejected by the numerical
> community.  It's too late for this language.  Sorry.

The original subject of your mail is "It's time." But now you say it is too late? Please stop wasting everyone's time with this nonsense. We all have better things to do.

Andrew

[Andrew Gerrand]

Hi Brendan,

It's not too late for backward-compatible language changes, or additions to the standard library. Such changes need to mesh well with the current state of things and the design goals of Go.

Not being a number crunching person myself, I'm in a poor position to suggest what form this should take. I suspect the authors of the various scientific computing packages would have thoughts about how the language could have helped them better solve their problems. Collecting those thoughts in a coherent document would be a good place to start.

Andrew

--

[John Nagle]

So go do them. You're not compelled to participate here.

John Nagle

[Dan Kortschak]

I'll invite you again to participate again in the project.

Dan

[luz...@gmail.com]

On Tuesday, August 27, 2013 10:31:27 PM UTC+2, John Nagle wrote:

On 8/27/2013 1:03 PM, Jsor wrote:
> Arrays of arrays are contiguous, but not slices of slices.

   That's true in C, and it's probably true in Go implementations,
but the language reference for Go does not guarantee it. 

Since the values of a one-dimensional array are contiguous, and since an array is a value in Go, not a reference, arrays of arrays must be contiguous as well by induction. 

[Andrew Gerrand]

I'm sorry for trying to help you get the features you want into the language. I certainly won't do so again.

But since I *am* compelled to read golang-nuts — it is my mailing list, after all — I must ask you to please stop posting to this thread. You have sufficiently expressed your opinions.

Andrew

[John Nagle]

I will not post further in this thread until after I
have contacted Mr. Gerrand's supervisor at Google Australia.

John Nagle

On 8/27/2013 1:49 PM, Andrew Gerrand wrote:
> I'm sorry for trying to help you get the features you want into the
> language. I certainly won't do so again.
>

> But since I *am* compelled to read golang-nuts � it is my mailing list,
> after all � I must ask you to please stop posting to this thread. You have

[Brendan Tracey]

Thanks. We're starting that process.

[Dan Kortschak]

Oh please.

[Jonathan Amsterdam]

I would think that there are several things about Go other than the lack of multidimensional slices that would make it unpalatable to numeric programmers. In particular, lack of operator overloading, and lack of generics (so that you'd need to duplicate your code for float32 and float64). I think it will be harder to add those features to the language than it will be to add multidimensional slices.

[Norman Yarvin]

On Tue, Aug 27, 2013 at 08:50:20AM -0700, John Nagle wrote:

> It looks like Go is dead in the water for number-crunching. If
>numerics had been taken seriously in the design phase, it might have
>been different.

Perhaps that is inevitable, given that the designers don't have much
interest in number-crunching, and are quite protective of their
language. When one doesn't have much interest, one is unable to do a
really good job of evaluating proposals; one ends up either rejecting
too many of them or accepting too many of them. (Or, as a middle
ground, doing some of each.)

There's still a way to get stuff like multidimensional arrays into the
language, which is to demonstrate, by writing the code to add them to
the compiler, that it doesn't mess things up -- that it can be
implemented cleanly and with minimal adverse consequences. That's
also a way to take oneself out of the category of mere supplicant who
should be told to "go tell it to the issue tracker", and into the
category of people worth having a conversation with. In some circles
one just doesn't get respect unless one can write compiler code. (Not
that that attitude is really appropriate, but it's understandable.)


--
Norman Yarvin http://yarchive.net/blog

[Andrew Gerrand]

On 28 August 2013 10:31, Norman Yarvin <yar...@yarchive.net> wrote:

Perhaps that is inevitable, given that the designers don't have much
interest in number-crunching, and are quite protective of their
language.  When one doesn't have much interest, one is unable to do a
really good job of evaluating proposals; one ends up either rejecting
too many of them or accepting too many of them.  (Or, as a middle
ground, doing some of each.)

 

There have been no proposals to evaluate.

 

There's still a way to get stuff like multidimensional arrays into the
language, which is to demonstrate, by writing the code to add them to
the compiler, that it doesn't mess things up -- that it can be
implemented cleanly and with minimal adverse consequences.

Please do not try to change the language by first implementing the language change. It will likely be a waste of your time.

Earlier in this thread I described the right way to get features added to the language.

Once a proposal has been circulated and generally considered a reasonable idea, then it makes sense to start hacking and explore the broader ramifications of the change.

 

 That's
also a way to take oneself out of the category of mere supplicant who
should be told to "go tell it to the issue tracker", and into the
category of people worth having a conversation with.  

Actually, the way to take oneself out of that category is to file the issue on the issue tracker (which still nobody has done yet, BTW). If you don't care enough about the feature to file a request for it, then why on earth would anyone take you seriously?!

 

In some circles
one just doesn't get respect unless one can write compiler code.  (Not
that that attitude is really appropriate, but it's understandable.)

That's not the way the Go project works. Our contribution guidelines state clearly, up front, to discuss your design before writing any code: http://golang.org/doc/contribute.html#Design

Andrew 

[Andrew Gerrand]

On 28 August 2013 10:56, Andrew Gerrand <a...@golang.org> wrote:

 That's
also a way to take oneself out of the category of mere supplicant who
should be told to "go tell it to the issue tracker", and into the
category of people worth having a conversation with.  

Actually, the way to take oneself out of that category is to file the issue on the issue tracker (which still nobody has done yet, BTW). If you don't care enough about the feature to file a request for it, then why on earth would anyone take you seriously?!

I suppose I should spell out that the primary way we coordinate work on this project is via the issue tracker.

If your issue is not on the tracker then it is largely invisible to the people who work on Go every day.

Asking someone to file an issue is not telling them to go away. On the contrary, it is the first step toward having the issue taken seriously, and prevents it from being forgotten.

Andrew 

[Dan Kortschak]

People on gonum-dev are already starting to think about this issue -
provoked by John's post. I'm sure someone will log an issue on
code.google.com/p/go from there.

Dan

[r]

Lol, this is not Burger King, nor he's cooking hamburgers.

[r]

No need to mention that you're not a customer either.

Anyway, here's some itchy spots I came across when I tried to use Go for computation (involving matrices):

-No operator overloading: matrix operations, as well as using non-primitive types (bigfloat, or even worse, complex numbers with bigfloat) become too verbose

-No SIMD or specialized instruction support: huge effect on performance. gccgo can do auto-vectorization sometimes, but overall the performance+memory usage is bad in comparison to 6g. The code emitted by 6g is also quite verbose and could be better.

-big package is slow

-C calls are expensive

I believe these will improve in time.

Multidimensional arrays is not one of them however, because the underlying data is abstracted away by the matrix class anyway.

[Norman Yarvin]

On Wed, Aug 28, 2013 at 10:56:21AM +1000, Andrew Gerrand wrote:
>On 28 August 2013 10:31, Norman Yarvin <yar...@yarchive.net> wrote:
>
>> Perhaps that is inevitable, given that the designers don't have much
>> interest in number-crunching, and are quite protective of their
>> language. When one doesn't have much interest, one is unable to do a
>> really good job of evaluating proposals; one ends up either rejecting
>> too many of them or accepting too many of them. (Or, as a middle
>> ground, doing some of each.)
>>
>
>There have been no proposals to evaluate.

It was posted a while ago, and wasn't explicitly referenced in the
current thread, but this is my idea of what multidimensional slices
would be like:

http://groups.google.com/group/golang-nuts/msg/2ba08fe85b97f441

>> There's still a way to get stuff like multidimensional arrays into the
>> language, which is to demonstrate, by writing the code to add them to
>> the compiler, that it doesn't mess things up -- that it can be
>> implemented cleanly and with minimal adverse consequences.
>
>Please do not try to change the language by first implementing the language
>change. It will likely be a waste of your time.
>
>Earlier in this thread I described the right way to get features added to
>the language.
>
>Once a proposal has been circulated and generally considered a reasonable
>idea, then it makes sense to start hacking and explore the broader
>ramifications of the change.

Yeah, but what do you do when an idea has been discussed yet ignored
by Go's designers? Putting it on the issue tracker isn't going to
change the level of interest of the Go team, and entries in the issue
tracker aren't any harder to ignore than posts are here -- that's what
"Status: WontFix" is for.

And if one actually writes the code, at least one can use it oneself
and share it with others who want it. The size of that audience then
can serve as an indication to the Go team of how much interest there
really is in the feature.

[Kyle Lemons]

On Wed, Aug 28, 2013 at 11:56 AM, Norman Yarvin <yar...@yarchive.net> wrote:

On Wed, Aug 28, 2013 at 10:56:21AM +1000, Andrew Gerrand wrote:
>On 28 August 2013 10:31, Norman Yarvin <yar...@yarchive.net> wrote:
>
>> Perhaps that is inevitable, given that the designers don't have much
>> interest in number-crunching, and are quite protective of their
>> language.  When one doesn't have much interest, one is unable to do a
>> really good job of evaluating proposals; one ends up either rejecting
>> too many of them or accepting too many of them.  (Or, as a middle
>> ground, doing some of each.)
>>
>
>There have been no proposals to evaluate.

It was posted a while ago, and wasn't explicitly referenced in the
current thread, but this is my idea of what multidimensional slices
would be like:

        http://groups.google.com/group/golang-nuts/msg/2ba08fe85b97f441

Unfortunately that only proposes syntax, and it doesn't cover a lot of the questions that we'll have about the proposal and its implementation.  That's why the suggestion was to create a doc to discuss it, so that it isn't strung out throughout a giant thread.

 

>> There's still a way to get stuff like multidimensional arrays into the
>> language, which is to demonstrate, by writing the code to add them to
>> the compiler, that it doesn't mess things up -- that it can be
>> implemented cleanly and with minimal adverse consequences.
>
>Please do not try to change the language by first implementing the language
>change. It will likely be a waste of your time.
>
>Earlier in this thread I described the right way to get features added to
>the language.
>
>Once a proposal has been circulated and generally considered a reasonable
>idea, then it makes sense to start hacking and explore the broader
>ramifications of the change.

Yeah, but what do you do when an idea has been discussed yet ignored
by Go's designers?  Putting it on the issue tracker isn't going to
change the level of interest of the Go team, and entries in the issue
tracker aren't any harder to ignore than posts are here -- that's what
"Status: WontFix" is for.

I don't think you can say it's been ignored.  The last time it was discussed was in 2010?  Until there is an issue filed and closed as WontFix, don't assume that's what they'll do.

 

And if one actually writes the code, at least one can use it oneself
and share it with others who want it.  The size of that audience then
can serve as an indication to the Go team of how much interest there
really is in the feature.

--
Norman Yarvin                                   http://yarchive.net/blog

[Andrew Gerrand]

Having a discussion on golang-nuts is not the same as making a serious language proposal. That's what I was saying earlier in this thread.

Assessing all the angles on language changes takes much careful thought. Who would have time to consider all the feature proposals on this mailing list? We would never get anything done.

I repeat: the best way to have a feature seriously considered is to file an issue with a detailed proposal. Yes, it might get marked WontFix, but at least then you know where you stand. 

Andrew

[Norman Yarvin]

On Wed, Aug 28, 2013 at 12:07:12PM -0700, Kyle Lemons wrote:
>On Wed, Aug 28, 2013 at 11:56 AM, Norman Yarvin <yar...@yarchive.net> wrote:
>> It was posted a while ago, and wasn't explicitly referenced in the
>> current thread, but this is my idea of what multidimensional slices
>> would be like:
>>
>> http://groups.google.com/group/golang-nuts/msg/2ba08fe85b97f441
>
>
>Unfortunately that only proposes syntax, and it doesn't cover a lot of the
>questions that we'll have about the proposal and its implementation.
> That's why the suggestion was to create a doc to discuss it, so that it
>isn't strung out throughout a giant thread.

Well, it does talk somewhat about implementation, in that it specifies
the data structure that would constitute a multidimensional slice. As
for questions, are there any particular ones that it raises in your
mind? My impression is that the implementation would be pretty
straightforward.

As for creating 'a doc', that sounds like something different from the
'filing an issue' that was suggested by others. In either case,
though, it's not clear what additional details might be called for.

>I don't think you can say it's been ignored. The last time it was
>discussed was in 2010?

No, it's come up on occasion since then. Lots of people who do
number-crunching want something like this.

[Kyle Lemons]

On Wed, Aug 28, 2013 at 4:47 PM, Norman Yarvin <yar...@yarchive.net> wrote:

On Wed, Aug 28, 2013 at 12:07:12PM -0700, Kyle Lemons wrote:
>On Wed, Aug 28, 2013 at 11:56 AM, Norman Yarvin <yar...@yarchive.net> wrote:

>> It was posted a while ago, and wasn't explicitly referenced in the
>> current thread, but this is my idea of what multidimensional slices
>> would be like:
>>
>>         http://groups.google.com/group/golang-nuts/msg/2ba08fe85b97f441
>
>
>Unfortunately that only proposes syntax, and it doesn't cover a lot of the
>questions that we'll have about the proposal and its implementation.
> That's why the suggestion was to create a doc to discuss it, so that it
>isn't strung out throughout a giant thread.

Well, it does talk somewhat about implementation, in that it specifies
the data structure that would constitute a multidimensional slice.  As
for questions, are there any particular ones that it raises in your
mind?  My impression is that the implementation would be pretty
straightforward.

That's precisely why it needs a doc.  It's not really straightforward.  Some questions that come to mind: can a vector sliced out of a multidim array be used as a slice?  Do you only allow major slicing or can you also slice across minor axes (in other words, can you slice a column out of a row-major matrix)?  How do you implement a function that can take multiple different sizes without generics?  Do you have append mechanics and how does it work?

A lot of these questions influence the implementation, but in general more than one implementation possibility should be possible (often an easy one and an optimal one for future improvements).

As for creating 'a doc', that sounds like something different from the
'filing an issue' that was suggested by others.  In either case,
though, it's not clear what additional details might be called for.

Create the issue with the feature request and the general gist, point at the "living" doc where details are hashed out.  They're not mutually exclusive.

[Kamil Kisiel]

There's some people taking a serious look at hashing out these kinds of details here: https://groups.google.com/d/topic/gonum-dev/WnptzWjqhmk/discussion 

[Norman Yarvin]

On Wed, Aug 28, 2013 at 05:13:42PM -0700, Kyle Lemons wrote:
>On Wed, Aug 28, 2013 at 4:47 PM, Norman Yarvin <yar...@yarchive.net> wrote:
>
>> On Wed, Aug 28, 2013 at 12:07:12PM -0700, Kyle Lemons wrote:
>> >On Wed, Aug 28, 2013 at 11:56 AM, Norman Yarvin <yar...@yarchive.net>
>> wrote:
>> >> It was posted a while ago, and wasn't explicitly referenced in the
>> >> current thread, but this is my idea of what multidimensional slices
>> >> would be like:
>> >>
>> >> http://groups.google.com/group/golang-nuts/msg/2ba08fe85b97f441
>> >
>> >
>> >Unfortunately that only proposes syntax, and it doesn't cover a lot of the
>> >questions that we'll have about the proposal and its implementation.
>> > That's why the suggestion was to create a doc to discuss it, so that it
>> >isn't strung out throughout a giant thread.
>>
>> Well, it does talk somewhat about implementation, in that it specifies
>> the data structure that would constitute a multidimensional slice. As
>> for questions, are there any particular ones that it raises in your
>> mind? My impression is that the implementation would be pretty
>> straightforward.
>
>That's precisely why it needs a doc. It's not really straightforward.
> Some questions that come to mind: can a vector sliced out of a multidim
>array be used as a slice?

Yes.

> Do you only allow major slicing or can you also
>slice across minor axes (in other words, can you slice a column out of a
>row-major matrix)?

No.

Those answers are already given in the linked post, which goes on
to give the general rule:

In general, the last dimension of an N-dimensional slice could
not be elided (by setting its index equal to a single value)
to produce a slice of fewer dimensions, but any subset of the
other dimensions could be elided.

(This is for efficiency; the last dimension is special because there
is no "stride" kept for it. Adding such a number would mean adding it
even to one-dimensional slices, and would mean an additional
multiplication to access slice elements.)

> How do you implement a function that can take multiple
>different sizes without generics?

What would the problem be? The language already provides for
functions that take any size of one-dimensional slice; this would just
extend that to N-dimensional slices. Or if you mean a function that
takes an N-dimensional slice with N being variable, that's not a
commonly desired feature, and it need not be implemented. (If you
really need that feature, you can pass in an interface.)

> Do you have append mechanics and how
>does it work?

No. That would require some sort of reallocation strategy, which is
not part of the language for one-dimensional slices either.

[gex]

Do you think that some of developers would be interested in helping out with the proposal?

It seems to me that most people who are interested in multi-dimensional arrays want to use go as low-level substitute for languages like matlab or python/numpy. At least that is what I am looking for in go. But the problem we face is that we have little or no idea of language implementation.
Also it seems that the go team has a very good grasp of the problems that arise with software that comes with a large number of lines of code.
It would be really interesting to get the opinion of the people who designed go on the subject of introducing multi-dimensional arrays in go both as a language implementation task and the implications of introducing them in the language definition.
Actually, I think it would be very educational to get the opinion of go designers/developers on scientific programming in general. What are the benefits and drawbacks of using go for scientific computing and what do you think should/could change in order to make go a contender (next to matlab, python/numpy etc.) in that category?

I am sorry if the question is a bit overloaded but I like reading your posts :D

[Norman Yarvin]

On Wed, Aug 28, 2013 at 09:19:43PM -0400, Norman Yarvin wrote:

>> Do you have append mechanics and how
>>does it work?
>
>No. That would require some sort of reallocation strategy, which is
>not part of the language for one-dimensional slices either.

Oops. Of course I was wrong about this for one-dimensional slices;
there is the append built-in function. Yes, it'd be desirable to have
a parallel of it for multidimensional ones, to make the language
symmetrical, and so that the "capacity" number that is stored for each
dimension would actually be a usable capacity. I don't think there'd
be much trouble in implementation, but finding a readable syntax seems
harder, given that the "appending" might be in any one of the slice's
dimensions. (Passing in a number to indicate which dimension to
expand would be workable but ugly. Trying to do multiple dimensions
at once would be sinfully ugly.) Perhaps, rather than an append
function that does two things at once (resize and add data), just a
function that resizes would be better. Then one could pass in the new
sizes for all dimensions.

[Andrew Gerrand]

Norman,

Your last couple of emails  demonstrate that mailing lists are a poor medium mailing for doing this.

I am sure that Kyle's questions were rhetorical in this case; his bigger point was that you don't have a complete proposal. Replying to his questions in this thread does not bring you closer to that point.

In Google Docs, someone might add a comment:

>  Do you only allow major slicing or can you also
>slice across minor axes (in other words, can you slice a column out of a
>row-major matrix)?

And you can respond by pointing them to the relevant part of the doc, adding it if it doesn't exist, or clarifying the existing prose. Then you mark the comment as "Resolved" and the comment goes away. After all comments and questions are answered, you have a final cohesive document that presents your proposal.

Using mailing lists, for someone to understand your ideas they need to go and read everything you've written on the subject. It is simply not tenable to work this way.

Andrew

[Rodrigo Moraes]

On Wed, Aug 28, 2013 at 11:37 PM, Andrew Gerrand wrote:
> In Google Docs, someone might add a comment:
>
>> Do you only allow major slicing or can you also
>>slice across minor axes (in other words, can you slice a column out of a
>>row-major matrix)?
>
> And you can respond by pointing them to the relevant part of the doc, adding
> it if it doesn't exist, or clarifying the existing prose.

An example of such dynamics (in a totally unrelated subject) is here:

https://docs.google.com/document/d/155ZJOHtOgnm8P80TDL8QGfNZ-wNoqsRNRGHRfJB4JGs/edit

-- rodrigo

[Michael Jones]

You might look through the Fortran 90 spec/tutorials to have a look at their multidimensional array capabilities and simply list which of these you would need and why, as well as which you don't need, and why. That would be a great start. (Since Fortran 90 is implicitly a superset of "enough")

--

[Kyle Lemons]

On Wed, Aug 28, 2013 at 6:29 PM, gex <gexa...@gmail.com> wrote:

Do you think that some of developers would be interested in helping out with the proposal?

It seems to me that most people who are interested in multi-dimensional arrays want to use go as low-level substitute for languages like matlab or python/numpy. At least that is what I am looking for in go. But the problem we face is that we have little or no idea of language implementation.

I'm sure the community as a whole would love to dive in and provide suggestions once there's a coherent proposal on the table.  In particular, you want to be able to describe the changes required to the spec to accommodate your proposal.  The feedback you get from the community may well be "That's too many changes!" or "That's too difficult to understand." but if not, we'll be able to help think about how the low level implementation could be done and whether it's feasible, and how to tweak the proposal to make it feasible.

 

Also it seems that the go team has a very good grasp of the problems that arise with software that comes with a large number of lines of code.
It would be really interesting to get the opinion of the people who designed go on the subject of introducing multi-dimensional arrays in go both as a language implementation task and the implications of introducing them in the language definition.

I can't speak for them, but I suspect it boils down to the same reason we don't have a GUI library in the stdlib: most of the core maintainers and a lot of the devs are client/server folk, and don't really feel qualified to write GUI APIs; in this case, most of us are not super familiar with scientific/mathematical computing, and so probably aren't really qualified to write such APIs.  I personally think that there is probably a certain amount of multidimensional array support that can be baked into the language to support math/sci computing, though because operator overloading and such are pretty much off the table it might not be to quite the degree you'd need to make it super compelling without a third party API.

 

Actually, I think it would be very educational to get the opinion of go designers/developers on scientific programming in general. What are the benefits and drawbacks of using go for scientific computing and what do you think should/could change in order to make go a contender (next to matlab, python/numpy etc.) in that category?

Again, I can't speak for them, but I think that Go has many advantages: reasonable concurrency is going to be a huge deal when utilizing the parallelism of today's CPUs, and the high-core-count trend doesn't seem to be going out of fashion; fine control over data layout without the burdens of C could be a big deal in terms of optimizing algorithms for a particular computer (knowing the sizes of your caches, etc); being a compiled language gives you generally good performance even without optimization; and strong type-safety could potentially avoid some classes of dimensional errors as well as a lot of general bugs.

 

--

[Kyle Lemons]

On Thu, Aug 29, 2013 at 8:34 AM, Kyle Lemons <kev...@google.com> wrote:

On Wed, Aug 28, 2013 at 6:29 PM, gex <gexa...@gmail.com> wrote:

Do you think that some of developers would be interested in helping out with the proposal?

It seems to me that most people who are interested in multi-dimensional arrays want to use go as low-level substitute for languages like matlab or python/numpy. At least that is what I am looking for in go. But the problem we face is that we have little or no idea of language implementation.

I'm sure the community as a whole would love to dive in and provide suggestions once there's a coherent proposal on the table.  In particular, you want to be able to describe the changes required to the spec to accommodate your proposal.  The feedback you get from the community may well be "That's too many changes!" or "That's too difficult to understand." but if not, we'll be able to help think about how the low level implementation could be done and whether it's feasible, and how to tweak the proposal to make it feasible.

I should also mention that, even if it gets to this point in the process, there's still the question of whether the proposal carries its own weight.  That is a very high bar to pass.  For instance, if adding multidimensional slice support is going to slow down normal slices becuase they need a stride, it's probably not going to fly.

[Norman Yarvin]

On Thu, Aug 29, 2013 at 12:37:17PM +1000, Andrew Gerrand wrote:
>Norman,
>
>Your last couple of emails demonstrate that mailing lists are a poor
>medium mailing for doing this.
>
>I am sure that Kyle's questions were rhetorical in this case; his bigger
>point was that you don't have a complete proposal. Replying to his
>questions in this thread does not bring you closer to that point.

They might have been intended to be rhetorical, but it's a pretty poor
rhetorical device to ask questions that were already answered in the
document being questioned. As a way to demonstrate that a proposal
was incomplete, it rather accomplishes the reverse of what was
intended. (Not that I am trying to assert that the proposal is
complete, or that it even really reaches the level of being
describable as a "proposal"; the question as to what was lacking was
meant as a real question, and to be answered rhetorically is
disappointing.)

>In Google Docs, someone might add a comment:
>
>> Do you only allow major slicing or can you also
>>slice across minor axes (in other words, can you slice a column out of a
>>row-major matrix)?
>
>And you can respond by pointing them to the relevant part of the doc,
>adding it if it doesn't exist, or clarifying the existing prose. Then you
>mark the comment as "Resolved" and the comment goes away. After all
>comments and questions are answered, you have a final cohesive document
>that presents your proposal.
>
>Using mailing lists, for someone to understand your ideas they need to go
>and read everything you've written on the subject. It is simply not tenable
>to work this way.

Searching through my writings really shouldn't be the way anyone tries
to understand this, since the core idea is quite simple. Perhaps I've
been taking too much for granted that people will get the idea --
that, for instance, the math to address elements of a multidimensional
slice will be obvious from a description of the slice data structure
-- but in that case the cure is not to move to some automated system
for managing complexity, but rather for me (or someone) to do a better
job explaining the basic mechanics of the scheme. Considering that
the final documentation would need to include some such explanation,
it seems especially indicated.

[Norman Yarvin]

On Wed, Aug 28, 2013 at 08:34:09PM -0700, Michael Jones wrote:
>You might look through the Fortran 90 spec/tutorials to have a look at
>their multidimensional array capabilities and simply list which of these
>you would need and why, as well as which you don't need, and why. That
>would be a great start. (Since Fortran 90 is implicitly a superset of
>"enough")

Fortran 90 multidimensional arrays are a mess, due largely to the
desire to have not just source compatibility but binary compatibility
with Fortran 77 code. Not only is it a strange mix of old and new
features, but there are some situations in Fortran 90 where an array
will be copied in its entirety when being passed to an F77-style
routine, rather than the normal pass by reference; unsuspecting
programmers can find their code slowed down by orders of magnitude
because of unexpected copies of multi-megabyte arrays.

We can do a lot better.

[Kyle Lemons]

On Thu, Aug 29, 2013 at 9:53 AM, Norman Yarvin <yar...@yarchive.net> wrote:

On Thu, Aug 29, 2013 at 12:37:17PM +1000, Andrew Gerrand wrote:
>Norman,
>
>Your last couple of emails  demonstrate that mailing lists are a poor
>medium mailing for doing this.
>
>I am sure that Kyle's questions were rhetorical in this case; his bigger
>point was that you don't have a complete proposal. Replying to his
>questions in this thread does not bring you closer to that point.

They might have been intended to be rhetorical, but it's a pretty poor
rhetorical device to ask questions that were already answered in the
document being questioned.  As a way to demonstrate that a proposal
was incomplete, it rather accomplishes the reverse of what was
intended.  (Not that I am trying to assert that the proposal is
complete, or that it even really reaches the level of being
describable as a "proposal"; the question as to what was lacking was
meant as a real question, and to be answered rhetorically is
disappointing.)

I asked them because I disagree with the answers given in the original or think they're confusing or the wrong choice.

[Michael Jones]

Norman,

No problem with that. Just "s/90/70/g" in that case. My point is to look at existing designs that are found useful for precisely the intended purposes and use them as a starting point for conceptual debate. My question is really, "how little of this is necessary?" Not that I'd fight for doing less than is best, but simply suspicious that much of what is there is superfluous for reasons such as you mention. I bet selectable [min:max] ranges are one such example, but I'm not sure. 

I hoped that my suggestion would lead to informed people pruning a more than sufficient F77/F90 feature list down to a small-yet-sufficient subset of concepts that need to be present. The, from that, a how to do it in Go discussion could be had. Here is an example of what I'd envisioned.

group resolution: "We need subroutines that work for arrays of various sizes" (clearly! For example, a float64 matrix inversion routine that works for N x N arrays of any N >= 1.) 

This would be a great provocation for discussion. What Go approach would allow [3,3] and [100,100] as an argument? Right now, only an interface. In Fortran, you'd have "invert(a(m,n), m, n)" where the dimensions come in as arguments. In go, you might come up with "invert(float64 a[int m, int n])" or perhaps "invert(float64 a[?][?])" where you could then do "len(a[0])" and "len(a[1])" or have len return a slice of cardinalities so "len(a)[0]" and "len(a)[1]"

There may be much better ways, but this is the kind of fruitful discussion that would follow from "We need subroutines that work for arrays of various sizes." If you seed the discussion with an agreed to be sufficient feature set then the conversations about specific features can be conducted with a more holistic view.

Michael

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Dan Adkins]

I have placed this on the radar. :)
http://code.google.com/p/go/issues/detail?id=6282

What now?

-Dan

On Mon, Aug 26, 2013 at 10:01 PM, Rob Pike <r...@golang.org> wrote:

Your tone makes it sound critical, but there isn't even an issue on
the tracker about this as far as I can detect.  Please add an issue so
it's on our radar.

-rob

[Tony Worm]

I wrote this a couple years back when I was thinking about implementing multi-dimensional arrays in the compiler for a PL class.

https://github.com/verdverm/mslice

(It's always interesting looking at your own code from way back when :)

On Tuesday, August 27, 2013 12:38:33 AM UTC-4, John Nagle wrote:

 Is there any progress on multidimensional arrays for Go?  Not
arrays of arrays, but real multidimensional arrays and slices
as part of the language.

  This has been discussed in the number-crunching community,
back to 2009.  The arguments for language level multidimensional
arrays are:

  1) Multiple packages with different array representations result in
     a huge headache when the same program pulls in multiple packages.
     Conversion code has to be written and called. This is a headache
     in Python, C, and C++, but not FORTRAN or Matlab.  This is one
     of the reasons so much number crunching still takes place in
     FORTRAN and Matlab.  It's more compatible if there's one way to
     do it, built into the language.

     Go is currently headed towards a diverse set of representations:
     Compare:

        https://github.com/Jragonmiris/mathgl/blob/master/matrixd.go
        https://github.com/skelterjohn/go.matrix
        https://github.com/eadf/math3d/blob/master/math3d64/matrix3.go
        https://github.com/spate/vectormath/blob/master/mat_aos.go

     each of which represents 2D matrices in its own way.  Code
     built on top of those libraries will not interoperate properly.
     This discourages the use of Go for numeric work.

  2) All the subscript checking for FOR loops can be lifted out
     of inner loops.  Performance can reach or exceed the levels
     of languages that don't have subscript checking.  Also, if
     you allocate a real multidimensional array as one allocation,
     it's contiguous for caching purposes.  Not so an array of arrays.

                                John Nagle

[John Nagle]

On 8/29/2013 8:34 AM, Kyle Lemons wrote:
> On Wed, Aug 28, 2013 at 6:29 PM, gex <gexa...@gmail.com> wrote:
>
>> Do you think that some of developers would be interested in helping out
>> with the proposal?
>>
>> It seems to me that most people who are interested in multi-dimensional
>> arrays want to use go as low-level substitute for languages like matlab or
>> python/numpy. At least that is what I am looking for in go. But the problem
>> we face is that we have little or no idea of language implementation.
>>
>
> I'm sure the community as a whole would love to dive in and provide
> suggestions once there's a coherent proposal on the table.

There's something of a consensus appearing here:

Multidimensional arrays/slices - probably a good addition to Go.
User-defined generics/operator overloading - probably unacceptable.
Basic operations (+,-,*) on arrays - maybe OK
Reshaping/reslicing of arrays - hard, needs design work.

Reshaping/reslicing/slice growth are hard problems.
Too little generality, and the numerical users will be unhappy.
Too much generality, and the implementation will be slow for
basic subscripting operations.

I can't speak to that; most of my numerical work hasn't involved
resizing or reshaping.

What capabilities are really needed in that area?

John Nagle

[Michael Jones]

I once debugged (and fixed!) the one of the first programs that Brian Kernighan wrote at Bell Labs. It was a travelling salesman optimizer named FAST, in Fortran. At its core were two separate arrays, one upper triangular and one lower triangular, both stored in the same NxN array. If I remember correctly, there was some funky way to deceive Fortran's support for adjustable array dimensions to make the accesses work normally when the two haves were logically swapped (transposed) but not moved in memory just accessed differently. That is the kind of generality that might be great to keep out of Go. ;-)

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[John Nagle]

On 8/29/2013 11:48 AM, Michael Jones wrote:> I once debugged (and

fixed!) the one of the first programs that Brian
> Kernighan wrote at Bell Labs. It was a travelling salesman optimizer named
> FAST, in Fortran. At its core were two separate arrays, one upper
> triangular and one lower triangular, both stored in the same NxN array. If
> I remember correctly, there was some funky way to deceive Fortran's
support
> for adjustable array dimensions to make the accesses work normally
when the
> two haves were logically swapped (transposed) but not moved in memory just
> accessed differently. That is the kind of generality that might be
great to
> keep out of Go. ;-)

I agree.

A useful metric for a numerical feature is "Is it needed for
Numerical Recipes or Graphics Gems"? Those have most of the
low-level math libraries in common use, the algorithms that
need to go fast. The way to get Go a set of good math libraries
in a hurry is to make it easy to port that code over.

Is there anything not used there that's widely used in
Matlab/Octave?

Assuming some reasonable slice representation for
multidimensional slices (with a "stride" value for
each dimension after the lowest) it's reasonable to consider
reslicing/reshaping functions which merely generate a
new slice descriptor pointing to the same underlying data.
What should those be?

John Nagle

>
>
> On Thu, Aug 29, 2013 at 11:16 AM, John Nagle <na...@animats.com> wrote:

...

[bugpowder]

On Tuesday, August 27, 2013 6:50:20 PM UTC+3, John Nagle wrote:

   It looks like Go is dead in the water for number-crunching.  If
numerics had been taken seriously in the design phase, it might have
been different.  But Go has clearly been rejected by the numerical
community.  It's too late for this language.  Sorry.

Well, it's not like anybody cares much about this, either from the number-crunching side or the Go side.

And I'd say Go would need a lot more to offer than merely multi-dimensional arrays to be of much use in number-crunching.

Like, say, operator overloading.

So what's all this exasperated rant and the "sorries" about? It's not like anything of value was lost. 

Merely a programming language and a community with specific needs do not match. 

If another language fits number-crunching better, use that. Not all languages have to be one size fits all.

[Norman Yarvin]

On Tue, Aug 27, 2013 at 01:31:27PM -0700, John Nagle wrote:
>On 8/27/2013 1:03 PM, Jsor wrote:
>> IMO, the real reason to have matrices built in is because matrices are a
>> numeric type just as real as floats and ints. At least +, -, and * are well
>> defined and should be implemented at the language level because it makes
>> math (much, much) more readable and follows the well established
>> conventions for dealing with matrices. I mean, unless you've been doing
>> polish notation all your life, I guess.
>
> That's going to be a big point of controversy. How general should
>"*" be? N-dimensional array and slice multiplication? That's a lot
>of code in the general case. It's a form of built-in operator
>overloading. And there's no way for an operator to return an error,
>short of "panic".
>
> On the other hand, the only things that can go wrong for +, -, and
>* are size mismatches, which are a form of subscript error. Go already
>generates subscript error aborts. The expected behavior of these
>operators is well-understood. We don't have the Python problem that
>"+" is considered concatenation for built-in arrays, but addition for
>NumPy arrays. Go doesn't have legacy overloads like that to cause
>trouble.

Even so, there is a bit of a problem with fitting arithmetic
operations on slices into the language. If you write

A = B

with A and B being slices (either one-dimensional or some extension to
multiple dimensions), then that's a pointer assignment: the data in
the slice doesn't get copied, just the pointer to it, plus the other
slice information. Which makes it a bit incongruous for

A = B + C

to be an operation that does an element-by-element addition. You
might alter the latter statement by removing C ("Oh, on reflection I
didn't want to add in C after all"), and instead of getting the
expected element-by-element copy, get a pointer copy, where now A and
B point to the same location in memory, so changing the elements of A
alters the elements of B and vice versa. Or if you altered the
statement in the reverse direction, you'd need to make sure that A had
already been allocated and that was is room in it for the elements
that were to be placed there.

This stuff violates the principle of minimum surprise. Various
languages have ugliness like this, and people do cope with it, but
it's annoying even if you do know what you're doing. We should avoid
it. In this case that might mean introducing another assignment
operator which would mean "copy the contents", so that, say

A = B

would mean a pointer assignment but

A === B

would mean a copy and

A === B + C

would mean an element-by-element addition. But how this would fit
into the rest of the language is unclear at first glance. (Would you
also want a :=== operator? And besides the meaning for numbers, would
you want === for anything else?)

[Nico]

This a very good point, but I'd argue that problem is not the
assignment, but the operation itself.

When I write A + B, I'm expecting the result to stored in a new object.

[John Nagle]

On 8/31/2013 9:25 AM, Norman Yarvin wrote:> Even so, there is a bit of a

problem with fitting arithmetic
> operations on slices into the language. If you write
>
> A = B
>
> with A and B being slices (either one-dimensional or some extension to
> multiple dimensions), then that's a pointer assignment: the data in
> the slice doesn't get copied, just the pointer to it, plus the other
> slice information.

Yes, there are some type system problems. Here, what
happens is dependent on the type of the left side. See

http://play.golang.org/p/MQ0kE5kZQn

In that example, "tab2 = tab1" is an fully array copy,
but "itab2 = itab1" is a slice reference update. Yet

So if A is an array, there is a array copy. If A is a slice, it's
a reference update. This is invisible at the point of assignment.
This, as you point out, violates the principle of "minimum
surprise". That's part of Go now.

> Which makes it a bit incongruous for
> A = B + C
> to be an operation that does an element-by-element addition.

Here, "B + C" is an internal temporary, which has
to be created new. This is unambiguous, regardless of
the semantics of "=".

> This stuff violates the principle of minimum surprise.

True, but that's a problem in slice/array assignment
Go already has. It's no worse than what we have now.
Given that Go programmers have to be aware of slice semantics now,
this doesn't make things worse.

> ... introducing another assignment
> operator which would mean "copy the contents"...

There's already "copy()" for that. We'd probably want to define,
in some common matrix package, utility functions like

func Dup1(a []float64) []float64;
func Dup2(a [,]float64) [,]float64;
func Dup3(a [,,]float64) [,,]float64;
...

to make it easy to duplicate arrays within a single expression.
New syntax doesn't seem to be necessary. There's lots of syntactic
sugar that could be provided for matrix math, but it's not absolutely
necessary, and is probably best left out at this stage.

(This would be a little easier if Go had read-only attributes
for types other than channels. If you can't write it, it's
less of an issue whether it's a copy. This is an issue for
more than matrix operations; it comes up when a slice is
sent to a goroutine, invisibly producing a shared variable
across a concurrency boundary. But that's another topic.)

John Nagle

[Norman Yarvin]

On Sat, Aug 31, 2013 at 12:53:27PM -0700, John Nagle wrote:

>On 8/31/2013 9:25 AM, Norman Yarvin wrote:
>> Even so, there is a bit of a problem with fitting arithmetic
>> operations on slices into the language. If you write
>>
>> A = B
>>
>> with A and B being slices (either one-dimensional or some extension to
>> multiple dimensions), then that's a pointer assignment: the data in
>> the slice doesn't get copied, just the pointer to it, plus the other
>> slice information.
>
> Yes, there are some type system problems. Here, what
>happens is dependent on the type of the left side. See
>
> http://play.golang.org/p/MQ0kE5kZQn
>
>In that example, "tab2 = tab1" is an fully array copy,
>but "itab2 = itab1" is a slice reference update. Yet
>
> So if A is an array, there is a array copy. If A is a slice, it's
>a reference update. This is invisible at the point of assignment.
>This, as you point out, violates the principle of "minimum
>surprise". That's part of Go now.

Still, for the variables' types to completely change assignment
behavior seems less surprising than for the presence or absence of an
addition to completely change assignment behavior. And the existence
of one ugly piece of syntax doesn't justify adding more.

>> Which makes it a bit incongruous for
>> A = B + C
>> to be an operation that does an element-by-element addition.
>
> Here, "B + C" is an internal temporary, which has
>to be created new. This is unambiguous, regardless of
>the semantics of "=".

Perhaps formally, but in practice there's no need for a temporary: the
operation can just be done element by element, putting each new
element in A as it is computed. That's true not just for this simple
expression but also any expression involving only matrix/vector
addition and subtraction. Multiplication by scalars and addition of a
scalar (to each element of a vector or matrix) can be added to the mix
without changing this. You can even throw in a single matrix multiply
without needing a temporary array. It's only for products of three
matrices/vectors (e.g. D=A*B*C) that temporary storage starts really
being needed.

Nevertheless, if you mean to imply that you would have the operation
A=B+C always be implemented via:

1. a new temporary variable is allocated
2. it gets filled with B+C
3. it gets assigned to A

then yes, this would solve the problem of surprise, because then the
assignment operator for slices would always be a pointer operation,
never a copy operation.

That seems unsatisfactory, though, since if this were in a loop, it
would mean repeatedly allocating new storage for A, even if there were
no reason to do so. That would unnecessarily stress the garbage
collector and the cache. The allocation couldn't easily be optimized
away, since some other code which saw A might retain a pointer to the
storage underlying one or more versions of A. While ugly syntax is
bad, I still prefer it to bad behavior behind the scenes.

>> ... introducing another assignment
>> operator which would mean "copy the contents"...
>
> There's already "copy()" for that. We'd probably want to define,
>in some common matrix package, utility functions like
>
> func Dup1(a []float64) []float64;
> func Dup2(a [,]float64) [,]float64;
> func Dup3(a [,,]float64) [,,]float64;
> ...
>
>to make it easy to duplicate arrays within a single expression.
>New syntax doesn't seem to be necessary.

Well, not just for the purposes of making copies. But while it's not
good to duplicate the existing copy(), a simple duplication in
language features is better than syntax that surprises people, like a
situation where appending an addition to an assignment statement
completely changes the meaning of that statement. It's complexity,
not mere bulk, that makes languages hard to learn and use.

[John Nagle]

On 8/31/2013 6:00 PM, Norman Yarvin wrote:
> On Sat, Aug 31, 2013 at 12:53:27PM -0700, John Nagle wrote:
>>
>>
>> On 8/31/2013 9:25 AM, Norman Yarvin wrote:> Even so, there is a bit of a
>> problem with fitting arithmetic
>>> operations on slices into the language. If you write

> Nevertheless, if you mean to imply that you would have the operation
> A=B+C always be implemented via:
>
> 1. a new temporary variable is allocated
> 2. it gets filled with B+C
> 3. it gets assigned to A
>
> then yes, this would solve the problem of surprise, because then the
> assignment operator for slices would always be a pointer operation,
> never a copy operation.
>
> That seems unsatisfactory, though, since if this were in a loop, it
> would mean repeatedly allocating new storage for A, even if there were
> no reason to do so. That would unnecessarily stress the garbage
> collector and the cache. The allocation couldn't easily be optimized
> away, since some other code which saw A might retain a pointer to the
> storage underlying one or more versions of A.

That's a fairly common compiler optimization - noting that
a function return value is being created as a temporary,
then copied, and using the destination object instead of the
temporary. See
"https://en.wikipedia.org/wiki/Return_value_optimization".
Go has an advantage over C++ here in that there's no
such thing as a Go copy constructor with side effects.
I don't know if the Go compilers do this for function
returns, but they certainly could.

On modern CPUs, adding complexity to avoid copying
is often not a big win, and may be a lose. Copying
recently-accessed contiguous data is cheap - it's
probably in the cache. This applies to both
Go channels and message-passing microkernels.

John Nagle

[Norman Yarvin]

On Sat, Aug 31, 2013 at 10:04:06PM -0700, John Nagle wrote:
>On 8/31/2013 6:00 PM, Norman Yarvin wrote:
>
>> Nevertheless, if you mean to imply that you would have the operation
>> A=B+C always be implemented via:
>>
>> 1. a new temporary variable is allocated
>> 2. it gets filled with B+C
>> 3. it gets assigned to A
>>
>> then yes, this would solve the problem of surprise, because then the
>> assignment operator for slices would always be a pointer operation,
>> never a copy operation.
>>
>> That seems unsatisfactory, though, since if this were in a loop, it
>> would mean repeatedly allocating new storage for A, even if there were
>> no reason to do so. That would unnecessarily stress the garbage
>> collector and the cache. The allocation couldn't easily be optimized
>> away, since some other code which saw A might retain a pointer to the
>> storage underlying one or more versions of A.
>
> That's a fairly common compiler optimization - noting that
> a function return value is being created as a temporary,
>then copied, and using the destination object instead of the
>temporary.

In this case, however, that particular optimization does not apply,
since instead of the final destination for the contents of the slice
always being the memory that A points to, it would be a new area,
which A would then point to.

But what I'm getting from this reply is that you really had no thought
of suggesting such a disgusting mechanism for solving the problem of
programmer surprise.

[John Nagle]

Again, it's more of a generic Go problem, in that you can't
tell by looking at a call whether you're getting a reference
or a value as a result.

One way around this problem is to use ":=" heavily. The
":=" operator in Go reduces the incentive to re-use variable
names. Writing in a more math-like style, where variable names
are not reused, helps to avoid confusion in this area.

"A := B*C" is optimizable, whether A,B and C are slices
or arrays.

John Nagle

[gta]

My 2 cent,

since there is still not a well defined proposal, and a lot of emails and documents have been spent, why not start again smaller.

I read some of the discussions and documents and the impression that I got from them is: let's try to include all the features we can think of.

Would someone be interested in a much smaller proposal?

 

An only 2 dimension matrix type.

A matrix a value type as an array and the dimensions are part of its type.

No slicing or appending.

Operators (+, -, *,...) overloaded in case of matrix of numeric types, it might be good to have matrix of any type e.g. images.

Some helper builtin functions to have some information on the type such as len(), dim(), stride() and whatnot.

No reshaping, but maybe functions to get/set rows and columns as array/slices because we have 1D types already so we know how to deal with them.

I believe something like this might bear its weight, many matrices operations are with 2D matrices anyways.

If this get into the language we have something to play with and to get some insight for the next steps. 

How to slice in 2D? 

Do we need append?

What else are we missing? Inverse? Determinant? Eigenvalues? Eigenvectors?

Should we have builtins or a package like strings?

Does this make any sense at all? Am I barking mad?

[Nico]

I suggest having a look at the following doc:

https://docs.google.com/document/d/1gejfouITT25k29eHYTgdvi4cCLVt5dhYiJVvF46gp78/edit?usp=sharing

It's early times, but some good points have already been discussed.

[Michael Jones]

That's seemed the natural outcome of the other discussion. I would leave out all the higher-level actions (inverse, determinant, etc.) because you'd want many different versions based on higher-level knowledge about the matrix (band symmetric, sparse, ...)

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Robert Johnstone]

 I'm very receptive to everyone working on this topic, as I do quite a bit of numerical modelling (although not in Go).  However, I'm not certain if this proposal will carry its weight.  If you want to provided support for numerical computing, will dense matrices be enough?  As Michael Jones mentioned, quite a few different structures are used to store matrices based on their properties.  I don't have a clear picture of the minimum support required to foster a numerical community in Go, but the issue will need to be addressed.

[John Nagle]

On 9/4/2013 8:15 AM, gta wrote:
> My 2 cent,
> since there is still not a well defined proposal, and a lot of emails and
> documents have been spent, why not start again smaller.
> I read some of the discussions and documents and the impression that I got
> from them is: let's try to include all the features we can think of.
>
> Would someone be interested in a much smaller proposal?
>
> An only 2 dimension matrix type.
> A matrix a value type as an array and the dimensions are part of its type.
> No slicing or appending.

That would be useful for game development and graphics, where
you use lots of fixed-size 4x4 and smaller matrices. It doesn't allow
conversion of common libraries like LAPACK, BLASS, Numeric Recipes,
etc.

Number of dimensions is less of an issue for syntax and
implementation than slicing and appending.

The main argument for slices is that standard math libraries work on
arrays of different sizes. You don't want to have a different copy
of "invert matrix" for each array size. In Go, slicing is tied to
passing a variable-sized array as a parameter. We need the latter,
and are thus forced to support the former.

> Operators (+, -, *,...) overloaded in case of matrix of numeric types, it
> might be good to have matrix of any type e.g. images.
> Some helper builtin functions to have some information on the type such as
> len(), dim(), stride() and whatnot.
> No reshaping, but maybe functions to get/set rows and columns as
> array/slices because we have 1D types already so we know how to deal with
> them.

Reshaping can easily get too complex. Some of the proposals
slow down element access to speed up reshaping. That's probably
not a win.

> I believe something like this might bear its weight, many matrices
> operations are with 2D matrices anyways.
> If this get into the language we have something to play with and to get
> some insight for the next steps.

> What else are we missing? Inverse? Determinant? Eigenvalues? Eigenvectors?

Those are library functions.

> Should we have builtins or a package like strings?

Strings are a built-in with a standard support library. It's
probably helpful to have a library with a few standard functions for
which the algorithm is standard (max, min, average, determinant, etc.)

> Does this make any sense at all? Am I barking mad?

It's helpful.

John Nagle

[John Nagle]

On 9/4/2013 9:21 AM, Robert Johnstone wrote:
> I'm very receptive to everyone working on this topic, as I do quite a bit
> of numerical modelling (although not in Go). However, I'm not certain if
> this proposal will carry its weight. If you want to provided support for
> numerical computing, will dense matrices be enough?

At the language level, dense matrices are probably enough. Sparse
matrix representations are complex and problem-dependent, and more
suited to a library.

Here's a discussion of four types of sparse matrices already
supported in Boost for C++:

http://www.guwi17.de/ublas/matrix_sparse_usage.html

This is way too complex to bolt into Go at the language level.

John Nagle

[Kevin Gillette]

On Wednesday, September 4, 2013 11:01:09 AM UTC-6, John Nagle wrote:

At the language level, dense matrices are probably enough.  Sparse 
matrix representations are complex and problem-dependent, and more 
suited to a library.

There are already precedents for this kind of decision in Go. For example, we have a builtin general map type that has no customization options for its internal structure.

[Gerard]

On Wednesday, September 4, 2013 6:55:39 PM UTC+2, John Nagle wrote:

    The main argument for slices is that standard math libraries work on
arrays of different sizes.  You don't want to have a different copy
of "invert matrix" for each array size.  In Go, slicing is tied to
passing a variable-sized array as a parameter.  We need the latter,
and are thus forced to support the former.

Funny, this functionality can be tricked (2D matrix only) with a regular slice. With len() as the width or height of the matrix and cap() as width x height.

[Volker Dobler]

Am Mittwoch, 4. September 2013 17:15:50 UTC+2 schrieb gta:

My 2 cent,

since there is still not a well defined proposal, and a lot of emails and documents have been spent, why not start again smaller.

I read some of the discussions and documents and the impression that I got from them is: let's try to include all the features we can think of.

Would someone be interested in a much smaller proposal?

[...] 

Does this make any sense at all? Am I barking mad?

I read those proposal and tried to follow the discussion and I feel

the same.

What I am missing most is a discussion about what type of

(highlevel) problem should be solved:  The "slice-of-slice-of..."

trick for multidimensional data has drawbacks, but a simple

"overcome the slice-of-slice... drawback" is IMHO not a

suitable understanding of a problem which requires a language

change.

Cui bono? What type of problems are we trying to solve?

 - 3d graphics (gaming)

 - Linear algebra

 - Quantum mechanics

 - Graph algorithms

 - Statistics

 - "Big data" (sorry)

 - Tensor algebra

 - Joe Average's 

Huge, complex, banded matrices are common on QM,

while 3d graphics is most about small, real, dense matrices,

graph algorithm might benefit from sparse boolean matrices,

tensor algebra for AR requires 4 dimensions, statistics

might use m x n matrices with m << n while in basic linear

algebra often m ~ n. And Joe Average might just be happy

if he can set up a table like data structure with 10 keystrokes.

No size will fit all (not taking the Fortran road).

Arguably linear algebra stuff like eigenvalues, determinate,

QR decomposition, and that like is so common, that

language assistance for the underlying data structures

seem justifiable. Which support your proposal.

What is the intersection of all "common" usecases for

multidimensional data?

I think something very simple might be beneficial to package

developers in all above topics:

 - n-dimensional, homogeneous, dense data structure

 - 1 <= n <= 8 (or any other small constant)

 - dimensionality and element type is part of the type...

 - ...but extensions (length) in each dimension are not

 - no append, grow or that like

 - range over all elements in memory order

 - nice element access like d[i,j,k]

 - possibility to extract (n-1) dimensional part from n-dim

   data.

Everything else goes into some package. I.e. no operator

overloading for multidimensional data but a package matrix

with matrix.Add.

This is also a smaller proposal with slightly different focus

than yours (higher dimensions, less operator overloading).

V.

 

[John Nagle]

On 9/4/2013 1:27 PM, Volker Dobler wrote:

> What I am missing most is a discussion about what type of
> (highlevel) problem should be solved: The "slice-of-slice-of..."
> trick for multidimensional data has drawbacks, but a simple
> "overcome the slice-of-slice... drawback" is IMHO not a
> suitable understanding of a problem which requires a language
> change.
>
> Cui bono? What type of problems are we trying to solve?
> - 3d graphics (gaming)
> - Linear algebra
> - Quantum mechanics
> - Graph algorithms
> - Statistics
> - "Big data" (sorry)
> - Tensor algebra
> - Joe Average's
>
> Huge, complex, banded matrices are common on QM,
> while 3d graphics is most about small, real, dense matrices,
> graph algorithm might benefit from sparse boolean matrices,
> tensor algebra for AR requires 4 dimensions, statistics
> might use m x n matrices with m << n while in basic linear
> algebra often m ~ n. And Joe Average might just be happy
> if he can set up a table like data structure with 10 keystrokes.

3D graphics is mostly about 4x4 matrices. Graphics boards
have hardware for that, but sometimes you need to do it on the
main CPU as well when you're moving objects around. So
dense, small matrices should be well supported. If CPU
features like MMX can be used, that's when to use them.
I do a lot of this sort of thing myself; I'm working on
robot dynamics now and used to work on physics engines
for animation and games.

Linear algebra underlies lots of other number crunching.
If we can translate LINPACK, BLAS, and Numerical Recipes to
Go and have them run almost as fast as C (maybe faster;
the hacks to make 2D arrays in C slow things down) we're
doing it right.

Sparse, banded, and symmetric matrices usually require
domain-specific code. I'm not sure about going there
at the language level. Some kinds of sparse matrices work
like maps, but hashed maps are inefficient to traverse
in order. So mapping sparse matrices to Go's map type
seems a bad fit.

> What is the intersection of all "common" usecases for
> multidimensional data?

Everybody who does number-crunching wants 2D matrices.
After that, what people want varies.

> I think something very simple might be beneficial to package
> developers in all above topics:

> - n-dimensional, homogeneous, dense data structure

Yes.

> - 1 <= n <= 8 (or any other small constant)

That makes sense, because some library functions
are going to have to be implemented for each
dimension.

> - dimensionality and element type is part of the type...
> - ...but extensions (length) in each dimension are not

Since Go has both arrays and slices, those concepts
should be present for higher dimensions.

> - no append, grow or that like

If the slice representation can accommodate it, why not?

> - range over all elements in memory order

That's a "flatten" function. It's probably useful
simply so you can do I/O and marshaling.

> - nice element access like d[i,j,k]

Yes.

> - possibility to extract (n-1) dimensional part from n-dim
> data.

This is worth allowing for the cases that the slice
representation can handle directly. For example,

arr[n,:]
and
arr[:,n]

are not equally easy to do. If the slice representation
has a "stride" even for the most dense subscript, both
of these are possible but there is a speed penalty on
simple indexing of regular 1D arrays, because they
now need a "stride". That is probably a bad trade.

If we have a multidimensional slice representation
which has the same representation as at present for
1D arrays and has a length and stride for each higher
dimension, that implicitly defines what subarray
and reslice operations are possible. That
means "arr[n,:]" is OK and returns a 1D slice,
but "arr[:,n]" is not allowed.

> Everything else goes into some package. I.e. no operator
> overloading for multidimensional data but a package matrix
> with matrix.Add.
>
> This is also a smaller proposal with slightly different focus
> than yours (higher dimensions, less operator overloading).

Operator overloading is controversial. Numpy uses a
"dot()" function for matrix multiply. "*" is an element by element
multiply. One argument for matrix multiply at the language level
is that it is both very common, and very optimizable when you have
size information available. What's thinking about this from
the implementers?

John Nagle

[Kyle Lemons]

I would be really disappointed if we had an implementation that couldn't stride the densest dimension.  The final stride should be able to be optimized away in some cases.

 

        If we have a multidimensional slice representation
        which has the same representation as at present for
        1D arrays and has a length and stride for each higher
        dimension, that implicitly defines what subarray
        and reslice operations are possible.  That
        means "arr[n,:]" is OK and returns a 1D slice,
        but "arr[:,n]" is not allowed.

> Everything else goes into some package. I.e. no operator
> overloading for multidimensional data but a package matrix
> with matrix.Add.
>
> This is also a smaller proposal with slightly different focus
> than yours (higher dimensions, less operator overloading).

        Operator overloading is controversial.  Numpy uses a
"dot()" function for matrix multiply.  "*" is an element by element
multiply.  One argument for matrix multiply at the language level
is that it is both very common, and very optimizable when you have
size information available.  What's thinking about this from
the implementers?

                                John Nagle

[Kevin Gillette]

On Wednesday, September 4, 2013 5:03:03 PM UTC-6, Kyle Lemons wrote:

I would be really disappointed if we had an implementation that couldn't stride the densest dimension.  The final stride should be able to be optimized away in some cases.

Please explain what you mean by "stride the densest dimension". 

[Kyle Lemons]

Make a slice of a N-dim array where only some of the densest (i.e. last) dimension are included.

var a [2,2]

b := a[:, 0] // <-- this one

c := a[0, :]

It would be incongruous if one of the above was allowed and the other was not.

--

[Kevin Gillette]

Ah

[Dan Kortschak]

Yes, you really want an ndslice being defined as something like:

struct {
data *T
cap int
dims [n]int
strides [n]int
}

where prod(dims) and prod(strides) <= cap and n is the dimensionality of
the ndslice, coming from a [m][o][p]...nT (which is already part of the
language).

Just having that would make much of the rest of the desires relatively
easy to implement in libraries and would give a significant performance
boost on ranging over 2nd and subsequent dimensions (I really don't see
adding all the operators to types like this as being a good thing).

Dan

[Kevin Gillette]

I'm interested to know what the use cases would be for appending to a multidimensional slice. I feel that capacity in a regular slice is a beneficial and simple artifact of the most sensible slice implementation. Capacity in a multidimensional slice is not simple, and for the typical use-cases of nd-slices that I can think of (e.g. matrix math), appending wouldn't even be useful. Reallocation would have comparatively bizarre semantics, since the shape of the new backing array would often be very distinct from the shape of the original backing array. Take for example:

m0 := [3,3]int{{1,2,3},{4,5,6},{7,8,9}}

m1 := m0[:, 1:2] // produces [,]int{{2}, {5}, {8}}

m1 = append(m1, [1,1]int{11}) // er, how do we even specify this?

would, from a sensible implementation perspective, result in a new backing array of [4,1]int, rather than what some people, viewing it from a sensible semantic perspective, would expect to be a backing array of [4,3]int. The semantic perspective would be useful since you could immediately perform a single column append to m1 without triggering a second reallocation, based on the assumption that you have the space for it if, semantically, the shape were maintained in as many dimensions as possible when any shape changing operation occurred -- if you did the column append before the row append, it'd certainly work from either perspective in this example, since only the row append in this case would then result in the reallocation.

Speaking of column appends (and other appends of lower dimensional data), what would the append expression for that look like?

The copy builtin implementation would have to gain odd semantics as well, since the behavior for normal slices will never panic, but what if you're trying to copy from a [15]int into a [4,4]int? Or a [17]int into a [4,4]int?

[Kyle Lemons]

On Wed, Sep 4, 2013 at 5:52 PM, Kevin Gillette <extempor...@gmail.com> wrote:

I'm interested to know what the use cases would be for appending to a multidimensional slice. I feel that capacity in a regular slice is a beneficial and simple artifact of the most sensible slice implementation. Capacity in a multidimensional slice is not simple, and for the typical use-cases of nd-slices that I can think of (e.g. matrix math), appending wouldn't even be useful. Reallocation would have comparatively bizarre semantics, since the shape of the new backing array would often be very distinct from the shape of the original backing array. Take for example:

I wouldn't allow appends.  While we call them slices here, I think they would rightly have a better name (matrix view?) because they're actually rather different.

 

m0 := [3,3]int{{1,2,3},{4,5,6},{7,8,9}}

m1 := m0[:, 1:2] // produces [,]int{{2}, {5}, {8}}

m1 = append(m1, [1,1]int{11}) // er, how do we even specify this?

would, from a sensible implementation perspective, result in a new backing array of [4,1]int, rather than what some people, viewing it from a sensible semantic perspective, would expect to be a backing array of [4,3]int. The semantic perspective would be useful since you could immediately perform a single column append to m1 without triggering a second reallocation, based on the assumption that you have the space for it if, semantically, the shape were maintained in as many dimensions as possible when any shape changing operation occurred -- if you did the column append before the row append, it'd certainly work from either perspective in this example, since only the row append in this case would then result in the reallocation.

Speaking of column appends (and other appends of lower dimensional data), what would the append expression for that look like?

The copy builtin implementation would have to gain odd semantics as well, since the behavior for normal slices will never panic, but what if you're trying to copy from a [15]int into a [4,4]int? Or a [17]int into a [4,4]int?

I'd similarly only allow copying between slices with identical dimensions.

 

On Wednesday, September 4, 2013 6:26:35 PM UTC-6, kortschak wrote:

Yes, you really want an ndslice being defined as something like:

struct {
        data    *T
        cap     int
        dims    [n]int
        strides [n]int
}

where prod(dims) and prod(strides) <= cap and n is the dimensionality of
the ndslice, coming from a [m][o][p]...nT (which is already part of the
language).

Just having that would make much of the rest of the desires relatively
easy to implement in libraries and would give a significant performance
boost on ranging over 2nd and subsequent dimensions (I really don't see
adding all the operators to types like this as being a good thing).

Dan

On Wed, 2013-09-04 at 16:03 -0700, Kyle Lemons wrote:
> I would be really disappointed if we had an implementation that
> couldn't stride the densest dimension.  The final stride should be
> able to be optimized away in some cases.

[Dan Kortschak]

On Wed, 2013-09-04 at 17:52 -0700, Kevin Gillette wrote:
> I'm interested to know what the use cases would be for appending to a
> multidimensional slice. I feel that capacity in a regular slice is a
> beneficial and simple artifact of the most sensible slice
> implementation.

I'm not convinced an append is meaningful here, but that doesn't
preclude the inclusion of a cap. It would take the implementation
towards something like what slices were before append was added; it
would allow resizing by reslicing (reshaping?) but the details would be
left up to the user.

I think you'll end up with a function that looks very much like the BLAS
Dcopy with incX and incY being taken from the relevant stride (or 1 if
the slice is a slice rather than an nd-slice) - the dimensionality must
match, so this would require a reshape.

fbf := make([4,4]int)
sl := make([]int, 17)

fl := reshape(fbf, 16) // makes a single dimension nd-slice backed by the same array.
copy(fl, sl) // returns 16, having filled the fbf backing array (row majorly presumably).

similarly

fbf := make([4,4]int)
sl := make([]int, 5)

copy(fbf[:,], sl) // returns 4, the first 4 elements of sl having been copied into the first dimension of fbf.

You can determine the dimensionality of the nd-slice at compile time
since it's part of the type (the dims/strides fields are arrays not
slices), so you fail at compile time if these don't match.

Dan

[Kevin Gillette]

On Wednesday, September 4, 2013 7:02:00 PM UTC-6, Kyle Lemons wrote:

I wouldn't allow appends.  While we call them slices here, I think they would rightly have a better name (matrix view?) because they're actually rather different.

I'd similarly only allow copying between slices with identical dimensions.

I personally agree with imposing both of these restrictions. That said, even copying between nd-slices with identical exposed shapes could have unpredictable timing. For example, copying from a [3000,3000]int to another [3000,3000]int would have considerably different timing than copying from a [3e5,3e5]int{}[:3000,:3000] to a [3000,3000]int -- backing array size does not make a difference when copying between contiguous slices (as the time required will always be linear to the size of the smallest slice).

[Kyle Lemons]

I think it's O(kN) in all cases, but k is a lot smaller when both input and output are contiguous and thus can be memcpy'd, right? 

[Kevin Gillette]

On Wednesday, September 4, 2013 7:15:58 PM UTC-6, kortschak wrote:

I'm not convinced an append is meaningful here, but that doesn't
preclude the inclusion of a cap. It would take the implementation
towards something like what slices were before append was added; it
would allow resizing by reslicing (reshaping?) but the details would be
left up to the user.

Strictly speaking, cap isn't necessary for that as long as you keep around a slice containing both the shape you were working with and the shape you now want. Since cap setting is already in the "let's try it out and see" phase, it's clear that enough people want to limit capacity for various reasons in their applications.

I put forth that the same situation is exponentially more important here: under what circumstances would you, semantically, 1) prefer to "grow" a sub-slice through reslicing into the cap instead of 2) "shrink" the containing slice into the desired shape? #2 has the benefit that you can always be sure it will work (a slice of shape [x,y,z] can always be shrunk into shape [p,q,r] provided that (p <= x && q <= y && r <= z), and the application is already much more likely to know about the lengths of dimensions than they are to know about the caps. Also, most of the multidimensional slice proposals I've seen are concerned with semantics rather than syntax, so it's unclear that there'll be a clean way to get per-dimension lengths and caps. If we use the straightforward approach, of treating nd-slices like slices of slices, then we'd likely need the reflect package (which would be unfortunate) to work with matrices of unknown dimensionality.

Unlike slices of slices, it would seem reasonable that there is no intermediate level element type -- you specify [2,2]int{1,2,3,4} instead of [2,2]int{{1,2},{3,4}}. Perhaps len and cap would thus need to be extended to accept a dimension parameter, only valid for nd-slices, so that to get the length of the first dimension, instead of len(x), you do len(x, 0), and to get the cap of the second dimension, instead of len(x[0]), you do len(x, 1) -- to query the dimensionality of an nd-slice, a new builtin 'dim' could be created, or perhaps, in line with extending the len builtin, len(x) would return the dimensionality of an nd-slice, rather than, as with slices of slices, the length of its first dimension.

[Kevin Gillette]

On Wednesday, September 4, 2013 7:39:12 PM UTC-6, Kyle Lemons wrote: 

I think it's O(kN) in all cases, but k is a lot smaller when both input and output are contiguous and thus can be memcpy'd, right?

Yes, the theoretical complexity would be identical. You'd just be dealing with potentially many memcpy's in the moderate case, and no memcpys in the worst case, unless there's some simd instruction for strided-in to nonstrided-out, such as with

copy([3e10,1]int{}[:], [3e10,3e10]int{}[:,0:1])

[Dan Kortschak]

On Wed, 2013-09-04 at 18:56 -0700, Kevin Gillette wrote:
> Strictly speaking, cap isn't necessary for that as long as you keep
> around a slice containing both the shape you were working with and the
> shape you now want. Since cap setting is already in the "let's try it
> out and see" phase, it's clear that enough people want to limit
> capacity for various reasons in their applications.

I'm not sure about this. And thinking about it more makes me uneasy.

Say you have a [n][m]T and you ndslice that, allowing you to reshape the
ndslice and now you could have a view on to a [k][l]T where k*l <= n*m
but which doesn't actually exist as a declared type. I'm not sure how
much of a problem this is.

> I put forth that the same situation is exponentially more important
> here: under what circumstances would you, semantically, 1) prefer to
> "grow" a sub-slice through reslicing into the cap instead of 2)
> "shrink" the containing slice into the desired shape? #2 has the
> benefit that you can always be sure it will work (a slice of shape
> [x,y,z] can always be shrunk into shape [p,q,r] provided that (p <= x
> && q <= y && r <= z), and the application is already much more likely
> to know about the lengths of dimensions than they are to know about
> the caps.

I don't really understand what you are getting at here. Sorry. I can see
very good reasons for keeping a workspace matrix around for performing
operations in, this may entail reslicing to larger than the current size
(but within the cap). (Note I was not suggesting - though now I'm less
sure - having more than one cap value per ndslice).

> Also, most of the multidimensional slice proposals I've seen are
> concerned with semantics rather than syntax, so it's unclear that
> there'll be a clean way to get per-dimension lengths and caps. If we
> use the straightforward approach, of treating nd-slices like slices of
> slices, then we'd likely need the reflect package (which would be
> unfortunate) to work with matrices of unknown dimensionality.

Yes, I don't think this is the way to go.

>
> Unlike slices of slices, it would seem reasonable that there is no
> intermediate level element type -- you specify [2,2]int{1,2,3,4}
> instead of [2,2]int{{1,2},{3,4}}.

I think this would be a bad idea for safety.

> Perhaps len and cap would thus need to be extended to accept a
> dimension parameter, only valid for nd-slices, so that to get the
> length of the first dimension, instead of len(x), you do len(x, 0),
> and to get the cap of the second dimension, instead of len(x[0]), you
> do len(x, 1) -- to query the dimensionality of an nd-slice, a new
> builtin 'dim' could be created, or perhaps, in line with extending the
> len builtin, len(x) would return the dimensionality of an nd-slice,
> rather than, as with slices of slices, the length of its first
> dimension.

len() returns an int though. Either a new builtin or a variadic len().

[Kyle Lemons]

my vague idea would be for a dim() builtin that returns a [...]int, so that dim(a)[0] can be compile-time bounds-checked 

[Dan Kortschak]

On Wed, 2013-09-04 at 19:23 -0700, Kyle Lemons wrote:
> my vague idea would be for a dim() builtin that returns a [...]int, so
> that dim(a)[0] can be compile-time bounds-checked

Does that mean you could say const d = len(dim(a))?

[Kyle Lemons]

You can't define constants to things that are not consts, so it would have to be `const dims = len(dim([4,3,3]int{}))`, but yes, for the same reason you can say `const length = len([10]int{})`.  In particular this would be useful for `type Matrix [4,4]int; const Dims = len(dims(Matrix{}))` and such.

[Dan Kortschak]

On Wed, 2013-09-04 at 19:38 -0700, Kyle Lemons wrote:
> You can't define constants to things that are not consts, so it would
> have to be `const dims = len(dim([4,3,3]int{}))`, but yes, for the
> same reason you can say `const length = len([10]int{})`. In
> particular this would be useful for `type Matrix [4,4]int; const Dims
> = len(dims(Matrix{}))` and such.
>

So can you compile code that says dim(a) == dim(b)? Presumably not.

[Kevin Gillette]

On Wednesday, September 4, 2013 8:14:55 PM UTC-6, kortschak wrote:

On Wed, 2013-09-04 at 18:56 -0700, Kevin Gillette wrote: 
> Unlike slices of slices, it would seem reasonable that there is no 
> intermediate level element type -- you specify [2,2]int{1,2,3,4} 
> instead of [2,2]int{{1,2},{3,4}}. 

I think this would be a bad idea for safety. 

I don't see how this could be "unsafe".

 

len() returns an int though. Either a new builtin or a variadic len(). 

What I'm talking about would still return an int.

len([3,2]int, 0) // returns 3

len([3,2]int, 1) // returns 2

[Kevin Gillette]

On Wednesday, September 4, 2013 8:23:15 PM UTC-6, Kyle Lemons wrote:

my vague idea would be for a dim() builtin that returns a [...]int, so that dim(a)[0] can be compile-time bounds-checked 

If these proposals don't also produce the concept of a first-class n-dimensional type with a runtime determinable n, then I don't see much point in the whole thing. And of course, not only would a runtime determinable number of dimensions not benefit from such a compile time check, your dim builtin would have to return an []int rather than an [...]int.

[Dan Kortschak]

On Wed, 2013-09-04 at 19:58 -0700, Kevin Gillette wrote:
> I don't see how this could be "unsafe".

Not unsafe in the Go sense, unsafe in the real world sense where humans
interact with machines via the written code. Just the same way that
semantically laden white space in python is unsafe. Adding the extra
checks on rows ensures that errors in coding are more easily
found/localised.

>
> > len() returns an int though. Either a new builtin or a variadic
> len().
> >
>
> What I'm talking about would still return an int.
>
> len([3,2]int, 0) // returns 3
>
> len([3,2]int, 1) // returns 2
>

Yeah, I was clear with that. I agree - this make len() variadic though,
which was my point (the alternative being Kyle's dim()).

[Kyle Lemons]

Quite the contrary.  The compiler must know the number of dimensions in the type, so the type of the array (eg [4]int) returned by dim(a) is known at compile time.  The contents, of course, are only known at runtime and thus the == cannot be compiled out, but arrays are comparable so that statement is not only valid but probably incredibly useful.

[Dan Kortschak]

OK. So that means you *can* always assign a constant with len(dim(a))
where a is an e.g. var [4,3,3]int{}. If you can't assign a constant then
you don't know the value at compile time. That was motivation for my
original query.

I guess this makes dim() a bit like unsafe.Sizeof.

[Kyle Lemons]

Sorry, I stand corrected.  I didn't think you could legally do this:

var a = [10]int{}

const b = len(a)

And, just to make matters worse, when I tried it out before responding, I managed to get my example wrong and thus confirmed my error :).

For the record, that is legal :).  Sorry about the noise.

[Dan Kortschak]

I think this is a noisy topic. Sometimes noise generates useful forward
motion.