What's the complexity of the concat strings operator in OCaml?-CodePudding

What is the complexity of str_A ^ str_B in OCaml ?

CodePudding user response：

It's O(n). Here's the source code of the function:

let ( ^ ) s1 s2 =
  let l1 = string_length s1 and l2 = string_length s2 in
  let s = bytes_create (l1   l2) in
  string_blit s1 0 s 0 l1;
  string_blit s2 0 s l1 l2;
  bytes_unsafe_to_string s

The function adds the length of the two strings, allocates a new buffer using that length, and then copies both the input strings into it.

In some languages, the runtime optimizes repeated string concatenations (for example several JavaScript implementations), but I don't believe OCaml does this based on this benchmark.