| Author |
Message |
|
| Guest |
 Posted: Mon Nov 15, 2010 10:13 pm |
 |
|
|
Guest
|
And a solution that uses the fact that A and B can not both be odd.
py6R(N)->
EvenA = lists:flatten([[{A,B,C}, {B,A,C}] ||
A <- lists:seq(2, N div 2, 2),
B <- lists:seq(A + 1, max(A, N*(N-2*A) div (2*(N-A)))),
C <- [trunc(math:sqrt(A * A + B * B))],
A + B + C =< N,
A*A + B*B =:= C*C]),
OddA = lists:flatten([[{A,B,C}, {B,A,C}] ||
A <- lists:seq(1, N div 2, 2),
B <- lists:seq(A + 1, max(A, N*(N-2*A) div (2*(N-A))), 2),
C <- [trunc(math:sqrt(A * A + B * B))],
A + B + C =< N,
A*A + B*B =:= C*C]),
lists:sort(EvenA ++ OddA).
Morten.
On 11/15/10 10:51 PM, Morten Krogh wrote:
> Hi again,
>
> The py3R can be made to have a much better check on the bounds of the
> lists.
> Also, you should use that the triples are symmetric so {A,B,C} can be
> replaced with {B,A,C}.
>
> py5R(N)->
> lists:sort(lists:flatten([[{A,B,C}, {B,A,C}] ||
> A <- lists:seq(1, N div 2),
> B <- lists:seq(A + 1, max(A, N*(N-2*A) div (2*(N-A)))),
> C <- [trunc(math:sqrt(A * A + B * B))],
> A + B + C =< N,
> A*A + B*B =:= C*C])).
>
>
>
> the max(..,..) is really stupid, but I learnt something new about
> erlang, namely that
>
> lists:seq(10, , for example, produces an exception, whereas
> lists:seq(10,9) = []
>
> if lists:seq(A,B) = [] for A > B, the max above could have been removed.
>
> Morten.
>
>
> On 11/15/10 10:28 PM, Jesper Louis Andersen wrote:
>> On Mon, Nov 15, 2010 at 4:21 PM, Fred Hebert<mononcqc@gmail.com> wrote:
>>> I think the first thing to do before optimizing is understanding how
>>> you use
>>> the data. In the case of Pythagorean triplets like these, the right
>>> question
>>> might as well be "how many triplets do I need? What values do I need
>>> to work
>>> with?"
>> Let me add:
>>
>> Optimization is many things. One of the tenets are how easy it is to
>> change your implementation, facing new knowledge. If you look at some
>> of the optimized variants, it should be fairly obvious that many of
>> them provide impressive speedups (for large N) with very few changes
>> to the original code as soon as an observation has been made.
>>
>> My experience is that C, C++ or Java tend to require much more work
>> for these iterations. It turns out there is more to fast code than
>> just having a language isomorphic to assembly 
>>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 1:56 am |
|
|
|
Guest
|
On 16/11/2010, at 4:02 AM, Edmond Begumisa wrote:
> Hello Richard,
>
> I have a question...
>
>> Erlang is a fine tool for jobs like this one.
>
> Interesting... I would have never thought this. I would have instinctively reached for a language with mutable memory, thinking that this would make the most sense for combinatorial* work (I don't know this for fact, and I could be very wrong, but that's what instinct would tell me.)
> * I've been calling this permutation but I don't know if that's accurate.
It isn't. "Permutation" has a very specific meaning, which does not apply here.
Let me quibble slightly: *memoisation* can help a lot for some combinatorial
algorithms, but mutable memory as such doesn't strike me as obviously useful.
(Indeed, since mutable memory makes memoisation invalid, it can seriously get
in your way.) Good support for large integers helps a lot.
Different algorithms may well have different needs.
>
>> There is little point in optimising a bad algorithm.
>
> Well put. But say you have an 'ok' algorithm. Not the best, but not blatantly flawed either.
I have a C program to compute various things from a data set which consists of
a hundred million lines, each containing four non-negative integers. My
program had to read it several times. (The first pass determines the sizes
of major areas; the second pass determines the size of minor areas within
major areas; the third pass loads the data.) It gets the effect of sorting
without actually sorting (or more precisely, by count-sorting). The first
version of the program took 68 seconds per pass on the fastest machine I
had access to. Considering that wc takes 20 seconds to _not_ process the
numbers in the file, that didn't seem too bad. But bypassing stdio and using
my own code let me get the time down to 6 seconds per pass, which means that
I can afford to run the program a lot more often.
That was a case where there was a _good_ algorithm, but a horrible library.
(Time is linear in the size of the input; results depend on all of the input;
up to a constant factor the algorithm is as good as it gets.)
But in the case we are discussing here, the initial algorithm was O(N**3)
when an O(N**2) algorithm -- in fact, several of them, there's even a
Wikipedia article on enumerating Pythagorean triples -- was not hard to find.
>
> So my question is: if version 1 isn't performing "reasonably" acceptably for Garcia's purpose, and version 1 isn't blatantly flawed.
To me, version 1 *IS* blatantly flawed.
In a pythagorean triple (a,b,c), a and b uniquely determine c,
so it seems *obvious* that a quadratic algorithm should be sought.
(It is not obvious that one *exists*, just that it should be sought.)
Make no mistake: I have used brute force algorithms quite happily myself.
But I never blame the language for the performance I get when I do so!
> Isn't this a strong indicator that he's using the wrong tool?
Ah, but what precisely is "the tool" in question?
- functional languages as such?
- Erlang?
- list comprehensions as such?
- Erlang's current implementation of list comprehensions?
Here are some more times. Erlang R14A, MacBook Pro.
8> pyth:t(p3, 300).
{p3,300,{length,146},{msec,10}}
9> pyth:t(p2, 300).
{p2,300,{length,146},{msec,210}}
10> pyth:t(p1, 300).
{p1,300,{length,146},{msec,970}}
11> pyth:t(p0, 300).
{p0,300,{length,146},{msec,420}}
What's p0?
It's the utterly naive cubic loop nest, with the loops written
as function calls working on integers, with the only list in
existence being the one that's being built.
The time for p0 was 420 milliseconds in Erlang.
On the same machine, the same function, the time was
91 milliseconds in SML/NJ.
SML/NJ MLton Erlang
n=100 L= 34 s=0.004 m=0.004 e=0.020
n=200 L= 86 s=0.028 m=0.027 e=0.130
n=300 L=146 s=0.090 m=0.086 e=0.410
n=400 L=210 s=0.213 m=0.202 e=0.980
n=500 L=274 s=0.415 m=0.394 e=1.900
We see that Erlang is about 5 times slower than SML.
Here's the SML code.
fun p0 n =
let fun fa 0 l = l
| fa a l = fb n a l
and fb 0 a l = fa (a-1) l
| fb b a l = fc n b a l
and fc 0 b a l = fb (b-1) a l
| fc c b a l = fc (c-1) b a (
if a+b+c <= n andalso a*a+b*b = c*c
then (a,b,c)::l else l)
in fa n []
end
It's completely tail recursive, building the list from right to
left. *THIS* is the version that is strictly comparable to any
C or C# code one might plausibly write; it allocates no
storage not part of the result, all looping is done with "while"
loops that compare and increment integers. What's more, SML is
strongly typed, and the Dialyzer should be able to handle this,
so the compiler *knows* it is dealing with integers.
I grant you that this code is not immediately clear.
Clear code in SML might look like this:
fun cat_tab l u f = (* concatenate + tabulate *)
let fun loop i r = if i < l then r else loop (i-1) (f i @ r)
in loop u []
end (* _happens_ not to be in List *)
fun p1 n =
cat_tab 1 n (fn a =>
cat_tab 1 n (fn b =>
cat_tab 1 n (fn c =>
if a+b+c <= n andalso a*a+b*b = c*c
then [(a,b,c)] else [])))
What happens to the times?
(----------direct-----) (------cat_tab------) original!
SML/NJ MLton Erlang SML/NJ Mlton Erlang Erlang
n=100 L= 34 s=0.004 m=0.004 e=0.020 s=0.015 m=0.006 e=0.040 o=0.040
n=200 L= 86 s=0.028 m=0.027 e=0.130 s=0.120 m=0.039 e=0.300 o=0.290
n=300 L=146 s=0.090 m=0.086 e=0.410 s=0.403 m=0.128 e=0.950 o=0.980
n=400 L=210 s=0.213 m=0.202 e=0.980 s=0.954 m=0.303 e=2.240 o=2.280
n=500 L=274 s=0.415 m=0.394 e=1.900 s=1.857 m=0.591 e=4.300 o=4.400
The MLton compiler is a whole-program compiler, and I've a
strong suspicion that it is able to inline cat_tab, so it
may be able to avoid building the answer twice. I'm pretty
sure that SML/NJ isn't inlining cat_tab, and is building the
answer twice. While the Erlang compiler _could_ be taught
about cat_tab, it's not generally wonderful at inlining recursive
procedures, which is why the rightmost column shows list
comprehension not doing so well.
There are two basic issues here:
(1) The Erlang compiler doesn't really handle list comprehension as
native loops; it compiles list comprehensions to recursive
functions. lists:seq(1, N) is not special syntax -- unlike Haskell --
and almost surely builds an actual list.
This could be changed, and maybe some day it will change.
(2) Erlang is compiled incrementally to support hot loading and
(again in order to support hot loading) does not do much if any
cross-module inlining.
MLton is a whole-program optimising compiler, it can SML _are_
allowed to do cross-module inlining by the nature of the language.
This *can't* be changed without making Erlang less useful for its job.
Ah, but there's one more wrinkle!
SML/NJ Erlang SML/NJ Smalltalk
n=100 L= 34 s=0.004 e=0.020 s= 0.250 p1=0.016
n=200 L= 86 s=0.028 e=0.130 s= 1.904 p1=0.109
n=300 L=146 s=0.090 e=0.410 s= 6.567 p1=0.369
n=400 L=210 s=0.213 e=0.980 s=15.581 p1=0.873
n=500 L=274 s=0.415 e=1.900 s=30.218 p1=1.705
(3) Erlang integer arithmetic is *not* limited to some ridiculous
size like 32 bits, it is _semantically_ unbounded integer
arithmetic, with a space-efficient representation and fast
calculation path for small integers. To get something
comparable in SML, you have to use the type IntInf.int
instead of Int.int. And when you do *that*, Erlang really
really shines.
The difference here is that if you use int in C or Java or C#
or SML, then you'll find a positive integer n such that n+1 < 0.
That kind of nonsense simply doesn't happen in Erlang.
It comes with a price, but the price of *not* using a Lispy
(or Smalltalky, or Erlangy) approach to integers is the price
of getting wrong answers without knowing.
The Smalltalk column was done using my Smalltalk-via-C compiler.
It might be possible to go a factor of 2 faster using machine-
specific assembly code, but what we seem to be looking at in
the Erlang column really does seem to be no more than the
price of arithmetic that gives correct results.
And by the way, no, I am not advocating writing code like p0 above
*UNTIL* it has been determined that the function is a performance
problem and that the algorithm is good. Like I said, you should
stick with the clean high level code until you understand the
problem space better.
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 9:33 am |
|
|
|
Guest
|
Hi
I couldn't wrap my head around why my prime number algorithm was so slow and had complexity N^2 or worse.
I realized that it was simply because I forgot to terminate some recursions as early as possible, hence doing an increasing number of irrelevant computations.
Theoretically I had expected N*log^2(N) behavior or so, because the relevant powers of the prime numbers falls of like log(P), which should maybe give N*log(N) behavior,
and then there is also the sorting in the end because the prime number algorithm will produce the triples in another order.
Anyway, I corrected the error, and see something like N*log^alpha(N) behavior.
The runtime for N = 300 is 300 microseconds, and for N = 1,000,000 8 seconds.
The final sorting of the result is actually a major overhead.
Morten.
pythag6(N) when is_integer(N) ->
Primes = sieve(N div 2),
M1M2s = incorporate_primes([{1,1}], [], N, Primes),
lists:usort(lists:flatten([ [{A,B,C}, {B,A,C}] || {M1, M2} <- M1M2s, M1 > M2, A <- [M1-M2], B <- [2*round(math:sqrt(M1*M2))], C <- [M1+M2], A+B+C =< N])).
incorporate_primes(Active_all, Passive_all, _N, []) ->
Active_all ++ Passive_all;
incorporate_primes(Active_all, Passive_all, N, [P|Primes]) ->
{Active, Passive} = incorporate_prime(Active_all, [], [], N, P),
incorporate_primes(Active, Passive ++ Passive_all, N, Primes).
incorporate_prime([], Active, Passive, _N, _P) ->
{Active, Passive};
incorporate_prime([{M1, M2}|M1M2s], Active, Passive, N, P) ->
{EvensM1, OddsM1} = m_times_powers_of_p(M1, N div 2, P, even, [], []),
{EvensM2, OddsM2} = m_times_powers_of_p(M2, N div 2, P, even, [], []),
case {EvensM1, OddsM1, EvensM2, OddsM2} of
{[_], [], [_], []} ->
incorporate_prime(M1M2s, Active, [{M1,M2}| Passive], N, P);
{[_], [_], [_], []} ->
incorporate_prime(M1M2s, Active, [{M1,M2}| Passive], N, P);
{[_], [], [_], [_]} ->
incorporate_prime(M1M2s, Active, [{M1,M2}| Passive], N, P);
_ ->
Evens = [{X, Y} || X <- EvensM1, Y <- EvensM2],
Odds = [{X, Y} || X <- OddsM1, Y <- OddsM2],
incorporate_prime(M1M2s, Odds ++ Evens ++ Active, Passive, N, P)
end.
m_times_powers_of_p(M, L, _P, _Parity, Evens, Odds) when M > L ->
{Evens, Odds};
m_times_powers_of_p(M, L, P, even, Evens, Odds) ->
m_times_powers_of_p(M*P, L, P, odd, [M|Evens], Odds);
m_times_powers_of_p(M, L, P, odd, Evens, Odds) ->
m_times_powers_of_p(M*P, L, P, even, Evens, [M|Odds]).
sieve(N) when is_integer(N) ->
erase(),
sieve(N,2).
sieve(N, K) when K >= N ->
[X || X <- lists:seq(2, N), erase(X) == undefined];
sieve(N, K) ->
cross_off(K, K, N div K - 1),
sieve(N, find_next_in_sieve(K + 1)).
cross_off(_K, _Current, 0) ->
ok;
cross_off(K, Current, Left) ->
Next = Current + K,
put(Next, out),
cross_off(K, Next, Left - 1).
find_next_in_sieve(K) ->
case get(K) of
undefined ->
K;
_ ->
find_next_in_sieve(K+1)
end.
On Nov 16, 2010, at 2:55 AM, Richard O'Keefe wrote:
>
> On 16/11/2010, at 4:02 AM, Edmond Begumisa wrote:
>
>> Hello Richard,
>>
>> I have a question...
>>
>>> Erlang is a fine tool for jobs like this one.
>>
>> Interesting... I would have never thought this. I would have instinctively reached for a language with mutable memory, thinking that this would make the most sense for combinatorial* work (I don't know this for fact, and I could be very wrong, but that's what instinct would tell me.)
>
>> * I've been calling this permutation but I don't know if that's accurate.
>
> It isn't. "Permutation" has a very specific meaning, which does not apply here.
>
> Let me quibble slightly: *memoisation* can help a lot for some combinatorial
> algorithms, but mutable memory as such doesn't strike me as obviously useful.
> (Indeed, since mutable memory makes memoisation invalid, it can seriously get
> in your way.) Good support for large integers helps a lot.
>
> Different algorithms may well have different needs.
>>
>>> There is little point in optimising a bad algorithm.
>>
>> Well put. But say you have an 'ok' algorithm. Not the best, but not blatantly flawed either.
>
> I have a C program to compute various things from a data set which consists of
> a hundred million lines, each containing four non-negative integers. My
> program had to read it several times. (The first pass determines the sizes
> of major areas; the second pass determines the size of minor areas within
> major areas; the third pass loads the data.) It gets the effect of sorting
> without actually sorting (or more precisely, by count-sorting). The first
> version of the program took 68 seconds per pass on the fastest machine I
> had access to. Considering that wc takes 20 seconds to _not_ process the
> numbers in the file, that didn't seem too bad. But bypassing stdio and using
> my own code let me get the time down to 6 seconds per pass, which means that
> I can afford to run the program a lot more often.
>
> That was a case where there was a _good_ algorithm, but a horrible library.
> (Time is linear in the size of the input; results depend on all of the input;
> up to a constant factor the algorithm is as good as it gets.)
>
> But in the case we are discussing here, the initial algorithm was O(N**3)
> when an O(N**2) algorithm -- in fact, several of them, there's even a
> Wikipedia article on enumerating Pythagorean triples -- was not hard to find.
>
>>
>> So my question is: if version 1 isn't performing "reasonably" acceptably for Garcia's purpose, and version 1 isn't blatantly flawed.
>
> To me, version 1 *IS* blatantly flawed.
> In a pythagorean triple (a,b,c), a and b uniquely determine c,
> so it seems *obvious* that a quadratic algorithm should be sought.
> (It is not obvious that one *exists*, just that it should be sought.)
>
> Make no mistake: I have used brute force algorithms quite happily myself.
> But I never blame the language for the performance I get when I do so!
>
>
>> Isn't this a strong indicator that he's using the wrong tool?
>
> Ah, but what precisely is "the tool" in question?
> - functional languages as such?
> - Erlang?
> - list comprehensions as such?
> - Erlang's current implementation of list comprehensions?
>
> Here are some more times. Erlang R14A, MacBook Pro.
>
> 8> pyth:t(p3, 300).
> {p3,300,{length,146},{msec,10}}
> 9> pyth:t(p2, 300).
> {p2,300,{length,146},{msec,210}}
> 10> pyth:t(p1, 300).
> {p1,300,{length,146},{msec,970}}
> 11> pyth:t(p0, 300).
> {p0,300,{length,146},{msec,420}}
>
> What's p0?
> It's the utterly naive cubic loop nest, with the loops written
> as function calls working on integers, with the only list in
> existence being the one that's being built.
>
> The time for p0 was 420 milliseconds in Erlang.
> On the same machine, the same function, the time was
> 91 milliseconds in SML/NJ.
> SML/NJ MLton Erlang
> n=100 L= 34 s=0.004 m=0.004 e=0.020
> n=200 L= 86 s=0.028 m=0.027 e=0.130
> n=300 L=146 s=0.090 m=0.086 e=0.410
> n=400 L=210 s=0.213 m=0.202 e=0.980
> n=500 L=274 s=0.415 m=0.394 e=1.900
>
> We see that Erlang is about 5 times slower than SML.
> Here's the SML code.
>
> fun p0 n =
> let fun fa 0 l = l
> | fa a l = fb n a l
> and fb 0 a l = fa (a-1) l
> | fb b a l = fc n b a l
> and fc 0 b a l = fb (b-1) a l
> | fc c b a l = fc (c-1) b a (
> if a+b+c <= n andalso a*a+b*b = c*c
> then (a,b,c)::l else l)
> in fa n []
> end
>
> It's completely tail recursive, building the list from right to
> left. *THIS* is the version that is strictly comparable to any
> C or C# code one might plausibly write; it allocates no
> storage not part of the result, all looping is done with "while"
> loops that compare and increment integers. What's more, SML is
> strongly typed, and the Dialyzer should be able to handle this,
> so the compiler *knows* it is dealing with integers.
>
> I grant you that this code is not immediately clear.
> Clear code in SML might look like this:
>
> fun cat_tab l u f = (* concatenate + tabulate *)
> let fun loop i r = if i < l then r else loop (i-1) (f i @ r)
> in loop u []
> end (* _happens_ not to be in List *)
>
> fun p1 n =
> cat_tab 1 n (fn a =>
> cat_tab 1 n (fn b =>
> cat_tab 1 n (fn c =>
> if a+b+c <= n andalso a*a+b*b = c*c
> then [(a,b,c)] else [])))
>
> What happens to the times?
> (----------direct-----) (------cat_tab------) original!
> SML/NJ MLton Erlang SML/NJ Mlton Erlang Erlang
> n=100 L= 34 s=0.004 m=0.004 e=0.020 s=0.015 m=0.006 e=0.040 o=0.040
> n=200 L= 86 s=0.028 m=0.027 e=0.130 s=0.120 m=0.039 e=0.300 o=0.290
> n=300 L=146 s=0.090 m=0.086 e=0.410 s=0.403 m=0.128 e=0.950 o=0.980
> n=400 L=210 s=0.213 m=0.202 e=0.980 s=0.954 m=0.303 e=2.240 o=2.280
> n=500 L=274 s=0.415 m=0.394 e=1.900 s=1.857 m=0.591 e=4.300 o=4.400
>
> The MLton compiler is a whole-program compiler, and I've a
> strong suspicion that it is able to inline cat_tab, so it
> may be able to avoid building the answer twice. I'm pretty
> sure that SML/NJ isn't inlining cat_tab, and is building the
> answer twice. While the Erlang compiler _could_ be taught
> about cat_tab, it's not generally wonderful at inlining recursive
> procedures, which is why the rightmost column shows list
> comprehension not doing so well.
>
> There are two basic issues here:
> (1) The Erlang compiler doesn't really handle list comprehension as
> native loops; it compiles list comprehensions to recursive
> functions. lists:seq(1, N) is not special syntax -- unlike Haskell --
> and almost surely builds an actual list.
>
> This could be changed, and maybe some day it will change.
>
> (2) Erlang is compiled incrementally to support hot loading and
> (again in order to support hot loading) does not do much if any
> cross-module inlining.
> MLton is a whole-program optimising compiler, it can SML _are_
> allowed to do cross-module inlining by the nature of the language.
>
> This *can't* be changed without making Erlang less useful for its job.
>
> Ah, but there's one more wrinkle!
>
> SML/NJ Erlang SML/NJ Smalltalk
> n=100 L= 34 s=0.004 e=0.020 s= 0.250 p1=0.016
> n=200 L= 86 s=0.028 e=0.130 s= 1.904 p1=0.109
> n=300 L=146 s=0.090 e=0.410 s= 6.567 p1=0.369
> n=400 L=210 s=0.213 e=0.980 s=15.581 p1=0.873
> n=500 L=274 s=0.415 e=1.900 s=30.218 p1=1.705
>
> (3) Erlang integer arithmetic is *not* limited to some ridiculous
> size like 32 bits, it is _semantically_ unbounded integer
> arithmetic, with a space-efficient representation and fast
> calculation path for small integers. To get something
> comparable in SML, you have to use the type IntInf.int
> instead of Int.int. And when you do *that*, Erlang really
> really shines.
>
> The difference here is that if you use int in C or Java or C#
> or SML, then you'll find a positive integer n such that n+1 < 0.
> That kind of nonsense simply doesn't happen in Erlang.
>
> It comes with a price, but the price of *not* using a Lispy
> (or Smalltalky, or Erlangy) approach to integers is the price
> of getting wrong answers without knowing.
>
> The Smalltalk column was done using my Smalltalk-via-C compiler.
> It might be possible to go a factor of 2 faster using machine-
> specific assembly code, but what we seem to be looking at in
> the Erlang column really does seem to be no more than the
> price of arithmetic that gives correct results.
>
> And by the way, no, I am not advocating writing code like p0 above
> *UNTIL* it has been determined that the function is a performance
> problem and that the algorithm is good. Like I said, you should
> stick with the clean high level code until you understand the
> problem space better.
>
>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 12:36 pm |
|
|
|
Guest
|
On Sun, Nov 14, 2010 at 5:50 PM, Edmond Begumisa
<ebegumisa@hysteria-tech.com> wrote:
> Hynek,
>
> A few comments...
>
>> When Erlang implementation is faster than C implementation *is* badly
>> written even it can be for maintainability or haste reason. C++ is
>> another beast
>
> I disagree. Quick example...
>
> 1. Write a "well-written" web-server in Erlang, the "Erlang way"
> (lightweight-weight concurrency, message passing).
> 2. Write a "well-written" web-server in C/C++, the "C/C++ way"
> (mulit-threading, shared-memory).
>
> See which is faster. Or, you could save yourself some time and look at
> Apache + Yaws. I wouldn't describe either of these as badly written. But the
> performance difference is undeniable.
>
Why I should write C/C++ web-server in "C/C++ way" (mulit-threading,
shared-memory)? Is dumbness included in using C? I can write C
web-server using libevent for example. I can use kernel poll. I can do
all this cool stuff as Erlang does and I can overperform Erlang using
its own weapons. I can do it better and tune for this particular case
and will be better. I can but if I should or would is another
question. Keep in mind that Erlang VM itself is written in C.
>> You can also do tricks in C which you can't in Erlang.
>
> And you can do tricks in Erlang that you can't do in typical C (e.g easy
> parallelism with little change to code as evidenced on this thread.)
Everything what I can do in Erlang I can do in C, principally.
Opposite is not true. Keep in mind that Erlang VM itself *is* written
in C.
>
>> Can you write k/v store which
>> is able do 200 millions of look up operations per second on one 2.4GHz
>> i5 core?
>
> Something is getting lost here. I go back to the promises a language makes.
> In delivering on those promises, priorities have to be set and compromises
> made. The language user has to weight these.
>
> C/C++ gives us pointers (amongst other things). The language makes great
> sacrifices to give us pointers (like garbage collection and debugability) so
> we can create insanely efficient data structures. When the benefits of
> pointers far outweigh the trade-offs, the choice is clear.
>
> Erlang gives us high concurrency (amongst other things). The Erlang team
> made great sacrifices to give us insanely efficient and scalable
> concurrency. When the benefits of this far outweigh the trade-offs the
> choice is clear.
>
> I see few areas where these benefits/trade-offs overlap. The choice is
> usually very clear. In cases where overlapping does occur, there are various
> ways of using both.
>
> - Edmond -
>
>
I would not argue using only one language for everything. Did I? As I
have written slight down in mine reply, I'm surprised by Erlang HiPE
compiler work. It performs surprisingly well and I would not expect
many orders of magnitude improvement by rewriting to C. I would not
say it would be even ten times unless I would try, but I bet it would,
if I pay enough effort.
I would argue that Erlang with NIFs gives you ultimate tool. Erlang
and C are not enemies, they don't fight themselves, they makes prefect
pair for almost all purposes.
>
> On Sun, 14 Nov 2010 22:32:42 +1100, Hynek Vychodil <hynek@gooddata.com>
> wrote:
>
>> On Sun, Nov 14, 2010 at 11:55 AM, Tony Rogvall <tony@rogvall.se> wrote:
>>>
>>> On 14 nov 2010, at 10.17, Hynek Vychodil wrote:
>>>
>>>
>>>
>>> Good idea but it seems that native (HiPE) compiler does this
>>> optimization for you when you keep staying in one module. (I also
>>> keeps exporting only main function. It can possibly take effect here
>>> also.) In BEAM it gives you 50% performance gain. Anyway Erlang is not
>>> right tool for this job. You should use NIF if performance matter.
>>>
>>> pythag4(N) when is_integer(N) -> pythag4(N,1).
>>>
>>> I have implemented several small Erlang programs that beat "native" C
>>> code.
>>> Most of the time the C programs where badly/hastily written, but that is
>>> the
>>> point 
>>> You must select the algorithm and the implementation wisely, and of
>>> course
>>> use the golden rule "Make it work, then make it fast". I would add, if it
>>> is
>>> needed.
>>> This does not imply that you should write your program unnecessary slow
>>> to
>>> start with!
>>> Any how. A couple of months ago I implemented the AKS algorithm in
>>> Erlang.
>>> The AKS algorithm is a deterministic primality test algorithm
>>> (http://en.wikipedia.org/wiki/AKS_primality_test)
>>> I benchmarked this implementation with an implementation in C++.
>>> I was shocked: The Erlang version was about 5 times faster, NOT using
>>> obvious parallelism.
>>> In this case I would suspect that garbage collection is the major
>>> contributor! The implementation use
>>> a lot of temporary polynomials intermediate results. A copy collector
>>> does
>>> the trick.
>>> /Tony
>>>
>>>
>>>
>>> "Have run Make so many times I dunno what's installed anymore"
>>>
>>
>> When Erlang implementation is faster than C implementation *is* badly
>> written even it can be for maintainability or haste reason. C++ is
>> another beast. Pun intended. I have similar experience to you but when
>> I found that Erlang implementation is faster then I would look how is
>> it possible and you are right, usually it is memory issue. Anyway
>> every time you can do same tricks as Erlang does but you will end up
>> with "half and error prone implementation of Erlang". You can also do
>> tricks in C which you can't in Erlang. Can you write k/v store which
>> is able do 200 millions of look up operations per second on one 2.4GHz
>> i5 core? Anyway HiPE compiler does very good work here. If I count it
>> correctly pythag3 and pythag4 does about hundred millions checks per
>> seconds. Very good result I think.
>>
>>
>
>
> --
> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>
--
--Hynek (Pichi) Vychodil
Analyze your data in minutes. Share your insights instantly. Thrill
your boss. |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 1:55 pm |
|
|
|
Guest
|
Thanks very much for your insight. You lost me at some point but I'm
basically with you (I hope!)
This thread has been very, very useful and educational for me. I'm trying
some of the algo's presented in C for further study and comparision. It's
clearer now that my assumptions about what should and should not be
attempted in Erlang were completely wrong.
Although that does introduce some confusion since I have to now think
harder! The naive decisions were much easier to make
There is a particular side project I wanted to do where I instinctively
decided certain parts would be out-sourced to C/C++. As a result of this
thread, I'm not so sure anymore. Venturing outside the emulator might not
be worth it. I'll have to look much closer.
One more question though! From real experiences, are there specific
problems that you would just NEVER EVER attempt in Erlang? (I know of the
list on the FAQ but even that seems shaky now.)
- Edmond -
PS: When this thread first appeared, I chose to ignore it, thinking
"that's a flame thread with nothing worth reading." This mailing list is
unique in resisting flame temptation and sticking to the issues. Other
lists are not like that
On Tue, 16 Nov 2010 12:55:01 +1100, Richard O'Keefe <ok@cs.otago.ac.nz>
wrote:
>
> On 16/11/2010, at 4:02 AM, Edmond Begumisa wrote:
>
>> Hello Richard,
>>
>> I have a question...
>>
>>> Erlang is a fine tool for jobs like this one.
>>
>> Interesting... I would have never thought this. I would have
>> instinctively reached for a language with mutable memory, thinking that
>> this would make the most sense for combinatorial* work (I don't know
>> this for fact, and I could be very wrong, but that's what instinct
>> would tell me.)
>
>> * I've been calling this permutation but I don't know if that's
>> accurate.
>
> It isn't. "Permutation" has a very specific meaning, which does not
> apply here.
>
> Let me quibble slightly: *memoisation* can help a lot for some
> combinatorial
> algorithms, but mutable memory as such doesn't strike me as obviously
> useful.
> (Indeed, since mutable memory makes memoisation invalid, it can
> seriously get
> in your way.) Good support for large integers helps a lot.
>
> Different algorithms may well have different needs.
>>
>>> There is little point in optimising a bad algorithm.
>>
>> Well put. But say you have an 'ok' algorithm. Not the best, but not
>> blatantly flawed either.
>
> I have a C program to compute various things from a data set which
> consists of
> a hundred million lines, each containing four non-negative integers. My
> program had to read it several times. (The first pass determines the
> sizes
> of major areas; the second pass determines the size of minor areas within
> major areas; the third pass loads the data.) It gets the effect of
> sorting
> without actually sorting (or more precisely, by count-sorting). The
> first
> version of the program took 68 seconds per pass on the fastest machine I
> had access to. Considering that wc takes 20 seconds to _not_ process the
> numbers in the file, that didn't seem too bad. But bypassing stdio and
> using
> my own code let me get the time down to 6 seconds per pass, which means
> that
> I can afford to run the program a lot more often.
>
> That was a case where there was a _good_ algorithm, but a horrible
> library.
> (Time is linear in the size of the input; results depend on all of the
> input;
> up to a constant factor the algorithm is as good as it gets.)
>
> But in the case we are discussing here, the initial algorithm was O(N**3)
> when an O(N**2) algorithm -- in fact, several of them, there's even a
> Wikipedia article on enumerating Pythagorean triples -- was not hard to
> find.
>
>>
>> So my question is: if version 1 isn't performing "reasonably"
>> acceptably for Garcia's purpose, and version 1 isn't blatantly flawed.
>
> To me, version 1 *IS* blatantly flawed.
> In a pythagorean triple (a,b,c), a and b uniquely determine c,
> so it seems *obvious* that a quadratic algorithm should be sought.
> (It is not obvious that one *exists*, just that it should be sought.)
>
> Make no mistake: I have used brute force algorithms quite happily
> myself.
> But I never blame the language for the performance I get when I do so!
>
>
>> Isn't this a strong indicator that he's using the wrong tool?
>
> Ah, but what precisely is "the tool" in question?
> - functional languages as such?
> - Erlang?
> - list comprehensions as such?
> - Erlang's current implementation of list comprehensions?
>
> Here are some more times. Erlang R14A, MacBook Pro.
>
> 8> pyth:t(p3, 300).
> {p3,300,{length,146},{msec,10}}
> 9> pyth:t(p2, 300).
> {p2,300,{length,146},{msec,210}}
> 10> pyth:t(p1, 300).
> {p1,300,{length,146},{msec,970}}
> 11> pyth:t(p0, 300).
> {p0,300,{length,146},{msec,420}}
>
> What's p0?
> It's the utterly naive cubic loop nest, with the loops written
> as function calls working on integers, with the only list in
> existence being the one that's being built.
>
> The time for p0 was 420 milliseconds in Erlang.
> On the same machine, the same function, the time was
> 91 milliseconds in SML/NJ.
> SML/NJ MLton Erlang
> n=100 L= 34 s=0.004 m=0.004 e=0.020
> n=200 L= 86 s=0.028 m=0.027 e=0.130
> n=300 L=146 s=0.090 m=0.086 e=0.410
> n=400 L=210 s=0.213 m=0.202 e=0.980
> n=500 L=274 s=0.415 m=0.394 e=1.900
>
> We see that Erlang is about 5 times slower than SML.
> Here's the SML code.
>
> fun p0 n =
> let fun fa 0 l = l
> | fa a l = fb n a l
> and fb 0 a l = fa (a-1) l
> | fb b a l = fc n b a l
> and fc 0 b a l = fb (b-1) a l
> | fc c b a l = fc (c-1) b a (
> if a+b+c <= n andalso a*a+b*b = c*c
> then (a,b,c)::l else l)
> in fa n []
> end
>
> It's completely tail recursive, building the list from right to
> left. *THIS* is the version that is strictly comparable to any
> C or C# code one might plausibly write; it allocates no
> storage not part of the result, all looping is done with "while"
> loops that compare and increment integers. What's more, SML is
> strongly typed, and the Dialyzer should be able to handle this,
> so the compiler *knows* it is dealing with integers.
>
> I grant you that this code is not immediately clear.
> Clear code in SML might look like this:
>
> fun cat_tab l u f = (* concatenate + tabulate *)
> let fun loop i r = if i < l then r else loop (i-1) (f i @ r)
> in loop u []
> end (* _happens_ not to be in List *)
>
> fun p1 n =
> cat_tab 1 n (fn a =>
> cat_tab 1 n (fn b =>
> cat_tab 1 n (fn c =>
> if a+b+c <= n andalso a*a+b*b = c*c
> then [(a,b,c)] else [])))
>
> What happens to the times?
> (----------direct-----) (------cat_tab------) original!
> SML/NJ MLton Erlang SML/NJ Mlton Erlang Erlang
> n=100 L= 34 s=0.004 m=0.004 e=0.020 s=0.015 m=0.006 e=0.040 o=0.040
> n=200 L= 86 s=0.028 m=0.027 e=0.130 s=0.120 m=0.039 e=0.300 o=0.290
> n=300 L=146 s=0.090 m=0.086 e=0.410 s=0.403 m=0.128 e=0.950 o=0.980
> n=400 L=210 s=0.213 m=0.202 e=0.980 s=0.954 m=0.303 e=2.240 o=2.280
> n=500 L=274 s=0.415 m=0.394 e=1.900 s=1.857 m=0.591 e=4.300 o=4.400
>
> The MLton compiler is a whole-program compiler, and I've a
> strong suspicion that it is able to inline cat_tab, so it
> may be able to avoid building the answer twice. I'm pretty
> sure that SML/NJ isn't inlining cat_tab, and is building the
> answer twice. While the Erlang compiler _could_ be taught
> about cat_tab, it's not generally wonderful at inlining recursive
> procedures, which is why the rightmost column shows list
> comprehension not doing so well.
>
> There are two basic issues here:
> (1) The Erlang compiler doesn't really handle list comprehension as
> native loops; it compiles list comprehensions to recursive
> functions. lists:seq(1, N) is not special syntax -- unlike Haskell
> --
> and almost surely builds an actual list.
>
> This could be changed, and maybe some day it will change.
>
> (2) Erlang is compiled incrementally to support hot loading and
> (again in order to support hot loading) does not do much if any
> cross-module inlining.
> MLton is a whole-program optimising compiler, it can SML _are_
> allowed to do cross-module inlining by the nature of the language.
>
> This *can't* be changed without making Erlang less useful for its
> job.
>
> Ah, but there's one more wrinkle!
>
> SML/NJ Erlang SML/NJ Smalltalk
> n=100 L= 34 s=0.004 e=0.020 s= 0.250 p1=0.016
> n=200 L= 86 s=0.028 e=0.130 s= 1.904 p1=0.109
> n=300 L=146 s=0.090 e=0.410 s= 6.567 p1=0.369
> n=400 L=210 s=0.213 e=0.980 s=15.581 p1=0.873
> n=500 L=274 s=0.415 e=1.900 s=30.218 p1=1.705
>
> (3) Erlang integer arithmetic is *not* limited to some ridiculous
> size like 32 bits, it is _semantically_ unbounded integer
> arithmetic, with a space-efficient representation and fast
> calculation path for small integers. To get something
> comparable in SML, you have to use the type IntInf.int
> instead of Int.int. And when you do *that*, Erlang really
> really shines.
>
> The difference here is that if you use int in C or Java or C#
> or SML, then you'll find a positive integer n such that n+1 < 0.
> That kind of nonsense simply doesn't happen in Erlang.
>
> It comes with a price, but the price of *not* using a Lispy
> (or Smalltalky, or Erlangy) approach to integers is the price
> of getting wrong answers without knowing.
>
> The Smalltalk column was done using my Smalltalk-via-C compiler.
> It might be possible to go a factor of 2 faster using machine-
> specific assembly code, but what we seem to be looking at in
> the Erlang column really does seem to be no more than the
> price of arithmetic that gives correct results.
> And by the way, no, I am not advocating writing code like p0 above
> *UNTIL* it has been determined that the function is a performance
> problem and that the algorithm is good. Like I said, you should
> stick with the clean high level code until you understand the
> problem space better.
>
>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 1:58 pm |
|
|
|
Guest
|
On Tue, 16 Nov 2010 08:28:22 +1100, Jesper Louis Andersen
<jesper.louis.andersen@gmail.com> wrote:
> My experience is that C, C++ or Java tend to require much more work
> for these iterations
I'm beginning to notice this.
- Edmond -
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 2:22 pm |
|
|
|
Guest
|
Richard O'Keefe wrote:
> ... SNIP
>
> The time for p0 was 420 milliseconds in Erlang.
> On the same machine, the same function, the time was
> 91 milliseconds in SML/NJ.
> SML/NJ MLton Erlang
> n=100 L= 34 s=0.004 m=0.004 e=0.020
> n=200 L= 86 s=0.028 m=0.027 e=0.130
> n=300 L=146 s=0.090 m=0.086 e=0.410
> n=400 L=210 s=0.213 m=0.202 e=0.980
> n=500 L=274 s=0.415 m=0.394 e=1.900
>
> We see that Erlang is about 5 times slower than SML.
Is Erlang running native code here?
(Because both SML/NJ and MLton are.)
> Here's the SML code.
>
> ... What's more, SML is
> strongly typed, and the Dialyzer should be able to handle this,
> so the compiler *knows* it is dealing with integers.
Let's leave dialyzer out of this discussion -- it is a type analyzer
alright, but the types it infers are not necessarily usable for
optimization purposes (I can possibly elaborate in some other mail).
Can you post p0 to see whether the compiler can infer whether the
program deals with integers or not?
> There are two basic issues here:
> (1) The Erlang compiler doesn't really handle list comprehension as
> native loops; it compiles list comprehensions to recursive
> functions. lists:seq(1, N) is not special syntax -- unlike Haskell --
> and almost surely builds an actual list.
Yes. This is an issue. Actually, it's more general: in my experience
most Erlang programmers do not understand the difference between list
comprehensions and lists:foreach/2. Many of them find list comprehension
notation so nice that they often use it in places where building the
list is not only is not their intention but is completely unnecessary.
The compiler is not sufficiently clever to perform deforestation and
avoid construction of intermediate lists.
> This could be changed, and maybe some day it will change.
>
> (2) Erlang is compiled incrementally to support hot loading and
> (again in order to support hot loading) does not do much if any
> cross-module inlining.
> MLton is a whole-program optimising compiler, it can SML _are_
> allowed to do cross-module inlining by the nature of the language.
>
> This *can't* be changed without making Erlang less useful for its job.
>
> Ah, but there's one more wrinkle!
Yes, there is that too in Erlang
> SML/NJ Erlang SML/NJ Smalltalk
> n=100 L= 34 s=0.004 e=0.020 s= 0.250 p1=0.016
> n=200 L= 86 s=0.028 e=0.130 s= 1.904 p1=0.109
> n=300 L=146 s=0.090 e=0.410 s= 6.567 p1=0.369
> n=400 L=210 s=0.213 e=0.980 s=15.581 p1=0.873
> n=500 L=274 s=0.415 e=1.900 s=30.218 p1=1.705
>
> (3) Erlang integer arithmetic is *not* limited to some ridiculous
> size like 32 bits, it is _semantically_ unbounded integer
> arithmetic, with a space-efficient representation and fast
> calculation path for small integers. To get something
> comparable in SML, you have to use the type IntInf.int
> instead of Int.int. And when you do *that*, Erlang really
> really shines.
>
> The difference here is that if you use int in C or Java or C#
> or SML, then you'll find a positive integer n such that n+1 < 0.
> That kind of nonsense simply doesn't happen in Erlang.
>
> It comes with a price, but the price of *not* using a Lispy
> (or Smalltalky, or Erlangy) approach to integers is the price
> of getting wrong answers without knowing.
>
> The Smalltalk column was done using my Smalltalk-via-C compiler.
> It might be possible to go a factor of 2 faster using machine-
> specific assembly code, but what we seem to be looking at in
> the Erlang column really does seem to be no more than the
> price of arithmetic that gives correct results.
Thanks for a nice post!
Kostis
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| mattevans |
| Posted: Tue Nov 16, 2010 2:58 pm |
|
|
|
User
Joined: 07 Jun 2009
Posts: 47
|
Interesting thread...I think we can all take the following from this:
1) Write your solution in the "Erlang way", using Erlang's strengths such as spawning parallel processes, also HIPE and NIFS where appropriate.
2) Write your solution efficiently - true in all languages, but especially in Erlang where you could end up doing needless recursion.
3) Erlang isn't always the best language for all problems. Neither is C, C++, C#, Java or any other language. Choose the language, or a mix of languages, that are the best fit your problem.
What I would like to add is that we are trying to get Erlang accepted in a very C/C++ centric development environment. Although time and time again Erlang has shown itself a superior language and development environment for our domain, there is still a big problem in people accepting it. One of the main stumbling blocks is it is perceived to be "slow". People always say "it won't be faster than a C/C++ solution", or "a language written in a VM will always be slow [rolleyes]".
We can argue until we are blue in the face that it will be as good or better when you throw multi-cores in the mix. That there are other advantages including shorter development time, better debugging, redundancy, failure detection etc. But overcoming that initial "speed" bias is a tough sell. I'm not saying there is an answer to this, and I know that the development team is doing their best to make Erlang faster, but we mustn't forget that for many, the "perceived" slowness is one factor that prevents them developing in Erlang.
/Rant over
Matt
-----Original Message-----
From: erlang-questions@erlang.org [mailto:erlang-questions@erlang.org] On Behalf Of Hynek Vychodil
Sent: Tuesday, November 16, 2010 7:35 AM
To: Edmond Begumisa
Cc: Tony Rogvall; Willem de Jong; Gilberto Carmenate Garc |
|
|
| Back to top |
 
