Why C++ instead of C#?

[klx]

"Allocating memory from the managed heap is faster than unmanaged memory allocation..

Sure, but not allocating at all is faster. The problem is when you release these objects and the managed heap needs to be collected.

For lists of reference types it can be faster to use a new List<T>

Sounds like a bad idea if you ask me, since there will be two memory references, one in the list, and one to the reference, the last one may not be contiguous in memory in which case there's an expensive cache miss on every lookup (see my recent post "Emanuel's Proximity Table" for why this is bad).

[amanjpro]

From msdn:
"Allocating memory from the managed heap is faster than unmanaged memory allocation. Because the runtime allocates memory for an object by adding a value to a pointer, it's almost as fast as allocating memory from the stack. In addition, because new objects that are allocated consecutively are stored contiguously in the managed heap, an application can access the objects quickly."

https://docs.microsoft.com/en-us/dotnet ... ndamentals

That might be unintuitive to some having made bad experiences with managed languages in the past but it matches with my experience. At least when using the .Net Runtime. C# in Unity is a different matter entirely.

An example to illustrate the smartness of the runtime and the garbage collector: For each node I explore in the search I create a new Position instance with the new operator. With 1M NPS you'd expect a lot of work for the garbage collector because it has to allocate and free memory for a million objects. But if you use a memory profiler you realize that the runtime is reusing the instances. If you're searching to depth 12 you just need 12 at the same time.

Another example: For lists of reference types it can be faster to use a new List<T> than to reuse an existing one by clearing it. Clearing actually visits every element in the lists and sets the pointer to null. But just letting the list go out of scope achieves the same thing much cheaper. The runtime can clean up the instance and all the references it contains directly.

To avoid walking the array to reset it, I basically have a struct with the following:

Code: Select all

type Array struct {
  Elements []int
  Size int
  Index int
}

When I reset it, I simply set Size to 0, and Size is "guaranteed" to be always less than length of Elements, when walking the array Index always goes upto Size (not the length of the array), but I can always add elements to the index Size and then increment Size
In my case, restting the array is O(1)

[lithander]

To avoid walking the array to reset it, I basically have a struct with the following:

Code: Select all

type Array struct {
  Elements []int
  Size int
  Index int
}

When I reset it, I simply set Size to 0, and Size is "guaranteed" to be always less than length of Elements, when walking the array Index always goes upto Size (not the length of the array), but I can always add elements to the index Size and then increment Size
In my case, restting the array is O(1)

That's why I made my example about lists containing reference types specifically. Your's is about int which is a value type. The reason why you need to set the reference to null in addition to setting size to 0 in C# (and other managed languages) is that you need to let the garbace collector know that they are not needed anymore. Otherwise the "cleared" portion of the array will still keep them alive.

Discussions like that actually create the urge in me to make an engine (or at least a move generator or something like that) in C# that optimizes for raw speed instead of what MinimalChess does. I'm getting curious about just how much slower C# would really be compared to C++. And my hunch is that many people would be surprised by how small the difference actually is. But klx is not wrong saying that no allocations are better than managed allocations - regardless of how fast the runtime actually can provide them. So the optimized result wouldn't look like a normal C# program anymore, I fear.

[amanjpro]

To avoid walking the array to reset it, I basically have a struct with the following:

Code: Select all

type Array struct {
  Elements []int
  Size int
  Index int
}

When I reset it, I simply set Size to 0, and Size is "guaranteed" to be always less than length of Elements, when walking the array Index always goes upto Size (not the length of the array), but I can always add elements to the index Size and then increment Size
In my case, restting the array is O(1)

That's why I made my example about lists containing reference types specifically. Your's is about int which is a value type. The reason why you need to set the reference to null in addition to setting size to 0 in C# (and other managed languages) is that you need to let the garbace collector know that they are not needed anymore. Otherwise the "cleared" portion of the array will still keep them alive.

Discussions like that actually create the urge in me to make an engine (or at least a move generator or something like that) in C# that optimizes for raw speed instead of what MinimalChess does. I'm getting curious about just how much slower C# would really be compared to C++. And my hunch is that many people would be surprised by how small the difference actually is. But klx is not wrong saying that no allocations are better than managed allocations - regardless of how fast the runtime actually can provide them. So the optimized result wouldn't look like a normal C# program anymore, I fear.

