Immutable strings… in Delphi?

One of the “novelties” of the NextGen Delphi compiler is immutable strings, which I find quite puzzling, for lack of a better word, given that Delphi already had reference-counted copy-on-write strings, and the NextGen compiler uses reference-counted strings.

I always considered that Delphi’s String type was one of its remaining strong points, being a high-level abstraction (higher than Java’s or .Net’s String/StringBuilder dichotomy) with excellent low-level performance (on par with C/C++  character arrays).

From the recent discussions, it appears many don’t know what makes/made Delphi String so special, so here is a quick summary.

Immutability

String being immutable means you can keep a single reference across threads without trouble. That’s an advantage over C strings.

It also means that copying a string, be it for an assignment or a parameter passing, is just like passing a reference, you don’t have to duplicate the content if you want to be sure it isn’t modified behind your back. That’s an advantage over C strings and StringBuilder.

Note that none of the above are advantages over Delphi Strings, since the copy-on-write mechanism means that Delphi Strings are effectively immutable once they’re referenced more than once.

Reference-counting vs Garbage Collection

Every time a new assignment or parameter passing is made, the reference count of the String has to be increased, this is an atomic lock, and is related to memory management, so it’s there whether you’re using simple reference-counting or copy-on-write.

Under a GC, no atomic lock is required, a simple reference (pointer) has to be copied. This is very efficient, locally, but the memory management costs are just deferred to a later garbage collection phase. Since immutable strings don’t have reference to other objects, the GC for them can theoretically happen in parallel without any drawbacks (assuming the GC supports it).

So under a GC, an immutable String type makes a whole lot of sense, as implementing a copy-on-write one requires a lot of effort, and a mutable one is problematic multi-threading wise.

Copy-on-write mutability

Making reference-counted strings mutable doesn’t change any of the above, you just add one capability: when the reference count indicates there is no other reference to a string, then you can mutate it, ie. change characters, adjust its length, etc.

In other words, when the only reference to a string is a single variable locally scoped to a procedure, then it’s safe to do just about anything with it, the multi-threading issues can’t  apply until that string is referenced somewhere else.

This is both convenient and very efficient, since what the compiler does before applying a mutation can be summarized as:

if myString is "referenced somewhere else" then
   myString := make a local copy of my String
mutate myString

The local copy is of course referenced nowhere else, and thus is safe to mutate. Copy-on-write is really copy-on-mutate, as it encompasses just not changing the characters, but also resizing a string (re-allocations) and concatenations.

Keep in mind this is an “added-on” behavior, where you just take advantage of the memory management scheme being a reference-counting one. If you know what you’re doing and want more performance, you can even waive the COW check by using UniqueString(), which will ensure you have a local copy, and then acquiring a PChar to the string content.

It can be done under a GC, but means you have to maintain a reference count or similar information since the GC doesn’t have one. Android relies a lot on copy-on-write, and that was actually one key differentiation between Dalvik VM and more classic Java VM.

Advantages of RawByteString & UTF8String over TBytes

And this will be a bit more controversial, but Copy-On-Write is also why RawByteString/UTF8String can ofttimes make a lot more sense than TBytes for binary buffers: RawByteString isn’t just reference-counted (like TBytes), it is also supporting copy-on-write.

This means that in a multi-threaded environment, RawByteString shares the same advantages of immutability String enjoys, and which TBytes just doesn’t enjoy, as TBytes is always mutable.

Conclusion

String wraps up both advantages of Java/.Net String & StringBuilder, they have bother multi-threading immutability advantages and the mutability capability.

Performance-wise, under a speculative memory manager (like most modern allocators), you’ll also find that merely concatenating to a String is typically just as fast as using TStringBuilder, and in several occurrences  it’s actually faster because String benefits from compiler magic, while TStringBuilder does not (also some TStringBuilder implementations are a little weak).

Alas some String performance was lost during the Unicode and 64bit transition, when some FastCode routines where replaced by lower performing pure-pascal ones, and you’ll lose even more performance with TStringHelper, which introduces some algorithmically poor pure-Pascal implementations.

