[erlang-questions] Vector instructions
jm
Has anyone given any thought to adding vector instructions or otherwise
adding support for vectors to Erlang?
Jeff.
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Jilani Khaldi
> Thought I'd just throw this out there.
>
> Has anyone given any thought to adding vector instructions or otherwise
> adding support for vectors to Erlang?
vector operations should open "some" doors to Erlang for scientific and
technical programming. Sometimes we have to remember that computers are
often useful to do some numerical calculations even in Erlang.
JK
--
***
T E M A
http://www.dotpas.org
James Hague
> adding support for vectors to Erlang?
I've proposed adding APL-style vector operations on tuples:
{1,2,3} + 1 ==> {2,3,4}
{1,2,3) * 2 ==> {2,4,6}
2 * {1,2,3} ==> {2,4,6}
{1,2,3} + {3,2,1} ==> {4,4,4}
The operations apply to the top level only; they're not recursive.
This would make vector math style code a lot simpler to write in
Erlang. One of the points raised in response to this was that we
shouldn't be overloading tuple operations like this, but have a
special "vector of float" type. I'm not sure I agree with that.
Zvi
James,
With generic tuples it's impossible to implement efficient SIMD operations.
Also there is many undefined/confusing behaiviors, when elements of tuple
are not numeric.
This is the same kind of mistakes, like 2 bad design decisions made in
Erlang:
1. "Ohh, record looks just like a tuple!", so let's throw in some syntactic
sugar for this, instead of real immutable structs/dictionaries.
2. "Ohh, string looks just like a list of integers!", so let's throw in some
syntactic sugar for this, instead of implementing real Unicode-aware
immutable string datatype.
In my opinion Erlang might be a good match, not only for High Availability
(HA) applications, but also High Performance Computing (HPC) applications,
and it might wipe out MPI as de-facto standard, by additing highly optimized
Matlab-like "matrix of double"/"multidimensional array of double" datatype.
Array Programming is also such a good fit for FP, since you may naturaly
extend map and fold/reduce for this datatype.
Also, vector math, even if not implemented efficiently, makes you much more
productive and allows you to prototype with one-liners from shell. Combining
this with Erlang's built-in concurrency and distrition primitives it makes
it Super-High-level language. Unlike other Array programming languages, I
propose that Erlang matrix datatype will be immutable.
So, in my view Erlang should be H^3 (read as H-cube) language:
Highly Available
HPC
High-level
For the start maybe it's possible to take some code from PyNum
(unfortunately Octave has GNU license).
http://en.wikipedia.org/wiki/Category:Array_programming_languages
http://en.wikipedia.org/wiki/Numpy
http://en.wikipedia.org/wiki/GNU_Octave
BTW, I somewhat disappointed with vector math implemented in Matlab and
kdb+/Q. It's not much faster than serial Erlang code (and much much slower
than parallel Erlang code). You can see it in my little PI calculation
benchmark:
Matlab:
>> tic; N=1000000; Step = 1/N; PI = Step*sum(4./(1+(((1:N)-0.5)*Step).^2));
>> toc
Elapsed time is 0.125428 seconds.
Q:
q)N:1000000
q)Step:1%N
q)PI: {[]; Step*((4f % (1f + ((Step*((1+ til N)-0.5)) xexp 2))) +/)}
q)PI()
3.141593
q)\t do[1000;PI()]
264359
q)
i.e. 264 ms
on my dual CPU workstation I getting ~ 200 ms.
Erlang:
Serial tail-recursuive Erlang version takes ~ 170 ms - 300 ms (on different
machines).
Parallel Erlang version on 16 cores takes 15 ms
Zvi
--
View this message in context: http://www.nabble.com/Vector-instructions-tp16468138p16529946.html
Sent from the Erlang Questions mailing list archive at Nabble.com.
Robert Virding
I don't agree with you on your other "mistakes":
1. With records we were constrained to make them as fast as pure tuple operations. We maybe could have made a new datatype for it though.
2. And I think that lists are a wonderful datatype for processing strings.
Robert
Richard A. O'Keefe
On 7 Apr 2008, at 9:16 am, Zvi wrote:
> This is the same kind of mistakes, like 2 bad design decisions made in
> Erlang:
> 1. "Ohh, record looks just like a tuple!", so let's throw in some
> syntactic
> sugar for this, instead of real immutable structs/dictionaries.
> 2. "Ohh, string looks just like a list of integers!", so let's throw
> in some
> syntactic sugar for this, instead of implementing real Unicode-aware
> immutable string datatype.
I cannot let this past. It must be understood clearly that
for many purposes, Erlang's use of lists of integers for strings
is an EXCEPTIONALLY GOOD design.
The number of programming languages with a "real Unicode-aware immutable
string datatype" can be counted on the fingers of one ear. Unicode is
far more complicated than most people realise. The Unicode 5.0 book
(which I am currently slogging through) is >1400 pages. Admittedly,
much of that is code charts, but an astonishing amount of it is not.
I am not excepting Java from the list of "not real Unicode" languages.
Unicode has about a hundred thousand characters. Java characters are
16 bits. Need I say more?
One language that _doesn't_ have Java's central defect is Haskell,
where the native representation for a string is, ahem, a list of
character( code)s.
Zvi
Richard A. O'Keefe wrote:
>
>
> On 7 Apr 2008, at 9:16 am, Zvi wrote:
>
> I cannot let this past. It must be understood clearly that
> for many purposes, Erlang's use of lists of integers for strings
> is an EXCEPTIONALLY GOOD design.
>
> The number of programming languages with a "real Unicode-aware immutable
> string datatype" can be counted on the fingers of one ear. Unicode is
> far more complicated than most people realise. The Unicode 5.0 book
> (which I am currently slogging through) is >1400 pages. Admittedly,
> much of that is code charts, but an astonishing amount of it is not.
>
> I am not excepting Java from the list of "not real Unicode" languages.
> Unicode has about a hundred thousand characters. Java characters are
> 16 bits. Need I say more?
>
> One language that _doesn't_ have Java's central defect is Haskell,
> where the native representation for a string is, ahem, a list of
> character( code)s.
>
Richard,
In my opinion the reason, that Erlang needs specialized datatypes like:
binary, bitstring, string, matrix, etc. it's because it's dynamically typed.
When Erlang designers/implementers needed to process sequences of bytes,
they for some strange reason didn't used tuples or lists of integers, but
introduced a new datatype. Same goes for recently introduced bitstring
datatype: why not to use tuples or lists of true or false atoms? :-)
In fact I was wrong and Erlang "strings" are not just syntactic sugar, I
think there is a lot of optimization behind the scenes and runtime trying to
guess on every list if it's a string or not. If it's string it may use a
more compact representation. The question is why to guess, if we have
dynamically typed language, where each value tagged by a datatype anyway?
My point is Erlang tuples and lists are polymorphic collections and when you
want to have homogenous collections. Also all datatypes mentioned above also
must provide indexing and subslicing, which is somewhat not very effective
when underlying represntation is linked lists.
About Unicode-support in string datatype, it must be practical, not 100%
right, so something like utf16 is good enough for me.
In Haskel you specify type of element (I do not know this language, just
guessing the syntax, I have no idea how to represent vector in Haskel, so
everything is a list):
type String = [Char]
type Binary = [0..255]
type Bitstring = [Bool]
type Matrix = (Int,Int,[Double])
BTW: I think Haskel's tuples are done right. I never understood why
Erlangs' functions have arity, when every function can have single argument
as a tuple. Haskel tuples must have at least 2 elements. So any single
element is a tuple of 1? It's the same like in Matlab - scalar is a matrix
of 1x1.
But in Erlang x and {x} is not the same. Probably it's because Erlangs
tuples are both tuples AND polymorphic vectors.
BR,
Zvi
--
View this message in context: http://www.nabble.com/Vector-instructions-tp16468138p16532464.html
Sent from the Erlang Questions mailing list archive at Nabble.com.
_______________________________________________
Ulf Wiger (TN/EAB)
In the U.S. there is a phrase, "Monday morning quarterback",
referring to all those who watched the football games on
Sunday, and come Monday are ready to tell the world how
they would have played the game differently.
Zvi skrev:
>
> This is the same kind of mistakes, like 2 bad design decisions
> made in Erlang:
> 1. "Ohh, record looks just like a tuple!", so let's throw in
> some syntactic sugar for this, instead of real immutable
> structs/dictionaries.
At the time when records were introduced, there were no
available type tags in the virtual machine, so adding real
structs would have involved major redesign of the VM.
There /was/, however, a real need for some sort of "struct"
support. The design was subject to intense debate, but just
about all agreed that the final result would be a compromise.
(The tag scheme was changed later, so nowadays it would be
possible to introduce a new type.)
> 2. "Ohh, string looks just like a list of integers!", so let's
> throw in some syntactic sugar for this, instead of
> implementing real Unicode-aware immutable string datatype.
In keeping with the philosophy to try to keep the language
as small as possible in the beginning, using lists of integers
as strings was perfectly logical and, as RoK has pointed out
several times, actually quite a good strategy in many respects.
Later, a 'binary' data type was introduced in order to handle
protocol packets etc as chunks of bytes. While binaries could
have replaced lists for string representation, it would have
given worse characteristics in almost every respect except
memory usage and substring by position.
And there really was very little demand for Unicode when Erlang
was first designed. Indeed, the earliest documented use of the
term "Unicode" was in December 1987 (according to unicode.org).
Back then, the subject of intense debate in the Erlang camp
(according to Joe's History of Erlang) was how to get concurrency
right. I think they had their priorities straight.
The Unicode standard version 1.0 was printed in June 1992. At
that time, the Erlang language was considered fairly stable.
In 1993, Distributed Erlang was implemented by Klacke, and
Tim Berners-Lee wrote the first HTML draft. The term "web
application" wasn't yet popular, even though TBL had
described "a multiply connected 'web'" in an information
management proposal back in 1989
(http://www.w3.org/History/1989/proposal.html), and the first
"WorldWideWeb" browser was demonstrated at the end of 1990.
The first non-European web server was set up in Stanford in
1992.
Dial-up Internet access started appearing in 1994.
Java first saw the light of day in 1995:
"Java, in its JDK 1.0 incarnation, had the beginnings of
international support, because a Java char is stored as a
Unicode character. But that was all. You couldn't enter or
display non-Latin characters, and there were no facilities
for language-sensitive formatting, sorting, and so on."
(http://www-128.ibm.com/developerworks/java/library/j-sun-ibm-java.html)
More or less complete support for Unicode didn't come until
JDK 2.0 in 1998, which was also the year when XML 1.0 came
out. It was also the year when the AXD 301 was released,
one of the biggest commercial product development projects
ever undertaken using a functional language.
After 1998, Erlang had millions of lines of legacy code to
consider, so any major changes to the language had to be
considered with utmost care.
One may also note that back in those days, string handling
was not an important factor in telecoms protocol design. All
protocols were byte coded, and work on a good bit syntax had
higher priority than improving string and regexp support.
BR,
Ulf W
James Hague
>
> With generic tuples it's impossible to implement efficient SIMD operations.
I would hesitate to say "impossible" :) Efficiency would clearly be
better than what we have now, though not the pinnacle of performance
(and is anything in Erlang the pinnacle of performance?).
I can certainly see the quirks in my proposal, and I don't ever expect
to see it in Erlang. But I don't know if adding yet another basic
data type to Erlang is the way to go.
> Also there is many undefined/confusing behaiviors, when elements of tuple
> are not numeric.
Not any more than you have with "1 + ok".
jm
> On Sun, Apr 6, 2008 at 4:16 PM, Zvi <ex...@walla.com> wrote:
>> With generic tuples it's impossible to implement efficient SIMD operations.
>
> I would hesitate to say "impossible" :) Efficiency would clearly be
> better than what we have now, though not the pinnacle of performance
> (and is anything in Erlang the pinnacle of performance?).
How about,
%% <3.1415, 1.0>
V1 = <<16#40, 16#49, 16#0E, 16#56, 16#3F, 16#80, 16#00, 16#00>>,
%% <1.0, 1.6180>
V2 = <<16#3F, 16#80, 16#00, 16#00, 16#3F, 16#CF, 16#1A, 16#9F>>,
vec:add(single, V1, V2).
obviously V1 and V2 would normally be created with helper functions. The
advantage of using binaries would be that you would have to add a new
type to Erlang and could more easily do DSP functionality on an input
stream, eg GSM codecs using for VOIP, before having to optimise with C
or another lower language. The first parameter to vec:add/3 would be one
of the atoms: single, double, octet, short, long, or longlong.
What about matricies? list of binaries?
Jeff.
Richard A. O'Keefe
On 7 Apr 2008, at 12:34 pm, Andrew Whitehead wrote:
> Hiya,
>
> Although I don't think you are really suggesting this,
I am not only "not REALLY" suggesting it, I am not suggesting it
to any degree whatsoever.
> the fact that few languages have yet implemented Unicode properly is
> of course no excuse to ignore the problem.
Nor am I, nor could any competent reader for one moment imagine that I
might be, suggesting that it is.
On the contrary, I have been aware of Unicode issues since Unicode 1.0
came
out and have made some specific proposals to the Prolog community about
handling Unicode in Prolog.
What I *AM* saying is that I am fed up to the back teeth with people who
DON'T seem to have thought through the issues thoroughly suggesting that
the designers of a tiny language designed for shipping BYTES around the
net are somehow culpable for not coming up with a string design that has
so far completely eluded the vastly larger and better funded C++, Java,
Javascript, &c communities. For yet another comparison, look at
SmartEiffel: CHARACTER is 8 bits, STRING is 8 bits, UNICODE_STRING
elements are INTEGER_32 values, not characters, and Erlang already has
more things you can do with a Unicode string.
What I *AM* suggesting is that instead of slagging off Joe Armstrong &
Co,
people who want good Unicode support in Erlang should start writing code
and/or EEPs and get it done themselves.
> Using integer lists in place of explicitly marked strings was never
> a good design decision.
This is flat-out wrong.
Remember Alan Perlis's "Epigrams in Programming", number 9:
It is better to have 100 functions operate on one data structure
than 10 functions on 10 data structures.
> It makes it impossible for functions to distinguish between strings
> and other lists without walking through every element.
This has nothing to do with the choice of lists as such and everything
to
do with the fact that Erlang is dynamically typed. In particular, this
turned out to be one of the STRENGTHS of Erlang string support:
iolists.
We can build up complex texts using O(1) concatenation and then flatten
in linear time to something flat if we want it. Now with Unicode,
iolists
turn out to be worth even more than just efficient concatenation.
Think of a "string" as a sequence of "characters".
Now what is a "character"? (From the viewpoint of a user.)
It is *not* the same thing as a Unicode code point.
The thing that the user expects to step over with a single
Ctrl-F or Right Arrow keypress may well be represented by
several Unicode code-points.
Using lists means that we have a choice: we can represent a text as a
list
of Unicode codepoints, but we can ALSO represent a text as a list of
things-the-user-thinks-of-as-characters, where each element might be a
single code-point, or it might be a list of code-points. This second
representation is more convenient for stepping over; far more
convenient.
But it is also easy to flatten when we've a need to.
> Strings can be encapsulated of course, but this is just a workaround
> for the fact that string constants are completely undistinguished,
> and it means you have to unwrap them before using any of the built-
> in string functions.
This is in no way different from other data types in Erlang.
When does {1,1} represent the pixel near the top left corner of a
window,
when does it represent the rational number 1 = 1/1, when does it
represent
a latitude/longitude pair, when does it represent the complex number
1+i,
when does it represent "board 0, connector 0", &c.
In *all* cases involving Erlang data, you as programmer have to KNOW
what you are expecting.
I will buy this as an argument for compile-time types.
> How many times have developers had to explain why printed output is
> showing up as a list of numbers?
Do you mean developers OF Erlang or developers IN Erlang?
If the first, the answer is "as many times as they have been asked by
people who didn't bother to read the documentation thoroughly".
If the second, the answer is "as many times as they have provided raw
Erlang terms to non-developers."
> How many hacks are there in the emulator in order to deal with
> strings efficiently?
Very few.
> (I'm thinking of the binary representation of terms for example.)
> Why can I tack atoms and floats and record values onto a list that
> was created from a string constant, and then have io:write choke
> halfway through printing it?
Because Erlang has no compile-time types and you were careless.
It's not a problem I've ever had in Prolog or Erlang.
>
> The only benefits of the current implementation are:
> - There's less work required of the language designer.
+ There is far less for the language USER to remember;
there is only one incrementally-constructible sequence type
and only one set of function names to remember.
If you don't think that's a problem, you've never found yourself unhappy
with Scheme because STRING-LENGTH and STRING-APPEND are different
functions
from LENGTH and APPEND, and you've never found your program "choke
halfway"
because you forgot to call STRING->LIST or LIST->STRING at some point.
And you have never found yourself hopping mad because there is some
function
that *is* available for lists but *isn't* available for strings so you
have
to do (list->string ... (string->list ...) ...) just to patch around
this.
>
> - Since you can treat strings as lists, you get to reuse some of
> your list processing functions. But really, the usefulness of this
> is overrated. How often do you really need to reverse a string,
Fairly often, actually. Tail recursive functions building a string
commonly end by reversing it.
> or repeat it some number of times,
Fairly often, actually. In fact strings are almost the only lists I do
that to.
> or calculate the maximum character value..
How else would you decide whether all the characters
- are BMP (maximum <= 65535)
- are Latin 1 (maximum <= 255)
- are ASCII (maximum <= 127)
> at least with string-specific versions of the functions you need it
> wouldn't be possible to corrupt your string.
I've used Scheme enough to detest string-specific versions of functions.
Since lists are immutable, it is impossible right now to corrupt a
string.
>
> - It's easier to iterate through characters, for a narrow definition
> of character. A Unicode-aware implementation should let you iterate
> through either code points or composed characters.
"composed character" is not in the Unicode glossary;
I suspect you mean "combining character sequence".
There is nothing about lists that prevents an Erlang unicode: library
offering the facility of iterating over combining character sequences.
>
>
> If Erlang strings were in fact lists of Unicode code points then the
> situation might be more tenable, but they aren't,
Precisely BECAUSE Erlang strings are nothing other than lists of
numbers,
there is nothing that stops you using Unicode code points in "string"
data.
We are agreed that Erlang needs good Unicode support.
We are agreed that at the very least any places that limit "strings"
to 8 bits should be relaxed.
I hope we are agreed that library support for Unicode-aware operations
can be at least prototyped without a special data type.
Larceny's string representations are of course tuned for a language
with mutable strings, which Erlang isn't.
Tony Rogvall
>
> How about,
> %% <3.1415, 1.0>
> V1 = <<16#40, 16#49, 16#0E, 16#56, 16#3F, 16#80, 16#00, 16#00>>,
> %% <1.0, 1.6180>
> V2 = <<16#3F, 16#80, 16#00, 16#00, 16#3F, 16#CF, 16#1A, 16#9F>>,
> vec:add(single, V1, V2).
>
This is a more promising start! Today floats are allocated as separate
objects so there
is no way to use SIMD instructions on tuple with floats anyway!!!
>
> obviously V1 and V2 would normally be created with helper functions.
> The
> advantage of using binaries would be that you would have to add a new
> type to Erlang and could more easily do DSP functionality on an input
> stream, eg GSM codecs using for VOIP, before having to optimise with C
> or another lower language. The first parameter to vec:add/3 would be
> one
> of the atoms: single, double, octet, short, long, or longlong.
>
> What about matricies? list of binaries?
>
I suggest first to implement the operation(s) you showed, possibly
adding alignment support
to the allocation of the vectors since many SIMD instructions operates
best when given 16 bytes aligned
pointers. Rough code ahead ;-)
Future binary comprehension could use an updated syntax to handle this
in a neat way.
[ <<X+Y:32/float>> || <<X:32/float>> <- V1 ; <<Y:32/float>> <- V2 ]
Note that the expression X+Y must have a special treat and that ; in
this comprehension expression means
"parallel". This would basically be compiled to vec:add(single, V1,
V2).
/Tony
jm
>
> This is a more promising start! Today floats are allocated as separate
> objects so there
> is no way to use SIMD instructions on tuple with floats anyway!!!
>
>
> I suggest first to implement the operation(s) you showed, possibly
> adding alignment support
> to the allocation of the vectors since many SIMD instructions operates
> best when given 16 bytes aligned
> pointers. Rough code ahead ;-)
>
> Future binary comprehension could use an updated syntax to handle this
> in a neat way.
>
> [ <<X+Y:32/float>> || <<X:32/float>> <- V1 ; <<Y:32/float>> <- V2 ]
>
> Note that the expression X+Y must have a special treat and that ; in
> this comprehension expression means
> "parallel". This would basically be compiled to vec:add(single, V1, V2).
That works for vectors. How about matricies?
The reason I initially stated vec:add/3 as an example is that this could
be implemented as a C-port module. Then if this proves successful the
atomic could be rolled into the VM eventually and the rest moved to a
normal library. At which point any changes needed to erlang syntax would
be readily apparent.
Where would you recommend starting? Any good references on parallel
vector and matrix operations/algorithms?
Jeff.
Alceste Scalas
> The reason I initially stated vec:add/3 as an example is that this could
> be implemented as a C-port module. Then if this proves successful the
> atomic could be rolled into the VM eventually and the rest moved to a
> normal library. At which point any changes needed to erlang syntax would
> be readily apparent.
>
> Where would you recommend starting? Any good references on parallel
> vector and matrix operations/algorithms?
Instead of reimplementing everything, I'd suggest to start here:
http://www.netlib.org/blas/
http://math-atlas.sourceforge.net/
The BLAS interface does not support integer arithmetics, but it's a
well-estabished standard. Furthermore, if the Erlang VM is dynamically
linked against a BLAS library (either directly or through a driver),
then users/developers could choose their highly-optimized
hardware-dependant implementation without recompiling everything.
Here at CRS4 we are still experimenting with Erlang as a tool for
developing distributed numerical applications. We've developed a BLAS
binding, based on the Erlang Foreign Function Interface EEP [1,2] ---
and in fact, we've created and proposed the Erlang FFI just to make it
easier to interface libraries with tens or hundreds of functions. In
general, if you plan to use Erlang for numerical and scientific
computation, then you'll definitely need an easy way to interface to
existing code.
Our current BLAS interface is something like:
blas:init(),
%% Create an identity matrix
I = blas:eye(s, % Precision: 's'ingle or 'd'ouble
3), % Rows and columns
V = blas:vector(s, 3, [1.0, 2.0, 3.0]),
V2 = blas:mul(blas:mul(2.0, I), V),
VL = blas:to_list(blas:transpose(V2)).
%% VL is:
%% [[2.00000,4.00000,6.00000]]
Matrices and vectors are implemented as records containing some
information (dimensions, row/column ordering, transposition...) and a
binary with floating point values. The BLAS binding consists of ~950
lines of Erlang code (the 'blas' module) and ~300 lines of C (various
helper functions).
Regards,
alceste
References:
[1] http://muvara.org/crs4/erlang/ffi
[2] http://erlang.org/eeps/eep-0007.html
--
Alceste Scalas <alc...@crs4.it>
CRS4 - http://www.crs4.it/
Thomas Lindgren
--- jm <je...@ghostgun.com> wrote:
> Where would you recommend starting? Any good
> references on parallel
> vector and matrix operations/algorithms?
I think Golub and Van Loan is a good point to get
going, though the field itself is vast. Also, take a
look at Fortran 90:s array syntax and how it is
compiled. (Matlab is probably similar.)
By the way, I also think it's quite feasible to
compile a suitable Erlang-like sublanguage (with
aligned binaries) into native-speed, native-space C
code, including the use of SIMD/vector intrinsics.
(Integration with the regular Erlang VM is another
issue :-)
Best,
Thomas
____________________________________________________________________________________
You rock. That's why Blockbuster's offering you one month of Blockbuster Total Access, No Cost.
http://tc.deals.yahoo.com/tc/blockbuster/text5.com
jm
> Il giorno mar, 08/04/2008 alle 16.13 +1000, jm ha scritto:
>> The reason I initially stated vec:add/3 as an example is that this could
>> be implemented as a C-port module. Then if this proves successful the
>> atomic could be rolled into the VM eventually and the rest moved to a
>> normal library. At which point any changes needed to erlang syntax would
>> be readily apparent.
>>
>> Where would you recommend starting? Any good references on parallel
>> vector and matrix operations/algorithms?
>
> Instead of reimplementing everything, I'd suggest to start here:
>
> http://www.netlib.org/blas/
> http://math-atlas.sourceforge.net/
I knew of blas (from lapack) or rather had heard of it, but hadn't heard
of math-atlas. Having never used it before I was browsing their website
looking for a starting point to access its suitability. Trying to
understand the wheel not re-invent it that is. The most I was hoping to
do was the initial investigation and, at worst, write a thin bridge
between Erlang and a suitable library. Any more than that and I was
going to bow out.
Nice to see you have saved someone else a lot of work! Not being very
familar with blas: Is the license compatible with Erlang? Assuming yes,
are you in a position to make any of the code public? How well does it
perform?
On the reimplementation front. There is something to be said for adding
SIMD support at a lower level. After I asked the question about adding
vector support I realised that my use of "vector" was too vague. There
are actually two valid intepretation:
1) SIMD at the low level. This would mean changes to the language.
2) Vector and matrix operations. This can easily be done by calling an
external library.
Lastly, what are the "distributed numerical applications" that Erlang is
being investigated for?
thanks, very informative.
Jeff.
Ulf Wiger (TN/EAB)
> --- jm <je...@ghostgun.com> wrote:
>> Where would you recommend starting? Any good
>> references on parallel
>> vector and matrix operations/algorithms?
>
> I think Golub and Van Loan is a good point to get
> going, though the field itself is vast. Also, take a
> look at Fortran 90:s array syntax and how it is
> compiled. (Matlab is probably similar.)
>
> By the way, I also think it's quite feasible to
> compile a suitable Erlang-like sublanguage (with
> aligned binaries) into native-speed, native-space C
> code, including the use of SIMD/vector intrinsics.
>
> (Integration with the regular Erlang VM is another
> issue :-)
>
> Best,
> Thomas
While we're at it, I'd like to throw in a wish to
be able to handle real-time manipulation of media
streams in Erlang (with good performance, that is).
Think, for example, transcoding of video streams.
Given Erlang's reputation as a language for telecoms,
I don't think this is too far-fetched, even if it
were to require some special syntax.
(Just doing SIMD operations on binaries seemed too easy. ;)
BR,
Ulf W
Christian S
> be able to handle real-time manipulation of media
> streams in Erlang (with good performance, that is).
>
> Think, for example, transcoding of video streams.
> Given Erlang's reputation as a language for telecoms,
> I don't think this is too far-fetched, even if it
> were to require some special syntax.
The ps3-platform would be an interesting target for such research.
Anyone on list that run erlang on their ps3 and use the SPEs from it?
Ulf Wiger (TN/EAB)
> --- "Ulf Wiger (TN/EAB)" <ulf....@ericsson.com>
> wrote:
>> While we're at it, I'd like to throw in a wish to
>> be able to handle real-time manipulation of media
>> streams in Erlang (with good performance, that is).
>>
>> Think, for example, transcoding of video streams.
>> Given Erlang's reputation as a language for
>> telecoms,
>> I don't think this is too far-fetched, even if it
>> were to require some special syntax.
>
> to the user base]' rather than the tech work itself?
> :-)
Yes. (:
> Anyway, I think there are plenty of interesting
> applications, including many outside of the telecoms
> field.
I'm sure.
> It's not quite in the core area of current
> Erlang practice, of course.
Not current Erlang practice, no, but I see it as a
fairly natural evolution, especially since the bit
syntax has sort of laid the ground work for bit
manipulation applications. Extending it to support more
complex updates with competitive performance seems like
a very worthy next step.
In experiments we've made in the past, Erlang offers
fairly good stream relay performance, as long as one
doesn't need to do any deep inspection of the data.
Updating the data as well makes it likely that an
Erlang-based solution fails to reach even the lowest
watermark in terms of performance. This is a pity,
since e.g. complex media firewalls etc. ought to be
fertile ground for Erlang, even in the absence of
special hardware. Right now, Erlang is Just Right for
the signaling parts of such an application, but
Totally Wrong for the media parts. But there's a fairly
big grey area, where acceptable performance of an all-
Erlang implementation would be just perfect.
Cryptol, http://www.cryptol.net, might offer some
inspiration, BTW.
BR,
Ulf W
Thomas Lindgren
> be able to handle real-time manipulation of media
> streams in Erlang (with good performance, that is).
>
> Think, for example, transcoding of video streams.
> Given Erlang's reputation as a language for
> telecoms,
> I don't think this is too far-fetched, even if it
> were to require some special syntax.
You mean '[not] too far-fetched [as a feature provided
to the user base]' rather than the tech work itself?
:-)
Anyway, I think there are plenty of interesting
applications, including many outside of the telecoms
field. It's not quite in the core area of current
Erlang practice, of course.
Best,
Thomas
____________________________________________________________________________________
You rock. That's why Blockbuster's offering you one month of Blockbuster Total Access, No Cost.
http://tc.deals.yahoo.com/tc/blockbuster/text5.com
Damien Morton
changes to the language they added to make the module nicer to use.
Im thinking particularly of the array slice notation.
tsuraan
>
> blas:init(),
>
> %% Create an identity matrix
> I = blas:eye(s, % Precision: 's'ingle or 'd'ouble
> 3), % Rows and columns
> V = blas:vector(s, 3, [1.0, 2.0, 3.0]),
>
> V2 = blas:mul(blas:mul(2.0, I), V),
>
> VL = blas:to_list(blas:transpose(V2)).
> %% VL is:
> %% [[2.00000,4.00000,6.00000]]
I'm curious, how much copying goes on here? With the normal port
method, I would imagine that every function call would involve
serializing the data from erlang to the c-port, doing the work in c,
then serializing it to send back to erlang. Does the FFI allow
everything to be stored as binaries, and then you can just hand the
binaries from the erlang machine to atlas directly without any data
munging or copying?
I think I'll have to look into the ffi proposal. It sounds interesting, anyhow.
Richard A. O'Keefe
> In my opinion the reason, that Erlang needs specialized datatypes
> like:
> binary, bitstring, string, matrix, etc. it's because it's
> dynamically typed.
You seem to be under the impression that adding specialised data types
is
cheap. It is not. It requires new tags (binaries use three tags, and I
would expect strings to require at least as many, but there are only two
tags unused in that block; see erl_term.h), new instructions, changes to
the compiler and HiPE, backwards-incompatible changes to the binary
representation of terms (which might not be a bad thing; we could do a
better job than the current one), and of course a thorough check of the
library to ensure that none of the code assumes that the only possible
data types are, well, the only currently possible data types.
I don't say it's not possible.
I don't say it's never warranted.
I do say it's not easy, not cheap, and had better pay off.
Erlang *has* binaries (which are also bitstrings) because they do a job
that (a) Erlang needs done and (b) can't be done with any combination of
other data types. What needs doing of course depends on the kind of
tasks
a programming language was devised for: Erlang's data types would not
do
for Fortran's tasks, and Fortran's data types won't do for Erlang's
tasks.
In particular, matrices are part of Fortran's tasks.
If I want Fortran, or APL, or Octave, or R, I know where to find them.
If I want distributed concurrent "scientific calculations",
http://www.sdl.sri.com/papers/concurrency95-preprint/
is the kind of thing I would like, and something not entirely unlike
that
might be a good way for Erlang to do it, IF that became part of Erlang's
application domain.
I note that there isn't just one kind of matrix.
Dear old LINPACK distinguished between general, triangular, and banded
matrices. Nowadays we have the Sparse BLAS, which distinguish between
"(1) ordinary sparse matrices, (2) sparse matrices with a regular block
structure, and (3) sparse matrices with a variable block structure."
(ACM TOMS 28.2, the model implementation in f95 article.)
All of this could be hidden from the user of course, but if you
seriously
care about efficient matrix calculations, *someone* has to recognise the
different kinds of matrices and deal with them appropriately. If you do
not care about efficient matrix calculations that much, then you don't
need a matrix data type in Erlang. (Hint: when I care about matrix
efficiency that much, which I sometimes do, I use Fortran 95 and the
hardware vendor's heavily tuned library.)
> When Erlang designers/implementers needed to process sequences of
> bytes,
> they for some strange reason didn't used tuples or lists of
> integers, but
> introduced a new datatype.
Nothing strange about it. As my previous message made clear, shipping
sequences of bytes around is what Erlang is *for*, and no other data
type
in Erlang is suited to the job. As soon as Haskell started being used
in
real earnest for network applications, behold, Haskell acquired a
ByteString data type as well. It is a bit misleading to call binaries a
"new" data type; binaries have been in Erlang since very early days.
Was there _ever_ a time that Erlang was available outside Ericsson
without
binaries?
> Same goes for recently introduced bitstring
> datatype: why not to use tuples or lists of true or false atoms? :-)
The bit string data type isn't really a new data type. It is just a
relaxation of the binary data type. Per Gustaffson's "Programming
Efficiently With Binaries and Bit Strings" explains that
"Bitstrings are so called sub-binaries" and
"any binary is also a bit string". My understanding of what he wrote
is that while binaries are logically a special case of bit strings,
the implementation is basically the old binary implementation with the
"sliced" version giving size and offset in bits instead of bytes.
(This is pretty much how the OCaml clone of Erlang bit strings works;
see http://et.redhat.com/~rjones/bitmatch/html/Bitmatch.html
which says "Internally a bitstring is stored as a normal OCaml string
together with an offset and length, where the offset and length are
measured in bits." Of course, OCaml is strongly statically typed.)
This is not as radical a change as a new data type, and it fits
perfectly with Erlang's core application area.
When the trade-offs are right, I dare say Erlang *will* acquire a string
data type. I note that the Unicode 5.0 book promises quite explicitly
that
there will be no characters allocated in top topmost plane, so I shall
have
to stop saying that Unicode characters are 21 bits and start saying
that they
are 20 bits. Three kinds of character storage will do: one byte per
character (Latin 1), two bytes per character (BMP), and three bytes per
character (full Unicode). Perhaps making all character strings be
slices
of binaries, with a new tag, and a field giving the character width,
might
just possibly be enough.
Understand, however, that that will never be an adequate string
representation
for all purposes, just as the equivalent in Java (every string is a
slice of
an array of 'short') is not adequate for all purposes. We shall
*still* want
to use iolists.
> I
> think there is a lot of optimization behind the scenes and runtime
> trying to
> guess on every list if it's a string or not.
Wrong.
> If it's string it may use a
> more compact representation. The question is why to guess, if we have
> dynamically typed language, where each value tagged by a datatype
> anyway?
Your starting point is wrong here. The Erlang run time system never
tries
to guess whether a list is a string or not, only whether it is a list of
bytes, and then only when encoding a term as a binary. It's done at
that
point in order to save some combination of space and network
transmission
time, just as it specially optimises the transmission of atoms, in
order to
try to make "symbolic" network protocols as efficient as "binary" ones.
>
> My point is Erlang tuples and lists are polymorphic collections and
> when you
> want to have homogenous collections.
And the point I made in my previous message is that when you are
processing
text you DON'T want to have a homogeneous (NOT "homogenous", by the way)
collection.
> Also all datatypes mentioned above also
> must provide indexing and subslicing, which is somewhat not very
> effective
> when underlying represntation is linked lists.
At this point I have lost track of what "all datatypes mentioned above"
were.
It is really really important to understand that indexing into strings
never did make any sense as an operation on text, except as a means of
iterating through the characters. Certainly it made no sense in ISO
646 (ASCII), where the construction of composite characters using
backspace was explicitly licensed by the standard. (That is, to get
é you were expected to do [e,backspace,'] or [',backspace,e].) This
was explicitly disallowed in ISO Latin 1, but Unicode brought back an
equivalent. If you access a randomly chosen element of a sequence of
codepoints, you have no right to expect to be able to interpret it.
Since 1989 C has allowed variable width encodings for characters. (For
that matter, Interlisp-D was doing the same back in 1984.)
If you land on U+202C, for example (Pop Directional Formatting), what
are you supposed to do about it?
Basically, if you expect to *interpret* Unicode, the only way that it
was designed to be possible, and the only way that it IS possible, is
strictly sequentially. That is, "random access indexing" is NOT a
relevant operation for Unicode text, and the fact that lists are not
good at it is of no importance at all.
Does anyone out there understand "variation selectors"? I don't.
Slicing is important, BUT there is a very simple very cheap way to
represent a slice of a list: {List_Suffix, Length}. The more study
I put into Unicode (and it is really quite hard to keep up: it was
bad enough when Unicode added language tag characters in violation of
its old core design principles, but I now find that they are "strongly
discouraged" -- looks like a political battle swayed one way and then
the other) the more I'm convinced that the only safe way to take
Unicode strings apart is via some kind of regular expressions.
And that is why I think it is more important to get a clean design for
regular expressions in Erlang that can be implemented very efficiently
than to jump into strings, because good string patterns are going to be
absolutely essential for Unicode string processing.
>
> About Unicode-support in string datatype, it must be practical, not
> 100%
> right, so something like utf16 is good enough for me.
Something which is not 100% right is not practical.
There are now *more* than 100 000 characters in Unicode.
(For example, the German lower case "sharp s" character now
has an upper case version, which, however, you are normally
not supposed to use. So lower case sharp s _is_ the lower
case version of upper case sharp s, but upper case sharp s is
NOT the upper case version of lower case sharp s, "SS" is.)
Just at the moment I have had a surfeit of programs not working 100%
correctly. I know we are human and cannot _achieve_ perfection, but
that is no reason to AIM at folly.
>
> In Haskel you specify type of element (I do not know this language,
> just
> guessing the syntax, I have no idea how to represent vector in
> Haskel, so
> everything is a list):
>
> type String = [Char]
This one is right.
>
> type Binary = [0..255]
There are no subrange types like 0..255 in Haskell.
As it happens, there are C-like Int8, Int16, Int32, Int64 (signed)
and Word8, Word16, Word32, Word64 (unsigned) in addition to the
old Int and Integer (unbounded). The actual implementation is
data ByteString = PS {-# UNPACK #-} !(ForeignPtr Word8)
{-# UNPACK #-} !Int -- offset
{-# UNPACK #-} !Int -- length
which is pretty much the same as an Erlang (sliced) binary.
However, the one that is suitable for incremental calculations is
Data.ByteString.Lazy, where we find
newtype ByteString = LPS [P.ByteString] -- LPS for lazy packed string
Both Data.ByteString and Data.ByteString.Lazy go to a great deal of
trouble to look as much like lists as they can. Be it noted that
Data.ByteString.Lazy does not offer constant-time indexing or slicing.
>
> type Bitstring = [Bool]
There is no such animal. There's no particular reason why there could
not be.
>
> type Matrix = (Int,Int,[Double])
The simplest version of Matrix would be
type Matrix = Array (Int,Int) Double
Nowadays Haskell offers a bewildering range of arrays: unboxed or boxed
strict or lazy, pure, in the IO monad, in a state change monad, ...
For efficient calculations, one would want to use Alberto Ruiz's
hmatrix library, which is layered on top of the BLAS, LAPACK, and GSL.
Data.Packed.Matrix and Data.Packed.Vector make good use of Haskell's
type system.
There are two fundamental things going on to make packages like hmatrix
work well in Haskell:
(1) Tight coupling with foreign code.
(2) Strong static Hindley-Milner typechecking extended with type-
classes.
I would expect to be able to do the same kind of thing in Mercury or
OCaml.
If the Clean FFI were better documented, I would expect to be able to do
the same kind of thing in Clean. Oh, SML fits here too. Because of the
type system, they are all *expecting* to be extended with thousands of
new
types. Because of the tight coupling with foreign code, they are all
*expecting* to be linked with untrustworthy code that they will fully
trust.
These days it is a perfectly reasonable thing to develop network
applications
in SML or Haskell or Mercury as long as you don't want hot loading and
very
large numbers of processes. (I don't know OCaml well enough to tell
what it
is like for network programming these days, although the fact that
there's a
package giving it a clone of Erlang's bit syntax makes me wonder...)
> BTW: I think Haskel's tuples are done right. I never understood why
> Erlangs' functions have arity, when every function can have single
> argument
> as a tuple.
Well, why do C functions have arity, when any C function can have a
struct as an argument?
ML has a similar type system to Haskell (except for typeclasses).
In Haskell, it's normal practice to use curried functions, e.g.,
append :: [a] -> [a] -> [a] -- really ++
In ML, it's normal practice to use uncurried functions, e.g.,
append : 'a list * 'a list -> 'a list (* really @ *)
Having used both, I find the ML convention a pain. ML compilers
have to go to some trouble to avoid actually allocating storage
for these tuples, and in fact cannot always do so.
Erlang's functions have multiple arguments because that's the way
people like to think about them. It is a member of a group of languages
including Prolog, Strand 88, Parlog, Concurrent Prolog, GHC, Janus, and
others I've forgotten, not to forget Mercury. It is a coherent and
useful
design. We don't all have to do the same thing. (I would argue that
the
SML interfaces are incoherent. Why should map be curried but append
not?)
> Haskel tuples must have at least 2 elements. So any single
> element is a tuple of 1? It's the same like in Matlab - scalar is a
> matrix
> of 1x1.
> But in Erlang x and {x} is not the same. Probably it's because
> Erlangs
> tuples are both tuples AND polymorphic vectors.
Matlab's treatment of scalars is a pain in the neck.
R does the same thing (because S does).
Much as I love R, this is not one of its best features.
As in many other aspects of array crunching, APL got this right.
In APL, a number has rank 0, a single-element vector has rank 1,
a single-element matrix has rank 2, and so on. It does not muddle
them up.
Haskell had precursors, notably Lazy ML, which copied much from ML,
in which tuple types are written using infix *. Where Haskell has
(Int,Bool,Char), SML has int * bool * char, and you simply cannot
express one-element tuple types in that syntax.
Erlang owes much to Strand 88. Several other Prolog-family languages,
notably Sigma Prolog and Concurrent Prolog, also have tuples with 0,
1, or more elements. For that matter, SETL (the language devised by
Jack Schwartz at the Courant Institute, explicitly intended to make
(finite) set theory a programming language), identifies tuples and
polymorphic vectors. It's a common enough and handy enough idea.
Alceste Scalas
> Not being very familar with blas: Is the license compatible with
> Erlang?
BLAS is just a standardized API, with several implementations. Some
examples:
* NetLib reference implementation: http://www.netlib.org/blas/
* ATLAS: http://math-atlas.sourceforge.net/
* AMD Core Math Library: http://developer.amd.com/acml.jsp
* Intel Math Kernel Library:
http://www.intel.com/cd/software/products/asmo-na/eng/266858.htm
* nVIDIA CUDA: http://developer.nvidia.com/object/cuda.html
Each implementation comes with its own license (Netlib and ATLAS are
released under BSD-like, GPL-compatible licenses). They are usually
binary compatible, so you can switch between them without recompiling
(as long as you use dynamic linking and don't depend on some
non-standard API extensions).
> Assuming yes, are you in a position to make any of the code
> public?
I hope I'll be able to release the code, but it depends on the FFI
patches --- so it may not be very useful, unless the FFI EEP is approved
in some form.
> How well does it perform?
We tried several ways to integrate BLAS and Erlang. The current
FFI-based implementation is slightly slower than dedicated BIFs, but
definitely faster than a linked-in driver (and definitely easier to
develop, since all the linked-in driver boilerplate code went away).
I can't provide the benchmarks data right now, but we plan to submit a
paper for the next Erlang Workshop.
> Lastly, what are the "distributed numerical applications" that Erlang is
> being investigated for?
Simulation of mechanical and thermodynamical systems.
Regards,
alceste
--
Alceste Scalas <alc...@crs4.it>
CRS4 - http://www.crs4.it/
_______________________________________________
Alceste Scalas
> Does the FFI allow everything to be stored as binaries, and then you
> can just hand the binaries from the erlang machine to atlas directly
> without any data munging or copying?
Yes, it does. The FFI allows both to receive and return binaries and
handle refcounting. Furthermore, several operations do not involve the
C side at all (for example: matrix/vector transposition just changes an
Erlang record field; the same goes for matrix/vector extraction from
existing matrices/vectors).
We developed the BLAS interface (and the FFI in the first place) trying
to avoid copying, unless the data is sent between different Erlang nodes
(and since matrices and vectors are just regular Erlang records, the
Erlang VM can handle them without problems).
Regards,
alceste
--
Alceste Scalas <alc...@crs4.it>
CRS4 - http://www.crs4.it/
_______________________________________________
tsuraan
> to avoid copying, unless the data is sent between different Erlang nodes
> (and since matrices and vectors are just regular Erlang records, the
> Erlang VM can handle them without problems).
That sounds really nice. I sure hope this FFI gets approved soon, or
at least merged into the official Erlang source as an unsupported
feature in testing.
Roger Larsson
For x86, PowerPC PPU, Cell SPE
http://www.bulletphysics.com/Bullet/phpBB3/viewtopic.php?p=4884&f=&t=
Read the "overview document" as it has some very interesting thoughts about
data layout - AoS (Array of Structures) and SoA (Structure of Arrays).
The library supports both layouts.
/RogerL
jm
> --- jm <je...@ghostgun.com> wrote:
>> Where would you recommend starting? Any good
>> references on parallel
>> vector and matrix operations/algorithms?
>
> I think Golub and Van Loan is a good point to get
> going, though the field itself is vast. Also, take a
> look at Fortran 90:s array syntax and how it is
> compiled. (Matlab is probably similar.)
Got five minutes and tracked it down. Thought I'd post the full citation
for anyone else interested
http://www.citeulike.org/user/sprite/article/252315
G. H. Golub & C. F. Van Loan (1996). Matrix Computations (Johns Hopkins
Studies in Mathematical Sciences). The Johns Hopkins University Press.
Jeff.