Playing with strings and performance in C#

A few weeks ago, I was solving a problem at HackerRank and after completing a solution that ran  under 100 milliseconds, the program would still timeout during execution. HackerRank limit is usually 1 second, so something was taking more than 900ms.

It was the strings!

Yes, we know handling strings is costly, but this time there was no way around it.  At the final stage of the problem I had to construct a string over 200k chars long from an array of Boolean values that represented the bits of the number.  

Disclaimer: Strings are slow, mainly because they are immutable. Concatenating two strings, creates a third one and possibly 2 for the garbage collector to pickup.

Looking through the code I noticed I was simply using "+=" instead of StringBuilder.Append method. After using StringBuilder the solution was faster and the submission was approved. It was  fast now, but it got me thinking "how much faster indeed?" which ended with me measuring the performance of concatenating strings, because we always knew StringBuilder was faster than regular operation with strings but I still wanted to see the numbers.

I used C# and tested the same set of examples in NetCore and full .Net Framework. I did not notice any performance differences between the two of them.

What was measured?

I measured 3 ways to concatenate strings, and each of them in reverse mode. Here are the 6 variants:
  • Using the + operator. (str += "1";)
  • Using + operator to insert in front (str = "1"+str)
  • Using string.Concat (str = string.Concat(str,"1"))
  • Using string.Concat to insert in front (str = string.Concat("1",str))
  • Using StringBuilder.Append to add at the end
  • Using StringBuilder.Insert to place in front
Every operation was ran against data sets of multiple lengths, for 10, 20, 30, 40 and 50k characters. The chart below shows the results in milliseconds. 

It was a surprise to see that StringBuilder.Append is not only faster, but appears to be in constant time O(1). Also, to see that the Insert method is for certain sizes slower than other operations, so StringBuilder is not always faster.  

Now if we run the tests for a data set with 100k characters, we get a new surprise: the insert method starts being faster at a bit over 50k chars in length, with the other operations degenerating in performance. 



If you like competitive programming or have an interesting in high performance solutions, make sure to always measure. Do experiments a lot in code and test different scenarios. In my case, I had an array reversed so I walked the array backwards and used the Append method instead of Insert. That was the difference between failing or passing a problem.   

 Check the code for StringBuilder at GitHub. The implementation uses string.wstrcpy, while is blazing fast, this is still O(n). 

Comments

Post a Comment

Popular posts from this blog

Get-ChildItem vs Dir in PowerShell

Image
Batch as usual Recently I was in the need of modifying a huge amount of files across a network share. After installing Serviio media streaming service I noticed that it will crash "randomly". After checking the logs it was clear that ffmpeg was crashing when trying to open subtitle files that were not in the encoding indicated by the Serviio console. I needed a quick way to update all subtitle files to a common encoding, so I decided to convert all files to UTF8. Since I use a windows environment I went directly to PowerShell and wrote this.  Get-ChildItem -path .\ -filter *.srt -file  | ForEach-Object { (get-content $_.FullName) | Out-File $_.FullName -encoding utf8 } This worked almost right except for files with "[" or "]" (among other symbols) on the name or path. To solve it, just added the "-LiteralPath" switch to tell powershell not to consider any wildcards on the path name and just use it exactly as it is.  Get-ChildIt
Read more

The case for a 4 week sprint

Image
Every time we talk about SCRUM, the length of the sprint is stated as a period of "two to four weeks", rarely, however, have I seen people going outside of the 2 weeks. This is not written on stone of course, and while 3 weeks might seems odd, there is a benefit to using a longer period for your sprints.  Image is taken from scrum.org Without any hard data to back that decision, the answer I get from asking about this decision seems to be related to "delivery speed", we assume that because we deliver value to the business every 2 weeks, we are in a more "agile" environment. Well, that might not be so true in every sense or for every project. Let's break some arguments: 1. Sprint length is not equal to the speed of delivery There is more to the speed of development and delivery than the timeframe of the delivery cycle, in a world with DevOps and full CI/CD implemented for your project, you could (should?) actually deliver features every single day all t
Read more

NODE.js fs.readFile and the BOM marker

Working on a ReactJS project, got a small glitch while trying to read a JSON file and parse it as a javascript object. getDataObject() { var dataString = fs.readFileSync("./json/data.json", "utf8"); return JSON.parse(dataString); } output:   SyntaxError: Unexpected token   After checking, double and triple checking again that the file was correct I went deeper and realized that "fs.readFileSync" was returning me the BOM for the UTF file at the beginning of the string. So we just need to strip it out. getDataObject() { var dataString = fs.readFileSync("./json/data.json", "utf8"); return JSON.parse(dataString.replace(/^\uFEFF/, "")); } I then checked and there are "packages" for this, however I don't think is proper to just import a new dependency just to fix something this small. The big issue here is why is this considered correct. The BOM is not
Read more