Sign in Join
Wiki copytemporary

Vectorization: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Vectorization

OldNewLine
1+*Editor's note:* This page has been set up as a collaboration and design specification for the proposal to include vectorization support in the `x86` and `x86_64` variant of the [[FPC]] (using SSE or AVX to reduce the number of instructions, and hence the execution speed, required to encode functionality). Eventually, this page can be converted into a guide to the optimizer once vectorization is at least partially supported. —CuriousKit ([[User talk:CuriousKit|talk]]) 22:52, 11 December 2017 (CET)
2+
3+## Vector types
4+
5+As of , only static arrays of [[Single|singles]] or [[Double|doubles]] are considered vector types, but they are unaligned unless enforced by additional compiler directives. [[Dynamic array|Dynamic arrays]] and [[Pointer|pointers]] to singles or doubles are currently not considered to be vectors.
6+
7+## Loop optimization
8+
9+Coupled with loop unrolling, it is possible to theoretically reduce the number of cycles by a factor of four or eight, depending on if SSE2 or AVX2 is used. It depends on the code contained within the loop, but if it utilizes only relatively simple arithmetic and pointer movement (e.g. reading and writing sequentially from/to an array), then it might be vectorized with relatively great ease.
10+
11+For example:
12+
13+``` pascal
14+var
15+ input0, input1, output: array of cardinal;
16+ x: integer;
17+
18+begin
19+ assert(length(input0) = length(input1));
20+ SetLength(output, length(input0));
21+
22+ for x := 0 to length(input0)-1 do
23+ begin
24+ output[x] := input0[x] * input1[x];
25+ end;
26+end;
27+```
28+
29+While the size of the inputs is not immediately known, it can be seen that the array sizes do not change within the loop and hence `length(input0)` is constant. Visualizing how the compiler might evaluate the code, it could be internally changed to the following:
30+
31+``` pascal
32+var
33+ input0, input1, output: array of cardinal;
34+ x, arrayLen: integer;
35+
36+begin
37+ assert(length(input0) = length(input1));
38+ SetLength(output, length(input0));
39+
40+ arrayLen := length(input0) div 4;
41+
42+ for x := 0 to arrayLen - 1 do
43+ begin
44+ output[4 * x + 0] := input0[4 * x + 0] * input1[4 * x + 0];
45+ output[4 * x + 1] := input0[4 * x + 1] * input1[4 * x + 1];
46+ output[4 * x + 2] := input0[4 * x + 2] * input1[4 * x + 2];
47+ output[4 * x + 3] := input0[4 * x + 3] * input1[4 * x + 3];
48+ end;
49+
50+ // Handle leftover array entries individually
51+ // (count = length(input0) mod 4).
52+end;
53+```
54+
55+As such, the four statements in the converted for-loop can be easily assembled into SSE2 opcodes (although `pmulld` is SSE4.1), even with potentially unaligned memory. For example:
56+
57+``` asm
58+ lea r8, output[0] ; r8 := @output
59+ lea r9, input0[0] ; r9 := @input0
60+ lea r10, input1[0] ; r10 := @input1
61+
62+ mov ecx, input0_len ; Calculate length(input0), a function call, beforehand and store in ecx
63+ xor rbx, rbx ; rbx := 0 - this is our index array
64+
65+ shr ecx, 2 ; Divide the length by 4, since we're processing 4 values at once.
66+ jz @loop_exit ; Don't enter loop if the length is less than 4
67+
68+@vectorized_loop:
69+ movdqu xmm0, [r9 + rbx * 4] ; Take 4 DWords from input0 and store in xmm0
70+ pmulld xmm0, [r10 + rbx * 4] ; xmm0 := xmm0[0..3] * (input1)^[0..3]
71+ movdqu [r8 + rbx * 4], xmm0 ; Store result in output.
72+
73+ inc rbx ; increment index
74+ dec ecx
75+ ja @vectorized_loop ; if ecx > 0 then repeat loop with incremented index
76+
77+@loop_exit:
78+ ; Handle last few entries separately (count = input0_len mod 4)
79+```
80+
81+Further optimizations can be achieved, for example, by performing two reads, multiplies and writes per loop cycle, taking advantage of the fact that modern processors have more than one SIMD port to send instructions to.
82+
83+## See also
84+
85+- [Free Pascal Programmer's Guide, Chapter 5: “Intel MMX support”](https://www.freepascal.org/docs-html/prog/progch5.html)
86+- [Unit `mmx`](https://www.freepascal.org/docs-html/rtl/mmx/index.html)
87+
88+---
89+*From the Free Pascal wiki, page "Vectorization", as it stood on 2023-09-20 after a change by RogueScholar, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*
90+Category: FPC
91+Category: Proposals

Back to history