[C#] Performance gets crushed(-30%) on Intel Celeron® J1800 #583
Replies: 4 comments 15 replies
-
|
@ItalyToast I think the size of the L1 cache also matters. At least on my hardware it does. I have 32kB L1 cache. Methods that do calculations in that size like my own You can run getconf -a on Linux to get your size and the size of the Celeron is 24kb according to the published report in PrimeView. |
Beta Was this translation helpful? Give feedback.
-
|
@fvbakel My assumtion was that we are accessing the memory linearly and we would always have prefetched data but that is not actually true when we get to factors bigger than 128 💡. But if thats the case why wouldnt that also affect the rust solution? I read the source code for and the striped ones does some funky stuff with how the bits are ordered thats maybe what gives it better usage of L1, I'll have to dig deeper here. |
Beta Was this translation helpful? Give feedback.
-
|
I think you could make this discussion a general discussion, not just specific to C#, about performance differences, especially between machines. I know that my Julia solution's performance can differ wildly between machines, so it might be good to consolidate information as to what factors affect performance here. That's one reason why I opened #584, to improve consistency of results between machines since I think my optimizations were getting close to CPU quirks instead of overall performance improvements. I had a discussion over at the Julia Discourse about why my loop was faster on my machine, and it had something to do with the registers maybe being pressured a little bit. I don't really understand it all, but all I know is that a lot of the solutions in this repository are almost as optimized as can be, so the CPU features really start to matter and can affect how we optimize our solutions. The Rust solution's striped algorithm is designed, if I understand correctly, to make better use of the cache. It's also why they implemented "striped-blocks" to work with CPUs with small cache sizes, like the Raspberry Pi. |
Beta Was this translation helpful? Give feedback.
-
|
Another factor might be that your CPU is a lot faster (~2.5 GHz vs ~3.9 GHz), meaning that instructions that are used to set up loops, for example, might have a lot less overhead on your machine than the Celeron. Most of the time is spent on the clearing loop, so the faster you can set up the loop with the other instructions, the more the inner loop matters. If your C# version has a high overhead but a faster loop, it would probably be faster on fast machines. If the Rust version has a low overhead but a slightly slower loop, on slower machines the lessened overhead might make up for the slower loop. I think that's what happened with my solution, where the I haven't examined the assembly for either your C# solution or the Rust solution, so I can't verify what I'm speculating. |
Beta Was this translation helpful? Give feedback.
-
I tried that in C on my hardware, it gives a 4% improvement. |
Beta Was this translation helpful? Give feedback.
-
Of course! Why didnt I think of that 😅
Is that the 1mill sieve on your hardware or on the leaderboard? |
Beta Was this translation helpful? Give feedback.
-
|
I ran rust solution 1 and c# solution 4 with 10 000 000 as the sieve size and the c#. The sieve size in memory is 625k and most of the sieve should be outside of the L1 for my CPU. Here are the results: Rust solution 1: bit-storage Passes: 515, Threads: 1, Time: 5.0085105896, Average: 0.0097252633, Limit: 10000000, Counts: 664579, Valid: Pass bit-storage-rotate Passes: 529, Threads: 1, Time: 5.0036330223, Average: 0.0094586639, Limit: 10000000, Counts: 664579, Valid: bit-storage-striped Passes: 490, Threads: 1, Time: 5.0074648857, Average: 0.0102193160, Limit: 10000000, Counts: 664579, Valid: C# solution 4: Passes: 568, Time: 5.0030142, Avg: 0.008808123591549295, Limit: 10000000, Count: 664579, Valid: True Hmm, I even tried 1 000 000 000 as the sieve size but that didnt improve the standing for rust on my machine. the best implementation for rust was bit-storage-rotate on 3.35 sec / pass and c# got 3.17 sec / pass. Im running on windows but doing the runs through docker. Hmm this is kinda frustrating 😠. Maybe a PI is the way to go anyway? |
Beta Was this translation helpful? Give feedback.
-
That is on my hardware, I7, 3th gen. The solution is not on the leader board, but I just made a plane 1 milion sieve and just tested the difference if you go back and forth. The source code is here: https://github.com/fvbakel/Primes/blob/feature/Cextra/PrimeC/solution_98/primes_bit7.c |
Beta Was this translation helpful? Give feedback.
-
|
@ItalyToast the original I'm also going to check what the influence of upgrading to from dotnet core 3.1 to dotnet 5.0 for C# was. I had some unexpected performance regressions that required a bit of hacking on some projects at work. |
Beta Was this translation helpful? Give feedback.
-
|
For what it's worth, here are the results from running a few solutions on Ubuntu 20.04 under WSL2 (without Docker, since I don't have the space for it) on a machine with an Intel Core i5-9300H. CPU-Z reports 32KBytes of both L1 D-Cache and L1 I-Cache (8-way set associative, 64-byte line size), 256KBytes of L2 Cache (4-way set associative, 64-byte line size) and 8MBytes of L3 Cache (16-way set associative, 64-bye line size). I used @ItalyToast's csharp-docker-net5 branch used in #603 since I don't have .NET Core 3.1 currently installed on WSL2. PrimeCSharp/solution_4 (best run out of 3): 9048 passes per 5 seconds I've shortened the output here since there's a lot of unnecessary information. This only concerns the single-threaded implementations. And just for fun, here's my PrimeJulia/solution_3 which I really only optimized using this machine. |
Beta Was this translation helpful? Give feedback.
-
|
I understand the striped version a little bit better now. Since it does not need to worry about shifting the bits that it is marking, the thight loop is superfast, if the cache can keep up. Why did he choose 8 stripes? Since you can keep the same mask for each iteration in the tight loop, going bigger would only mean more overhead since we need to clear each stripe. Each stripe got a setup cost and more stripes would not be a benefit for the tight loop but would give you more overhead. |
Beta Was this translation helpful? Give feedback.
-
|
I actually implemented a striped variant now, lets see how it holds up on the celeron. #610 |
Beta Was this translation helpful? Give feedback.
-
|
Interesting. I'm still figuring out how to implement it in Julia. Nice to see more new techniques being ported to different languages! Let's see how things play out, I guess. |
Beta Was this translation helpful? Give feedback.
-
|
Take a look at my implementation, its much simpler IMO and keeps the normal bitarray representation. |
Beta Was this translation helpful? Give feedback.
-
|
Alright, I'll be sure to do that, thanks! |
Beta Was this translation helpful? Give feedback.
-
I was very excited and waiting in excitement to see my performance results pop up on PrimeView yesterday. Then the numbers showed: # 28 2680. 👀 What just happened... I was expecting to see it around mike-barber_bit-storage-striped since my machine (Intel I7 4770K) beats it by a couple of of hundred passes/sec. 2680 passes/s vs 3799 passes/s thats a 30%+ deviation from the expected numbers. Both runs were on docker with "docker run solution_x" where x is the solution number.
Maybe this is just difference in hardware that causes these discrepancies. But if so what is the difference? The L2 cache is bigger than the sieve on both processors. The sieve is 62.5kb and both the celeron and 4770k have 1mb / 256k of L2 cache respectively.
One theory is that the allocation and GC in C# would consume more memory and thus have an impact. The allocations will stay nice and tidy and only cause 1 or 2 cache misses per pass but we would build on the heap until we get a GC. The GC would get a lot of cache misses BUT the GC is a on a background thread if im not mistaken and should not impact performance. Rust in this case would alloc one sieve, calculate, dealloc and the next iteration would alloc in the same space that we just deallocated.
Anyone got some ideas about what is going on or how to debug these performance issues? Since I dont have access to daves machine Im not sure how to proceed.
The code in question: CSharp/solution_4
Here is the spec sheet for the two processors:
Celeron J1800
I7 4770K
Beta Was this translation helpful? Give feedback.
All reactions