incr.comp.: Speed up result hashing and DepNode computation by caching certain stable hashes

[michaelwoerister]

Incremental compilation often spends quite a bit of time computing stable hashes of various things. Profiling shows that a large part of this time is spent hashing AdtDef and Substs ty::Slice values. In both cases it is likely that the same values are hashed over and over again. It's worth investigating whether doing some caching here, as we do for macro expansion contexts, is viable and brings speed ups.

[wesleywiser]

I'd like to take this. Is there a good test case I can use to measure the speedup?

[michaelwoerister]

Great, thank you @wesleywiser!

You should see speedups in all incremental builds. In debug builds they should be more pronounced. In builds with an empty cache the absolute compile time difference should be greater because those builds have to do the most result hashing. In builds with a full cache there should also be a speedup but it might be small. Result hashes are loaded from disk in this case but the compiler still needs to hash types when constructing DepNode UUIDs.

I also recommend that just do the implementation and, when it works, open a PR. Then we'll let @bors do a try-build and run that through perf.rlo. That will give us a broader idea of the performance impact.

The two implementations that need updating are:

rust/src/librustc/ich/impls_ty.rs

Lines 23 to 31 in 619ced0

	impl<'gcx, T> HashStable<StableHashingContext<'gcx>>
	for &'gcx ty::Slice<T>
	where T: HashStable<StableHashingContext<'gcx>> {
	fn hash_stable<W: StableHasherResult>(&self,
	hcx: &mut StableHashingContext<'gcx>,
	hasher: &mut StableHasher<W>) {
	(&self[..]).hash_stable(hcx, hasher);
	}
	}

and:

rust/src/librustc/ty/mod.rs

Lines 1475 to 1491 in 619ced0

	impl<'gcx> HashStable<StableHashingContext<'gcx>> for AdtDef {
	fn hash_stable<W: StableHasherResult>(&self,
	hcx: &mut StableHashingContext<'gcx>,
	hasher: &mut StableHasher<W>) {
	let ty::AdtDef {
	did,
	ref variants,
	ref flags,
	ref repr,
	} = *self;
	did.hash_stable(hcx, hasher);
	variants.hash_stable(hcx, hasher);
	flags.hash_stable(hcx, hasher);
	repr.hash_stable(hcx, hasher);
	}
	}

The nice thing about these interned data structures is we can use their memory address as hashmap key. I suggest you get the address like this:

impl<'gcx> HashStable<StableHashingContext<'gcx>> for AdtDef {
    fn hash_stable<W: StableHasherResult>(&self,
                                          hcx: &mut StableHashingContext<'gcx>,
                                          hasher: &mut StableHasher<W>) {
        let cache_key = self as *const AdtDef as usize;
        ...
    }
}

The rest should look very similar to the implementation for expansion contexts:

rust/src/librustc/ich/hcx.rs

Lines 357 to 380 in 2e33c89

	// Since the same expansion context is usually referenced many
	// times, we cache a stable hash of it and hash that instead of
	// recursing every time.
	thread_local! {
	static CACHE: RefCell<FxHashMap<hygiene::Mark, u64>> =
	RefCell::new(FxHashMap());
	}
	let sub_hash: u64 = CACHE.with(|cache| {
	let mark = span.ctxt.outer();
	if let Some(&sub_hash) = cache.borrow().get(&mark) {
	return sub_hash;
	}
	let mut hasher = StableHasher::new();
	mark.expn_info().hash_stable(hcx, &mut hasher);
	let sub_hash: Fingerprint = hasher.finish();
	let sub_hash = sub_hash.to_smaller_hash();
	cache.borrow_mut().insert(mark, sub_hash);
	sub_hash
	});
	sub_hash.hash_stable(hcx, hasher);

Please cache the full Fingerprint though, not just half of it as in the implementation above.