Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Qsort.h – Quicksort as a C macro (2019)

github.com

Post reply on HN
Print view View original

31–40 of 50 posts

Re: Qsort.h – Quicksort as a C macro (2019)

#31

Post by WalterBright »

alphaglosined wrote: post #30
WalterBright wrote: post #29

Earlier quoted context omitted.

The C preprocessor was an easy and compact way to extend C back when memory was really really tight. You can't even fit a C++98 compiler into DOS's memory space, but you can fit a C compiler in 64K. (Well, an earlier version of C.) C has been adding generics anyway, like _Generic.

About a year ago I had a look at a C compiler for 16bit computers, featured in disk form on I think Adrian's digital basement YT channel. The compiler was very basic, nothing like you'd expect from a compiler even from the dragon book. So simple and it was a production compiler too! Sadly I can't remember the name of it to reference here.

I wrote one back in 1983 or so for 16 bit DOS, too!

A few years later, I was at a C++ conference where they asked me to sit on an "Ask us anything" panel. I was there along with the developers of Microsoft C, Borland C, etc.

The first question was "do you still ship a version of your compiler that will run on a floppy disk system?"

Vendor 1 said sure, and launched into a long description of how the files could be shuffled about on the floppy to make it work.

Vendor 2 said sure, and launched into ...

My turn. I said sure, and said the floppy disk version costs $200 and comes with a hard disk drive. (That was the price of a hard disk in those days.)

That was the end of that, I never heard that question again from anybody.

Progress...

Re: Qsort.h – Quicksort as a C macro (2019)

#32

Post by alphaglosined »

rootw0rm wrote: post #17
WalterBright wrote: post #15

Earlier quoted context omitted.

> But the LESS and SWAP operations may or may not get inlined. True. But modern inliners are pretty good, and if they can't inline it due to its complexity, it's pretty unlikely it'll be faster. Note the performance comparison in the article. Low level hand-optimizations paid off handsomely in the 1980s, but are usually best left to the compiler's optimizer these days.

SIMD being an exception still (unless maybe Intel compiler + C/C++ + proper annotations)

LLVM can do an awful lot with SIMD that isn't visible in clang.

We have experienced this with LDC in D.

What I've been told is that LDC produces better IR than clang (I haven't compared, I only know that LDC is practically magical from both mine and other peoples experiments).

About the only thing I've seen that has problems with inlining is inline assembly. Intrinsics are fine (which you don't need thanks to vectorization being practically magical as long as you do some annotations like assert and get the memory layout right).

Re: Qsort.h – Quicksort as a C macro (2019)

#34

Post by orlp »

nwallin wrote: post #24
kazinator wrote: post #3

