Recent

Author Topic: Lomuto Quicksort is very slow  (Read 2041 times)

SimoneD

  • Newbie
  • Posts: 4
Lomuto Quicksort is very slow
« on: January 21, 2021, 06:24:34 pm »
Hi, I just coded a Quicksort algorithm (Lomuto scheme) in pascal, but it is super slow (takes about the time my bubblesort takes for 100000 random elements and more than double compared to insertionsort). The output procedure is the same for every algorithm so I assume, that that isn't the problem.

this is my function:
Code: Pascal  [Select][+][-]
  1. function AlgorithmusQuicksortLomuto(Anfang, Ende: integer; Werte:arr):arr;
  2. var
  3.     i, pivotWert, pivotIndex : integer;
  4. begin
  5.    if (Anfang < Ende) then
  6.    begin
  7.      pivotWert:= Werte[Ende];
  8.      pivotIndex:= Anfang;
  9.  
  10.      for i:= Anfang to (Ende-1) do //Array is sorted in what is smaller and larger than pivot
  11.      begin                    
  12.           if (Werte[i] < pivotWert) then
  13.           begin
  14.                Tauschen(i, pivotIndex, Werte); //switch
  15.                pivotIndex:= pivotIndex + 1;
  16.           end;
  17.      end;
  18.  
  19.      Tauschen(pivotIndex, Ende, Werte); //switchPivot is placed on right place of array
  20.      AlgorithmusQuicksortLomuto(Anfang, pivotIndex-1, Werte); //left side
  21.      AlgorithmusQuicksortLomuto(pivotIndex+1, Ende, Werte); //right side
  22.    end;
  23.    AlgorithmusQuicksortLomuto:= Werte;
  24. end;                            


Do you have any idea why it is so terribly slow? Thanks for any help!
« Last Edit: January 21, 2021, 06:43:42 pm by SimoneD »

MathMan

  • Sr. Member
  • ****
  • Posts: 325
Re: Lomuto Quicksort is very slow
« Reply #1 on: January 22, 2021, 01:34:37 pm »
Hard to judge in total, as your implementation for bubble- & insertion-sort have not been shown. Things I see directly

* lomuto is easier to implement than Hoare, but on average generates more comparisons & swaps - you may want to read this
https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

* Lomuto behaves much worse than Hoare, if there are many duplicates in the array to be sorted. Are you sure that in your benchmark with 100000 elements no (or only few) values are duplicated?

* I see that you do the swaps as a separate function call. In comparison with thee actual work required this is a substantial overhead. Can you inline "Tauschen"?

Cheers,
MathMan

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Lomuto Quicksort is very slow
« Reply #2 on: January 22, 2021, 01:37:02 pm »
And of course an (nearly) already sorted list is a worst case for quicksort.  E.g. adding a few elements to an existing list and then resorting.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Lomuto Quicksort is very slow
« Reply #3 on: January 22, 2021, 01:42:31 pm »
* I see that you do the swaps as a separate function call. In comparison with thee actual work required this is a substantial overhead. Can you inline "Tauschen"?

Noting that FPC 3.2.0 has problems with functions declared as "inline", do you mean explicitly cut-and-pasting here?

I'm not a CS or algorithms man but I notice that the function is recursive and that the final parameter is passed by value i.e. copied in memory. That doesn't look very good if done repeatedly.

I think (a generator for reproducible) test data would be useful.

MarkMLl
« Last Edit: January 22, 2021, 01:48:05 pm by MarkMLl »
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MathMan

  • Sr. Member
  • ****
  • Posts: 325
Re: Lomuto Quicksort is very slow
« Reply #4 on: January 22, 2021, 01:50:02 pm »
* I see that you do the swaps as a separate function call. In comparison with thee actual work required this is a substantial overhead. Can you inline "Tauschen"?

Noting that FPC 3.2.0 has problems with functions declared as "inline", do you mean explicitly cut-and-pasting here?

I think (a generator for reproducible) test data would be useful.

MarkMLl

I personally would explicitely cut-and-paste for various reasons.

MathMan

SimoneD

  • Newbie
  • Posts: 4
Re: Lomuto Quicksort is very slow
« Reply #5 on: January 23, 2021, 07:10:55 pm »
Thanks for your help. I copy and pasted the "Tauschen"-procedure, which almost cut the time in half. Still seems kind of slow, but I think I am satisfied.

Blaazen

  • Hero Member
  • *****
  • Posts: 3237
  • POKE 54296,15
    • Eye-Candy Controls
Re: Lomuto Quicksort is very slow
« Reply #6 on: January 23, 2021, 10:05:31 pm »
Your QuickSort is basically good, what is wrong is how you choose the pivot. You choose the last element of the (sub)array. It does not matter for random inputs but for sorted or partially sorted inputs (both ascendent or desc.) it causes the worst case O(n^2) and ít slow down sorting to times of BubbleSort. I recommend you to choose pivot from the middle of subarray or even better, the median of three. It is well explained on wiki: https://en.wikipedia.org/wiki/Quicksort.
Lazarus 2.3.0 (rev main-2_3-2863...) FPC 3.3.1 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Lomuto Quicksort is very slow
« Reply #7 on: January 24, 2021, 12:00:57 pm »
* I see that you do the swaps as a separate function call. In comparison with thee actual work required this is a substantial overhead. Can you inline "Tauschen"?

