Sharing my unit for quickly dividing integer values fastdiv

[ALLIGATOR]

https://github.com/Alligator-1/fastdiv

This unit uses an algorithm that replaces division with multiplication, as many compilers now do when dividing by a constant

It's probably similar to the libdivide library for C

I honestly stole the main algorithm for calculating magic values from the FPC source code

Where can this be applied? For example, where you perform frequent integer division (it is worth noting that I only implemented unsigned division) and the divisor rarely changes

For example, I am currently trying to parse a lot of JSON using FpJSON, and it uses the Contnrs unit under the hood. By replacing div something in its code with this solution, I got an additional 13%⬆️ speedup (the speedup percentage depends on how much work falls on this particular part; I think that if you test the hash table itself, the increase will be even higher!)

Oh, and one more thing: this module is currently only compatible with 🪟Windows x86/x64 and 🐧Linux x64 platforms

[gues1]

Are you sure what have you done ?

Simply adding inline to f1 and f2 function the timing are:

19
30
622
manual: 2635249153387078802, comp: 2635249153387078802

The timing of your new function is about 20 times more slow the normal div functions ....

Are you sure you are measuring the math ops and not the call times ?

[ALLIGATOR]

When you added inline, the compiler simply calculated the value in advance, so no division actually takes place; it simply writes the finished answer based on the number of iterations in the loop (this can be seen if you open the assembler window)