|
| Guest |
| Posted: Tue Nov 16, 2010 3:30 pm |
|
|
|
Guest
|
Hello Hynek,
> I can do
> all this cool stuff as Erlang does and I can overperform Erlang using
> its own weapons
I can't
> Everything what I can do in Erlang I can do in C, principally.
> Opposite is not true. Keep in mind that Erlang VM itself *is* written
> in C.
For me, the opposite is true.
That settles it then! You're a gazillion times a better C programmer than
I am And probably far better than any I've personally met!
Light-weight concurrency, SMP parallelism, soft real-time properties,
fault-tolerance, hot-code swapping, distribution, etc. My skill-set is
nowhere near wide enough to implement those things. Actually, from *my* C
code, those things are damn near impossible! It's quite magical the way
Erlang brings them to life. And I'd need those things to be able to say
anything I can do in Erlang I can do in C, principally or otherwise.
My C is just not that good. My knowledge is just not that wide. I rely too
heavily on the combined effort of others who are much smarter than me.
But I do play a mean blues guitar though! Take that, Erlang team
- Edmond -
On Tue, 16 Nov 2010 23:34:51 +1100, Hynek Vychodil <hynek@gooddata.com>
wrote:
> On Sun, Nov 14, 2010 at 5:50 PM, Edmond Begumisa
> <ebegumisa@hysteria-tech.com> wrote:
>> Hynek,
>>
>> A few comments...
>>
>>> When Erlang implementation is faster than C implementation *is* badly
>>> written even it can be for maintainability or haste reason. C++ is
>>> another beast
>>
>> I disagree. Quick example...
>>
>> 1. Write a "well-written" web-server in Erlang, the "Erlang way"
>> (lightweight-weight concurrency, message passing).
>> 2. Write a "well-written" web-server in C/C++, the "C/C++ way"
>> (mulit-threading, shared-memory).
>>
>> See which is faster. Or, you could save yourself some time and look at
>> Apache + Yaws. I wouldn't describe either of these as badly written.
>> But the
>> performance difference is undeniable.
>>
>
> Why I should write C/C++ web-server in "C/C++ way" (mulit-threading,
> shared-memory)? Is dumbness included in using C? I can write C
> web-server using libevent for example. I can use kernel poll. I can do
> all this cool stuff as Erlang does and I can overperform Erlang using
> its own weapons. I can do it better and tune for this particular case
> and will be better. I can but if I should or would is another
> question. Keep in mind that Erlang VM itself is written in C.
>
>>> You can also do tricks in C which you can't in Erlang.
>>
>> And you can do tricks in Erlang that you can't do in typical C (e.g easy
>> parallelism with little change to code as evidenced on this thread.)
>
> Everything what I can do in Erlang I can do in C, principally.
> Opposite is not true. Keep in mind that Erlang VM itself *is* written
> in C.
>>
>>> Can you write k/v store which
>>> is able do 200 millions of look up operations per second on one 2.4GHz
>>> i5 core?
>>
>> Something is getting lost here. I go back to the promises a language
>> makes.
>> In delivering on those promises, priorities have to be set and
>> compromises
>> made. The language user has to weight these.
>>
>> C/C++ gives us pointers (amongst other things). The language makes great
>> sacrifices to give us pointers (like garbage collection and
>> debugability) so
>> we can create insanely efficient data structures. When the benefits of
>> pointers far outweigh the trade-offs, the choice is clear.
>>
>> Erlang gives us high concurrency (amongst other things). The Erlang team
>> made great sacrifices to give us insanely efficient and scalable
>> concurrency. When the benefits of this far outweigh the trade-offs the
>> choice is clear.
>>
>> I see few areas where these benefits/trade-offs overlap. The choice is
>> usually very clear. In cases where overlapping does occur, there are
>> various
>> ways of using both.
>>
>> - Edmond -
>>
>>
> I would not argue using only one language for everything. Did I? As I
> have written slight down in mine reply, I'm surprised by Erlang HiPE
> compiler work. It performs surprisingly well and I would not expect
> many orders of magnitude improvement by rewriting to C. I would not
> say it would be even ten times unless I would try, but I bet it would,
> if I pay enough effort.
>
> I would argue that Erlang with NIFs gives you ultimate tool. Erlang
> and C are not enemies, they don't fight themselves, they makes prefect
> pair for almost all purposes.
>
>>
>> On Sun, 14 Nov 2010 22:32:42 +1100, Hynek Vychodil <hynek@gooddata.com>
>> wrote:
>>
>>> On Sun, Nov 14, 2010 at 11:55 AM, Tony Rogvall <tony@rogvall.se> wrote:
>>>>
>>>> On 14 nov 2010, at 10.17, Hynek Vychodil wrote:
>>>>
>>>>
>>>>
>>>> Good idea but it seems that native (HiPE) compiler does this
>>>> optimization for you when you keep staying in one module. (I also
>>>> keeps exporting only main function. It can possibly take effect here
>>>> also.) In BEAM it gives you 50% performance gain. Anyway Erlang is not
>>>> right tool for this job. You should use NIF if performance matter.
>>>>
>>>> pythag4(N) when is_integer(N) -> pythag4(N,1).
>>>>
>>>> I have implemented several small Erlang programs that beat "native" C
>>>> code.
>>>> Most of the time the C programs where badly/hastily written, but that
>>>> is
>>>> the
>>>> point
>>>> You must select the algorithm and the implementation wisely, and of
>>>> course
>>>> use the golden rule "Make it work, then make it fast". I would add,
>>>> if it
>>>> is
>>>> needed.
>>>> This does not imply that you should write your program unnecessary
>>>> slow
>>>> to
>>>> start with!
>>>> Any how. A couple of months ago I implemented the AKS algorithm in
>>>> Erlang.
>>>> The AKS algorithm is a deterministic primality test algorithm
>>>> (http://en.wikipedia.org/wiki/AKS_primality_test)
>>>> I benchmarked this implementation with an implementation in C++.
>>>> I was shocked: The Erlang version was about 5 times faster, NOT using
>>>> obvious parallelism.
>>>> In this case I would suspect that garbage collection is the major
>>>> contributor! The implementation use
>>>> a lot of temporary polynomials intermediate results. A copy collector
>>>> does
>>>> the trick.
>>>> /Tony
>>>>
>>>>
>>>>
>>>> "Have run Make so many times I dunno what's installed anymore"
>>>>
>>>
>>> When Erlang implementation is faster than C implementation *is* badly
>>> written even it can be for maintainability or haste reason. C++ is
>>> another beast. Pun intended. I have similar experience to you but when
>>> I found that Erlang implementation is faster then I would look how is
>>> it possible and you are right, usually it is memory issue. Anyway
>>> every time you can do same tricks as Erlang does but you will end up
>>> with "half and error prone implementation of Erlang". You can also do
>>> tricks in C which you can't in Erlang. Can you write k/v store which
>>> is able do 200 millions of look up operations per second on one 2.4GHz
>>> i5 core? Anyway HiPE compiler does very good work here. If I count it
>>> correctly pythag3 and pythag4 does about hundred millions checks per
>>> seconds. Very good result I think.
>>>
>>>
>>
>>
>> --
>> Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
>>
>
>
>
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 3:33 pm |
|
|
|
Guest
|
On 2010-11-16, at 09:51 AM, Evans, Matthew wrote:
> Interesting thread...I think we can all take the following from this:
>
> 1) Write your solution in the "Erlang way", using Erlang's strengths such as spawning parallel processes, also HIPE and NIFS where appropriate.
Spawning parallel processes is, in my opinion, a false ideal when it comes to algorithms like the ones presented here. In a micro-benchmark or in software that is oriented on doing only this task, multiprocessing might gain you points. In a loaded production system where all the processors are likely already busy, I wouldn't be surprised to see no big gain by using multiple processes, and if any, the gain would likely be very hard to predict.
I think it's better to aim for the scaling kind of concurrency, not the speed-up kind. If you use processes for truly concurrent tasks (rather than attempting speedups of a single call), You'll benefit from concurrency on a higher level on a server than from each function individually.
This has to be pretty application specific, though.
> 2) Write your solution efficiently - true in all languages, but especially in Erlang where you could end up doing needless recursion.
>
> 3) Erlang isn't always the best language for all problems. Neither is C, C++, C#, Java or any other language. Choose the language, or a mix of languages, that are the best fit your problem.
>
> What I would like to add is that we are trying to get Erlang accepted in a very C/C++ centric development environment. Although time and time again Erlang has shown itself a superior language and development environment for our domain, there is still a big problem in people accepting it. One of the main stumbling blocks is it is perceived to be "slow". People always say "it won't be faster than a C/C++ solution", or "a language written in a VM will always be slow [rolleyes]".
>
> We can argue until we are blue in the face that it will be as good or better when you throw multi-cores in the mix. That there are other advantages including shorter development time, better debugging, redundancy, failure detection etc. But overcoming that initial "speed" bias is a tough sell. I'm not saying there is an answer to this, and I know that the development team is doing their best to make Erlang faster, but we mustn't forget that for many, the "perceived" slowness is one factor that prevents them developing in Erlang.
>
I think the speed obsession has to be remnants of an education always based on time efficiency, especially for programmers coming from the era where processors were really slow. Whether this explanation is right or not, I don't think it is easily possible to convince someone that 1. his priorities are not the right one and 2. the language he uses isn't the best choice for the priorities he has.
We should consider that the burden of proof is ours, not theirs. Any unsubstantiated claim is usually met with skepticism and possibly violence. This is completely normal and natural, in my opinion. The best way to convince someone is with irrefutable proof, which might be why the most common suggested way to get a team to accept Erlang is to provide them with an implementation or success stories. And maybe Erlang is no better than what they're using right now, in which case it would be a waste of money to train everyone to work in a new environment with little benefit in the long run.
If people still are not accepting it even after valid proofs, then all bets are off: maybe they don't feel like learning new technology, maybe they don't believe that *they* can write efficient Erlang code (and then you have to prove them they can), maybe they think it all comes down to the same anyway (project success isn't language dependent? which could be true in many cases), etc. I'm not sure much can be done except leading by example, in any case.
> /Rant over
>
> Matt
>
--
Fred H |
|
|
| Back to top |
|
| anders_n |
| Posted: Tue Nov 16, 2010 3:36 pm |
|
|
|
User
Joined: 28 Feb 2005
Posts: 155
Location: Saltillo, Mexico
|
On Tue, Nov 16, 2010 at 8:20 AM, Kostis Sagonas <kostis@cs.ntua.gr> wrote:
> Richard O'Keefe wrote:
>>
>> ... SNIP
>>
>> The time for p0 was 420 milliseconds in Erlang.
>> On the same machine, the same function, the time was
>> 91 milliseconds in SML/NJ.
>> |
|
|
| Back to top |
|
| Guest |
| Posted: Tue Nov 16, 2010 3:42 pm |
|
|
|
Guest
|
On Wed, 17 Nov 2010 01:20:51 +1100, Kostis Sagonas <kostis@cs.ntua.gr>
wrote:
> There are two basic issues here:
> (1) The Erlang compiler doesn't really handle list comprehension as
> native loops; it compiles list comprehensions to recursive
> functions. lists:seq(1, N) is not special syntax -- unlike Haskell
> --
> and almost surely builds an actual list.
> Yes. This is an issue. Actually, it's more general: in my experience
> most Erlang programmers do not understand the difference between list
> comprehensions and lists:foreach/2. Many of them find list comprehension
> notation so nice that they often use it in places where building the
> list is not only is not their intention but is completely unnecessary.
> The compiler is not sufficiently clever to perform deforestation and
> avoid construction of intermediate lists.
>
First I'm hearing of this. It really ought to be in one of those green
boxes in the documentation.
- Edmond -
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Wed Nov 17, 2010 3:11 am |
|
|
|
Guest
|
On 17/11/2010, at 3:20 AM, Kostis Sagonas wrote:
> Richard O'Keefe wrote:
>> ... SNIP
>> The time for p0 was 420 milliseconds in Erlang.
>> On the same machine, the same function, the time was
>> 91 milliseconds in SML/NJ.
>> SML/NJ MLton Erlang
>> n=100 L= 34 s=0.004 m=0.004 e=0.020
>> n=200 L= 86 s=0.028 m=0.027 e=0.130
>> n=300 L=146 s=0.090 m=0.086 e=0.410
>> n=400 L=210 s=0.213 m=0.202 e=0.980
>> n=500 L=274 s=0.415 m=0.394 e=1.900
>> We see that Erlang is about 5 times slower than SML.
>
> Is Erlang running native code here?
> (Because both SML/NJ and MLton are.)
Yes.
>
>> Here's the SML code.
>> ... What's more, SML is
>> strongly typed, and the Dialyzer should be able to handle this,
>> so the compiler *knows* it is dealing with integers.
>
> Let's leave dialyzer out of this discussion -- it is a type analyzer alright, but the types it infers are not necessarily usable for optimization purposes (I can possibly elaborate in some other mail).
Let's not leave dialyzer out just yet, because there's an important distinction.
The dialyzer can discover that certain variables will have integer values,
but that's not at all the same thing as discovering that they will have
*small* integer values. But with arguments declared or inferred as 'int' in
SML, small hardware-sized integers just the same as C is what you get. The
best plausible case for Erlang here is code that still has to check
arithmetic operations to see whether bignum arithmetic is needed, at run time.
>
> Can you post p0 to see whether the compiler can infer whether the program deals with integers or not?
>
It isn't pretty!
p0(N) when is_integer(N), N >= 3 ->
p0_A(N, N, []).
p0_A(0, _, L) ->
L;
p0_A(A, N, L) ->
p0_B(N, A, N, L).
p0_B(0, A, N, L) ->
p0_A(A-1, N, L);
p0_B(B, A, N, L) ->
p0_C(N, A, B, N, L).
p0_C(0, A, B, N, L) ->
p0_B(B-1, A, N, L);
p0_C(C, A, B, N, L) when A+B+C =< N, A*A+B*B =:= C*C ->
p0_C(C-1, A, B, N, [{A,B,C}|L]);
p0_C(C, A, B, N, L) ->
p0_C(C-1, A, B, N, L).
It wouldn't take a *huge* amount of effort to make the existing compiler
recognise "X <- lists:seq(Y, Z)" as a special case and generate code not
entirely unlike this, except that I took the opportunity to count down
to 0.
Here's what p1 looks like in Smalltalk.
p1
|r|
r := OrderedCollection new.
1 to: self do: [:a |
1 to: self do: [:b |
1 to: self do: [:c |
(a+b+c <= self and: [a squared + b squared = c squared])
ifTrue: [r addLast: {a. b. c}]]]].
^r
By tradition, Smalltalk compilers *do* treat _ to: _ do: _ as a special
case, and mine is no exception, although the code is still sufficiently
generic to work with any kind of number or even Dates, not just integers.
I'll spare you all the generated C code, but here's the inner loop,
cleaned up a bit. I'm including it to make a point. The lines flagged
with ** are the lines that would are affected by (a) the lack of a
static type system and (b) the possibility of bignums.
The 'return is_not_boolean(...)' lines are there because you cannot
rely on comparison operators like < always returning a Boolean.
(The next big change to the compiler will be to deal with this another
way.) The "i<fn>(...)" macros would be single hardware instructions in
C, but the arguments might not be integers, and if integers, might be
big, and if small, might lead to a big result. (Oh, #squared should
have had a fast path too; I forgot.)
#define ib_p(x, y) \
(AREINTS(x, y) ? BOXS(UNINT(x) + UNINT(y)) : b_p(GLOBALS_OUT x, y))
On a SPARC, BOXS(UNINT(x)+UNINT(y)) could be a single tadd, but I'm still
trying to generate portable C, so there's a penalty there. The minimum
at assembly level would be something like
or x, y -> z
and z, 3 -> z
brnz z, L1
add x, y -> z
boc L2
L1: call out_of_line_add
L2:
which is still a lot more than a simple add instruction. The thing I
find astonishing is that it is fast enough to be *useful*.
a4 /*c*/ = ASINT(1); /* c := 1 */
for (; {
** b4 = ib_l(self, a4); /* self < c */
if (b4 != FALSE) break;
** t4 = ib_p(a2 /*a*/, a3 /*b*/); /* t4 := a + b */
** t3 = ib_p(t4, a4 /*c*/); /* t3 := (a+b) + c */
** t2 = ib_le(t3, self); /* t2 := t3 <= self */
if (t2 == FALSE) {
t1 = FALSE;
} else
if (t2 == TRUE) {
** t5 = u_squared(a2 /*a*/);
** t6 = u_squared(a3 /*b*/);
** t3 = ib_p(t5, t6); /* t3 := a**2 + b**2 */
** t4 = u_squared(a4 /*c*/);
** t1 = ib_e(t3, t4); /* t1 := (a**2+b**2)=c**2 */
} else {
** return is_not_boolean(t2);
}
if (t1 == TRUE) {
t3 = OBJECT_NEW(GCLASS(n_Array), ASINT(3));
ELEM(t3, 1) = a2 /*a*/;
ELEM(t3, 2) = a3 /*b*/;
ELEM(t3, 3) = a4 /*c*/;
(void)k_addLast(l1 /*r*/, t3);
} else
** if (t1 != FALSE) {
** return is_not_boolean(t1);
}
** a4 = ib_p(a4, ASINT(1)); /* c := c + 1 */
}
** if (b4 != TRUE) return is_not_boolean(b4);
H
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Wed Nov 17, 2010 5:14 am |
|
|
|
Guest
|
On 17/11/2010, at 3:51 AM, Evans, Matthew wrote:
> Interesting thread...I think we can all take the following from this:
>
> 1) Write your solution in the "Erlang way", using Erlang's strengths such as spawning parallel processes, also HIPE and NIFS where appropriate.
I think this is important for any language: you really do need to learn how
to work *with* the language.
We are *all* of us having to learn new ways of programming.
I've got quite good at seeing how to make single-core programs go faster.
Seeing the parallelism in a problem is still a challenge for me.
Let's not forget that one of Erlang's strengths is distribution.
Moving a computation where the data is has been a good idea (sometimes!)
for a long time. Moving a computation is NOT necessarily the same thing
as moving executable code; it could be some sort of data structure
requesting a particular activity, which might or might not result in new
code being generated, compiled, and loaded on a remote server.
> 2) Write your solution efficiently - true in all languages, but especially in Erlang where you could end up doing needless recursion.
"needless recursion"? There is nothing special about needless *recursion* to
warrant distinguishing it from any other kind of needless work.
I'm not sure that I go along with this. When I presented the A and B determine C
version of the Pythagorean triple finder, I *knew* that there were more efficient
ways to do it. The code was efficient *enough* to make my point.
So let's say "Don't make your solution blatantly inefficient".
People often focus on computational steps when thinking about efficiency.
Memory is also something to think about.
Let's take that 100 million element data set I mentioned earlier in this
thread. It's basically just a rather large sparse matrix with
500,000 rows
20,000 columns
100,000,000 nonzero entries (they fit in a byte).
Store it as a full array, and you need 10 GB of memory.
The machine I'm typing on today has 3 GB. Oops.
One way to represent a sparse matrix is as an array of
pointers to pairs of (column number, value) arrays,
which works out at about 303 MB of memory.
The method I'm using takes about 210 MB of memory.
It's not just the quantitive difference, taking >47 times less
memory, it's the qualitative difference between being able to
do the job in the memory I have or not.
By the way, the same data structure could be adapted to Erlang,
taking about 434 MB. I haven't tried it, and it would take a fair
bit longer to load, but it should work. If done, this would
provide an example of
Erlang + efficient data structure : slowish but workable
C + inefficient data structure : unusable
In much the same way, I once had a statistical calculation where
I wanted to use a published Fortran algorithm. I had trouble
getting the published code to work, so I rewrote it in Prolog.
When I had that going, I used it to help debug the Fortran
version. And at the end of the day, the Prolog version was
*faster*, because it used a better data structure. And the
Prolog code wasn't even running as native instructions!
(To this day, rewriting something tricky in another language is
a debugging strategy I find helpful.)
> 3) Erlang isn't always the best language for all problems. Neither is C, C++, C#, Java or any other language. Choose the language, or a mix of languages, that are the best fit your problem.
It's also important to be clear about what's *problematic* about the problem.
*Development* time and *execution* time are different.
If you are trying to develop embedded software for something where the (moral)
cost of failure is high, like a medical device, the SPARK subset of Ada,
with an actual attempt to verify as much as you can of the software, would be
a good choice. If you are trying to enumerate Pythagorean triples for fun,
that would be a bad choice. In some projects, what you need to do is to
move quickly from prototype to prototype as you learn more about the problem,
the domain, the risks, the clients, &c.
> What I would like to add is that we are trying to get Erlang accepted in a very C/C++ centric development environment. Although time and time again Erlang has shown itself a superior language and development environment for our domain, there is still a big problem in people accepting it. One of the main stumbling blocks is it is perceived to be "slow". People always say "it won't be faster than a C/C++ solution", or "a language written in a VM will always be slow [rolleyes]".
Well, Erlang *is* slow at arithmetic. The question is whether that really matters.
Let's put this in perspective.
About 12 years ago I was an expert witness in a court case.
Amongst other things, the contractor claimed that the reason the
program was too slow was that the client's PC was too feeble.
If memory serves me, the PC was one that the contractor had
recommended when the project began. I pointed out that the
whole of the banking in this country had been done 20 years
earlier on a mainframe with far less memory, far slower, and
with somewhat slower discs, so the machine really ought to be
able to handle one shop!
Today's machines are awesome. My laptop can sort 250 million
64-bit floats in under a minute (albeit not using qsort()).
I was about to try a bigger benchmark when I realised that was 2GB.
I used to be able to get times like that with a few thousand numbers.
We now see people _happily_ developing entire applications in
(sorry; I don't like to be offensive, but it's true) PHP.
We see *major* natural language processing frameworks like GATE
written in Java, and project management tools like Colibri.
People will tell you that Java can be, or is about to be, or even
is, as fast as C. Every benchmark I've ever tried, some of them
quite recently, says NO. But it's fast _enough_.
>
> We can argue until we are blue in the face that it will be as good or better when you throw multi-cores in the mix.
I'm sorry, but I don't believe that Erlang will *ever* run faster than
C. What we need to remember is that *most* large projects fail.
The question we should be looking at is not
"will a [multicore] Erlang program be faster"
"will a [multicore] C program be faster"
but
"will a [multicore] Erlang program be DELIVERABLE"
"will a [multicore] C program be DELIVERABLE"
An Erlang program that *exists* is infinitely faster than a C program
that had to be abandoned. A slow Erlang program that customers can
actually *use* is going to earn you more money (that you can spend on
rewriting parts of it in C if you really want to) than a C program
that isn't ready for release outside the Dilbert zone.
You know, a lot of people think that their program is efficient
*because it is written in C*. But there is a lot of inefficient
code written in C. I'm sure we've all seen things like
for (i = 0; i < strlen(s); i++)
if (s[i] == ' ') s[i] = '_';
It might well be that the best way to overcome the "speed" bias
would be to look at some recently written code and show how fast
it *isn't*.
A colleague here once challenged me to improve a back-propagation
program he had written in C. Thinking like an APL programmer I
speeded it up by a factor of 2.5. That code was actually a
half-way house to using the BLAS, but since I'd made my point,
I stopped there.
> for many, the "perceived" slowness is one factor that prevents them developing in Erlang.
Just like the way the "perceived" slowness of garbage collection
stopped people using Lisp, until along came Java, and suddenly
GC was respectable. Yet despite that, and despite experiments
finding faster development in Lisp *and* better performance in the
result, people still stayed away from Lisp.
Wearing my complete cynic's hat here, I suspect that if someone developed
an alternative syntax for Erlang that *looked* like C, it might be more
attractive to the hard-of-thinking.
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
| Guest |
| Posted: Wed Nov 17, 2010 5:25 am |
|
|
|
Guest
|
On 17/11/2010, at 4:23 AM, Anders Nygren wrote:
> On Tue, Nov 16, 2010 at 8:20 AM, Kostis Sagonas <kostis@cs.ntua.gr> wrote:
>> Richard O'Keefe wrote:
>>>
>>> ... SNIP
>>>
>>> The time for p0 was 420 milliseconds in Erlang.
>>> On the same machine, the same function, the time was
>>> 91 milliseconds in SML/NJ.
>>> SML/NJ MLton Erlang
>>> n=100 L= 34 s=0.004 m=0.004 e=0.020
>>> n=200 L= 86 s=0.028 m=0.027 e=0.130
>>> n=300 L=146 s=0.090 m=0.086 e=0.410
>>> n=400 L=210 s=0.213 m=0.202 e=0.980
>>> n=500 L=274 s=0.415 m=0.394 e=1.900
>>>
>>> We see that Erlang is about 5 times slower than SML.
>>
>> Is Erlang running native code here?
>> (Because both SML/NJ and MLton are.)
>>
>>> Here's the SML code.
>>>
>>> ... What's more, SML is
>>> strongly typed, and the Dialyzer should be able to handle this,
>>> so the compiler *knows* it is dealing with integers.
>>
>> Let's leave dialyzer out of this discussion -- it is a type analyzer
>> alright, but the types it infers are not necessarily usable for optimization
>> purposes (I can possibly elaborate in some other mail).
>>
>> Can you post p0 to see whether the compiler can infer whether the program
>> deals with integers or not?
>>
>>
>>> There are two basic issues here:
>>> (1) The Erlang compiler doesn't really handle list comprehension as
>>> native loops; it compiles list comprehensions to recursive
>>> functions. lists:seq(1, N) is not special syntax -- unlike Haskell --
>>> and almost surely builds an actual list.
>>
>> Yes. This is an issue. Actually, it's more general: in my experience most
>> Erlang programmers do not understand the difference between list
>> comprehensions and lists:foreach/2. Many of them find list comprehension
>> notation so nice that they often use it in places where building the list is
>> not only is not their intention but is completely unnecessary.
>> The compiler is not sufficiently clever to perform deforestation and avoid
>> construction of intermediate lists.
>
>
> Maybe You are talking about some special case here that I missed but the
> "Efficiency Guide" ch 5.2, in the documentation says
> "In R12B, if the result of the list comprehension will obviously not
> be used, a list will not be constructed."
We are talking about completely different lists.
What I'm talking about is that
R = [f(X) || X <- lists:seq(1, N)]
will construct lists:seq(1, N), even though it doesn't need to.
You are talking about the fact that
_ = [g(Y) || Y <- L]
won't construct a list of g results. But that is not at all relevant
to the problem at hand, where the list of triples obviously *WILL* be
used, so the comprehension *MUST* construct it. That's fine, that's
what we want.
Compare this with Haskell, where for
[(a,b,c) | a <- [1..n], b <- [1..n], c <- [1..n],
a+b+c <= n, a^2 + b^2 == c^2]
some compilers *won't* construct the lists [1..n].
________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:erlang-questions-unsubscribe@erlang.org
Post received from mailinglist |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
