Code Level Optimization Techniques

Some of the techniques mentioned below “arithmetic operators”, “jump table to replace if…elseif”, “faster for loops” makes the code hard to debug, un-portable and un-maintainable. If there is no other way to optimize, then only attempt these techniques.

Use pass by reference for user defined type

Passing parameters by value to functions, result in the complete parameter being copied on to the stack. Pass by value shall be replaced by const references to avoid this data copy. Passing bigger objects as return values also has the same performance issues; instead replace it as OUT parameters for that function.

Pre-compute quantities to speed up run-time calculations

Avoid constant computing inside the loops. Though most of the compilers do this optimization, it is still better if it is handled in our code rather than relying on the compiler.

for (int i=0; i <100; i++) {
    offset = offset + strlen(str);
}
Shall be replaced to 

int size = strlen(str);
for (int i=0; i <100; i++) {
    offset = offset + size;
}

Avoid system calls in time critical section of the code 

System calls are costly as it involves switching into kernel mode from user mode. For instances where two process needs to communicate, using shared memory is better than using message queues of pipes as shared memory does not incur any system calls to send and receive data.

Lazy / Minimal Evaluation 

Lazy or delayed evaluation is the technique of delaying a computation until the result of the computation is actually needed for that code path. 

For example, if the expressions are concatenated using logical ‘AND’ or ‘OR’ operator, the expression is evaluated from left to right. We shall gain CPU cycles by placing the expressions in correct position

Consider the code example

if (strcmp(str, “SYSTEM”) && flag == 1)

{

   //…

}

In the above code segment, strcmp() function takes lot of time and for cases where flag != 1, it still does the comparison wasting lot of CPU cycles. The efficient code is

if (flag ==1 && strcmp(str, “SYSTEM”))

{

   //…

}

The same is applicable for OR logical operator when flag == 1. In general, for expressions using operator &&, make the condition that is most likely to be false the leftmost condition. For expressions using operator ||, make the condition that is most likely to be true the leftmost condition

Frequently executed cases should come first in the switch case or if..elseif statement so that the number of comparisons is reduced for the frequently executed case.

The following switch statement is inefficient as integer datatype, which is used most of the time, is placed in the last case and then string data type. Double data type is seldom used in most of the applications, but it is placed in the first case.

switch(dataType) {
  case typeDouble: { doDoubleAction(); break; }
  case typeDate: {doDateAction();; break; }
  case typeShort: {doShortAction();.; break; }
  case typeString: {doStringAction(); break; }
  case typeTimeStamp: {doTimeStampAction(); break; }
  case typeInt: { doIntAction(); break; }
  default: {doDefaultAction(); break; }
}
This shall be made efficient by keeping the frequently used data types first and followed by least and seldom-used data types.

switch(dataType) {
  case typeInt: {…; break; }
  case typeString: {…; break; }
  case typeShort: {…; break; }
  case typeDouble: {…; break; }
  case typeTimeStamp: {…; break; }
  case typeDate: {…; break; }
  default: {…; break; }
}
Much more elegant way is to implement a jump table using function pointers. Consider the following code

typedef void (*functs)();
functs JumpTable[] = { doIntAction, doStringAction(), doShortAction() /* etc*/} ;

Place your function pointers in the same sequence of dataType enum. The above JumpTable assumes that DataType enum is defined as follows

enum DataType{
typeInt =0,
typeString,
typeShort,
/* other types */
};

To call the appropriate implementation just use the following statement

JumpTable[dataType]();

Now the compare operations are replaced with array indexing operation, which are much faster. Moreover the time taken for every data type is nearly the same as compared to if..elseif and switch() constructs.

Minimize local variables

If the number of local variables in a function is less, then the compiler will be able to fit them into registers, thereby avoiding access to the memory (stack). If no local variables need to be saved on the stack, the compiler need not set up and restore the frame pointer.

Reduce number of parameters

Function calls with large number of parameters may be expensive due to large number of parameter pushes on stack on each call. This is applicable even when struct is passed by value. 

Declare local functions as static

If the function is small enough, it may be inlined without having to maintain an external copy if declared as static.

Avoid using global variables in performance critical code

