search

dotnet / runtime

.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.
https://docs.microsoft.com/dotnet/core/
MIT License
14.91k stars 4.63k forks source link

Is it time to replace Marvin? #85206

Open stephentoub opened 1 year ago

stephentoub commented 1 year ago

We could, for example, bring XxHash3 down into corelib from System.IO.Hashing, delete Marvin, and use XxHash3 in place of it.

public static IEnumerable<int> GetLengths()
{
    for (int i = 0; i < 100; i++) yield return i;
    yield return 1000;
}

[ParamsSource(nameof(GetLengths))]
public int Length { get; set; }

private string _str;
private static readonly long s_seed = BitConverter.ToInt64(RandomNumberGenerator.GetBytes(8));

[GlobalSetup]
public void Setup() => _str = RandomNumberGenerator.GetString("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", Length);

[Benchmark(Baseline = true)]
public int Marvin() => string.GetHashCode(_str);

[Benchmark]
public int XXH3() => (int)(long)XxHash3.HashToUInt64(MemoryMarshal.AsBytes(_str.AsSpan()), s_seed);
Method Length Mean Error StdDev Ratio
Marvin 0 2.205 ns 0.0046 ns 0.0038 ns 1.00
XXH3 0 3.522 ns 0.0164 ns 0.0137 ns 1.60
Marvin 1 2.806 ns 0.0078 ns 0.0073 ns 1.00
XXH3 1 3.705 ns 0.0072 ns 0.0060 ns 1.32
Marvin 2 2.916 ns 0.0054 ns 0.0048 ns 1.00
XXH3 2 3.776 ns 0.0082 ns 0.0073 ns 1.29
Marvin 3 2.924 ns 0.0086 ns 0.0067 ns 1.00
XXH3 3 3.774 ns 0.0105 ns 0.0098 ns 1.29
Marvin 4 3.950 ns 0.0100 ns 0.0084 ns 1.00
XXH3 4 3.768 ns 0.0059 ns 0.0049 ns 0.95
Marvin 5 3.968 ns 0.0333 ns 0.0260 ns 1.00
XXH3 5 3.105 ns 0.0157 ns 0.0139 ns 0.78
Marvin 6 4.825 ns 0.0063 ns 0.0053 ns 1.00
XXH3 6 3.094 ns 0.0037 ns 0.0031 ns 0.64
Marvin 7 4.826 ns 0.0101 ns 0.0090 ns 1.00
XXH3 7 3.093 ns 0.0038 ns 0.0034 ns 0.64
Marvin 8 5.869 ns 0.0092 ns 0.0081 ns 1.00
XXH3 8 3.091 ns 0.0064 ns 0.0060 ns 0.53
Marvin 9 5.872 ns 0.0086 ns 0.0071 ns 1.00
XXH3 9 5.247 ns 0.0116 ns 0.0103 ns 0.89
Marvin 10 6.910 ns 0.0133 ns 0.0111 ns 1.00
XXH3 10 5.250 ns 0.0102 ns 0.0085 ns 0.76
Marvin 11 6.910 ns 0.0105 ns 0.0098 ns 1.00
XXH3 11 5.226 ns 0.0085 ns 0.0071 ns 0.76
Marvin 12 8.040 ns 0.0130 ns 0.0115 ns 1.00
XXH3 12 5.219 ns 0.0109 ns 0.0091 ns 0.65
Marvin 13 8.039 ns 0.0188 ns 0.0167 ns 1.00
XXH3 13 5.299 ns 0.0761 ns 0.0712 ns 0.66
Marvin 14 9.243 ns 0.0462 ns 0.0433 ns 1.00
XXH3 14 5.303 ns 0.0476 ns 0.0422 ns 0.57
Marvin 15 9.234 ns 0.0630 ns 0.0589 ns 1.00
XXH3 15 5.316 ns 0.0696 ns 0.0651 ns 0.58
Marvin 16 10.584 ns 0.0520 ns 0.0434 ns 1.00
XXH3 16 5.274 ns 0.0573 ns 0.0536 ns 0.50
Marvin 17 10.615 ns 0.0586 ns 0.0548 ns 1.00
XXH3 17 7.277 ns 0.1186 ns 0.1110 ns 0.69
Marvin 18 11.830 ns 0.0869 ns 0.0813 ns 1.00
XXH3 18 7.220 ns 0.0899 ns 0.0750 ns 0.61
Marvin 19 11.777 ns 0.0336 ns 0.0315 ns 1.00
XXH3 19 7.251 ns 0.0765 ns 0.0679 ns 0.62
Marvin 20 13.162 ns 0.1112 ns 0.1040 ns 1.00
XXH3 20 7.324 ns 0.1073 ns 0.1004 ns 0.56
Marvin 21 13.123 ns 0.0572 ns 0.0535 ns 1.00
XXH3 21 7.266 ns 0.0735 ns 0.0651 ns 0.55
Marvin 22 14.351 ns 0.0717 ns 0.0635 ns 1.00
XXH3 22 7.206 ns 0.0646 ns 0.0604 ns 0.50
Marvin 23 14.368 ns 0.0944 ns 0.0883 ns 1.00
XXH3 23 7.261 ns 0.0846 ns 0.0791 ns 0.51
Marvin 24 15.678 ns 0.0413 ns 0.0387 ns 1.00
XXH3 24 7.243 ns 0.1070 ns 0.0894 ns 0.46
Marvin 25 15.667 ns 0.0455 ns 0.0403 ns 1.00
XXH3 25 7.266 ns 0.0909 ns 0.0851 ns 0.46
Marvin 26 16.983 ns 0.0701 ns 0.0656 ns 1.00
XXH3 26 7.329 ns 0.1174 ns 0.1098 ns 0.43
Marvin 27 16.978 ns 0.0798 ns 0.0746 ns 1.00
XXH3 27 7.230 ns 0.0865 ns 0.0766 ns 0.43
Marvin 28 18.209 ns 0.0697 ns 0.0618 ns 1.00
XXH3 28 7.226 ns 0.1110 ns 0.0866 ns 0.40
Marvin 29 18.188 ns 0.0426 ns 0.0356 ns 1.00
XXH3 29 7.200 ns 0.0965 ns 0.0856 ns 0.40
Marvin 30 19.492 ns 0.0686 ns 0.0573 ns 1.00
XXH3 30 7.200 ns 0.0304 ns 0.0270 ns 0.37
Marvin 31 19.417 ns 0.0479 ns 0.0374 ns 1.00
XXH3 31 8.962 ns 0.1872 ns 0.1659 ns 0.46
Marvin 32 20.672 ns 0.1128 ns 0.1000 ns 1.00
XXH3 32 7.503 ns 0.1780 ns 0.3165 ns 0.37
Marvin 33 20.814 ns 0.1463 ns 0.1296 ns 1.00
XXH3 33 9.921 ns 0.0378 ns 0.0335 ns 0.48
Marvin 34 21.951 ns 0.0495 ns 0.0439 ns 1.00
XXH3 34 9.354 ns 0.0592 ns 0.0525 ns 0.43
Marvin 35 23.116 ns 0.2080 ns 0.1737 ns 1.00
XXH3 35 9.289 ns 0.1670 ns 0.1562 ns 0.40
Marvin 36 23.245 ns 0.0868 ns 0.0678 ns 1.00
XXH3 36 9.122 ns 0.0169 ns 0.0132 ns 0.39
Marvin 37 23.272 ns 0.0736 ns 0.0574 ns 1.00
XXH3 37 9.226 ns 0.1643 ns 0.1456 ns 0.40
Marvin 38 24.480 ns 0.0279 ns 0.0233 ns 1.00
XXH3 38 9.602 ns 0.0235 ns 0.0220 ns 0.39
Marvin 39 24.544 ns 0.0472 ns 0.0419 ns 1.00
XXH3 39 9.124 ns 0.0486 ns 0.0454 ns 0.37
Marvin 40 26.297 ns 0.4920 ns 0.4109 ns 1.00
XXH3 40 9.123 ns 0.0446 ns 0.0372 ns 0.35
Marvin 41 25.857 ns 0.0798 ns 0.0666 ns 1.00
XXH3 41 9.113 ns 0.0240 ns 0.0200 ns 0.35
Marvin 42 27.123 ns 0.0506 ns 0.0448 ns 1.00
XXH3 42 9.082 ns 0.0336 ns 0.0298 ns 0.33
Marvin 43 27.116 ns 0.0918 ns 0.0767 ns 1.00
XXH3 43 9.102 ns 0.0319 ns 0.0266 ns 0.34
Marvin 44 28.390 ns 0.0551 ns 0.0430 ns 1.00
XXH3 44 9.344 ns 0.1681 ns 0.2127 ns 0.33
Marvin 45 28.286 ns 0.1756 ns 0.1557 ns 1.00
XXH3 45 9.174 ns 0.0874 ns 0.0775 ns 0.32
Marvin 46 29.300 ns 0.0890 ns 0.0695 ns 1.00
XXH3 46 9.131 ns 0.0370 ns 0.0289 ns 0.31
Marvin 47 29.392 ns 0.2965 ns 0.2774 ns 1.00
XXH3 47 9.179 ns 0.0755 ns 0.0631 ns 0.31
Marvin 48 30.552 ns 0.0832 ns 0.0778 ns 1.00
XXH3 48 9.119 ns 0.0384 ns 0.0359 ns 0.30
Marvin 49 31.003 ns 0.2855 ns 0.2670 ns 1.00
XXH3 49 11.157 ns 0.1705 ns 0.1595 ns 0.36
Marvin 50 32.171 ns 0.1526 ns 0.1353 ns 1.00
XXH3 50 10.954 ns 0.0641 ns 0.0599 ns 0.34
Marvin 51 31.982 ns 0.1082 ns 0.1012 ns 1.00
XXH3 51 10.994 ns 0.0646 ns 0.0505 ns 0.34
Marvin 52 33.574 ns 0.1167 ns 0.1034 ns 1.00
XXH3 52 11.150 ns 0.2129 ns 0.1991 ns 0.33
Marvin 53 33.289 ns 0.1263 ns 0.0986 ns 1.00
XXH3 53 11.628 ns 0.1974 ns 0.1750 ns 0.35
Marvin 54 34.830 ns 0.1631 ns 0.1362 ns 1.00
XXH3 54 10.989 ns 0.0533 ns 0.0498 ns 0.32
Marvin 55 34.834 ns 0.2934 ns 0.2450 ns 1.00
XXH3 55 10.954 ns 0.0450 ns 0.0399 ns 0.31
Marvin 56 35.928 ns 0.1376 ns 0.1220 ns 1.00
XXH3 56 11.043 ns 0.1518 ns 0.1267 ns 0.31
Marvin 57 36.067 ns 0.0865 ns 0.0676 ns 1.00
XXH3 57 10.992 ns 0.0619 ns 0.0579 ns 0.30
Marvin 58 37.230 ns 0.2899 ns 0.2570 ns 1.00
XXH3 58 10.965 ns 0.0591 ns 0.0524 ns 0.29
Marvin 59 37.265 ns 0.1673 ns 0.1565 ns 1.00
XXH3 59 11.418 ns 0.0478 ns 0.0447 ns 0.31
Marvin 60 39.014 ns 0.4613 ns 0.4315 ns 1.00
XXH3 60 11.224 ns 0.1864 ns 0.1744 ns 0.29
Marvin 61 38.295 ns 0.0890 ns 0.0743 ns 1.00
XXH3 61 11.053 ns 0.0562 ns 0.0469 ns 0.29
Marvin 62 40.999 ns 0.3287 ns 0.3074 ns 1.00
XXH3 62 11.011 ns 0.0409 ns 0.0342 ns 0.27
Marvin 63 40.162 ns 0.4329 ns 0.4050 ns 1.00
XXH3 63 11.069 ns 0.0757 ns 0.0708 ns 0.28
Marvin 64 41.214 ns 0.1653 ns 0.1465 ns 1.00
XXH3 64 11.011 ns 0.0790 ns 0.0701 ns 0.27
Marvin 65 41.048 ns 0.1866 ns 0.1654 ns 1.00
XXH3 65 12.981 ns 0.2273 ns 0.3111 ns 0.32
Marvin 66 42.330 ns 0.0583 ns 0.0545 ns 1.00
XXH3 66 13.466 ns 0.1692 ns 0.1321 ns 0.32
Marvin 67 42.295 ns 0.1306 ns 0.1158 ns 1.00
XXH3 67 12.810 ns 0.0710 ns 0.0554 ns 0.30
Marvin 68 44.611 ns 0.1313 ns 0.1097 ns 1.00
XXH3 68 12.774 ns 0.0894 ns 0.0836 ns 0.29
Marvin 69 43.565 ns 0.1541 ns 0.1441 ns 1.00
XXH3 69 12.736 ns 0.0426 ns 0.0377 ns 0.29
Marvin 70 44.838 ns 0.1492 ns 0.1246 ns 1.00
XXH3 70 12.764 ns 0.0706 ns 0.0626 ns 0.28
Marvin 71 44.679 ns 0.2256 ns 0.1884 ns 1.00
XXH3 71 12.774 ns 0.0658 ns 0.0584 ns 0.29
Marvin 72 46.242 ns 0.1360 ns 0.1206 ns 1.00
XXH3 72 13.756 ns 0.0441 ns 0.0412 ns 0.30
Marvin 73 46.221 ns 0.0975 ns 0.0912 ns 1.00
XXH3 73 13.707 ns 0.0539 ns 0.0450 ns 0.30
Marvin 74 47.326 ns 0.0998 ns 0.0833 ns 1.00
XXH3 74 13.672 ns 0.0472 ns 0.0441 ns 0.29
Marvin 75 47.355 ns 0.0720 ns 0.0639 ns 1.00
XXH3 75 15.349 ns 0.0567 ns 0.0443 ns 0.32
Marvin 76 48.792 ns 0.2150 ns 0.1795 ns 1.00
XXH3 76 13.923 ns 0.2677 ns 0.2504 ns 0.29
Marvin 77 49.093 ns 0.4068 ns 0.3805 ns 1.00
XXH3 77 13.853 ns 0.1196 ns 0.1118 ns 0.28
Marvin 78 49.633 ns 0.2275 ns 0.2016 ns 1.00
XXH3 78 13.760 ns 0.1350 ns 0.1262 ns 0.28
Marvin 79 50.116 ns 0.1726 ns 0.1614 ns 1.00
XXH3 79 13.729 ns 0.0465 ns 0.0413 ns 0.27
Marvin 80 51.202 ns 0.0328 ns 0.0290 ns 1.00
XXH3 80 14.814 ns 0.0745 ns 0.0622 ns 0.29
Marvin 81 51.313 ns 0.2195 ns 0.2053 ns 1.00
XXH3 81 14.803 ns 0.0397 ns 0.0352 ns 0.29
Marvin 82 52.436 ns 0.1511 ns 0.1262 ns 1.00
XXH3 82 14.768 ns 0.0900 ns 0.0798 ns 0.28
Marvin 83 52.408 ns 0.1683 ns 0.1492 ns 1.00
XXH3 83 14.786 ns 0.0993 ns 0.0880 ns 0.28
Marvin 84 53.937 ns 0.0650 ns 0.0507 ns 1.00
XXH3 84 14.786 ns 0.0309 ns 0.0274 ns 0.27
Marvin 85 54.101 ns 0.4325 ns 0.3834 ns 1.00
XXH3 85 14.741 ns 0.0440 ns 0.0343 ns 0.27
Marvin 86 55.323 ns 0.2775 ns 0.2317 ns 1.00
XXH3 86 14.788 ns 0.0435 ns 0.0363 ns 0.27
Marvin 87 55.093 ns 0.1377 ns 0.1149 ns 1.00
XXH3 87 14.729 ns 0.0300 ns 0.0234 ns 0.27
Marvin 88 55.894 ns 0.1049 ns 0.0930 ns 1.00
XXH3 88 15.776 ns 0.0403 ns 0.0377 ns 0.28
Marvin 89 56.322 ns 0.1114 ns 0.0987 ns 1.00
XXH3 89 15.770 ns 0.0329 ns 0.0291 ns 0.28
Marvin 90 57.563 ns 0.0939 ns 0.0784 ns 1.00
XXH3 90 15.788 ns 0.0382 ns 0.0358 ns 0.27
Marvin 91 57.267 ns 0.0740 ns 0.0656 ns 1.00
XXH3 91 15.773 ns 0.0193 ns 0.0161 ns 0.28
Marvin 92 58.407 ns 0.1212 ns 0.1074 ns 1.00
XXH3 92 15.971 ns 0.2320 ns 0.1937 ns 0.27
Marvin 93 58.557 ns 0.1270 ns 0.1126 ns 1.00
XXH3 93 17.170 ns 0.1486 ns 0.1317 ns 0.29
Marvin 94 59.852 ns 0.2075 ns 0.1839 ns 1.00
XXH3 94 16.016 ns 0.1614 ns 0.1510 ns 0.27
Marvin 95 61.040 ns 0.1310 ns 0.1094 ns 1.00
XXH3 95 15.816 ns 0.0612 ns 0.0478 ns 0.26
Marvin 96 61.263 ns 0.2978 ns 0.2640 ns 1.00
XXH3 96 17.219 ns 0.2472 ns 0.2312 ns 0.28
Marvin 97 61.382 ns 0.1737 ns 0.1540 ns 1.00
XXH3 97 17.094 ns 0.2303 ns 0.2155 ns 0.28
Marvin 98 62.734 ns 0.3698 ns 0.3278 ns 1.00
XXH3 98 17.218 ns 0.3134 ns 0.2932 ns 0.27
Marvin 99 62.758 ns 0.3744 ns 0.3502 ns 1.00
XXH3 99 17.045 ns 0.1692 ns 0.1583 ns 0.27
Marvin 1000 641.771 ns 1.9370 ns 1.7171 ns 1.00
XXH3 1000 90.804 ns 0.5840 ns 0.5463 ns 0.14

