Pure annotation for stateless functions

language design
21

If optimizations have such effects on your code then it most likely has UB, but here we're talking about completely safe Rust code.

22

Yes you will need to keep track of potentially diverging code paths, but if all relevant operatons are pure you don't need to worry about the order of them (even if some potentially diverge!). Since if they are pure, they can't have side-effects, by definition. This means starting a panic isn't pure (due to the panic hook and that it unwinds the stack, which is typically considered impure). And I don't think pure/diverge can get the same optimizations are just pure, while it is interesting.

23

The counterexample I believe is that the way the compiler does code deduplication you can end up with backtraces that print the names of functions that you never called, because they were deduplicated with a function that you did call. As far as I know this still happens in safe rust.

1 Like
24

Is any work performed or research on the topic of more strict function definitions? I'm not praying for something so beautiful as in Koka, but at least something... Heck even Haskell pure functions would do. :slight_smile: Well, in the meantime I'm trying to use const fns. Looking for references... Thanks!

25

I'm not talking about code with UB. And I'd like to note that the original function under discussion to be "pure" is an x + 1 function which contains a panic. In any case I am imagining an optimization mode that would permit e.g.:

#[allow(arithmetic_overflow)]
let (a, b) = (2, 3);
let x = a + usize::MAX;
let y = b + usize::MAX; // <- panics here! The optimizer did some reordering.

Perhaps only certain instances of panic would be allowed to be reordered. Perhaps the only guarantee would be that a single thread of execution which panics will, after optimization, still panic. I imagine that with enough pure functions in one place (many math routines), and some inlining, the resulting panic could easily be confusingly late within a function. I would probably still be enabling such an optimization.

26

I don't think pureness would be enough for this optimization though, you would also need the compiler to prove that the statements that are executed after the panic are free from UB.

27

I wonder if adding something like a concurrent { ... } block that explicitly opts-in to arbitrary reordering would be more palatable. The block is guaranteed to have the same return value (divergent or otherwise) as if it had been executed straight-through, but no guarantees are provided regarding what order side effects happen in (or, for a diverging block, which side effects happen at all).

When combining such a block with unsafe, it is the programmer's responsibility to make sure that potential UB has either been guarded against before entering the concurrent section at all, or within some construct that guarantees in-order execution within the concurrent block. The exact specification for these constructs is TBD, but would at a minimum include the internal details of individual function calls (whether inlined or not).

Early returns from within a concurrent block are another interesting question. I can certainly imagine scenarios where there are a lot of ? operators, and I don't really care which error case gets returned as long as returning from the block means that all of the checks passed.

3 Likes
28

I am a little bit lost in the discussion. Let me summarize based on my understanding.

The first question is:

Should the compiler take the responsibility to handle cases in the example?

  1. If the compiler should handle the case without user awareness

    The unwind mechanism may prevent this. I'm not expert on this, so correct me if it's not.

  2. If users need to explicit add some annotations

    There are two closely-related questions:

    2.1. Should we add some rules to check the correctness of such annotation?

    2.2. Should the annotation be unsafe?

    If the annotation must be unsafe, then I don't think the compiler should add additional rules to check the correctness (maybe just some simple rules in clippy).

    If the annotation can be safe, then we need to carefully design rules about the behavior of diverging calls.

    However, as I mentioned in the post, in certain situations, there are some other non-pure functions, such as log::info, should not interfere with the purity deduction of the caller function. Only considering diverging calls may not be sufficient enough to make it more general.

Personally speaking, there are two approaches that I prefer:

  • Simply introduce #[unsafe(pure)] annotation to indicate the function can be treated as a pure function, which can be used for sub-expression elimination

    The advantage of this approach is simplicity, but it easier for developers to make mistakes, and this annotation is required in every "pure-or-diverging" functions, which is very common, thus may be a distraction for graceful coding.

  • Add some complex rules to make compiler implicitly infer the purity of those "pure-or-diverging" functions, and add #[unsafe(pure)] annotations for extending the optimization for functions that contain logging or something else.

    The advantage of this approach is that the annotation is not needed in a vast number of functions. However, as I said before, I'm not an expert on the unwind mechanism, so I don't know if we can actually come up with such rules that are sound enough.

P.S. I don't care if we don't use the name pure, just bikeshed it.

29

