CODEWITHSUNDEEP
c#.netstringcomplexity-theorybig-o
Matthew
Matthew

Reputation: 29236

What order of time does the .NET System.String.Length property take?

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?

Upvotes: 16

Views: 3042

Answers (6)

this. __curious_geek
this. __curious_geek

Reputation: 43217

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.

Upvotes: 3

Simon Chadwick
Simon Chadwick

Reputation: 1148

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.

Upvotes: 2

Eric Hauser
Eric Hauser

Reputation: 5581

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.

Upvotes: 0

Matti Virkkunen
Matti Virkkunen

Reputation: 65166

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.

Upvotes: 5

Jon Skeet
Jon Skeet

Reputation: 1502786

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...

Upvotes: 28

John Saunders
John Saunders

Reputation: 161821

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

Upvotes: 3

Related Questions