The above is for case-sensitive. Not sure exactly how we'd want to tweak the XXH3 algorithm for case-insensitive, but we could probably do something similar to what we do with Marvin today.

(It's also possible to improve on these numbers a bit for this purpose for XxHash3. There are some calculations in the current implementation that are done on every call, based on the seed supplied to that call, but for string hashing purposes where the seed is constant for the process lifetime, those calculations could be done once for the process when the random seed for the process is selected.)

cc: @GrabYourPitchforks, @jkotas

ghost commented 1 year ago

Tagging subscribers to this area: @dotnet/area-system-runtime See info in area-owners.md if you want to be subscribed.

Issue Details
We could, for example, bring XxHash3 down into corelib from System.IO.Hashing, delete Marvin, and use XxHash3 in place of it. ```C# public static IEnumerable GetLengths() { for (int i = 0; i < 100; i++) yield return i; yield return 1000; } [ParamsSource(nameof(GetLengths))] public int Length { get; set; } private string _str; private static readonly long s_seed = BitConverter.ToInt64(RandomNumberGenerator.GetBytes(8)); [GlobalSetup] public void Setup() => _str = RandomNumberGenerator.GetString("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", Length); [Benchmark(Baseline = true)] public int Marvin() => string.GetHashCode(_str); [Benchmark] public int XXH3() => (int)(long)XxHash3.HashToUInt64(MemoryMarshal.AsBytes(_str.AsSpan()), s_seed); ``` | Method | Length | Mean | Error | StdDev | Ratio | |------- |------- |-----------:|----------:|----------:|------:| | Marvin | 0 | 2.205 ns | 0.0046 ns | 0.0038 ns | 1.00 | | XXH3 | 0 | 3.522 ns | 0.0164 ns | 0.0137 ns | 1.60 | | | | | | | | | Marvin | 1 | 2.806 ns | 0.0078 ns | 0.0073 ns | 1.00 | | XXH3 | 1 | 3.705 ns | 0.0072 ns | 0.0060 ns | 1.32 | | | | | | | | | Marvin | 2 | 2.916 ns | 0.0054 ns | 0.0048 ns | 1.00 | | XXH3 | 2 | 3.776 ns | 0.0082 ns | 0.0073 ns | 1.29 | | | | | | | | | Marvin | 3 | 2.924 ns | 0.0086 ns | 0.0067 ns | 1.00 | | XXH3 | 3 | 3.774 ns | 0.0105 ns | 0.0098 ns | 1.29 | | | | | | | | | Marvin | 4 | 3.950 ns | 0.0100 ns | 0.0084 ns | 1.00 | | XXH3 | 4 | 3.768 ns | 0.0059 ns | 0.0049 ns | 0.95 | | | | | | | | | Marvin | 5 | 3.968 ns | 0.0333 ns | 0.0260 ns | 1.00 | | XXH3 | 5 | 3.105 ns | 0.0157 ns | 0.0139 ns | 0.78 | | | | | | | | | Marvin | 6 | 4.825 ns | 0.0063 ns | 0.0053 ns | 1.00 | | XXH3 | 6 | 3.094 ns | 0.0037 ns | 0.0031 ns | 0.64 | | | | | | | | | Marvin | 7 | 4.826 ns | 0.0101 ns | 0.0090 ns | 1.00 | | XXH3 | 7 | 3.093 ns | 0.0038 ns | 0.0034 ns | 0.64 | | | | | | | | | Marvin | 8 | 5.869 ns | 0.0092 ns | 0.0081 ns | 1.00 | | XXH3 | 8 | 3.091 ns | 0.0064 ns | 0.0060 ns | 0.53 | | | | | | | | | Marvin | 9 | 5.872 ns | 0.0086 ns | 0.0071 ns | 1.00 | | XXH3 | 9 | 5.247 ns | 0.0116 ns | 0.0103 ns | 0.89 | | | | | | | | | Marvin | 10 | 6.910 ns | 0.0133 ns | 0.0111 ns | 1.00 | | XXH3 | 10 | 5.250 ns | 0.0102 ns | 0.0085 ns | 0.76 | | | | | | | | | Marvin | 11 | 6.910 ns | 0.0105 ns | 0.0098 ns | 1.00 | | XXH3 | 11 | 5.226 ns | 0.0085 ns | 0.0071 ns | 0.76 | | | | | | | | | Marvin | 12 | 8.040 ns | 0.0130 ns | 0.0115 ns | 1.00 | | XXH3 | 12 | 5.219 ns | 0.0109 ns | 0.0091 ns | 0.65 | | | | | | | | | Marvin | 13 | 8.039 ns | 0.0188 ns | 0.0167 ns | 1.00 | | XXH3 | 13 | 5.299 ns | 0.0761 ns | 0.0712 ns | 0.66 | | | | | | | | | Marvin | 14 | 9.243 ns | 0.0462 ns | 0.0433 ns | 1.00 | | XXH3 | 14 | 5.303 ns | 0.0476 ns | 0.0422 ns | 0.57 | | | | | | | | | Marvin | 15 | 9.234 ns | 0.0630 ns | 0.0589 ns | 1.00 | | XXH3 | 15 | 5.316 ns | 0.0696 ns | 0.0651 ns | 0.58 | | | | | | | | | Marvin | 16 | 10.584 ns | 0.0520 ns | 0.0434 ns | 1.00 | | XXH3 | 16 | 5.274 ns | 0.0573 ns | 0.0536 ns | 0.50 | | | | | | | | | Marvin | 17 | 10.615 ns | 0.0586 ns | 0.0548 ns | 1.00 | | XXH3 | 17 | 7.277 ns | 0.1186 ns | 0.1110 ns | 0.69 | | | | | | | | | Marvin | 18 | 11.830 ns | 0.0869 ns | 0.0813 ns | 1.00 | | XXH3 | 18 | 7.220 ns | 0.0899 ns | 0.0750 ns | 0.61 | | | | | | | | | Marvin | 19 | 11.777 ns | 0.0336 ns | 0.0315 ns | 1.00 | | XXH3 | 19 | 7.251 ns | 0.0765 ns | 0.0679 ns | 0.62 | | | | | | | | | Marvin | 20 | 13.162 ns | 0.1112 ns | 0.1040 ns | 1.00 | | XXH3 | 20 | 7.324 ns | 0.1073 ns | 0.1004 ns | 0.56 | | | | | | | | | Marvin | 21 | 13.123 ns | 0.0572 ns | 0.0535 ns | 1.00 | | XXH3 | 21 | 7.266 ns | 0.0735 ns | 0.0651 ns | 0.55 | | | | | | | | | Marvin | 22 | 14.351 ns | 0.0717 ns | 0.0635 ns | 1.00 | | XXH3 | 22 | 7.206 ns | 0.0646 ns | 0.0604 ns | 0.50 | | | | | | | | | Marvin | 23 | 14.368 ns | 0.0944 ns | 0.0883 ns | 1.00 | | XXH3 | 23 | 7.261 ns | 0.0846 ns | 0.0791 ns | 0.51 | | | | | | | | | Marvin | 24 | 15.678 ns | 0.0413 ns | 0.0387 ns | 1.00 | | XXH3 | 24 | 7.243 ns | 0.1070 ns | 0.0894 ns | 0.46 | | | | | | | | | Marvin | 25 | 15.667 ns | 0.0455 ns | 0.0403 ns | 1.00 | | XXH3 | 25 | 7.266 ns | 0.0909 ns | 0.0851 ns | 0.46 | | | | | | | | | Marvin | 26 | 16.983 ns | 0.0701 ns | 0.0656 ns | 1.00 | | XXH3 | 26 | 7.329 ns | 0.1174 ns | 0.1098 ns | 0.43 | | | | | | | | | Marvin | 27 | 16.978 ns | 0.0798 ns | 0.0746 ns | 1.00 | | XXH3 | 27 | 7.230 ns | 0.0865 ns | 0.0766 ns | 0.43 | | | | | | | | | Marvin | 28 | 18.209 ns | 0.0697 ns | 0.0618 ns | 1.00 | | XXH3 | 28 | 7.226 ns | 0.1110 ns | 0.0866 ns | 0.40 | | | | | | | | | Marvin | 29 | 18.188 ns | 0.0426 ns | 0.0356 ns | 1.00 | | XXH3 | 29 | 7.200 ns | 0.0965 ns | 0.0856 ns | 0.40 | | | | | | | | | Marvin | 30 | 19.492 ns | 0.0686 ns | 0.0573 ns | 1.00 | | XXH3 | 30 | 7.200 ns | 0.0304 ns | 0.0270 ns | 0.37 | | | | | | | | | Marvin | 31 | 19.417 ns | 0.0479 ns | 0.0374 ns | 1.00 | | XXH3 | 31 | 8.962 ns | 0.1872 ns | 0.1659 ns | 0.46 | | | | | | | | | Marvin | 32 | 20.672 ns | 0.1128 ns | 0.1000 ns | 1.00 | | XXH3 | 32 | 7.503 ns | 0.1780 ns | 0.3165 ns | 0.37 | | | | | | | | | Marvin | 33 | 20.814 ns | 0.1463 ns | 0.1296 ns | 1.00 | | XXH3 | 33 | 9.921 ns | 0.0378 ns | 0.0335 ns | 0.48 | | | | | | | | | Marvin | 34 | 21.951 ns | 0.0495 ns | 0.0439 ns | 1.00 | | XXH3 | 34 | 9.354 ns | 0.0592 ns | 0.0525 ns | 0.43 | | | | | | | | | Marvin | 35 | 23.116 ns | 0.2080 ns | 0.1737 ns | 1.00 | | XXH3 | 35 | 9.289 ns | 0.1670 ns | 0.1562 ns | 0.40 | | | | | | | | | Marvin | 36 | 23.245 ns | 0.0868 ns | 0.0678 ns | 1.00 | | XXH3 | 36 | 9.122 ns | 0.0169 ns | 0.0132 ns | 0.39 | | | | | | | | | Marvin | 37 | 23.272 ns | 0.0736 ns | 0.0574 ns | 1.00 | | XXH3 | 37 | 9.226 ns | 0.1643 ns | 0.1456 ns | 0.40 | | | | | | | | | Marvin | 38 | 24.480 ns | 0.0279 ns | 0.0233 ns | 1.00 | | XXH3 | 38 | 9.602 ns | 0.0235 ns | 0.0220 ns | 0.39 | | | | | | | | | Marvin | 39 | 24.544 ns | 0.0472 ns | 0.0419 ns | 1.00 | | XXH3 | 39 | 9.124 ns | 0.0486 ns | 0.0454 ns | 0.37 | | | | | | | | | Marvin | 40 | 26.297 ns | 0.4920 ns | 0.4109 ns | 1.00 | | XXH3 | 40 | 9.123 ns | 0.0446 ns | 0.0372 ns | 0.35 | | | | | | | | | Marvin | 41 | 25.857 ns | 0.0798 ns | 0.0666 ns | 1.00 | | XXH3 | 41 | 9.113 ns | 0.0240 ns | 0.0200 ns | 0.35 | | | | | | | | | Marvin | 42 | 27.123 ns | 0.0506 ns | 0.0448 ns | 1.00 | | XXH3 | 42 | 9.082 ns | 0.0336 ns | 0.0298 ns | 0.33 | | | | | | | | | Marvin | 43 | 27.116 ns | 0.0918 ns | 0.0767 ns | 1.00 | | XXH3 | 43 | 9.102 ns | 0.0319 ns | 0.0266 ns | 0.34 | | | | | | | | | Marvin | 44 | 28.390 ns | 0.0551 ns | 0.0430 ns | 1.00 | | XXH3 | 44 | 9.344 ns | 0.1681 ns | 0.2127 ns | 0.33 | | | | | | | | | Marvin | 45 | 28.286 ns | 0.1756 ns | 0.1557 ns | 1.00 | | XXH3 | 45 | 9.174 ns | 0.0874 ns | 0.0775 ns | 0.32 | | | | | | | | | Marvin | 46 | 29.300 ns | 0.0890 ns | 0.0695 ns | 1.00 | | XXH3 | 46 | 9.131 ns | 0.0370 ns | 0.0289 ns | 0.31 | | | | | | | | | Marvin | 47 | 29.392 ns | 0.2965 ns | 0.2774 ns | 1.00 | | XXH3 | 47 | 9.179 ns | 0.0755 ns | 0.0631 ns | 0.31 | | | | | | | | | Marvin | 48 | 30.552 ns | 0.0832 ns | 0.0778 ns | 1.00 | | XXH3 | 48 | 9.119 ns | 0.0384 ns | 0.0359 ns | 0.30 | | | | | | | | | Marvin | 49 | 31.003 ns | 0.2855 ns | 0.2670 ns | 1.00 | | XXH3 | 49 | 11.157 ns | 0.1705 ns | 0.1595 ns | 0.36 | | | | | | | | | Marvin | 50 | 32.171 ns | 0.1526 ns | 0.1353 ns | 1.00 | | XXH3 | 50 | 10.954 ns | 0.0641 ns | 0.0599 ns | 0.34 | | | | | | | | | Marvin | 51 | 31.982 ns | 0.1082 ns | 0.1012 ns | 1.00 | | XXH3 | 51 | 10.994 ns | 0.0646 ns | 0.0505 ns | 0.34 | | | | | | | | | Marvin | 52 | 33.574 ns | 0.1167 ns | 0.1034 ns | 1.00 | | XXH3 | 52 | 11.150 ns | 0.2129 ns | 0.1991 ns | 0.33 | | | | | | | | | Marvin | 53 | 33.289 ns | 0.1263 ns | 0.0986 ns | 1.00 | | XXH3 | 53 | 11.628 ns | 0.1974 ns | 0.1750 ns | 0.35 | | | | | | | | | Marvin | 54 | 34.830 ns | 0.1631 ns | 0.1362 ns | 1.00 | | XXH3 | 54 | 10.989 ns | 0.0533 ns | 0.0498 ns | 0.32 | | | | | | | | | Marvin | 55 | 34.834 ns | 0.2934 ns | 0.2450 ns | 1.00 | | XXH3 | 55 | 10.954 ns | 0.0450 ns | 0.0399 ns | 0.31 | | | | | | | | | Marvin | 56 | 35.928 ns | 0.1376 ns | 0.1220 ns | 1.00 | | XXH3 | 56 | 11.043 ns | 0.1518 ns | 0.1267 ns | 0.31 | | | | | | | | | Marvin | 57 | 36.067 ns | 0.0865 ns | 0.0676 ns | 1.00 | | XXH3 | 57 | 10.992 ns | 0.0619 ns | 0.0579 ns | 0.30 | | | | | | | | | Marvin | 58 | 37.230 ns | 0.2899 ns | 0.2570 ns | 1.00 | | XXH3 | 58 | 10.965 ns | 0.0591 ns | 0.0524 ns | 0.29 | | | | | | | | | Marvin | 59 | 37.265 ns | 0.1673 ns | 0.1565 ns | 1.00 | | XXH3 | 59 | 11.418 ns | 0.0478 ns | 0.0447 ns | 0.31 | | | | | | | | | Marvin | 60 | 39.014 ns | 0.4613 ns | 0.4315 ns | 1.00 | | XXH3 | 60 | 11.224 ns | 0.1864 ns | 0.1744 ns | 0.29 | | | | | | | | | Marvin | 61 | 38.295 ns | 0.0890 ns | 0.0743 ns | 1.00 | | XXH3 | 61 | 11.053 ns | 0.0562 ns | 0.0469 ns | 0.29 | | | | | | | | | Marvin | 62 | 40.999 ns | 0.3287 ns | 0.3074 ns | 1.00 | | XXH3 | 62 | 11.011 ns | 0.0409 ns | 0.0342 ns | 0.27 | | | | | | | | | Marvin | 63 | 40.162 ns | 0.4329 ns | 0.4050 ns | 1.00 | | XXH3 | 63 | 11.069 ns | 0.0757 ns | 0.0708 ns | 0.28 | | | | | | | | | Marvin | 64 | 41.214 ns | 0.1653 ns | 0.1465 ns | 1.00 | | XXH3 | 64 | 11.011 ns | 0.0790 ns | 0.0701 ns | 0.27 | | | | | | | | | Marvin | 65 | 41.048 ns | 0.1866 ns | 0.1654 ns | 1.00 | | XXH3 | 65 | 12.981 ns | 0.2273 ns | 0.3111 ns | 0.32 | | | | | | | | | Marvin | 66 | 42.330 ns | 0.0583 ns | 0.0545 ns | 1.00 | | XXH3 | 66 | 13.466 ns | 0.1692 ns | 0.1321 ns | 0.32 | | | | | | | | | Marvin | 67 | 42.295 ns | 0.1306 ns | 0.1158 ns | 1.00 | | XXH3 | 67 | 12.810 ns | 0.0710 ns | 0.0554 ns | 0.30 | | | | | | | | | Marvin | 68 | 44.611 ns | 0.1313 ns | 0.1097 ns | 1.00 | | XXH3 | 68 | 12.774 ns | 0.0894 ns | 0.0836 ns | 0.29 | | | | | | | | | Marvin | 69 | 43.565 ns | 0.1541 ns | 0.1441 ns | 1.00 | | XXH3 | 69 | 12.736 ns | 0.0426 ns | 0.0377 ns | 0.29 | | | | | | | | | Marvin | 70 | 44.838 ns | 0.1492 ns | 0.1246 ns | 1.00 | | XXH3 | 70 | 12.764 ns | 0.0706 ns | 0.0626 ns | 0.28 | | | | | | | | | Marvin | 71 | 44.679 ns | 0.2256 ns | 0.1884 ns | 1.00 | | XXH3 | 71 | 12.774 ns | 0.0658 ns | 0.0584 ns | 0.29 | | | | | | | | | Marvin | 72 | 46.242 ns | 0.1360 ns | 0.1206 ns | 1.00 | | XXH3 | 72 | 13.756 ns | 0.0441 ns | 0.0412 ns | 0.30 | | | | | | | | | Marvin | 73 | 46.221 ns | 0.0975 ns | 0.0912 ns | 1.00 | | XXH3 | 73 | 13.707 ns | 0.0539 ns | 0.0450 ns | 0.30 | | | | | | | | | Marvin | 74 | 47.326 ns | 0.0998 ns | 0.0833 ns | 1.00 | | XXH3 | 74 | 13.672 ns | 0.0472 ns | 0.0441 ns | 0.29 | | | | | | | | | Marvin | 75 | 47.355 ns | 0.0720 ns | 0.0639 ns | 1.00 | | XXH3 | 75 | 15.349 ns | 0.0567 ns | 0.0443 ns | 0.32 | | | | | | | | | Marvin | 76 | 48.792 ns | 0.2150 ns | 0.1795 ns | 1.00 | | XXH3 | 76 | 13.923 ns | 0.2677 ns | 0.2504 ns | 0.29 | | | | | | | | | Marvin | 77 | 49.093 ns | 0.4068 ns | 0.3805 ns | 1.00 | | XXH3 | 77 | 13.853 ns | 0.1196 ns | 0.1118 ns | 0.28 | | | | | | | | | Marvin | 78 | 49.633 ns | 0.2275 ns | 0.2016 ns | 1.00 | | XXH3 | 78 | 13.760 ns | 0.1350 ns | 0.1262 ns | 0.28 | | | | | | | | | Marvin | 79 | 50.116 ns | 0.1726 ns | 0.1614 ns | 1.00 | | XXH3 | 79 | 13.729 ns | 0.0465 ns | 0.0413 ns | 0.27 | | | | | | | | | Marvin | 80 | 51.202 ns | 0.0328 ns | 0.0290 ns | 1.00 | | XXH3 | 80 | 14.814 ns | 0.0745 ns | 0.0622 ns | 0.29 | | | | | | | | | Marvin | 81 | 51.313 ns | 0.2195 ns | 0.2053 ns | 1.00 | | XXH3 | 81 | 14.803 ns | 0.0397 ns | 0.0352 ns | 0.29 | | | | | | | | | Marvin | 82 | 52.436 ns | 0.1511 ns | 0.1262 ns | 1.00 | | XXH3 | 82 | 14.768 ns | 0.0900 ns | 0.0798 ns | 0.28 | | | | | | | | | Marvin | 83 | 52.408 ns | 0.1683 ns | 0.1492 ns | 1.00 | | XXH3 | 83 | 14.786 ns | 0.0993 ns | 0.0880 ns | 0.28 | | | | | | | | | Marvin | 84 | 53.937 ns | 0.0650 ns | 0.0507 ns | 1.00 | | XXH3 | 84 | 14.786 ns | 0.0309 ns | 0.0274 ns | 0.27 | | | | | | | | | Marvin | 85 | 54.101 ns | 0.4325 ns | 0.3834 ns | 1.00 | | XXH3 | 85 | 14.741 ns | 0.0440 ns | 0.0343 ns | 0.27 | | | | | | | | | Marvin | 86 | 55.323 ns | 0.2775 ns | 0.2317 ns | 1.00 | | XXH3 | 86 | 14.788 ns | 0.0435 ns | 0.0363 ns | 0.27 | | | | | | | | | Marvin | 87 | 55.093 ns | 0.1377 ns | 0.1149 ns | 1.00 | | XXH3 | 87 | 14.729 ns | 0.0300 ns | 0.0234 ns | 0.27 | | | | | | | | | Marvin | 88 | 55.894 ns | 0.1049 ns | 0.0930 ns | 1.00 | | XXH3 | 88 | 15.776 ns | 0.0403 ns | 0.0377 ns | 0.28 | | | | | | | | | Marvin | 89 | 56.322 ns | 0.1114 ns | 0.0987 ns | 1.00 | | XXH3 | 89 | 15.770 ns | 0.0329 ns | 0.0291 ns | 0.28 | | | | | | | | | Marvin | 90 | 57.563 ns | 0.0939 ns | 0.0784 ns | 1.00 | | XXH3 | 90 | 15.788 ns | 0.0382 ns | 0.0358 ns | 0.27 | | | | | | | | | Marvin | 91 | 57.267 ns | 0.0740 ns | 0.0656 ns | 1.00 | | XXH3 | 91 | 15.773 ns | 0.0193 ns | 0.0161 ns | 0.28 | | | | | | | | | Marvin | 92 | 58.407 ns | 0.1212 ns | 0.1074 ns | 1.00 | | XXH3 | 92 | 15.971 ns | 0.2320 ns | 0.1937 ns | 0.27 | | | | | | | | | Marvin | 93 | 58.557 ns | 0.1270 ns | 0.1126 ns | 1.00 | | XXH3 | 93 | 17.170 ns | 0.1486 ns | 0.1317 ns | 0.29 | | | | | | | | | Marvin | 94 | 59.852 ns | 0.2075 ns | 0.1839 ns | 1.00 | | XXH3 | 94 | 16.016 ns | 0.1614 ns | 0.1510 ns | 0.27 | | | | | | | | | Marvin | 95 | 61.040 ns | 0.1310 ns | 0.1094 ns | 1.00 | | XXH3 | 95 | 15.816 ns | 0.0612 ns | 0.0478 ns | 0.26 | | | | | | | | | Marvin | 96 | 61.263 ns | 0.2978 ns | 0.2640 ns | 1.00 | | XXH3 | 96 | 17.219 ns | 0.2472 ns | 0.2312 ns | 0.28 | | | | | | | | | Marvin | 97 | 61.382 ns | 0.1737 ns | 0.1540 ns | 1.00 | | XXH3 | 97 | 17.094 ns | 0.2303 ns | 0.2155 ns | 0.28 | | | | | | | | | Marvin | 98 | 62.734 ns | 0.3698 ns | 0.3278 ns | 1.00 | | XXH3 | 98 | 17.218 ns | 0.3134 ns | 0.2932 ns | 0.27 | | | | | | | | | Marvin | 99 | 62.758 ns | 0.3744 ns | 0.3502 ns | 1.00 | | XXH3 | 99 | 17.045 ns | 0.1692 ns | 0.1583 ns | 0.27 | | | | | | | | | Marvin | 1000 | 641.771 ns | 1.9370 ns | 1.7171 ns | 1.00 | | XXH3 | 1000 | 90.804 ns | 0.5840 ns | 0.5463 ns | 0.14 | The above is for case-sensitive. Not sure exactly how we'd want to tweak the XXH3 algorithm for case-insensitive, but we could probably do something similar to what we do with Marvin today. (It's also possible to improve on these numbers a bit for this purpose for XxHash3. There are some calculations in the current implementation that are done on every call, based on the seed supplied to that call, but for string hashing purposes where the seed is constant for the process lifetime, those calculations could be done once for the process when the random seed for the process is selected.) cc: @GrabYourPitchforks, @jkotas
Author: stephentoub
Assignees: -
Labels: `area-System.Runtime`, `tenet-performance`
Milestone: 8.0.0
danmoseley commented 1 year ago

