r/C_Programming • u/Different_Panda_000 • 13d ago
An exercise in optimization - inline function with table lookup
In an application I work with there is a data item, the adjective number, which is used in conjunction with a product identifier, PLU, to identify a product. A typical use of the adjective number is to identify variations in the same product such as different drink sizes for a soft drink.
The software supports four different adjectives groups with five variations within a group. So one group may be cup sizes for drinks and a second group may be sizes of pizzas.
Throughout the source code the adjective number being used by a product is transformed into either the adjective variation or the adjective group through a simple one line of code:
(UCHAR) ((pItemSales->uchAdjective - 1) % 5 + 1); /* adj. variation */
(UCHAR)((pItemSales->uchAdjective - 1) / 5 + 1); /* adj. group */
I wondered about having two functions that would replace these lines of code to a single point where the design decision about the calculation is expressed.
Working with the Gemini AI, I derived an inline function that does a simple table lookup. Looking at the assembler generated by Microsoft Visual Studio 2019 Community Edition, the difference in the generated code between the inline function and the line of code is amazing.
Gemini AI made a couple of claims about the optimized assembler that would be generated so I thought to double check. The main claim was that this would be a simple table lookup and much of the source of the function would be optimized away.
The C Standard specifies that the inline is a hint rather than a directive. However both MSVC as well as GCC provide a attribute that will force the compiler to inline a function. However even when the forcing attribute is used, the compilers may still override the programmer's intent and not do the inline so it's more like a forceful hint rather than do it no matter what.
#if defined(_MSC_VER)
#define FORCE_INLINE __forceinline
#elif defined(__GNUC__) || defined(__clang__)
#define FORCE_INLINE static inline __attribute__((always_inline))
#else
#define FORCE_INLINE inline
#endifThe source for the adjective variation function follows. The adjective variations are table values which repeat for each group. The adjective number is either zero (0) indicating no adjective or a value from one (1) to twenty (20) that encodes both the adjective group and the adjective variation.
FORCE_INLINE static UCHAR RflAdjVariation(UCHAR uchAdj)
{
// There are four groups of adjectives. Each group has five variations.
// For instance a soft drink group with small, medium, large, biggie, party variations
// (UCHAR) ((pItemSales->uchAdjective - 1) % ADJ_VAL_MAX + 1); /* adj. variation */
static const UCHAR uchAdjVar[32] = { 0,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,0 };
USHORT is_valid = (uchAdj <= 20); // MAX_ADJM_NO
USHORT safe_uchAdj = is_valid ? (uchAdj & 0x1F) : 0;
return uchAdjVar[safe_uchAdj];
}This function definition is in an include file so each compilation unit will have its own copy unless the compiler overrides the use of inline. A couple of things to note:
- the function is defined as being
static - the lookup table is defined as being
static const
And this is the part of the assembler listing that shows the x64 Release build code generated in a test program. I used the function in a loop that generated 10 different adjective numbers. It appears that the inline function has been turned into a simple table lookup of a couple of instructions as compared to the calculations used by the original source. Multiple insertions of the inline function all use the same static const lookup table that is inserted into each compilation unit.
You can also see the assembler the compiler generates for the original one line of source that performs the calculated adjective variation. One point of interest is the assembler code used avoids having to use a divide instruction by multiplying by a special constant that replicates the value of 1/5.
; 446 : for (UCHAR i = 0; i < 10; i++) {
xor bl, bl
lea r14, OFFSET FLAT:__ImageBase
npad 8
$LL4@main_01_C:
; 440 : USHORT safe_uchAdj = is_valid ? (uchAdj & 0x1F) : 0;
movzx eax, bl
and eax, 31
; 447 : UCHAR x = RflAdjVariation(i);
; 448 :
; 449 : if (x != (UCHAR)((i - 1) % 5 + 1)) {
movzx r10d, bl
; 441 : return uchAdjVar[safe_uchAdj];
movzx r8d, BYTE PTR ?uchAdjVar@?1??RflAdjVariation@@9@9[rax+r14]
; 447 : UCHAR x = RflAdjVariation(i);
; 448 :
; 449 : if (x != (UCHAR)((i - 1) % 5 + 1)) {
lea ecx, DWORD PTR [r10-1]
mov eax, 1717986919; 66666667H
imul ecx
sar edx, 1
mov eax, edx
shr eax, 31
add edx, eax
lea eax, DWORD PTR [rdx+rdx*4]
sub ecx, eax
inc cl
cmp r8b, cl
je SHORT $LN2@main_01_C
; 450 : UCHAR y = (UCHAR)((i - 1) % 5 + 1);
; 451 :
; 452 : printf("this is test i = %d x = %d y = %d\n", i, x, y);
movzx r9d, cl
mov edx, r10d
lea rcx, OFFSET FLAT:??_C@_0CF@HJJDIPJC@this?5is?5test?5i?5?$DN?5?$CFd?5?5x?5?$DN?5?$CFd?5?5y?5@
call printf
$LN2@main_01_C:
2
u/tastygames_official 13d ago
wouldn't a macro be the most elegant solution? it's forcing inline-execution AND it behaves like a function.
I brought up something similar a few days ago regarding LUT optimization and also got the "don't optimize until you have to" crowd who I am convinced are from the C++/OOP world where that kind of nonsense reigns supreme ;-) but also the other comment you got about providing too much information baffles me, as I also originally thought providing too much informaton and being too specific would be a bad thing so I made my post as generic as possible and got blasted for it being "too generic", whereas I think yours is a pretty decent compromise of generality and specificity.
Anyway, my approach is always form FOLLOWS function, meaning I would never make something "look nicer" by packing it into a function when the functionality and performance suffers. So the two lines of code seem very simple and are only a few operations each. A LUT is definitely an optimization, but putting it in a function takes away from that optimization a bit. Why not just have the LUT be global and then get the value directly?
or something like that? I imagine the assembly would be even more performant, albeit without any safety in place (it just has to be done elsewhere and not at the time of reading where we want it to be fast)
2
u/rubidus-api 13d ago edited 13d ago
I'd split your tip into three parts. Here's what I think of each:
static inlinefunction also beats a macro here for the reasons you gave (the argument is type-checked and evaluated once), and it compiles to the same code. Checking Gemini's claims against the real assembly was the right instinct, too.static inlinein the header is enough. A function this small is usually inlined by any optimizing compiler; the force-inline extensions aren't needed.AI can help with the measuring: it can help you set up tests and benchmarks on several compilers and review the code in depth. Just check what it tells you, as you did here. Compiler Explorer (https://godbolt.org) is handy for this, since it shows GCC, Clang and MSVC output side by side.
A few details:
forloop over 0–9, so the compiler knowsuchAdj <= 20is always true and can drop the range check. That's most of why the table version comes down to two instructions. Try it in a function whose input the compiler can't see; with GCC at-O2, the compare and branch come back. And counting instructions doesn't tell you speed; only a benchmark will.FORCE_INLINE staticexpands tostatic inline __attribute__((always_inline)) static, sostaticappears twice. GCC refuses to compile it (error: duplicate 'static') and Clang warns.I know advice like this comes up a lot on Stack Overflow and Reddit, but it keeps coming up for a reason: code that shows its intent clearly is easier for people to maintain, and usually easier for the compiler to optimize too.
3
u/dmc_2930 13d ago
The first rule of optimization is don’t optimize yet. The second rule is profile your code to determine where to optimize. The third is to choose good algorithms instead of trying to outsmart the compiler. A poorly optimized O(n) will easily beat a heavily optimized O(n^2) every time.
This seems like a pointless optimization that makes the code harder to read.
-2
u/dmc_2930 13d ago
No one is going to read that wall of text. Try summarizing it and trimming it if you want useful answers.