Live data from Hacker News

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

github.com

21–30 of 50 posts

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

#21
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…

>"Not everyone knows there are better ways to do things."

In theory you might be right but I doubt it is applicable in this particular case.

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

#22

Earlier quoted context omitted.

If you want to show cleverness, by all means! I still use some primitive tools, and know there are better alternatives, but I'm not going to defend sticking with them. BTW, I did win the Obfuscated C contest one year, and (naturally) used the preprocessor: https://www.ioccc.org/1986/bright/bright.c

just last night i was thinking how cool it would be for an IDE plugin that expands rust macros for easier grokking. now i need one for your #defines, lol

cargo expand?

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

#24

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 equal to the pivot. This makes most data inputs that result in the O(n^2) worst case of quicksort give O(n) performance instead.

Unfortunately the code is horrific looking. It's not something I'd ever want to do in a C macro.

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

#25
Today I learned that for modern processors, quicksort code is small enough that the compiler can inline them if the definition is visible during compilation. See here for comparison of isort function implemented using plain static functions vs the macro in TFA: https://godbolt.org/z/arGjPGhKE . It's not as flexible as the macro form (not being able to pass two arrays at once like the sortByAge example in TFA), but I figure it should be friendlier to debuggers (though with all the inlining the experience is not going to be that great either).

IIRC, if LTO is enabled the calls to the less and swap functions can also be inlined even if the generic function is compiled to a separate translation unit. Haven't tried it for the quick sort code above, but I found that out for some other thing I experimented with.

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

#26

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 trade-off like anything else in computing.

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

#27

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…

> many problems can be solved without having to invent new language features

You mean something like a type checker?

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

#28

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.

The article is talking code and demonstrating results. Talk is cheap, show the code!

A rote translation of Q_SORT3 would look like:

    /* Sort 3 elements. */
    void Q_SORT3(alias Q_LESS, alias Q_SWAP, Q_UINT) (Q_UINT q_a1, Q_UINT q_a2, Q_UINT q_a3)
    {
        if (Q_LESS(q_a2, q_a1)) {
            if (Q_LESS(q_a3, q_a2))
                Q_SWAP(q_a1, q_a3);
            else {
                Q_SWAP(q_a1, q_a2);
                if (Q_LESS(q_a3, q_a2))
                    Q_SWAP(q_a2, q_a3);
            }
        }
        else if (Q_LESS(q_a3, q_a2)) {
            Q_SWAP(q_a2, q_a3);
            if (Q_LESS(q_a2, q_a1))
                Q_SWAP(q_a1, q_a2);
        }
    }
A D template function is distinguished by having two parameter lists, the compile time parameter list and the runtime parameter list. Q_UINT would be a type parameter with its type inferred from the function arguments. Q_LESS and Q_SWAP are alias parameters, which can be an alias to any symbol or type. This is often used to pass lambdas.

Note that D allows the following ways to pass a parameter:

1. by value

2. by reference

3. by name

4. by type

The alias parameters are "by name". C++ has by name parameters in the form of template template parameters, along with the restriction that such a parameter can only be a template. D allows any symbol or type to be passed by name.

Passing the lambdas by name means a direct function call/inlining rather than an indirect call through a function pointer.

Anyhow, with this example you can see how the rest can be fairly easily translated.

So, you might ask, what's the advantage?

1. name hygiene

2. your debugger will see the symbols

3. no ugly \ line splicing

4. no wacky do-while(0) kludge

5. the names are actual symbols rather than transitory apparitions seen only by the preprocessor

6. color syntax highlighting in your editor works

7. the compiler will check the syntax and give error messages in terms of the symbols, not generated preprocessor text

8. It's not going to conflict with another symbol named Q_SORT

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

#29

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…

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.

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

#30

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.

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.

Post reply on HN