6 ms·

How do you write a generic quicksort function without generics? There are two ways I know of: (1) throw type and memory safety out the window and use void poin

How do you write a generic quicksort function without generics? There are two ways I know of: (1) throw type and memory safety out the window and use void pointers plus size/alignment like qsort(3) does; (2) require that users manually write an interface with a swap(int i, int j) function like Go before generics does. Both solutions are really bad.

joe_guy 5y ago
Void pointers also add an unfortunate layer of dereferencing. In C# for example, generics are important to keep values on the stack instead of the heap, not only avoiding garbage collection but improving data locality.
- pcwalton 5y ago
  Well, a modern optimizing compiler can get rid of the indirection if it inlines qsort() and then inlines the comparison function. Of course, it needs to be able to see the source of qsort() to do so (which might be a problem if it's dynamically linked).
  - joe_guy 5y ago
    If I'm understanding correctly, you're saying a compiler will optimize out "void*" to instead be the value put into it, so theres no pointer dereference to get to it? That's what I am talking about. I don't know much about modern C optimizations.
    - jstimpfle 5y ago
      There isn't any pointer to optimize out really, I don't think - at the machine level, a pointer is a pointer is an integer number regardless of its type at the source code level. What can be measureable though is function call overhead - if you write a sort function that takes a function pointer and your sort function calls that, there is a lot of work for saving the local state, preparing all the arguments for the function, etc. That work can potentially be avoided if the compiler can inline the function call into (a copy of) your sort function.
      - joe_guy 5y ago
        At the machine level there is absolutely a difference. one means your data is right here, the other means the data is elsewhere. That poor data locality can cause cache misses and always consumes extra cycles.
        jstimpfle 5y ago
        What is "right there"? If the computer should sort an array that is located in main memory, it needs to know their addresses (pointers) to even load them. There is no way around.
        joe_guy 5y ago
        It depends on how many times removed it is. Lets say it's 4 8bit ints. It can be sequentially and directly in memory like: stack: [0x01, 0x02, 0x03, 0x03] Each int is directly next to each other in memory. But it could instead be pointers to the ints, like: stack: [0x07002412, 0x0700241A, 0x07002424, 0x070036A0] heap (or stack, really): 0x07002412: 0x01 0x0700241A: 0x02 0x07002424: 0x03 0x070036A0: 0x04 The CPU needs to dereference that pointer, and the cache is getting all screwed up. That is what "void*" is doing. You're using a pointer instead of a value. In C# this is what generics allow you to avoid. // This is like my first memory layout above. struct Foo<T> { public T MyField; } vs: // This is like the second layout above. struct Foo { public object MyField; }
        deleted 5y ago
        [deleted]
      - tsimionescu 5y ago
        In the case of qsort, void* isn't a problem, since sort() would always take a pointer, but there absolutely is a difference at the machine level between void* and int - one is a value, the other is the address of a value. One is used for calculations, the other is used for calculations OR loading data from memory.
    - pcwalton 5y ago
      Among other things, yes, compilers will do that.
      - joe_guy 5y ago
        That seems strange because you'd think you may need the guarantee the pointer remains a pointer for an ABI? Or does it only do this in very limited circumstances? Do you know the term I can use to Google more info about this?
        pcwalton 5y ago
        It only works if you use link-time optimization or the qsort() definition is otherwise available for the compiler to see.
  - mattarm 5y ago
    The similarity of this optimization and what is typically thought of as "generic programming" is interesting.
- deleted 5y ago
  [deleted]
jstimpfle 5y ago
I rarely ever do need a sorting algorithm for what I do. I might not have done even one sort call in 2021. Usually the data I have is sorted by construction, or doesn't need to be sorted in any particular order. When I do need to sort, I just use qsort from libc. It's also easy to write my own version of qsort. I once measured qsort vs std::sort on plain ints (basically the most pessimistic case for qsort vs std::sort) and the difference was like 2x. If this becomes a bottleneck then it's worth investigating how to take advantage of additional context to speed up the sorting much more than any generic sorting algorithm could do anyway. Simple example: bucket sort. (I'm 100% confident sorting performance hasn't ever been noticeable in my career so far, but I've done simple optimizations like that once in a while for fun). > Both solutions are really bad. Due to what I described above, I'm actually in favour of qsort - no new code is generated, just a simple library call that takes a pointer to the comparison function. Really really easy to use.
- dnautics 5y ago
  I don't know what you do, but for our codebase, we run transactions against the database in most of the integration tests. We can't generally be sure the database won't return rows in some order it likes that aren't the rows we expect -- so if we don't have a generic sorting function we will have flaky tests.
  - jstimpfle 5y ago
    If you can't bring the database to return the values in a well defined order, absolutely go ahead and sort it! No need for _generics_ though, qsort() will do just fine. (C probably isn't great for DB interop in any case).
