String operation 1000X slower for special characters

Question

It seems that the string operation is very slow if we have special characters in the string. Consider this example,

str = 
  StringJoin@
   RandomChoice[Join[Alphabet[], ToString /@ Range[0, 9]], 1000000];

str2 = StringJoin[str, "â"];

sampleCorpus[corpus_, len_, num_] := Module[
   {positions = 
     RandomInteger[{len + 1, StringLength[corpus] - 1}, num]},
   Thread[
    StringTake[corpus, {# - len, #} & /@ positions] -> 
     StringPart[corpus, positions + 1]]];

trainingData = sampleCorpus[str, 25, 10000]; // AbsoluteTiming
(* {0.020949, Null} *)

trainingData = sampleCorpus[str2, 25, 10000]; // AbsoluteTiming
(* {24.5085, Null} *)

The performance is decreased by a factor of more than 1000X. So why does this happen and is this a bug? I'm very surprised to see this since these string operations are very fundamental in a computer language, and I don't expect it to be so slow. As a comparison, both Python and Java doesn't have this problem.

---

Python

Here is a naive implementation in python, which doesn't slow down for the string with special characters and it is about 2X faster than the faster one in Mathematica

import random
import string
import time

ls = list(string.ascii_lowercase) + list(string.ascii_uppercase) + [str(x) for x in range(10)]

str1 = "".join([random.choice(ls) for _ in range(1000000)])
str2 = str1 + 'â'


def sampleCorpus(corpus, l, num):
    training = []
    for _ in range(num):
        idx = random.randrange(len(corpus)-l-1)
        training.append([corpus[idx:idx+l],corpus[idx+l+1]])
    return training

print("timing:")
start = time.time()
training = sampleCorpus(str1,25,10000)
end = time.time()
print("{:3f}s".format(end - start))

print("timing:")
start = time.time()
training = sampleCorpus(str2,25,10000)
end = time.time()
print("{:3f}s".format(end - start))


timing:
0.012459s
timing:
0.012882s

Java

Examples with and without special characters run about the same speed, about 10X faster than the faster version in Mathematica.

import java.util.Random;
public class Hello {

    public static void main(String[] args) {
        char[] ls = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZYZ0123456789".toCharArray();
        Random rand = new Random();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 1000000; i++) sb.append(ls[rand.nextInt(ls.length)]);
        String str1 = sb.toString();
        sb.append('\u00E2');
        String str2 = sb.toString();

        long start = 0, end = 0;
        System.out.println("timing:");
        start = System.currentTimeMillis();
        String[][] training = sampleCorpus(str1, 25, 10000);
        end =  System.currentTimeMillis();
        System.out.println(end - start);

        System.out.println("timing:");
        start = System.currentTimeMillis();
        training = sampleCorpus(str2, 25, 10000);
        end =  System.currentTimeMillis();
        System.out.println(end - start);
    }

    private static String[][] sampleCorpus(String corpus, int l, int num) {
        String[][] training = new String[num][2];
        Random rand = new Random();
        for(int i = 0; i < num; i++) {
            int idx = rand.nextInt(corpus.length() - l - 1);
            training[i][0] = corpus.substring(idx, idx + l);
            training[i][1] = corpus.substring(idx, idx + l + 1);
        }
        return training;
    }

}

Answer 1

Note that StringTake[corpus, List /@ (positions + 1)] is approximately 3 times faster than StringPart[corpus, positions + 1] with Mathematica 11. This change along with replacing Alphabet[] by equivalent CharacterRange["a", "z"] allows to test the code with versions earlier than Mathematica 11 (see the code dump at the bottom of the post). Here are the timings (OS Windows 7 x64, all on the same machine):

Mathematica 11.1.1: 0.0266484 and 48.2524

Mathematica 10.4.1: 0.0381949 and 48.7356

Mathematica 8.0.4: 179.7102788 and 179.6032727

One can see that for Mathematica 8.0.4 the timings are identical and about 3 times larger than the worst timings for versions 10 and 11. The picture remains the same if we include the complete ASCII table (with control characters) into the string:

str = StringJoin@RandomChoice[FromCharacterCode /@ Range[0, 127], 1000000];

Addition of any non-ASCII character to the set (irrespective whether it has code lesser than 255 or larger) makes the timings 1000 times larger in the recent versions of Mathematica but doesn't alter them in version 8.0.4:

str2 = StringJoin[str, FromCharacterCode@10000];

Hence it becomes clear that in the recent versions of Mathematica string operations (at least StringTake and StringPart) are specially optimized for purely ASCII strings what gives more than 1000 times faster execution as compared to the version 8. No bugs there.

Update: why ASCII only

Itai Seggev's next statement sheds some light on the reason why optimization only concerns purely ASCII strings (which require only 7 bit per character):

We internally encode strings in a variant of UTF-8. Now, of course, any byte can be faithfully converted to/from ISO8859-1, but that encoding only equals UTF-8 for the lower 7 bits. For other values, you need to use multiple bytes per character. So using a string to store byte data is both less space efficient and time efficient (since you need to ensure to correct conversion between the two encodings.)

Let us check how much memory requires one character in a purely ASCII string (7-bit per character) as compared to non-ASCII strings depending on a code point used:

TableForm[Table[{Row[{2^ToString[n], "=", 2^n}], 
   Round[ByteCount[StringRepeat[FromCharacterCode[2^n], 10^6]]/10^6]}, {n, 6, 15}], 
 TableHeadings -> {None, {"Code point", "Bytes per character"}}]

(output is from Mathematica 11.1.1).

We see that purely ASCII string requires 1 byte per character while a string consisting from characters with code 128 require 2 bytes per character, and starting from code 2048 it requires 3 bytes per character.

For comparison, let us see how the same table looks in Mathematica 8.0.4:

TableForm[Table[{Row[{2^ToString[n], "=", 2^n}], 
   Round[ByteCount[StringJoin@Table[FromCharacterCode[2^n], {10^6}]]/10^6]}, {n, 6, 15}], 
 TableHeadings -> {None, {"Code point", "Bytes per character"}}]

Obviously in version 8 another internal encoding was used, seemingly UCS-2. For version 5.2 the table looks the same.

---

Here is the code dump for testing with earlier versions:

SeedRandom[1]

str = StringJoin@
   RandomChoice[Join[CharacterRange["a", "z"], ToString /@ Range[0, 9]], 1000000];

str2 = StringJoin[str, "â"];

sampleCorpus[corpus_, len_, num_] := 
  Module[{positions = RandomInteger[{len + 1, StringLength[corpus] - 1}, num]}, 
   Thread[StringTake[corpus, {# - len, #} & /@ positions] -> 
     StringTake[corpus, List /@ (positions + 1)]]];

trainingData = sampleCorpus[str, 25, 10000]; // AbsoluteTiming

trainingData = sampleCorpus[str2, 25, 10000]; // AbsoluteTiming