I was having a conversation with a friend about the C# StringBuilder class, and what it's behavior was. I'll paraphrase, but my side of the conversation was something like this (I oversimplified because exactly how StringBuilder works isn't important for my question)

StringBuilder is more efficient to use for extensive string concatenation than to simply use +. The reason is that StringBuilder doesn't dynamically create a new string for each concatenation operation. It waits until all of your desired concatenations are "built" and only then does it dynamically allocate the space and give you back your string.

My friend said something along the lines of

That may be true today, but if you are reliant on such optimizations, then you should make your own StringBuilder. In future versions, there's no reason that StringBuilder couldn't use simple string concatenation (str1 = str2 + str3). Libraries only guarantee functional equivalence, not runtime equivalence.

Is this true for libraries?

  • If I use a library's Sort() function that has runtime O(n*log(n)), is it possible that a future version would change the runtime to O(n^2)?

Is the same true for executable tools?

  • Could (for example) grep's runtime fundamentally change in the future?

That aside, wouldn't it be good practice for a library/API/tool developer to keep runtimes for the same calls similar over time?

  • Why would one intentionally slow down a function? – tkausl Jan 16 '16 at 11:45
  • For a regex matcher (grep) significant changes in performance seem plausible. When you switch to a different engine in might have different pathological cases. – CodesInChaos Jan 16 '16 at 14:01
  • @tkausl I was also thinking of a bug fix scenario. What if you overlooked something that was in your functional contract but the only way to fix it is to add a bunch of code and slow the algorithm a hit. With sorting, a profiler for quick sort and merge sort may say that quick sort is faster for smaller N. An implementer could change it for that reason, too – Frank Bryce Jan 16 '16 at 14:07
  • Your friend picked a terrible example to make this point. The whole raison d'etre of StringBuilder is to avoid string concatenations. If the functionality was made equivalent to str1 + str2 it would be utterly useless. – Rotem Jan 16 '16 at 14:20
  • @Rotem I agree with you! I'm not sure why he decided to argue about that. It got me second guessing myself, which led to this broader question. – Frank Bryce Jan 16 '16 at 16:06

Short answer: it is not true for libraries or tools "in general". Each vendor can guarantee for his library or tool whatever he wants. There are libraries and tools where the vendor does guarantee

  • functional equivalence and the equivalence of certain aspects of non-functional requirements
  • just functional equivalence, not more
  • only syntactical equivalence
  • none of the above

And even if a vendor guarantees you something for a specific version or version line of a product, noone can hinder him legally to create a new version or product line with a different API, or different non-functional behaviour. So the question "can it be changed" is not really the correct one, instead you should ask is "how likely is that for a specific tool or library?"

For your example of the StringBuilder class, IMHO it is absurdly unlikely that MS will change its run time behaviour within the .NET framework in a manner so the effort of writing such a class by yourself will ever be worth it. The cite of your friend sounds more like superstitious nonsense an overcautious misconception for me, at least for this case.

Microsoft added such a class explicitly to the .NET framework to provide a mutable alternative to the immutable String class with certain performance aspects in mind, the documentation of that class is very detailed about that. MS in the past tried to keep newer versions of the .NET framework mostly backwards compatible to older versions, even if that means not to fix certain bugs or live with some imperfectness. And changing the run time behaviour of a StringBuilder in a significant manner would not break only your program, but most probably ten thousands of other programs - StringBuilder is one of the central core classes of the framework, and widely used among the .NET ecosystem. That is nothing any sensible library vendor would change lightheartly. When they annoy their customers too much, customers start looking for a different vendor, and that will cost them money.

The same is true for lots of other tool or library vendors, and those which do not care for this risk to annoy their customers until they look for a different vendor.

To give you another example: the C++ standard library gives explicit specifications for the run time behaviour of std::sort, it guaranteed to be O(n * log(n)) for the average case, see Wikipedia.

And for question of "grep": I am pretty sure there already exist different implementations of grep from different older unix or unix-like systems, and I would be astonished if they all have the same run time behaviour. The Posix standard makes them have same command line switches, at least for any Posix-conform OS. However, today the fact Linux including GNU grep is so popular, you can probably rely even on its non-functional behaviour at least on any decent Linux system.

  • The standard (de facto or otherwise) for grep is POSIX. You'll find that almost all of the switches there date back at least as far as Unix V7, which was the first version that ported easily. – Blrfl Jan 16 '16 at 14:36
  • @Blrfl: thanks for the remark, changed my answer accordingly. – Doc Brown Jan 16 '16 at 17:36

...if you are reliant on such optimizations, then you should make your own ...

It's a bit of a tautology to say so, but code guarantees only what it guarantees. One of the purposes of having libraries is to form a boundary that's opaque to callers, and the only time there should be a complaint is when one of the guarantees isn't being met. (This is concept is at the core of design by contract.)

Your colleague is saying that if you become reliant on a particular implementation, you've established requirements that go beyond the original guarantees. That doesn't mean you have to write your own, but it does you can't switch to another implementation until you've verified that it meets all of the requirements.

If I use a library's Sort() function that has runtime O(n*log(n)), is it possible that a future version would change the runtime to O(n^2)?

Sure. I doubt anyone would do that intentionally unless someone said "I need you to make this code run slower." A future version might perform better, which is something most folks like. But, again, if you've dependent on the library to operate in a certain amount of time, a faster implementation won't meet your requirements and will break your software.

... wouldn't it be good practice for a library/API/tool developer to keep runtimes for the same calls similar over time?

Not really. The reductio ad absurdum implication would be that implementations should be immutable because someone may have become dependent on the incorrect behavior brought about by a bug. The only changes you could make would be the additions of functions that do completely new things or are modified versions of those that already exist (e.g. foo(), foo_version_2(), etc.). There are a few very rare cases where that's desirable, but most times if you think you need this, you should probably think again.

Good practice for library developers is to document changes in a way that library users can understand what's changed. Good practice for users of that library is to understand the changes and the effects on their own code before deploying them. Bad practice is to drop in a new version of a library just because one has become available.

All of this applies to whole programs the same way it applies to libraries. Most people expect that the -x switch in grep(1) will print only lines exactly matching the pattern. A change in that behavior between versions will break things that depend on it and require the dependencies to change or that the old version remain in place.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.