Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > 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)