Some relevant info in #68616. If it has comparable security guarantees and is faster - seems potentially a good idea.

danmoseley commented 1 year ago

I'm going to guess the 99% case is hashing less than 100 bytes. I wonder whether there are algorithms that perhaps don't perform as well across all input sizes as xxHash but do even better for such short inputs.

EgorBo commented 1 year ago

I wonder if with this XXH3 we can even remove the fast hashcode that we use in Dictionary till we hit collisitions and fallback to the default randomized one.

jkotas commented 1 year ago

Does XxHash3 provide same or better protection against DoS attacks compared to Marvin? Is there a test that can measure it?

GrabYourPitchforks commented 1 year ago

I'm going to guess the 99% case is hashing less than 100 bytes. I wonder whether there are algorithms that perhaps don't perform as well across all input sizes as xxHash but do even better for such short inputs.

Most inputs here are in the 6 - 10 char range for strings which represent identifiers. For strings which represent people's names, they can of course be arbitrarily long, but less than 16 chars is a good rule of thumb.

The primary scenario for this is strings which are used within record-like types. Strings which are used as keys in collections are already special cased to go down a faster code path, assuming that optimization remains in place.

stephentoub commented 1 year ago

Does XxHash3 provide same or better protection against DoS attacks compared to Marvin? Is there a test that can measure it?

