From 74f8201586435a7a2e7f8fd49c7eb0750a089180 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 20 Jan 2021 14:47:42 +0300 Subject: Avoid intermediate collections --- docs/dev/style.md | 34 +++++++++++++++++++++++++++++++++- 1 file changed, 33 insertions(+), 1 deletion(-) (limited to 'docs') diff --git a/docs/dev/style.md b/docs/dev/style.md index aed15cee9..389649398 100644 --- a/docs/dev/style.md +++ b/docs/dev/style.md @@ -421,12 +421,44 @@ fn frobnicate(s: &str) { **Rationale:** reveals the costs. It is also more efficient when the caller already owns the allocation. -## Collection types +## Collection Types Prefer `rustc_hash::FxHashMap` and `rustc_hash::FxHashSet` instead of the ones in `std::collections`. **Rationale:** they use a hasher that's significantly faster and using them consistently will reduce code size by some small amount. +## Avoid Intermediate Collections + +When writing a recursive function to compute a sets of things, use an accumulator parameter instead of returning a fresh collection. +Accumulator goes first in the list of arguments. + +```rust +// GOOD +pub fn reachable_nodes(node: Node) -> FxHashSet { + let mut res = FxHashSet::default(); + go(&mut res, node); + res +} +fn go(acc: &mut FxHashSet, node: Node) { + acc.insert(node); + for n in node.neighbors() { + go(acc, n); + } +} + +// BAD +pub fn reachable_nodes(node: Node) -> FxHashSet { + let mut res = FxHashSet::default(); + res.insert(node); + for n in node.neighbors() { + res.extend(reachable_nodes(n)); + } + res +} +``` + +**Rational:** re-use allocations, accumulator style is more concise for complex cases. + # Style ## Order of Imports -- cgit v1.2.3