std: Move rand to librand.

This functionality is not super-core and so doesn't need to be included
in std. It's possible that std may need rand (it does a little bit now,
for io::test) in which case the functionality required could be moved to
a secret hidden module and reexposed by librand.

Unfortunately, using #[deprecated] here is hard: there's too much to
mock to make it feasible, since we have to ensure that programs still
typecheck to reach the linting phase.
Remove the dependence of std::io::test on rand.

This replaces it with a manual "task rng" using XorShift and a crappy
seeding mechanism. Theoretically good enough for the purposes
though (unique for tests).
Update users for the std::rand -> librand move.
rand: deprecate `rng`.

This should be called far less than it is because it does expensive OS
interactions and seeding of the internal RNG, `task_rng` amortises this
cost. The main problem is the name is so short and suggestive.

The direct equivalent is `StdRng::new`, which does precisely the same
thing.

The deprecation will make migrating away from the function easier.
syntax: Add support for trait bounds on procs

This is needed to make progress on #10296 as the default bounds will no longer
include Send. I believe that this was the originally intended syntax for procs,
and it just hasn't been necessary up until now.
auto merge of #12650 : huonw/rust/librand, r=alexcrichton

Move std::rand to a separate rand crate

This functionality is not super-core and so doesn't need to be included
in std. It's possible that std may need rand (it does a little bit now,
for io::test) in which case the functionality required could be moved to
a secret hidden module and reexposed by librand.

Unfortunately, using #[deprecated] here is hard: there's too much to
mock to make it feasible, since we have to ensure that programs still
typecheck to reach the linting phase.

Also, deprecates/removes `rand::rng` (this time using `#[deprecated]`), since it's too easy to accidentally use inside a loop, making things very slow (have to read randomness from the OS and seed the RNG each time.)
auto merge of #12774 : alexcrichton/rust/proc-bounds, r=pcwalton

This is needed to make progress on #10296 as the default bounds will no longer
include Send. I believe that this was the originally intended syntax for procs,
and it just hasn't been necessary up until now.
test: Relax a debuginfo test

This test is blocking a snapshot. Apparently the snapshot bot doesn't print
'limited-debuginfo::main()' but rather just 'main()'. Who knew?
auto merge of #12839 : alexcrichton/rust/fix-snap, r=huonw

This test is blocking a snapshot. Apparently the snapshot bot doesn't print
'limited-debuginfo::main()' but rather just 'main()'. Who knew?
Performance-oriented hashtable.

Previously, rust's hashtable was totally unoptimized. It used an Option
per key-value pair, and used very naive open allocation.

The old hashtable had very high variance in lookup time. For an example,
see the 'find_nonexisting' benchmark below. This is fixed by keys in
'lucky' spots with a low probe sequence length getting their good spots
stolen by keys with long probe sequence lengths. This reduces hashtable
probe length variance, while maintaining the same mean.

Also, other optimization liberties were taken. Everything is as cache
aware as possible, and this hashtable should perform extremely well for
both large and small keys and values.

Benchmarks:

comprehensive_old_hashmap         378 ns/iter (+/- 8)
comprehensive_new_hashmap         206 ns/iter (+/- 4)
1.8x faster

old_hashmap_as_queue              238 ns/iter (+/- 8)
new_hashmap_as_queue              119 ns/iter (+/- 2)
2x faster

old_hashmap_insert                172 ns/iter (+/- 8)
new_hashmap_insert                146 ns/iter (+/- 11)
1.17x faster

old_hashmap_find_existing         50 ns/iter (+/- 12)
new_hashmap_find_existing         35 ns/iter (+/- 6)
1.43x faster

old_hashmap_find_notexisting      49 ns/iter (+/- 49)
new_hashmap_find_notexisting      34 ns/iter (+/- 4)
1.44x faster

Memory usage of old hashtable (64-bit assumed):

aligned(8+sizeof(K)+sizeof(V))/0.75 + 6 words

Memory usage of new hashtable:

(aligned(sizeof(K))
+ aligned(sizeof(V))
+ 8)/0.9 + 6.5 words

BUT accesses are much more cache friendly. In fact, if the probe
sequence length is below 8, only two cache lines worth of hashes will be
pulled into cache. This is unlike the old version which would have to
stride over the stoerd keys and values, and would be more cache
unfriendly the bigger the stored values got.

And did you notice the higher load factor? We can now reasonably get a
load factor of 0.9 with very good performance.