No one else I can find uses or evaluates Marvin, so it doesn't show up in any academic / industry comparisons I've seen nor gets much in the way of external scrutiny (that in and of itself might be reason to move on). But XXH3 gets good marks on standard test suites like SMHasher. Levi can likely comment further. We could also adapt such a suite and measure it ourselves if desired.

My suggestion also isn't tied specifically to XXH3... we just have a good implementation of it now, it looks to be well-respected, and its the fastest algorithm we've implemented. If something better came along, we could switch to that instead.

stephentoub commented 1 year ago

FWIW, I was curious to see how XXH3 compared against FNV-1a, which is what C# uses for hashing strings in switches. I was wondering if it'd make sense for the C# compiler itself to switch to depend on XxHash3 if doing so didn't require an additional assembly reference. But on my machine, the crossover point where XxHash3 starts being faster is at ~13 characters, which I expect is larger than the average string length used in switches, so it's unlikely to be a win. (For very long string lengths, XXH3 is a clear winner; on my machine, at 100 characters, FNV-1a is ~5x slower than XXH3, and at 1000 characters is ~10x slower.)

tannergooding commented 1 year ago

Putting this into future as we won't be doing it for 8.

We can move it to 9 when and if work actually starts on this to avoid needing to keep pushing it out to the next milestone.

