Consider optimizing the use of Vector in MemoryPoolIterator

[mburbea]

A slew of CoreCLR issues have been opened up in regard to method Seek().
Testing against Vector<byte>.Zero is currently slow because of the low quality code generation. Slightly better code is generated if you first convert to Vector<long>, but It is better to simply scan for a non-zero value over the four longs.

Another thing to consider is inside FindFirstEqualByte maybe using a Debruijn table to find the appropriate byte once you have a long.

        static readonly byte[] Debruijn64 =
        {
        0, 0, 0, 7, 0, 4, 7, 5, 3, 0, 2, 4, 0, 7, 1, 5,
        7, 3, 2, 0, 2, 2, 4, 2, 6, 1, 7, 4, 3, 1, 6, 4,
        7, 6, 3, 5, 3, 2, 0, 1, 7, 2, 1, 2, 6, 4, 3, 4,
        6, 5, 3, 1, 7, 1, 6, 4, 5, 3, 1, 6, 5, 6, 5, 5,
        };
        const long DEBRUIJN_SEQ64 = 0x26752B916FC7B0D;
        static int DebruijnFindByte(long v)
        {
            return Debruijn64[((ulong)((v & -v) * DEBRUIJN_SEQ64)) >> 58];
        }

This will perform better than the current quasi-tree search, and this helper will almost certainly inline. Obviously, I'd rather there be a bitscanforward intrinsic.

[benaadams]

The Vector<byte>.Zero test should now be resolved dotnet/coreclr#7367 and is good that the jit is improving as it effects the wider ecosystem (additionally coming dotnet/coreclr#7407).

The De Bruijn table is very interesting, hadn't come across that before.

[davidfowl]

@mburbea Can you explain what this code does? How did you generate DEBRUIJN_SEQ64?

[mburbea]

Some what, as I did look into them for a project I had once.
The x&-x unsets everything except the least significant set bit. Now for any long value, we've effectively reduced it to one of 65 values. (all zero, a 1 in position 0, a 1 in position 1,.. a 1 in position 63). We're not particularly interested in the zero case as we will probably exclude that one straight out.

Now we need to map the powers of 2 uniquely, so that we can quickly look up the values in an array. This Debruijn constant offers an interesting property in that when we multiply by our x it acts a a perfect hash look up for this reduced range and maps each input to a unique 6 bit sequence in the high bits of a long (which is why we have to >>58)

Here is a whitepaper on debruijn sequences, Note that while this paper is pretty old. It's still faster than a series of conditionals.
http://supertech.csail.mit.edu/papers/debruijn.pdf

I wrote some code a while ago to generate it (the 32 bit version is fairly common and its pretty easy to extend to 64 bit), and I can't exactly remember it or have an implementation handy. But a quick look here is some C code somebody used to build a 64bit bitScanForward
https://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator
Also, debruijn sequences are not unique as my constant is different then this one.
Since we are only interested in bytes we can just divide the values in the table to index the appropriate byte instead.

[Tornhoof]

Update: This is result set is wrong, see below for updated values

Small Benchmark for the two different methods.

The suggestion by @mburbea is ~3 times faster and is obviously not dependent on the position of the byte, so it's equally fast for each byte.
ByteSet shows the position of the byte which is set.
An unit test is supplied to check if the values are correct.
Source is here: https://gist.github.com/Tornhoof/c62542a1ccd0c94bf564dcd30052e370 (I apparently can't attach source code to the issue)

A short test on .NET core does not show any bigger differences to the desktop framework (below the full benchmark)

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Xeon(R) CPU E5-1620 0 3.60GHz, ProcessorCount=8
Frequency=3507207 ticks, Resolution=285.1272 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0

Type=FirstByteBenchmark  Mode=Throughput  

