Case Compiler Optimization: what changed

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

Old	New		Line
1	1		## x86
2	2
3	3		### Jump Table
4	4
5	5		- Complexity O(1).
6	6
7	7		#### Requirements
8	8
9	9		- 50 or more branches.
10	10		- Case labels are not sparse.
11	11
12	12		#### Overview
13	13
14	14		When the number of individual branches grows to a large value, it becomes computationally expensive to test each valid value one-by-one; this is especially the case if a common branch appears at the end of the list (e.g. the largest value of a given set). A jump table seeks to eliminate this penalty by mapping each branch's address into a direct lookup table. Any gaps in the table can easily be filled with an address to the else block (or the end of the case block if one isn't present).
15	15
16	16		Nevertheless, the lookup table is stored separately to the current code block and must be fetched from memory; this, on top of a near jump, consumes a large number of cycles where the CPU is waiting for the address to reach a register, sometimes to the point where it's faster to simply compare the input contained within a register with each case label individually, since the current block of code is already in the cache and all work is done through immediate values. This is why such jump tables are only beneficial with a large number of branches.
17	17
18	18		This system, however, breaks down if the range of values is sparse, since this produces an excessively large lookup table where most addresses point to the else block. Even if storage space is not a concern, fetching the lookup table from memory gets more expensive with size.
19	19
20	20		#### Example
21	21
22	22		Say we have a table with 80 entries ranging from -20 to +70, each containing a 32-bit address, with a few values that don't map onto branches redirected to the else block. Since the domain is 90 (70-(-20)), these are indexed sequentially from 0 to 89, with -20 subtracted (i.e. 20 is added) from the input.
23	23
24	24		Initially, a simple comparison is performed to determine if the input falls within the given range of -20 to +70, and jumps to the else block if not.
25	25
26	26		``` asm
27	27		sub $-20, %input ; min = -20; this will probably be optimised later to "add $20, %index"
28	28		cmp $90, %input ; max-min = 70-(-20) = 90
29	29		ja @ElseBlock
30	30		```
31	31
32	32		This also has the added benefit of remapping %input so the smallest case label is equal to zero.
33	33
34	34		Even though %input contains a signed value, the design of two's complement notation is taken advantage of because if %input was initially less than -20, then it will still be negative after the remapping, hence the highest bit will be set and will appear to be a very large unsigned number when evaluated under the rules of 'jump if above'. In other words, the JA command successfully branches if %index is too small or too large.
35	35
36	36		For the actual lookup, it is a simple matter of scaling the input and adding it to the base address of the jump table. For i386:
37	37
38	38		``` asm
39	39		mov @TableAddress, %addr
40	40		add (%addr,%input,4), %addr ; Note: this assumes that the addresses are relative to the base pointer.
41	41		; If they aren't, this instruction needs to be "mov" instead
42	42		jmp *%addr
43	43		```
44	44
45	45		For x86_64:
46	46
47	47		``` asm
48	48		lea @TableAddress(%rip), %base ; 64-bit address.
49	49		movs (%base,%input,4), %addr ; Jump addresses are strictly 32-bit, even under x86_64.
50	50		add %base, %addr ; Note: this assumes that the addresses are relative to the base pointer.
51	51		; If they aren't, this instruction can be removed
52	52		jmp *%addr
53	53		```
54	54
55	55		If size is not a concern, this could be very slightly optimised by having the jump table sign-extended to 64-bit entries, then code similar to the i386 version can be utilised with one fewer registers used:
56	56
57	57		``` asm
58	58		lea @TableAddress(%rip), %addr
59	59		add (%addr,%input,4), %addr ; Note: this assumes that the addresses are relative to the base pointer.
60	60		; If they aren't, this instruction needs to be "mov" instead
61	61		jmp *%addr
62	62		```
63	63
64	64		#### Entire Range Covered
65	65
66	66		If the entire range of input values is covered, as is the case with an enumerated type, then the initial remapping and range check can be skipped, and all is required is an offset to the reference. For example, if -20 to +70 is the entire valid range:
67	67
68	68		For i386:
69	69
70	70		``` asm
71	71		mov %addr, @TableAddress
72	72		add -80(%addr,%input,4), %addr ; min4 = -204 = -80
73	73		jmp *%addr
74	74		```
75	75
76	76		For x86_64:
77	77
78	78		``` asm
79	79		lea %base, @TableAddress(%rip)
80	80		movs -80(%base,%input,4), %addr ; min4 = -204 = -80
81	81		add %base, %addr
82	82		jmp *%addr
83	83		```
84	84
85	85		Just be warned that this code trusts that the input is sane and isn't set to an ordinal value that is outside of the given valid range (as might happen if the input variable hasn't been initialised). Failure to uphold this prerequisite will cause unpredictable behaviour.
86	86
87	87		### Binary Search Lookup
88	88
89	89		Main article: [Binary search algorithm](https://en.wikipedia.org/wiki/Binary_search_algorithm)
90	90
91	91		- Complexity O(log n)
92	92
93	93		#### Requirements
94	94
95	95		- 32 or more branches.
96	96		- All branches call an identical function. Branches that have multiple case values or ranges are treated as individual branches for each single value.
97	97		- The range of case labels is large, which would make a direct index or hash lookup impractical.
98	98
99	99		##### Most suitable case
100	100
101	101		A case block that evaluates an ordinal value with many identical branches that share a common header design. Example below taken from compiler\x86_64\aoptcpu.pas, lines 68-119:
102	102
103	103		``` pascal
104	104
105	105		{ All subroutines share the form "function(var p: tai): Boolean;" - note that if
106	106		one of them is, say "function(const p: tai): Boolean;", this system won't work }
107	107
108	108		case taicpu(p).opcode of
109	109		A_AND:
110	110		Result:=OptPass1AND(p);
111	111		A_MOV:
112	112		Result:=OptPass1MOV(p);
113	113		A_MOVSX,
114	114		A_MOVZX:
115	115		Result:=OptPass1Movx(p);
116	116		A_VMOVAPS,
117	117		A_VMOVAPD,
118	118		A_VMOVUPS,
119	119		A_VMOVUPD:
120	120		result:=OptPass1VMOVAP(p);
121	121		A_MOVAPD,
122	122		A_MOVAPS,
123	123		A_MOVUPD,
124	124		A_MOVUPS:
125	125		result:=OptPass1MOVAP(p);
126	126		A_VDIVSD,
127	127		A_VDIVSS,
128	128		A_VSUBSD,
129	129		A_VSUBSS,
130	130		A_VMULSD,
131	131		A_VMULSS,
132	132		A_VADDSD,
133	133		A_VADDSS,
134	134		A_VANDPD,
135	135		A_VANDPS,
136	136		A_VORPD,
137	137		A_VORPS,
138	138		A_VXORPD,
139	139		A_VXORPS:
140	140		result:=OptPass1VOP(p);
141	141		A_MULSD,
142	142		A_MULSS,
143	143		A_ADDSD,
144	144		A_ADDSS:
145	145		result:=OptPass1OP(p);
146	146		A_VMOVSD,
147	147		A_VMOVSS,
148	148		A_MOVSD,
149	149		A_MOVSS:
150	150		result:=OptPass1MOVXX(p);
151	151		A_LEA:
152	152		result:=OptPass1LEA(p);
153	153		A_SUB:
154	154		result:=OptPass1Sub(p);
155	155		A_SHL,A_SAL:
156	156		result:=OptPass1SHLSAL(p);
157	157		A_SETcc:
158	158		result:=OptPass1SETcc(p);
159	159		end;
160	160		```
161	161
162	162		#### Table Design
163	163
164	164		Internally, each entry of the lookup table contains two ordinal fields equal to the machine word size, totalling 8 bytes for 32-bit and 16 bytes for 64-bit.
165	165
166	166		``` pascal
167	167		TCaseTableEntry = packed record
168	168		Key: NativeInt;
169	169		ProcAddr: CodePointer;
170	170		end;
171	171
172	172		TCaseTable = array[0..ListSize-1] of TCaseTableEntry;
173	173		```
174	174
175	175		The most important element with this table, as with all binary searches, is that it must be sorted by key in ascending order. Given such case tables are static during runtime, this can be done during compilation using any general-purpose sorting algorithm.
176	176
177	177		#### Iteration Count
178	178
179	179		A binary search divides the eligible list in half with each iteration, meaning its complexity grows with the base-2 logarithm of the list size -- that is, the algorithm is O(log n). While this gives us a rough guide as to the number of times the critical loop will run, it is not an exact answer, and log2(n) is only integral when n is a power of 2. However, if we analyse the workings of the binary search, we can deduce the iteration count:
180	180
181		-	~~<figure>~~
182		-	~~<img src="BinSearch8.png" title="BinSearch8.png" />~~
183		-	~~<figcaption>BinSearch8.png</figcaption>~~
184		-	~~</figure>~~
	181	+	![](/wiki-images/0/01/BinSearch8.png)
185	182
186	183		If we take a list size of 8 and evaluate the midpoint (either one of the two middle values will suffice) and determine it is not a match, we can exclude this value and hence are left with one of two sublists to evaluate, one of size 3 and one of size 4. Given the search may take us to the larger of the two, we have to assume worst-case behaviour. Similarly, at size 4, the sublists are of size 1 and 2, and then at size 2, we are left with either a sublist of 1, a match, or a mismatch, since there is no second sublist. At size 1, we just check if this is the value we are looking for, and if not, then we can conclude that the value does not appear in the list.
187	184
188	185		This evaluates to 3 iterations and a final comparison with the 1-sized sublist. This agrees with the value of log2(8) = 3. This is the simplest case though where the list size is a power of two. If we go one higher to a list size of 9...
189	186
190		-	~~<figure>~~
191		-	~~<img src="BinSearch9.png" title="BinSearch9.png" />~~
192		-	~~<figcaption>BinSearch9.png</figcaption>~~
193		-	~~</figure>~~
	187	+	![](/wiki-images/1/19/BinSearch9.png)
194	188
195	189		Because we can exclude the midpoint, both sublists have a size of 4, and following the worst-case process listed above, this also results in 3 iterations. If we instead reduce the size to 7...
196	190
197		-	~~<figure>~~
198		-	~~<img src="BinSearch7.png" title="BinSearch7.png" />~~
199		-	~~<figcaption>BinSearch7.png</figcaption>~~
200		-	~~</figure>~~
	191	+	![](/wiki-images/9/95/BinSearch7.png)
201	192
202	193		Both sublists are now only size 3, and taking the midpoint of one of these sublists yields a pair of 1-sized sublists, thereby reducing the iteration count to just 2 plus the final comparison.
203	194
204	195		From this, we can deduce that the largest sublist size from a list of size n is equal to floor(n/2). Taken to the logical extreme where the sublist size is an odd number in each division stage, we find that only 3 iterations are required up to an initial list size of 15, since this divides down to 7, then 3, and then we are left with one of two 1-sized sublists that just need a comparison. Such number sequences are all 1s in binary, and this corresponds with values of the form 2<sup>a</sup> - 1, one below the argument that causes log2 to reach its next integral value. Therefore, we can conclude that the total iteration count is a remarkably simple equation:
205	196
206	197		floor(log2(n))
207	198
208	199		This is relatively fast to calculate, as it's equivalent to the position of the most significant 1-bit in the binary value of n.
209	200
210	201		#### Loop Code
211	202
212	203		Start with %lo = -1, %hi = number of case labels, %key = value to be searched (assumed to be a signed integer), %table being the address of the map that contains the pointers (which may have to be set beforehand due to the requirement of relocatable code on x86-64), and %mid and %temp undefined. The reason for "lea 2(%lo), %temp" is explained later.
213	204
214	205		``` asm
215	206		@LoopBegin:
216	207		lea 1(%lo,%hi,1), %mid
217	208		shr %mid
218	209		cmp (%table,%mid,8), %key
219	210		cmovge %mid, %lo
220	211		cmovle %mid, %hi
221	212		lea 2(%lo), %temp
222	213		cmp %temp, %hi
223	214		jg @LoopBegin
224	215		```
225	216
226	217		With loop unrolling, this can be simplified further:
227	218
228	219		``` asm
229	220		lea 1(%lo,%hi,1), %mid
230	221		shr %mid
231	222		cmp (%table,%mid,8), %key
232	223		je @CaseMatch
233	224		cmovge %mid, %lo
234	225		cmovle %mid, %hi
235	226		```
236	227
237	228		... with “@CaseMatch” appearing later. This block of code is repeated for each iteration. If there is concern that the conditional jump may incur a performance penalty, it can be removed without incident, especially during the last couple of iterations (an exact match will set %lo and %hi to the same value).
238	229
239	230		For 64-bit systems, the comparison is more complicated because each entry in the table is 16 bytes, and there is no facility to multiply by 16 in reference operands. Nevertheless, with some rearrangement of the commands to take advantage of a CPU core's multiple ports and the availability of additional registers, this can be resolved relatively painlessly:
240	231
241	232		``` asm
242	233		lea 1(%lo,%hi,1), %index
243	234		lea 1(%lo,%hi,1), %mid
244	235		and $-2, %index ; Clear lsb
245	236		shr %mid
246	237		cmp (%table,%index,8), %key
247	238		je @CaseMatch
248	239		cmovge %mid, %lo
249	240		cmovle %mid, %hi
250	241		```
251	242
252	243		During the search, the value of %lo is one below the lowest valid index, while %hi is one above the highest valid index. If at any point that %lo + 1 ≥ %hi, the entire list has been searched. Due to how %mid is calculated, if execution passes through the unrolled loop without jumping out, %lo and %hi will have a difference of 2 and sit either side of the index of the last remaining entry in the list that hasn't been checked, hence one final lookup in the table against %key will confirm a match, with a jump to the case's "else" block (or the end of the block if one isn't present) if it's not.
253	244
254	245		For i386:
255	246
256	247		``` asm
257	248		lea 1(%lo,%hi), %mid
258	249		shr %mid
259	250		cmp (%table,%mid,8), %key
260	251		jne @ElseBlock
261	252		@CaseMatch:
262	253		mov 4(%table,%mid,8), %procaddr
263	254		; Do common parameter set-up
264	255		call %procaddr
265	256		; Do common result handling
266	257		jmp @CaseBlockEnd
267	258		@ElseBlock:
268	259		; Else block code
269	260		...
270	261		@CaseBlockEnd:
271	262		...
272	263		```
273	264
274	265		For x86-64 (note the use of %index in the @CaseMatch setion):
275	266
276	267		``` asm
277	268		lea 1(%lo,%hi), %index
278	269		and $-2, %index
279	270		cmp (%table,%index,8), %key
280	271		jne @ElseBlock
281	272		@CaseMatch:
282	273		mov 8(%table,%index,8), %procaddr
283	274		; Do common parameter set-up
284	275		call %procaddr
285	276		; Do common result handling
286	277		jmp @CaseBlockEnd
287	278		@ElseBlock:
288	279		; Else block code
289	280		...
290	281		@CaseBlockEnd:
291	282		...
292	283		```
293	284
294	285		#### Buffer Overrun Trap
295	286
296	287		One drawback to this highly optimised binary search is that it doesn't trap the situation where the input key is greater than the largest key in the table, and if this happens, the loop may exit with %lo + 1 = %hi = list length, then "lea 1(%lo, %hi), %mid" sets %mid to a value which is out of bounds. To get around this, we recall that in normal operation, %lo and %hi have a difference of 2 if the flow reaches the end of the loop, and are equal if a match was found early, therefore being both odd or both even, their sum is a multiple 2, and so the "+1" part of the LEA instruction has no effect after dividing the sum by 2, so the simple fix is to replace the LEA instruction with "lea (%lo, %hi), %mid", which stops %mid from ever exceeding the upper bound without affecting normal behaviour. In other words, for i386:
297	288
298	289		``` asm
299	290		lea (%lo,%hi), %mid
300	291		shr %mid
301	292		cmp (%table,%mid,8), %key
302	293		jne @ElseBlock
303	294		@CaseMatch:
304	295		mov 4(%table,%mid,8), %procaddr
305	296		; Do common parameter set-up
306	297		call %procaddr
307	298		; Do common result handling
308	299		jmp @CaseBlockEnd
309	300		@ElseBlock:
310	301		; Else block code
311	302		...
312	303		@CaseBlockEnd:
313	304		...
314	305		```
315	306
316	307		For x86-64:
317	308
318	309		``` asm
319	310		lea (%lo,%hi), %index
320	311		and $-2, %index
321	312		cmp (%table,%index,8), %key
322	313		jne @ElseBlock
323	314		@CaseMatch:
324	315		mov 8(%table,%index,8), %procaddr
325	316		; Do common parameter set-up
326	317		call %procaddr
327	318		; Do common result handling
328	319		jmp @CaseBlockEnd
329	320		@ElseBlock:
330	321		; Else block code
331	322		...
332	323		@CaseBlockEnd:
333	324		...
334	325		```
335	326
336	327		#### Putting it all together
337	328
338	329		Now that the registers and exceptional cases are explained, we can put the entire thing together.
339	330
340	331		For i386:
341	332
342	333		``` asm
343	334		@LoopBegin:
344	335		lea 1(%lo,%hi,1), %mid
345	336		shr %mid
346	337		cmp (%table,%mid,8), %key
347	338		cmovge %mid, %lo
348	339		cmovle %mid, %hi
349	340		lea 2(%lo), %temp
350	341		cmp %temp, %hi
351	342		jg @LoopBegin
352	343		; Unroll the above if desired
353	344
354	345		lea (%lo,%hi), %mid
355	346		shr %mid
356	347		cmp (%table,%mid,8), %key
357	348		jne @ElseBlock
358	349		@CaseMatch:
359	350		mov 4(%table,%mid,8), %procaddr
360	351		; Do common parameter set-up
361	352		call %procaddr
362	353		; Do common result handling
363	354		jmp @CaseBlockEnd
364	355		@ElseBlock:
365	356		; Else block code
366	357		...
367	358		@CaseBlockEnd:
368	359		...
369	360		```
370	361
371	362		For x86-64:
372	363
373	364		``` asm
374	365		@LoopBegin:
375	366		lea 1(%lo,%hi,1), %index
376	367		lea 1(%lo,%hi,1), %mid
377	368		and $-2, %index ; Clear lsb
378	369		shr %mid
379	370		cmp (%table,%index,8), %key
380	371		cmovge %mid, %lo
381	372		cmovle %mid, %hi
382	373		lea 2(%lo), %temp
383	374		cmp %temp, %hi
384	375		jg @LoopBegin
385	376		; Unroll the above if desired
386	377
387	378		lea (%lo,%hi), %index
388	379		and $-2, %index
389	380		cmp (%table,%index,8), %key
390	381		jne @ElseBlock
391	382		@CaseMatch:
392	383		mov 8(%table,%index,8), %procaddr
393	384		; Do common parameter set-up
394	385		call %procaddr
395	386		; Do common result handling
396	387		jmp @CaseBlockEnd
397	388		@ElseBlock:
398	389		; Else block code
399	390		...
400	391		@CaseBlockEnd:
401	392		...
402	393		```
403	394
404	395		---
405	396		From the Free Pascal wiki, page "Case Compiler Optimization", as it stood on 2019-04-25 after a change by CuriousKit, 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).
406	397		Category: Compiler design
407	398		Category: Proposals

Back to history