neon-sunset commented 1 year ago

Does XxHash3 provide same or better protection against DoS attacks compared to Marvin? Is there a test that can measure it?

The main point it is likely that Marvin loses to XxHash3 on all criteria, with the latter being optimal choice on collision rate + performance across all input lenghts:

Given this would affect one of the foundational behaviors in .NET, this probably warrants a more extensive research rather than a simple "go vs no go", with non-trivial performance wins on the table across the board with improved dictionary/hashset lookups and code simplification (likely no more need for custom implementations for specific containers).

EgorBo commented 11 months ago

@stephentoub I'm seeing String.GetNonRandomizedHashCode on a hot path (I guess, Dictionary<string, T> lookups) in some of out 1P customer's workload - I wonder if we can use XxHash3 there easily since DDoS is not a concern - if we hit collisions we'll switch to the default String.GetHashCode anyway. I can probably even tell you an average string's length for that customer.

stephentoub commented 11 months ago

I can probably even tell you an average string's length for that customer.

Yes please

Genbox commented 10 months ago

Does XxHash3 provide same or better protection against DoS attacks compared to Marvin? Is there a test that can measure it?

DoS against hashmap data structures comes from key collisions, and while both Marvin and xxHash have good mixing properties and, therefore, a low rate of collision, protection against DoS should come from seeding the hash functions rather than their collision resistance.