Method	ByteSet	Median	StdDev	Gen 0	Gen 1	Gen 2	Bytes Allocated/Op
FirstByteVector	0	4.8814 ns	0.0076 ns	-	-	-	0,00
FirstByteDeBruijn	0	1.8984 ns	0.0172 ns	-	-	-	0,00
FirstByteVector	1	5.7019 ns	0.1184 ns	-	-	-	0,00
FirstByteDeBruijn	1	1.8997 ns	0.0061 ns	-	-	-	0,00
FirstByteVector	2	5.4284 ns	0.0894 ns	-	-	-	0,00
FirstByteDeBruijn	2	1.8990 ns	0.0020 ns	-	-	-	0,00
FirstByteVector	3	6.2405 ns	0.0050 ns	-	-	-	0,00
FirstByteDeBruijn	3	1.8999 ns	0.0088 ns	-	-	-	0,00
FirstByteVector	4	5.4260 ns	0.0829 ns	-	-	-	0,00
FirstByteDeBruijn	4	1.9012 ns	0.0725 ns	-	-	-	0,00
FirstByteVector	5	5.7028 ns	0.0114 ns	-	-	-	0,00
FirstByteDeBruijn	5	1.9014 ns	0.0460 ns	-	-	-	0,00
FirstByteVector	6	5.9679 ns	0.0079 ns	-	-	-	0,00
FirstByteDeBruijn	6	1.8999 ns	0.0637 ns	-	-	-	0,00
FirstByteVector	7	5.6960 ns	0.0138 ns	-	-	-	0,00
FirstByteDeBruijn	7	1.8991 ns	0.0052 ns	-	-	-	0,00

.NET Core

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Windows
Processor=?, ProcessorCount=8
Frequency=3507207 ticks, Resolution=285.1272 ns, Timer=TSC
CLR=CORE, Arch=64-bit ? [RyuJIT]
GC=Concurrent Workstation
dotnet cli version: 1.0.0-preview2-003121

Type=FirstByteBenchmark  Mode=Throughput  

Method	ByteSet	Median	StdDev
FirstByteVector	5	6.2407 ns	0.1725 ns
FirstByteDeBruijn	5	1.8999 ns	0.0118 ns

[benaadams]

Do you run FirstByteBenchmark()?

Else FirstByteVector will be always be examining 4 longs and FirstByteDeBruijn will be examining 1 long as all values will be 0.

[Tornhoof]

I run

 BenchmarkRunner.Run<FirstByteBenchmark>();

Ist that correct?

[mburbea]

Yeah, this is not a complete replacement of that method. It's just a replacement for the conditional check for the active byte.

[Tornhoof]

@mburbea Ah I see, yes, I basically tested the full method vs. only the bitmask replacement part. My bad. I'll update the benchmarks.

[Tornhoof]

I updated the gist https://gist.github.com/Tornhoof/c62542a1ccd0c94bf564dcd30052e370 from above, only replacing the bitmask part and changing the tests, both methods now return the same values for the full 16 byte vector.
I had to reduce the default (automatic) runtime value selection for launcount etc, otherwise it would have taken too long.
There is quiet a bit of standard deviation in there, but it still looks faster, but not by factor of three, but maybe by 25%-30%.

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Xeon(R) CPU E5-1620 0 3.60GHz, ProcessorCount=8
Frequency=3507207 ticks, Resolution=285.1272 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0

Type=FirstByteBenchmark  Mode=Throughput  LaunchCount=1  
WarmupCount=10  TargetCount=10  

Method	ByteSet	Median	StdDev
FirstByteVector	0	4.3446 ns	0.0053 ns
FirstByteDeBruijn	0	3.3739 ns	0.0058 ns
FirstByteVector	1	4.6213 ns	0.0060 ns
FirstByteDeBruijn	1	3.3565 ns	0.0175 ns
FirstByteVector	2	4.3504 ns	0.0144 ns
FirstByteDeBruijn	2	3.3532 ns	0.2117 ns
FirstByteVector	3	4.1054 ns	0.2267 ns
FirstByteDeBruijn	3	3.3453 ns	0.0043 ns
FirstByteVector	4	4.8999 ns	0.0142 ns
FirstByteDeBruijn	4	3.3600 ns	0.0731 ns
FirstByteVector	5	4.0751 ns	0.0031 ns
FirstByteDeBruijn	5	3.3869 ns	0.0073 ns
FirstByteVector	6	4.3458 ns	0.0089 ns
FirstByteDeBruijn	6	3.3822 ns	0.3688 ns
FirstByteVector	7	3.5296 ns	0.0101 ns
FirstByteDeBruijn	7	3.3589 ns	0.0042 ns
FirstByteVector	8	5.7042 ns	0.0260 ns
FirstByteDeBruijn	8	4.3878 ns	0.0058 ns
FirstByteVector	9	5.9792 ns	0.0137 ns
FirstByteDeBruijn	9	4.3745 ns	0.0020 ns
FirstByteVector	10	5.6977 ns	0.0091 ns
FirstByteDeBruijn	10	4.3691 ns	0.0189 ns
FirstByteVector	11	5.4304 ns	0.0049 ns
FirstByteDeBruijn	11	4.3493 ns	0.0026 ns
FirstByteVector	12	6.2619 ns	0.0183 ns
FirstByteDeBruijn	12	4.3479 ns	0.0066 ns
FirstByteVector	13	5.4231 ns	0.0061 ns
FirstByteDeBruijn	13	4.8975 ns	0.0045 ns
FirstByteVector	14	5.6986 ns	0.0067 ns
FirstByteDeBruijn	14	4.5942 ns	0.0064 ns
FirstByteVector	15	4.8933 ns	0.0180 ns
FirstByteDeBruijn	15	4.3534 ns	0.0038 ns