11 thoughts on “Immutable strings… in Delphi?

  1. AFAIK dynamic arrays also support reference counting.

    Nice article: it is always worth explaining the benefit of the COW string implementation in Delphi.

  2. The performance decrease in latest version of the Delphi RTL was one of the reasons why we re-invented the wheel in SynCommons.pas for mORMot, and wrote a TStringBuilder on steroids and dedicated high performance and multi-thread friendly UTF-8 process.

  3. Very interesting post.

    I hope Marco Cantu or Allen Bauer reply this post and Arnaud Bouchez one.

  4. @A. Bouchez Yes dynamic arrays use reference counting for memory management, but they don’t have any form of COW (and shouldn’t, they’re for a different purpose).

    And sadly yes as well, I’ve also been reinventing several key RTL functions and classes lately, and with XE4, I’ve started reinventing them not for performance, but to minimize ifdef hell… 🙁

  5. @Will Watts Actually he was ranting against a particular implementation around mutexes and critical sections, jump to the bottom of the article near “Mild vs. Severe Inefficiencies” and “Some Actual Numbers”, what Delphi uses is what he labelled:

    COW_AtomicInt is an efficient thread-safe COW string that uses
    atomic integer operations for serializing access to the 
    reference count.

    As for the remaining multi-threading overhead he mentions, it’s there as soon as you use any form of reference-counting, and the only two alternatives are manual memory management and GC.

  6. Excellent article! A very even-handed presentation of the different approaches. What seems to be discounted elsewhere is that there are, in fact, many using Delphi in industrial applications work, where low-level interface is necessary, and serial I/O rarely means USB. Also seemingly discounted is the breakage which is caused by eliminating low-level manipulation of characters in a string through array indices.

    When people are forced to rewrite, they often find time to reflect on whether Delphi remains the value it once was. Not all will find in the affirmative.

  7. It is also worth mentioning the immutable strings shifts the burden of string change management to you at the expense of more complicated mechanisms like a stringbuilder. The intended tradeoff is intended to be that multiple string modifications do not cause multiple copy phases (even when there is a reference count of 1, if insufficent memory is allocated to add data, you have to allocate new memory copy and then append).

    This really requires StringBuilder to be very efficient to justify the extra exposed complexity. I recall seeing some early metrics that made it clear this battle was not started on a good basis. We could use some new numbers here.

    String modifications on short strings tend to be fairly cheap, so unless you are doing a LOT of modifications to a single string, and that string gets very large, the extra complexity comes at no real advantage. And often, you can use a TStringList instead of a string or stringbuilder to get around all of it AND gain a lot of extra features along the way.

    Frankly, immutable strings are a crutch to a poorly designed runtime feature to force people into better string management techniques. It is such a poor solution the problem that I would not be surprised to find patent avoidance or other IP related issues at its true core.

  8. @C Johnson

    SetLength(OldStr,Length(OldStr)+length(AddStr));
    Move(AddStr[1],OldStr[Length(OldStr)+1],length(AddStr));

    Much Faster then using string builder.

  9. Very nice roundup about the features and advantages of strings in Delphi compared to other platforms. I agree on some speed loss compared to FastCode, but mostly because we moved away from assembly (given platform portability is very relevant for Delphi today). Also, TStringBuilder can be faster in the scenarios it beats the native memory manager in terms of pre-allocations, something FastMM4 does pretty well on Windows, the native iOS allocator doesn’t seem so smart doing.

    Stay assured, there is no plan to change anything going forward unless there is a proven advantage. This is particularly true for immutable strings. They could provide some advantage (for example in heavy multi-threading, when managing string fragments, and in other scenarios)… but will also have disadvantages. At this point there is no definitive decisions on this. Strings in the current Delphi iOS compiler are NOT IMMUTABLE, there is only a warning indicating where things might change in the future. Native might change, not will certainly change.

    -Marco Cantu (Delphi PM)

Comments are closed.