What string type should we use for short UTF-8 strings?

[sffc]

We commonly need to handle short UTF-8 strings that are longer than one code point. For example, a lot of CLDR data may be one grapheme cluster long, or may be one code point plus a bidi control character.

@zbraniecki compiled a great list of some options:

https://github.com/zbraniecki/tinystr/wiki/Performance

Here are the options in that doc, along with my initial thoughts on their pros and cons.

• SmolStr
  • 29 stars on GitHub
  • Pro: size_of::<SmolStr>() == size_of::<String>()
  • Pro: Serde integration
  • Pro: No dependencies except for the Serde traits
  • Con: Doesn't support #![no_std]
  • Con: No mutable functions
• smallstr
  • 6 stars on GitHub
  • Pro: FFI integration
  • Pro: Serde integration
  • Pro: Good documentation
  • Pro: #![no_std] (uses alloc)
  • Con: Only 6 stars; owner's affiliation unclear
• ArrayString
  • 255 stars on GitHub
  • Pro: Serde integration
  • Pro: Good documentation
  • Pro: #![no_std] (no dependence on alloc)
  • Pro: Lots of stars and contributors
  • Pro: Comes with other non-String stack vectors that we could leverage
  • Pro: No dependencies except for the Serde traits
  • Con: Does not support overflow onto heap, which may be necessary since grapheme clusters are not bounded by length
• istring
  • No stars on GitLab
  • Pro: #![no_std] (uses alloc)
  • Con: Only one contributor, and no activity since 2018
  • Con: Not much documentation

Thoughts? @Manishearth @hsivonen

The doc also lists "istring", but I can't find it on GitHub. Pointers?

[zbraniecki]

https://crates.io/crates/istring

[sffc]

https://crates.io/crates/istring

Thanks; found it on GitLab. Added it above.

[Manishearth]

I think we might want to make a custom type that is ArrayString on no_std and ArrayString+spillover on std.

SmolStr is also not mutable, otherwise that would be nice. smallstr is okay.

[sffc]

Mutability is a nice-to-have, but I think not essential. When we want to build up strings from pieces, we probably want something more full-featured than a mutable string, something that can keep track of field positions, capitalization contexts, etc. (ICU calls this FormattedStringBuilder.)

Maintaining our own custom type sounds complicated.

I think I'm leaning toward smallstr because it has all the features we want, and it's built on a solid foundation (smallvec).

We can always change before v1.

[zbraniecki]

CC @emilio @hsivonen for feedback

It would be great to document our decision in https://github.com/unicode-org/icu4x/blob/master/docs/string-representation.md

[hsivonen]

The string representation doc is scoped to the outer API.

Do we expect this type to be visible in the API that a Rust application developer using ICU4X sees?

[zbraniecki]

My understanding was that this is an internal type, but Shane's:

We can always change before v1.

make me question that.

If it is indeed internal, we can also switch it post v1 I believe.
I mostly wanted to get your feedback to verify that what we're choosing will work well between public API and internal types.

[sffc]

The type is mostly internal, but I was thinking that we could use it in the data provider structs, which are public API since you can build your own data provider.

[sffc]

Agreement: use smallstr.

[sffc]

I looked at the binary sizes. I selectively compiled the following functions to WASM:

// #[no_mangle]
pub fn init_smallstr() {
	let message: SmallString<[u8; 16]> = SmallString::from("Hello, world!");
	unsafe {
		alert(&message);
	}
}

// #[no_mangle]
pub fn greet_smallstr(input: &str) {
	let mut message: SmallString<[u8; 16]> = SmallString::new();
	message.push_str("Hello, ");
	message.push_str(input);
	message.push_str("!");
	unsafe {
		alert(&message);
	}
}

// #[no_mangle]
pub fn init_arraystring() {
	let message: ArrayString<[_; 16]> = ArrayString::from("Hello, world!").unwrap();
	unsafe {
		alert(&message);
	}
}

// #[no_mangle]
pub fn greet_arraystring(input: &str) {
	let mut message: ArrayString<[_; 16]> = ArrayString::new();
	message.push_str("Hello, ");
	message.push_str(input);
	message.push_str("!");
	unsafe {
		alert(&message);
	}
}

// #[no_mangle]
pub fn init_str() {
	let message = String::from("Hello, world!");
	unsafe {
		alert(&message);
	}
}

// #[no_mangle]
pub fn greet_str(input: &str) {
	let mut message = String::new();
	message.push_str("Hello, ");
	message.push_str(input);
	message.push_str("!");
	unsafe {
		alert(&message);
	}
}

Results:

Function	Bytes of .wat file
(control)	5578
init_smallstr	29084
greet_smallstr	43388
init_arraystring	6305
greet_arraystring	23897
init_str	31295
greet_str	37333

See: sffc/rust-wasm-i18n@1583344

Main takeaways:

• SmallString is smaller than the standard library String when using FromStr, but a bit bloated when using mutation methods (the greet input/output function).
• Most of the size of both SmallString and standard library String is in WeeAlloc
• ArrayString is very small in the FromStr, because it doesn't need WeeAlloc, but gets substantially larger in the greet function. It appears that most of the assembly code for the greet function is core::fmt::Display.
• SmallString gets a bit smaller, down to 28917 on init_smallstr, when the nightly union feature is used.

I expect that the high-runner use case for these types is as a data type constructed from a fixed string, and both SmallString and ArrayString are slimmer than standard library String in that case. However, ArrayString lacks the ability to heap-allocate on overflow.

Conclusion: stick with SmallString.

[EvanJP]

A recent email in the rust-users google group brought up this interesting blog post on SmolStr vs SmartString (no SmallStr). https://fasterthanli.me/articles/small-strings-in-rust. There are benchmarks regarding heap allocation (regardless of mutation/immutability) that are if nothing else an interesting read.