From 17a8aff20abdef46ae90801c85cc232e81443e1b Mon Sep 17 00:00:00 2001
From: Nicholas Nethercote <nnethercote@mozilla.com>
Date: Thu, 28 Mar 2019 12:27:26 +1100
Subject: [PATCH] Use `SmallVec` in `TokenStreamBuilder`.

This reduces by 12% the number of allocations done for a "clean
incremental" of `webrender_api`, which reduces the instruction count by
about 0.5%.

It also reduces instruction counts by up to 1.4% across a range of
rustc-perf benchmark runs.
---
 src/libsyntax/parse/attr.rs  |  3 ++-
 src/libsyntax/tokenstream.rs | 14 ++++++++------
 2 files changed, 10 insertions(+), 7 deletions(-)

diff --git a/src/libsyntax/parse/attr.rs b/src/libsyntax/parse/attr.rs
index 4211268f33e..e99a86e807f 100644
--- a/src/libsyntax/parse/attr.rs
+++ b/src/libsyntax/parse/attr.rs
@@ -6,6 +6,7 @@
 use crate::tokenstream::{TokenStream, TokenTree};
 
 use log::debug;
+use smallvec::smallvec;
 
 #[derive(Debug)]
 enum InnerAttributeParsePolicy<'a> {
@@ -171,7 +172,7 @@ fn parse_attribute_with_inner_parse_policy(&mut self,
                 } else {
                     self.parse_unsuffixed_lit()?.tokens()
                 };
-                TokenStream::from_streams(vec![eq.into(), tokens])
+                TokenStream::from_streams(smallvec![eq.into(), tokens])
             } else {
                 TokenStream::empty()
             };
diff --git a/src/libsyntax/tokenstream.rs b/src/libsyntax/tokenstream.rs
index 80a7bde606a..2d47b982ebd 100644
--- a/src/libsyntax/tokenstream.rs
+++ b/src/libsyntax/tokenstream.rs
@@ -24,6 +24,7 @@
 use rustc_data_structures::static_assert;
 use rustc_data_structures::sync::Lrc;
 use serialize::{Decoder, Decodable, Encoder, Encodable};
+use smallvec::{SmallVec, smallvec};
 
 use std::borrow::Cow;
 use std::{fmt, iter, mem};
@@ -224,7 +225,7 @@ fn from(token: Token) -> TokenStream {
 
 impl<T: Into<TokenStream>> iter::FromIterator<T> for TokenStream {
     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
-        TokenStream::from_streams(iter.into_iter().map(Into::into).collect::<Vec<_>>())
+        TokenStream::from_streams(iter.into_iter().map(Into::into).collect::<SmallVec<_>>())
     }
 }
 
@@ -256,7 +257,7 @@ pub fn is_empty(&self) -> bool {
         }
     }
 
-    pub(crate) fn from_streams(mut streams: Vec<TokenStream>) -> TokenStream {
+    pub(crate) fn from_streams(mut streams: SmallVec<[TokenStream; 2]>) -> TokenStream {
         match streams.len() {
             0 => TokenStream::empty(),
             1 => streams.pop().unwrap(),
@@ -393,12 +394,13 @@ fn last_tree_if_joint(&self) -> Option<TokenTree> {
     }
 }
 
+// 99.5%+ of the time we have 1 or 2 elements in this vector.
 #[derive(Clone)]
-pub struct TokenStreamBuilder(Vec<TokenStream>);
+pub struct TokenStreamBuilder(SmallVec<[TokenStream; 2]>);
 
 impl TokenStreamBuilder {
     pub fn new() -> TokenStreamBuilder {
-        TokenStreamBuilder(Vec::new())
+        TokenStreamBuilder(SmallVec::new())
     }
 
     pub fn push<T: Into<TokenStream>>(&mut self, stream: T) {
@@ -485,7 +487,7 @@ pub fn append(&mut self, new_stream: TokenStream) {
         }
         let index = self.index;
         let stream = mem::replace(&mut self.stream, TokenStream(None));
-        *self = TokenStream::from_streams(vec![stream, new_stream]).into_trees();
+        *self = TokenStream::from_streams(smallvec![stream, new_stream]).into_trees();
         self.index = index;
     }
 
@@ -572,7 +574,7 @@ fn test_concat() {
             let test_res = string_to_ts("foo::bar::baz");
             let test_fst = string_to_ts("foo::bar");
             let test_snd = string_to_ts("::baz");
-            let eq_res = TokenStream::from_streams(vec![test_fst, test_snd]);
+            let eq_res = TokenStream::from_streams(smallvec![test_fst, test_snd]);
             assert_eq!(test_res.trees().count(), 5);
             assert_eq!(eq_res.trees().count(), 5);
             assert_eq!(test_res.eq_unspanned(&eq_res), true);
-- 
2.44.0