3 ms·
"Many string operations are useful as a general list operations as well, including regular expression matcher." The way to get around that is to have some conc
by nostrademons 17y ago
"Many string operations are useful as a general list operations as well, including regular expression matcher."
The way to get around that is to have some concept of interfaces in the language, and then have a generic Sequence type that strings, arrays, lists, and a bunch of other concrete types all implement. This makes your sequence operations even more polymorphic, eg. you can have them work on ropes, iterators, tree traversals, etc.
The real problem with the list representation for strings is memory consumption. English UTF-8 text in a byte array takes one byte per code point. English unicode text in a list where each code point is an immediate 32-bit int takes up 8 bytes per character. That's a factor of 8 difference in memory consumption.
And more memory means you can't fit as much into cache. There's a huge difference between being able to keep all your strings in L2 cache vs. having to go to main memory, particularly for string manipulations, which may need to touch a lot of different memory locations without a lot of locality.
"Some people emphasize importance of O(1) access of string access by index, but using integer index is also a performance hack. If search operations can return some way to point to the substring you don't need integer indexes."
Also, UTF-8 usually means you have to give up O(1) indexing. Your string may have multi-byte characters, which you can't discover unless you iterate through it.
In practice, this doesn't matter. The vast majority of string slices chop a few characters off from either the beginning or the end. You can do Boyer-Moore on byte sequences and return the byte offset instead of the character offset. Most other indexing operations involve some sort of iteration over the string anyway. The only real pathological case is when you need to find the midpoint of a string repeatedly.