Is it time to replace Marvin?

[stephentoub]

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]

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.

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

Author:	stephentoub
Assignees:	-
Labels:	area-System.Runtime, tenet-performance
Milestone:	8.0.0

[danmoseley]

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

[danmoseley]

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]

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]

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

[GrabYourPitchforks]

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]

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]

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]

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]

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:

• https://github.com/Cyan4973/xxHash/wiki/Collision-ratio-comparison#testing-64-bit-hashes-on-small-inputs-
• https://github.com/Cyan4973/xxHash/wiki/Performance-comparison#benchmarks-concentrating-on-small-data-

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]

@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]

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

Yes please

[Genbox]

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]

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]

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:

• The implementation of xxHash in System.IO.Hashing is rather slow compared to the original xxhash implementation. It also returns a byte array rather than an uint/ulong, which is not great for performance.
• System.HashCode.Combine() is based on the 32bit variant of xxHash v2.
• There is a SMHasher3 which has more extensive tests than SMHasher2. Interestingly xxHash v3 fails in more tests than xxHash v2 (look at the bottom for results).

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:

• I've grouped the benchmarks according to input size (size is in bytes) and then speed.
• The benchmarks with unsafe in the name use unsafe code for less overhead. It is likely a "safer" version using the Unsafe class and ref/out would perform similar, but without unsafe code.
• xxHash v3 is known for its throughput, but it mainly pertains to larger inputs due to the use of SIMD. I've not been able to replicate the supposedly improved speed of xxHash v3 in the scalar version.

[stephentoub]

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. #77881 (comment).
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]

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]

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]

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

• Xx2Hash32NetTest
• Xx2Hash64NetTest
• Xx3Hash64NetTest

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]

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]

@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]

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]

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 |