4

Learning Rust (yay!) and I'm trying to understand the intended idiomatic programming required for certain iterator patterns, while scoring top performance. Note: not Rust's Iterator trait, just a method I've written accepting a closure and applying it to some data I'm pulling off of disk / out of memory.

I was delighted to see that Rust (+LLVM?) took an iterator I had written for sparse matrix entries, and a closure for doing sparse matrix vector multiplication, written as

iterator.map_edges({ |x, y| dst[y] += src[x] });

and inlined the closure's body in the generated code. It went quite fast. :D

If I create two of these iterators, or use the first a second time (not a correctness issue) each instance slows down quite a lot (about 2x in this case), presumably because the optimizer no longer chooses to do specialization because of the multiple call sites, and you end up doing a function call for each element.

I'm trying to understand if there are idiomatic patterns that keep the pleasant experience above (I like it, at least) without sacrificing the performance. My options seem to be (none satisfying this constraint):

  1. Accept dodgy performance (2x slower is not fatal, but no prizes either).
  2. Ask the user to supply a batch-oriented closure, so acting on an iterator over a small batch of data. This exposes a bit much of the internals of the iterator (the data are compressed nicely, and the user needs to know how to unwrap them, or the iterator needs to stage an unwrapped batch in memory).
  3. Make map_edges generic in a type implementing a hypothetical EdgeMapClosure trait, and ask the user to implement such a type for each closure they want to inline. Not tested, but I would guess this exposes distinct methods to LLVM, each of which get nicely inlined. Downside is that the user has to write their own closure (packing relevant state up, etc).
  4. Horrible hacks, like make distinct methods map_edges0, map_edges1, ... . Or add a generic parameter the programmer can use to make the methods distinct, but which is otherwise ignored.

Non-solutions include "just use for pair in iterator.iter() { /* */ }"; this is prep work for a data/task-parallel platform, and I would like to be able to capture/move these closures to work threads rather than capturing the main thread's execution. Maybe the pattern I should be using is to write the above, put it in a lambda/closure, and ship it around instead?

In a perfect world, it would be great to have a pattern which causes each occurrence of map_edges in the source file to result in different specialized methods in the binary, without forcing the entire project to be optimized at some scary level. I'm coming out of an unpleasant relationship with managed languages and JITs where generics would be the only way (I know of) to get this to happen, but Rust and LLVM seem magical enough that I thought there might be a good way. How do Rust's iterators handle this to inline their closure bodies? Or don't they (they should!)?

3
  • Not sure, but you might give a try to marking your method with #[inline(always)].
    – Levans
    Oct 10, 2014 at 21:48
  • As an update, #[inline(always)] gets the performance back, but probably for the "wrong reason": since the method is inlined into main, the closures can subsequently get inlined too. But, I'm not hoping to inline the iterator in to main (rather, writing library code taking closures as args). Still, neat that it helps, and I'll see if I can exploit that. Thanks! Oct 14, 2014 at 14:58
  • Also, the generic approach, writing map_edges<T>( ..., extra: T), works great but is really unsettlingly gross. Who would I have to pay to support a #[monomorphise_for_constant_arguments] attribute? :D Oct 14, 2014 at 15:00

1 Answer 1

1

It seems that the problem is resolved by Rust's new approach to closures outlined at

http://smallcultfollowing.com/babysteps/blog/2014/11/26/purging-proc/

In short, Option 3 above (make functions generic with respect to a new closure type) is now transparently implemented when you make an implementation generic using the new closure traits. Rust produces the type behind the scenes for you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.