Forcing SmolStr to allocate on stack when the size_hint of an iterator is bad

[thomas-k-cameron]

Implementation

• https://github.com/thomas-k-cameron/smol_str/tree/smol-str
• Smol str thomas-k-cameron/smol_str#1

What we should do

SmolStr allocates data on heap when size_hint of a iterator is above 24.
Even when the size hint is incorrect, it keeps it's data on heap, wrapped in Arc.

I want SmolStr to allocate it's contents on stack when the resulting data is turns out to be smaller.

Why do we need this

It allows us to introduce new optimization, reduce interaction with Arc... etc.

Proof

Here is an analysis of assembly code.
(I'm pretty sure that there is a better way to do this)

You can see that my optimization reduces number of instructions and improves uOps per cycle/IPC.

Current version of the code.

https://rust.godbolt.org/z/Mh9GhYbM9

Iterations:        100
Instructions:      97400
Total Cycles:      52538
Total uOps:        124800

Dispatch Width:    6
uOps Per Cycle:    2.38
IPC:               1.85
Block RThroughput: 208.0

This one with my optimization.

https://rust.godbolt.org/z/3Gh8jacYK

Iterations:        100
Instructions:      91200
Total Cycles:      36167
Total uOps:        117500

Dispatch Width:    6
uOps Per Cycle:    3.25
IPC:               2.52
Block RThroughput: 195.8

[bjorn3]

How much performance does this cost if the size_hint was correct after all? The size hint is supposed to be correct.

[thomas-k-cameron]

It wouldn't cost anything If the size hint is correct. (tbh, I don't think it would make any significant improvement either.)

It only affects when size_hint tells it's more than 24 when it's 24 or less, i.e. SmolStr gets allocated on heap when it doesn't have to.

There was a test case for incorrect size hint, so I just assumed that it's an assumption that you have to make.

https://github.com/thomas-k-cameron/smol_str/pull/1/files#diff-7b19987f13f75d72d1f447086be16710eb6330767898f3493bf54ac2b15fa0c1L253-L258

[Veykril]

I do think we should have the invariant that when SmolStr is Heap backed, the string needs to be longer than the INLINE_CAP, the last release does have the extra check for if the size hint lies to fall back to inline.