15

I had someone advise me to avoid repeatedly calling String.Length, because it was recalculated each time I called it. I had assumed that String.Length ran in O(1) time. Is String.Length more complex than that?

Matthew
  • 28,056
  • 26
  • 104
  • 170
  • 4
    I believe you're asking about the .NET `System.String.Length` property, since there is no such property in C#. – John Saunders May 14 '10 at 17:30
  • Related: http://stackoverflow.com/questions/151472/what-is-the-difference-between-string-empty-and/151481 – Brian R. Bondy May 14 '10 at 17:30
  • 1
    also related: http://stackoverflow.com/questions/717801/is-string-length-in-c-net-instant-variable – jball May 14 '10 at 17:33
  • John Saunders: Yep, I meant System.String.Length. Thanks for the fix. Is there any particularly reason to say the full name (System.String.Length) instead of just String.Length? Edit: Oh, I think you mean because System.String is part of .NET, rather than the C# language. – Matthew May 14 '10 at 17:33
  • Accessing String.Length is trivially slower than accessing a local variable. You should only worry about it if you have a tight loop where you're accessing it billions of times and you want to shave off a few seconds. On my machine, the difference between string.Length and a local variable was about 1.4 nanoseconds. Whether the string was 50 characters or 50 million characters made no difference. – Igby Largeman May 14 '10 at 18:24

6 Answers6

27

That's bad advice - String.Length is indeed O(1). It's not like strlen in C.

Admittedly it's not guaranteed in the docs as far as I can tell, but the immutability of strings makes it a pretty silly thing not to make O(1). (And not just O(1), but a very fast constant time too.)

Frankly if someone is giving that sort of advice, I would become a bit more skeptical about other advice they may provide too...

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • I'd really would look at the context first though, say the call is being unnecessarily in a loop with millions of iterations ... overall, in those cases is just good practice not to call a property if its the same for the whole loop. – eglasius May 14 '10 at 17:34
  • 6
    @Freddy: I disagree - if it's the simplest code and it's evaluating a very simple property which is going to be inlined, I'd rather do that than introduce a temporary local variable. In some cases (array lengths) the JIT does *better* using the property than with a temporary local... – Jon Skeet May 14 '10 at 17:37
  • @Freddy Rios, I don't know, but would not be surprised that the compiler knows strings are immutable and optimizes the code accordingly. It would, I think, be a rather easy optimization for a compiler. – tster May 14 '10 at 17:38
  • A decade later, .NET is open source so we can see the .NET Core implementation here: [String.cs#L754](https://github.com/dotnet/runtime/blob/5e7cfbf086a03d2613e2e390805470063836262b/src/libraries/System.Private.CoreLib/src/System/String.cs#L754). It is indeed constant time because, as strings are immutable, the length is cached. Note the code comment *This is an intrinsic function so that the JIT can recognise it specially and eliminate checks on character fetches in a loop... The actual code generated for this will be one instruction and will be inlined.* – dbc Sep 01 '22 at 20:48
5

String.Length is O(1). The reason people tell you not to call it in a loop is because it's a property access, which is the same as a method call. In reality one extra method call rarely makes any significant difference.

As always, don't start going through your code caching all calls to String.Length unless your profiler says it's the source of a performance problem.

Matti Virkkunen
  • 63,558
  • 9
  • 127
  • 159
3

Recall that strings are immutable. System.String.Length never changes.

John Saunders
  • 160,644
  • 26
  • 247
  • 397
3

No it does not recalculate. String type is immutable.

To take this further, as per the .net framework design guidelines, a property of an object that is very much static and non-volatile in nature would be designed as property. Should the property be of a volatile nature that needs recalculation on every call, it shall be made available as method.

you can take this rule while you attempt to check if a property takes enough processing cycles to attract your attention.

this. __curious_geek
  • 42,787
  • 22
  • 113
  • 137
2

As others have said String.Length is a constant property. If you really care about performance (or have significant iterations), you could assign its value to a local integer variable once, and read that many times (in a loop, etc.). This would give the optimizer a better chance of allocating this value to a CPU register. Accessing a property is a much more expensive operation than a stack variable or a register.

Simon Chadwick
  • 1,148
  • 6
  • 12
0

According to the internal comments, the String.Length property is a single instruction that does not run a for loop. Therefore, it is an O(1) operation.

Eric Hauser
  • 5,551
  • 3
  • 26
  • 29