5 ms·

The n^2 argument the author points at is a red herring. The reason this is an invalid criticism of the benchmark is that both benchmarks are using the same quer

The n^2 argument the author points at is a red herring. The reason this is an invalid criticism of the benchmark is that both benchmarks are using the same query structure, so theyre both n^2. The author himself admits later on that the real issue is allocations. However, they posit that allocating of structs is done using a different allocator than classes. I dont know enough about C# to know if this is true, but even so, the advice that "structs are more performant overall" still holds...so this article seems to be mostly clickbait.

agent281 3y ago
I disagree. Using an n^2 algorithm will exaggerate the difference between the two data types at higher values of n. Using a linear algorithm would give a more consistent perspective on the relative performance of the two data types.
neonsunset 3y ago
The criticism aims at poorly written benchmarking code that fails to evaluate its own claim and uses an anti-pattern. You may want to read the article in full. Also, structs do not use an allocator, this is basics of many programming languages - they simply represent a structure in memory, which by default is placed on the stack. Think an integer variable in a local method scope.
- astrange 3y ago
  Allocation with a GC is typically not any more expensive than being "on the stack", so I don't think something being "on the stack" is a useful distinction. (And in a language with stackful closures the stack itself is GCed.)
  - neonsunset 3y ago
    This is incorrect in multiple ways. C# stack is completely native, identical to C++ or Rust. The following factors contribute to “structs being faster”: - Heap allocations have go to through allocation calls, which need to find free memory, possibly zero it out, and then return pointer (reference) to it, both in managed and unmanaged languages, with C# being much faster at small object allocation (tlv read, pointer bump, and object header write) while unmanaged wins for large allocations instead (you don't have to go through LOH and extra cost associated with it). In comparison, stack is already zeroed for structs that are written to it, and those are just movs (or ldr/ldp's and str/stp's in case of arm64), and even then, only when spilled to stack at all (see below) - Stack may not be the best way to describe it - think "local exclusively owned memory" which means that compilers, no matter how strict, can reason about the exact lifetimes of local values and the changes that happen to them. This means that all struct values can be promoted to CPU registers and never touch memory unlike with heap allocations, where multiple reads of the same property may require repeated dereferencing to account for the fact that object memory may be globally observable. This in turn applies to optimizations like CSE which can elide multiple identical checks against struct values knowing they won't change between operations. - In .NET, generic method bodies for class-based generic arguments are shared (closest example in Rust - Box<dyn Trait>-based dispatch but with less overhead). However, struct generic arguments force method body monomorphization aka emitting specialized version for the exact generic type, which allows to write code with zero-cost abstractions the same way one would do in Rust with generics or in C++ with templates.
    - whoknowsidont 3y ago
      >C# stack is completely native, identical to C++ or Rust. This is absolutely not true. Where are you getting this from? Pray tell, what you think this is: https://github.com/dotnet/runtime https://github.com/dotnet/runtime
    - astrange 3y ago
      > In comparison, stack is already zeroed for structs that are written to it This is not possible. A stack is a bump pointer allocator and is the same as any other bump pointer allocator. This includes having to decide when/if to zero memory. (The best time is on free because of memory compression, but most implementations don't do this.) It's certainly not true that the unused part of the stack is always already zeroed; what if you already used it once? (But it is true if you zero on free.) > - Stack may not be the best way to describe it - think "local exclusively owned memory" which means that compilers, no matter how strict, can reason about the exact lifetimes of local values and the changes that happen to them. This is escape analysis and applies to anything with a known lifetime.
      - neonsunset 3y ago
        This is .NET and not JVM, my previous comment describes how it works today. Be it C++, Rust or C#, the necessary space on stack is usually reserved in function/method prologue when known statically. Additionally, because C# guarantees that all local variables/memory are initialized, the corresponding stack space is pre-zeroed (it is efficient since it is done with widest applicable writes - scalar, sse/avx(2/512)/neon, etc. (arm64 has dczva which kicks in above certain threshold). Regardless, the cost is not in bumping the offset/ptr or zeroing out the memory, it is in going through the allocator call (even if it's inlined, you're still executing more code) and the book-keeping required for heap allocations in general (both .NET's GC and allocators like Mimalloc do it), and then there is subsequent cost for tracking and collecting objects in the case of GC. In addition, .NET does not do escape analysis because, again, it is not JVM - while it may be added in the future, it is (relatively) unprofitable to do today because allocation traffic is far lower since everything isn't a potentially escaping object, and structs or stack-allocated buffers are often used in performance-sensitive code (or where it makes sense to do so in general). The way .NET views the objects is similar to the way C++ views heap allocated data, albeit with less aggressive (and often unsound or UB) assumptions compared to GCC. I cannot stress this enough that while JVM's escape analysis does lead to object stack-allocation, the reasoning the compilers can do about state of the data on stack is what e.g. JVM gets as a result of doing escape analysis, not vice versa. And other "unmanaged" languages are subject to similar limitations when it comes to stack vs heap.
nullzzz 3y ago
To me the point seems that the benchmark is so misguided and missed the obvious error in the usage on LINQ that the results are not relevant. You should not take perf advice from the authors of that course.
throwaheyy 3y ago
> I dont know enough about C# to know if this is true Do you know enough about C# to realize that .Select() by itself doesn’t materialize the collections, making the benchmark completely nonsensical? The query structure is the same because it was a failed attempt to evaluate classes vs. structs, not one query vs. another.
- quietbritishjim 3y ago
  The comment you're replying to is talking about the second benchmark, which does access the enumeration so does materialize the select().
mjr00 3y ago
The original benchmark author is just really unclear what they're trying to benchmark. "Class vs struct performance" is meaningless, because performance at what? The first benchmark does nothing, as the article points out. The second benchmark tests the performance of large numbers of object creations; but why is ElementAt even being called in a loop there? It's confusing since it's irrelevant to what actually ends up taking time. If you're benchmarking the time it takes to create the struct/class objects, just write a benchmark that does that and don't include random other code! And "structs are more performant" isn't even a correct conclusion; they're pass-by-value, so you could construct benchmarks where the copy time outweighs heap memory allocation time, eg constructing a large object once and passing it to a function many times.
- quietbritishjim 3y ago
  I don't think you've really refuted the parent comment here. But, what you have done, is written a much better blog post than the original article :-)
  - mjr00 3y ago
    I wasn't really trying to refute the parent! I agree that the article author focusing on LINQ making things secretly n^2 is a red herring (though important to know). But the more fundamental problem is the benchmark being very unclear in what it's benchmarking.
