May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Jan-Eric Duden | ```
"Jan-Eric Duden" <jeduden@whisset.com> wrote in message
news:c7sioo$cvh$1@digitaldaemon.com...
>
> > You're welcome. You should also note that arrays have a built-in sort
> > property, which uses quicksort. It'll blow away heapsort <g>. Doing that
> > cuts the sort time on my machine from 453 ms to 63 ms. Source attached.
> >
> I am wondering if the difference of execution time is the result of using
> different algorithms (quicksort or heapsort). Or can the code for the sort
> property be better optimized than a "normal" implementation of a sort
> algorithm?
I'd have to do testing to make sure, but I'm pretty sure it's due to
quicksort being algorithmically superior. One of the reasons I built sort
into arrays is because people implement inefficient sorts over and over, and
I wanted to make it real easy to use the best algorithm. (A job I had once
was to optimize a large program written by others; in poking around in it I
found 3 different hacky implementations of bubblesort. Replaced them all
with a call to C's qsort(), and I was an instant hero for the speedup <g>.)
``` |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Walter | > I'd have to do testing to make sure, but I'm pretty sure it's due to > quicksort being algorithmically superior. One of the reasons I built sort > into arrays is because people implement inefficient sorts over and over, and > I wanted to make it real easy to use the best algorithm. (A job I had once > was to optimize a large program written by others; in poking around in it I > found 3 different hacky implementations of bubblesort. Replaced them all > with a call to C's qsort(), and I was an instant hero for the speedup <g>.) I thought qsort and heapsort work about at the same speed. I thought the most important difference between a heapsort and q-sort implementation in C is the order of the algorithms: - heapsort has roughly the same performance for all array instanciations O(n*log n) - qsort is a lot slower O(n^2) on some instanciations and a lot faster on almost sorted arrays O(n). the average is of course: O(n*log n) Maybe the difference is that the C q-sort implementation is highly optimizied and the heapsort implementation that was used is not? |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Jan-Eric Duden | "Jan-Eric Duden" <jeduden@whisset.com> wrote in message news:c7spim$n4h$1@digitaldaemon.com... > > I'd have to do testing to make sure, but I'm pretty sure it's due to > > quicksort being algorithmically superior. One of the reasons I built sort > > into arrays is because people implement inefficient sorts over and over, > and > > I wanted to make it real easy to use the best algorithm. (A job I had once > > was to optimize a large program written by others; in poking around in it > I > > found 3 different hacky implementations of bubblesort. Replaced them all > > with a call to C's qsort(), and I was an instant hero for the speedup > <g>.) > > I thought qsort and heapsort work about at the same speed. > > I thought the most important difference between a heapsort and q-sort > implementation in C is the order of the algorithms: > - heapsort has roughly the same performance for all array instanciations > O(n*log n) > - qsort is a lot slower O(n^2) on some instanciations and a lot faster on > almost sorted arrays O(n). the average is of course: O(n*log n) > > Maybe the difference is that the C q-sort implementation is highly > optimizied and the heapsort implementation that was > used is not? Both quicksort and heapsort are O(n log n) on average but the constants involved in Quicksort are much better. Quicksort though depends a lot on whether the partitioning subroutine is balanced. The differences are discussed at length in Introduction to Algorithms by Cormen, Leiserson and Rivest ( http://theory.lcs.mit.edu/~clr/ ) -- Christopher Diggins http://www.cdiggins.com http://www.heron-language.com |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Kevin Bealer | "Kevin Bealer" <Kevin_member@pathlink.com> wrote in message news:c7rkjh$2216$1@digitaldaemon.com... > In article <c7rhdv$1t4h$1@digitaldaemon.com>, christopher diggins says... > .. > >You are correct, but Vector2D is used to demonstrate a class that is > >run-time polymorphic but happens to be used in a non-polymorphic manner. I > >could easily add to the demo a modification that forces the issue of > >polymorphism, but I thought it would complicate things too much. Do you > >recommend that I change the demo to make this more explicit? > > Heron's approach of non-inheritance binding is interesting; I take it there is > a global dispatch table with pointers to all methods appearing in non-deduceable > cases? Close, there are lots of small tables created. > I think the demo you have is good as far as it goes. But I would be more > interested to know what happens in both cases for both languages: i.e. C++ > run-time and compile-time and Heron run-time and compile-time. If Heron can > outperform in *both* cases, that would be much more impressive. Good point. > But in (performance oriented code) in a language like C++, virtual-ness is > usually used only when compile time binding is difficult to achieve. In retrospect, I am starting to be of the opinion that the example may fact rigged as you mentioned. There is no way that I can justify a design that uses ICompare as a class with virtual functions. -- Christopher Diggins http://www.cdiggins.com http://www.heron-language.com |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to christopher diggins | christopher diggins wrote: <snip> >> - qsort is a lot slower O(n^2) on some instanciations and a lot >> faster on almost sorted arrays O(n). the average is of course: >> O(n*log n) Can you give an example of an O(n) case of quicksort? >> Maybe the difference is that the C q-sort implementation is highly >> optimizied and the heapsort implementation that was used is not? > > Both quicksort and heapsort are O(n log n) on average <snip> Yes, but in the worst case, heapsort wins O(n log n) to O(n^2). When benchmarking a sorting algorithm, it's helpful to try a number of random cases, as well as the control cases of already sorted and already sorted backwards. If you're benchmarking algorithms, rather than compilers or languages, you should try to use the same compiler, the same language and the same compiler options. As such, it makes limited sense to compare a ready-made C library function of one algorithm with your own implementation of another. Of course, if you're comparing languages/compilers, you should compare implementations of the same algorithm, and set as similar levels of optimisation as possible (ITMS). Stewart. -- My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment. Please keep replies on the 'group where everyone may benefit. |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Stewart Gordon | > > Can you give an example of an O(n) case of quicksort? A sorted array. You only get O(n) in a slightly modified version of q-sort that quits if no swaps occured. > > >> Maybe the difference is that the C q-sort implementation is highly > >> optimizied and the heapsort implementation that was used is not? > > > > Both quicksort and heapsort are O(n log n) on average > <snip> > > Yes, but in the worst case, heapsort wins O(n log n) to O(n^2). Yep, that's why sometimes heapsort is preferred over quicksort. My question was more related to the constants. I wasn't aware that heapsort is that much slower. |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Jan-Eric Duden | Jan-Eric Duden wrote: >>Can you give an example of an O(n) case of quicksort? > > A sorted array. You only get O(n) in a slightly modified version of q-sort > that quits if no swaps occured. By 'swaps' do you mean the swapping of an element with the hole into which the key element is to go? How can one element being already in the right place imply that the whole array is sorted? <snip> > Yep, that's why sometimes heapsort is preferred over quicksort. > > My question was more related to the constants. I wasn't aware that heapsort > is that much slower. What constants? Stewart. -- My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment. Please keep replies on the 'group where everyone may benefit. |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Stewart Gordon | ```
Stewart Gordon wrote:
>
> Yes, but in the worst case, heapsort wins O(n log n) to O(n^2).
But some versions of heapsort need a considerable memory overhead to
run. In general, quicksort is the better choice for average sorting
situations. People with special needs generally also know how to code
for those needs :)
Sean
``` |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to Sean Kelly | Sean Kelly wrote: > Stewart Gordon wrote: > >> >> Yes, but in the worst case, heapsort wins O(n log n) to O(n^2). > > > But some versions of heapsort need a considerable memory overhead to > run. In general, quicksort is the better choice for average sorting > situations. People with special needs generally also know how to code > for those needs :) > > Sean Right! Even sort algorithms like short-circuit bubble sort can be useful if they are used in right application. Short-circuit bubble sort is most useful when you know that most-of-the the array is sorted because then you get o(n). With standard quicksort you'd get O(n^2) for a sorted array. -- -Anderson: http://badmama.com.au/~anderson/ |

May 12, 2004 Re: D performance compared with other languages | |
---|---|

Posted in reply to J Anderson | J Anderson wrote: <snip> > Right! Even sort algorithms like short-circuit bubble sort can be > useful if they are used in right application. Short-circuit bubble sort > is most useful when you know that most-of-the the array is sorted > because then you get o(n). With standard quicksort you'd get O(n^2) for > a sorted array. Even better for nearly sorted data is bidirectional short-circuit bubble sort. Stewart. -- My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment. Please keep replies on the 'group where everyone may benefit. |