Any idea why C# is so much slower than Java and Go in related_post_gen benchmark? #93225
-
|
Does anyone have any ideas why C# AOT is so much slower than Java (GraalVM) and Go in related_post_gen benchmark? I'm just interested to learn what is the culprit. I tried optimizing it but I can't get any meaningful performance improvements and I don't understand where the big difference comes from. Do other two compilers just produce more optimized assembly, or is one used type from the standard library that is less optimized, or UTF16 vs UFT8 strings? Or is there some glaring issue in C# implementation that I'm missing? Snapshot of benchmark results
|
Beta Was this translation helpful? Give feedback.
Replies: 6 comments 26 replies
-
|
Might be interesting to compare nativeaot |
Beta Was this translation helpful? Give feedback.
-
|
These results are with NativeAOT. |
Beta Was this translation helpful? Give feedback.
-
|
Few things...
|
Beta Was this translation helpful? Give feedback.
-
|
CC @MichalStrehovsky for nativeaot comparison |
Beta Was this translation helpful? Give feedback.
-
|
I wanted to suggest not using Native AOT since dynamic PGO has a decent chance to make wonders, but even the 30k entry run is not enough for dynamic PGO to pay for itself unfortunately. So we're stuck with native AOT. One would think native AOT should be comparable with Java/GraalVM, but GraalVM uses checked-in PGO data (two thirds of the related_post_gen repo size is Graal's optimization data in default.iprof). If I was the repo maintainer, I would not have accepted that contribution because it sets a bad precented (e.g. Rust doesn't use PGO yet, but I assume it soon will, and so will all the other languages). We don't have a usable PGO for native AOT in .NET 8, so we can't check in our giant blob. My suggestions:
This diff seemed to help on .NET 8. There's absolutely no reason to stackalloc for something that runs once and the more explicit bounds seemed to help RyuJIT figure out some bounds check can be elided. I don't know if it helps on .NET 7. All of the above applies to .NET 8. diff --git a/csharp/Program.cs b/csharp/Program.cs
index f2fb00c..b4223ee 100644
--- a/csharp/Program.cs
+++ b/csharp/Program.cs
@@ -32,13 +32,13 @@ foreach (var (tag, postIds) in tagMapTemp)
tagMap[tag] = postIds.ToArray();
}
-Span<RelatedPosts> allRelatedPosts = new RelatedPosts[postsCount];
-Span<byte> taggedPostCount = stackalloc byte[postsCount];
-Span<(byte Count, int PostId)> top5 = stackalloc (byte Count, int PostId)[topN];
+var allRelatedPosts = new RelatedPosts[postsCount];
+var taggedPostCount = new byte[postsCount];
+var top5 = new (byte Count, int PostId)[topN];
-for (var i = 0; i < postsCount; i++)
+for (var i = 0; i < taggedPostCount.Length; i++)
{
- taggedPostCount.Clear(); // reset counts
+ Array.Fill(taggedPostCount, default); // reset counts
foreach (var tag in posts[i].Tags)
{
@@ -49,11 +49,11 @@ for (var i = 0; i < postsCount; i++)
}
taggedPostCount[i] = 0; // Don't count self
- top5.Clear();
+ Array.Fill(top5, default);
byte minTags = 0;
// custom priority queue to find top N
- for (var j = 0; j < postsCount; j++)
+ for (var j = 0; j < taggedPostCount.Length; j++)
{
byte count = taggedPostCount[j];
@@ -76,7 +76,7 @@ for (var i = 0; i < postsCount; i++)
var topPosts = new Post[topN];
// Convert indexes back to Post references. skip even indexes
- for (int j = 0; j < 5; j ++)
+ for (int j = 0; j < topPosts.Length; j ++)
{
topPosts[j] = posts[top5[j].PostId];
} |
Beta Was this translation helpful? Give feedback.
-
|
Here are results I get with suggested changes. There seems to be a performance regression in NativeAOT 8.0 compared to NativeAOT 7.0 for NativeAOT 7.0 → NativeAOT 8.0 (RC1):
Codeusing System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text.Json;
using System.Text.Json.Serialization;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
public static class Program
{
public static void Main()
{
var summary = BenchmarkRunner.Run<Bench>();
}
}
[SimpleJob(RuntimeMoniker.NativeAot70, iterationCount: 200)]
[SimpleJob(RuntimeMoniker.NativeAot80, iterationCount: 200)]
[SimpleJob(RuntimeMoniker.Net70, iterationCount: 200, warmupCount: 200)]
[SimpleJob(RuntimeMoniker.Net80, iterationCount: 200, warmupCount: 200)]
public class Bench
{
private List<Post> posts;
private RelatedPosts[] allRelatedPosts;
[IterationSetup]
public void IterationSetup()
{
posts = JsonSerializer.Deserialize(File.ReadAllText(@"posts.json"), MyJsonContext.Default.ListPost)!;
}
[IterationCleanup]
public void IterationCleanup()
{
File.WriteAllText(@"related_posts_csharp.json",
JsonSerializer.Serialize(allRelatedPosts.ToArray(), MyJsonContext.Default.RelatedPostsArray));
}
[Benchmark(Baseline = true)]
public void Original()
{
const int topN = 5;
var postsCount = posts.Count;
var sw = Stopwatch.StartNew();
// slower when int[] is used
var tagMapTemp = new Dictionary<string, LinkedList<int>>(100);
for (var i = 0; i < postsCount; i++)
{
foreach (var tag in posts[i].Tags)
{
// single lookup
ref var stack = ref CollectionsMarshal.GetValueRefOrAddDefault(tagMapTemp, tag, out _);
stack ??= new LinkedList<int>();
stack.AddLast(i);
}
}
var tagMap = new Dictionary<string, int[]>(tagMapTemp.Count);
foreach (var (tag, postIds) in tagMapTemp)
{
tagMap[tag] = postIds.ToArray();
}
allRelatedPosts = new RelatedPosts[postsCount];
Span<byte> taggedPostCount = stackalloc byte[postsCount];
Span<(byte Count, int PostId)> top5 = stackalloc (byte Count, int PostId)[topN];
for (var i = 0; i < postsCount; i++)
{
taggedPostCount.Clear(); // reset counts
foreach (var tag in posts[i].Tags)
{
foreach (var otherPostIdx in tagMap[tag])
{
taggedPostCount[otherPostIdx]++;
}
}
taggedPostCount[i] = 0; // Don't count self
top5.Clear();
byte minTags = 0;
// custom priority queue to find top N
for (var j = 0; j < postsCount; j++)
{
byte count = taggedPostCount[j];
if (count > minTags)
{
int upperBound = topN - 2;
while (upperBound >= 0 && count > top5[upperBound].Count)
{
top5[upperBound + 1] = top5[upperBound];
upperBound--;
}
top5[upperBound + 1] = (count, j);
minTags = top5[topN - 1].Count;
}
}
var topPosts = new Post[topN];
// Convert indexes back to Post references. skip even indexes
for (int j = 0; j < 5; j++)
{
topPosts[j] = posts[top5[j].PostId];
}
allRelatedPosts[i] = new RelatedPosts
{
Id = posts[i].Id,
Tags = posts[i].Tags,
Related = topPosts
};
}
sw.Stop();
Console.WriteLine($"Processing time (w/o IO): {sw.Elapsed.TotalMilliseconds}ms");
}
[Benchmark()]
public void Tanner1_NoTagMapTemp()
{
const int topN = 5;
Span<Post> postsSpan = CollectionsMarshal.AsSpan(posts);
var postsCount = posts.Count;
var sw = Stopwatch.StartNew();
var tagMap = new Dictionary<string, List<int>>(100);
for (var i = 0; i < postsCount; i++)
{
foreach (var tag in postsSpan[i].Tags)
{
// single lookup
ref var stack = ref CollectionsMarshal.GetValueRefOrAddDefault(tagMap, tag, out _);
stack ??= new List<int>();
stack.Add(i);
}
}
allRelatedPosts = new RelatedPosts[postsCount];
Span<byte> taggedPostCount = stackalloc byte[postsCount];
Span<(byte Count, int PostId)> top5 = stackalloc (byte Count, int PostId)[topN];
for (var i = 0; i < postsCount; i++)
{
taggedPostCount.Clear(); // reset counts
var post = postsSpan[i];
foreach (var tag in post.Tags)
{
foreach (var otherPostIdx in CollectionsMarshal.AsSpan(tagMap[tag]))
{
taggedPostCount[otherPostIdx]++;
}
}
taggedPostCount[i] = 0; // Don't count self
top5.Clear();
byte minTags = 0;
// custom priority queue to find top N
for (var j = 0; j < postsCount; j++)
{
byte count = taggedPostCount[j];
if (count > minTags)
{
int upperBound = topN - 2;
while (upperBound >= 0 && count > top5[upperBound].Count)
{
top5[upperBound + 1] = top5[upperBound];
upperBound--;
}
top5[upperBound + 1] = (count, j);
minTags = top5[topN - 1].Count;
}
}
var topPosts = new Post[topN];
Span<Post> topPostsSpan = topPosts;
// Convert indexes back to Post references.
for (int j = 0; j < 5; j++)
{
topPostsSpan[j] = postsSpan[top5[j].PostId];
}
allRelatedPosts[i] = new RelatedPosts
{
Id = post.Id,
Tags = post.Tags,
Related = topPosts
};
}
sw.Stop();
Console.WriteLine($"Processing time (w/o IO): {sw.Elapsed.TotalMilliseconds}ms");
}
[Benchmark]
public void Tanner2_NoTagMapTempAndWoBoundsCheck()
{
const int TOP_N = 5;
const int INITIAL_TAGGED_COUNT_SIZE = 100;
var sw = Stopwatch.StartNew();
Span<Post> postsSpan = CollectionsMarshal.AsSpan(posts);
var tagMap = new Dictionary<string, List<int>>(INITIAL_TAGGED_COUNT_SIZE);
for (var i = 0; i < postsSpan.Length; i++)
{
foreach (var tag in Unsafe.Add(ref MemoryMarshal.GetReference(postsSpan), i).Tags.AsSpan())
{
ref var tags = ref CollectionsMarshal.GetValueRefOrAddDefault(tagMap, tag, out _);
tags ??= new List<int>(postsSpan.Length);
tags.Add(i);
}
}
allRelatedPosts = new RelatedPosts[postsSpan.Length];
Span<RelatedPosts> allRelatedPostsSpan = allRelatedPosts;
Span<int> taggedPostCount = new int[postsSpan.Length];
Span<int> top5 = new int[TOP_N * 2];
for (var i = 0; i < postsSpan.Length; i++)
{
taggedPostCount.Clear();
foreach (var tag in Unsafe.Add(ref MemoryMarshal.GetReference(postsSpan), i).Tags.AsSpan())
{
foreach (var otherPostIdx in CollectionsMarshal.AsSpan(tagMap[tag]))
{
Unsafe.Add(ref MemoryMarshal.GetReference(taggedPostCount), otherPostIdx)++;
}
}
Unsafe.Add(ref MemoryMarshal.GetReference(taggedPostCount), i) = 0;
top5.Clear();
int minTags = 0;
// custom priority queue to find top N
for (var j = 0; j < postsSpan.Length; j++)
{
int count = Unsafe.Add(ref MemoryMarshal.GetReference(taggedPostCount), j);
if (count > minTags)
{
int upperBound = (TOP_N - 2) * 2;
while (upperBound >= 0 && count > Unsafe.Add(ref MemoryMarshal.GetReference(top5), upperBound))
{
Unsafe.Add(ref MemoryMarshal.GetReference(top5), upperBound + 2) =
Unsafe.Add(ref MemoryMarshal.GetReference(top5), upperBound);
Unsafe.Add(ref MemoryMarshal.GetReference(top5), upperBound + 3) =
Unsafe.Add(ref MemoryMarshal.GetReference(top5), upperBound + 1);
upperBound -= 2;
}
int insertPos = upperBound + 2;
Unsafe.Add(ref MemoryMarshal.GetReference(top5), insertPos) = count;
Unsafe.Add(ref MemoryMarshal.GetReference(top5), insertPos + 1) = j;
minTags = Unsafe.Add(ref MemoryMarshal.GetReference(top5), TOP_N * 2 - 2);
}
}
var topPosts = new Post[TOP_N];
for (var j = 1; j < 10; j += 2)
{
topPosts[j / 2] = Unsafe.Add(ref MemoryMarshal.GetReference(postsSpan),
Unsafe.Add(ref MemoryMarshal.GetReference(top5), j));
}
var post = Unsafe.Add(ref MemoryMarshal.GetReference(postsSpan), i);
var relatedPost = new RelatedPosts
{
Id = post.Id,
Tags = post.Tags,
Related = topPosts
};
Unsafe.Add(ref MemoryMarshal.GetReference(allRelatedPostsSpan), i) = relatedPost;
}
sw.Stop();
Console.WriteLine($"Processing time (w/o IO): {sw.Elapsed.TotalMilliseconds}ms");
}
[Benchmark()]
public void Michael_NoStackalloc()
{
const int topN = 5;
var postsCount = posts.Count;
var sw = Stopwatch.StartNew();
// slower when int[] is used
var tagMapTemp = new Dictionary<string, LinkedList<int>>(100);
for (var i = 0; i < postsCount; i++)
{
foreach (var tag in posts[i].Tags)
{
// single lookup
ref var stack = ref CollectionsMarshal.GetValueRefOrAddDefault(tagMapTemp, tag, out _);
stack ??= new LinkedList<int>();
stack.AddLast(i);
}
}
var tagMap = new Dictionary<string, int[]>(tagMapTemp.Count);
foreach (var (tag, postIds) in tagMapTemp)
{
tagMap[tag] = postIds.ToArray();
}
allRelatedPosts = new RelatedPosts[postsCount];
var taggedPostCount = new byte[postsCount];
var top5 = new (byte Count, int PostId)[topN];
for (var i = 0; i < taggedPostCount.Length; i++)
{
Array.Fill(taggedPostCount, default); // reset counts
foreach (var tag in posts[i].Tags)
{
foreach (var otherPostIdx in tagMap[tag])
{
taggedPostCount[otherPostIdx]++;
}
}
taggedPostCount[i] = 0; // Don't count self
Array.Fill(top5, default);
byte minTags = 0;
// custom priority queue to find top N
for (var j = 0; j < taggedPostCount.Length; j++)
{
byte count = taggedPostCount[j];
if (count > minTags)
{
int upperBound = topN - 2;
while (upperBound >= 0 && count > top5[upperBound].Count)
{
top5[upperBound + 1] = top5[upperBound];
upperBound--;
}
top5[upperBound + 1] = (count, j);
minTags = top5[topN - 1].Count;
}
}
var topPosts = new Post[topN];
// Convert indexes back to Post references. skip even indexes
for (int j = 0; j < topPosts.Length; j++)
{
topPosts[j] = posts[top5[j].PostId];
}
allRelatedPosts[i] = new RelatedPosts
{
Id = posts[i].Id,
Tags = posts[i].Tags,
Related = topPosts
};
}
sw.Stop();
Console.WriteLine($"Processing time (w/o IO): {sw.Elapsed.TotalMilliseconds}ms");
}
}
public record struct Post
{
[JsonPropertyName("_id")] public string Id { get; set; }
[JsonPropertyName("title")] public string Title { get; set; }
[JsonPropertyName("tags")] public string[] Tags { get; set; }
}
public record RelatedPosts
{
[JsonPropertyName("_id")] public string Id { get; set; }
[JsonPropertyName("tags")] public string[] Tags { get; set; }
[JsonPropertyName("related")] public Post[] Related { get; set; }
}
[JsonSerializable(typeof(Post))]
[JsonSerializable(typeof(List<Post>))]
[JsonSerializable(typeof(RelatedPosts))]
[JsonSerializable(typeof(RelatedPosts[]))]
public partial class MyJsonContext : JsonSerializerContext { } |
Beta Was this translation helpful? Give feedback.
-
|
Weird that my suggestion doesn't seem to help. I saw a improvement. I did measure for the 30k entries only scenario. Dynamic pgo in .net 8 has the best chance to catch up on the largest benchmark and since all benchmark times get added up, this one has the most weight and makes most sense to optimize for. |
Beta Was this translation helpful? Give feedback.
-
|
I tested for 5k posts as that file is already included in the repo and original test was for 5k posts, but I agree optimizing for 30k makes the most sense. I'm learning a lot here. PGO explains the performance of Java. For C# JIT, PGO does seem to kick in For comparison, on my machine Go benchmark runs in ~11–12ms. It seems Go compiler is able to optimize away bounds checking. (Just a wild guess, as I'm not really familiar how compilers work). I find it interesting that it's able to do it without PGO. I understand that NativeAOT in .NET is still very young, so I'm keeping my fingers crossed it will continue to be improved like in the pass few versions. |
Beta Was this translation helpful? Give feedback.
-
|
One optimization that crossed my mind was possibly due to string-deduping the Json parsing. I don't know if any of the other languages libraries attempt to do that to any degree, but I know that S.T.Json does not: Since the inner-most loop is doing a dictionary lookup on the tag string, it would benefit if the tags were de-duped during deserialization, as there are only 28 distinct tags . My understanding is that string.GetHashCode gets cached per instance, which would avoid having to hash all the duplicated strings during the "processing" phase, since it was already done during the serialization phase. Additionally, the dictionary lookup needs to do the full string equality check for duplicate strings rather than the reference equality fast-path that would be done when de-duped. Testing this on my machine: standard deserializer (dupe tags): custom deserializer (deduped tags): So, it saves about 16% processing time. I used Ben.StringIntern for the string-deduping. I should mention that the overall time is reduced because my custom deserialization code ignores the "title" property since it isn't actually needed to produce the correct output. |
Beta Was this translation helpful? Give feedback.
-
|
Interesting optimization. It doesn't look like Go and Java implementations are doing this, so this can't be the source of the difference. Still, it's a nice performance improvement. |
Beta Was this translation helpful? Give feedback.
-
|
Made a PR to make the benchmark faster (jinyus/related_post_gen#304). Now it's in top 3 in the latest results. |
Beta Was this translation helpful? Give feedback.
-
|
That's terrific @MichalStrehovsky! Biggest performance gain seems to come from changes done to the custom priority queue. I'm guessing that compiler manages to optimize (remove) bound checks for tight while loop? What seems to be the reason compiler managed to optimize this version, but not the original version? It would be great, if you would write a post explaining optimization process like this. From the detective work, on how to find a C# code that's not getting optimally optimized by the compiler, to the code shaping process that shows what can we try, to shape the code in a way that the compiler can optimize it. I would be thrilled to learn to do something like this. C# now gets really impressive result in the benchmark. |
Beta Was this translation helpful? Give feedback.
-
|
@danmoseley I'll try to do a simple concurrent version using the vectorized version of the custom priority queue that was done by @MichalStrehovsky, as SIMD is allowed for multi-threaded implementations. |
Beta Was this translation helpful? Give feedback.
-
Oh, I have reasons to believe it's even more faster than graal than what the results show right now: jinyus/related_post_gen#322 |
Beta Was this translation helpful? Give feedback.
-
|
@danmoseley I added PR for concurrent version (jinyus/related_post_gen#325). Just adding a simple Original single-threaded implementations was |
Beta Was this translation helpful? Give feedback.
-
|
From the table at the bottom of https://github.com/jinyus/related_post_gen, C# is now fastest or near to it on the parallel benchmark. Nice work @zigzag312 . (I don't know how optimized the other entries are though.) |
Beta Was this translation helpful? Give feedback.
-
SIMD alone is unlikely to help much. It needs to use multiple threads or it will be a very slow version.
The bounds check were getting removed in the original version too, but the problem was that the code was jumping around too much. Here's the summary:
The hot path is that the next count of posts is lower than what we already have in the queue. But as you can see, the hot path starts at the top, then does a jump from 00007FF7612BD217 to 07FF7612BD280 (because count is lower), then it increments j, compares it with the limit and jumps back from 00007FF7612BD284 to 07FF7612BD20C at the top. The PR added an inner loop for this that doesn't do so much jumping around. The hot loop is just: And we go from top to bottom, many many times (the branch at 00007FF692DAE55B is not taken most of the time, and the one at 00007FF692DAE566 is taken pretty much always). |
Beta Was this translation helpful? Give feedback.
-
|
I must admit, I have never thought of using Disassembly window in VS while debugging and using a breakpoint to get to the correct place. I only used tools for viewing the IL. This is going to help so much! Running with debugging in release mode will run in JIT mode and show assembly produced by JIT even when |
Beta Was this translation helpful? Give feedback.
-
|
Run the AOT executable under the native debugger (as if you're debugging C++). You should still be able to hit breakpoints set in C# code (the symbols are mapping the instructions back to C# sources). The disassembly window should work basically the same as shown above. |
Beta Was this translation helpful? Give feedback.
Made a PR to make the benchmark faster (jinyus/related_post_gen#304). Now it's in top 3 in the latest results.