- ablob 3y ago
  If struct copies are you problem you can always pass it by ref, so even that isn't an easy claim to make.
sitharus 3y ago
The odd thing is this behaviour is documented. Classes reference types, are always heap allocated, and passed by reference. Structs are value types, allocated inline (that is inline in the containing object/array, or on the stack for local variables), and passed by value. Allocation time is going to be around the same for both types due to the GC, but there are performance implications depending on what you do later. In particular you can avoid garbage collection with appropriate use of structs but pass by value can mitigate those improvements.
deleted 3y ago
[deleted]

agent281 3y ago

I disagree. Using an n^2 algorithm will exaggerate the difference between the two data types at higher values of n. Using a linear algorithm would give a more consistent perspective on the relative performance of the two data types.

neonsunset 3y ago

The criticism aims at poorly written benchmarking code that fails to evaluate its own claim and uses an anti-pattern. You may want to read the article in full. Also, structs do not use an allocator, this is basics of many programming languages - they simply represent a structure in memory, which by default is placed on the stack. Think an integer variable in a local method scope.

astrange 3y ago
Allocation with a GC is typically not any more expensive than being "on the stack", so I don't think something being "on the stack" is a useful distinction. (And in a language with stackful closures the stack itself is GCed.)
- neonsunset 3y ago
  This is incorrect in multiple ways. C# stack is completely native, identical to C++ or Rust. The following factors contribute to “structs being faster”: - Heap allocations have go to through allocation calls, which need to find free memory, possibly zero it out, and then return pointer (reference) to it, both in managed and unmanaged languages, with C# being much faster at small object allocation (tlv read, pointer bump, and object header write) while unmanaged wins for large allocations instead (you don't have to go through LOH and extra cost associated with it). In comparison, stack is already zeroed for structs that are written to it, and those are just movs (or ldr/ldp's and str/stp's in case of arm64), and even then, only when spilled to stack at all (see below) - Stack may not be the best way to describe it - think "local exclusively owned memory" which means that compilers, no matter how strict, can reason about the exact lifetimes of local values and the changes that happen to them. This means that all struct values can be promoted to CPU registers and never touch memory unlike with heap allocations, where multiple reads of the same property may require repeated dereferencing to account for the fact that object memory may be globally observable. This in turn applies to optimizations like CSE which can elide multiple identical checks against struct values knowing they won't change between operations. - In .NET, generic method bodies for class-based generic arguments are shared (closest example in Rust - Box<dyn Trait>-based dispatch but with less overhead). However, struct generic arguments force method body monomorphization aka emitting specialized version for the exact generic type, which allows to write code with zero-cost abstractions the same way one would do in Rust with generics or in C++ with templates.
  - whoknowsidont 3y ago
    >C# stack is completely native, identical to C++ or Rust. This is absolutely not true. Where are you getting this from? Pray tell, what you think this is: https://github.com/dotnet/runtime https://github.com/dotnet/runtime
  - astrange 3y ago
    > In comparison, stack is already zeroed for structs that are written to it This is not possible. A stack is a bump pointer allocator and is the same as any other bump pointer allocator. This includes having to decide when/if to zero memory. (The best time is on free because of memory compression, but most implementations don't do this.) It's certainly not true that the unused part of the stack is always already zeroed; what if you already used it once? (But it is true if you zero on free.) > - Stack may not be the best way to describe it - think "local exclusively owned memory" which means that compilers, no matter how strict, can reason about the exact lifetimes of local values and the changes that happen to them. This is escape analysis and applies to anything with a known lifetime.
    - neonsunset 3y ago
      This is .NET and not JVM, my previous comment describes how it works today. Be it C++, Rust or C#, the necessary space on stack is usually reserved in function/method prologue when known statically. Additionally, because C# guarantees that all local variables/memory are initialized, the corresponding stack space is pre-zeroed (it is efficient since it is done with widest applicable writes - scalar, sse/avx(2/512)/neon, etc. (arm64 has dczva which kicks in above certain threshold). Regardless, the cost is not in bumping the offset/ptr or zeroing out the memory, it is in going through the allocator call (even if it's inlined, you're still executing more code) and the book-keeping required for heap allocations in general (both .NET's GC and allocators like Mimalloc do it), and then there is subsequent cost for tracking and collecting objects in the case of GC. In addition, .NET does not do escape analysis because, again, it is not JVM - while it may be added in the future, it is (relatively) unprofitable to do today because allocation traffic is far lower since everything isn't a potentially escaping object, and structs or stack-allocated buffers are often used in performance-sensitive code (or where it makes sense to do so in general). The way .NET views the objects is similar to the way C++ views heap allocated data, albeit with less aggressive (and often unsound or UB) assumptions compared to GCC. I cannot stress this enough that while JVM's escape analysis does lead to object stack-allocation, the reasoning the compilers can do about state of the data on stack is what e.g. JVM gets as a result of doing escape analysis, not vice versa. And other "unmanaged" languages are subject to similar limitations when it comes to stack vs heap.

nullzzz 3y ago

To me the point seems that the benchmark is so misguided and missed the obvious error in the usage on LINQ that the results are not relevant. You should not take perf advice from the authors of that course.

throwaheyy 3y ago

> I dont know enough about C# to know if this is true Do you know enough about C# to realize that .Select() by itself doesn’t materialize the collections, making the benchmark completely nonsensical? The query structure is the same because it was a failed attempt to evaluate classes vs. structs, not one query vs. another.

quietbritishjim 3y ago
The comment you're replying to is talking about the second benchmark, which does access the enumeration so does materialize the select().

mjr00 3y ago

The original benchmark author is just really unclear what they're trying to benchmark. "Class vs struct performance" is meaningless, because performance at what? The first benchmark does nothing, as the article points out. The second benchmark tests the performance of large numbers of object creations; but why is ElementAt even being called in a loop there? It's confusing since it's irrelevant to what actually ends up taking time. If you're benchmarking the time it takes to create the struct/class objects, just write a benchmark that does that and don't include random other code! And "structs are more performant" isn't even a correct conclusion; they're pass-by-value, so you could construct benchmarks where the copy time outweighs heap memory allocation time, eg constructing a large object once and passing it to a function many times.

quietbritishjim 3y ago
I don't think you've really refuted the parent comment here. But, what you have done, is written a much better blog post than the original article :-)
- mjr00 3y ago
  I wasn't really trying to refute the parent! I agree that the article author focusing on LINQ making things secretly n^2 is a red herring (though important to know). But the more fundamental problem is the benchmark being very unclear in what it's benchmarking.
ablob 3y ago
If struct copies are you problem you can always pass it by ref, so even that isn't an easy claim to make.

sitharus 3y ago

The odd thing is this behaviour is documented. Classes reference types, are always heap allocated, and passed by reference. Structs are value types, allocated inline (that is inline in the containing object/array, or on the stack for local variables), and passed by value. Allocation time is going to be around the same for both types due to the GC, but there are performance implications depending on what you do later. In particular you can avoid garbage collection with appropriate use of structs but pass by value can mitigate those improvements.

deleted 3y ago

[deleted]