Search code examples
stringconcatenationocamlcomplexity-theory

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

What is the complexity of str_A ^ str_B in OCaml ?

Solution

  • 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.