Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > Быстрое деление

Автор: Alix 23.3.2008, 19:05

Друг ковырялся в сорсах Paint.net, а я там увидел такое: Код         // i = z * 3;         // (x / z) = ((x * masTable[i]) + masTable[i + 1]) >> masTable[i + 2)         private static readonly uint[] masTable =          {             0x00000000, 0x00000000, 0,  // 0             0x00000001, 0x00000000, 0,  // 1             0x00000001, 0x00000000, 1,  // 2             0xAAAAAAAB, 0x00000000, 33, // 3             0x00000001, 0x00000000, 2,  // 4             0xCCCCCCCD, 0x00000000, 34, // 5             0xAAAAAAAB, 0x00000000, 34, // 6             0x49249249, 0x49249249, 33, // 7             0x00000001, 0x00000000, 3,  // 8             0x38E38E39, 0x00000000, 33, // 9             0xCCCCCCCD, 0x00000000, 35, // 10             0xBA2E8BA3, 0x00000000, 35, // 11             0xAAAAAAAB, 0x00000000, 35, // 12             0x4EC4EC4F, 0x00000000, 34, // 13             0x49249249, 0x49249249, 34, // 14             0x88888889, 0x00000000, 35, // 15             0x00000001, 0x00000000, 4,  // 16             0xF0F0F0F1, 0x00000000, 36, // 17             0x38E38E39, 0x00000000, 34, // 18             0xD79435E5, 0xD79435E5, 36, // 19             0xCCCCCCCD, 0x00000000, 36, // 20             0xC30C30C3, 0xC30C30C3, 36, // 21             0xBA2E8BA3, 0x00000000, 36, // 22             0xB21642C9, 0x00000000, 36, // 23             0xAAAAAAAB, 0x00000000, 36, // 24             0x51EB851F, 0x00000000, 35, // 25             0x4EC4EC4F, 0x00000000, 35, // 26             0x97B425ED, 0x97B425ED, 36, // 27             0x49249249, 0x49249249, 35, // 28             0x8D3DCB09, 0x00000000, 36, // 29             0x88888889, 0x00000000, 36, // 30             0x42108421, 0x42108421, 35, // 31             0x00000001, 0x00000000, 5,  // 32             0x3E0F83E1, 0x00000000, 35, // 33             0xF0F0F0F1, 0x00000000, 37, // 34             0x75075075, 0x75075075, 36, // 35             0x38E38E39, 0x00000000, 35, // 36             0x6EB3E453, 0x6EB3E453, 36, // 37             0xD79435E5, 0xD79435E5, 37, // 38             0x69069069, 0x69069069, 36, // 39             0xCCCCCCCD, 0x00000000, 37, // 40             0xC7CE0C7D, 0x00000000, 37, // 41             0xC30C30C3, 0xC30C30C3, 37, // 42             0x2FA0BE83, 0x00000000, 35, // 43             0xBA2E8BA3, 0x00000000, 37, // 44             0x5B05B05B, 0x5B05B05B, 36, // 45             0xB21642C9, 0x00000000, 37, // 46             0xAE4C415D, 0x00000000, 37, // 47             0xAAAAAAAB, 0x00000000, 37, // 48             0x5397829D, 0x00000000, 36, // 49             0x51EB851F, 0x00000000, 36, // 50             0xA0A0A0A1, 0x00000000, 37, // 51             0x4EC4EC4F, 0x00000000, 36, // 52             0x9A90E7D9, 0x9A90E7D9, 37, // 53             0x97B425ED, 0x97B425ED, 37, // 54             0x94F2094F, 0x94F2094F, 37, // 55             0x49249249, 0x49249249, 36, // 56             0x47DC11F7, 0x47DC11F7, 36, // 57             0x8D3DCB09, 0x00000000, 37, // 58             0x22B63CBF, 0x00000000, 35, // 59             0x88888889, 0x00000000, 37, // 60             0x4325C53F, 0x00000000, 36, // 61             0x42108421, 0x42108421, 36, // 62             0x41041041, 0x41041041, 36, // 63             0x00000001, 0x00000000, 6,  // 64             0xFC0FC0FD, 0x00000000, 38, // 65             0x3E0F83E1, 0x00000000, 36, // 66             0x07A44C6B, 0x00000000, 33, // 67             0xF0F0F0F1, 0x00000000, 38, // 68             0x76B981DB, 0x00000000, 37, // 69             0x75075075, 0x75075075, 37, // 70             0xE6C2B449, 0x00000000, 38, // 71             0x38E38E39, 0x00000000, 36, // 72             0x381C0E07, 0x381C0E07, 36, // 73             0x6EB3E453, 0x6EB3E453, 37, // 74             0x1B4E81B5, 0x00000000, 35, // 75             0xD79435E5, 0xD79435E5, 38, // 76             0x3531DEC1, 0x00000000, 36, // 77             0x69069069, 0x69069069, 37, // 78             0xCF6474A9, 0x00000000, 38, // 79             0xCCCCCCCD, 0x00000000, 38, // 80             0xCA4587E7, 0x00000000, 38, // 81             0xC7CE0C7D, 0x00000000, 38, // 82             0x3159721F, 0x00000000, 36, // 83             0xC30C30C3, 0xC30C30C3, 38, // 84             0xC0C0C0C1, 0x00000000, 38, // 85             0x2FA0BE83, 0x00000000, 36, // 86             0x2F149903, 0x00000000, 36, // 87             0xBA2E8BA3, 0x00000000, 38, // 88             0xB81702E1, 0x00000000, 38, // 89             0x5B05B05B, 0x5B05B05B, 37, // 90             0x2D02D02D, 0x2D02D02D, 36, // 91             0xB21642C9, 0x00000000, 38, // 92             0xB02C0B03, 0x00000000, 38, // 93             0xAE4C415D, 0x00000000, 38, // 94             0x2B1DA461, 0x2B1DA461, 36, // 95             0xAAAAAAAB, 0x00000000, 38, // 96             0xA8E83F57, 0xA8E83F57, 38, // 97             0x5397829D, 0x00000000, 37, // 98             0xA57EB503, 0x00000000, 38, // 99             0x51EB851F, 0x00000000, 37, // 100             0xA237C32B, 0xA237C32B, 38, // 101             0xA0A0A0A1, 0x00000000, 38, // 102             0x9F1165E7, 0x9F1165E7, 38, // 103             0x4EC4EC4F, 0x00000000, 37, // 104             0x27027027, 0x27027027, 36, // 105             0x9A90E7D9, 0x9A90E7D9, 38, // 106             0x991F1A51, 0x991F1A51, 38, // 107             0x97B425ED, 0x97B425ED, 38, // 108             0x2593F69B, 0x2593F69B, 36, // 109             0x94F2094F, 0x94F2094F, 38, // 110             0x24E6A171, 0x24E6A171, 36, // 111             0x49249249, 0x49249249, 37, // 112             0x90FDBC09, 0x90FDBC09, 38, // 113             0x47DC11F7, 0x47DC11F7, 37, // 114             0x8E78356D, 0x8E78356D, 38, // 115             0x8D3DCB09, 0x00000000, 38, // 116             0x23023023, 0x23023023, 36, // 117             0x22B63CBF, 0x00000000, 36, // 118             0x44D72045, 0x00000000, 37, // 119             0x88888889, 0x00000000, 38, // 120             0x8767AB5F, 0x8767AB5F, 38, // 121             0x4325C53F, 0x00000000, 37, // 122             0x85340853, 0x85340853, 38, // 123             0x42108421, 0x42108421, 37, // 124             0x10624DD3, 0x00000000, 35, // 125             0x41041041, 0x41041041, 37, // 126             0x10204081, 0x10204081, 35, // 127             0x00000001, 0x00000000, 7,  // 128             0x0FE03F81, 0x00000000, 35, // 129             0xFC0FC0FD, 0x00000000, 39, // 130             0xFA232CF3, 0x00000000, 39, // 131             0x3E0F83E1, 0x00000000, 37, // 132             0xF6603D99, 0x00000000, 39, // 133             0x07A44C6B, 0x00000000, 34, // 134             0xF2B9D649, 0x00000000, 39, // 135             0xF0F0F0F1, 0x00000000, 39, // 136             0x077975B9, 0x00000000, 34, // 137             0x76B981DB, 0x00000000, 38, // 138             0x75DED953, 0x00000000, 38, // 139             0x75075075, 0x75075075, 38, // 140             0x3A196B1F, 0x00000000, 37, // 141             0xE6C2B449, 0x00000000, 39, // 142             0xE525982B, 0x00000000, 39, // 143             0x38E38E39, 0x00000000, 37, // 144             0xE1FC780F, 0x00000000, 39, // 145             0x381C0E07, 0x381C0E07, 37, // 146             0xDEE95C4D, 0x00000000, 39, // 147             0x6EB3E453, 0x6EB3E453, 38, // 148             0xDBEB61EF, 0x00000000, 39, // 149             0x1B4E81B5, 0x00000000, 36, // 150             0x36406C81, 0x00000000, 37, // 151             0xD79435E5, 0xD79435E5, 39, // 152             0xD62B80D7, 0x00000000, 39, // 153             0x3531DEC1, 0x00000000, 37, // 154             0xD3680D37, 0x00000000, 39, // 155             0x69069069, 0x69069069, 38, // 156             0x342DA7F3, 0x00000000, 37, // 157             0xCF6474A9, 0x00000000, 39, // 158             0xCE168A77, 0xCE168A77, 39, // 159             0xCCCCCCCD, 0x00000000, 39, // 160             0xCB8727C1, 0x00000000, 39, // 161             0xCA4587E7, 0x00000000, 39, // 162             0xC907DA4F, 0x00000000, 39, // 163             0xC7CE0C7D, 0x00000000, 39, // 164             0x634C0635, 0x00000000, 38, // 165             0x3159721F, 0x00000000, 37, // 166             0x621B97C3, 0x00000000, 38, // 167             0xC30C30C3, 0xC30C30C3, 39, // 168             0x60F25DEB, 0x00000000, 38, // 169             0xC0C0C0C1, 0x00000000, 39, // 170             0x17F405FD, 0x17F405FD, 36, // 171             0x2FA0BE83, 0x00000000, 37, // 172             0xBD691047, 0xBD691047, 39, // 173             0x2F149903, 0x00000000, 37, // 174             0x5D9F7391, 0x00000000, 38, // 175             0xBA2E8BA3, 0x00000000, 39, // 176             0x5C90A1FD, 0x5C90A1FD, 38, // 177             0xB81702E1, 0x00000000, 39, // 178             0x5B87DDAD, 0x5B87DDAD, 38, // 179             0x5B05B05B, 0x5B05B05B, 38, // 180             0xB509E68B, 0x00000000, 39, // 181             0x2D02D02D, 0x2D02D02D, 37, // 182             0xB30F6353, 0x00000000, 39, // 183             0xB21642C9, 0x00000000, 39, // 184             0x1623FA77, 0x1623FA77, 36, // 185             0xB02C0B03, 0x00000000, 39, // 186             0xAF3ADDC7, 0x00000000, 39, // 187             0xAE4C415D, 0x00000000, 39, // 188             0x15AC056B, 0x15AC056B, 36, // 189             0x2B1DA461, 0x2B1DA461, 37, // 190             0xAB8F69E3, 0x00000000, 39, // 191             0xAAAAAAAB, 0x00000000, 39, // 192             0x15390949, 0x00000000, 36, // 193             0xA8E83F57, 0xA8E83F57, 39, // 194             0x15015015, 0x15015015, 36, // 195             0x5397829D, 0x00000000, 38, // 196             0xA655C439, 0xA655C439, 39, // 197             0xA57EB503, 0x00000000, 39, // 198             0x5254E78F, 0x00000000, 38, // 199             0x51EB851F, 0x00000000, 38, // 200             0x028C1979, 0x00000000, 33, // 201             0xA237C32B, 0xA237C32B, 39, // 202             0xA16B312F, 0x00000000, 39, // 203             0xA0A0A0A1, 0x00000000, 39, // 204             0x4FEC04FF, 0x00000000, 38, // 205             0x9F1165E7, 0x9F1165E7, 39, // 206             0x27932B49, 0x00000000, 37, // 207             0x4EC4EC4F, 0x00000000, 38, // 208             0x9CC8E161, 0x00000000, 39, // 209             0x27027027, 0x27027027, 37, // 210             0x9B4C6F9F, 0x00000000, 39, // 211             0x9A90E7D9, 0x9A90E7D9, 39, // 212             0x99D722DB, 0x00000000, 39, // 213             0x991F1A51, 0x991F1A51, 39, // 214             0x4C346405, 0x00000000, 38, // 215             0x97B425ED, 0x97B425ED, 39, // 216             0x4B809701, 0x4B809701, 38, // 217             0x2593F69B, 0x2593F69B, 37, // 218             0x12B404AD, 0x12B404AD, 36, // 219             0x94F2094F, 0x94F2094F, 39, // 220             0x25116025, 0x25116025, 37, // 221             0x24E6A171, 0x24E6A171, 37, // 222             0x24BC44E1, 0x24BC44E1, 37, // 223             0x49249249, 0x49249249, 38, // 224             0x91A2B3C5, 0x00000000, 39, // 225             0x90FDBC09, 0x90FDBC09, 39, // 226             0x905A3863, 0x905A3863, 39, // 227             0x47DC11F7, 0x47DC11F7, 38, // 228             0x478BBCED, 0x00000000, 38, // 229             0x8E78356D, 0x8E78356D, 39, // 230             0x46ED2901, 0x46ED2901, 38, // 231             0x8D3DCB09, 0x00000000, 39, // 232             0x2328A701, 0x2328A701, 37, // 233             0x23023023, 0x23023023, 37, // 234             0x45B81A25, 0x45B81A25, 38, // 235             0x22B63CBF, 0x00000000, 37, // 236             0x08A42F87, 0x08A42F87, 35, // 237             0x44D72045, 0x00000000, 38, // 238             0x891AC73B, 0x00000000, 39, // 239             0x88888889, 0x00000000, 39, // 240             0x10FEF011, 0x00000000, 36, // 241             0x8767AB5F, 0x8767AB5F, 39, // 242             0x86D90545, 0x00000000, 39, // 243             0x4325C53F, 0x00000000, 38, // 244             0x85BF3761, 0x85BF3761, 39, // 245             0x85340853, 0x85340853, 39, // 246             0x10953F39, 0x10953F39, 36, // 247             0x42108421, 0x42108421, 38, // 248             0x41CC9829, 0x41CC9829, 38, // 249             0x10624DD3, 0x00000000, 36, // 250             0x828CBFBF, 0x00000000, 39, // 251             0x41041041, 0x41041041, 38, // 252             0x81848DA9, 0x00000000, 39, // 253             0x10204081, 0x10204081, 36, // 254             0x80808081, 0x00000000, 39  // 255         }; Заинтересовался, решил проверить. Программа на дельфи прилагается. К ней пара комментариев: добавление в memo использовалось чтобы обмануть оптимизатор, иначе даже при втором цикле от 0..255 ошибки деления на ноль не возникало! тип int64 в masTable был применен в связи с тем, что shr/shl в дельфе не сдвигает на большее число разрядов, чем размер типа сдвигаемой переменной, он берет модуль по ее длине Однако проверив, я получил несколько странные результаты:                                                                 Result 1                               Result 2                         Result 3 div                                                            72375                                  67547                            52928 non-optimized div {$O-}                          71031                                  90500                            48969 divide routine                                            70359                                177016                           49031 direct code                                                70422                                154515                           49562 direct code + var                                       70734                                131293                           49125 Resul1 получен мной на core2duo, result2 на p4, result3 на Сeleron. Я вот думаю, может это потому так, что там проц 32 разрядный? Но ведь третий тест тоже для 32 разрядного был. Или я некорректно написал тест. В общем не понятно, стоит ли использовать подобную процедуру. Что думаете?

