Hacker News Reader

Comment by OskarS | Hacker News Reader

This is good to know, but fairly unsurprising. The interesting case is List<T>. The .Count property is actually a function call, and the value could change during the loop. If you don’t mutate the list, is it smart enough to both inline the function call and hoist the value out as an invariant?

View on HN

Ist doesn‘t even need to be a function call: Accessing a class field repeatedly in a tight loop is slower than a local variable.

There's no mathematical way for it to know that you won't modify (especially remove). The developer would have to express that by, say, iterating over the internal array directly.

This is veering into C and undefined behavior territory, but with List<T> there's a guarantee that you cannot modify the list while enumerating over it, so could the compiler theoretically assume that when using foreach?

I assume it does, if you try to do so it throws an exception. It's a rather common footgun with multi-threaded code until you've lost a few toes to it. People are always writing naive producer-consumer queues with an unlocked List<T> backing it until they learn better.

> with List<T> there's a guarantee that you cannot modify the list while enumerating over it, so could the compiler theoretically assume that when using foreach?

No such guarantee exists.

The only guarantee there is is that enumeration will throw on next iteration after a modification.

The compiler can assume nothing.

>There's no mathematical way for it to know that you won't modify

That's an overstatement. That's currently impossible in C#, but Microsoft is working on it in F*: https://www.fstar-lang.org I hope some of that will trickle down to F# and C# some day.

A good compiler can in a large number of cases infer that it won't modify.

The compiler can explore the call graph of the loop body and find out which methods might be called on the list, and then check that none of those methods write to the list's internal length variable.

How deeply and precisely the compiler (or JIT) analyzes the code in an attept to prove that the length won't change involves a tradeoff in compilation speed, but I'd expect .NET to have found a pretty good sweet spot by now.

> A good compiler can in a large number of cases infer that it won't modify.

For a single thread that should be doable. But that’s not mathematically covering all bases is it?

And how can the compiler know if the relevant list is not accessed from multiple threads? I’m pretty sure that’s next to impossible and definitely not worth the complexity for such a small optimisation.

Compilers have been assuming single-threaded memory access by default since, forever? If you want your code to work with multiple threads, then you have to explicitly write code to do so. Otherwise, the compiler is liable to store things in registers, shuffle instructions around, and do whatever it feels like to optimize performance for the single-threaded case. If the compiler didn't do this, then every program would run many many times slower than it does.

Doing some quick googling, this article seems to explain things well from the perspective of a C# developer: https://afana.me/archive/2015/07/10/memory-barriers-in-dot-n...

It often is easy to know it isn’t accessed elsewhere (escape analysis can prove it for local variables), and compilers do check the simple cases (search term: “lock elison”).

For example, see https://shipilev.net/jvm/anatomy-quarks/19-lock-elision/.

This also can help when using java’s StringBuffer, which is thread-safe, but can often be ‘converted’ into a non-thread-safe variant by the compiler (the existence of StringBuilder shows that ‘often’ at least in some version of Java wasn’t often enough, though)

> There's no mathematical way for it to know that you won't modify (especially remove).

This is not true. Here's three examples:

A positive result from escape analysis and then scalar replacement of aggregates.

A positive result from partial escape analysis until after this point in the program.

Speculation that list is not modified, and deoptimisation if it is.

Reply on news.ycombinator.com