[benaadams]

@Tornhoof thank you, definitely looks worth pursuing.

@mburbea there are two FirstByteVector methods for different endianness; presumably this could be solved by using a different lookup table for the other endianess and make both types fast?

[halter73]

@mburbea Results look good 👍 Thanks for the suggestion and measurements. Are you interested in submitting a PR?

[mburbea]

I think so. Since ((ulong)((v & -v) * DEBRUIJN_SEQ64)) >> 58 returns a unique value from 0-63 for all powers of 2 this means you can probably get the array by saying

Debruijn64BigEndian[i] = 7-Debruijn64[i]

I've found an alternate version of the algorithm which might be faster on intel core i* series hardware with the right compilation.

        const ulong DEBRUIJN_SEQ64 = 0x03f79d71b4cb0a89;
        [MethodImpl(MethodImplOptions.AggressiveInlining)]

        private static int DebruijnFindByteXor(ulong v)
        {
            return Debruijn64Xor[((v ^ (v - 1)) * DEBRUIJN_SEQ64) >> 58];
        }

        private static readonly byte[] Debruijn64Xor =
        {
            0, 5, 0, 7, 6, 3, 0, 7,  7, 6, 5, 4, 3, 2, 0, 7,
            6, 7, 4, 6, 6, 5, 2, 5,  4, 4, 3, 2, 2, 1, 0, 7,
            5, 6, 3, 7, 5, 4, 1, 6,  4, 6, 2, 5, 3, 2, 1, 5,
            3, 4, 1, 4, 2, 3, 1, 3,  1, 2, 1, 1, 0, 0, 0, 7,
        };

And other micro opts like maybe using int[] as they might be faster to index into.

