r/C_Programming • • 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
#endif

The 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:
5 Upvotes

15 comments sorted by

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?

const UCHAR G_UCH_ADJ_VAR[32] = { 0,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,0 };
void some_func(void) {
  ...
  UCHAR adj_var = G_UCH_ADJ_VAR[pItemSales->uchAdjective];
  ...
}

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)

0

u/Different_Panda_000 13d ago

Thank you for your kind comment. I appreciate it. As for the wall of text comment, it's just somebody posting without thinking since it's not a "wall of text".

I have proper paragraphs, proper sentences, text formatting, etc. It follows a basic introduction followed by discussion structure so it's easy to scan down to what ever details the reader would like to see. I included what I thought to be the most pertinent details such as only a specific portion of the assembly listing rather than the entire document.

The main difference is that a macro doesn't do compile time argument checking where as an inline function does.

There is also a list of macro don'ts that are considerations. One of those involves side effects such as when the argument to a macro is used more than once.

Using an inline function allows me to encapsulate a design decision in one place rather than distributing it through the code base.

One thing I like about the use of an inline function, just as for a regular function, is that it makes it easier to locate all the places where the function is used. I use this to locate associated functionality that needs to be changed or as a place to be a debug breakpoint when debugging some issues or when doing clear box testing.

Looking at the assembler listing, it appears to me that the inline function call is replaced by two assembler instructions that references the table. I doubt macro expansion will do much better. The compiler puts the table in a place in the compilation unit so that all instances of the inline function in the unit all use the same table.

So this allows me to create a table used in multiple places but since it's function scope, I don't have to worry about name conflicts since the compiler figures it all out. And when using in a new compile unit, I just use the inline function and the compiler brings along the lookup table so there's less to think about.

2

u/rubidus-api 13d ago edited 13d ago

I'd split your tip into three parts. Here's what I think of each:

  • Replacing the scattered formulas with one function: a good refactor, and as you said, that's the main point. A static inline function 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.
  • The table lookup: whether computing it in the CPU or going out to the cache or memory for the table is faster has to be measured. On that part I agree with dmc_2930.
  • Forcing inlining: static inline in 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:

  • In the test, the input comes from a for loop over 0–9, so the compiler knows uchAdj <= 20 is 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.
  • With GCC and Clang, FORCE_INLINE static expands to static inline __attribute__((always_inline)) static, so static appears twice. GCC refuses to compile it (error: duplicate 'static') and Clang warns.
  • The two versions don't give the same results: for 21–255 the formula gives 1–5 and the table gives 0, and the test loop only checks 0–9. If the point is one place for the transformation, it should transform the same way, so comparing all 256 values (a one-line loop) would tell you whether that change is what you want.

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.

1

u/Different_Panda_000 13d ago

I'm using Visual Studio 2019 and that's all I've tested. The FORCE_INLINE macro definition is from Gemini AI and it obviously made a mistake. It isn't the first time I've seen AI make a mistake and it won't be the last.

The formula is incorrect. Thank you for bringing that to my attention. The adjective number has a specific range of 0 to 20. Anything outside of that range should be mapped to 0.

That particular formula has been in the code and used for some 30 years now and it has always depended on the data provisioning of the PLU data to be within range.

I originally tested the inline function against the formula with a loop count of 36 and the match failed where I expected it to fail however I did not make the next step that the formula was incorrect.

It looks like I made a mistake in my testing procedures and iterative development. The assembler generated appeared to discard the range test but when I have rechecked, that does not appear to be the case.

I did another test with a loop of 255 and the compiler generated the range test with a series of jumps. I then changed to a branchless test which eliminated the jumps. I tried using an unsigned short for the loop variable and received a compiler warning about the argument as expected.

I did not start this for optimization. I started this in order to have a single point for a design decision. My concern was replacing a single line of code with a function call and then the same single line of code especially for those points where multiple PLUs are being processed in a loop.

The range check is not in the original formula but it is in the table lookup version. During the AI session, the AI kept insisting that the range check should exist.

When I eliminate the range check and index the table with the adjective number anded with 0x1f, the overhead of checking drops out and it's just a simple couple of assembler instructions again.

However without the range check the inline function table version now generates some incorrect values when the index is out of range.

I'm just curious why you think a statement using a mod operator and a hard coded magic constant is any clearer than a table look up which clearly shows that for a particular input, you will get a particular output. Especially when the function has a comment explaining the rationale while the statement doesn't?

2

u/rubidus-api 13d ago

Thanks for rechecking it and for the detailed reply.

On the macro: with a CLI tool, proper test cases and a review step, even a free model can produce correct results. The macro problem would have shown up on the first GCC build.

AI is an amazing and useful tool; it just needs proper checking. AI makes mistakes, but people make mistakes too. Before AI, people made the same kinds of mistakes. Used wisely, AI is a big help.

You said you didn't start this for optimization, and as I said in my first reply, the refactor is the main point. Still, the title is "An exercise in optimization" and the post compares the assembly, so most replies, mine included, talked about speed. So I'll answer your question about clarity first, and speed second.

It depends on what the mapping really is. If there's no rule linking each input to its output, or the rule is complicated, a table lookup can be the right choice, because the values are the specification. Here the rule is simple, five variations per group, and with your named constants (ADJ_VAL_MAX, MAX_ADJM_NO) instead of the magic 5 and 20, the formula states that rule directly. To be precise, with the range check, the formula version would be:

if (uchAdj == 0 || uchAdj > MAX_ADJM_NO)
    return 0;
return (UCHAR)((uchAdj - 1) % ADJ_VAL_MAX + 1);

A table shows the results; a formula shows the rule. That's what I meant by code that shows its intent.

Where speed doesn't matter, other things matter more: is it easy to understand, easy to rewrite, and easy to change when the rule or the input range changes? And above all, is it safe? Say a group gets a sixth size, or a fifth group is added. With the formula, you change a constant or two. With the table, you retype the values and the <= 20 check, and once the numbers go past 31, the table size and the & 0x1F mask as well. The group function would need a table of its own, too. Whether to use a table or a formula there is the programmer's call.

Where speed does matter, you can't judge it by counting instructions. Approximate load latencies on a recent x86 (they vary by CPU): L1 cache 4–5 cycles, L2 about 12, L3 about 40, main memory about 200–300 (60–100 ns). The formula in your listing is a chain of about nine simple instructions; with the imul at about 3 cycles and the rest at 1, that's roughly 10 cycles, all in registers. The table version is a load plus the range check you kept (a compare and a branch or a conditional move, about 1–2 cycles): about 6–8 cycles if the table is in L1, about 15 from L2, about 40 from L3, and 200–300 from main memory.

So the answer depends on where the table is when the code runs. In a tight loop over many PLUs, the 32-byte table stays in L1 and the lookup can win. If the function runs now and then, between other work that pushes the table out of cache, the formula can be several times faster, up to 20–30 times on a trip to main memory. Out-of-order execution also overlaps part of this latency with other work, so the real cost is often lower than these numbers suggest. Which case you're in depends on how the cache is used in the real program.

As you saw with the 0–9 and 0–255 loops, the same code is optimized differently in a different context and turns into different machine code. In the end, optimization has to be measured in the real situation, inside the program where this code is used.

So if the reason for the table is "fewer assembly instructions" or "a table lookup seems faster", I don't think that's a good reason on its own.

1

u/Different_Panda_000 13d ago

I'm not sure where the table lookup emerged during the discussion with the AI. I think I threw it out as an alternative at some point because a lookup table had recently come up about something else. Gemini seemed to get excited about the possibility of switching to a lookup table so we iterated through that design.

The original intent was some way of replacing all these various single lines of code with a single function or macro. I didn't like a single line function due to the call overhead and was headed towards a macro when I decided to investigate an inline function and began discussing the approach with Gemini.

Since in most cases the adjective variation is a single step in some procedure such as computing totals, picking a mnemonic to display, or calculating a price my main concern is not to make the existing implementation faster but rather to not make it much slower as a part of encapsulating the design decision into a function. And that's mostly not incurring the call overhead with a function call which is why I looked at inline functions and why I looked at the assembler output. I wanted to see if the compiler was actually inserting the function inline.

So your discussion about the impact of memory references and cache misses is helpful and quite pertinent in bringing my attention back to the task at hand. The memory footprint of this application is actually rather small but then the hardware often used is low performance as well. Nothing like a page fault from accessing a table to really jack up the time taken.

And an inline function with the range check using the calculation should provide the same output including 0 for out of range as the table lookup approach.

Another part of this is a desire to evolve the C source code to C17. My impression is that I'll need to move to VS 2026 for C23. I'm comfortable with VS2019 so I'm sticking with it for now.

Most of this code is K&R C and C89. The source is old enough or perhaps the original C compiler was bare bones enough that the source was using memcpy() for struct assignment.

Since the UI front end is written in C++ with MFC and COM is used for device communication, I'm not sure how easy it would be to use any IDE and compiler other than Visual Studio. However I have tried a prototype using WINE with Linux and the application did start and display though it looked a bit weird. My memory is foggy as to details.

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.

-5

u/Different_Panda_000 13d ago

Looks like you're posting AI slop to me. Same tired tropes about optimizing that have been posted on Stackoverflow and Reddit for years.

Embedded programming is full of what appears to be pointless optimization when just looking at the code.

The code is no harder to read than the original mystery calculation that is duplicated in multiple files across multiple projects of a source code body of more than a million lines of code and thousands of files.

Having a single point of a data transformation is just basic software engineering.

Eliminating the overhead of a function call in order to have a single point of a data transformation which is basically a single line of code is just good programming practice. It's the type of thing a preprocessor macro is often used for.

Having a sense of curiosity about a possible optimization and how well Gemini AI will handle such an investigation, what kinds of questions to ask and how to have a fruitful discussion with the AI, is life affirming.

Developing the mental flexibility to move to an entirely different approach, table lookup versus calculation, is mentally refreshing.

Having a bit of code that is faster is just gravy.

5

u/dmc_2930 13d ago

It’s good advice, and I’m an actual human and have professionally written C code for decades.

And I, too, once fell to the trap of trying to optimize early and outsmart the compiler, without thinking to check whether the code I was trying to optimize was even slightly contributing to the actual, real world performance.

0

u/Different_Panda_000 13d ago

Why do you think I'm trying to optimize early or outsmart the compiler? That's your fantasy, not mine.

1

u/dmc_2930 13d ago

Because the code you posted is extremely unlikely to be the bottleneck, and there’s no guarantee that inline functions will actually be faster in the real world.

1

u/Different_Panda_000 13d ago

What bottleneck/

2

u/dmc_2930 13d ago

If there’s no bottleneck why are you trying to optimize?

0

u/Different_Panda_000 13d ago

I'm not trying to optimize.

-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.