- tsimionescu 5y ago
  qsort is a horrible function, and infamously so. First, since it's part of the C stdlib, it is almost universally dynamically linked, precluding any chance for it to be inlined, and even worse, it calls a function pointer. Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly. For example, I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` and I'll get a really bad time, with absolutely no way for the compiler to tell me I'm doing something obviously wrong.
mpweiher 5y ago
Use Smalltalk?
- travisgriggs 5y ago
  Don't you mean "If you use a late bound language, you don't need to chase down the type rabbit hole and encounter the nasty teeth that are generics along the way"? An example of which is Smalltalk, but could also include Dart 1, Python, Elixir, CLOS/Lisp, JavaScript, etc. Smalltalk is an interesting exhibition of a similar principle though. If you did add types to Smalltalk, you'd likely solve this containment parameterization problem the same way you do nearly everything in Smalltalk: by binding some new behavior (adding a method) to some data (a class object). You'd add a message to the MetaClass types that could create flyweight class types parameterized on the fly. And when you compiled, you'd send messages to the instance of the class itself to manufacture that synthetic on-the-fly type. Hand wave, hand wave, hand wave. The "let's see where naval gazing on a unifying principle goes?" that is employed in Zig is to use the same language itself to recurse on itself when defining itself, types included. What happens in more traditional/mainstream/Algol derived languages, is that each part of the system gets a sort of sub department of the language. You have a set of keywords/syntax for expressing run time behavior. And then someone says, but how do actually bring data to life--a sort of "Creatio ex nihilo" problem--and the answer is we need a new department in the language, so we get keywords/syntax for constructors. When behavior/construction needs to be parameterized across compilation paths, we get another set of keywords/syntax. And another for type definition. And yet another for scope management. And then again with meta things. And maybe a preprocessor. I do think there's a trick to finding a sweet spot in these "turtles all the way down" systems. In Smalltalk, I was happy with how the "don't know what's going on? just follow the message sends", but at the same time still providing enough structure/composition to have to be reflecting/introspecting all the time. Forth is event simpler, but I found I had to constant recompile things in my head to resolve. I'm relatively new on the Elixir curve, and am beginning to worry this happens with macros there. Figuring out how Plug works really messes with my brain. I haven't done enough with Zig to know where it's @comptime ends up in this balance.
deleted 5y ago
[deleted]

joe_guy 5y ago

Void pointers also add an unfortunate layer of dereferencing. In C# for example, generics are important to keep values on the stack instead of the heap, not only avoiding garbage collection but improving data locality.

pcwalton 5y ago
Well, a modern optimizing compiler can get rid of the indirection if it inlines qsort() and then inlines the comparison function. Of course, it needs to be able to see the source of qsort() to do so (which might be a problem if it's dynamically linked).
- joe_guy 5y ago
  If I'm understanding correctly, you're saying a compiler will optimize out "void*" to instead be the value put into it, so theres no pointer dereference to get to it? That's what I am talking about. I don't know much about modern C optimizations.
  - jstimpfle 5y ago
    There isn't any pointer to optimize out really, I don't think - at the machine level, a pointer is a pointer is an integer number regardless of its type at the source code level. What can be measureable though is function call overhead - if you write a sort function that takes a function pointer and your sort function calls that, there is a lot of work for saving the local state, preparing all the arguments for the function, etc. That work can potentially be avoided if the compiler can inline the function call into (a copy of) your sort function.
    - joe_guy 5y ago
      At the machine level there is absolutely a difference. one means your data is right here, the other means the data is elsewhere. That poor data locality can cause cache misses and always consumes extra cycles.
      - jstimpfle 5y ago
        What is "right there"? If the computer should sort an array that is located in main memory, it needs to know their addresses (pointers) to even load them. There is no way around.
        joe_guy 5y ago
        It depends on how many times removed it is. Lets say it's 4 8bit ints. It can be sequentially and directly in memory like: stack: [0x01, 0x02, 0x03, 0x03] Each int is directly next to each other in memory. But it could instead be pointers to the ints, like: stack: [0x07002412, 0x0700241A, 0x07002424, 0x070036A0] heap (or stack, really): 0x07002412: 0x01 0x0700241A: 0x02 0x07002424: 0x03 0x070036A0: 0x04 The CPU needs to dereference that pointer, and the cache is getting all screwed up. That is what "void*" is doing. You're using a pointer instead of a value. In C# this is what generics allow you to avoid. // This is like my first memory layout above. struct Foo<T> { public T MyField; } vs: // This is like the second layout above. struct Foo { public object MyField; }
        deleted 5y ago
        [deleted]
    - tsimionescu 5y ago
      In the case of qsort, void* isn't a problem, since sort() would always take a pointer, but there absolutely is a difference at the machine level between void* and int - one is a value, the other is the address of a value. One is used for calculations, the other is used for calculations OR loading data from memory.
  - pcwalton 5y ago
    Among other things, yes, compilers will do that.
    - joe_guy 5y ago
      That seems strange because you'd think you may need the guarantee the pointer remains a pointer for an ABI? Or does it only do this in very limited circumstances? Do you know the term I can use to Google more info about this?
      - pcwalton 5y ago
        It only works if you use link-time optimization or the qsort() definition is otherwise available for the compiler to see.
- mattarm 5y ago
  The similarity of this optimization and what is typically thought of as "generic programming" is interesting.
deleted 5y ago
[deleted]

jstimpfle 5y ago

I rarely ever do need a sorting algorithm for what I do. I might not have done even one sort call in 2021. Usually the data I have is sorted by construction, or doesn't need to be sorted in any particular order. When I do need to sort, I just use qsort from libc. It's also easy to write my own version of qsort. I once measured qsort vs std::sort on plain ints (basically the most pessimistic case for qsort vs std::sort) and the difference was like 2x. If this becomes a bottleneck then it's worth investigating how to take advantage of additional context to speed up the sorting much more than any generic sorting algorithm could do anyway. Simple example: bucket sort. (I'm 100% confident sorting performance hasn't ever been noticeable in my career so far, but I've done simple optimizations like that once in a while for fun). > Both solutions are really bad. Due to what I described above, I'm actually in favour of qsort - no new code is generated, just a simple library call that takes a pointer to the comparison function. Really really easy to use.

