Primitives and array computation

Hi,

I have to build a class which makes intensive mathematical
computations (which I will connect to a Squeak GUI).

For this purpose, I tried the mathematical functions on arrays, and
evaluated the performances:

Examples:

Time millisecondsToRun: [

tab1:=(1 to: 1000000).

tab1 collect: [:each | each cos]]

 7716


Time millisecondsToRun: [

(1 to: 1000000) cos]

 7780


Time millisecondsToRun: [

tab1:=(1 to: 1000000).

tab1 do: [:each | each cos]]

 1231


The best is about 1s for computing cos(x) 1000000 times.

By reducing the the vector size, the three algorithms seem to be
equivalent in time (I guess that there are additional time consumed
for memory management).


Now, in comparison, the same tests for a C implementation is about
0.002s, about 500x better.

By browsing the classes, it did not saw primitives acting directly on
arrays, and it seemed that the loops are done by Squeak...
An explanation of this dramatical difference.

So, my question is: does the VM implements primitives for computing
mathematical functions on arrays?

Best regards,

FD
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

Am 10.07.2008 um 18:47 schrieb Frederic Dambreville:

> So, my question is: does the VM implements primitives for computing
> mathematical functions on arrays?


Generally, no. It's also hard to do in a general Array, since each  
Float is a full object, any arithmetic on it does unboxing and boxing  
of a newly allocated Float object. To speed this up considerably you  
would have to create primitive array that do not hold objects but.

There is the class FloatArray which works on a primitive array of 32-
bit floats, but only very basic operations are supported by the  
FloatArrayPlugin.

- Bert -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

> Generally, no. It's also hard to do in a general Array, since each
> Float is a full object, any arithmetic on it does unboxing and boxing

OK!
The way I use it, this implies a strong limitation of squeak; each
algorithm with intensive mathematical computation will need a
dedicated primitive...

> of a newly allocated Float object. To speed this up considerably you
> would have to create primitive array that do not hold objects but.

?'but'?

So, I understand that I need:
- intermediate classes, for storing 'true' arrays,
- translators for converting to/from standard squeak classes from/to
these intermediate classes,
- primitives for array computation on these classes
or something like that.

A lot of work...
Are there people, which have already done a part of the job? Or are
interested by such classes and primitives?

Thanks,

FD
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

Frederic Dambreville a écrit :
When you think of it, it's pretty well the case of Matlab:

Matlab interpreter is very inefficient.
(Don't you write a loop in matlab !).
And each arithmetic computation
    a = b*c;
allocates a mxArray... like Smalltalk will allocate a Float...

However, Matlab has much of the needed array primitives.
Given that, the idea is to implement such array primitives in Smalltalk too.
I started to interface Blas and Lapack to Smalltalk, this is called
Smallapack (search with google).

Though i have a decently working version under Visualworks and Dolphin,
the Squeak one is unfortunately bleding edge (that means the tests do
not pass, worse, they can crash or block your image).

By now, i'm not working on it.
But if you want to use it as a starting point, i can provide some help.

Cheers.

Nicolas

_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

Am 10.07.2008 um 22:09 schrieb Frederic Dambreville:

... but instead hold floats directly so that primitives can operate  
without boxing and unboxing. This is how FloatArray works.


See Nic's mail.

- Bert -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

> So, I understand that I need:
> - intermediate classes, for storing 'true' arrays,
> - translators for converting to/from standard squeak classes from/to
> these intermediate classes,
> - primitives for array computation on these classes
> or something like that.

  The KedamaPlugin2 has some more operations defined, including the
mixed FloatArray and WordArray operations, and operations with
mask-bits.

  The following is probably a squeak-dev topic, but one thing that is
conceivable is to have a primitive that takes a function name as
string ('cos', 'sin', etc.) and in the primitive, it looks up the
symbol in various library can call it:

-----------------
  primApply: aString toArray: aFloatArray into: resultArray

      self var: 'val' type 'double'.
      func := dlsym(aString).
      0 to: aFloatArray size -1 do: [:i|
         val := aFloatArray at: i.
         resultArray at: i put: (self cCode: '(*func)(val)').
      ].

-----------------

-- Yoshiki
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

>
> When you think of it, it's pretty well the case of Matlab:
>  
That's it. Actually, I was also thinking about something like the J
language.

> Though i have a decently working version under Visualworks and Dolphin,
> the Squeak one is unfortunately bleding edge (that means the tests do
> not pass, worse, they can crash or block your image).
>
> By now, i'm not working on it.
> But if you want to use it as a starting point, i can provide some help.
>  
I will look at it. However,  my contribution in the close future will be
restricted  to my current  need (a Bellman-like equation propagation).

See you,

FD


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

It is interesting to look at the Computer Language Benchmarks Game and
see the relative speed of dynamic vs statically typed languages on
micro-benchmarks (these are math heavy tests). I didn't look at the
Lisp derivatives to see if they were using dynamic or static typing (I
believe they can use either as required), but it looks like the
fastest purely dynamically typed language I've used is Python with
Psyco. That is about 7x slower than the fastest C++ implementation.
The fastest smalltalk in the game is VisualWorks at about 10x slower
than C++ and Squeak is about 50x slower than C++.

http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all

I understand in theory it is possible to have good performance out of
dynamicly typed languages, but it seems the only way to get good
performance today is to punt out of your dynamic language into a C or
Fortran library for all the heavy lifting. It's a shame really. In
fact, I think there is a high-speed compiler for Smalltalk that is
typeless, but it was swallowed by Sun before it took off.

David


On Thu, Jul 10, 2008 at 4:27 PM, Frederic Dambreville
<[hidden email]> wrote:


--
David Finlayson, Ph.D.
Operational Geologist

U.S. Geological Survey
Pacific Science Center
400 Natural Bridges Drive
Santa Cruz, CA 95060, USA

Tel: 831-427-4757, Fax: 831-427-4748, E-mail: [hidden email]
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners