Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C# compare 3 byte field

EDIT

The cmp instructions that are not used are to cause a NullPointerException.

What are these strange cmp [ecx], ecx instructions doing in my C# code?

ORIGINAL POST (even more edits below)

I'm trying to understand the way the JIT compiles code.

In memory I have a 3 char field. In c++ to compare two such fields I can do this:

return ((*(DWORD*)p) & 0xFFFFFF00) == ((*(DWORD*)q) & 0xFFFFFF00);

MSVC 2010 will generate something like this (from memory):

 1 mov         edx,dword ptr [rsp+8] 
 2 and         edx,0FFFFFF00h 
 3 mov         ecx,dword ptr [rsp] 
 4 and         ecx,0FFFFFF00h 
 5 cmp         edx,ecx 

In C#, I am trying to figure out how to get as close to that as I can. We have records made up of a lot of 1,2,3,4,5,6,7,8 byte fields. I have tested a lot of different ways in c# to build a larger struct representing a record using smaller structs of those sizes. I am not satisfied with the assembly code. Right now I am playing with something like this:

[StructLayout(LayoutKind.Sequential, Size = 3)]
public unsafe struct KLF3
{
    public fixed byte Field[3];
    public bool Equals(ref KLF3 r)
    {
        fixed (byte* p = Field, q = r.Field)
        {
            return ((*(UInt32*)p) & 0xFFFFFF00) == ((*(UInt32*)q) & 0xFFFFFF00);
        }
    }
}

But I have two problems. Problem one is the compiler generates a lot of useless looking code:

            fixed (byte* p = Field, q = r.Field)
 1 sub         rsp,18h 
 2 mov         qword ptr [rsp+8],0 
 3 mov         qword ptr [rsp],0 
 4 cmp         byte ptr [rcx],0 
 5 mov         qword ptr [rsp+8],rcx 
 6 cmp         byte ptr [rdx],0 
 7 mov         qword ptr [rsp],rdx 
                return ((*(UInt32*)p) & 0xFFFFFF00) == ((*(UInt32*)q) & 0xFFFFFF00);
 8 mov         rax,qword ptr [rsp+8] 
 9 mov         edx,dword ptr [rax] 
10 and         edx,0FFFFFF00h 
11 mov         rax,qword ptr [rsp] 
12 mov         ecx,dword ptr [rax] 
13 and         ecx,0FFFFFF00h 
14 xor         eax,eax 
15 cmp         edx,ecx 
16 sete        al 
17 add         rsp,18h 
18 ret 

Lines 2,3,4,5,6,7 seem useless since we could just use the register rcx and rdx and not need line 8 and line 11. lines 4 and 6 seem useless, since nothing is using the result of the cmp. I see a lot of these useless cmps in .net code.

Problem two is I cant get the compiler to inline the Equals function. In fact I'm having a hard time seeing anything go inline.

Any tips to get this to compile better? I'm using visual studio 2010 and .net version 4. I am working to get 4.5 installed and visual studio 2013, but that might take a few more days.

EDIT

So i tried a bunch of alternates

This produces better looking code, but still kinda long:

[StructLayout(LayoutKind.Sequential, Size = 3, Pack = 1)]
public unsafe struct KLF31
{
    public UInt16 pos0_1;
    public byte pos2;
    public bool Equals(ref KLF31 r)
    {
        return pos0_1 == r.pos0_1 && pos2 == r.pos2;
    }
}
            return pos0_1 == r.pos0_1 && pos2 == r.pos2;
00000000  mov         r8,rdx 
00000003  mov         rdx,rcx 
00000006  movzx       ecx,word ptr [rdx] 
00000009  movzx       eax,word ptr [r8] 
0000000d  cmp         ecx,eax 
0000000f  jne         0000000000000025 
00000011  movzx       ecx,byte ptr [rdx+2] 
00000015  movzx       eax,byte ptr [r8+2] 
0000001a  xor         edx,edx 
0000001c  cmp         ecx,eax 
0000001e  sete        dl 
00000021  mov         al,dl 
00000023  jmp         0000000000000027 
00000025  xor         eax,eax 
00000027  rep ret 

This one is pretty lean, except the struct size is 4 bytes instead of 3.

[StructLayout(LayoutKind.Explicit, Size = 3, Pack = 1)]
public unsafe struct KLF33
{
    [FieldOffset(0)] public UInt32 pos0_3;
    public bool Equals(ref KLF33 r)
    {
        return (pos0_3 & 0xFFFFFF00) == (r.pos0_3 & 0xFFFFFF00);
    }
}
            return (pos0_3 & 0xFFFFFF00) == (r.pos0_3 & 0xFFFFFF00);
00000000  mov         rax,rdx 
00000003  mov         edx,dword ptr [rcx] 
00000005  and         edx,0FFFFFF00h 
0000000b  mov         ecx,dword ptr [rax] 
0000000d  and         ecx,0FFFFFF00h 
00000013  xor         eax,eax 
00000015  cmp         edx,ecx 
00000017  sete        al 
0000001a  ret 

This one looks just like the crappy fixed char array, as expected:

[StructLayout(LayoutKind.Sequential, Size = 3, Pack = 1)]
public unsafe struct KLF34
{
    public byte pos0, pos1, pos2;
    public bool Equals(ref KLF34 r)
    {
        fixed (byte* p = &pos0, q = &r.pos0)
        {
            return ((*(UInt32*)p) & 0xFFFFFF00) == ((*(UInt32*)q) & 0xFFFFFF00);
        }
    }
}
            fixed (byte* p = &pos0, q = &r.pos0)
00000000  sub         rsp,18h 
00000004  mov         qword ptr [rsp+8],0 
0000000d  mov         qword ptr [rsp],0 
00000015  cmp         byte ptr [rcx],0 
00000018  mov         qword ptr [rsp+8],rcx 
0000001d  cmp         byte ptr [rdx],0 
00000020  mov         qword ptr [rsp],rdx 
            {
                return ((*(UInt32*)p) & 0xFFFFFF00) == ((*(UInt32*)q) & 0xFFFFFF00);
00000024  mov         rax,qword ptr [rsp+8] 
00000029  mov         edx,dword ptr [rax] 
0000002b  and         edx,0FFFFFF00h 
00000031  mov         rax,qword ptr [rsp] 
00000035  mov         ecx,dword ptr [rax] 
00000037  and         ecx,0FFFFFF00h 
0000003d  xor         eax,eax 
0000003f  cmp         edx,ecx 
00000041  sete        al 
00000044  add         rsp,18h 
00000048  ret 

EDIT

In response to Hans, here is sample code.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;
using System.Reflection;
using System.Runtime.InteropServices;

namespace ConsoleApplication2
{
    [StructLayout(LayoutKind.Sequential, Size = 3)]
    public unsafe struct KLF30
    {
        public fixed byte Field[3];
        public bool Equals(ref KLF30 r)
        {
            fixed (byte* p = Field, q = r.Field)
            {
                return ((*(UInt32*)p) & 0xFFFFFF00) == ((*(UInt32*)q) & 0xFFFFFF00);
            }
        }
        public bool Equals1(ref KLF30 r)
        {
            fixed (byte* p = Field, q = r.Field)
            {
                return p[0] == q[0] && p[1] == q[1] && p[2] == q[2];
            }
        }
        public bool Equals2(ref KLF30 r)
        {
            fixed (byte* p = Field, q = r.Field)
            {
                return p[0] == q[0] && p[1] == q[1] && p[2] == q[2];
            }
        }
    }

    [StructLayout(LayoutKind.Sequential, Size = 3, Pack = 1)]
    public unsafe struct KLF31
    {
        public UInt16 pos0_1;
        public byte pos2;
        public bool Equals(ref KLF31 r)
        {
            return pos0_1 == r.pos0_1 && pos2 == r.pos2;
        }
    }

    [StructLayout(LayoutKind.Sequential, Size = 3, Pack = 1)]
    public unsafe struct KLF32
    {
        public fixed byte Field[3];
        public bool Equals(ref KLF32 r)
        {
            fixed (byte* p = Field, q = r.Field)
            {
                return EqualsImpl(p, q);
            }
        }
        private bool EqualsImpl(byte* p, byte* q)
        {
            return (*(uint*)p & 0xffffff) == (*(uint*)q & 0xffffff);
        }
    }

    [StructLayout(LayoutKind.Explicit, Size = 3, Pack = 1)]
    public unsafe struct KLF33
    {
        [FieldOffset(0)]
        public UInt32 pos0_3;
        public bool Equals(ref KLF33 r)
        {
            return (pos0_3 & 0xFFFFFF00) == (r.pos0_3 & 0xFFFFFF00);
        }
    }

    [StructLayout(LayoutKind.Sequential, Size = 3, Pack = 1)]
    public unsafe struct KLF34
    {
        public byte pos0, pos1, pos2;
        public bool Equals(ref KLF34 r)
        {
            fixed (byte* p = &pos0, q = &r.pos0)
            {
                return ((*(UInt32*)p) & 0xFFFFFF00) == ((*(UInt32*)q) & 0xFFFFFF00);
            }
        }
    }

    [StructLayout(LayoutKind.Explicit)]
    public struct Klf
    {
        [FieldOffset(0)] public char pos0;
        [FieldOffset(1)] public char pos1;
        [FieldOffset(2)] public char pos2;
        [FieldOffset(3)] public char pos3;
        [FieldOffset(4)] public char pos4;
        [FieldOffset(5)] public char pos5;
        [FieldOffset(6)] public char pos6;
        [FieldOffset(7)] public char pos7;

        [FieldOffset(0)] public UInt16 pos0_1;
        [FieldOffset(2)] public UInt16 pos2_3;
        [FieldOffset(4)] public UInt16 pos4_5;
        [FieldOffset(6)] public UInt16 pos6_7;

        [FieldOffset(0)] public UInt32 pos0_3;
        [FieldOffset(4)] public UInt32 pos4_7;

        [FieldOffset(0)] public UInt64 pos0_7;
    }

    [StructLayout(LayoutKind.Sequential, Size = 3)]
    public unsafe struct KLF35
    {
        public Klf Field;
        public bool Equals(ref KLF35 r)
        {
            return (Field.pos0_3 & 0xFFFFFF00) == (r.Field.pos0_3 & 0xFFFFFF00);
        }
    }

    public unsafe class KlrAAFI
    {
        [StructLayout(LayoutKind.Sequential, Pack = 1)]
        public struct _AAFI
        {
            public KLF30 AirlineCxrCode0;
            public KLF31 AirlineCxrCode1;
            public KLF32 AirlineCxrCode2;
            public KLF33 AirlineCxrCode3;
            public KLF34 AirlineCxrCode4;
            public KLF35 AirlineCxrCode5;
        }

        public KlrAAFI(byte* pData)
        {
            Data = (_AAFI*)pData;
        }
        public _AAFI* Data;
        public int Size = sizeof(_AAFI);
    }

    class Program
    {
        static unsafe void Main(string[] args)
        {
            byte* foo = stackalloc byte[256];
            var a1 = new KlrAAFI(foo);
            var a2 = new KlrAAFI(foo);
            var p1 = a1.Data;
            var p2 = a2.Data;
            //bool f01= p1->AirlineCxrCode0.Equals (ref p2->AirlineCxrCode0);
            //bool f02= p1->AirlineCxrCode0.Equals1(ref p2->AirlineCxrCode0);
            //bool f03= p1->AirlineCxrCode0.Equals2(ref p2->AirlineCxrCode0);
            //bool f1 = p1->AirlineCxrCode1.Equals (ref p2->AirlineCxrCode1);
            bool f2 = p1->AirlineCxrCode2.Equals (ref p2->AirlineCxrCode2);
            //bool f3 = p1->AirlineCxrCode3.Equals (ref p2->AirlineCxrCode3);
            //bool f4 = p1->AirlineCxrCode4.Equals (ref p2->AirlineCxrCode4);
            //bool f5 = p1->AirlineCxrCode5.Equals (ref p2->AirlineCxrCode5);
            //int q = f01 | f02 | f03 | f1 | f2 | f3 | f4 ? 0 : 1;
            int q = f2 ? 0 : 1;
            Console.WriteLine("{0} {1} {2} {3} {4} {5}",
                sizeof(KLF30), sizeof(KLF31), sizeof(KLF32), sizeof(KLF33), sizeof(KLF34), sizeof(KLF35));
            Console.WriteLine("{0}", q);
        }
    }
}

When I compile that with all but f2 commented out, i get this:

            var p1 = a1.Data;
0000007b  mov         rax,qword ptr [rdi+8] 
            var p2 = a2.Data;
0000007f  mov         rcx,qword ptr [rbx+8] 
            bool f2 = p1->AirlineCxrCode2.Equals (ref p2->AirlineCxrCode2);
00000083  cmp         byte ptr [rax],0 
00000086  add         rax,10h 
0000008c  cmp         byte ptr [rcx],0 
0000008f  add         rcx,10h 
00000093  xor         edx,edx 
00000095  mov         qword ptr [rbp],rdx 
00000099  mov         qword ptr [rbp+8],rdx 
0000009d  cmp         byte ptr [rax],0 
000000a0  mov         qword ptr [rbp],rax 
000000a4  cmp         byte ptr [rcx],0 
000000a7  mov         qword ptr [rbp+8],rcx 
000000ab  mov         rax,qword ptr [rbp] 
000000af  mov         rcx,qword ptr [rbp+8] 
000000b3  mov         edx,dword ptr [rax] 
000000b5  and         edx,0FFFFFFh 
000000bb  mov         ecx,dword ptr [rcx] 
000000bd  and         ecx,0FFFFFFh 
000000c3  xor         eax,eax 
000000c5  cmp         edx,ecx 
000000c7  sete        al 
000000ca  movzx       ecx,al 
000000cd  movzx       eax,cl 

If you look closely at the assembly, it is inlined as Hans indicated, but most of that asm doesn't do anything. Look at all the useless cmp statements before 000000c5. Look at how many times it moves the same value into and out of rbp and rbp+8. Maybe I don't understand the utility of that.

if you comment out everything except for f1, i get this:

            var p1 = a1.Data;
00000071  mov         rdx,qword ptr [rdi+8] 
            var p2 = a2.Data;
00000075  mov         r8,qword ptr [rbx+8] 
            bool f1 = p1->AirlineCxrCode1.Equals (ref p2->AirlineCxrCode1);
00000079  cmp         byte ptr [rdx],0 
0000007c  cmp         byte ptr [r8],0 
00000080  movzx       ecx,word ptr [rdx+8] 
00000084  movzx       eax,word ptr [r8+8] 
00000089  cmp         ecx,eax 
0000008b  jne         00000000000000A2 
0000008d  movzx       ecx,byte ptr [rdx+0Ah] 
00000091  movzx       eax,byte ptr [r8+0Ah] 
00000096  xor         edx,edx 
00000098  cmp         ecx,eax 
0000009a  sete        dl 
0000009d  movzx       eax,dl 
000000a0  jmp         00000000000000A4 
000000a2  xor         eax,eax 

which still has useless cmp instr 79, 7c, but a lot less overhead.

Seems that fixed generates a lot of (useless?) asm in this case.

like image 256
johnnycrash Avatar asked Aug 27 '14 20:08

johnnycrash


1 Answers

Yes, the optimizer flounders at this code, it isn't very happy about the pinning. You can whack it over the head by writing a separate method:

    public bool Equals(ref KLF3 r) {
        fixed (byte* p = Field, q = r.Field) {
            return EqualsImpl(p, q);
        }
    }
    private unsafe bool EqualsImpl(byte* p, byte* q) {
        return (*(uint*)p & 0xffffff) == (*(uint*)q & 0xffffff);
    }

Which wisens it up to:

0000006b  mov         rax,qword ptr [rsp+20h] 
00000070  mov         rcx,qword ptr [rsp+28h] 
00000075  mov         edx,dword ptr [rax] 
00000077  and         edx,0FFFFFFh 
0000007d  mov         ecx,dword ptr [rcx] 
0000007f  and         ecx,0FFFFFFh 
00000085  xor         eax,eax 
00000087  cmp         edx,ecx 
00000089  sete        al 
0000008c  movzx       ecx,al 
0000008f  movzx       ecx,cl 

Generated inline in the caller method. Also pretty important that you profile a version that doesn't pass the argument by ref, ought to be faster and your current version causes too many accidents. I changed your bitmasks, they ought to be 0xffffff on a little-endian machine.

like image 139
Hans Passant Avatar answered Oct 02 '22 07:10

Hans Passant