That being said, the lack of (at least public) analysis of MarvinHash, and the fact that xxHash has been analyzed (flaws were found and fixed), will by default make xxHash the preferred choice.

Genbox commented 10 months ago

I was wondering if it'd make sense for the C# compiler itself to switch to depend on XxHash3

It is worth noting that reducing the xxHash function to a mixer (ulong -> mixed ulong) considerably speeds up the function. Specializing the function rather than using a generic version often provides a very large speedup.

Genbox commented 10 months ago

My FastHash project has a benchmark suite for common hash functions with sizes 8, 32, 128, etc.

I've included Marvin, as well as both xxHash v2 and xxHash v3 hash functions. I've made little to no changes to the original algorithms. There is a test suite that tests against published test vectors to ensure correctness.

General notes:

Benchmark: Method Size Mean Error StdDev
Xx2Hash32UnsafeTest 2 1.372 ns 0.0089 ns 0.0083 ns
MarvinHash32Test 2 1.837 ns 0.0126 ns 0.0118 ns
Xx2Hash64UnsafeTest 2 1.895 ns 0.0097 ns 0.0086 ns
Xx2Hash64Test 2 2.153 ns 0.0031 ns 0.0026 ns
Xx2Hash32Test 2 2.329 ns 0.0110 ns 0.0103 ns
Xx3Hash64UnsafeTest 2 3.460 ns 0.0165 ns 0.0155 ns
Xx3Hash64Test 2 3.623 ns 0.0412 ns 0.0386 ns
Xx3Hash128UnsafeTest 2 7.348 ns 0.0436 ns 0.0387 ns
Xx2Hash32UnsafeTest 4 0.8460 ns 0.0083 ns 0.0074 ns
Xx2Hash64UnsafeTest 4 1.2169 ns 0.0107 ns 0.0095 ns
MarvinHash32Test 4 1.6236 ns 0.0114 ns 0.0095 ns
Xx2Hash32Test 4 1.6752 ns 0.0136 ns 0.0113 ns
Xx2Hash64Test 4 1.9443 ns 0.0127 ns 0.0106 ns
Xx3Hash64UnsafeTest 4 4.0610 ns 0.0153 ns 0.0143 ns
Xx3Hash64Test 4 4.0684 ns 0.0103 ns 0.0091 ns
Xx3Hash128UnsafeTest 4 8.7722 ns 0.0126 ns 0.0112 ns
Xx2Hash64UnsafeTest 8 1.062 ns 0.0140 ns 0.0131 ns
Xx2Hash32UnsafeTest 8 1.357 ns 0.0163 ns 0.0145 ns
Xx2Hash64Test 8 1.875 ns 0.0198 ns 0.0185 ns
MarvinHash32Test 8 2.119 ns 0.0120 ns 0.0113 ns
Xx2Hash32Test 8 2.513 ns 0.0280 ns 0.0234 ns
Xx3Hash64Test 8 3.835 ns 0.0257 ns 0.0241 ns
Xx3Hash64UnsafeTest 8 4.039 ns 0.0135 ns 0.0113 ns
Xx3Hash128UnsafeTest 8 9.136 ns 0.0630 ns 0.0590 ns
Xx2Hash32UnsafeTest 16 1.627 ns 0.0058 ns 0.0052 ns
Xx2Hash64UnsafeTest 16 1.993 ns 0.0069 ns 0.0061 ns
Xx2Hash32Test 16 2.554 ns 0.0103 ns 0.0091 ns
Xx2Hash64Test 16 2.972 ns 0.0024 ns 0.0019 ns
Xx3Hash64UnsafeTest 16 3.440 ns 0.0051 ns 0.0045 ns
MarvinHash32Test 16 3.464 ns 0.0086 ns 0.0076 ns
Xx3Hash128UnsafeTest 16 9.586 ns 0.0144 ns 0.0120 ns
Xx3Hash64Test 16 11.475 ns 0.0185 ns 0.0173 ns
Xx2Hash32UnsafeTest 32 2.805 ns 0.0084 ns 0.0078 ns
Xx2Hash32Test 32 3.985 ns 0.0103 ns 0.0097 ns
Xx2Hash64UnsafeTest 32 4.290 ns 0.0144 ns 0.0128 ns
Xx3Hash64Test 32 4.545 ns 0.0126 ns 0.0105 ns
Xx2Hash64Test 32 4.913 ns 0.0189 ns 0.0167 ns
Xx3Hash64UnsafeTest 32 6.065 ns 0.0201 ns 0.0178 ns
MarvinHash32Test 32 6.779 ns 0.0161 ns 0.0134 ns
Xx3Hash128UnsafeTest 32 21.619 ns 0.0387 ns 0.0323 ns