This module, in the part I described—i.e., support for Win_x86/x64 and Linux x64 (although I didn't really test it on Linux x64 (only at the very beginning, when I started writing), but it should work too)—is finished

But there is always room for improvement. For example, while analyzing your example, I found another place for optimization

[ALLIGATOR]

For now, you can change the code to leave it inline and see the difference in performance

There is still room for improvement (depending on the data bit depth), but you need to think about how best to do this

Code: Pascal  [Select][+][-]

1. unit ubench;
2. {$mode objfpc}{$h+}
3.  
4. interface
5.  
6. uses
7.   SysUtils, ufastdiv;
8.  
9. procedure bench(N: Integer);
10.  
11. implementation
12.  
13. function f1(v: NativeUInt): NativeUInt; inline;
14. begin
15.   Result := v div 1909;
16. end;
17.  
18. function f2(v: NativeUInt; k: NativeUInt): NativeUInt; inline;
19. begin
20.   Result := v div k;
21. end;
22.  
23. procedure bench(N: Integer);
24. var
25.   v: NativeUInt = 100000000;
26.   d: NativeUInt = 1909;
27. var
28.   fd: TFastDiv;
29.   i: Integer;
30.   timer: TDateTime;
31. begin
32.   timer:=Now;
33.   for i:=N downto 0 do
34.   begin
35.     f1(v);
36.     f1(v);
37.     f1(v);
38.     f1(v);
39.     f1(v);
40.     f1(v);
41.     f1(v);
42.     f1(v);
43.   end;
44.   WriteLn((Now-timer)*MSecsPerDay:0:0);
45.  
46.   timer:=Now;
47.   for i:=N downto 0 do
48.   begin
49.     f2(v, d);
50.     f2(v, d);
51.     f2(v, d);
52.     f2(v, d);
53.     f2(v, d);
54.     f2(v, d);
55.     f2(v, d);
56.     f2(v, d);
57.   end;
58.   WriteLn((Now-timer)*MSecsPerDay:0:0);
59.  
60.   timer:=Now;
61.   fd.PrepareUnsignedDivision(d);
62.   for i:=N downto 0 do
63.   begin
64.     fd.Divide(v);
65.     fd.Divide(v);
66.     fd.Divide(v);
67.     fd.Divide(v);
68.     fd.Divide(v);
69.     fd.Divide(v);
70.     fd.Divide(v);
71.     fd.Divide(v);
72.   end;
73.   WriteLn((Now-timer)*MSecsPerDay:0:0);
74. end;
75.  
76. end.

My machine (i7-8750H laptop) currently displays the following values for this code:

Code: [Select]

548
4305
1082


[ALLIGATOR]

In fact, it can be improved to near perfection by patching the code... but at first I thought I would avoid doing that, but now I think it can be done...
Initially, I wanted to avoid using assembly language inserts and make this code cross-platform, but that's impossible (while maintaining normal performance), so one way or another, the code on each platform will be individual.

Okay, I'll write back to the thread later when I've finished working on it. Thanks for testing! 

[ALLIGATOR]

Okay, I've refined this library a bit more, and now everything is a little better, and in some cases much better than before (thanks to the FPC developers!)

(i7-8750h, laptop)

Code: [Select]

Unsigned div 32 by const compiler inline:             395 ms,  200000000 iterations
Unsigned div 32 by const compiler:                   1001 ms,  200000000 iterations
Unsigned div 64 by const compiler inline:             556 ms,  200000000 iterations
Unsigned div 64 by const compiler:                   1016 ms,  200000000 iterations

The results of division by a constant are provided for reference only, as the compiler effectively replaces division by multiplication in such cases. Therefore, comparison with the FastDiv method is only useful for understanding the slowdown it introduces relative to these methods (since it cannot currently be efficiently inlined into the code) and the speedup it provides relative to actual division methods.

Unsigned div 32 native inline:                       1284 ms,  200000000 iterations
Unsigned div 32 native:                              1881 ms,  200000000 iterations
Unsigned div 64 native inline:                       4402 ms,  200000000 iterations
Unsigned div 64 native:                              5393 ms,  200000000 iterations
Unsigned div 32 FastDiv:                              939 ms,  200000000 iterations
Unsigned div 64 FastDiv:                             1100 ms,  200000000 iterations

full 32 bit range div u32:
2% 4% 6% 9% 11% 13% 15% 18% 20% 22% 25% 27% 29% 31% 34% 36% 38% 40% 42% 45% 47% 49% 51% 53% 56% 58% 60% 62% 64% 66% 68% 70% 72% 74% 76% 78% 80% 82% 85% 87% 89% 91% 93% 96% 97% 99% 100%
full 32 bit range div u32:
2% 4% 6% 8% 11% 13% 15% 17% 20% 22% 24% 26% 29% 31% 33% 35% 38% 40% 42% 44% 47% 49% 51% 54% 56% 58% 61% 63% 65% 67% 69% 71% 74% 76% 78% 80% 82% 85% 87% 89% 91% 93% 96% 97% 99% 100%
partially 64 bit range:
2% 4% 6% 8% 10% 12% 15% 17% 19% 21% 23% 25% 27% 29% 32% 34% 36% 38% 40% 42% 44% 47% 49% 51% 53% 55% 57% 59% 59% 59% 60% 60% 61% 61% 61% 62% 62% 63% 63% 64% 64% 64% 65% 65% 66% 66% 67% 67% 68% 68% 68% 69% 69% 70% 70% 71% 71% 72% 72% 72% 73% 73% 74% 74% 74% 75% 75% 76% 76% 77% 77% 78% 78% 78% 79% 79% 80% 80% 81% 81% 81% 82% 82% 83% 83% 84% 84% 85% 85% 86% 86% 86% 87% 87% 88% 88% 89% 89% 90% 90% 90% 91% 91% 91% 92% 92% 93% 93% 93% 94% 94% 95% 95% 95% 96% 96% 97% 97% 98% 98% 98% 99% 99% 99% 100%
TRUE, manual32: 24924924, comp32: 24924924
TRUE, manual32: 00000003, comp32: 00000003
TRUE, manual64: 2492492492492492, comp64: 2492492492492492
TRUE, manual64: 0000000000000001, comp64: 0000000000000001

[ALLIGATOR]

Acceleration for 32-bit division: (1284-939)/1284 = 26%
Acceleration for 64-bit division: (4402-1100)/4402 = 75%

Acceleration for 32-bit division: 1284/939 = 1.36x
Acceleration for 64-bit division: 4402/1100 = 4.00x