Самый быстрый способ построить 64-битное int из четырех 16-битных значений? - PullRequest
Новая
       5

Самый быстрый способ построить 64-битное int из четырех 16-битных значений?

4 голосов
/ 10 февраля 2020

По сути, я пытаюсь создать уникальный 64-битный идентификатор из координат, которые потом можно будет потом разделить. Эти операции будут выполняться в миллиарды раз в короткие сроки, поэтому скорость имеет решающее значение. Вот то, что я после. У меня есть 4 - 32-битные целые числа, но релевантны только младшие 16 бит. Я хочу объединить нижние 16 бит в один 64-битный «long» (не имеет значения, подписан он или нет, поскольку биты одинаковые). Поэтому, если у меня есть: 

largeId = 0000 0000 0000 0000   0000 0000 1000 1000
x       = 0000 0000 0000 0000   0000 0000 1100 1100
y       = 0000 0000 0000 0000   0000 0000 1110 1110
z       = 0000 0000 0000 0000   0000 0000 1111 1111

, оно станет: 

Id = 0000 0000 1000 1000   0000 0000 1100 1100   0000 0000 1110 1110   0000 0000 1111 1111

Я написал несколько подпрограмм, которые дают желаемые результаты (т.е. строит и разделяет), и рассчитал их используя 500 ^ 3 итераций, чтобы попытаться найти самую быструю процедуру. Процедура, которая декодирует 64-битное число обратно в 4 переменные типа int, выполняется примерно в 43% времени, необходимого для их кодирования. Как я могу ускорить кодирование ??

Подпрограммы: (обновлено с изменениями из предложений Пола Смита ниже) 

        public static long GetCombinedId(int largeId, int x, int y, int z)
        {

            var _largeId = (long)largeId;
            var _x = (long)x;
            var _y = (long)y;
            var _z = (long)z;

            return (_largeId << 48) | (_x << 32) | (_y << 16) | _z;

        }

        public static long GetCombinedId2(int largeId, int x, int y, int z)
        {
            return ((long)largeId << 48) | ((long)x << 32) | ((long)y << 16) | (long)z;
        }

        public static long GetCombinedId3(int largeId, int x, int y, int z)
        {
            unchecked
            {
                return ((long)(largeId << 16 | x) << 32) | (y << 16 | z );
            }

        }



        public static void GetCoordinates(long id, out int largeId, out int x, out int y, out int z)
        {

            largeId = (int)(id >> 48);

            x = (int)((id >> 32) & 0x0000_0000_0000_FFFF);
            y = (int)((id >> 16) & 0x0000_0000_0000_FFFF);
            z = (int)(id & 0x0000_0000_0000_FFFF);


        }

        public static void GetCoordinates2(long id, out int largeId, out int x, out int y, out int z)
        {

            largeId = (int)(id >> 48);

            x = (int)((id << 16 ) >> 48);
            y = (int)((id << 32 ) >> 48);
            z = (int)((id << 48 ) >> 48);

        }

Вариации техники Пола Смита, описанные в разделе ответов 

  [StructLayout(LayoutKind.Explicit)]
        public struct Mapper
        {
            [FieldOffset(0)] public Int64 Combined;
            [FieldOffset(0)] public Int16 Short0;
            [FieldOffset(2)] public Int16 Short1;
            [FieldOffset(4)] public Int16 Short2;
            [FieldOffset(6)] public Int16 Short3;
        }

        public static long GetId4(int largeId, int x, int y, int z)
        {

            Mapper mapper = new Mapper()
            {
                Short0 = (Int16)z,
                Short1 = (Int16)y,
                Short2 = (Int16)x,
                Short3 = (Int16)largeId
            };

            return mapper.Combined;

        }

        private static Mapper _mapper = new Mapper();
        public static long GetId5(int largeId, int x, int y, int z)
        {

            _mapper.Short0 = (Int16)z;
            _mapper.Short1 = (Int16)y;
            _mapper.Short2 = (Int16)x;
            _mapper.Short3 = (Int16)largeId;

            return _mapper.Combined;
        }

        [StructLayout(LayoutKind.Explicit)]
        public struct Mapper2
        {
            [FieldOffset(0)] public Int64 Combined;
            [FieldOffset(0)] public Int32 Integer0;
            [FieldOffset(4)] public Int32 Integer1;
        }

        private static Mapper2 _mapper2 = new Mapper2();
        public static long GetId6(int largeId, int x, int y, int z)
        {


            _mapper2.Integer0 = y << 16 | z;   //dangerous because we aren't checking upper bits of z
            _mapper2.Integer1 = largeId << 16 | x; //dangerous because we aren't checking upper bits of x


            return _mapper2.Combined;
        }

Результаты: 

GetId1 = 2168ms
GetId2 = 1824ms
GetId3 = 1679ms
GetId4 = 2217ms
GetId5 = 2008ms
GetId6 = 1757ms
GetCoord1 = 785ms
GetCoord2 = 865ms
Routine1: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine2: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine3: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine4: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine5: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine6: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
255, 170, 187, 204
255, 170, 187, 204

Есть ли лучший / более быстрый способ кодирования 4 целых чисел в длину 64 бита?

(кстати ... класс BitConverter является парализующе медленным и был удален, потому что он не возможно)

Ответы [ 2 ]

1 голос
/ 15 февраля 2020

5 дней спустя, и у меня возник вопрос, когда я принимал душ ... Что если время израсходовано, перемещая возвращаемое значение из локального стека в стек вызывающей процедуры? Оказывается ... это было.

Новый метод, приведенный ниже, использует самый быстрый метод сверху (метод # 3) и вместо возврата переменной (которая вызывает копирование "stack to stack"), я передаю возвращаемое значение в качестве ссылки "out". Это позволяет выполнять вычисления непосредственно в результирующей переменной из вызывающей процедуры.

Делая это ... Теперь я могу кодировать быстрее , чем могу декодировать, что было целью с самого начала , Ниже приведена новая процедура сравнения скорости. 

        public static void GetId7(int largeId, int x, int y, int z, out long id)
        {

            id = ((long)(largeId << 16 | x) << 32) | (y << 16 | z);

        }

Сравнение скорости. GetId7 показывает новые результаты: 

GetId1 = 2282ms
GetId2 = 1910ms
GetId3 = 1782ms
GetId4 = 2306ms
GetId5 = 2092ms
GetId6 = 1816ms
GetId7 = 831ms
GetCoord1 = 828ms
GetCoord2 = 930ms
Routine1: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine2: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine3: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine4: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine5: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine6: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
Routine7: 71776849217913036   binary: 11111111000000001010101000000000101110110000000011001100
255, 170, 187, 204
255, 170, 187, 204

Не то, чтобы это было нужно, но мне любопытно, может ли кто-нибудь получить его еще быстрее.

0 голосов
/ 10 февраля 2020

Это не рассчитано по времени, но, похоже, это позволяет избежать смещения и маскировки 

[StructLayout(LayoutKind.Explicit)]
public struct Mapper
{
   [FieldOffset(0)] public UInt64 Combined;
   [FieldOffset(1)] public UInt16 Short0;
   [FieldOffset(2)] public UInt16 Short1;
   [FieldOffset(3)] public UInt16 Short2;
   [FieldOffset(4)] public UInt16 Short3;
}

Создать Mapper и затем назначить различные значения Shortx. Считайте комбинированное значение; 

var test = new Mapper();
test.Short0 = 1;
test.Short1 = 16;
test.Short2 = 256;
test.Short3 = 4096;

, тогда test.Combined будет 64-битной конкатенацией.

...