I see your point, somehow in my engine the only lists I have are for int or int aliases really... but yeah, it is hard to measure a language, based on another language's best practices, or even an engine based on another... to do a fair assessment, you need to build something for the assessment

[klx]

I'm getting curious about just how much slower C# would really be compared to C++.

yeah, it is hard to measure a language

So the best answer to that question is "Benchmarks Game", a series of programs where folks have submitted solutions in different languages, competing for fastest possible. You can assume that the best solutions there are indicative of what can be achieved in each language. Of course, some tasks are more or less suitable for each language, as we can see in the range of results; C++ is 1-5x faster. In my experience, 2x is a reasonable estimate for things like a chess engine.

With that said, C# programmers may well find themselves writing slower C++ code, since they are unaware of how to write fast C++ code. And some programmers are not performance aware at all -- thinking for example of the one in the other thread with a 23,500 nodes / second engine -- in which case there are more important things to focus on than choice of language (ie: there is a close to 1000x performance potential available by optimizing the code, but only 2x by switching to C++).

So the optimized result wouldn't look like a normal C# program anymore, I fear.

You may also find this in C++. The fastest possible code is not always idiomatic or pretty.

[Mergi]

You may also find this in C++. The fastest possible code is not always idiomatic or pretty.

C++ should suffer from this way less than most other languages though, as it's goal already is to be as efficient as possible. If you stick to the STL and "proper" C++ code, the performance gains from using some dirty tricks or trying to avoid certain constructs should be minimal.

[klx]

C++ should suffer from this way less than most other languages though, as it's goal already is to be as efficient as possible. If you stick to the STL and "proper" C++ code, the performance gains from using some dirty tricks or trying to avoid certain constructs should be minimal.

Well, I dunno, if you look at the fastest C++ program to solve the Mandelbrot problem on the page I linked, it's not exactly pretty. This is what super fast C++ code may look like. The "proper" solution you can see here and is 34x slower. If you look at the code, it's not even "proper" since they manually compute the norm instead of using std::norm, claiming it leads to a 5-7x speedup. So a "proper proper" solution may be ~200x slower than that optimized monstrosity.

[Mergi]

I don't think that's a fair comparison, the "ugly" code is just using SIMD instructions, which is perfectly fine c++ (although perhaps a bit hard to read if you don't work with them often), and some tricky multithreading. By it's nature, it's not possible to efficiently parallelize alpha-beta search, so multithreading in most engines is just a very simple lazy SMP where you don't have to worry much about data races or anything really, and SIMD instructions aren't used outside of NNUE stuff as far as i know. But in any case, comparing speed of a 100 lines long hyper specific program and a chess engine and claiming possible 200x speedup is nonsense. You simply cannot use either SIMD nor multithreading in such a capacity in a chess engine.

[klx]

claiming possible 200x speedup is nonsense

I did not claim 200x faster for chess engine. In my response above, I estimated 2x between C# and C++.

200x faster was in response to your statement "the performance gains from using some dirty tricks or trying to avoid certain constructs should be minimal". This example shows that in general, this is not correct. Separate code paths for each vector width with hand-optimized SIMD code is certainly a "dirty trick", and not "sticking to proper C++" if you ask me.

Just FYI, that slow solution is all SIMD too, you often don't see it in the code (nor need to use it), since the compiler SIMDs the code for you where appropriate.

[R. Tomasi]

You may also find this in C++. The fastest possible code is not always idiomatic or pretty.

C++ should suffer from this way less than most other languages though, as it's goal already is to be as efficient as possible. If you stick to the STL and "proper" C++ code, the performance gains from using some dirty tricks or trying to avoid certain constructs should be minimal.

I second that. In my experience modern compilers are very very good at optimizing and the more you stick to recommended design patterns, the better it will understand your code and do it's job. Granted, on rare occasions you can do "ugly" code that performs better than "pretty" code, but usually that is then tied to one particular platform and one particular compiler.

Concerning the the question of C# or C++ being the better language, i would say that both have their pros and cons. I really do love C#, and whenever the target platform allows it (you will need the .net runtime or some replacement like mono) and the problem at hands is not totally time critical. That's because in C# I am simply much more productive. It takes less time to code the same thing for me, and the .net standard library is fantastic. Obviously if you really need that last bit of performance you should go for C++, however most people would be surprised how good a well written C# program can perform. It's not worlds apart from C++ imho.