I'd really like to find a way to have a "pretend this function has no side effects" annotation, and maybe also "pretend this callsite has no side effects". I mainly want them to reduce how much code generation is perturbed when you add debugging printouts and the like, but it also occurs to me that the concept (maybe not exactly the same) might help us grapple with the paradoxes associated with optimizing out unnecessary resource allocations, that @RalfJung occasionally talks about.

There is a nasty catch, though. Consider the trivial case

#[unsafe(does_not_make_caller_impure)]
fn debug_println(args: &std::fmt::Arguments<'_>);

fn wadd(u32 a, u32 b)
{
    u32 rv = a.wrapping_add(b);
    debug_println(format_args!("{} +_w {} = {}", a, b, rv);
    rv
}

The programmer's intent is that calls to wadd should be optimized as-if it were truly a pure function. But each actual call to wadd still needs to cause a call to debug_println, which means that that call cannot be treated as a call to a pure function! This feels like it might be too slippery of a property to expect compilers to preserveo.

30

Printing to stdout or writing to a file is definitely a side-effect, so doing that in a function marked as "no side-effects" would be insta-UB. So this sounds like a bad motivation for such an annotation. What you are asking for is an entirely different feature with no existing proper foundations that I am aware of, unlike "purity" in its usual form which is widely-studied.

EDIT: Ah, you actually hint at that problem in the 2nd half of your post. I missed that, sorry.

Panics are definitely impure. This can be shown with a simple test: for pure functions f() and g(), the following two blocks are equivalent:

{
  let x = f();
  println!("---");
  let y = g();
  (x, y)
}

and

{
  let y = g();
  println!("---");
  let x = f();
  (x, y)
}

Obviously, if f panics, the two blocks are not equivalent. Therefore, panicking is not pure.

The same test also shows that f is impure if it has an infinite loop.

Some people think that Haskell is a pure functional programming languages, and therefore everything you can do in Haskell is pure -- that is unfortunately a widespread misconception. Haskell is an impure programming language, having two effects built-in: exceptions and divergence.

Functions that have only the effects of exceptions and divergence are still interesting, but those effects cannot just be ignored.

2 Likes
31

I don't think this works because purity does not imply a function is total. So, for any pure and total function, yes, your test works. But if f or g diverge, then I don't think you can conclude anything from your test.

I dug around, but I couldn't find anything that requires pure functions to be total. And from totality doesn't follow from the definition of pure functions: a referentially transparent function with no side-effects. (I guess, unless you consider potential nontermination to be a side-effect, I couldn't find any sources that do this, and I found sources that said that nontermination is not a side-effect on its own.)

32

Hm, I think you are using the term "total function" for what I would call a "pure function". Wikipedia lists "the function has no side effects" as requirement for a pure function, and in PL theory, both throwing an exception and looping indefinitely are typically considered side-effects (precisely because they break equational reasoning of the form my example is based on).

But maybe there's so few functions that are fully pure that it's not worth having an annotation for that.

1 Like
33

I feel like this discussion is getting side tracked into definitions instead of trying to find a sound way to allow certain optimisations users want.

As I stated early in the thread: Could we not have a different concept, that allow some of the same optimisations? Lets for the sake of discussion call it "deterministic partial bikeshed function" (but if this concept has a proper name, I'm all ears):

  • The function only observe parameters (possibly following references in said parameters)
  • No non-locals are written to.
  • No globals (except constants) are read.
  • Doesn't allocate heap memory that escapes the function.
  • For any given input, the return value is deterministic: Same input -> same output.
  • The function may (deterministically) for some inputs diverge (not return). This may happen via panic or loop {} etc.

Given that a function f is one of these, it should be sound to optimise:

let a = f(123);
let b = f(123);

into

let a = f(123);
let b = a;

(The syntax is assuming a is of a Copy type here, but you could adjust it as needed for other cases.)

Why should this be sound in this case? There are two scenarios given the definition above:

  • f(123) returns a value. It is always the same (f behaves as if it is pure on this input), so the optimisation is trivially correct.
  • f(123) panics or loops forever every time it is called with this input. It would never had reached the second invocation, since it is guaranteed to diverge on the first invocation. We cannot observe the de-duplication.

This specifically allows for the panic case. It would not allow for arbitrary side effects (e.g. logging). I don't see a way to soundly allow for that.

Is this an optimisation that is worth pursuing though? I don't know how common this is, but here are some std functions that would fall into this class:

That was just looking for 5 minutes at the primitives, I would not be surprised if there are more functions elsewhere like this.

2 Likes
34

I think a lot of the simpler cases can be handled by compiler analysis to infer these attribute, especially some of the std functions you showed. I think that is the better approach to persue than adding random optimization attributes with little formal backing.

3 Likes
35

I absolutely agree that this is something the compiler should infer automatically itself (just as it apparently infers pure functions today). The questions that remain are really:

  • How common are these functions?
  • How common are code patterns where these functions can be optimised? A lot of redundant code can show up after inlining and other optimisations have had a go at simplifying the code of course.
  • What optimisations exactly are enabled by this? (Presumably not quite as many as with pure functions.)
  • How much can be gained? Vs. How difficult is it to implement and maintain?

As a user of Rust (rather than a rustc developer) these are not questions I'm capable of answering.

36

I wish compilers would use a more relaxed a definition of program equivalence in the presence of exceptions, which would allow for such reordering. Or, at least, provide an option to opt out of the strict definition. Most people do not care whether f or g has panicked first, only that a panic has happened and why.

The current strict definition often prevents the compiler from applying optimizations such as autovectorization. Relaxing the definition may make debugging of panics slightly harder, but on the other hand it should produce a more efficient code "for free" without sprinkling experience-driven asserts in random places.

2 Likes
37

That was just looking for 5 minutes at the primitives, I would not be surprised if there are more functions elsewhere like this.

Things get worse if some heavy functions calls panic, such as sha2 invokes copy_from_slice, petgraph's graph algo takes index that may panic. If users use a seemingly "pure" encapsulation over those heavy functions, it is still not considered pure by rust compiler.

BTW, as Vec::push may also panic, a pure function that manipulates a local vec is not considered pure as well, this may definitely involve a lot of "seemly pure" functions. (Will Vec::new panic? I don't remember well about the rules of global allocator what will happen if there are no more space)

1 Like
38

Note that in practice sha2 is completely panic-free with enabled optimizations. It's a classical problem with proposals to add a no_panic annotation. Non-trivial functions can be written in a panic-free fashion, but only accounting for optimization passes.

Naive no_panic proposals which do not rely on compiler optimizations are borderline useless in practice since they quickly stop working outside of extremely trivial examples. On the other hand, it's hard to create an annotation which relies on optimizations, especially considering that optimization passes may become "broken" (i.e. no longer eliminate all panics) depending on compiler version, compilation flags (e.g. lto and codegen-units), or compilation target.

2 Likes
39

You also need to rule out the function doing any kind of syscall, such as printing to stdout -- otherwise, your transformation obviously changes program behavior.

OTOH, you do not actually need the function to be deterministic. Your proposed transformation reduces the number of times f is called; this is fine to do even for non-deterministic functions: a and b getting the same value was a possibility all along, so we can refine the program to commit to that possibility.

It's not about who paniced why, it's about which code even runs. If f panics but g does not, then the transformed program suddenly prints --- when the original program did not. In other words, the transformed program executed what was previous dead code.

I see no way that compilers could possibly relax program equivalence here while remaining useful. Executing dead code completely violates any kind of reasoning about the program.

40

If only there was a builtin way [1] to get rustc to print a warning (opt-in) if this happens (after optimizations are applied [2]), without failing the compilation ... #[cfg_attr(not(debug_assertions), warn(panic))] ... perhaps with a simpler to remember alias if it is used often ... #[warn_panic_release], #[warn_panic].

With that you could do something like the following to get a warning on all everything, except specific functions [3]:

#[warn_panic_release]
mod foo {
    fn bar() {}
    #[allow(panic)]
    fn baz() {}
}

  1. Yes, I know that the no_panic crate exists, see my note about not failing the compilation (esp. if a dependency introduces a new panic path, which as far as I know isn't considered a breaking change by many). ↩ī¸Ž

  2. Granted: That probably has to work similar to the no_panic crate as that likely needs to happen after LLVM optimizes the code. Therefore I don't know how difficult such a warning would be to implement (probably harder than expected) ↩ī¸Ž

  3. This would also allow you (esp. if possible on the entire crate) to get a list of all functions that can panic, potentially even with the information whether this depends on optimizations (and which ones) if built in release mode. Since the panic message contains the location in the code (and thus two panic paths are distinct) it could even list the exact location within a function that was considered reachable after optimizations, something no_panic doesn't do iirc. ↩ī¸Ž