Appreciable compilation slowdown with Sync + Send markers

[llogiq]

Well, of course the compiler has to do a lot more work when so many types implement the method.

[DenisKolodin]

compiler has to do a lot more work when so many types implement the method

What do you mean? next is a method of my trait, in the earlier example I bound generic with a trait without any implementation. It also has a different declaration in comparsion with other next methods of std traits.

Why I can’t use next name for method of own trait?

[nikomatsakis]

Not to defend the compiler’s performance in this case, but in general when we see a call like foo.next(..) we do not know what trait the method next belongs to, and we have to figure it out by examining what traits foo implements. Still, I suspect we’ll be able to improve things here quite a bit.

[DenisKolodin]

in general when we see a call like foo.next(…) we do not know what trait the method next belongs to, and we have to figure it out by examining what traits foo implements

For which reason this approach is used? Why trait’s names don’t take into consideration? I don’t see duck typing feature. Traits ignoring seems to me strange.

Is there a list of never to do things for Rust like Python has: “no cpu-bound tasks because of GIL”?

[arielb1]

@DenisKolodin

If you could give a code example demonstrating the slowdown, I will try to track it down.

[DenisKolodin]

@arielb1 Here it is:

extern crate mongodb;
use mongodb::coll::Collection;

pub trait Worker {
    fn next(&mut self);
}

impl<F> Worker for F where F: FnMut(), F: Sync + Send {
    fn next(&mut self) { self() }
}

pub struct GetRecord {
	collection: Collection,
}

impl Worker for GetRecord {
	fn next(&mut self) {
		let mut cursor = self.collection.find(None, None).unwrap();
		let _ = cursor.next();
	}
}

fn main() {
}

[arielb1]

An example without external deps would have been nicer.

[DenisKolodin]

I regret that I can’t reproduce slowdown without the dependecy. I think because it also has the next method.

May be useful: I use cargo in verbose mode to get rustc command with arguments to call it under debugger later with dependencies (especially when there are a lot of them).

[arielb1]

It looks like winnowing could use some memoization. There is a different O(2^n) issue that involves projections, but it doesn’t look like the problem here.

[arielb1]

struct S0<T>(T,T);
struct S1<T>(Box<S0<T>>,Box<S0<T>>);
struct S2<T>(Box<S1<T>>,Box<S1<T>>);
struct S3<T>(Box<S2<T>>,Box<S2<T>>);
struct S4<T>(Box<S3<T>>,Box<S3<T>>);
struct S5<T>(Box<S4<T>>,Box<S4<T>>);
struct S6<T>(Box<S5<T>>,Box<S5<T>>);
struct S7<T>(Box<S6<T>>,Box<S6<T>>);
struct S8<T>(Box<S7<T>>,Box<S7<T>>);
struct S9<T>(Box<S8<T>>,Box<S8<T>>);
struct Sa<T>(Box<S9<T>>,Box<S9<T>>);
struct Sb<T>(Box<Sa<T>>,Box<Sa<T>>);
struct Sc<T>(Box<Sb<T>>,Box<Sb<T>>);
struct Sd<T>(Box<Sc<T>>,Box<Sc<T>>);
struct Se<T>(Box<Sd<T>>,Box<Sd<T>>);
struct Sf<T>(Box<Se<T>>,Box<Se<T>>);

trait Foo { fn xxx(&self); }
trait Bar {} // anything local or #[fundamental]

impl<T> Foo for T where T: Bar, T: Sync {
    fn xxx(&self) {}
}

impl Foo for Sf<u32> { fn xxx(&self) {} }

fn main() {
    let _ = <Sf<u32>>::xxx;
}

[arielb1]

