elixir-lang/elixir — pull request #2538 by alco (2014-07-15 11:45:39+00:00)
Title: Do not traverse the string twice in String.slice(<str>, <range>)

The approach I've taken here is to keep byte sizes of each codepoint in a list until we reach the end of the string, then we calculate byte offsets and call `binary_part` once.

This uses the amount of memory proportional to the absolute value of the smallest offset in the range just to keep the byte sizes. I can't say exactly how much more memory it uses compared to keeping an accumulator on master.

I've tried replacing lists with binary arithmetic and queues. Both techniques showed worse performance than master.

Feel free to reject this PR as it adds more complexity to the code with not as much gain as I had hoped.

Some graphs (benchmark code – https://gist.github.com/alco/330d7b8a601bfed057dc). The dark green bars are master, the lighter green bars are this PR. The Y axis is execution time in microseconds.
![slice_left](https://cloud.githubusercontent.com/assets/207748/3584137/490364a8-0c14-11e4-87e6-a147556fca72.png)
![slice_right](https://cloud.githubusercontent.com/assets/207748/3584139/5093a46c-0c14-11e4-9378-d9f13b05553f.png)
![slice_both](https://cloud.githubusercontent.com/assets/207748/3584141/54d5b04c-0c14-11e4-8e24-525244a734f3.png)