Hacker News Reader

Comment by tedunangst | Hacker News Reader

Now call qsort with a closure.

qsort(3) or even ftw(3) is the simple case. You can either dynamically generate trampoline code with exactly bounded dynamic scope (and even do the gcc-style executable stack hack) or simply stash the whole context in some TLS region and completely sidestep the whole issue.

Side point: ftw(3) is much more interesting unix API to call from some FFI layer than qsort(3). And I spent about a year pestering people from Sun with you should implement fts_open(3) and friends because it presents more sane API for FFIs for the same functionality.

And it appears that you succeeded. Awesome!

It seems Solaris has been adding many BSD and, especially, Linux compatibility APIs lately. It seems too little, too late; or perhaps the initiative is part of their effort to EoL Solaris, providing an upgrade path to Linux.

Well in fact I gave up about 10 years ago :)

`void ()(void, everything_else)` is in my personal experience a much more common API than that of `qsort` (probably for exactly the point you're pedantically trying to make), so I chose to focus on that API for this article.

There's really no reason to pass a rust closure to `qsort` instead of sorting in Rust. That said, if there's demand for real world use cases that require passing Rust closures to C APIs that take only a function pointer and not a data pointer, I'll be happy to write a follow up.

XSetErrorHandler for instance.

signal, sigaction.

In any decent language, all functions are first-class, so if you want to use them as callbacks, you need that to work.

That's still true even if the API takes a separate context pointer that is given to your function as an argument.

There is still a function pointer there, and what you'd like to use as a function pointer is a function in your local language, and that's an object with an environment. Even if some instances of it have no environment, the FFI mechanism might want to tack on its own. For instance, the FFI needs to be able to route the callback to the appropriate function. Whatever function pointer FFI gives to the C function, when the C library calls that function, FFI has to dispatch it back to the original high level function. That requires context. Now that context could be shoehorned into that context parameter, but it could be inconvenient to do so; that parameter belongs to the program and to the conversation that program is having with the C API.

Generating native function pointers on the fly:

- is inherently slow, because CPUs have separate data and instruction caches;

- is extra slow in practice because you need a separate allocation for executable memory (unless your stacks and heap are RWX, which is a terrible idea);

- is not portable, requiring architecture- and OS-specific code; and

- is not supported at all in many environments (of varying levels of braindeadness).

For a statically compiled language like Rust, it makes much more sense to use the context pointer.

I don't think qsort changes anything about the mechanism described in the blog post, but maybe I'm missing something. (I.e., use qsort_r...)

(qsort is really only for C. Other languages can potentially inline the comparison function, so using FFI for that is kind of insane.)

Gets me thinking: I wonder how good Intel CPUs are with dealing with this sort of thing. Can the CPU detect repeated jumps to comparators and in-line them from there? I’d be interested to see a comparative benchmark.

Use `qsort_r()`, which gives you an extra argument for your closure.

If a Rust closure doesn’t actually close over any variables, it can be coerced to a function pointer. Otherwise, you’re stuck with the workarounds others have mentioned.

I’m sure we could have rustc generate a trampoline function directly on the stack like gcc can. What could go wrong?

Nothing, if your Rust implementation is bug-free ;)

Just stash the data in a stack in thread local storage.

Problem solved.

Then it wouldn't be a lexical closure.

It can be from the perspective of the calling code.

Roughly speaking:

  thread_local! {
    static CBQ: Option<Box<impl FnMut(i32, i32) -> i32>>;
  }

  #[no_mangle]
  extern "C" fn qsort(array: *mut i32, val: usize, callback: impl FnMut(i32, i32) -> i32);

  pub fn rust_qsort(array : Vec<i32>, callback: impl FnMut(i32, i32) -> i32){
    CBQ.replace(Box::new(callback)).unwrap_none();
    
    unsafe {
        qsort(array.as_mut_ptr(), array.len(), &rust_qsort_callback);
    }
    
    CBQ.take().unwrap();
  }

  fn rust_qsort_callback(a: *mut i32, b: *mut i32) -> i32 {
    let callback = CBQ.take().unwrap();

    let (a, b) = unsafe { 
        (*a, *b)
    };

    let result = callback(a, b);
    
    CBQ.replace(callback).unwrap_none();

    result
  }

  fn main() {
    let a = vec![4,5,6,3,2];

    rust_qsort(a, |a, b| {
        if a < b {
            -1
        } else if a > b {
            1
        } else {
            0
        }
    })
  }

ought to work. (There's some fun with generics and panics, which is some fun to solve, but nothing which breaks the premise above).

This fails horribly if called recursively (or from a signal handler). You need something like:

  wrapped_qsort(/* array,callback */)
    {
    auto tmp = CBQ;
    CBQ = wrap(callback);
    qsort(array.ptr,array.len,cbq_callback);
    CBQ = tmp; /* pop old value from stack */
    }

It'll fail from a signal handler inside qsort, or inside the callback function.

It won't fail recursively - while the second call is happening, the first will be stored on the stack (see the take and replace in the callback shim function)

Your `fn rust_qsort` takes ownership of the vector, so it frees its memory after sorting and it can't be used after sorting in the caller function. And generic `impl FnMut` won't work in `extern "C"`, it only accepts function pointers.

you have reinvented dynamic scoping :).

  This is the TXR Lisp interactive listener of TXR 228.
  Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet.
  1> (with-dyn-lib nil
      (deffi qsort "qsort" void ((ptr (array wstr)) size-t size-t closure))
      (deffi-cb qsort-cb int ((ptr wstr-d) (ptr wstr-d))))
  #:lib-0005
  2> (let ((vec #("the" "quick" "brown" "fox"
                  "jumped" "over" "the" "lazy" "dogs")))
       (prinl vec)
       (qsort vec (length vec) (sizeof wstr)
              [qsort-cb (lambda (a b) (cmp-str a b))])
       (prinl vec))
  #("the" "quick" "brown" "fox" "jumped" "over" "the" "lazy" "dogs")
  #("brown" "dogs" "fox" "jumped" "lazy" "over" "quick" "the" "the")
  #("brown" "dogs" "fox" "jumped" "lazy" "over" "quick" "the" "the")

The lambda is pointless; we could create the FFI closure directly from cmp-str with [qsort-cb cmp-str]. It shows more clearly that we can use any closure.

Reply on news.ycombinator.com