struct S0<T>(T,T);
struct S1<T>(Box<S0<T>>,Box<S0<T>>);
struct S2<T>(Box<S1<T>>,Box<S1<T>>);
struct S3<T>(Box<S2<T>>,Box<S2<T>>);
struct S4<T>(Box<S3<T>>,Box<S3<T>>);
struct S5<T>(Box<S4<T>>,Box<S4<T>>);
struct S6<T>(Box<S5<T>>,Box<S5<T>>);
struct S7<T>(Box<S6<T>>,Box<S6<T>>);
struct S8<T>(Box<S7<T>>,Box<S7<T>>);
struct S9<T>(Box<S8<T>>,Box<S8<T>>);
struct Sa<T>(Box<S9<T>>,Box<S9<T>>);
struct Sb<T>(Box<Sa<T>>,Box<Sa<T>>);
struct Sc<T>(Box<Sb<T>>,Box<Sb<T>>);
struct Sd<T>(Box<Sc<T>>,Box<Sc<T>>);
struct Se<T>(Box<Sd<T>>,Box<Sd<T>>);
struct Sf<T>(Box<Se<T>>,Box<Se<T>>);

trait Foo { fn xxx(&self); }
trait Bar {} // anything local or #[fundamental]

impl<T> Foo for T where T: Bar, T: Sync {
    fn xxx(&self) {}
}

impl Foo for Se<u32> { fn xxx(&self) {} }

fn main() {
    let _ = <Se<u32>>::xxx;
}

[DenisKolodin]

Cool example!

playpen: timeout triggered!

It looks like winnowing could use some memoization. There is a different O(2^n) issue that involves projections, but it doesn’t look like the problem here.

Could you help me to find it in the rustc sources? Which functions I have to track?

I’m interesting to see how it works internally.

[arielb1]

It is somewhat subtle - but the sources are at src/librustc/middle/traits. I would prefer @nikomatsakis to help me with that.

[huon]

I ran @arielb1’s example with perf record --call-graph dwarf rustc ..., and then perf report indicates that 60+% of the compilation time is spent in (demangled) middle::traits::select::SelectionContext<...>::confirm_candidate and its descendants. (Any C/C++ profiler should work for this task, e.g. perf on Linux or Instruments.app on OSX)

(The crate name isn’t included in the symbols but the rest of the path is usually more than enough, e.g. the middle module is in the rustc crate, and even without that info, using grep and/or DXR’s search for the method name works well.)

[arielb1]

@huon

This is a case of O(2^n). I know what the issue is, at least in my minified case.

[huon]

That’s great and I hope your knowledge helps improve performance, however my comment was directed to @DenisKolodin, providing some (hopefully reusable) tips/tools for poking around in the compiler.

[DenisKolodin]

I ran @arielb1’s example with perf record --call-graph dwarf rustc …, and then perf report indicates that 60+% of the compilation time is spent in (demangled)

Thank you! It’s very useful to me. Also I’ve never listen about DXR before

@huon could you prompt me the handy tool to explore how Rust compiler works inside? I use GDB in terminal, but it’s hard to steps through the code. Internal data exploration is tangled. What tool do you use to work with running code? I dream about something like Visual Studio But I admit that another tools can also be handy.

[huon]

I’m not sure the best way to track that sort of thing. Personally I use the logging statements that are inside it, e.g. RUST_LOG=rustc::middle::traits rustc ... will cause debug! and info! statements inside that module to print during that invocation. I believe getting debug! statements to print requires compiling a compiler manually, passing --enable-debug-assertions to ./configure. (The compiler’s RUST_LOG is similar to that in the external env_logger crate, but possibly not 100% identical.)

gdb will also work better if you build the compiler yourself and pass --enable-debuginfo to ./configure. I believe one can pass both --enable-debug-assertions and --enable-debuginfo with the --enable-debug flag, but you’ll probably want to also pass --enable-optimize to avoid getting a horribly slow compiler. Also, there’s been some unreliabilities with using a debugger on the compiler (and/or with building a compiler for a debugger) in the past, which may still exist.

(./configure accepts --help, so you don’t have to remember all the details about the various flags.)

[DenisKolodin]

I had no idea that there are more debug options! Thanks for your tips. It’s useful to me.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.