Автор: Alexeis 23.3.2008, 19:16

Alix, подробнее что это такое? В каких единицах результат? Что измеряется?

Автор: Alix 23.3.2008, 19:22

Цитата(Alexeis @  23.3.2008,  19:16 ) Alix, подробнее что это такое? В каких единицах результат? Что измеряется?  Код   memo1.Lines.BeginUpdate;   timeStart := GetTickCount;   for i := 1 to iter do     for j := 0 to 255 do       for k := 1 to 255 do begin         r := ...;          // вот этот блок меняется для различного способа деления         memo1.Lines.add(inttostr(r));       end;   timeFinish := GetTickCount;   Memo1.Lines.EndUpdate;   Memo1.Lines.Clear;   labelX.Caption := IntToStr(timeFinish - timeStart);   Application.ProcessMessages; блок кода, выполняющий измерение. iter = 10. Подставляются следующие куски кода (в порядке перечисления в посте выше): Код r := j div k; Код r := j div k;  (но весь цикл от timeStart до timeFinish обрамлен {$O-} ... {$O+}) Код r := divide(j, k); где function divide(const x, z : byte) : byte; var i : longword; begin   i := z * 3;   result := ((x * masTable[i]) + masTable[i + 1]) shr masTable[i + 2]; end; Код r := ((j * masTable[k * 3]) + masTable[k * 3 + 1]) shr masTable[k * 3 + 2]; Код t := k * 3; r := ((j * masTable[t]) + masTable[t + 1]) shr masTable[t + 2]; массив описан так: Код masTable : array [0..256*3-1] of int64 = (...);

