How suitable Go will be for scientific computing?
Franz
scientific community still lacks a language which is
- small and easy to learn (scientists are not all
_computer_scientist_);
- portable;
- fast for number crunching and accurate (IEEE floating point
standard) ;
- concurrent (no need for OpenMP/MPI/Cuda etc...)
ANSI C (plus libraries) is the most suitable of a host of unsuitable
languages. C++ is too big and it takes a life time to master it. Java
lives in a virtual machine, therefore it is slow.
Some scripting languages (e.g. python+numpy) are very good, but only
when neither speed or concurrency is crucial.
From a cursory look it seems to me that Go might evolve into the
perfect high performance computing language for scientific use (in
addition to other uses, of course).
Am I wrong?
Is there some feature (or lack of it) that discourages making a time
investment in learning and deploying Go for scientific computing,
especially for large projects?
Is Go's concurrency model going to be inherently limited to shared-
memory machines, or can it be expanded to other types of parallel
architectures (e.g. clusters)?
Pat Notz
separate CPUs when launching MPI jobs and MPI is actually very
efficient about that (it uses shared memory when possible). However,
that really increases pressure on CPU cache and as we get to manycore
machines we'll have to move to a hybrid model with MPI for distributed
machines and threaded concurrency on each socket. (FLOPs are free.)
Goroutines seem incompatible with a distributed model. A hybrid
GO+MPI would be really interesting.
We will need portable bindings for C and Fortran. There's too much
money tied up in all those well tested and understood libraries.
Getting them re-written will take time and that will really only
happen if people first see Go as a viable language. Binding to
existing C/Fortran libs is the most expedient (only?) way to make that
happen. It doesn't have to be fancy -- most APIs are just passing
ints, floats and doubles (values, references and arrays).
Cuda/OpenCL could eventually be a layer below Go -- where goroutines
are launched on GPUs. (I'm dreaming here.)
OpenMP was always very limiting. It's useful in deep compute kernels
but not as a general concurrency paradigm.
Your reference to Python+Numpy is interesting... I really feel like Go
has potential to compete there. Go is almost as easy to code in as
Python and as the standard library grows and tools are built I could
actually see Go becoming easier than Python. (Python's main advantage
is you don't need a build tool.) Go's concurrency is much more
natural than Python and since Go is a static language we should
eventually see powerful IDEs (like the CDT for Eclipse) and static
analysis tools.
~ Pat
Ian Lance Taylor
> Is Go's concurrency model going to be inherently limited to shared-
> memory machines, or can it be expanded to other types of parallel
> architectures (e.g. clusters)?
The goroutine model is limited to shared-memory machines by design.
As ordinary processors get more and more cores, it's not appropriate
to use the same concurrency model on a single machine as on multiple
machines.
Go can support different concurrency models for multiple machines, but
the language provides no direct support for that.
Ian
Ryanne Dolan
For me, the big thing keeping Go from being my numerical language of choice is the absense of operator overloading. I abhore overloading in general, and I understand why user-defined operators are purposefully impossible in Go. Unfortunately, that makes manipulating complex numbers and matrices way more complicated than it should be.
In general I believe that operators should be restricted to built-in types so that operator behavior is always well-defined and obvious. The only potential solution I can think of is to augment Go with native support for matrices and complex numbers and provide operators to manipulate them. Then I'd use Go nearly exclusively.
I don't think native matrices are too far fetched either. We already have built-in maps (thank you!) and strings. I don't understand at all why + can mean append but not element-wise addition...
I was actually thinking of embedding a small interpreter into my programs so I can have infix expressions with custom operators.
result := infix.Eval(" A * B ")
...after registering what *, A, and B are.
Ryanne
- from my phone -
Ryanne Dolan
Shoot sorry, wish my phone had spell check. Now the whole world knows I can't spell...
- from my phone -
On Jan 14, 2010 1:21 PM, "Ryanne Dolan" <ryann...@gmail.com> wrote:For me, the big thing keeping Go from being my numerical language of choice is the absense of operator overloading. I abhore overloading in general, and I understand why user-defined operators are purposefully impossible in Go. Unfortunately, that makes manipulating complex numbers and matrices way more complicated than it should be.
In general I believe that operators should be restricted to built-in types so that operator behavior is always well-defined and obvious. The only potential solution I can think of is to augment Go with native support for matrices and complex numbers and provide operators to manipulate them. Then I'd use Go nearly exclusively.
I don't think native matrices are too far fetched either. We already have built-in maps (thank you!) and strings. I don't understand at all why + can mean append but not element-wise addition...
I was actually thinking of embedding a small interpreter into my programs so I can have infix expressions with custom operators.
result := infix.Eval(" A * B ")
...after registering what *, A, and B are.
Ryanne
- from my phone -
> > On Jan 14, 2010 8:04 AM, "Franz" <francesco...@unisalento.it> wrote: > > While Fortran g...
andrey mirtchovski
you squint at it the right way) gofmt can't be used for the creation
of DSLs translated to and compiled with Go's tools. seeing how well it
dealt with the transition from semicolons to non-terminated lines, it
ought to be possible to get it to do operator overloading for you.
whether that's a good idea on the other hand i can not judge... :)
Jon Harrop
> While Fortran grows like a cancer (withouth dying, though) the
> scientific community still lacks a language which is
> - small and easy to learn (scientists are not all
> _computer_scientist_);
> - portable;
> - fast for number crunching and accurate (IEEE floating point
> standard) ;
> - concurrent (no need for OpenMP/MPI/Cuda etc...)
> ANSI C (plus libraries) is the most suitable of a host of unsuitable
> languages. C++ is too big and it takes a life time to master it. Java
> lives in a virtual machine, therefore it is slow.
> Some scripting languages (e.g. python+numpy) are very good, but only
> when neither speed or concurrency is crucial.
I am trying to address this exact problem, beginning with the creation of a
new VM:
http://www.ffconsultancy.com/ocaml/hlvm/
and I'm already getting impressive results:
http://flyingfrogblog.blogspot.com/2010/01/hlvm-on-ray-tracer-language-comparison.html
> From a cursory look it seems to me that Go might evolve into the
> perfect high performance computing language for scientific use (in
> addition to other uses, of course).
> Am I wrong?
There are several missing features such as the lack of operating overloading
and general verbosity of the Go language. There are also some design
decisions, e.g. if Go ever gets generics it looks like they will be extremely
inefficient (like Java's).
> Is there some feature (or lack of it) that discourages making a time
> investment in learning and deploying Go for scientific computing,
> especially for large projects?
Lack of a decent garbage collector.
Right now, C# is probably your best bet for scientific computing from a
technical perspective if you consider Mono to satisfy the portability
requirement. If you're willing to sacrifice portability then F# is far
better.
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
Jonathan Amsterdam
> inefficient (like Java's).
What is your evidence for this claim?
Johann Höchtl
On Jan 14, 3:03 pm, Franz <francesco.papare...@unisalento.it> wrote:
> While Fortran grows like a cancer (withouth dying, though) the
> scientific community still lacks a language which is
> - small and easy to learn (scientists are not all
> _computer_scientist_);
> - portable;
> - fast for number crunching and accurate (IEEE floating point
> standard) ;
I miss abrbitrary precission integers most. I would rather like not
have to about wheather an integer may overflow and possibly spoil a
computation. Linking against Bignum without syntactic language support
would be verbose. bignumAdd(a,b)? brrrr!
Hint: "integer" is free to take ....
Jon Harrop
The proposed implementations of generics for Go follow the existing
implementation used by Java, which has well known (awful) performance
characteristics due to boxing. Moreover, Go's comparatively-inefficient
garbage collectors exacerbate the problem.
For example, functions generic over types of number will cause all numbers to
be boxed and that results in catastrophic performance degradation. You've
basically recovered the performance characteristics of a dynamic language.
Ian Lance Taylor
> The proposed implementations of generics for Go follow the existing
> implementation used by Java, which has well known (awful) performance
> characteristics due to boxing. Moreover, Go's comparatively-inefficient
> garbage collectors exacerbate the problem.
To be clear for onlookers, the core Go team has not yet made any
proposals regarding generics. Jon is referring to ideas which have
been discussed on the list. These ideas are helpful in developing our
plans, but they do not in themselves indicate what will be done for
Go, if anything.
Ian
NoiseEHC
> The proposed implementations of generics for Go follow the existing
> implementation used by Java, which has well known (awful) performance
> characteristics due to boxing. Moreover, Go's comparatively-inefficient
> garbage collectors exacerbate the problem.
>
>
Jonathan asked about evidence if I am not mistaken. What you say here is
only speculation since as far as I know no proposals ever touched
implementation only syntax and semantics. Mine proposal (the macro
rewrite) has even left the choice of implementation to the developer of
the generic library.
> For example, functions generic over types of number will cause all numbers to
> be boxed and that results in catastrophic performance degradation. You've
> basically recovered the performance characteristics of a dynamic language.
>
What you say is the thing what is possible now without any generics
support. You can create generic algorithms and collections in Go by
using interface{} which is almost equivalent with boxing.
Franz
A few clarifications are probably in order.
The kind of "programmers" that I have in mind is not somebody that
spends all his/her time coding, nor has an extensive computer science
background, yet must produce highly performant code.
As a typical application developed by this kind of people you can take
a big weather/climate/ocean model. Believe it or not, about all models
used by the IPCC (intergovernamental panel on climate change) are
written in Fortran.
Full-time software engineers usually don't belong to the core
development teams of these programs: the community tends to distrust
those who don't have a strong backgound in math or physics.
Don't take me wrong: I'm not talking about mindless bozos, but about
very skilled and intelligent scientist, who have a very limited time
to practice the art of programming (and probably have never read Peter
Norvig's essay http://norvig.com/21-days.html ).
In this kind of setting C has a very hard life: they will try it out,
get burned badly (e.g. because they didn't metabolize the difference
between an array and a pointer, and wrote some Fortran-style code with
arrays that fill-up the stack), and then declare to the world that
Fortran is way better.
Of course C++ has all the subltleties of C, and then some. It's the
worst possible language for this kind of users. Anything that takes
more than a month to learn and more than a year to master will not
make inroads in these communities.
Go seems a much cleaner language than C, while still holding the
promise of good performances.
I agree with several observations:
- bindings to C and Fortran. Yet I thought that go on gcc could
already call C code. Would it be difficult to write a wrapper to, say,
the Gnu Scietific Library, or to FFTW?
- arbitrary precision integers may be important.
- a native complex type, modeled after the C99 specs?
- a standard library implementing vectors and matrices would also be
nice.
- a standard library implementing MPI-like message passing would be
possible? I've seen there is one for remote procedure calls...
The main observation that I disagree with, is the stress on operator
overloading.
The idea of expressing computations as operations on high-level things
as vectors, matrices and tensors (as opposed to element-wise
manipulation) is very appealing in principle, but it doesn't work for
two reasons.
- there aren't that many operators to overload, but there are way too
many operations that one may use: e.g. in the C++ ray tracing code
mentioned by J. Harrop, * becomes a scalar-by vector multiplication,
and the dot product is a function dot(). Vector normalization is not
an unary operator, but, again, a function. The code doesn't need
external product, dyadic products, etc. etc. but if it did, I bet they
would be again functions.
- manipulations of vectors and matrices as whole things, instead of
element-wise manipulations is inefficient. A trivial example: let
a,b,c be vectors of length N. Take the dyadic product of a and b and
multiply the result by c. That's again a vector of length N. If you
hand-code this element-by-element, you need no extra storage. Tell me
there is a compiler smart enough to avoid creating an intermediate N
by N matrix, if you go the overloading way. Another example is sparse
matrices: most finite differences schemes may be expressed elegantly
as operations on sparse matrices. Show me a sparse matrix
implementation which is as fast as element-by-element coding for, say,
a Poisson solver.
A matrix-oriented language has, of course, its own niche, as the large
popularity of Matlab shows. For example, in many cases the post-
processing of the output of those big climate models I was talking
about is made with Matlab or similar tools.
For those inclined to day-dreaming, we might evoke a math-go pre-
processor that can turn a matrix-oriented superset of Go into plain go
code. The biggest advantage of this proposal comes from the native
support of UTF8: there will be no shortage of symbols to denote in a
sinthetic and expressive way just about any mathematical operation.
But that's just a dream.
Ryanne Dolan
Franz,
I don't understand why you assert that operator overloading would imply inefficient code. C++ doesn't disallow per-element manipulation... it just makes it possible to write more readable code in the cases where per-element manipulation would be tedious.
In languages supporting operator overloading, operators are just functions. It doesn't make any sense to say that operators are less efficient than functions. Furthermore, it isn't impossible to write sparse matrix operators or operators that work on mixes of sparse/dense matrices without losing efficiency.
One of the reasons operator overloading sorta kinda works in C++ but wouldn't in Go is the (non)existence of exceptions. Code such as
A / B
...can throw an exception in C++, whereas Go code must look like:
C,err = mat.Div (A, B)
if err...
...which gets tedious quickly. And it isn't enough to say "check inputs not errors" because some checks might be just as complicated as the intended operation. Is this singular? etc
The problem in Go gets really bad when you want to write expressions. Try A*B+C in Go when each operation might return an error. (I realize mult and add might not have error checks in practice, but you get the point.) You end up using lots of intermediate variables and your code becomes a mess.
That's one reason an embedded interpreter makes some sense to me:
res,err := infix.Eval ("A * B + C")
is readable and doesn't need exceptions.
- from my phone -
Gabor
computing:
Can we expect the exponentiation operator anytime soon?
Jon Harrop
I think the kinds of scientists you are describing are a dying breed that are
now only found in pockets of academia and surround major legacy applications.
In industry, most scientists are already using modern alternatives not just
because it is prohibitively difficult to solve many interesting problems
using Fortran but also because Fortran is no longer competitively performant
on multicores and cannot compete with GPUs.
> Go seems a much cleaner language than C, while still holding the
> promise of good performances.
There is some potential there outside Windows but I do not see Go ever
catching up with where F# already is today, for example.
> The main observation that I disagree with, is the stress on operator
> overloading.
> The idea of expressing computations as operations on high-level things
> as vectors, matrices and tensors (as opposed to element-wise
> manipulation) is very appealing in principle, but it doesn't work for
> two reasons.
> - there aren't that many operators to overload, but there are way too
> many operations that one may use: e.g. in the C++ ray tracing code
> mentioned by J. Harrop, * becomes a scalar-by vector multiplication,
> and the dot product is a function dot(). Vector normalization is not
> an unary operator, but, again, a function. The code doesn't need
> external product, dyadic products, etc. etc. but if it did, I bet they
> would be again functions.
Probably, yes.
> - manipulations of vectors and matrices as whole things, instead of
> element-wise manipulations is inefficient. A trivial example: let
> a,b,c be vectors of length N. Take the dyadic product of a and b and
> multiply the result by c. That's again a vector of length N. If you
> hand-code this element-by-element, you need no extra storage. Tell me
> there is a compiler smart enough to avoid creating an intermediate N
> by N matrix, if you go the overloading way.
Sure. I was doing that with template metaprogramming in C++ about 10 years
ago.
Provided your matrices are large enough, you can just accumulate a
vector-matrix expression and apply optimizations to eliminate temporaries
before evaluating it. That is a lot easier in a language designed for
metaprogramming, i.e. not Fortran or Go.
> Another example is sparse
> matrices: most finite differences schemes may be expressed elegantly
> as operations on sparse matrices. Show me a sparse matrix
> implementation which is as fast as element-by-element coding for, say,
> a Poisson solver.
>
> A matrix-oriented language has, of course, its own niche, as the large
> popularity of Matlab shows. For example, in many cases the post-
> processing of the output of those big climate models I was talking
> about is made with Matlab or similar tools.
> For those inclined to day-dreaming, we might evoke a math-go pre-
> processor that can turn a matrix-oriented superset of Go into plain go
> code. The biggest advantage of this proposal comes from the native
> support of UTF8: there will be no shortage of symbols to denote in a
> sinthetic and expressive way just about any mathematical operation.
> But that's just a dream.
F# already allows unicode source including operators. :-)
Ian Lance Taylor
I don't think that is very likely. The operators in Go are
implemented as single machine instructions on many modern processors.
Exponentiation is not. I think math.Pow seems appropriate for a
language like Go.
Ian
Franz
> It doesn't make any sense to say that operators are less efficient than
> functions.
I didn't say that. I said that
1) functions (and operator overloading) are often less efficient than
element-by-element coding.
2) overloading might not buy you more readability over functions,
because there aren't that many operators to overload.
> Furthermore, it isn't impossible to write sparse matrix
> operators or operators that work on mixes of sparse/dense matrices without
> losing efficiency.
Wonderful! Do you actually know a piece of code that does just that
and that I can study to learn the trick?
> C,err = mat.Div (A, B)
> if err...
>
> ...which gets tedious quickly.
That's a good point. To me it seems one more reason to stick with
element-by-element manipulations, at least in Go and similar
languages.
Franz
> because it is prohibitively difficult to solve many interesting problems
> using Fortran but also because Fortran is no longer competitively performant
> on multicores and cannot compete with GPUs.
I wish you were right, but you might be over optimistic. For example:
10 out of 17 bechmarks of the SPEC CFP2006 use Fortran code (and only
4 use C++) http://www.spec.org/cpu2006/CFP2006/.
> I think the kinds of scientists you are describing are a dying breed that are
> now only found in pockets of academia and surround major legacy applications.
The trend is in the opposite direction: as computing resources become
faster and cheaper, more and more scientist and technicians end up
doing some sort of programming, at various levels, from those who
occasionally write a script with an application-specific language
(e.g. matlab) scaling up to implementors and maintainers of enormous
code bases.
A real life example might be enlightening: read the answer to the 1st
question about HIM (Hallberg isopycnal model, a leading ocean model)
http://data1.gfdl.noaa.gov/~arl/pubrel/l/him/doc/HIM_faq.html You are
allowed to weep, afterwards.
(and no, Princeton geophysicists are not dying...)
> There is some potential there outside Windows but I do not see Go ever
> catching up with where F# already is today, for example.
The future of windows as a platform for supercomputing doen't look
bright to me: http://www.top500.org/stats/list/34/os
Believe me, the next time that Nature will feature a simulation of a
supernova explosion, it won't be made on windows. And your weekly
weather forecast isn't computed on it, either, although The Weather
Channel might be using it for post-processing.
> > - manipulations of vectors and matrices as whole things, instead of
> > element-wise manipulations is inefficient. A trivial example: let
> > a,b,c be vectors of length N. Take the dyadic product of a and b and
> > multiply the result by c. That's again a vector of length N. If you
> > hand-code this element-by-element, you need no extra storage. Tell me
> > there is a compiler smart enough to avoid creating an intermediate N
> > by N matrix, if you go the overloading way.
>
> Sure. I was doing that with template metaprogramming in C++ about 10 years
> ago.
>
> Provided your matrices are large enough, you can just accumulate a
> vector-matrix expression and apply optimizations to eliminate temporaries
> before evaluating it. That is a lot easier in a language designed for
> metaprogramming, i.e. not Fortran or Go.
I'd love to see an example. If what you say doesn't boil down to
rewrite the element-by-element calculation somewhere else in the
source code, then I'll take my time to master C++ and use it in my
projects.
Another interesting test problem is computing the Mandelbrot set.
The low-level way to do it is to loop z:=z^2+c until |z|>2 or N
iterations are done, for some large fixed N.
This inner loop is bracketed by to outer loops that explore a matrix
of values for the constant c. This is verbose, messy, but speedy,
because for many values of c the inner loop runs for much less than N
cycles.
The matrix-based way is: define a complex-values matrix C whose
elements are all the c values that you want to plot. Then iterate
exactly N times Z:=Z*Z+C, where * now means 'element-by-element matrix
multiplication'. The (approximate) Mandelbrot set is represented by
the elements of Z having modulus less than 2. This is elegant and very
readable, and there is only one loop (the other two are implicit in
the matrix operations) but all elements of Z iterate N times, even if
their modulus has already exceded 2. Big waste.
Do your metaprogramming techniques allow to keep the elegance of the
second approach and the speed of the first? Any example code?
Norman Yarvin
Probably by far the most common case in numerical programming is taking a
small integer power of a floating point number, with the power most often
being two. That's a matter of a relatively few machine instructions.
It might not seem like a big deal to write, for example,
pressure*pressure
instead of
pressure^2
but if one is writing hundreds of lines of math, the former can get quite
tiresome.
Bob Cunningham
>> In industry, most scientists are already using modern alternatives not just
>> because it is prohibitively difficult to solve many interesting problems
>> using Fortran but also because Fortran is no longer competitively performant
>> on multicores and cannot compete with GPUs.
>>
> I wish you were right, but you might be over optimistic. For example:
> 10 out of 17 bechmarks of the SPEC CFP2006 use Fortran code (and only
> 4 use C++) http://www.spec.org/cpu2006/CFP2006/.
>
I've been "the" programmer on several projects staffed with (non-CS)
PhDs. There is no way I'd let any of them near a compiler for a
low-level language like C, or a complex language like C++ or Java.
The scientists I've known who were competent in any general-purpose
language beyond FORTRAN most often used Python, and that was primarily
due to the awesome SciPy/NumPy package. Perl does has a significant
presence in Biological computing, primary due to its powerful pattern
matching capabilities.
The scientists I've known generally don't WANT to write programs! They
see programming as a vile but necessary evil forced upon them in order
to obtain access to automated calculation. FORTRAN is, to them, the
simplest and fastest way to minimize the pain. If they had to leave
FORTRAN behind, they'd prefer to go more toward Python, and further away
from C.
Go is a great language testbed, but in industrial contexts it does not
(yet) seem on track to replace either C at the low-end (embedded
real-time and memory-constrained environments), or C++/Java at the
high-end (monster projects), or FORTRAN (scientific) or Ada
(high-integrity systems). That may change as Go evolves, but I'm not
betting on it. The above domains benefit greatly from "rich" (big
syntax) languages and/or complex (slow) compilers: Go's stated mission
is to avoid both of those areas.
One direction of evolution I'd like to see Go attempt would be to expand
the notion of channels and goroutines to work across meshes and
networks, replacing or hiding packages such as MPI and PVM. That would
be a HUGE draw to much of the scientific community.
Rather than trying to make the Go syntax more suitable for scientific
work, I'd rather see channels and goroutines added to Python and FORTRAN
to permit PhDs to leverage their current programming experience to make
better use of multiple cores (and eventually distributed processors /
clouds) with minimal effort, and without needing to use or become a
"professional" programmer.
>> I think the kinds of scientists you are describing are a dying breed that are
>> now only found in pockets of academia and surround major legacy applications.
>>
> The trend is in the opposite direction: as computing resources become
> faster and cheaper, more and more scientist and technicians end up
> doing some sort of programming, at various levels, from those who
> occasionally write a script with an application-specific language
> (e.g. matlab) scaling up to implementors and maintainers of enormous
> code bases.
> A real life example might be enlightening: read the answer to the 1st
> question about HIM (Hallberg isopycnal model, a leading ocean model)
> http://data1.gfdl.noaa.gov/~arl/pubrel/l/him/doc/HIM_faq.html You are
> allowed to weep, afterwards.
> (and no, Princeton geophysicists are not dying...
Great comments and replies!
In the "big problem" scientific context, making it easy and efficient to
distribute computation and data across multiple cores and distributed
processors may matter far more than access to a native Complex type or
generic Vectors.
In other words, the "elephant" problem is not ease of coding or
efficient use of any single execution unit: The problem is making
effective use of all available cores and processors. Serial code
efficiency matters far less compared to making use of the exponentially
growing number of cores (1, 2, 4, 8, ...) and processors (clouds).
The Go crew is absolutely correct to omit complex code optimizers from
their fast (non-GCC) compilers. That would not be the best use of such
an amazingly talented team!
Go has made a huge step in the direction of simplified multicore
processing (channels + goroutines), and the rest of its features pale in
comparison (fast compile, interfaces, multi-value return, type
inference, etc.).
What makes Go so exciting to me is that it is the ONLY language I can
imagine being used to implement the examples in "Multicore Programming
for Dummies".
I'd like to eventually see Go used in "Cloud Programming for Dummies".
But I don't envision Go ever being used in the book "Programming For
Scientists".
-BobC
Franz
> small integer power of a floating point number, with the power most often
> being two. That's a matter of a relatively few machine instructions.
>
> It might not seem like a big deal to write, for example,
>
> pressure*pressure
>
> instead of
>
> pressure^2
>
> but if one is writing hundreds of lines of math, the former can get quite
> tiresome.
This leads me to ask about inline functions
assume you define the function
func pow3(x float64) float64 {return x*x*x}
is this always going to incur a call overhead, or will the Go compiler
inline it? I guess there will never be an explicit 'inline' keyword in
Go...
Gabor
...
I agree with most of what you say about go's importance and potential
in multicore programming.
On the other hand I do not agree with your general claim about
scientist's attitude towards modern programming languages/techniques.
Most of them do not have the luxury to work with a professional
computer scientist, so quite naturally they do the job themselves.
Many of them use languages like C/C++ or techniques like MPI/OpenMP/
Cuda correctly. And depending on how the Google's go language evolves,
would use it too. At the birth of a language, it would be unwise to
consider the whole scientific community as illiterate in modern
programming techniques and incapable of adjusting to new variants. The
features required by this community can be carefully selected (e.g.
complex numbers), kept to a bare minimum and therefore, would not blow
up the original language design.
Johann Höchtl
On Jan 17, 10:32 am, Bob Cunningham <FlyM...@gmail.com> wrote:
> The Go crew is absolutely correct to omit complex code optimizers from
> their fast (non-GCC) compilers. That would not be the best use of such
> an amazingly talented team!
>
Fully agreed!
> Go has made a huge step in the direction of simplified multicore
> processing (channels + goroutines), and the rest of its features pale in
> comparison (fast compile, interfaces, multi-value return, type
> inference, etc.).
>
> What makes Go so exciting to me is that it is the ONLY language I can
> imagine being used to implement the examples in "Multicore Programming
> for Dummies".
>
> I'd like to eventually see Go used in "Cloud Programming for Dummies".
>
I know this is a Go-mailing list and while not strictly advocating ...
for scientists which probably have internalized mathematical notation
and single assignment, Erlang would be the language which would first
come to my mind, beeing more high-level than Go. But both languages
fit their nice (which in the case of Go might soon be not so small
anymore)
> But I don't envision Go ever being used in the book "Programming For
> Scientists".
>
Uhm, I do. It's from Go ogle, you know, and for some this might smell
like a million dollar baby ...
> -BobC
Johann Höchtl
On Jan 16, 2:42 am, Ian Lance Taylor <i...@google.com> wrote:
> To be clear for onlookers, the core Go team has not yet made any
> proposals regarding generics. Jon is referring to ideas which have
> been discussed on the list. These ideas are helpful in developing our
> plans, but they do not in themselves indicate what will be done for
> Go, if anything.
>
And I for myself never missed generics from any language I used and
found them much overused in C++. While they have their need (STL is a
wonderful example), language newbees tend to use every fancy feature
without thinking on suitability and later servicability.
In that respect, sad but true: Worse is better.
And as the discussion somewhat mentions "types of scientiests", I very
much liked that post from reddit (reddit search down at the moment, so
I fail to post the link)
"An algorithm in Haskell is worth a paper, an algorithm in Python is a
blog post"
> Ian
Bob Cunningham
I never said scientists don't program: I said the ones I know don't WANT
to program.
The scientists I know believe that having a scientist write programs is
like having a pastry chef grind his own flour. Sure, it can be done,
but it's probably not the best use of the chef's time or talent. But
when there is no alternative, they always step up to meet the need.
Nor did I say scientists CAN'T program. Most of the ones I know are
true wizards in FORTRAN. But their expertise typically was only in
FORTRAN, no matter how many other languages they knew.
I should have mentioned that all the scientists I've worked with have
been in the private sector, outside of academia and government. They
were focused on solving tough problems on a tight schedule, often with a
very tight budget.
That made them extremely expensive programmers! Even if they did like
to write code, the project would proceed faster if they spent their time
where their value was highest.
I don't know anything about how other scientists feel about
programming. I suspect there are many scientists with the luxury of
time who would love to try a new scientific programming language.
I suspect most would prefer to see the languages they already know
become better.
-BobC
Jon Harrop
> > In industry, most scientists are already using modern alternatives not
> > just because it is prohibitively difficult to solve many interesting
> > problems using Fortran but also because Fortran is no longer
> > competitively performant on multicores and cannot compete with GPUs.
>
> I wish you were right, but you might be over optimistic. For example:
> 10 out of 17 bechmarks of the SPEC CFP2006 use Fortran code (and only
> 4 use C++) http://www.spec.org/cpu2006/CFP2006/.
>
> > I think the kinds of scientists you are describing are a dying breed that
> > are now only found in pockets of academia and surround major legacy
> > applications.
>
> The trend is in the opposite direction: as computing resources become
> faster and cheaper, more and more scientist and technicians end up
> doing some sort of programming, at various levels, from those who
> occasionally write a script with an application-specific language
> (e.g. matlab) scaling up to implementors and maintainers of enormous
> code bases.
> A real life example might be enlightening: read the answer to the 1st
> question about HIM (Hallberg isopycnal model, a leading ocean model)
> http://data1.gfdl.noaa.gov/~arl/pubrel/l/him/doc/HIM_faq.html You are
> allowed to weep, afterwards.
> (and no, Princeton geophysicists are not dying...)
You're talking about monolithic legacy applications. That is no more
representative of scientific computing than COBOL running on mainframes in
banks is representative of software in industry.
> > There is some potential there outside Windows but I do not see Go ever
> > catching up with where F# already is today, for example.
>
> The future of windows as a platform for supercomputing doen't look
> bright to me: http://www.top500.org/stats/list/34/os
Supercomputing is a tiny and shrinking part of scientific computing.
> Believe me, the next time that Nature will feature a simulation of a
> supernova explosion, it won't be made on windows. And your weekly
> weather forecast isn't computed on it, either, although The Weather
> Channel might be using it for post-processing.
The vast majority of scientific computing is now done on multicore desktops
where, of course, Windows has the lion's share of the market. The vast
majority of the computed content presented in Nature will have been done on a
desktop machine running Windows.
> > Sure. I was doing that with template metaprogramming in C++ about 10 years
> > ago.
> >
> > Provided your matrices are large enough, you can just accumulate a
> > vector-matrix expression and apply optimizations to eliminate temporaries
> > before evaluating it. That is a lot easier in a language designed for
> > metaprogramming, i.e. not Fortran or Go.
>
> I'd love to see an example. If what you say doesn't boil down to
> rewrite the element-by-element calculation somewhere else in the
> source code, then I'll take my time to master C++ and use it in my
> projects.
C++ has been obsolete for years. Don't start learning it now!
> Another interesting test problem is computing the Mandelbrot set.
> The low-level way to do it is to loop z:=z^2+c until |z|>2 or N
> iterations are done, for some large fixed N.
> This inner loop is bracketed by to outer loops that explore a matrix
> of values for the constant c. This is verbose, messy, but speedy,
> because for many values of c the inner loop runs for much less than N
> cycles.
> The matrix-based way is: define a complex-values matrix C whose
> elements are all the c values that you want to plot. Then iterate
> exactly N times Z:=Z*Z+C, where * now means 'element-by-element matrix
> multiplication'. The (approximate) Mandelbrot set is represented by
> the elements of Z having modulus less than 2. This is elegant and very
> readable, and there is only one loop (the other two are implicit in
> the matrix operations) but all elements of Z iterate N times, even if
> their modulus has already exceded 2. Big waste.
>
> Do your metaprogramming techniques allow to keep the elegance of the
> second approach and the speed of the first?
Yes.
> Any example code?
The simplest example is traditional deforestation in a functional language. To
take your Mandelbrot example, this matrix version:
let f z = z * z + c
nest n (map f) matrix
Can be deforested to:
map (nest n f) matrix
You've just exchanged the combinators to switch the loops, avoiding the
creation of a temporary.
Things like matrix operators and slices are just special cases of combinators
in a functional language. Once you've got that functional capability you can
easily express the solutions to such problems and optimize them. Ultimately,
you can create a compiler for a domain specific language that takes your
matrix operations and compiles them down to efficient machine code.
I used to same technique to rewrite a vector-based wavelet transform written
in Python into a function-based representation in OCaml that was many times
faster because it compiles down to element-wise operations without you having
to code a single loop:
http://www.mail-archive.com/python-list%40python.org/msg121602.html
Here's the code:
let rec d4 s1 d1 d2 x =
let c1 = 1.7320508075688772 in
let c2 = 0.4330127018922193 in
let c3 = -0.066987298107780702 in
let c4 = 0.51763809020504137 in
let c5 = 1.9318516525781364 in
let n = Array.length x in
let odd i = x.(2*i) and even i = x.(2*i + 1) in
let d1 i = odd i -. c1 *. even i in
let f = function -1 -> n/2 - 1 | i -> i in
let s1 i = even i +. c2 *. d1 i +. c3 *. d1 (f(i-1)) in
let d2 i = d1 i +. s1 (f(i-1)) in
let even = Array.init (n/2) (fun i -> c4 *. s1 i) in
if n > 2 then d4 s1 d1 d2 even else s1, d1, d2
Mathematica has also helped to make this functional style of programming more
popular in scientific circles.
Jon Harrop
> Rather than trying to make the Go syntax more suitable for scientific
> work, I'd rather see channels and goroutines added to Python and FORTRAN
> to permit PhDs to leverage their current programming experience to make
> better use of multiple cores (and eventually distributed processors /
> clouds) with minimal effort, and without needing to use or become a
> "professional" programmer.
If you want to make efficient use of multicores, you'll almost certainly want
Cilk-style wait-free work-stealing task queues. They're in .NET 4, for
example.
> In the "big problem" scientific context, making it easy and efficient to
> distribute computation and data across multiple cores and distributed
> processors may matter far more than access to a native Complex type or
> generic Vectors.
If you get basics like complex numbers wrong, as Java did, then your
performance is so badly degraded that your supercomputer will run as fast as
a desktop.
For example, hash tables over value types are 32x slower in Java than C# due
to fundamental deficiencies in the JVM. Even if you assume linear scaling,
Java running on Azul's 256-core supercomputer would only be competitive with
C# running on my 8 core desktop. In practice, the JVM's inefficiencies will
rapidly max out the memory bandwidth for the whole machine and you won't get
anywhere near linear scaling.
> In other words, the "elephant" problem is not ease of coding or
> efficient use of any single execution unit: The problem is making
> effective use of all available cores and processors. Serial code
> efficiency matters far less compared to making use of the exponentially
> growing number of cores (1, 2, 4, 8, ...) and processors (clouds).
I disagree. Amdahl's law places a limit on the performance gain from an
infinite number of cores that, for many applications, in not substantially
larger than the performance improvements offered by serial optimizations.
Moreover, that is imposed in practice not only from serial segments of
computation but from global resource limits such as memory bandwidth.
> Go has made a huge step in the direction of simplified multicore
> processing (channels + goroutines),
Compared to F# on .NET 4, Go is cumbersome and hugely inefficient for
multicore programming.
> What makes Go so exciting to me is that it is the ONLY language I can
> imagine being used to implement the examples in "Multicore Programming
> for Dummies".
You're joking.
Ian Lance Taylor
> This leads me to ask about inline functions
> assume you define the function
>
> func pow3(x float64) float64 {return x*x*x}
>
> is this always going to incur a call overhead, or will the Go compiler
> inline it? I guess there will never be an explicit 'inline' keyword in
> Go...
At the moment the 6g/8g compilers will not inline functions. At the
moment the gccgo compiler will inline calls within a package (at
appropriate optimization levels), but will not inline calls across
packages. Both compilers may change over time.
Ian
The Parrot's Theorem
probably I am not even passable as professional programmer.
Can we have a serious comparison benchmark of some computationally and
memory intensive operation run in F#, Go (and possibly a couple of
other languages, ideally R) on a multicore (like 16 cores) machine
with at least 64Gb of RAM just to see what we are talking about?
For example, a large non linear constrained convex optimisation
problem, or some GCM type model, or some climatic simulation or fluid
mechanics simulation or some serious numerical simulation? Something
you normally need to run for a week, so if the performances are that
amazing, we should see a substantial performance increase.
I our research groups we tend to use languages either high level
languages like R or Matlab / Octave or Python, or C and Cuda / Open CL
for optimised routines or Java and Ruby for generic stuff.
Traditionally it is either C or Python or Java for stuff that goes on
distributed machines, and Java, Python or Ruby when the code can make
use of object oriented features.
It would help greatly to be able to spread computational load on
several cores and on several machine in a very simple transparent and
seamless way, without making us learn MP/ MPI.
I am surprised that F#, C# and .NET do all this things, and we have
never used them .... could you please elaborate John? All our clusters
are actually using *nix because we can get better performance and
memory utilisation.
Also, I am surprised you say that there is no equivalent for the NET
platform .... I would have thought the JVM wasn't very different, and
allowed for many languages that we keep using in scientific
computation like python or ruby. The other problem with the NET
platform is the fact you cannot port it anywhere really.
The other very important aspect is that it is completely open source,
which means it can be optimised progressively.
To me, go looks promising because allows to manage the multi core in a
nearly seamless way, but it would be nice to have mechanisms to
manage:
(1) distributed computing (spreading on more than one machine)
(1) high performance numerical types, like multidimensional matrices /
multi-dimensional arrays (not nested arrays!) , that allows for
integration in R and Octave / GDL
(1) in-line functions
(1) Good documentation
(1) Good documentary
(1) Good documentation
(2) GPUs
(forgive me the joke)
I personally very much like the idea of the garbage collector, because
it takes away the hassle of managing the memory. The documentation
says current gc is a temporary one and a new high performance one is
under development.
Regards
David Roundy
> It would help greatly to be able to spread computational load on
> several cores and on several machine in a very simple transparent and
> seamless way, without making us learn MP/ MPI.
MPI isn't particularly hard, and is probably easier to program with
than anything you'd write using go, unless you're writing something
that is very atypical. (e.g. computations involving extra nodes
joining in and leaving dynamically) On the other hand, MPI isn't a
particularly good fit if you aren't actually running on multiple
nodes, and parallelization with pthreads is *definitely* harder than
parallelization in go.
I haven't written or run any scientific code in go, but I have written
heavy-duty scientific code, and I've written code in go. My guess
would be that for any sort of linear-algebra-dominated workload, go
will be as fast as C (with appropriate calls to lapack). In any case,
it'll be way faster than python. The sticking point for me is
actually just operator overloading, which is likely to keep me from
leaving C++ in the short term: scientific code is *so* much more
readable and consequently debuggable when you can use + to represent
addition as in a+b rather than a.Plus(b) or the like.
> To me, go looks promising because allows to manage the multi core in a
> nearly seamless way, but it would be nice to have mechanisms to
> manage:
> (1) distributed computing (spreading on more than one machine)
This would be interesting, but doesn't seem like a good thing to be
written into the core language. It's also unclear to me whether it'd
be better to have decent libmpi bindings or something more flexible.
The trouble with putting this into the core language is that the core
language shouldn't have any way to run something on another machine,
which should require some sort of authentication.
> (1) high performance numerical types, like multidimensional matrices /
> multi-dimensional arrays (not nested arrays!) , that allows for
> integration in R and Octave / GDL
Indeed, I also long for multi-dimensional arrays. It's really sad
that if you want to avoid manually computing indices in a compiled
language, you *still* need to use fortran!
> (1) in-line functions
This is just an optimization, and I feel confident will come in time.
> I personally very much like the idea of the garbage collector, because
> it takes away the hassle of managing the memory. The documentation
> says current gc is a temporary one and a new high performance one is
> under development.
I agree about garbage collection. It's completely worth the overhead,
and in inner loops it should cost nothing, since all allocation (in
well-written inner loops) is on the stack.
--
David Roundy
befelemepeseveze
wrote:
> Indeed, I also long for multi-dimensional arrays. It's really sad
> that if you want to avoid manually computing indices in a compiled
> language, you *still* need to use fortran!
Maybe I misunderstood something:
http://golang.org/doc/go_spec.html#Array_types
-bflm
David Roundy
I was thinking of multidimensional arrays with a size determined at
runtime. It's nice to have fixed-size multidimensional arrays, but
doesn't help for much of my work. Basically, it's only useful for 3x3
tensors and rotational matrices (among the matrices that I use). Oh,
and 4x4 symmetry operators. But those don't show up in any (of my)
performance-critical code anyhow, so the overhead of nested arrays
wouldn't greatly matter for them.
--
David Roundy
David Roundy
Of course, we could go back to fortran 77-style code (before they had
dynamic allocation) and just recompile the program for each problem we
want to solve. Since go is fast to compile, maybe that wouldn't be so
bad... we could just run the go code through the cpp preprocessor or
something. But it doesn't feel like a step forwards.
--
David Roundy
befelemepeseveze
wrote:
> I was thinking of multidimensional arrays with a size determined at
> runtime.
Maybe I'm still confused:
http://golang.org/doc/go_spec.html#Slice_types
Quoted from that link:
"Like arrays, slices are always one-dimensional but may be composed to
construct higher-dimensional objects. With arrays of arrays, the inner
arrays are, by construction, always the same length; however with
slices of slices (or arrays of slices), the lengths may vary
dynamically. Moreover, the inner slices must be allocated individually
(with make). "
-bflm
David Roundy
<befeleme...@gmail.com> wrote:
> Quoted from that link:
> "Like arrays, slices are always one-dimensional but may be composed to
> construct higher-dimensional objects. With arrays of arrays, the inner
> arrays are, by construction, always the same length; however with
> slices of slices (or arrays of slices), the lengths may vary
> dynamically. Moreover, the inner slices must be allocated individually
> (with make). "
As it says, there's no support for multidimensional slices, only for
multidimensional arrays or nested slices, and the latter means you get
poor performance. We have that in C also (pointers to pointers), but
no one who cares about performance uses it, since you have an extra
level of indirection. On top of that, you still need to allocate one
large array/slice for all your data, or it won't be in a contiguous
chunk of memory, and you'll get even worse performance.
I don't have much of a leg to stand on criticizing go for lacking
multidimensional slices (or dynamically-sizable multidimensional
arrays), since no other compiled language has the either (except
fortran), but it still seems a shame. It's almost as if language
developers no longer consider HPC a priority... which probably also
explains the demise of the ** operator, which is a pain to replace
efficiently and readably. My C++ inline replacement uses an extra
multiply beyond the optimal.
--
David Roundy
befelemepeseveze
wrote:
> On Fri, Mar 19, 2010 at 10:45 AM, befelemepeseveze
>
> > Quoted from that link:
> > "Like arrays, slices are always one-dimensional but may be composed to
> > construct higher-dimensional objects. With arrays of arrays, the inner
> > arrays are, by construction, always the same length; however with
> > slices of slices (or arrays of slices), the lengths may vary
> > dynamically. Moreover, the inner slices must be allocated individually
> > (with make). "
> As it says, there's no support for multidimensional slices, only for
> multidimensional arrays or nested slices, and the latter means you get
> poor performance. We have that in C also (pointers to pointers), but
> no one who cares about performance uses it, since you have an extra
> level of indirection. On top of that, you still need to allocate one
> large array/slice for all your data, or it won't be in a contiguous
> chunk of memory, and you'll get even worse performance.
I can't agree (and it can be my fault for sure).
1) Not only array of slices, but also slices of slices (explicitly
stated in the link's quoted part).
2) Runtime array sizing (aka dynamic arrays, i.e. heap based [let's
ignore for now C's VLAs]), inevitably requires an at runtime created
reference. In the n-dims case, you thus get that "pointers to
pointers" thing, possibly somehow, more or less, hidden by the
language used.
3) Making the n-dims issue, size and/or dims decided at runtime,
contiguous in memory, can't be done statically and so the dynamic (run-
time) implementation case inevitably leads to 2), i.e. "pointers to
pointers" chain of dereferencing (plus the final index times element
size addition) or n dim-ubound multiplications (plus the final add as
before).
4) A "smart" (this is general term, not a personal offense to anyone)
programmer can try to prematurely optimize this by explicitly coding
*one* of the previous point 3) implementation *possibilities*. That's
pretty often a win of the human intellect dueling some/many of the
nowadays compilers. In the same time, it's a granted lose of that very
same programmer, would the same code be thrown anytime in the future
to a more-than-current-state-of-art advanced compiler.
> I don't have much of a leg to stand on criticizing go for lacking
> multidimensional slices (or dynamically-sizable multidimensional
> arrays), since no other compiled language has the either (except
> fortran), but it still seems a shame.
Shame in me, I have to refresh my almost 30yo Fortran lessons and have
a look on the "new" extensions :-)
-bflm
Ian Lance Taylor
> I was thinking of multidimensional arrays with a size determined at
> runtime. It's nice to have fixed-size multidimensional arrays, but
> doesn't help for much of my work. Basically, it's only useful for 3x3
> tensors and rotational matrices (among the matrices that I use). Oh,
> and 4x4 symmetry operators. But those don't show up in any (of my)
> performance-critical code anyhow, so the overhead of nested arrays
> wouldn't greatly matter for them.
Offhand, I think you have two choices right now.
This gives you convenient syntax at the cost of one extra memory load
per lookup.
func Multidim(m, n int) [][]int {
p := make([]int, m * n)
r := make([][]int, m)
for i := 0; i < m; i++ {
r[i] = p[i*n : i*n + n-1]
}
return r
}
This gives you uglier syntax but no runtime cost.
type Multidim struct {
int m
a []int
}
func NewMultidim(m, n int) *Multidim {
return &Multidim{m, make([]int, m * n)}
}
func (p *Multidim) Get(x, y int) int {
return p.a[p.m*x + y]
}
func (p *Multidim) Set(x, y int, v int) {
p.a[p.m*x + y] = v
}
I guess I don't think these options are too terrible.
(Code is not tested.)
Ian
David Roundy
<befeleme...@gmail.com> wrote:
> David Roundy <roun...@physics.oregonstate.edu> wrote:
>> As it says, there's no support for multidimensional slices, only for
>> multidimensional arrays or nested slices, and the latter means you get
>> poor performance. We have that in C also (pointers to pointers), but
>> no one who cares about performance uses it, since you have an extra
>> level of indirection. On top of that, you still need to allocate one
>> large array/slice for all your data, or it won't be in a contiguous
>> chunk of memory, and you'll get even worse performance.
>
> I can't agree (and it can be my fault for sure).
>
> 1) Not only array of slices, but also slices of slices (explicitly stated in the link's quoted part).
As the quoted (well, now cut) text points out, slices of slices are
not multidimensional slices. They aren't as efficient or as simple.
> 2) Runtime array sizing (aka dynamic arrays, i.e. heap based [let's
> ignore for now C's VLAs]), inevitably requires an at runtime created
> reference. In the n-dims case, you thus get that "pointers to
> pointers" thing, possibly somehow, more or less, hidden by the
> language used.
No, the point of dynamically-allocated matrices would be to *not* have
pointers-to-pointers, which isn't inevitably required, since they can
be allocated in a single block of memory.
> 3) Making the n-dims issue, size and/or dims decided at runtime,
> contiguous in memory, can't be done statically and so the dynamic (run-
> time) implementation case inevitably leads to 2), i.e. "pointers to
> pointers" chain of dereferencing (plus the final index times element
> size addition) or n dim-ubound multiplications (plus the final add as
> before).
Right, several multiplications and additions is the way one accesses
multidimensional arrays, just as the single bit shift plus add, which
is how one accesses a one-dimensional array. Unless it's an array of
bytes, in which case you could just add the integer to the pointer.
Hiding this multiplication is a very handy feature to have in a
language. In fact, I thought it was the subject of this
conversation...
> 4) A "smart" (this is general term, not a personal offense to anyone)
> programmer can try to prematurely optimize this by explicitly coding
> *one* of the previous point 3) implementation *possibilities*. That's
> pretty often a win of the human intellect dueling some/many of the
> nowadays compilers. In the same time, it's a granted lose of that very
> same programmer, would the same code be thrown anytime in the future
> to a more-than-current-state-of-art advanced compiler.
The question of what memory layout to use for dense matrices is a
closed one. If you want to use any of the fast algorithms developed
in the last twenty years or so, you need to store your matrix in a
contiguous chunk of memory. If you want to use any of the
highly-optimized code that currently exists, you also need to store
your matrix in a contiguous chunk of memory.
It doesn't look like the memory hierarchy is going away in the short
term, so it is likely to remain true that locality of memory access is
important.
--
David Roundy
David Roundy
> I guess I don't think these options are too terrible.
I agree, they aren't that bad, which is why I don't use fortran.
Well, the first one is pretty terrible, but the latter isn't so very
bad, as long as the accessor function is inlined. But it'd be nicer
to be able to use array syntax. And it'd be *really* nice to not have
my fortran using friends gloating that not only is their language
faster, but their code is cleaner, too.
--
David Roundy
Rob 'Commander' Pike
(I'd trust Ian before myself on that issue) but it's worth pointing
out that both have the same memory locality. Both versions lay the
elements out identically in memory.
To put it another way, notice that the first example allocates
*elements* only once, even though it calls make twice.
-rob
> To unsubscribe from this group, send email to golang-nuts
> +unsubscribegooglegroups.com or reply to this email with the words
> "REMOVE ME" as the subject.
Norman Yarvin
>I guess I don't think these options are too terrible.
It's nice to have the first option (making multidimensional arrays out of
pointers to pointers). It's a way to solve the problem of memory
fragmentation when allocating lots of big N-dimensional arrays: rather
than allocating the whole array as a single chunk, allocate each row of
the array separately. That way one is never trying to allocate any big
chunks of memory, so fragmentation (where there's lots of memory
available, but only in smaller chunks than one wants) isn't a problem.
Otherwise it can be a crippling problem, especially in long-running
programs that want to allocate and free lots of big arrays.
But not all programs fall into that category, and the overhead for the
additional array (or arrays) of pointers can be serious. Following a
pointer chain, on modern processors, is one of the slowest operations;
multiplication (as in accessing Fortran or C99 arrays) is faster than
doing a memory access or even an L2 cache access. Also, in many
contexts, the multiplication can be optimized away: when stepping through
the array element by element, in pretty much any direction (including
diagonally), the multiplication can be strength-reduced to an addition.
With pointers-to-pointers, the row pointer can be reused for operations
that stay on the same row; but that's about it.
But using functions to access N-dimensional arrays, as per the second
option, is not tolerable if one intends to write thousands of lines of
code manipulating those arrays. In scientific computing, those lines of
code are often less than completely clear even when expressed in C or
Fortran syntax; replacing each instance of a[i][j] or a(i,j) with
Multidim.Get(a,i,j) or even just Get(a,i,j) would not only expand their
size but push some of them over the borderline into incomprehensibility.
In Go, though, unlike in C, the comma is not an operator; so it seems
like the syntax has room for a[i,j] to refer to the (i,j)-th element of a
two-dimensional slice. Having the syntax a[i][j] for slices-of-slices,
and a[i,j] for two-dimensional slices, would be more transparent than in
C, where the former syntax is used for both styles of two-dimensional
array. But how exactly to define and use two-dimensional slices (and
higher-dimensional ones) would take more thought than I've given it.
Corrado
I agree .... should we submit a request of enhancement regarding the
native multidimensional arrays?I think for the gurus it is a relatively
simple task.
Regards
--
Corrado Topi
PhD Researcher
Global Climate Change and Biodiversity
Area 18,Department of Biology
University of York, York, YO10 5YW, UK
Phone: + 44 (0) 1904 328645, E-mail: ct...@york.ac.uk
Norman Yarvin
>In Go, though, unlike in C, the comma is not an operator; so it seems
>like the syntax has room for a[i,j] to refer to the (i,j)-th element of a
>two-dimensional slice. Having the syntax a[i][j] for slices-of-slices,
>and a[i,j] for two-dimensional slices, would be more transparent than in
>C, where the former syntax is used for both styles of two-dimensional
>array. But how exactly to define and use two-dimensional slices (and
>higher-dimensional ones) would take more thought than I've given it.
Thinking about it a bit more, it seems straightforward enough.
One-dimensional slices consist of a pointer, a length, and a capacity.
Two-dimensional ones would need a pointer, two lengths, and two
capacities, plus another integer variable, which I'll call 'stride'. The
lengths and capacities would mean the same thing they mean in one
dimension: if a two-dimensional array were declared with
var a [5,7]int
and a two-dimensional slice of it were declared with
b := a[1:3,2:5]
then the pointer of b would point to a[1,2], the first dimension of b
would have length 2 and capacity 4, its second dimension would have
length 3 and capacity 5, and its stride would be 7. That last variable
is needed to access the array properly: to make b[i,j] the same thing as
a[1+i,2+j], one needs to do an access to the memory location at
bp[i*stride+j]
where bp denotes the pointer of b. (At least that's the semantics that
people generally want; the desire is to take a larger matrix and pick out
a rectangular subsection of it to use in some operation.)
In general, N-dimensional slices would require a pointer, N lengths, N
capacities and N-1 strides.
This would provide enough flexibility to satisfy all but the most devoted
Fortran weenies. (The latter might hold out for an equivalent of F90's
RESHAPE function, which allows reassignment of dimensions -- for instance
the array 'a' above might become a one-dimensional array of length 35 --
but they can safely be told "if you want that, you know where to find
it".)
I don't know quite what the best syntax would be for the built-in
functions that access slices. Perhaps len(b,1) could give the length for
the first dimension, and len(b,2) the length for the second dimension;
likewise for cap(). As for the range function, it'd be nice to be able
to write
for i, j, c := range b {
// do something with c aka b[i,j]
}
In a loop written that way, of the two indices, j would be the
fastest-changing, since that would make memory accesses contiguous. (If
someone wants to access memory the slow way, he can write the loops by
hand.) That is, the above loop would be equivalent to
for i, s := range b { // here s becomes a one-dimensional
// slice containing the i'th row of b
for j, c := range s {
// do something with c aka b[i,j]
}
}
Outside such a loop, taking a one-dimensional slice containing
a single row of a two-dimensional slice could be done via:
s := b[i,:]
To take just part of the row, the syntax could be:
s := b[i,2:4]
However, the syntax
s := b[:,i]
could not be permissible, since there is no efficient way to implement
it: it would mean having to add strides to one-dimensional slices. 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.
As for make(), the syntax to allocate two-dimensional slices could be
make([,]int, len1, len2, cap1, cap2)
with the last two arguments being optional. (The stride need not be
specifiable, since setting it equal to cap2 is the only sensible thing to
do: specifying it to be greater than cap2 would amount to saying "I want
you to allocate a bunch of elements that can never be used", and
specifying it to be less than cap2 would be impermissible.)
So far, this doesn't look like it'd require any changes to existing
syntax, just the addition of new syntax that is not presently valid. But
not having worked with the language, I've probably made enough errors for
one message.
--
Norman Yarvin http://yarchive.net
Steven
Norman Yarvin
>Some minor gripes (from a non language designer/compiler writer/parser
>writer)
>1) To take a single row:
>s := b[i]
>s := b[i][1:3]
>or at least
>s := b[i, 0:]
>to be consistent with present syntax in Go.
>
>2) Inconsistency with multidimensional arrays
>var a [3][3]int
>
>println(a[1][2])
>
>s := a[:0,:0]
>println(s[1,2])
>
>Both are referring to the same underlying behaviour on the same underlying
>data, but the syntax is different.
I figured I must be neglecting to take some things into account, and
that's indeed one of them. But those multidimensional arrays are easy to
neglect, since their dimensions have to be constant. If you write a
routine that takes a 3x3 array defined that way, it can't be generalized
to accept 4x4 arrays too: you can't just replace the constant 3 with a
variable n. That makes them not useful for much.
Slices are more useful; but with slices, b[1][2] refers to a slice of
slices, which is a different data structure: instead of being a single
hunk of memory, it's one hunk of memory which contains pointers to other
hunks containing the actual data. It's a more flexible data structure
(since, for instance, the arrays containing the actual data don't have to
all be equal in size), but is usually slower to use than traditional 2-D
arrays are.
Also, even if b is a slice of slices, b[1:3][1:3] is not a rectangular
piece of the matrix b, but rather the same thing as b[2:4]. That's not
only because it's parenthesized as (b[1:3])[1:3], and the thing inside
the parentheses has the same type as b does -- a slice of slices -- and
thus gets treated the same way by the second [1:3]. Such things can be
hard to change, as a matter of language definition and compiler writing;
but also, one might not want to change this one, since it reflects a
fundamental reality. To take a rectangular piece of b, one has to
allocate a new slice of slices, and fill it in with pointers to the
included parts of the rows of b. That's an expensive enough thing to do
that it might not deserve a simple syntax. In contrast, with traditional
2-D arrays, taking a rectangular piece is just a matter of a tiny amount
of integer arithmetic.
Ideally one would like to have both types of data structures available --
slices of slices and multidimensional slices -- and in that case,
referring to the two data structures with different syntax can be an
advantage, since it makes it more obvious what is being done. If, for
instance, one wrote
A[k][i,j]
it'd be clear that what is being operated on is a slice of
two-dimensional slices (or maybe a map of two-dimensional slices). If
the same syntax were used for both, as in
A[k][i][j]
that'd be less clear. It's only a minor convenience, since one can look
at how A is declared to see what sort of data structure it is; but such
minor conveniences add up.
David Roundy
> Thinking about it a bit more, it seems straightforward enough.
> One-dimensional slices consist of a pointer, a length, and a capacity.
> Two-dimensional ones would need a pointer, two lengths, and two
> capacities, plus another integer variable, which I'll call 'stride'. The
> lengths and capacities would mean the same thing they mean in one
> dimension: if a two-dimensional array were declared with
>
> var a [5,7]int
Sounds nice to me!
--
David Roundy
ondrej...@gmail.com
While Fortran grows like a cancer (withouth dying, though) the
scientific community still lacks a language which is
- small and easy to learn (scientists are not all
_computer_scientist_);
- portable;
- fast for number crunching and accurate (IEEE floating point
standard) ;
- concurrent (no need for OpenMP/MPI/Cuda etc...)
ANSI C (plus libraries) is the most suitable of a host of unsuitable
languages. C++ is too big and it takes a life time to master it. Java
lives in a virtual machine, therefore it is slow.
Some scripting languages (e.g. python+numpy) are very good, but only
when neither speed or concurrency is crucial.