This is very good: it uses the original Hoare partitioning algorithm which moves two indices at opposite ends of the array partition toward each other, rather than the ill-considered Lomuto partitioning: while (1) { \ do q_i++; while (Q_LESS(q_i, q_l)); \ do q_j--; while (Q_LESS(q_l, q_j)); \ if (q_i >= q_j) break; /* Sedgewick says "until j Lomuto is that algorithm that moves one index, swapping lower-than-pivot ele…

Lomuto partitioning has one major advantage over Hoare: Lomuto can be implemented in such that the inner loop is branchless, while the inner loops in Hoare are branchy and wreck the branch predictor. Lomuto typically fixes the Dutch National Flag problem by keeping two 'midpoints'; left of the left midpoint is less than the pivot, right of the right midpoint is greater than the pivot, between the two midpoints is equ…

And my algorithm pdqsort uses Hoare-style partitioning, is branchless, and properly solves the Dutch National Flag problem by being 0(n log k) for k unique values on average using only a single extra comparison per partitioning.

https://github.com/orlp/pdqsort

Re: Qsort.h – Quicksort as a C macro (2019)

#35

Post by _the_inflator »

metadat wrote: post #5
kazinator wrote: post #4

Earlier quoted context omitted.

The paper says that more detailed discussion of partition methods is given in [15]. That looks like Sedwicks's Ph. D thesis which was on Quicksort? I found this: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975... Basically a longer book on Quicksort with a lot more analysis. He doesn't discuss any partitioning methods that do not move two indices toward each other from opposite ends of the subarray. It's…

Of course the logo on the paper title page is a sequence of 8 lines with each doubling on thickness. Though it'd be more visually and intuitively accurate if the lines started large and cut in half each step. :P

Nice catch, yes!

Re: Qsort.h – Quicksort as a C macro (2019)

#36

Post by murdoze »

flohofwoe wrote: post #26
WalterBright wrote: post #6

If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.

In many cases it's also enough to just enable LTO to give the compiler enough information for stamping out a specialized version. But TBH I'm a bit tired of people shitting on the C preprocessor. It's a relatively simple text replacement tool, and provides an incredible amount of bang for the buck (e.g. many problems can be solved without having to add more specialized bells and whistles to the language). It's a trad…

Agree, but it's nowhere near TASM or even MASM macro processor ;0)

Re: Qsort.h – Quicksort as a C macro (2019)

#37

Post by 1ris »

WalterBright wrote: post #29
flohofwoe wrote: post #26

Earlier quoted context omitted.

In many cases it's also enough to just enable LTO to give the compiler enough information for stamping out a specialized version. But TBH I'm a bit tired of people shitting on the C preprocessor. It's a relatively simple text replacement tool, and provides an incredible amount of bang for the buck (e.g. many problems can be solved without having to add more specialized bells and whistles to the language). It's a trad…

The C preprocessor was an easy and compact way to extend C back when memory was really really tight. You can't even fit a C++98 compiler into DOS's memory space, but you can fit a C compiler in 64K. (Well, an earlier version of C.) C has been adding generics anyway, like _Generic.

>C has been adding generics anyway, like _Generic.

"_Generic" added function overloads to c, not generics. The naming is exceptionally poor.

The submission is an example of generic programming. It an implementatin of something that works on all types that fullfill certain constrains. In this case comparable and swapable. "All types" include user defined types.

"_Generic" does something completely different. The C++ equvivalent would be std::conditional_v, myIntFunc, std::conditional, myDoubleFunc ............ The exact opposite of a generic, I'd argue, as myIntFunc and myDoubleFunc do depend on the type. You might use the preprocessor to create these functions that differ only in type, but then again, you might do what OP did.

Re: Qsort.h – Quicksort as a C macro (2019)

#38

Post by actionfromafar »

WalterBright wrote: post #31
alphaglosined wrote: post #30

Earlier quoted context omitted.

About a year ago I had a look at a C compiler for 16bit computers, featured in disk form on I think Adrian's digital basement YT channel. The compiler was very basic, nothing like you'd expect from a compiler even from the dragon book. So simple and it was a production compiler too! Sadly I can't remember the name of it to reference here.

I wrote one back in 1983 or so for 16 bit DOS, too! A few years later, I was at a C++ conference where they asked me to sit on an "Ask us anything" panel. I was there along with the developers of Microsoft C, Borland C, etc. The first question was "do you still ship a version of your compiler that will run on a floppy disk system?" Vendor 1 said sure, and launched into a long description of how the files could be shu…

Wow, in 1983 I hadn’t even seen a hard disk in person!

Re: Qsort.h – Quicksort as a C macro (2019)

#39

Post by Asooka »

WalterBright wrote: post #8
FpUser wrote: post #7

Earlier quoted context omitted.

I knew someone would come up with this kind of "wisdom". For starters you do not know what other languages they might be using for development. And whatever they do they definitely do not need patronizing.

I've done a share of C metaprogramming with the preprocessor myself, and have dealt a lot with other peoples' C metaprogramming. I've also seen people use pages of algrebra as a substitute for a couple lines of calculus. I struggled for years with a soldering iron, always frustrated by bad solder joints. Then, I discovered a Weller thermostat controlled iron, and get a perfect joint every time. Not everyone knows the…

I would probably use a separate templating language to manually generate variants of the function for each type I need, check those in git along with the template.

Re: Qsort.h – Quicksort as a C macro (2019)

#40

Post by WhereIsTheTruth »

AbsoluteCabbage wrote: post #23
WalterBright wrote: post #6

If you're doing metaprogramming using the C preprocessor, it's time to move to a more advanced language.

C is still the King of languages.

I agree with that

None of the new languages managed to capture what makes C great

The few "modern" ones are interesting, Zig, Jai and Odin for example, I like how they took C designated initialization to the next level

Zig's comptime is also nice

D is nice, but is loosing its charm now that the competition is here.. also what used to be a D strength now is a weakness; it's slow to compile thanks to the std.. debugging still is a pain, and code can become quite overly verbose

Post reply on HN