Автор: Alexeis 23.3.2008, 19:33

memo1.Lines.add(inttostr®); - так не годиться, это нужно убрать. Максимум создать массив интов статического размера и туда записывать значение... и то врать будет страшно. Лучше не делать совсем этого при выключенной оптимизации. И использовать QuoeryPerformance для измерение периодов времени.

Автор: Alix 23.3.2008, 19:42

Цитата(Alexeis @  23.3.2008,  19:33 ) Лучше не делать совсем этого при выключенной оптимизации. она выключена только для второго теста, для всех остальных - по умолчанию.  Цитата(Alexeis @  23.3.2008,  19:33 ) И использовать QuoeryPerformance для измерение периодов времени.  Это даст точность? В принципе для ее повышения я и делаю десять итераций, разница в 2сек - это уже довольно много чтобы считать погрешностью или я не прав?

Автор: Alexeis 23.3.2008, 19:48

Цитата(Alix @  23.3.2008,  18:42 ) Это даст точность? В принципе для ее повышения я и делаю десять итераций, разница в 2сек - это уже довольно много чтобы считать погрешностью или я не прав?   Чем больше итераций тем тем сильнее кэширование + прерывания других процессов. Итераций 10 вполне хватит. Лучше не делать никаких добавлений -  memo1.Lines.add эта операция в 1000 раз дольше деления и весь тест идет насмарку.