Benchmark notes:

stephentoub commented 10 months ago

The implementation of xxHash in System.IO.Hashing is rather slow compared to the original xxhash implementation.

Can you elaborate? On what hardware? This is contrary to what we previously saw when measuring optimizations here, e.g. https://github.com/dotnet/runtime/pull/77881#issue-1435656399. cc: @xoofx

It also returns a byte array rather than an uint/ulong, which is not great for performance.

You're looking for the HashToUInt64 method. It doesn't create a byte array; it just returns a ulong. https://learn.microsoft.com/en-us/dotnet/api/system.io.hashing.xxhash3.hashtouint64

Genbox commented 10 months ago

You're looking for the HashToUInt64 method. It doesn't create a byte array; it just returns a ulong. https://learn.microsoft.com/en-us/dotnet/api/system.io.hashing.xxhash3.hashtouint64

I tested against the release version of the package. Seems the HashToUint64 was introduced in the pre-release of version 8.0 packages. I'll redo my benchmark against the pre-release version. The byte array allocation overhead certainly will have impacted performance.

stephentoub commented 10 months ago

I tested against the release version of the package.

Ok. In that case, you also weren't using XxHash3, which along with XxHash128 was added in the 8.0 package. Thanks.

Genbox commented 10 months ago

Here are the new benchmarks. These functions are the ones from System.IO.Hashing:

The others are my implementations from Genbox.FastHash.

Method Size Mean Error StdDev
Xx2Hash32UnsafeTest 2 1.355 ns 0.0122 ns 0.0109 ns
MarvinHash32Test 2 1.813 ns 0.0337 ns 0.0298 ns
Xx2Hash64UnsafeTest 2 1.827 ns 0.0123 ns 0.0109 ns
Xx3Hash64NetTest 2 1.864 ns 0.0161 ns 0.0150 ns
Xx2Hash64Test 2 2.142 ns 0.0292 ns 0.0273 ns
Xx2Hash32Test 2 2.640 ns 0.0152 ns 0.0142 ns
Xx3Hash64Test 2 3.458 ns 0.0297 ns 0.0264 ns
Xx3Hash64UnsafeTest 2 3.548 ns 0.0396 ns 0.0370 ns
Xx2Hash64NetTest 2 3.595 ns 0.0164 ns 0.0146 ns
Xx2Hash32NetTest 2 4.098 ns 0.0267 ns 0.0236 ns
Xx2Hash32UnsafeTest 4 1.167 ns 0.0142 ns 0.0126 ns
Xx2Hash64UnsafeTest 4 1.254 ns 0.0094 ns 0.0152 ns
MarvinHash32Test 4 1.625 ns 0.0088 ns 0.0083 ns
Xx2Hash32Test 4 1.662 ns 0.0123 ns 0.0115 ns
Xx2Hash64Test 4 1.748 ns 0.0143 ns 0.0133 ns
Xx3Hash64NetTest 4 1.894 ns 0.0082 ns 0.0076 ns
Xx2Hash32NetTest 4 3.015 ns 0.0087 ns 0.0082 ns
Xx2Hash64NetTest 4 3.295 ns 0.0161 ns 0.0150 ns
Xx3Hash64UnsafeTest 4 3.839 ns 0.0119 ns 0.0093 ns
Xx3Hash64Test 4 4.072 ns 0.0242 ns 0.0202 ns
Xx2Hash32UnsafeTest 8 1.331 ns 0.0179 ns 0.0167 ns
Xx2Hash64UnsafeTest 8 1.342 ns 0.0094 ns 0.0088 ns
Xx2Hash32Test 8 1.677 ns 0.0145 ns 0.0128 ns
Xx3Hash64NetTest 8 1.846 ns 0.0095 ns 0.0089 ns
Xx2Hash64Test 8 1.918 ns 0.0249 ns 0.0233 ns
MarvinHash32Test 8 2.154 ns 0.0346 ns 0.0307 ns
Xx2Hash64NetTest 8 3.183 ns 0.0310 ns 0.0259 ns
Xx2Hash32NetTest 8 3.261 ns 0.0265 ns 0.0221 ns
Xx3Hash64Test 8 3.871 ns 0.0378 ns 0.0354 ns
Xx3Hash64UnsafeTest 8 4.104 ns 0.0867 ns 0.0811 ns
Xx3Hash64NetTest 16 1.539 ns 0.0095 ns 0.0089 ns
Xx2Hash32UnsafeTest 16 1.946 ns 0.0102 ns 0.0095 ns
Xx2Hash64UnsafeTest 16 2.088 ns 0.0126 ns 0.0112 ns
Xx2Hash32Test 16 2.498 ns 0.0101 ns 0.0094 ns
Xx2Hash64Test 16 2.968 ns 0.0178 ns 0.0158 ns
MarvinHash32Test 16 3.415 ns 0.0219 ns 0.0205 ns
Xx3Hash64UnsafeTest 16 3.429 ns 0.0193 ns 0.0150 ns
Xx2Hash32NetTest 16 3.908 ns 0.0250 ns 0.0222 ns
Xx2Hash64NetTest 16 4.220 ns 0.0443 ns 0.0392 ns
Xx3Hash64Test 16 11.696 ns 0.1103 ns 0.0978 ns
Xx3Hash64NetTest 32 2.611 ns 0.0122 ns 0.0114 ns
Xx2Hash32UnsafeTest 32 2.793 ns 0.0055 ns 0.0052 ns
Xx2Hash32Test 32 3.977 ns 0.0099 ns 0.0088 ns
Xx2Hash64UnsafeTest 32 4.259 ns 0.0107 ns 0.0095 ns
Xx3Hash64Test 32 4.591 ns 0.0086 ns 0.0076 ns
Xx2Hash64Test 32 4.891 ns 0.0256 ns 0.0227 ns
Xx2Hash32NetTest 32 6.040 ns 0.0256 ns 0.0239 ns
Xx3Hash64UnsafeTest 32 6.103 ns 0.0124 ns 0.0116 ns
Xx2Hash64NetTest 32 6.486 ns 0.0147 ns 0.0123 ns
MarvinHash32Test 32 6.771 ns 0.0165 ns 0.0146 ns

Config/Hardware:

System.IO.Hashing: 8.0.0-rc.2.23479.6
Genbox.FastHash: 1.0.0-alpha.2

BenchmarkDotNet v0.13.7, Windows 10 (10.0.19045.3570/22H2/2022Update)
12th Gen Intel Core i7-12700K, 1 CPU, 20 logical and 12 physical cores
.NET SDK 8.0.100-rc.2.23502.2
  [Host] : .NET 7.0.13 (7.0.1323.51816), X64 RyuJIT AVX2

