Recent

Author Topic: I made a Pascal translation of PDQSort.  (Read 1531 times)

Akira1364

  • Hero Member
  • *****
  • Posts: 539
I made a Pascal translation of PDQSort.
« on: October 30, 2019, 10:09:04 pm »
You can find it here:

https://github.com/Akira13641/PasPDQSort

Initial tests are giving me results that are consistently quite a bit faster than regular QuickSort as implemented by TArrayHelper from RTL-Generics, so at the very least it doesn't seem like I "lost anything in translation", haha.

edwinyzh

  • New Member
  • *
  • Posts: 37
Re: I made a Pascal translation of PDQSort.
« Reply #1 on: November 02, 2019, 10:00:44 am »
Thanks for sharing your open source project!

avk

  • Full Member
  • ***
  • Posts: 154
    • my self-education project
Re: I made a Pascal translation of PDQSort.
« Reply #2 on: November 07, 2019, 06:23:48 am »
Thank you very much, I've added your implementation in my own benchmark(called "sortrace").

Thaddy

  • Hero Member
  • *****
  • Posts: 9183
Re: I made a Pascal translation of PDQSort.
« Reply #3 on: November 07, 2019, 06:56:30 am »
Thank you very much, I've added your implementation in my own benchmark(called "sortrace").
And how does it perform?
also related to equus asinus.

JernejL

  • Jr. Member
  • **
  • Posts: 64
Re: I made a Pascal translation of PDQSort.
« Reply #4 on: November 07, 2019, 07:23:22 am »
The hero we needed!
 
Also, your code - basic usage example is a really good example for why we need anonymous functions :) the function could be just simply put in as a parameter.
 
Btw - PasPDQSort.pas is missing the MIT license in the file itself.
 
A small code nitpick: the code is super well organized, simple and elegant and i'm super grateful - but it has zero comments so it's not easy to study.
 
« Last Edit: November 07, 2019, 07:28:31 am by JernejL »

avk

  • Full Member
  • ***
  • Posts: 154
    • my self-education project
Re: I made a Pascal translation of PDQSort.
« Reply #5 on: November 07, 2019, 07:38:16 am »
And how does it perform?
Pretty good, on my win7 machine:

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: I made a Pascal translation of PDQSort.
« Reply #6 on: November 08, 2019, 06:58:48 am »
Thank you very much, I've added your implementation in my own benchmark(called "sortrace").

I noticed! (I use LGenerics for a few things.) I'm not sure you have quite the most recent version of it, however (I added a bit more inlining and some other small optimizations a few days ago, nothing too major though.)

Btw - PasPDQSort.pas is missing the MIT license in the file itself.

That's actually not required. It just needs to be included alongside the code. I might add it anyways though, I suppose.

A small code nitpick: the code is super well organized, simple and elegant and i'm super grateful - but it has zero comments so it's not easy to study.

Thanks! As far as the comments, I didn't really see the need because it's just a direct line-by-line translation of the original C++ version (which does have very in-depth comments for everything.)
« Last Edit: November 08, 2019, 07:44:46 am by Akira1364 »

Thaddy

  • Hero Member
  • *****
  • Posts: 9183
Re: I made a Pascal translation of PDQSort.
« Reply #7 on: November 08, 2019, 08:49:17 am »
@Akira1364
It is a very useful piece of code and indeed the C++ code is well documented, but many users, unlike you or me or avk, have no clue.
Nice to see that we have another option and for certain scenario's your code is impressive as shown from avk's benchmarks.
(which is, by itself, a well founded piece of code. It tries to circumvent bias, which is a hard thing to do with benchmarking)
What I still need to test is memory pressure.
« Last Edit: November 08, 2019, 08:53:00 am by Thaddy »
also related to equus asinus.

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: I made a Pascal translation of PDQSort.
« Reply #8 on: November 08, 2019, 02:42:46 pm »
Nice to see that we have another option and for certain scenario's your code is impressive as shown from avk's benchmarks.

I hope to improve the performance even more, but yeah, I'm fairly happy that the overall design holds up fairly well despite the fact it's clearly designed to take advantage of optimizations that only C++ compilers do.

E.G. as far as I can tell, the functions I wrote to mimic the specific behaviour of the pre and post increment / decrement C++ operators probably have a bit more overhead than the actual operators do in C++, even though I made sure they were fully inlined.

So I might see if there's anywhere else I can eliminate their use and just use FPC's normal operators directly (which I've already done to some extent in a few places.)

Thaddy

  • Hero Member
  • *****
  • Posts: 9183
Re: I made a Pascal translation of PDQSort.
« Reply #9 on: November 08, 2019, 03:54:57 pm »
despite the fact it's clearly designed to take advantage of optimizations that only C++ compilers do.
I see no reason why Pascal compilers could not do that and not all C++ compilers do good optimization.
(I already asked for post-increment/decrement etc, but that was refused, btw, because there are equivalents possible with while and repeat)
also related to equus asinus.

440bx

  • Hero Member
  • *****
  • Posts: 1199
Re: I made a Pascal translation of PDQSort.
« Reply #10 on: November 08, 2019, 04:01:15 pm »
(I already asked for post-increment/decrement etc, but that was refused, btw, because there are equivalents possible with while and repeat)
pre and post increment/decrement are a can of worms, due in part to implicit operator precedence which is not obvious (you have to know the subtleties of the language.)

A good optimizer doesn't need them to generate optimal code.  All they do is save some typing.
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

argb32

  • Jr. Member
  • **
  • Posts: 78
    • Pascal IDE based on IntelliJ platform
Re: I made a Pascal translation of PDQSort.
« Reply #11 on: November 09, 2019, 11:20:05 am »
Nice code, thanks! I'll take note of some tricks.

Thank you very much, I've added your implementation in my own benchmark(called "sortrace").

Is it open source? If so I'll add my sort routines too.

avk

  • Full Member
  • ***
  • Posts: 154
    • my self-education project
Re: I made a Pascal translation of PDQSort.
« Reply #12 on: November 09, 2019, 01:00:34 pm »
I'm not sure you have quite the most recent version of it, however
I want to wait until you finish all the optimizations.
Is it open source?
Yes, it lives here https://github.com/avk959/LGenerics, in the "example" folder.

Akira1364

  • Hero Member
  • *****
  • Posts: 539
Re: I made a Pascal translation of PDQSort.
« Reply #13 on: November 09, 2019, 08:14:49 pm »
I see no reason why Pascal compilers could not do that and not all C++ compilers do good optimization.
(I already asked for post-increment/decrement etc, but that was refused, btw, because there are equivalents possible with while and repeat)

I didn't mean that a Pascal compiler couldn't do them. I just meant like in terms of what I specifically know GCC and Clang do at -O3 today, versus what I specifically know FPC does at -O3 today.

pre and post increment/decrement are a can of worms, due in part to implicit operator precedence which is not obvious (you have to know the subtleties of the language.)

Yeah, I generally agree.

I wouldn't use them for no reason on my own, but for this translation I pretty much had to imitate them directly in order to make sure the behavior ended up equivalent so the sorting would actually work, since the huge amount of pointer arithmetic relied on them very heavily in the original version.
« Last Edit: November 09, 2019, 08:33:21 pm by Akira1364 »

440bx

  • Hero Member
  • *****
  • Posts: 1199
Re: I made a Pascal translation of PDQSort.
« Reply #14 on: November 09, 2019, 08:58:35 pm »
I pretty much had to imitate them directly in order to make sure the behavior ended up equivalent so the sorting would actually work, since the huge amount of pointer arithmetic relied on them very heavily in the original version.
I know what you're saying.  That is so typical of C code.
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.