Автор: Alix 23.3.2008, 19:51

изменил так: Код   // добавил в public-секцию формы   res : array [0..255,1..255] of integer;   // и блок теста   for i := 1 to iter do     for j := 0 to 255 do       for k := 1 to 255 do begin         res[j, k] := ...;          // вот этот блок меняется для различного способа деления       end; Сделал iter = 10000, такие результаты: 5250 5156 13875 13078 16688 как то совсем не в пользу быстрого деления... Но ведь его не дураки придумали, значит либо тестирую не так, либо что-то еще... Добавлено @ 19:52 Цитата(Alexeis @  23.3.2008,  19:48 ) Чем больше итераций тем тем сильнее кэширование + прерывания других процессов. Итераций 10 вполне хватит. ага... возможно... попробую с perfomancequery Добавлено @ 19:58 С использованием QueryPerformanceCounter, результаты (в попугаях) таковы (iter=10): 45561 50252 158851 131384 112994 Мдя...

Автор: Alexeis 23.3.2008, 19:58

Alix, еще такой интересный факт. Обращение к большим глобальным массивам тоже может оказаться дольше деления.

Автор: Alix 23.3.2008, 20:02

Цитата(Alexeis @  23.3.2008,  19:58 ) Alix, еще такой интересный факт. Обращение к большим глобальным массивам тоже может оказаться дольше деления.   возможно, но ведь это обращение у всех методов одинаково, разница только в делении.

