In unicode_string if you have a look at how the segmentation is implemented (https://github.com/elixir-unicode/unicode_string/blob/master...) it will make a lot of calls to Regex.split and it does this as it moves along the string. It will be calling Regex.split on the remaining part of the string it needs to work on a lot. The problem is Regex.split as implemented in Elixir just runs the regex on the whole string looking for all the matches even if you include a limit on the number of parts so the segmentation algorithm is going to have quadratic complexity. Also, when there are unicode ranges in the regular expression it runs a lot slower. However, the erlang re engine is not validating whether the binary is valid utf8 or not before running the regular expression matching. These errors they were getting was because Regex.split() causes the erlang re engine to match the whole string.

For example:

    iex(86)> v = "£AXAX" <> String.duplicate("A", 10_000) <> "\xFF"; {:ok, r} = :re.compile("[£-¨]"); :timer.tc(fn() -> :re.run(v, r) end)
    {65, {:match, [{0, 1}]}}

Also, even though Regex.split() returns two strings that are the size of the input the function does not necessarily have to linear because erlang has fast substring slicing. Example:

    iex(47)> x = String.duplicate("A", 100_000); y = :binary.part(x, {0, 5000}); :binary.referenced_byte_size(y)
    100000

Though, its probably not safe to rely on this because :binary.part() will not always use a fast slice if the slice is not big enough. I know some erlang parsing code explicitly keeps track of indices instead of using <<"foo", rest::binary()>> idiom presumably because its faster.

Here are some timings from Regex.split() that show that it is linear to the size of the input. You can see there are some very big constant costs that hide that Regex.split() is linear when not using unicode ranges.

    iex(25)> v = "AXAX" <> String.duplicate("A", 1); r = ~r/[£-¨]/; :timer.tc(fn() -> Regex.split(r, v, parts: 2) end)
    {31, ["AXAXA"]}

    iex(26)> v = "AXAX" <> String.duplicate("A", 10_000); r = ~r/[£-¨]/; :timer.tc(fn() -> Regex.split(r, v, parts: 2) end)
    {232, ...}


    iex(37)> v = "AXAX" <> String.duplicate("A", 1); r = ~r/X/; :timer.tc(fn() -> Regex.split(r, v, parts: 2) end)
    {39, ["A", "AXA"]}

    iex(29)> v = "AXAX" <> String.duplicate("A", 10_000); r = ~r/X/; :timer.tc(fn() -> Regex.split(r, v, parts: 2) end)
    {38, ...}

    iex(38)> v = "AXAX" <> String.duplicate("A", 100_000); r = ~r/X/; :timer.tc(fn() -> Regex.split(r, v, parts: 2) end)
    {274, ..}