real fp vs. scheme/lisp implicit ordering
raould
i thought one thing people 'sell' about fp is that the compiler can
reorder things. but it appears to me that there's an awful lot of
implicit ordering in things like lisp and scheme (which aren't pure fp
of course, but still), to the extent that i find myself confused what
*isn't* implicitly ordered :-}
any opinions / thoughts on how this hurts fp or the 'intuitiveness' of
the languages?
(i don't like it, personally. i'd rather require being more often.)
thanks.
Vend
> hi,
>
> i thought one thing people 'sell' about fp is that the compiler can
> reorder things.
Compiler can sometimes reorder operations in any language.
Using the functional programming paradigm this might be easier.
> but it appears to me that there's an awful lot of
> implicit ordering in things like lisp and scheme (which aren't pure fp
> of course, but still), to the extent that i find myself confused what
> *isn't* implicitly ordered :-}
Pure functional languages also have constraints on execution order, to
make sure that termination is not implementation-dependent and I/O
operations are properly sequenced.
> any opinions / thoughts on how this hurts fp or the 'intuitiveness' of
> the languages?
Specified ordering can hurt performance but not 'intuitiveness'.
Jon Harrop
>> any opinions / thoughts on how this hurts fp or the 'intuitiveness' of
>> the languages?
>
> Specified ordering can hurt performance but not 'intuitiveness'.
Unspecified order can allow the compiler to evaluate subexpressions in any
order which, in turn, can give rise to unintuitive time and space usage.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
raould
>
> Unspecified order can allow the compiler to evaluate subexpressions in any
> order which, in turn, can give rise to unintuitive time and space usage.
seems like we're agreed that specified ordering is better for
intuitiveness? not sure how that should end up in the code. maybe
instead of a begin keyword there should be a keyword which says "the
stuff here is allowed to be reordered"?
Jon Harrop
Possibly but Haskell permits all of these optimizations and, yet, its
performance sucks beyond belief. Look at the idiomatic Haskell quicksort,
for example:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
You cannot get much simpler, yet the state-of-the-art Haskell compiler still
runs it about 6,000x slower than most other languages precisely because
these optimizations all failed to pay off.
I think it is fair to say that conveying potential for reordering the
evaluation of arbitrary expressions to the compiler is a waste of time in
general. Reordering is very important at the instruction level but that is
already done and the consequence is memory barriers in lock-free
multithreaded code, which is a small price to pay for decent performance.
Nobody
> You cannot get much simpler, yet the state-of-the-art Haskell compiler still
> runs it about 6,000x slower than most other languages precisely because
> these optimizations all failed to pay off.
Or, more accurately, because these optimisations aren't actually implemented.
Erik de Castro Lopo
> qsort [] = []
> qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
>
> You cannot get much simpler, yet the state-of-the-art Haskell compiler still
> runs it about 6,000x slower than most other languages precisely because
> these optimizations all failed to pay off.
You certainly seem to be a big fan of lies, damn lies and statistics don't
you Jon?
The above qsort implementation is elegant but far from optimal. The
important thing however is that compiling that with GHC does not produce
a program significantly slower than than other compilers compiling the
same algorithm.
Here is a full (corrected) haskell test program:
import System.Random (randomRIO)
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (> x) xs)
randIntList :: Int -> Int -> IO [Int]
randIntList len maxint = do
list <- mapM (\_ -> randomRIO (0, maxint)) [1 .. len]
return list
main :: IO ()
main = do
list <- randIntList 1000000 1000000
let sorted = qsort list
-- For verification:
-- putStrLn $ show sorted
putStrLn $ show $ head sorted
and here is the Ocaml version of the *same* *algorithm* :
(* Need this to avoid stack overflows in the stdlib version. *)
open ExtList
let rec qsort lst =
match lst with
| [] -> []
| x :: xs ->
qsort (List.filter (fun y -> y < x) xs)
@ [x] @ qsort (List.filter (fun y -> y > x) xs)
let randIntList len maxint =
let rec builder accum count =
if count >= len then accum
else builder (Random.int maxint :: accum) (count + 1)
in
builder [] 0
let () =
let lst = randIntList 1000000 1000000 in
let sorted = qsort lst in
(* For verification only.
print_endline (String.concat "," (List.map string_of_int sorted)) ;
*)
print_int (List.hd sorted) ;
print_newline ()
Guess what, compiled as:
ocamlopt -I +extlib extLib.cmxa mlsort.ml -o mlsort
ghc -O2 --make hssort.hs -o hssort
they both take about 10 seconds to execute. Sometimes the Ocaml version wins
and sometimes the Haskell version wins.
Let me re-iterate, this algorithm is non-optimal in any language and
comparing Haskell compiling this algorithm against optimal algorithms
in other langauges shows you as the clown you are.
Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/
Vend
That algorithm runs slow not because the compiler doesn't optimize
execution ordering, but because it uses immutable linked lists and
fails to optimize 'filter', I think.
Vend
In order to optimize that program the compiler would have to figure
out these properties:
- The two 'filter' operations generate a partition.
This allows them to be executed in a single pass.
- 'qsort' returns a list with the same length (and type) of the input
list, with reference count equal to 1, and it doesn't increase the
reference count of the input list.
This allows the procedure to be implemented using mutable arrays
instead of immutable liked lists.
Vend
>
> Let me re-iterate, this algorithm is non-optimal in any language and
> comparing Haskell compiling this algorithm against optimal algorithms
> in other langauges shows you as the clown you are.
But in other languages you can write the efficient version of that
algorithm which uses mutable arrays, by taking advantage of the
implicit specified execution order.
In Haskell you can write mutable code by explicitely specifying the
execution order using special state monads. You get (at most) the same
thing, with an inconvenient syntax.
Erik de Castro Lopo
> On 3 Dic, 23:10, Erik de Castro Lopo <er...@mega-nerd.com> wrote:
> >
> > Let me re-iterate, this algorithm is non-optimal in any language and
> > comparing Haskell compiling this algorithm against optimal algorithms
> > in other langauges shows you as the clown you are.
>
> But in other languages you can write the efficient version of that
> algorithm which uses mutable arrays, by taking advantage of the
> implicit specified execution order.
Haskell also has mutable arrays and converting a list to a mutable
array, doing a mergesort and them converting back to a list is
supposedly faster than the standard sort implementation in Data.List:
http://lindstroem.wordpress.com/2009/02/19/using-mutable-arrays-for-faster-sorting/
That still doesn't change the fact that the qsort implementation
Jon Harrop showed is highly non-optimal regardless of language and
that comparing that non-optimal implementation to optimal algorithms
in other languages is clownish.
Erik de Castro Lopo
> In order to optimize that program the compiler would have to figure
> out these properties:
> - The two 'filter' operations generate a partition.
> This allows them to be executed in a single pass.
Ocaml's library has a List.partition function which allows you to
replace two filter operations with one.
> - 'qsort' returns a list with the same length (and type) of the input
> list, with reference count equal to 1, and it doesn't increase the
> reference count of the input list.
> This allows the procedure to be implemented using mutable arrays
> instead of immutable liked lists.
The only language I know of which is likely to ba able to detect the
possibility of that optimisation and apply it is Disciple:
http://www.haskell.org/haskellwiki/DDC
the compiler for which is still in a pre-alpha state.
Erikhttp://www.haskell.org/haskellwiki/DDC
Matti Nykanen
> Ocaml's library has a List.partition function which allows you to
> replace two filter operations with one.
So does Haskell's.
Putting it into Jon's code gave me a 10% speedup in GHCi. I got
another 10% by replacing the (++) operations with an accumulator
parameter.
Manlio Perillo
> [...]
> Here is a full (corrected) haskell test program:
>
> import System.Random (randomRIO)
>
To make better comparison, you should use the same input sequence for
both Haskell and Ocaml.
> [...]
> putStrLn $ show $ head sorted
Why not
print $ head sorted
?
> [...]
> and here is the Ocaml version of the *same* *algorithm* :
>
> (* Need this to avoid stack overflows in the stdlib version. *) open
> ExtList
>
Stack overflow does not happen on my system.
> [...]
> Guess what, compiled as:
>
> ocamlopt -I +extlib extLib.cmxa mlsort.ml -o mlsort
>
> ghc -O2 --make hssort.hs -o hssort
>
There is no need for the -o option.
> they both take about 10 seconds to execute. Sometimes the Ocaml version
> wins and sometimes the Haskell version wins.
>
I noted that the OCaml version take less memory.
But to make more precise comparison, the same input sequence should be
used.
> [...]
Regards Manlio
Erik de Castro Lopo
> Il Fri, 04 Dec 2009 09:10:45 +1100, Erik de Castro Lopo ha scritto:
>
> To make better comparison, you should use the same input sequence for
> both Haskell and Ocaml.
> Why not
> print $ head sorted
> Stack overflow does not happen on my system.
> There is no need for the -o option.
> I noted that the OCaml version take less memory.
All of those are valid but completely irrelevant observations.
Jon Harrop's claim was about the Haskell qsort he posted:
> You cannot get much simpler, yet the state-of-the-art Haskell compiler still
> runs it about 6,000x slower than most other languages
And I showed that the Ocaml version of the same algorithn was almost exactly
the same speed as the Haskell version.
> But to make more precise comparison, the same input sequence should be
> used.
That could not possibly account for Jon Harrop's claim of 6000x slower.
Jon Harrop
> Let me re-iterate, this algorithm is non-optimal in any language
I agree. Languages that use purity to relax evaluation order to permit
optimizations fail to offer real benefits in practice. They just make time
and space unpredictable.
> and comparing Haskell compiling this algorithm against optimal algorithms
> in other langauges shows you as the clown you are.
I agree that this comparison is ridiculous because the Haskell is not
comparable to decent code (indeed, Haskell cannot even express a decent
generic solution) but it was neither my comparison nor my claim: it was
taken directly from the introduction on haskell.org:
http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
As you say, their claim:
"To get an idea of what a functional program is like, and the
expressiveness of functional languages, look at the following quicksort
programs. They both sort a sequence of numbers into ascending order using a
standard method called "quicksort". The first program is written in Haskell
and the second in C."
is complete nonsense because the Haskell actually compiles to something
uselessly worse than quicksort.
Manlio Perillo
> [...]
> I agree that this comparison is ridiculous because the Haskell is not
> comparable to decent code (indeed, Haskell cannot even express a decent
> generic solution) but it was neither my comparison nor my claim: it was
> taken directly from the introduction on haskell.org:
>
> http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
>
> As you say, their claim:
>
> "To get an idea of what a functional program is like, and the
> expressiveness of functional languages, look at the following quicksort
> programs. They both sort a sequence of numbers into ascending order
> using a standard method called "quicksort". The first program is written
> in Haskell and the second in C."
>
> is complete nonsense because the Haskell actually compiles to something
> uselessly worse than quicksort.
Well, then it's the same for OCaml since on the Wikipedia page there is a
quicksort implementation that is as slow as the Haskell one.
Regards Manlio
Jon Harrop
Sure. The point is that you can write a usable array-based implementation in
OCaml but not in Haskell. This generic array-based OCaml is 10x faster than
Erik's list-based Haskell:
let swap a i j =
let t = a.(i) in
a.(i) <- a.(j);
a.(j) <- t
let rec qsort a l u =
if l < u then
let m = ref l in
for i=l+1 to u do
if a.(i) < a.(l) then begin
m := !m + 1;
swap a !m i
end
done;
swap a l !m;
qsort a l (!m - 1);
qsort a (!m + 1) u
This parallel generic F# is 330x faster than Erik's Haskell:
open System.Threading
let inline sort cmp (a: _ array) =
let inline swap i j =
let t = a.[i]
a.[i] <- a.[j]
a.[j] <- t
let rec qsort l u =
if l < u then
swap l ((l + u) / 2)
let mutable m = l
for i=l+1 to u do
if cmp a.[i] a.[l] < 0 then
m <- m + 1
swap m i
swap l m
if u-l > 1000 then
let m = m
let f = Tasks.Future.Create(fun () -> qsort l (m-1))
qsort (m+1) u
f.Value
else
qsort l (m-1)
qsort (m+1) u
qsort 0 (a.Length-1)
In fact, this F# can sort 100M elements faster than Haskell sorts 1M
elements!
These are the practically valuable optimizations. F# facilitates them.
Haskell makes them difficult or impossible.
Manlio Perillo
> [...]
>>> "To get an idea of what a functional program is like, and the
>>> expressiveness of functional languages, look at the following
>>> quicksort programs. They both sort a sequence of numbers into
>>> ascending order using a standard method called "quicksort". The first
>>> program is written in Haskell and the second in C."
>>>
>>> is complete nonsense because the Haskell actually compiles to
>>> something uselessly worse than quicksort.
>>
>> Well, then it's the same for OCaml since on the Wikipedia page there is
>> a quicksort implementation that is as slow as the Haskell one.
>
> Sure. The point is that you can write a usable array-based
> implementation in OCaml but not in Haskell. This generic array-based
> OCaml is 10x faster than Erik's list-based Haskell:
Ah, ok.
But then don't say that Haskell implementation is bad!
It is a problem with naive pure functional implementations, including
OCaml.
>
> let swap a i j =
> let t = a.(i) in
> a.(i) <- a.(j);
> a.(j) <- t
>
> let rec qsort a l u =
> if l < u then
> let m = ref l in
> for i=l+1 to u do
> if a.(i) < a.(l) then begin
> m := !m + 1;
> swap a !m i
> end
> done;
> swap a l !m;
> qsort a l (!m - 1);
> qsort a (!m + 1) u
>
I'm rather sure that you can write a similar function in Haskell, using
Haskell mutable arrays.
Why do you say that such an implementation is not usable in Haskell?
And, again, why do you write:
"This generic array-based OCaml is 10x faster than Erik's list-based
Haskell"
instead of
"This generic array-based sort is 10x faster than naive list based sort,
in Ocaml".
?
The problem with Haskell is that mutable arrays are not handy to use, and
here I think the same thing.
I like OCaml since it is pragmatic, however to be pragmatic I think there
are a lot of problems with its grammar; there are many special cases; in
fact I don't really like OCaml syntax and instead I find Haskell syntax
very good and regular.
> [...]
>
> These are the practically valuable optimizations. F# facilitates them.
> Haskell makes them difficult or impossible.
In Haskell things are just a bit problematic when dealing with mutable
arrays.
I hope that this will be fixed in a future revision of the standard; but
it is only a matter of syntax, IMHO.
Regards Manlio
Erik de Castro Lopo
Here we have a prefect example of Jon Harrop in a ction. Earlier in this
thread he posted the elegant but non-optimal Haskell qsort implementation
and stated:
> You cannot get much simpler, yet the state-of-the-art Haskell compiler still
> runs it about 6,000x slower than most other languages precisely
> Jon Harrop wrote:
Now he does this amazing back pedal:
> Sure. The point is that you can write a usable array-based implementation in
> OCaml but not in Haskell. This generic array-based OCaml is 10x faster than
> Erik's list-based Haskell:
and says that Ocaml sorting arrays is faster than Haskell sorting lists. Well
this would not surpise anyone who has studied computer science. Lists are
simply not the right data structure for efficient sorting.
He then goes on to make another outrageous claim:
> This parallel generic F# is 330x faster than Erik's Haskell:
> In fact, this F# can sort 100M elements faster than Haskell sorts 1M
> elements!
There is no mention here of how many cores are being used to sort this
nor is there acknowledgement that its sorting arrays and not lists.
I really, really doubt running "parallel generic F#" to sort *arrays*
on a single core is 330x faster than the Haskell qsort of a list.
If you throw more cores at it this may be true, but that's not really
comparing like with like is it? And where is the evidence to support
the 6000x slower claim?
Jon Harrop
> It is a problem with naive pure functional implementations, including
> OCaml.
No, it is a problem with Haskell.
>> let swap a i j =
>> let t = a.(i) in
>> a.(i) <- a.(j);
>> a.(j) <- t
>>
>> let rec qsort a l u =
>> if l < u then
>> let m = ref l in
>> for i=l+1 to u do
>> if a.(i) < a.(l) then begin
>> m := !m + 1;
>> swap a !m i
>> end
>> done;
>> swap a l !m;
>> qsort a l (!m - 1);
>> qsort a (!m + 1) u
>>
>
> I'm rather sure that you can write a similar function in Haskell, using
> Haskell mutable arrays.
No, you cannot. That's the whole point. Every write to a generic array in
Haskell is potentially O(n) in general instead of O(1). So you get
asymptotically much worse performance that is unusable in practice. That is
why real Haskell code resorts to unsuitable data structures like lists to
avoid this problem whereas idiomatic OCaml/F# code does not.
> In Haskell things are just a bit problematic when dealing with mutable
> arrays.
So problematic that Haskell still doesn't provide a usable hash table
implementation.
> I hope that this will be fixed in a future revision of the standard; but
> it is only a matter of syntax, IMHO.
This is not a syntactic issue. Try to write a decent generic quicksort in
Haskell: it is an unsolved problem.
Jon Harrop
>
> import System.Random (randomRIO)
>
> qsort :: Ord a => [a] -> [a]
> qsort [] = []
> qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (> x)
> xs)
BTW, the original program I posted was correct but your "corrected" program
is wrong because it silently drops duplicates.
Jon Harrop
> thread he posted the elegant but non-optimal Haskell qsort implementation
> and stated:
>
>> You cannot get much simpler, yet the state-of-the-art Haskell compiler
>> still runs it about 6,000x slower than most other languages precisely
>> Jon Harrop wrote:
>
> Now he does this amazing back pedal:
>
>> Sure. The point is that you can write a usable array-based implementation
>> in OCaml but not in Haskell. This generic array-based OCaml is 10x faster
>> than Erik's list-based Haskell:
OCaml might be an order of magnitude faster than Haskell at sorting but it
is a lot slower than other languages.
> and says that Ocaml sorting arrays is faster than Haskell sorting lists.
> Well this would not surpise anyone who has studied computer science. Lists
> are simply not the right data structure for efficient sorting.
I look forward to seeing some fast array-based Haskell code from you.
> He then goes on to make another outrageous claim:
>
>> This parallel generic F# is 330x faster than Erik's Haskell:
>
>> In fact, this F# can sort 100M elements faster than Haskell sorts 1M
>> elements!
>
> There is no mention here of how many cores are being used...
8 cores.
> I really, really doubt running "parallel generic F#" to sort *arrays*
> on a single core is 330x faster than the Haskell qsort of a list.
Even if you cripple my F# to run on only a single core then it is still 100x
faster than your (incorrect) Haskell.
> If you throw more cores at it this may be true, but that's not really
> comparing like with like is it?
Benchmarking against your broken Haskell code isn't comparing like with like
either.
> And where is the evidence to support the 6000x slower claim?
At the end of the rainbow of correctness.
Fix your code so that it can sort 100M elements correctly and then compare
its performance to C++ or F#.
Florian Kreidler
> Manlio Perillo wrote:
>> It is a problem with naive pure functional implementations, including
>> OCaml.
>
> No, it is a problem with Haskell.
>
>>> let swap a i j =
>>> let t = a.(i) in
>>> a.(i) <- a.(j);
>>> a.(j) <- t
>>>
>>> let rec qsort a l u =
>>> if l < u then
>>> let m = ref l in
>>> for i=l+1 to u do
>>> if a.(i) < a.(l) then begin
>>> m := !m + 1;
>>> swap a !m i
>>> end
>>> done;
>>> swap a l !m;
>>> qsort a l (!m - 1);
>>> qsort a (!m + 1) u
>>>
>>
>> I'm rather sure that you can write a similar function in Haskell, using
>> Haskell mutable arrays.
>
> No, you cannot.
Yes, you can.
> That's the whole point. Every write to a generic array in
> Haskell is potentially O(n) in general instead of O(1).
Wrong.
Manlio Perillo
> [...]
>> In Haskell things are just a bit problematic when dealing with mutable
>> arrays.
>
> So problematic that Haskell still doesn't provide a usable hash table
> implementation.
>
See
http://hackage.haskell.org/trac/ghc/ticket/3149
and
http://hackage.haskell.org/trac/ghc/ticket/650
And, finally, see:
http://shootout.alioth.debian.org/u64q/benchmark.php?
test=knucleotide&lang=ghc&id=4
for an efficient hash table implementation.
Here is a comparison of the same problem in all languages
http://shootout.alioth.debian.org/u64q/benchmark.php?
test=knucleotide&lang=all&box=1
> [...]
Regards Manlio
Nobody
> In Haskell you can write mutable code by explicitely specifying the
> execution order using special state monads. You get (at most) the same
> thing, with an inconvenient syntax.
... plus a guarantee that whatever happens in one runST has no effect upon
any other runST anywhere else in the program.
Jon Harrop
Post working code.
Nobody
>> I'm rather sure that you can write a similar function in Haskell, using
>> Haskell mutable arrays.
>
> No, you cannot. That's the whole point. Every write to a generic array in
> Haskell is potentially O(n) in general instead of O(1). So you get
> asymptotically much worse performance that is unusable in practice. That is
> why real Haskell code resorts to unsuitable data structures like lists to
> avoid this problem whereas idiomatic OCaml/F# code does not.
The reason people use lists over arrays isn't because of an implementation
defect in GHC's garbage collection with regard to boxed arrays.
Jon Harrop
> See
> http://hackage.haskell.org/trac/ghc/ticket/3149
> and
> http://hackage.haskell.org/trac/ghc/ticket/650
Those describe the GC perf bug that causes the problem.
> And, finally, see:
> http://shootout.alioth.debian.org/u64q/benchmark.php?
> test=knucleotide&lang=ghc&id=4
>
> for an efficient hash table implementation.
Using malloc and memset directly, i.e. not written in Haskell.
> Here is a comparison of the same problem in all languages
> http://shootout.alioth.debian.org/u64q/benchmark.php?
> test=knucleotide&lang=all&box=1
You need to fix that perf bug before you can write a performant quicksort or
hash table in Haskell or many other array-based solutions. Until then,
Haskell programmers resort to list-based sorts that are orders of magnitude
slower (which was my original point).
Manlio Perillo
> Manlio Perillo wrote:
>> See
>> http://hackage.haskell.org/trac/ghc/ticket/3149 and
>> http://hackage.haskell.org/trac/ghc/ticket/650
>
> Those describe the GC perf bug that causes the problem.
>
>> And, finally, see:
>> http://shootout.alioth.debian.org/u64q/benchmark.php?
>> test=knucleotide&lang=ghc&id=4
>>
>> for an efficient hash table implementation.
>
> Using malloc and memset directly, i.e. not written in Haskell.
>
This is Haskell code, instead.
>> Here is a comparison of the same problem in all languages
>> http://shootout.alioth.debian.org/u64q/benchmark.php?
>> test=knucleotide&lang=all&box=1
>
> You need to fix that perf bug before you can write a performant
> quicksort or hash table in Haskell or many other array-based solutions.
Yes, that's true.
And that bug is now 4 years old; not a good thing.
> Until then, Haskell programmers resort to list-based sorts that are
> orders of magnitude slower (which was my original point).
Regards Manlio
Florian Kreidler
Jon Harrop
Why do you think Haskell programmers choose inefficient data structures if
not because they don't have a choice? For example, why does GHC's stdlib
provide only sort functions that are orders of magnitude slower than most
other compiled languages and which stack overflows?
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> Florian Kreidler wrote:
>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>> Manlio Perillo wrote:
>>>>> I'm rather sure that you can write a similar function in Haskell,
>>>>> using Haskell mutable arrays.
>>>>
>>>> No, you cannot.
>>>
>>> Yes, you can.
>>
>> Post working code.
You cannot because it is impossible.
> Substantiate your claim...
Burden of proof fallacy.
> ...instead of deleting it.
I deleted only your incorrect claim that I was wrong.
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> Florian Kreidler wrote:
>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>> Manlio Perillo wrote:
>>>>>> I'm rather sure that you can write a similar function in Haskell,
>>>>>> using Haskell mutable arrays.
>>>>>
>>>>> No, you cannot.
>>>>
>>>> Yes, you can.
>>>
>>> Post working code.
>
> You cannot because it is impossible.
>
>> Substantiate your claim...
>
> Burden of proof fallacy.
You were the one who claimed that "every write to a
generic array in Haskell is potentially O(n) in
general instead of O(1)."
>> ...instead of deleting it.
>
> I deleted only your incorrect claim that I was wrong.
Goodbye.
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> Florian Kreidler wrote:
>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>> Florian Kreidler wrote:
>>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>>> Manlio Perillo wrote:
>>>>>>> I'm rather sure that you can write a similar function in Haskell,
>>>>>>> using Haskell mutable arrays.
>>>>>>
>>>>>> No, you cannot.
>>>>>
>>>>> Yes, you can.
>>>>
>>>> Post working code.
>>
>> You cannot because it is impossible.
>>
>>> Substantiate your claim...
>>
>> Burden of proof fallacy.
>
> You were the one who claimed that "every write to a
> generic array in Haskell is potentially O(n) in
> general instead of O(1)."
Google the last time I proved it here.
Jon Harrop
> Il Sat, 05 Dec 2009 17:28:37 +0000, Jon Harrop ha scritto:
>> Using malloc and memset directly, i.e. not written in Haskell.
>
> This is Haskell code, instead.
Eh?
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> Florian Kreidler wrote:
>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>> Florian Kreidler wrote:
>>>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>>>> Manlio Perillo wrote:
>>>>>>>> I'm rather sure that you can write a similar function in Haskell,
>>>>>>>> using Haskell mutable arrays.
>>>>>>>
>>>>>>> No, you cannot.
>>>>>>
>>>>>> Yes, you can.
>>>>>
>>>>> Post working code.
>>>
>>> You cannot because it is impossible.
>>>
>>>> Substantiate your claim...
>>>
>>> Burden of proof fallacy.
>>
>> You were the one who claimed that "every write to a
>> generic array in Haskell is potentially O(n) in
>> general instead of O(1)."
>
> Google the last time I proved it here.
Okay. I have found that Johannes Laire has disproved your
claim on 2009-07-10 here in this group. I won't argue against
your strategical amnesia.
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> Florian Kreidler wrote:
>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>> Florian Kreidler wrote:
>>>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>>>> Manlio Perillo wrote:
>>>>>>>> I'm rather sure that you can write a similar function in Haskell,
>>>>>>>> using Haskell mutable arrays.
>>>>>>>
>>>>>>> No, you cannot.
>>>>>>
>>>>>> Yes, you can.
>>>>>
>>>>> Post working code.
>>>
>>> You cannot because it is impossible.
>>>
>>>> Substantiate your claim...
>>>
>>> Burden of proof fallacy.
>>
>> You were the one who claimed that "every write to a
>> generic array in Haskell is potentially O(n) in
>> general instead of O(1)."
>
> Google the last time I proved it here.
Okay. I have found that Johannes Laire has disproved your
claim on 2009-07-10 in comp.lang.lisp. I won't argue against
your strategical amnesia.
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> Florian Kreidler wrote:
>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>> Florian Kreidler wrote:
>>>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>>>> Manlio Perillo wrote:
>>>>>>>> I'm rather sure that you can write a similar function in Haskell,
>>>>>>>> using Haskell mutable arrays.
>>>>>>>
>>>>>>> No, you cannot.
>>>>>>
>>>>>> Yes, you can.
>>>>>
>>>>> Post working code.
>>>
>>> You cannot because it is impossible.
>>>
>>>> Substantiate your claim...
>>>
>>> Burden of proof fallacy.
>>
>> You were the one who claimed that "every write to a
>> generic array in Haskell is potentially O(n) in
>> general instead of O(1)."
>
> Google the last time I proved it here.
Okay. I have found that Johannes Laire has disproved your
claim on 2009-07-11 in comp.lang.lisp. I won't argue against
your strategical amnesia.
Jon Harrop
> I have found that Johannes Laire has disproved your claim on 2009-07-11 in
> comp.lang.lisp.
Johannes made a statement about a special case:
"It is O(1) for unboxed arrays." -
http://groups.google.com/group/comp.lang.lisp/msg/0079d1e0841eb75e
That does not disprove my statement about the generic case, which was
correct.
Florian Kreidler
> Florian Kreidler wrote:
>> I have found that Johannes Laire has disproved your claim on 2009-07-11 in
>> comp.lang.lisp.
>
> Johannes made a statement about a special case:
>
> "It is O(1) for unboxed arrays." -
> http://groups.google.com/group/comp.lang.lisp/msg/0079d1e0841eb75e
>
> That does not disprove my statement about the generic case, which was
> correct.
I don't want to discuss the meaning of "generic".
But why should boxed mutable arrays be needed for an in-place Quicksort?
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> Florian Kreidler wrote:
>>> I have found that Johannes Laire has disproved your claim on 2009-07-11
>>> in comp.lang.lisp.
>>
>> Johannes made a statement about a special case:
>>
>> "It is O(1) for unboxed arrays." -
>> http://groups.google.com/group/comp.lang.lisp/msg/0079d1e0841eb75e
>>
>> That does not disprove my statement about the generic case, which was
>> correct.
>
> I don't want to discuss the meaning of "generic".
The "generic" was the essence of my statement. There are workarounds for
special cases like rolling your own hash table using malloc as Manlio said
or writing a sort that works on specific types as you've implied but these
are obviously undesirable. You want to just write a generic definition,
have it work and get on with your life.
> But why should boxed mutable arrays be needed for an in-place Quicksort?
Your users might want to sort arbitrary-precision integers, options, lists
or strings. There is no sane reason why they should not be able to do so
with your generic code.
Florian Kreidler
> There are workarounds for
> special cases like rolling your own hash table using malloc as Manlio said
> or writing a sort that works on specific types as you've implied but these
> are obviously undesirable. You want to just write a generic definition,
> have it work and get on with your life.
I have 'implied' to write an all-purpose quicksort. That's quite
easy with an unboxed mutable array.
(It is not so easy to retain the advantages of the 'naive' quicksort
implementation.)
>> But why should boxed mutable arrays be needed for an in-place Quicksort?
>
> Your users might want to sort arbitrary-precision integers, options, lists
> or strings. There is no sane reason why they should not be able to do so
> with your generic code.
Indeed.
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> There are workarounds for
>> special cases like rolling your own hash table using malloc as Manlio
>> said or writing a sort that works on specific types as you've implied but
>> these are obviously undesirable. You want to just write a generic
>> definition, have it work and get on with your life.
>
> I have 'implied' to write an all-purpose quicksort. That's quite
> easy with an unboxed mutable array.
How? What happens when your user wants to sort strings with your
unboxed-array sort but Haskell's unboxed arrays prohibit string elements?
Can you parallelize it?
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> There are workarounds for
>>> special cases like rolling your own hash table using malloc as Manlio
>>> said or writing a sort that works on specific types as you've implied but
>>> these are obviously undesirable. You want to just write a generic
>>> definition, have it work and get on with your life.
>>
>> I have 'implied' to write an all-purpose quicksort. That's quite
>> easy with an unboxed mutable array.
>
> How?
Hold the elements in an immutable boxed array and sort indices
that point into that array. Easy, isn't it?
> What happens when your user wants to sort strings with your
> unboxed-array sort but Haskell's unboxed arrays prohibit string elements?
> Can you parallelize it?
Yes, just break the mutable array of indices into smaller parts.
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> Florian Kreidler wrote:
>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>> There are workarounds for
>>>> special cases like rolling your own hash table using malloc as Manlio
>>>> said or writing a sort that works on specific types as you've implied
>>>> but these are obviously undesirable. You want to just write a generic
>>>> definition, have it work and get on with your life.
>>>
>>> I have 'implied' to write an all-purpose quicksort. That's quite
>>> easy with an unboxed mutable array.
>>
>> How?
>
> Hold the elements in an immutable boxed array and sort indices
> that point into that array. Easy, isn't it?
Easy but can still be several times slower than necessary.
>> What happens when your user wants to sort strings with your
>> unboxed-array sort but Haskell's unboxed arrays prohibit string elements?
>> Can you parallelize it?
>
> Yes, just break the mutable array of indices into smaller parts.
Yes. Better to fix that bug in GHC though...
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> Florian Kreidler wrote:
>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>> There are workarounds for
>>>>> special cases like rolling your own hash table using malloc as Manlio
>>>>> said or writing a sort that works on specific types as you've implied
>>>>> but these are obviously undesirable. You want to just write a generic
>>>>> definition, have it work and get on with your life.
>>>>
>>>> I have 'implied' to write an all-purpose quicksort. That's quite
>>>> easy with an unboxed mutable array.
>>>
>>> How?
>>
>> Hold the elements in an immutable boxed array and sort indices
>> that point into that array. Easy, isn't it?
>
> Easy but can still be several times slower than necessary.
Maybe, maybe not.
>>> What happens when your user wants to sort strings with your
>>> unboxed-array sort but Haskell's unboxed arrays prohibit string elements?
>>> Can you parallelize it?
>>
>> Yes, just break the mutable array of indices into smaller parts.
>
> Yes. Better to fix that bug in GHC though...
No, fixing that bug will not allow different threads to modify the same
array simultaneously.
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> schrieb:
>> Florian Kreidler wrote:
>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>> Florian Kreidler wrote:
>>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>>> There are workarounds for
>>>>>> special cases like rolling your own hash table using malloc as Manlio
>>>>>> said or writing a sort that works on specific types as you've implied
>>>>>> but these are obviously undesirable. You want to just write a generic
>>>>>> definition, have it work and get on with your life.
>>>>>
>>>>> I have 'implied' to write an all-purpose quicksort. That's quite
>>>>> easy with an unboxed mutable array.
>>>>
>>>> How?
>>>
>>> Hold the elements in an immutable boxed array and sort indices
>>> that point into that array. Easy, isn't it?
>>
>> Easy but can still be several times slower than necessary.
>
> Maybe, maybe not.
4.6x slower according to my measurements.
>>>> What happens when your user wants to sort strings with your
>>>> unboxed-array sort but Haskell's unboxed arrays prohibit string
>>>> elements? Can you parallelize it?
>>>
>>> Yes, just break the mutable array of indices into smaller parts.
>>
>> Yes. Better to fix that bug in GHC though...
>
> No, fixing that bug will not allow different threads to modify the same
> array simultaneously.
I have been told before that different threads can already modify separate
subarrays of the same array in Haskell. The person who told me that failed
to provide any working Haskell code though.
Florian Kreidler
> Florian Kreidler wrote:
>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>> Florian Kreidler wrote:
>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>> Florian Kreidler wrote:
>>>>>> Jon Harrop <j...@ffconsultancy.com> schrieb:
>>>>>>> There are workarounds for
>>>>>>> special cases like rolling your own hash table using malloc as Manlio
>>>>>>> said or writing a sort that works on specific types as you've implied
>>>>>>> but these are obviously undesirable. You want to just write a generic
>>>>>>> definition, have it work and get on with your life.
>>>>>>
>>>>>> I have 'implied' to write an all-purpose quicksort. That's quite
>>>>>> easy with an unboxed mutable array.
>>>>>
>>>>> How?
>>>>
>>>> Hold the elements in an immutable boxed array and sort indices
>>>> that point into that array. Easy, isn't it?
>>>
>>> Easy but can still be several times slower than necessary.
>>
>> Maybe, maybe not.
>
> 4.6x slower according to my measurements.
You said that the straightforward solution was impossible to
implement. And now you have measured it? How did you do that?
> I have been told before that different threads can already modify separate
> subarrays of the same array in Haskell. The person who told me that failed
> to provide any working Haskell code though.
That sounds interesting. Is it possible with ordinary STUArrays?
Jon Harrop
>
> You said that the straightforward solution was impossible to
> implement.
In Haskell because the fast solution would be O(n^4) due to that perf bug in
the GC, yes.
> And now you have measured it? How did you do that?
I wrote both versions in F#, benchmarked them and assumed the performance
ratio would be similar in Haskell if it could express the programs (i.e. if
that perf bug in the GC were fixed). That seems reasonable because this
boils down to C-like array-mutating code except for the parallelism which
is coarse grained anyway. Specifically, I sorted float32 arrays either
directly or with the extra indirecting array and found the latter to be
4.6x slower.
>> I have been told before that different threads can already modify
>> separate subarrays of the same array in Haskell. The person who told me
>> that failed to provide any working Haskell code though.
>
> That sounds interesting. Is it possible with ordinary STUArrays?
I've lost the description of how its done. :-(
raould
> > intuitiveness? not sure how that should end up in the code. maybe
> > instead of a begin keyword there should be a keyword which says "the
> > stuff here is allowed to be reordered"?
>
> Possibly but Haskell permits all of these optimizations and, yet, its
> performance sucks beyond belief. Look at the idiomatic Haskell quicksort,
> for example:
[while i (sincerely, as another critic) appreciate you like any chance
to dog haskell, my original point was not about getting side-tracked
into talking about bugs in ghc; note how i never even mentioned
haskell, and was in particular talking about lisps. my point right now
being that i get the feeling it is hard to start up and continue a
diversity of discussions here when they are seemingly inevitably
hijacked to repeat ad nauseum some old bitching about haskell. please,
please, avoid doing that.]
to get back to what i was originally trying to ask about -- sure, i
might have failed to get it across -- was a question about the
"intuitiveness" (a loaded term, i know) of implicit vs. explicit re/
ordering of expressions.
speaking for myself, i find the lisp/scheme middle-ground to be
confusing. i would prefer a situation that requires things to be more
explicitly spelled out in the source code. the 2 options seem to be:
everything is sequential unless otherwise noted, vs. nothing is
guaranteed to be sequential unless otherwise noted.
i am curious how other people react to this particular issue.
thanks.
Jon Harrop
>> > seems like we're agreed that specified ordering is better for
>> > intuitiveness? not sure how that should end up in the code. maybe
>> > instead of a begin keyword there should be a keyword which says "the
>> > stuff here is allowed to be reordered"?
>>
>> Possibly but Haskell permits all of these optimizations and, yet, its
>> performance sucks beyond belief. Look at the idiomatic Haskell quicksort,
>> for example:
>
> [while i (sincerely, as another critic) appreciate you like any chance
> to dog haskell, my original point was not about getting side-tracked
> into talking about bugs in ghc;
The post of mine that you are replying to had nothing to do with bugs in
GHC.
> note how i never even mentioned
> haskell, and was in particular talking about lisps.
Sure. My point was that Haskell already took this idea to the extreme and
produced results that answer your question. Languages like F# already
learned from those results and chose not to take the same route as Haskell
precisely because it does not pay off: for all the optimizations that
Haskell exposes and facilitates it remains an extremely slow language.
> my point right now
> being that i get the feeling it is hard to start up and continue a
> diversity of discussions here when they are seemingly inevitably
> hijacked to repeat ad nauseum some old bitching about haskell. please,
> please, avoid doing that.]
Perhaps I misunderstood your question but it seems to me that Haskell
already answered your question. The only other thing I'd add is that
OCaml's undefined evaluation order for function applications only serves to
confuse newbies and introduce bugs.
The fact that Haskell makes it difficult or impossible to optimize code and
attain competitive performance for trivial algorithms like parallel generic
quicksort has nothing to do with your question. I'm sorry that the thread
descended into that but I don't like it when Erik/Ertugrul/whoever try to
dismiss these failures or limit comparisons to crap languages or crap code
in other languages. Perhaps I should have changed the post's subject...