My previous testing was against System.IO.Hashing 7.0.0, which did not have xxhash v3 or the HashToUInt64/HashToUInt32 functions which are a really nice addition.

xxhash v3 from System.IO.Hashing 8.0.0-rc is indeed fast. It gains traction on 16+ bytes, but has overall good performance.

ogxd commented 9 months ago

Good to see Marvin being challenged! It performs well for small input sizes but significantly falls behind some other algorithms such as xxh3 as input size grows.

I've put some of my free time lately into making another non-cryptographic algorithm named gxhash, leveraging SIMD and with high ILP. It's very recent and probably hasn't been adopted by anyone yet, so you may not want to consider it (at least now), still it passes SMHasher (while xxh3 does not) so I believe it is still interesting to have a look.

With the rust implementation the benchmark results are compelling, outperforming all counterparts I have found for all input sizes on my ARM and x64 machines.

As a quick test I have ported the algorithm in full managed C# (using portable SIMD from System.Runtime.Intrinsics). The implementation is not perfect and could probably be fine-tuned, but already outperforms the proposed Xxh3.

Another benefit is that it compiles for a much shorter assembly code compared Xxh3 and several other algorithms, but I need to get some numbers for .NET (better inlining opportunities?)

Please let me know if you think it's worth putting a little more effort into this. If you are interested I can clean the C# implementation a bit and share it. Of course any feedback is more than welcome.

Here are some numbers with the current implementation (.NET 8, MacBook M1 pro ARM). The benchmark code is the same as the one in the first post of this issue + GxHash_32.

Method Length Mean Error StdDev Ratio RatioSD
Marvin 0 1.369 ns 0.0361 ns 0.0056 ns baseline
XXH3 0 2.326 ns 0.0677 ns 0.0105 ns 1.70x slower 0.01x
GxHash_32 0 1.905 ns 0.0420 ns 0.0328 ns 1.38x slower 0.01x
Marvin 1 1.370 ns 0.0296 ns 0.0046 ns baseline
XXH3 1 2.314 ns 0.0574 ns 0.0149 ns 1.69x slower 0.01x
GxHash_32 1 1.904 ns 0.0370 ns 0.0096 ns 1.39x slower 0.01x
Marvin 2 1.375 ns 0.0454 ns 0.0118 ns baseline
XXH3 2 2.337 ns 0.0605 ns 0.0269 ns 1.71x slower 0.03x
GxHash_32 2 1.878 ns 0.0269 ns 0.0015 ns 1.37x slower 0.01x
Marvin 4 2.399 ns 0.0710 ns 0.0593 ns baseline
XXH3 4 2.343 ns 0.0345 ns 0.0053 ns 1.04x faster 0.04x
GxHash_32 4 1.935 ns 0.0307 ns 0.0017 ns 1.28x faster 0.05x
Marvin 8 3.662 ns 0.0936 ns 0.0416 ns baseline
XXH3 8 2.330 ns 0.0272 ns 0.0042 ns 1.58x faster 0.02x
GxHash_32 8 1.928 ns 0.0236 ns 0.0037 ns 1.91x faster 0.03x
Marvin 16 5.213 ns 0.0436 ns 0.0067 ns baseline
XXH3 16 2.332 ns 0.0683 ns 0.0407 ns 2.22x faster 0.06x
GxHash_32 16 1.935 ns 0.0415 ns 0.0064 ns 2.69x faster 0.01x
Marvin 32 15.791 ns 0.2854 ns 0.0156 ns baseline
XXH3 32 2.339 ns 0.0514 ns 0.0183 ns 6.73x faster 0.08x
GxHash_32 32 1.932 ns 0.0426 ns 0.0066 ns 8.18x faster 0.04x
Marvin 128 74.875 ns 1.2884 ns 0.0706 ns baseline
XXH3 128 13.743 ns 0.2111 ns 0.0327 ns 5.44x faster 0.01x
GxHash_32 128 9.366 ns 0.1968 ns 0.0108 ns 7.99x faster 0.02x
Marvin 1000 273.099 ns 3.5320 ns 0.1936 ns baseline
XXH3 1000 63.287 ns 0.4308 ns 0.0667 ns 4.32x faster 0.00x
GxHash_32 1000 6.635 ns 0.0863 ns 0.0133 ns 41.14x faster 0.11x
Marvin 10000 5,442.992 ns 46.8482 ns 2.5679 ns baseline
XXH3 10000 300.116 ns 3.5788 ns 0.1962 ns 18.14x faster 0.01x
GxHash_32 10000 73.945 ns 0.8099 ns 0.0444 ns 73.61x faster 0.08x
danmoseley commented 9 months ago

@ogxd interesting! Interested in thoughts of others but I imagine we'd want to stick to something that's industry tested for something this fundamental and it sounds like it's relatively early days for your algorithm, although the performance sounds encouraging.

ogxd commented 9 months ago

Yes I completely agree, I was just thinking it was worth mentioning it here, despite it being new, given that XxH3 performs worse than Marvin on small input sizes, making the switch to XxH3 more of a compromise than a 100% win.

ogxd commented 9 months ago

As some seem to be interested I took some more time on this C# implementation for gxhash. If more people are interested the source code is here. gxhash passes all SMHasher quality/collision/avalanche tests (although the PR to have it integrated is still in progress) and uses rounds of AES block cipher internally, so it should be pretty robust, but I let you be the judges, you have the source now.

Some benchmark results from a github runner:

|   Method |                Value |         Mean |     Error |    StdDev | Ratio |  Thoughput (MiB/s) |
|--------- |--------------------- |-------------:|----------:|----------:|------:|-------------------:|
|   Marvin |                   zk |     3.405 ns | 0.0041 ns | 0.0037 ns |  1.00 |     1120.19 ± 2.72 |
|     XxH3 |                   zk |     3.756 ns | 0.0058 ns | 0.0048 ns |  1.10 |     1015.52 ± 3.12 |
| GxHash32 |                   zk |     1.592 ns | 0.0130 ns | 0.0108 ns |  0.47 |    2396.34 ± 39.01 |
|          |                      |              |           |           |       |                    |
|   Marvin |                 9Iza |     4.345 ns | 0.0113 ns | 0.0106 ns |  1.00 |     1756.08 ± 9.15 |
|     XxH3 |                 9Iza |     3.765 ns | 0.0132 ns | 0.0117 ns |  0.87 |    2026.15 ± 14.19 |
| GxHash32 |                 9Iza |     1.573 ns | 0.0149 ns | 0.0140 ns |  0.36 |    4849.14 ± 92.00 |
|          |                      |              |           |           |       |                    |
|   Marvin |             kwqYIEC7 |     6.418 ns | 0.0325 ns | 0.0304 ns |  1.00 |    2377.46 ± 24.07 |
|     XxH3 |             kwqYIEC7 |     4.048 ns | 0.0077 ns | 0.0068 ns |  0.63 |    3769.81 ± 14.32 |
| GxHash32 |             kwqYIEC7 |     1.568 ns | 0.0112 ns | 0.0105 ns |  0.24 |   9732.41 ± 139.11 |
|          |                      |              |           |           |       |                    |
|   Marvin |  cO0w(...)mE36 [512] |   395.916 ns | 0.1137 ns | 0.1008 ns |  1.00 |     2466.59 ± 1.42 |
|     XxH3 |  cO0w(...)mE36 [512] |    53.312 ns | 0.2560 ns | 0.2395 ns |  0.13 |  18317.93 ± 175.94 |
| GxHash32 |  cO0w(...)mE36 [512] |    15.647 ns | 0.2386 ns | 0.2232 ns |  0.04 | 62410.91 ± 1904.05 |
|          |                      |              |           |           |       |                    |
|   Marvin | F2fW(...)I1XD [8192] | 6,330.805 ns | 1.5850 ns | 1.4050 ns |  1.00 |     2468.09 ± 1.24 |
|     XxH3 | F2fW(...)I1XD [8192] | 1,017.953 ns | 5.8021 ns | 5.4273 ns |  0.16 |  15349.43 ± 174.98 |
| GxHash32 | F2fW(...)I1XD [8192] |   223.868 ns | 2.1845 ns | 2.0434 ns |  0.04 | 69795.58 ± 1362.24 |