dnautics 5y ago
I don't know what you do, but for our codebase, we run transactions against the database in most of the integration tests. We can't generally be sure the database won't return rows in some order it likes that aren't the rows we expect -- so if we don't have a generic sorting function we will have flaky tests.
- jstimpfle 5y ago
  If you can't bring the database to return the values in a well defined order, absolutely go ahead and sort it! No need for _generics_ though, qsort() will do just fine. (C probably isn't great for DB interop in any case).
tsimionescu 5y ago
qsort is a horrible function, and infamously so. First, since it's part of the C stdlib, it is almost universally dynamically linked, precluding any chance for it to be inlined, and even worse, it calls a function pointer. Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly. For example, I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` and I'll get a really bad time, with absolutely no way for the compiler to tell me I'm doing something obviously wrong.

mpweiher 5y ago

Use Smalltalk?

travisgriggs 5y ago
Don't you mean "If you use a late bound language, you don't need to chase down the type rabbit hole and encounter the nasty teeth that are generics along the way"? An example of which is Smalltalk, but could also include Dart 1, Python, Elixir, CLOS/Lisp, JavaScript, etc. Smalltalk is an interesting exhibition of a similar principle though. If you did add types to Smalltalk, you'd likely solve this containment parameterization problem the same way you do nearly everything in Smalltalk: by binding some new behavior (adding a method) to some data (a class object). You'd add a message to the MetaClass types that could create flyweight class types parameterized on the fly. And when you compiled, you'd send messages to the instance of the class itself to manufacture that synthetic on-the-fly type. Hand wave, hand wave, hand wave. The "let's see where naval gazing on a unifying principle goes?" that is employed in Zig is to use the same language itself to recurse on itself when defining itself, types included. What happens in more traditional/mainstream/Algol derived languages, is that each part of the system gets a sort of sub department of the language. You have a set of keywords/syntax for expressing run time behavior. And then someone says, but how do actually bring data to life--a sort of "Creatio ex nihilo" problem--and the answer is we need a new department in the language, so we get keywords/syntax for constructors. When behavior/construction needs to be parameterized across compilation paths, we get another set of keywords/syntax. And another for type definition. And yet another for scope management. And then again with meta things. And maybe a preprocessor. I do think there's a trick to finding a sweet spot in these "turtles all the way down" systems. In Smalltalk, I was happy with how the "don't know what's going on? just follow the message sends", but at the same time still providing enough structure/composition to have to be reflecting/introspecting all the time. Forth is event simpler, but I found I had to constant recompile things in my head to resolve. I'm relatively new on the Elixir curve, and am beginning to worry this happens with macros there. Figuring out how Plug works really messes with my brain. I haven't done enough with Zig to know where it's @comptime ends up in this balance.

deleted 5y ago

[deleted]