That said the current code gen isn't great on the desktop (and I couldn't get coreCLR to work properly), In practice, a naive safe for loop outperformed it in the average case, because of the bad code gen on the vector types. At least on my haswell I7 :(
When I get home later I'll try on my broadwell.
If this were implemented (extract a bitmask of bytes set) https://github.com/dotnet/corefx/issues/1010#issuecomment-249690575
then a debruijn table may even be faster than the intrinsic for bit scan forward.

edit: probably should include the benchmark
https://gist.github.com/mburbea/d36918c64569b7a6d1d126cfbcd7e020

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Core(TM) i7-4770 CPU 3.40GHz, ProcessorCount=8
Frequency=3312685 ticks, Resolution=301.8699 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0

Type=FirstByteBenchmark  Mode=Throughput  LaunchCount=1
WarmupCount=10  TargetCount=10

Method	ByteSet	Median	StdDev
FirstByteVector	1	17.9186 ns	0.1360 ns
FirstByteDeBruijnXor	1	17.3095 ns	0.0874 ns
FirstByteDeBruijnClassic	1	17.8256 ns	0.0728 ns
FindFirstByteNaive	1	2.4449 ns	0.0225 ns
FirstByteVector	2	17.6520 ns	0.1449 ns
FirstByteDeBruijnXor	2	17.8651 ns	0.2627 ns
FirstByteDeBruijnClassic	2	18.2289 ns	0.2113 ns
FindFirstByteNaive	2	3.7891 ns	0.0497 ns
FirstByteVector	3	17.7570 ns	0.1225 ns
FirstByteDeBruijnXor	3	17.8317 ns	0.1536 ns
FirstByteDeBruijnClassic	3	18.2723 ns	0.1313 ns
FindFirstByteNaive	3	4.2838 ns	0.0626 ns
FirstByteVector	4	17.9409 ns	0.1893 ns
FirstByteDeBruijnXor	4	17.6894 ns	0.4552 ns
FirstByteDeBruijnClassic	4	18.4549 ns	0.2710 ns
FindFirstByteNaive	4	4.9142 ns	0.1071 ns
FirstByteVector	5	17.9950 ns	0.2008 ns
FirstByteDeBruijnXor	5	17.7747 ns	0.1235 ns
FirstByteDeBruijnClassic	5	17.9675 ns	0.1408 ns
FindFirstByteNaive	5	6.0285 ns	0.0437 ns
FirstByteVector	6	17.9405 ns	0.1602 ns
FirstByteDeBruijnXor	6	17.4278 ns	0.1094 ns
FirstByteDeBruijnClassic	6	18.0632 ns	0.1070 ns
FindFirstByteNaive	6	7.1493 ns	0.0530 ns
FirstByteVector	7	18.8065 ns	0.0819 ns
FirstByteDeBruijnXor	7	17.6817 ns	0.0687 ns
FirstByteDeBruijnClassic	7	18.1503 ns	0.0902 ns
FindFirstByteNaive	7	7.1266 ns	0.1713 ns
FirstByteVector	8	19.0887 ns	0.1319 ns
FirstByteDeBruijnXor	8	18.6622 ns	0.1167 ns
FirstByteDeBruijnClassic	8	18.8322 ns	0.3818 ns
FindFirstByteNaive	8	8.9413 ns	0.0888 ns
FirstByteVector	9	18.8609 ns	0.1812 ns
FirstByteDeBruijnXor	9	19.2897 ns	0.2176 ns
FirstByteDeBruijnClassic	9	18.8903 ns	0.3366 ns
FindFirstByteNaive	9	9.3659 ns	0.1795 ns
FirstByteVector	10	18.8856 ns	0.3256 ns
FirstByteDeBruijnXor	10	18.6969 ns	0.1551 ns
FirstByteDeBruijnClassic	10	18.2785 ns	0.0844 ns
FindFirstByteNaive	10	10.3959 ns	0.1025 ns
FirstByteVector	11	19.0604 ns	0.0589 ns
FirstByteDeBruijnXor	11	18.8191 ns	0.1077 ns
FirstByteDeBruijnClassic	11	18.3147 ns	0.1214 ns
FindFirstByteNaive	11	11.4307 ns	0.0511 ns
FirstByteVector	12	19.6556 ns	0.4926 ns
FirstByteDeBruijnXor	12	18.6979 ns	0.2096 ns
FirstByteDeBruijnClassic	12	19.3688 ns	0.1543 ns
FindFirstByteNaive	12	11.7552 ns	0.1944 ns
FirstByteVector	13	19.8004 ns	0.0800 ns
FirstByteDeBruijnXor	13	18.6403 ns	0.0767 ns
FirstByteDeBruijnClassic	13	18.3756 ns	0.1761 ns
FindFirstByteNaive	13	9.4940 ns	0.2266 ns
FirstByteVector	14	19.2997 ns	0.1424 ns
FirstByteDeBruijnXor	14	18.7824 ns	0.1354 ns
FirstByteDeBruijnClassic	14	19.0790 ns	0.3999 ns
FindFirstByteNaive	14	13.2689 ns	0.6779 ns
FirstByteVector	15	19.2776 ns	0.9281 ns
FirstByteDeBruijnXor	15	18.6615 ns	0.0636 ns
FirstByteDeBruijnClassic	15	18.4017 ns	0.0832 ns
FindFirstByteNaive	15	14.4639 ns	0.1979 ns
FirstByteVector	31	20.0605 ns	0.3529 ns
FirstByteDeBruijnXor	31	19.8614 ns	0.0843 ns
FirstByteDeBruijnClassic	31	19.9310 ns	0.1994 ns
FindFirstByteNaive	31	30.5443 ns	0.3698 ns

[benaadams]

@mburbea if you are using full framework you will need to target 4.6.1+ for it to use RyuJit and accelerate the Vector types (may or may not have been the issue you were having)

Though the actual FirstByte method isn't vector accelerated (other than load to long) as its trying to find what triggered the Vector match.

[mburbea]

I targeted 4.6.2 and Vector.IsHardwareAccelerated returned true. I was surprised as well. I don't think this haswell i7 is much worse than the xeon, so it might just be something wrong on my end.

[Tornhoof]

Your benchmark is that much slower because you recreate the vector in each benchmark method

        [Benchmark]
        public int FirstByteDeBruijnClassic()
        {
            var bytes = _vectors[ByteSet];
            var vector = new Vector<byte>(bytes); // <--  here
            return FindFirstEqualByteDeBrujin(ref vector);
        }

        [Benchmark]
        public int FindFirstByteNaive()
        {
            var bytes = _vectors[ByteSet];
            return FindFirstByteNaive(bytes);
        }

which obviously takes some time and you don't do it for your naive code method.

So your results are skewed towards the naive one.