UMA's Small Collection

Optimizing C and C++ Code

2010-08-31T18:18:00.006+05:30

Embedded software often runs on processors with limited computation power, thus optimizing the code becomes a necessity. In this article we will explore the following optimization techniques for C and C++ code developed for Real-time and Embedded Systems.

Adjust structure sizes to power of two

When arrays of structures are involved, the compiler performs a multiply by the structure size to perform the array indexing. If the structure size is a power of 2, an expensive multiply operation will be replaced by an inexpensive shift operation. Thus keeping structure sizes aligned to a power of 2 will improve performance in array indexing.

Place case labels in narrow range

If the case labels are in a narrow range, the compiler does not generate a if-else-if cascade for the switch statement. Instead, it generates a jump table of case labels along with manipulating the value of the switch to index the table. This code generated is faster than if-else-if cascade code that is generated in cases where the case labels are far apart. Also, performance of a jump table based switch statement is independent of the number of case entries in switch statement.

Place frequent case labels first

If the case labels are placed far apart, the compiler will generate if-else-if cascaded code with comparing for each case label and jumping to the action for leg on hitting a label match. By placing the frequent case labels first, you can reduce the number of comparisons that will be performed for frequently occurring scenarios. Typically this means that cases corresponding to the success of an operation should be placed before cases of failure handling.

Break big switch statements into nested switches

The previous technique does not work for some compilers as they do not generate the cascade of if-else-if in the order specified in the switch statement. In such cases nested switch statements can be used to get the same effect.

To reduce the number of comparisons being performed, judiciously break big switch statements into nested switches. Put frequently occurring case labels into one switch and keep the rest of case labels into another switch which is the default leg of the first switch.For example:

switch (val) {

case "Freq_1":

Handle_Freq_1();

case "Freq_2":

Handle_Freq_2();

...

case "Freq_n":

Handle_Freq_n();

default:

switch (val) {

"NonFreq_1":

Handle_NonFreq_1();

...

case "NonFreq_m":

Handle_NonFreq_m();

}

Minimize local variables

If the number of local variables in a function is less, the compiler will be able to fit them into registers. Hence, it will be avoiding frame pointer operations on local variables that are kept on stack. This can result in considerable improvement due to two reasons:

All local variables are in registers so this improves performance over accessing them from memory.

If no local variables need to be saved on the stack, the compiler will not incur the overhead of setting up and restoring the frame pointer.

Declare local variables in the inner most scope

Do not declare all the local variables in the outermost function scope. You will get better performance if local variables are declared in the inner most scope. Consider the example below; here object a is needed only in the error case, so it should be invoked only inside the error check. If this parameter was declared in the outermost scope, all function calls would have incurred the overhead of object a's creation (i.e. invoking the default constructor for a). For example:

void function() {

...

if (condition == true) {

int myVar;

...

}

Reduce the number of parameters

unction calls with large number of parameters may be expensive due to large number of parameter pushes on stack on each call. For the same reason, avoid passing complete structures as parameters. Use pointers and references in such cases.

Use references for parameter passing and return value for types bigger than 4 bytes

Passing parameters by value results in the complete parameter being copied on to the stack. This is fine for regular types like integer, pointer etc. These types are generally restricted to four bytes. When passing bigger types, the cost of copying the object on the stack can be prohibitive. In case of classes there will be an additional overhead of invoking the constructor for the temporary copy that is created on the stack. When the function exits the destructor will also be invoked.

Thus it is efficient to pass references as parameters. This way you save on the overhead of a temporary object creation, copying and destruction. This optimization can be performed easily without a major impact to the code by replacing pass by value parameters by const references. (It is important to pass const references so that a bug in the called function does not change the actual value of the parameter.
Passing bigger objects as return values also has the same performance issues. A temporary return object is created in this case too.

Don't define a return value if not used

The called function does not "know" if the return value is being used. So, it will always pass the return value. This return value passing may be avoided by not defining a return value which is not being used.

Consider locality of reference for code and data

The processor keeps data or code that is referenced in cache so that on its next reference if gets it from cache. These cache references are faster. Hence it is recommended that code and data that are being used together should actually be placed together physically. This is actually enforced into the language in C++. In C++, all the object's data is in one place and so is code. When coding is C, the declaration order of related code and functions can be arranged so that closely coupled code and data are declared together.

Prefer int over char and short

With C and C++ prefer use of int over char and short. The main reason behind this is that C and C++ perform arithmetic operations and parameter passing at integer level, If you have an integer value that can fit in a byte, you should still consider using an int to hold the number. If you use a char, the compiler will first convert the values into integer, perform the operations and then convert back the result to char.

Define lightweight constructors

As far as possible, keep the constructor light weight. The constructor will be invoked for every object creation. Keep in mind that many times the compiler might be creating temporary object over and above the explicit object creations in your program. Thus optimizing the constructor might give you a big boost in performance. If you have an array of objects, the default constructor for the object should be optimized first as the constructor gets invoked for every object in the array.

Prefer initialization over assignment

Consider the following example of a complex number:

void foo() { Complex c; c = (Complex)5; } void foo_optimized() { Complex c = 5; }
In the function foo, the complex number c is being initialized first by the instantiation and then by the assignment. In foo_optimized, c is being initialized directly to the final value, thus saving a call to the default constructor of Complex.
Use constructor initialization lists

Use constructor initialization lists to initialize the embedded variables to the final initialization values. Assignments within the constructor body will result in lower performance as the default constructor for the embedded objects would have been invoked anyway. Using constructor initialization lists will directly result in invoking the right constructor, thus saving the overhead of default constructor invocation.
In the example given below, the optimized version of the Employee constructor saves the default constructor calls for m_name and m_designation strings.
Employee::Employee(String name, String designation) { m_name = name; m_designation = designation; } /* === Optimized Version === */ Employee::Employee(String name, String designation): m_name(name), m_destignation (designation) { } Do not declare "just in case" virtual functionsVirtual function calls are more expensive than regular function calls so do not make functions virtual "just in case" somebody needs to override the default behavior. If the need arises, the developer can just as well edit the additional base class header file to change the declaration to virtual. In-line 1 to 3 line functions Converting small functions (1 to 3 lines) into in-line will give you big improvements in throughput. In-lining will remove the overhead of a function call and associated parameter passing. But using this technique for bigger functions can have negative impact on performance due to the associated code bloat. Also keep in mind that making a method inline should not increase the dependencies by requiring a explicit header file inclusion when you could have managed by just using a forward reference in the non-inline version. Source: Optimizing C and C++ Code

Optimizing C and C++ Code

2010-08-31T18:18:00.003+05:30

Adjust structure sizes to power of two

Place case labels in narrow range

Place frequent case labels first

Break big switch statements into nested switches

switch (val) {

case "Freq_1":

Handle_Freq_1();

case "Freq_2":

Handle_Freq_2();

...

case "Freq_n":

Handle_Freq_n();

default:

switch (val) {

"NonFreq_1":

Handle_NonFreq_1();

...

case "NonFreq_m":

Handle_NonFreq_m();

}

Minimize local variables

All local variables are in registers so this improves performance over accessing them from memory.

If no local variables need to be saved on the stack, the compiler will not incur the overhead of setting up and restoring the frame pointer.

Declare local variables in the inner most scope

void function() {

...

if (condition == true) {

int myVar;

...

}

Reduce the number of parameters

Use references for parameter passing and return value for types bigger than 4 bytes

Categories of free and non-free software

2010-06-29T14:56:00.003+05:30

Links:

http://www.gnu.org/philosophy/categories.html

http://www.gnu.org/philosophy/words-to-avoid.html

http://www.gnu.org/philosophy/open-source-misses-the-point.html

http://www.gnu.org/copyleft/copyleft.html

http://www.gnu.org/copyleft/gpl.html

Process and Thread In Linux

2010-06-10T13:30:00.003+05:30

Process:

A process is a unit of execution that can be scheduled. Examples include the shell in Linux, and the invocation of a command from the shell. In Linux, one can find process manipulation functions in the header file unistd.h. A process is identified by pid_t, defined in sys/types.h, where pid refers to the Process ID. Linux has a special process called init from which all other processes are spawned. The init process has an ID of 1. The ID of the process your program

is running in can be obtained with the function getpid(). Every process, except init, has a parent process. The parent’s ID can also be obtained with the function getppid(). To view all processes running on a system, the user can use the shell command ps with the option -e. Each process’s ID, parent’s ID, and command that started it is displayed. To end a process, the kill command can be executed with the process’s ID as an argument. When killing a process, the kernel sends a SIGTERM signal to it. A handler could be implemented in the program to intercept the signal so that, for example, files or connections could be released before stopping the process gracefully.

When a program is running, it can be terminated with the exit function. There are several ways to create a process. The first is with the system function, which will run the command given as an argument in a shell. The second is to fork the process; a new child process will begin running the exact same program as its parent, beginning at the statement after the fork command. All memory is copied from one process to the other, and no memory is shared between them. Conflicts could arise from the use of resources such as files. Finally, the exec function can switch the program being run altogether. Using exec does not result in concurrency like fork can; it only changes the program. It is as though the code has been swapped out for new code. Note that while it used to be fashionable to create multiple processes for each program, there is a big performance hit for creating and communicating between them, so it is much less prudent to do this today. An exception is agent-style programming where multiple processes are still used.

It is sometimes desirable to give a particular process more execution time than the others. This can be done with the nice command, where a lower number means higher priority.

Thread:

Threads are often a preferable alternative to processes, especially for simple tasks. While a process is handled by the kernel, threads are contained and managed by processes. This results in higher performance and the ability to share memory. In fact, thread creation is 10 to 100 times faster than process creation. Despite these pros for using threads, there are dangers involved as well. Because memory is shared between threads, data must be thread-safe; that is, mechanisms must be put into place to ensure that the integrity of data is maintained even if multiple threads are trying to access it at the same time. Furthermore, race conditions can occur where the order and timing of events between multiple threads unexpectedly determine the outcome of a procedure. For example, suppose that a user starts a chat on one server, thereby getting channel-operator privileges. At the same time, a second user with the same name tries to start another chat on the same network, but on a different server. Neither server has received notice of the other server’s channel allocation, so the users will be able to access each others’ chats with higher privileges because they have the same name. To create a thread in Linux, the pthread_create function is used:

int pthread_create(

pthread_t * thread,

pthread_attr_t * attr,

void * (*start_routine)(void *),

void * arg;

The new thread will execute concurrently with the calling thread. The function start_routine will be called with the argument arg when the new thread starts, and attr indicates the attributes to be applied to the new thread. When start_routine ends, the thread will be terminated implicitly. Alternatively, the thread can be explicitly terminated with pthread_exit. If the thread was joined to another, the joined thread will begin execution when this thread has terminated via

either method. A thread may be run in detached mode with the function pthread_detach, guaranteeing that memory resources consumed in the function’s argument thread will be freed immediately when the thread terminates. This causes the thread to be nonjoinable, so other threads cannot synchronise on the termination of this thread. To help make programs run thread-safe, a pthread_mutex may be used. Such a mutual exclusion mechanism will help ensure that concurrent access to certain data is thread-safe. The function pthread_mutex_lock may be called in an attempt to get exclusive access to the data it protects for a particular thread. If another thread already has the lock, the calling thread will be suspended until the lock is released. To unlock access, pthread_mutex_unlock is used. Note that the pthread facilities are available as C code. It may be desirable to make use of them in C++. One way to do this is to use a C++ class that contains a reference to a thread via the pthread_t type. When the thread is created in the class’s initialization code, a static (non-class) function can be called via start_routine. Then, this main entry point for the thread can call back to a class function via its argument.

Predefined Macros

2010-05-31T11:48:00.002+05:30

Every compiler that conforms to the ISO C standard must define the following seven macros. Each of these macro names begins and ends with two underscore characters:

_ _DATE_ _

The replacement text is a string literal containing the compilation date in the format "Mmm dd yyyy" (example: "Mar 19 2006"). If the day of the month is less than 10, the tens place contains an additional space character.

_ _FILE_ _

A string literal containing the name of the current source file.

_ _LINE_ _

An integer constant whose value is the number of the line in the current source file that contains the _ _LINE_ _ macro reference, counting from the beginning of the file.

_ _TIME_ _

A string literal that contains the time of compilation, in the format "hh:mm:ss" (example: "08:00:59").

_ _STDC_ _

The integer constant 1, indicating that the compiler conforms to the ISO C standard.

_ _STDC_HOSTED_ _

The integer constant 1 if the current implementation is a hosted implementation; otherwise the constant 0.

_ _STDC_VERSION_ _

The long integer constant 199901L if the compiler supports the C99 standard of January 1999.

The values of the _ _FILE_ _ and _ _LINE_ _ macros can be influenced by the #line directive. The values of all the other predefined macros remains constant throughout the compilation process.

The value of the constant _ _STDC_VERSION_ _ will be adjusted with each future revision of the international C standard.

Under the C99 standard, C programs are executed either in a hosted or in a freestanding environment. Most C programs are executed in a hosted environment, which means that the C program runs under the control and with the support of an operating system. In this case, the constant _ _STDC_HOSTED_ _ has the value 1, and the full standard library is available.

A program in a freestanding environment runs without the support of an operating system, and therefore only minimal standard library resources are available to it.

Unlike the macros listed previously, the following standard macros are optional. If any of these macros is defined, it indicates that the implementation supports a certain IEC or ISO standard:

_ _STDC_IEC_559_ _

This constant is defined with the value 1 if the implementation's real floating-point arithmetic conforms to the IEC 60559 standard.

_ _STDC_IEC_559_COMPLEX_ _

This constant is defined with the value 1 if the implementation's complex floating-point arithmetic also conforms to the IEC 60559 standard.

_ _STDC_ISO_10646_ _

This long integer constant represents a date in the form yyyymmL (example: 199712L). This constant is defined if the encoding of wide characters with type wchar_t conforms to the ISO/IEC 10646 standard, including all supplements and corrections up to the year and month indicated by the macro's value.

You must not use any of the predefined macro names described in this section in a #define or #undef directive. Finally, the macro name _ _cplusplus is reserved for C++ compilers, and must not be defined when you compile a C source file.

Source: C in a Nutshell - O'Reilly Media

The _Pragma Operator

2010-05-31T11:42:00.002+05:30

You cannot construct a #pragma directive (or any other preprocessor directive) by means of a macro expansion. For cases where you would want to do that, C99 has also introduced the preprocessor operator _Pragma, which you can use with macros. Its syntax is as follows:

_Pragma ( string_literal )

Here is how the _Pragma operator works. First, the string_literal operand is "de-stringized," or converted into a sequence of preprocessor tokens, in this way: the quotation marks enclosing the string are removed; each sequence of a backslash followed by a double quotation mark (\") is replaced by a quotation mark alone ("); and each sequence of two backslash characters (\\) is replaced with a single backslash (\). Then the preprocessor interprets the resulting sequence of tokens as if it were the text of a #pragma directive.

The following line defines a helper macro, STR, which you can use to rewrite any #pragma directive using the _Pragma operator:

#define STR(s) #s // This # is the "stringify" operator.

With this definition, the following two lines are equivalent:

#pragma tokens

_Pragma ( STR(tokens) )

The following example uses the _Pragma operator in a macro:

#define ALIGNMENT(n) _Pragma( STR(pack(n)) )

ALIGNMENT(2)

Macro replacement changes the ALIGNMENT(2) macro call to the following:

_Pragma( "pack(2)" )

The preprocessor then processes the line as it would the following directive:

#pragma pack(2)

Source: C in a Nutshell - O'Reilly Media

The #pragma Directive

2010-05-31T11:33:00.002+05:30

The #pragma directive is a standard way to provide additional information to the compiler. This directive has the following form:

#pragma [tokens]

If the first token after #pragma is STDC, then the directive is a standard pragma. If not, then the effect of the #pragma directive is implementation-dependent. For the sake of portability, you should use #pragma directives sparingly.

If the preprocessor recognizes the specified tokens, it performs whatever action they stand for, or passes information on to the compiler. If the preprocessor doesn't recognize the tokens, it must ignore the #pragma directive.

Recent versions of the GNU C compiler and Microsoft's Visual C compiler both recognize the pragma pack(n), for example, which instructs the compiler to align structure members on certain byte boundaries. The following example uses pack(1) to specify that each structure member be aligned on a byte boundary:

#if defined( _ _GNUC_ _ ) || defined( _MSC_VER )

#pragma pack(1) // Byte-aligned: no padding.

#endif

Single-byte alignment ensures that there are no gaps between the members of a structure. The argument n in a pack pragma is usually a small power of two. For example, pack(2) aligns structure members on even-numbered byte addresses, and pack(4) on four-byte boundaries. pack( ) with no arguments resets the alignment to the implementation's default value.

C99 introduced the following three standard pragmas:

#pragma STDC FP_CONTRACT on_off_switch

#pragma STDC FENV_ACCESS on_off_switch

#pragma STDC CX_LIMITED_RANGE on_off_switch

The value of the on_off_switch must be ON, OFF, or DEFAULT.

Source: C in a Nutshell - O'Reilly Media

Generating Error Messages

2010-05-31T11:13:00.004+05:30

The #error directive makes the preprocessor issue an error message, regardless of any actual formal error. Its syntax is:

#error [text]

If the optional text is present, it is included in the preprocessor's error message. The compiler then stops processing the source file and exits as it would on encountering a fatal error. The text can be any sequence of preprocessor tokens. Any macros contained in it are not expanded. It is a good idea to use a string literal here to avoid problems with punctuation characters, such as single quotation marks.

The following example tests whether the standard macro _ _STDC_ _ is defined, and generates an error message if it is not:

#ifndef _ _STDC_ _

#error "This compiler does not conform to the ANSI C standard."

#endif

Source: C in a Nutshell - O'Reilly Media

Defining Line Numbers

2010-05-31T11:11:00.003+05:30

The compiler includes line numbers and source filenames in warnings, error messages, and information provided to debugging tools. You can use the #line directive in the source file itself to change the compiler's filename and line numbering information. The #line directive has the following syntax:

#line line_number ["filename"]

The next line after a #line directive has the number specified by line_number. If the directive also includes the optional string literal "filename", then the compiler uses the contents of that string as the name of the current source file.

The line_number must be a decimal constant greater than zero. An example:

#line 1200 "primary.c"

The line containing the #line directive may also contain macros. If so, the preprocessor expands them before executing the #line directive. The #line directive must then be formally correct after macro expansion.

Programs can access the current line number and filename settings as values of the standard predefined macros _ _LINE_ _ and _ _FILE_ _:

printf( "This message was printed by line %d in the file %s.\n", _ _LINE_ _, _ _FILE_ _ );

The #line directive is typically used by programs that generate C source code as their output. By placing the corresponding input file line numbers in #line directives, such programs can make the C compiler's error messages refer to the pertinent lines in the original source.

Source: C in a Nutshell - O'Reilly Media

The token-pasting operator

2010-05-31T10:53:00.003+05:30

The operator `##` is a binary operator, and can appear in the replacement text of any macro. It joins its left and right operands together into a single token, and for this reason is commonly called the token-pasting operator. If the resulting text also contains a macro name, the preprocessor performs macro replacement on it. Whitespace characters that occur before and after the `##` operator are removed along with the operator itself.

Usually, at least one of the operands is a macro parameter. In this case, the argument value is first substituted for the parameter, but the macro expansion itself is postponed until after token-pasting. An example:

    #define TEXT_A "Hello, world!"     #define msg(x) puts( TEXT_ ## x )     msg(A);

Regardless of whether the identifier A has been defined as a macro name, the preprocessor first substitutes the argument A for the parameter x, and then performs the token-pasting operation. The result of these two steps is the following line:

    puts( TEXT_A );

Now, because TEXT_A is a macro name, the subsequent macro replacement yields this statement:

    puts( "Hello, world!" );

If a macro parameter is an operand of the ## operator and a given macro invocation contains no argument for that parameter, then the preprocessor uses a placeholder to represent the empty string substituted for the parameter. The result of token pasting between such a placeholder and any token is that token. Token-pasting between two placeholders results in one placeholder. When all the token-pasting operations have been carried out, the preprocessor removes any remaining placeholders. Here is an example of a macro call with an empty argument:

    msg( );

This call expands to the following line:

    puts( TEXT_ );

If TEXT_ is not an identifier representing a string, the compiler will issue an error message.

The order of evaluation of the stringify and token-pasting operators # and ## is not specified. If the order matters, you can influence it by breaking a macro up into several macros.

Source: C in a Nutshell - O'Reilly Media

The stringify operator

2010-05-31T10:49:00.002+05:30

The unary operator `#` is commonly called the stringify operator (or sometimes the stringizing operator) because it converts a macro argument into a string. The operand of `#` must be a parameter in a macro replacement text. When a parameter name appears in the replacement text with a prefixed `#` character, the preprocessor places the corresponding argument in double quotation marks, forming a string literal. All characters in the argument value itself remain unchanged, with the following exceptions:

Any sequence of whitespace characters between tokens in the argument value is replaced with a single space character.
A backslash character (\) is prefixed to each double quotation mark character (") in the argument.
A backslash character is also prefixed to each existing backslash that occurs in a character constant or string literal in the argument, unless the existing backslash character introduces a universal character name.

The following example illustrates how you might use the # operator to make a single macro argument work both as a string and as an arithmetic expression in the replacement text:

    #define printDBL( exp ) printf( #exp " = %f ", exp )     printDBL( 4 * atan(1.0));       // atan( ) is declared in math.h.

The macro call in the last line expands to this statement:

    printf( "4 * atan(1.0)" " = %f ", 4 * atan(1.0));

Because the compiler merges adjacent string literals, this code is equivalent to the following:

    printf( "4 * atan(1.0) = %f ", 4 * atan(1.0));

That statement would generate the following console output:

    4 * atan(1.0) = 3.141593

Source: C in a Nutshell - O'Reilly Media

How the Preprocessor Finds Header Files

2010-05-31T10:27:00.004+05:30

It is up to the given C implementation to define where the preprocessor searches for files specified in `#include` directives. Whether filenames are case-sensitive is also implementation-dependent. For files specified between angle brackets, the preprocessor usually searches in certain system directories, such as /usr/local/include and /usr/include on Unix systems, for example.

For files specified in quotation marks ("filename"), the preprocessor usually looks in the current directory first, which is typically the directory containing the program's other source files. If such a file is not found in the current directory, the preprocessor searches the system include directories as well. A filename may contain a directory path. If so, the preprocessor looks for the file only in the specified directory.

You can always specify your own search path for #include directives, either by using an appropriate command-line option in running the compiler, or by adding search paths to the contents of an environment variable, often named INCLUDE. Consult your compiler's documentation.

Source: C in a Nutshell - O'Reilly Media

Null Pointers

2010-05-24T14:46:00.003+05:30

A null pointer constant is an integer constant expression with the value 0, or such an expression cast as the type `void `. The macro `NULL` is defined in stdlib.h, stdio.h* and other header files as a null pointer constant.

#include /* ... */

FILE *fp = fopen( "demo.txt", "r" );

if ( fp == NULL )

{   // Error: unable to open the file demo.txt for reading.

Null pointers are implicitly converted to other pointer types as necessary for assignment operations, or for comparisons using == or !=. Hence no cast operator is necessary in the previous example. A null pointer is what results when you convert a null pointer constant to a pointer type.

Source: C in a Nutshell - O'Reilly Media