Global variables are never allocated to registers. Global variables can be changed by assigning them indirectly using a pointer, or by a function call. Hence, the compiler cannot cache the value of a global variable in a register, resulting in extra loads and stores when globals are used. 

Pointer chains

Pointer chains are frequently used to access information in structures. For example, a common code sequence is:

 typedef struct { int x, y, color; } Point;

 typedef struct { Point *pos, int something; } Pixel;

 void initPixel(Pixel*p)

 {

 p->pos->x = 0;

 p->pos->y = 0;

 p->pos->color =0;

 }

However, this code must reload p->pos for each assignment. A better version would cache p->pos in a local variable:

 void initPixel(Pixel *p)

 {

 Point *pos = p->pos;

 pos->x = 0;

 pos->y = 0;

 pos->color = 0;

 }

Another way is to include the Point structure in the Pixel structure, thereby avoiding pointers completely. Some compilers do provide this optimization by default.

Replace frequent read/write with mmap

If the application does lot of read/write calls, then you should seriously consider to convert it into mmap() . This does not incur data copy from kernel to user and vice versa and avoids kernel mode switch for executing the read() or write() system call. You can use fsync() call, once to flush all the data to the disk file after you write all your data into the mapped memory area. 

Place elements together, which are accessed together

When you declare a structure make sure that the data elements are declared in such a way that most frequently accessed elements at the beginning

For example if page element is accessed many times and hasSpace little less and freeNode rarely, then declare the structure as follows.

Struct Node{

Int page;

Int hasSpace;

Int freeNode;

///other types

};

This improves the performance because L1 or L2 cache miss, will not get only the required byte, it also gets one full cache line size of data into the appropriate cache. When page is cached, it also caches hasSpace if cache line is 64 bit.  L1 cache line size is usually 64 bits and for L2, it is 128 bits.

Arithmetic operator

Replacing multiplication and division by shift and add operations.

X * 2 shall be replaced to X+X or X<<1

X * N shall be replaced by X<<I where N is 2 ^ I

X / N shall be replaced by X >>I where N is 2 ^ I

Faster for() loops 

for( i=0; i<10; i++){ … } 

If the code inside the loop does not care about the order of the loop counter, we can do this instead:

for( i=10; i–; ) { … }

This runs faster because it is quicker to process i– as the test condition, which says “Is i non-zero? If so, decrement it and continue”. For the original code, the processor has to calculate “Subtract i from 10. Is the result non-zero? If so, increment i and continue.” 

Prefer int over char and short

If you have an integer value that can fit in a byte, you should still consider using an int to hold the number. This is because, when you use a char, the compiler will first convert the values into integer, perform the operations and then convert back the result to char. Doing so, will increase the memory usage but decreases the CPU cycles 

Advise OS on how it should manage memory pages

Using madvise()  system call, we can specify how the swapping and prefetching should be handled by the operating system. If you are accessing data sequentially, OS can prefetch some pages and keep it ready before the program references it. If program accesses data in some memory location frequently, it shall be locked in physical memory avoiding page swap to disk, using mlock() system call.

Advertisements

Thread Design Techniques

A) Pipeline
Task is divided into multiple sub tasks and each thread is responsible for doing one subtask. Job is passed from one thread to other till it reaches the final state.

B) Master/Servant
Master thread does accept the work and delegates work to its servants. Servants are created on the fly by the master when a work arrives to the master. After finishing the job servants go away. For next work, master creates new servants.

C) Thread Pool
Master thread accepts the work and delegate it to predefined set of servants, called thread pool. This is usually accomplished by using a queuing mechanism in between. Master adds request to the queue and all the threads in the pool removes the request from the queue and handles it iteratively.

Network Debugging Utility – netstat

netstat is a useful tool for checking your network configuration and statistics.

When invoked with the –i flag, it displays statistics for the network interfaces currently configured.

Output

Kernel Interface table

Iface       MTU Met    RX-OK RX-ERR RX-DRPRX-OVR   TX-OK TX-ERRTX-DRPTX-OVR Flg

eth0       1500   0   245257      0            0            0               118056      0        0              0     BMRU

lo        16436   0    23632        0            0            0                23632       0       0               0       LRU