Noting that FPC 3.2.0 has problems with functions declared as "inline", do you mean explicitly cut-and-pasting here?

Please elaborate. FPC 3.2.0 is not worse in inlining than older compilers in contrary, it's better (and 3.3.1 even more so). What is different however is that FPC 3.2.0 generates a hint if it decides not to inline a routine marked as inline which older compilers did not do, instead they silently did not do the inlining.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Lomuto Quicksort is very slow
« Reply #8 on: January 24, 2021, 12:24:29 pm »
What is different however is that FPC 3.2.0 generates a hint if it decides not to inline a routine marked as inline which older compilers did not do, instead they silently did not do the inlining.

Thanks, noted. I was basing it on previous comments from somebody (possibly but not necessarily you) that inlining was currently forcibly disabled: presumably that applied only to the trunk development version. (I think the context was somebody complaining that his functions were never being inlined, and my pointing out that the relevant bit of the compiler and the decision criteria were easily found.)

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Lomuto Quicksort is very slow
« Reply #9 on: January 24, 2021, 12:37:16 pm »
Thanks, noted. I was basing it on previous comments from somebody (possibly but not necessarily you) that inlining was currently forcibly disabled: presumably that applied only to the trunk development version. (I think the context was somebody complaining that his functions were never being inlined, and my pointing out that the relevant bit of the compiler and the decision criteria were easily found.)

You'd have to find that comment again... Inlining (no matter if 3.2.x or trunk) is only disabled for specific situations (e.g. when you have an open array parameter) cause the compiler can not handle them yet (and that's also when the hint comes into play).

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: Lomuto Quicksort is very slow
« Reply #10 on: January 24, 2021, 01:28:52 pm »
Thanks, noted. I was basing it on previous comments from somebody (possibly but not necessarily you) that inlining was currently forcibly disabled: presumably that applied only to the trunk development version. (I think the context was somebody complaining that his functions were never being inlined, and my pointing out that the relevant bit of the compiler and the decision criteria were easily found.)

You'd have to find that comment again... Inlining (no matter if 3.2.x or trunk) is only disabled for specific situations (e.g. when you have an open array parameter) cause the compiler can not handle them yet (and that's also when the hint comes into play).

There's been two threads related to inlining in the last few months, and one of them links to https://wiki.freepascal.org/Inline which explicitly says

Quote
Warning: Use inline with caution as there are currently bugs in all FPC versions. This affects all platforms. As of 14 February 2020

If that's not (or is no longer) true then it could do with fixing, and I think it could also usefully do with a brief exposition of what is and what isn't inlined.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Lomuto Quicksort is very slow
« Reply #11 on: January 25, 2021, 09:11:10 am »
There's been two threads related to inlining in the last few months, and one of them links to https://wiki.freepascal.org/Inline which explicitly says

Quote
Warning: Use inline with caution as there are currently bugs in all FPC versions. This affects all platforms. As of 14 February 2020

If that's not (or is no longer) true then it could do with fixing, and I think it could also usefully do with a brief exposition of what is and what isn't inlined.

In my opinion that was never true to the extent explained there.

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Lomuto Quicksort is very slow
« Reply #12 on: January 25, 2021, 09:22:31 am »
Not opinion but fact.
The comment reflects a misunderstanding about inline: It is a compiler hint that can be ignored by the compiler.
So there is never a guarantee that code will be inlined.

This is clearly documented. https://freepascal.org/docs-html/ref/refsu75.html#x195-21700014.9.5

Furthermore, the compiler is very chatty about not inlining, so someone has been ignoring warnings.
I have editted the wiki warning to explain what really happens.
« Last Edit: January 25, 2021, 09:32:20 am by Thaddy »
Specialize a type, not a var.

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Lomuto Quicksort is very slow
« Reply #13 on: January 25, 2021, 01:47:32 pm »
Furthermore, the compiler is very chatty about not inlining, so someone has been ignoring warnings.
I have editted the wiki warning to explain what really happens.

Please note that this "chatty" behaviour is only since 3.2.0 (or some time in 3.1.1).

Also your warning is not quite right either: it's not only about code complexity, but also about the compiler not supporting something. E.g. in 3.3.1 the compiler gained support for inlining functions from another unit that accesses local symbols, thus the "can not inline" hint disappears for such messages and thus user shouldn't remove the inline directive as future versions might improve this (also it's simply a hint, not a warning...)

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Lomuto Quicksort is very slow
« Reply #14 on: January 25, 2021, 01:52:39 pm »
I will adapt accordingly. Tnx Sven.
Specialize a type, not a var.

 

TinyPortal © 2005-2018