Use of SmallVec in PluralRules Parser/AST

[zbraniecki]

You have a lot of boxes, which means a lot of mallocs. This is probably fine, but I wonder if smallvec would be useful, since I expect that most of these lists will be between 0 and 2 elements long, with a few going up to 5 or 6.

Originally posted by @sffc in https://github.com/unicode-org/icu4x/diffs/22

[zbraniecki]

I have the following patch that tests that:

diff --git a/components/pluralrules/Cargo.toml b/components/pluralrules/Cargo.toml
index 58ed6f8..c7e8aa4 100644
--- a/components/pluralrules/Cargo.toml
+++ b/components/pluralrules/Cargo.toml
@@ -20,6 +20,7 @@ serde = { version = "1.0", optional = true, features = ["derive"] }
 serde_json = {version = "1.0", optional = true }
 bincode = { version = "1.3", optional = true }
 serde-tuple-vec-map = { version = "1.0", optional = true }
+smallvec = "1.0"
 
 [dev-dependencies]
 criterion = "0.3"
diff --git a/components/pluralrules/src/rules/ast.rs b/components/pluralrules/src/rules/ast.rs
index b90bc33..3386d63 100644
--- a/components/pluralrules/src/rules/ast.rs
+++ b/components/pluralrules/src/rules/ast.rs
@@ -34,6 +34,7 @@
 //! [`PluralCategory`]: ../enum.PluralCategory.html
 //! [`parse`]: ../fn.parse.html
 //! [`test_condition`]: ../fn.test_condition.html
+use smallvec::SmallVec;
 use std::ops::RangeInclusive;
 
 #[derive(Debug, Clone, PartialEq)]
@@ -76,7 +77,7 @@ pub struct Rule {
 /// )
 /// ```
 #[derive(Debug, Clone, PartialEq)]
-pub struct Condition(pub Box<[AndCondition]>);
+pub struct Condition(pub SmallVec<[AndCondition; 2]>);
 
 /// An incomplete AST representation of a plural rule. Comprises a vector of Relations.
 ///
@@ -114,7 +115,7 @@ pub struct Condition(pub Box<[AndCondition]>);
 ///
 /// ```
 #[derive(Debug, Clone, PartialEq)]
-pub struct AndCondition(pub Box<[Relation]>);
+pub struct AndCondition(pub SmallVec<[Relation; 2]>);
 
 /// An incomplete AST representation of a plural rule. Comprises an Expression, an Operator, and a RangeList.
 ///
@@ -245,7 +246,7 @@ pub enum Operand {
 /// ]));
 /// ```
 #[derive(Debug, Clone, PartialEq)]
-pub struct RangeList(pub Box<[RangeListItem]>);
+pub struct RangeList(pub SmallVec<[RangeListItem; 2]>);
 
 /// An enum of items that appear in a RangeList: Range or a Value.
 ///
diff --git a/components/pluralrules/src/rules/parser.rs b/components/pluralrules/src/rules/parser.rs
index 0357a89..b83a80a 100644
--- a/components/pluralrules/src/rules/parser.rs
+++ b/components/pluralrules/src/rules/parser.rs
@@ -1,6 +1,7 @@
 use super::ast;
 use super::lexer::{Lexer, Token};
 use std::iter::Peekable;
+use smallvec::SmallVec;
 
 #[derive(Debug, PartialEq, Eq)]
 pub enum ParserError {
@@ -47,12 +48,12 @@ impl<'p> Parser<'p> {
     }
 
     fn parse(mut self) -> Result<ast::Condition, ParserError> {
-        let mut result = vec![];
+        let mut result = SmallVec::new();
 
         if let Some(cond) = self.get_and_condition()? {
             result.push(cond);
         } else {
-            return Ok(ast::Condition(result.into_boxed_slice()));
+            return Ok(ast::Condition(result));
         }
 
         while self.take_if(Token::Or) {
@@ -63,12 +64,13 @@ impl<'p> Parser<'p> {
             }
         }
         // If lexer is not done, error?
-        Ok(ast::Condition(result.into_boxed_slice()))
+        Ok(ast::Condition(result))
     }
 
     fn get_and_condition(&mut self) -> Result<Option<ast::AndCondition>, ParserError> {
         if let Some(relation) = self.get_relation()? {
-            let mut rel = vec![relation];
+            let mut rel = SmallVec::new();
+            rel.push(relation);
 
             while self.take_if(Token::And) {
                 if let Some(relation) = self.get_relation()? {
@@ -77,7 +79,7 @@ impl<'p> Parser<'p> {
                     return Err(ParserError::ExpectedRelation);
                 }
             }
-            Ok(Some(ast::AndCondition(rel.into_boxed_slice())))
+            Ok(Some(ast::AndCondition(rel)))
         } else {
             Ok(None)
         }
@@ -115,14 +117,14 @@ impl<'p> Parser<'p> {
     }
 
     fn get_range_list(&mut self) -> Result<ast::RangeList, ParserError> {
-        let mut range_list = Vec::with_capacity(1);
+        let mut range_list = SmallVec::new();
         loop {
             range_list.push(self.get_range_list_item()?);
             if !self.take_if(Token::Comma) {
                 break;
             }
         }
-        Ok(ast::RangeList(range_list.into_boxed_slice()))
+        Ok(ast::RangeList(range_list))
     }
 
     fn take_if(&mut self, token: Token) -> bool {

[sffc]

We no longer use runtime allocations in PluralRules.