The MTU and Met fields show the current MTU and metric values for that interface. The RX and TX columns show how many packets have been received or transmitted error-free (RX-OK/TX-OK) or damaged (RX-ERR/TX-ERR); how many were dropped (RX-DRP/TX-DRP); and how many were lost because of an overrun (RX-OVR/TX-OVR).

When invoked with –a flag, netstat displays all the active internet socket connections

Output

Active Internet connections (servers and established)

Proto Recv-Q Send-Q Local Address               Foreign Address             State

tcp        0      0 prabakaran:irdmi            *:*                         LISTEN

tcp        0      0 *:43812                     *:*                         LISTEN

tcp        0      0 *:mysql                     *:*                         LISTEN

tcp        0      0 *:sunrpc                    *:*                         LISTEN

tcp        0      0 prabakaran:ncube-lm         prabakaran:49594            ESTABLISHED

tcp        0      0 prabakaran:49594            prabakaran:ncube-lm         ESTABLISHED

udp        0      0 prabakaran:filenet-cm       *:*

Active UNIX domain sockets (servers and established)

Proto RefCnt Flags       Type       State         I-Node Path

unix  2      [ ACC ]     STREAM     LISTENING     5624   @/tmp/fam-root-

unix  2      [ ACC ]     STREAM     LISTENING     5039   /var/run/cups/cups.sock

unix  2      [ ACC ]     STREAM     LISTENING     4986   /var/run/avahi-daemon/socket

unix  2      [ ACC ]     STREAM     LISTENING     6130   /tmp/.X11-unix/X0

where

   Proto

       specifies the protocol used by the socket(tcp, upd or raw)

   Recv-Q

       Total bytes not copied by the user program connected to this socket.

   Send-Q

       Total bytes not acknowledged by the remote host.

   Local Address

       Address and port number of the local end of the socket. 

   Foreign Address

       Address and  port  number of the remote end of the socket.

   State

       It represents Socket state and is applicable only for TCP sockets. Possible values are

       ESTABLISHED

              The socket has an established connection.

       SYN_SENT

              The socket is actively attempting to establish a connection.

       SYN_RECV

              A connection request has been received from the network.

       FIN_WAIT1

              The socket is closed, and the connection is shutting down.

       FIN_WAIT2

              Connection is closed, and socket is waiting for a shutdown from the remote end.

       TIME_WAIT

              The socket is waiting after close to handle packets still in the network.

       CLOSED

               The socket is not being used.

       CLOSE_WAIT

              The remote end has shut down, waiting for the socket to close.

       LAST_ACK

              The remote end has shut down, and socket is closed but waiting for acknowledgement.

       LISTEN

              The socket is listening for incoming connections.

       CLOSING

              Both sockets are shut down but we still don’t have all our data sent.

       UNKNOWN

              The state of the socket is unknown.

When invoked with –p option, it displays the process ID and executable file name for all sockets.

Output

Active Internet connections (w/o servers)

Proto Recv-Q Send-Q Local Address      Foreign Address       State                  PID/Program name

tcp        0         0    prabakaran:ncube-lm  prabakaran:49594   ESTABLISHED    1750/tnslsnr

…..

This option will help to know the process which owns the socket when bind() call returns “address already in use” for the port.

When invoked with –s option, it displays statistics of TCP, UDP, IP protocol such as total number of active and passive connections for TCP, failed connection attempts for TCP, established connections for TCP, total TCP segments received and sent, total UDP packets received and sent, packet receive errors for UDP, etc.

Inspecting What is inside executable or library

Sometimes, it is necessary to know what dynamic libraries an executable depends on and what functions are defined in particular library, etc. In this blog, some tools which aid understanding the content of executable / library is discussed.

size

Size is a diagnostic tool for executable file analysis. This utility displays the total size for each object file. The running program of the computer is called a process. Each process of the computer allocates some memory from RAM known as process memory. The process memory of the computer is divided into different blocks segment such as code, data, heap and stack.

Ex.

int x=100; // data

int y; // bss

void main()