Автор: bems 26.3.2008, 18:53

Цитата(Alix @  23.3.2008,  19:22 ) function divide(const x, z : byte) : byte; var i : longword; begin   i := z * 3;   result := ((x * masTable[i]) + masTable[i + 1]) shr masTable[i + 2]; end; один только вызов функции время отнимает.  Цитата(Alix @  23.3.2008,  19:05 ) тип int64 в masTable был применен в связи с тем, что shr/shl в дельфе не сдвигает на большее число разрядов, чем размер типа сдвигаемой переменной, он берет модуль по ее длине помоему всегда на 32, даже если тип операнда byte или word

Автор: Alix 26.3.2008, 23:12

Цитата(bems @  26.3.2008,  18:53 ) один только вызов функции время отнимает. Разумеется. Но там есть вызов и без функции. Мне было интересно проверить, если такое деление будет достаточно быстрым, будет ли так же быстрым оно при вызове из функии. Цитата(bems @  26.3.2008,  18:53 ) помоему всегда на 32, даже если тип операнда byte или word Оказалось, что да. Однако вот из хелпа:  Цитата Note that the value of y is interpreted modulo the size of the type of x. Thus for example, if x is an integer, x shl 40 is interpreted as x shl 8 because an integer is 32 bits and 40 mod 32 is 8.  Причем компилятор не дает сделать shr 33, например, но если записать через переменную x := 33; w := w shr x; то компиляция проходит, но сдвигает только на 1 бит.

Автор: Esperito 28.3.2008, 23:02

Я немного изменил программу и взял другой счётчик. Если проводить несколько тестов, дабы исключить всякие случаи ухода процессора на другие задачи, получается примерно вот такое: div                                                            29492530 non-optimized div {$O-}                          29403580 divide routine                                           46843200 direct code                                               38055380 direct code + var                                      53020300

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)