# Best practice for performant string operation? **URL:** \ **Category:** Learning\ **Tags:** string, performance\ **Created:** [February 17, 2022, 12:57am UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345 "2022-02-17T00:57:23Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![bn-d](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bn-d/32/6471_2.png) [@bn-d](https://discuss.ocaml.org/u/bn-d)\ **Post date:** [February 17, 2022, 12:57am UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/1 "2022-02-17T00:57:23Z")
> [@\[ANN\] First Release of ppx\_pyformat 0.1.1](https://discuss.ocaml.org/t/ann-first-release-of-ppx-pyformat-0-1-1/9321/5): > > Using ^ for concatenation for each elements looks inefficient. Generating a call to String.concat "" should be more efficient and quite comparable in term of complexity for the code generator. I recently received this comment (thanks!) for a package I published. It is honestly something I never think of before. ```ocaml str_1 ^ str_2 ^ str_3 ^ str_4 ^ str_5 ``` This code seems innocent and clean. But if you look at `^` underlying implementation, you will know this is inefficient. `^` only handles two strings at a time. So 4 new `String.t`/`Bytes.t` objects are created during the process and the first string is copied 4 times. On contract, `String.concat ""` can do everything in one run. This comment led me back to re-evaluate all my string operations, and reimplement some of them. For example, I originally had ```ocaml let align_left w c s = let len = String.length s in if len >= w then s else s ^ String.make (w - len) c ``` A re-implementation was ```ocaml let align_left w c s = if len >= w then s else let b = Bytes.create w in Bytes.blit_string s 0 b 0 len; Bytes.fill b len (w - len) c; Bytes.to_string b ``` To my surprise, the re-implementation is slightly slower than the old one. So I rewrote the function using lower-level API. ```ocaml external bytes_unsafe_fill : bytes -> int -> int -> char -> unit = "caml_fill_bytes" [@@noalloc] external bytes_unsafe_blit_string : string -> int -> bytes -> int -> int -> unit = "caml_blit_string" [@@noalloc] external bytes_unsafe_to_string : bytes -> string = "%bytes_to_string" let align_left w c s = if len >= w then s else let b = Bytes.create w in bytes_unsafe_blit_string s 0 b 0 len; bytes_unsafe_fill b len (w - len) c; bytes_unsafe_to_string b ``` This code is up to 100% faster the original one (according to my limited and unscientific tests)! The questions are - It seems chaining `^` is a trap a lot of people will fall into. Is it possible to have compiler level optimization for this? When the complier sees a chain of `^` operation, it will be automatically compiled to `String.concat` or something else similar. Is there anything prevent us doing this? - Why does the second implementation have worse performance than the first one? - Is it a good idea to use all the external functions as in the third implementation? - And… what is the best practice for performant string operation in general? Thanks. Happy hacking! ---
**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\ **Post date:** [February 17, 2022, 1:14am UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/2 "2022-02-17T01:14:13Z")
> [@bn-d](#): > > When the complier sees a chain of `^` operation, it will be automatically compiled to `String.concat` or something else similar. This would be a really bad thing to do, I think. There are many equations between different expressions, and starting to implement this sort of stuff is just a Pandora’s box. Now, I can understand why you might have gotten the impression that `a ^ b ^ c ^ d` was innocent: in Java, it gets converted into (1) create a string buffer, (2) append `a`, `b`, etc, (3) extract the final string. The thing is: OCaml (and ML generally) has a history of being a language where you can look at what you wrote and know what it’s going to do. That means that whey you write `a ^ b ^ c ^ d` you’re expecting it to be three binary-concats, and left-to-right. The compiler doesn’t second-guess you on that. At least, that’s been the history. ---
**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\ **Post date:** [February 17, 2022, 7:18am UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/3 "2022-02-17T07:18:20Z")
Let’s examine this code: ```ocaml let align_left w c s = let len = String.length s in if len >= w then s else s ^ String.make (w - len) c (* 1: 2 allocations + 2 copies *) ``` The line marked `1` has 2 allocations: one for the new string, and one for the concatenation, and 2 copies: again, one for the `String.make` and one for the concatenation. Now let’s look at the second version: ```ocaml let align_left w c s = if len >= w then s else let b = Bytes.create w in (*1: allocation *) Bytes.blit_string s 0 b 0 len; (*2: copy + bounds check *) Bytes.fill b len (w - len) c; (*3: copy + bounds check *) Bytes.to_string b (*4: allocation + copy *) ``` In line 1 we have an allocation. In line 2 we have a copy + a bounds check to make sure you’re not getting a buffer overflow. The same is true for line 3. And then in line 4, we have another allocation + copy. We have to allocate because a string is read-only, whereas a byte could be modified by its holder. So you see, the second version is actually slightly worse than the first one: we have an extra copy + 2 bounds checks since the copy in these cases is mandated by the programmer rather than the runtime, and is therefore potentially a buffer overflow. Now let’s examine the 3rd version: ```ocaml let align_left w c s = if len >= w then s else let b = Bytes.create w in (* 1: allocation *) bytes_unsafe_blit_string s 0 b 0 len; (* 2: copy *) bytes_unsafe_fill b len (w - len) c; (* 3: copy *) bytes_unsafe_to_string b (* 4: no-op *) ``` First of all, it’s worth mentioning that all these unsafe functions are already present in the stdlib within the Bytes module. For some reason they don’t show up in the API, but `Bytes` has `unsafe_blit_string`, `unsafe_blit` and `unsafe_fill`. But it’s important to understand why they’re faster. The unsafe copy functions skip bounds checking, which is usually a bad idea. The `Bytes.unsafe_to_string` function doesn’t do anything, because it assumes you know what you’re doing and that it can use the same underlying `bytes` object as a `string`, despite potentially read/write issues. So what’s the bottom line? You need to especially think about your allocations. If you’re going to be augmenting a string with chars, as you are here, then avoiding `^` is a good idea. A simple `^` concatenation is best when you don’t care about performance (which is a lot of the time), or when you’re only doing one concatenation of 2 existing strings. It’s also worth considering the `Buffer` module, which was created for exactly these kinds of use-cases. However, for this particular function, the monitored reuse of `bytes` as a `string`, though not safe in the general case, is probably optimal. Also, dropping bounds checks is very dangerous and should very rarely be done. ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [February 17, 2022, 8:45am UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/4 "2022-02-17T08:45:16Z")
> [@Chet\_Murthy](#): > > OCaml (and ML generally) has a history of being a language where you can look at what you wrote and know what it’s going to do. That means that whey you write `a ^ b ^ c ^ d` you’re expecting it to be three binary-concats, and left-to-right. You defeated your point as soon as you made it ;-). Indeed, the `(^)` operator is right-associative, so the expression `a ^ b ^ c ^ d` is actually `a ^ (b ^ (c ^ d))`. ---
**Author:** ![mseri](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mseri/32/91_2.png) [@mseri](https://discuss.ocaml.org/u/mseri)\ **Post date:** [February 17, 2022, 9:46am UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/5 "2022-02-17T09:46:24Z")
Tangentially related, have a look also at [this thread](https://discuss.ocaml.org/t/whats-the-fastest-way-to-concatenate-strings) for a discussion and benchmarks on the subject ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [February 17, 2022, 3:02pm UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/6 "2022-02-17T15:02:39Z")
> [@bluddy](#): > > It’s also worth considering the `Buffer` module, which was created for exactly these kinds of use-cases. Buffer will force an additional allocation+copy on you at the end, because it doesn’t give you access to its internal `bytes`. So if you’re counting allocations, just stay away from it. ---
**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\ **Post date:** [February 17, 2022, 3:41pm UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/7 "2022-02-17T15:41:18Z")
> [@c-cube](#): > > Buffer will force an additional allocation+copy on you at the end, because it doesn’t give you access to its internal `bytes` . So if you’re counting allocations, just stay away from it. Buffer is still useful when you want to build a string gradually but don’t want to compute how big it will eventually be (which is to say, most of the time). It is unfortunate that we don’t have access to the underlying data - after all, Buffer is a Vector version of `bytes` - but it’s still more useful (and safer) than trying to predict how big your final `bytes` buffer should be. ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [February 17, 2022, 4:14pm UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/8 "2022-02-17T16:14:51Z")
That’s true, that’s the use case. If you’re going to allocate a string eventually it’s fine to use Buffer. ---
**Author:** ![bn-d](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bn-d/32/6471_2.png) [@bn-d](https://discuss.ocaml.org/u/bn-d)\ **Post date:** [February 17, 2022, 9:48pm UTC](https://discuss.ocaml.org/t/best-practice-for-performant-string-operation/9345/9 "2022-02-17T21:48:57Z")
Thanks! That is an excellent explanation! I totally overlooked the extra allocation and copy caused by `Bytes.to_string` in the second implementation. It is also good to know all the unsafe functions are actually available through the `Stdlib.Bytes`. I compared the performance of the function with bounds check vs without bonds check (using unsafe functions). Although the one with bounds check is significantly faster than the `string` implementation, it is still 20%~30% slower than the unsafe one. For this specific function, I am 100% sure the input is within the bounds. So I decide to take the risk.