5 ms·

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 duri

by OskarS 7y ago

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?

zamalek 7y ago
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.
- ygra 7y ago
  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?
  - thrower123 7y ago
    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.
  - josteink 7y ago
    > 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.
- antisemiotic 7y ago
  >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 https://www.fstar-lang.org I hope some of that will trickle down to F# and C# some day.
- mpartel 7y ago
  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.
  - josteink 7y ago
    > 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.
    - sreque 7y ago
      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-net.aspx/ https://afana.me/archive/2015/07/10/memory-barriers-in-dot-n...
    - Someone 7y ago
      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/ 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)
- chrisseaton 7y ago
  > 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.
legulere 7y ago
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.

by OskarS 7y ago

zamalek 7y ago

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.

ygra 7y ago
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?
- thrower123 7y ago
  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.
- josteink 7y ago
  > 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.
antisemiotic 7y ago
>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 https://www.fstar-lang.org I hope some of that will trickle down to F# and C# some day.
mpartel 7y ago
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.
- josteink 7y ago
  > 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.
  - sreque 7y ago
    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-net.aspx/ https://afana.me/archive/2015/07/10/memory-barriers-in-dot-n...
  - Someone 7y ago
    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/ 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)
chrisseaton 7y ago
> 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.

legulere 7y ago

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.