{

static int a=10; // data

static int b; // bss

In the above program x and y are external variables where as a and b are static variable. All external and initialize static and external variable are created in Data Segment but uninitialized static and external variables are created in bss (uninitialized data segment) segment. To view the memory allocation by each of these segment we can use the size command.

$ size ./a.out

output:

data bss dec hex filename

252 8 1319 527 a.out

You can type the object files name to be examined. If none are specified, the file "a.out" will be used.

options

-d The total size is always displayed in decimal format.

-o The total size is always displayed in octal format.

$ size -x ./a.out

text data bss dec hex filename

0x3b7 0x100 0x10 1223 4c7 ./a.out

$ size -o ./a.out

text data bss oct hex filename

01667 0400 020 2307 4c7 ./a.out

ldd

ldd is a diagnostic tool for executable file analysis. It shows which shared libraries an executable would use in your environment. A C program is nothing but collection of some functions. Every function is defined in a library file (static/dynamic library). When a program is loaded along with that the respective dynamic libraries are loaded. To enhance yourself with the dynamic libraries used in your program you are equipped with a development tool called ldd. It gives you brief details about which dynamic library is loaded & which dynamic library is missing in your program.

Ex.

main()

{

printf(“Hello”);

bbsr();

Here main.c is the source file. On compiling generates the object file ( main.o). Now the object file is linked with the dynamic libraries (libc.so, sample.so) to build the executable file(singo).

For Example:

$ldd ./singo

Output :

linux-gate.so.1 => (0x00110000)

sample.so=> not found

libc.so.6 => /lib/libc.so.6 (0x00367000)

/lib/ld-linux.so.2 (0x00348000) 

nm

This command list symbol names from object file. These symbol names can be either functions, global variables or static variables. For each symbol the value, symbol type & symbol names are displayed. Lower case symbol types means the symbol is local , upper case means the symbol is global.

Options:

-S print size of undefined symbols

-D Print dynamic, not normal, symbols. Useful only when working with dynamic objects (for example some kinds of shared libraries).

-l For each symbol, use debugging information to try to find a file name and line number. For a defined symbol, look for the line number of the address of the symbol. For an undefined symbol, look for the line number of a relocation entry which refers to the symbol. If line number information can be found, print it after the other symbol information.

Ex.

//prg.c

main()

{

bbsr();

printf(“Hello”);

ctc();

}

int ctc()

{

printf(“I am incuttack”);

}

$ gcc -c prg.c

$nm prg.o

output:

U bbsr

00000030 T ctc

00000000 T main

U printf

Here in the above output printf() & bbsr() are undefined.

$ nm -D -l -S ./a.out

080484b8 00000004 R _IO_stdin_used

w __gmon_start__

U __libc_start_main

U printf 

objdump

It displays information about object files.

This command is used to disassemble shared objects & libraries. It locates the method in which the problem originates.

Options:

-d Display the assembler mnemonics for the machine instructions from object file. This option disassembles only those sections that are expected to contain instructions.

-s Display the full contents of any section requested.

-h Display summary information from the section headers of the object file.

using objdump -h to list the file section headers can’t show the correct addresses. Instead, it shows the usual addresses, which are implicit for the target.

Example

//prg1.c

main()

{

static int x=12;

static int y;

printf(“%d”,x);

bbsr();

}

int bbsr()

{

printf(“Hi”);

}

$objdump -h ./a.out

output:

./a.out: file format elf32-i386

Sections:

Idx Name Size VMA LMA File off Algn

0 .interp 00000013 08048134 08048134 00000134 2**0

CONTENTS, ALLOC, LOAD, READONLY, DATA

1 .note.ABI-tag 00000020 08048148 08048148 00000148 2**2

CONTENTS, ALLOC, LOAD, READONLY, DATA

2 .note.gnu.build-id 00000024 08048168 08048168 00000168 2**2

CONTENTS, ALLOC, LOAD, READONLY, DATA

$ objdump -s -j .rowdata ./a.out

output:

a.out: file format elf32-i386

$ objdump -d -r -j .text ./a.out

output:

./a.out: file format elf32-i386

Disassembly of section .text:

080482f0 <_start>:

80482f0: 31 ed xor %ebp,%ebp

80482f2: 5e pop %esi

80482f3: 89 e1 mov %esp,%ecx

80482f5: 83 e4 f0 and $0xfffffff0,%esp

80482f8: 50 push %eax

The above output is the disassembly of text section with the -d flag. This option disassembles the section which are expected to contains the instructions.

How to analyze issue without source code

Run time tracing allows the debugger to identify the problem on executable. This technique shall also be used to understand the code flow of the program. There are tools which traces all system calls or library routines.

strace utility provides the capability to trace the execution of an application from the perspective of system calls. Along with the system call routine, it also displays their arguments, return value, etc

Linux permits to access 4 GB virtual address space for a process and that 4 GB virtual space is divided into two parts such as user space ( 3 GB) and kernel space (1 GB). When we run any application program along with library , they allocates memory from user space . Here in the following example printf is a library function and internally uses a standard library libc.so. The function printf writes data “Hello” into monitor , but how it happens.

Ex.

void main()

{

printf(“Hello”);

}

 

Operating system uses system call to copy the data from user space to kernel space and write into device file which is associated with a device ( example stdout for monitor) . The driver known as modules works in kernel space which reads the data from a device file and write into the port .

 

To list out the system call maintained by o/s there is a development tool called strace .Ittrace the system calls and signals . It intercepts and records the system calls made by a running process. strace can print a record of each system call, its arguments, and its return value. strace is a system call tracer, i.e. a debugging tool which prints out a trace of all the system calls .

$strace ./singo

output:

 

open(“/etc/ld.so.cache”, O_RDONLY) = 3

fstat64(3, {st_mode=S_IFREG|0644, st_size=111023, …}) = 0

mmap2(NULL, 111023, PROT_READ, MAP_PRIVATE, 3, 0) = 0xb7f91000

close(3) = 0

open(“/lib/libc.so.6”, O_RDONLY) = 3

read(3, “\177ELF\1\1\1\3\3\1\360\3247004″…, 512) = 512

write(1, “Hello”, 5Hello) = 5

Each line starts with a system call name, is followed by its arguments in the parenthesis & then has return value at the end of the line. The important system call made in the above output are open,close,read,write. The last line write(1, “Hello”, 5Hello) = 5 line corresponding to the system call that cause Hello to be printed on the screen. The first argument -1 is the file descriptor of the file i.e. stdout to write to. So it writes the message on the terminal instead of writing in some other file on disk. The second argument tells the data is a string & third argument display the total number of character in the string.

$ strace -c ./singo

Hello% time seconds usecs/call calls errors syscall

—— ———– ———– ——— ——— —————-

nan 0.000000 0 1 read

nan 0.000000 0 1 write

nan 0.000000 0 2 open

nan 0.000000 0 2 close

nan 0.000000 0 1 execve

nan 0.000000 0 1 1 access

nan 0.000000 0 1 brk

nan 0.000000 0 1 munmap

nan 0.000000 0 2 mprotect

nan 0.000000 0 7 mmap2

nan 0.000000 0 3 fstat64

nan 0.000000 0 1 set_thread_area

—— ———– ———– ——— ——— —————-

100.00 0.000000 23 1 total

 

From the above output, it is evident that write system call is used 1time. This is initiated by printf() statement on stdout file descriptor.

One another important option of strace is -tt, it causes strace to print out the time at which each call finished.

Library Tracing with ltrace

ltrace allows tracing any library function calls. It traces not only libc.so, but also any third party libraries.

To run ltrace on the executable ‘test’ created in the previous section, run

$ltrace ./test
It displays the following

__libc_start_main(0x80484c4, 1, 0xbfea17f4, 0x8048570, 0x8048560 <unfinished …>
fopen(“info.txt”, “r”)                                                                           = 0x8a03008
fgets(“1\n”, 80, 0x8a03008)                                                                      = 0xbfea16fc
printf(“Line %d: %s”, 4568017, “1\n”Line 4568017: 1
)                                                            = 16
—more output—-

fgets(“10\n”, 80, 0x8a03008)                                                                     = 0xbfea16fc
printf(“Line %d: %s”, 4568026, “10\n”Line 4568026: 10
)                                                           = 17
fgets(“10\n”, 80, 0x8a03008)                                                                     = NULL
fclose(0x8a03008)                                                                                = 0
+++ exited (status 0) +++
Without the source code, we can understand that fgets and printf functions are used heavily by this executable. We can try to optimize the code to reduce cpu cycles.

Most of the option present in strace is also present in ltrace. For the complete set of options run `man ltrace`.

Network Debugging Utility – tcpdump

tcpdump tool helps to see all or certain packets going over the Ethernet to debug network problems. It needs to be run as root under Linux in order to be able to sniff network packets.
The range of packets captured can be specified by the using a combination of logical operators and parameters such as source and destination IP addresses, protocol types and TCP/UDP port numbers.

tcpdump output has the following format,

For UDP packets

20:12:40.623187 csqlcache.com.3050> 192.168.1.51.34353: udp 234

where

Timestamp  20:12:40.623187
Source address csqlcache.com
Source port 3050
Destination address  192.168.1.51
Destination port 34353
Protocol udp
Packet Size  234

For TCP packets

20:12:40.623187 IP(…) csqlcache.com.3051 > 192.168.1.51.34353: P1:53(52)) ack 168 win 64315 

where

Timestamp  16:23:01.079553
Protocol IP
Source address csqlcache.com
Source port 3051
Destination address 192.168.1.51
Destination port 34353
Sequence number 1
Number of user data bytes in datagram (52)

To capture all traffic with the tcp or udp source or destination number 22 (ssh port), run the following command

$tcpdump port 22
It displays the following output

0:12:40.623084 IP (tos 0x10, ttl 64, id 34755, offset 0, flags [DF], proto TCP (6), length 92) 192.168.1.113.ssh > 192.168.1.103.appserv-https: P 3533382018:3533382070(52) ack 1574531805 win 9648
20:12:40.699411 IP (tos 0x10, ttl 64, id 34756, offset 0, flags [DF], proto TCP (6), length 156) 192.168.1.113.ssh > 192.168.1.103.appserv-https: P 52:168(116) ack 1 win 9648
20:12:40.623187 IP (tos 0x0, ttl 128, id 5012, offset 0, flags [DF], proto TCP (6), length 40) 192.168.1.103.appserv-https > 192.168.1.113.ssh: ., cksum 0x57ec (correct), ack 52 win 64431
20:12:40.777047 IP (tos 0x0, ttl 128, id 5013, offset 0, flags [DF], proto TCP (6), length 40) 192.168.1.103.appserv-https > 192.168.1.113.ssh: ., cksum 0x57ec (correct), ack 168 win 64315
20:12:41.506720 IP (tos 0x0, ttl 128, id 5014, offset 0, flags [DF], proto TCP (6), length 92) 192.168.1.103.appserv-https > 192.168.1.113.ssh: P 1:53(52) ack 168 win 64315
From this you can derive meaningful information for doing network analysis of your programs. This tool will be very helpful for debugging socket programs.

There are many options provided for this tool, for example

To capture all TCP traffic with source address csqlcache

$tcpdump tcp src host csqlcache
For complete set of options, please visit http://www.tcpdump.org/

Techniques to reduce memory footprint

Avoid using recursive calls

Recursive calls grow the stack memory of the process and when it is deeply nested, it may lead to stack overflow.

Prefer lazy loading than initial loading.

For example, if we need to count the number of words in a file, it is better to read the data line rather than reading the whole file into memory and then count the words.Readingline by line into the same buffer and processing each line can do this.

Prefer Shared libraries than static libraries

When shared library is used, the physical pages associated with the shared libraries are shared for all the process using that library. But in case of static libraries, each executable has its own copy leading to huge memory utilization for all the process using that library.

Modularizing and on-demand loading

Instead of linking your executable with your big-shared library, which contains all the functionality, we can modularize and create multiple shared libraries, which shall be loaded on demand based on the configuration. One issue with this, the performance will degrade as the program will do dlsym() to locate the symbol in the library. This we shall overcome by populating the function pointer list only once by providing the initialization function which does dlsym for all the necessary symbol and store it in lookup table or array of function pointers.

Use bit mask to store flags rather than bool or char data type

When multiple options need to be specified, it is usually defined as set of integer or character values that takes lot of space

struct Options{

bool isFlag1;

bool isFlag2;

bool isFlag3;

bool isFlag4;

bool isFlag5;

};

Instead, it can be stored in bit mask as follows

struct Options {

char opt;

};

#define FLAG1   1

#define FLAG2   2

#define FLAG1   4

#define FLAG1   8

#define FLAG1   16

Using the macro values defined above you can set the options by OR’ing values to it.