LinAsm benchmarks

LinAsm benchmarks were made to demonstrate how fast the libraries are. Benchmarks source and latest LinAsm release may be downloaded by the links at the bottom of this page. You may compile and run these tests on your own PC to get personal results and find is there any space for speed improvement for your platform and the code.

Following tests use vector extensions of x86 processors from first SSE version to SSE 4.2 instructions set. They do not use AVX extension for now. I will try to fix this and make AVX version in future. But I cannot provide any deadline for this.

Benchmarks compare LinAsm functions with scalar code and analogous functions from GNU libc and C++ STL. Not all LinAsm functions have analogs in C library, because the main goal of this project is not to replace C library or STL, but reimplement some widely used algorithms from different libraries and improve their speed. This is very critical for engineering calculations, data analysis and multimedia software.

Testing platform

All tests were made for single thread (except tests for ADTs, which have single and concurrent threads benchmarks) on Intel Core i5 CPU (2 physical cores with hyper-threading technology) using a laptop with 4Gb of RAM, running 64-bit Arch Linux live CD. No other tasks were running during the tests. All functions in LinAsm libraries are thread safe, except the abstract data types (which use access predicates to provide thread safety). So you may expect linear speed improvement for multithreading programs with no memory conflicts. CPU specification of the laptop is provided below. Its peak performance is around 6 GFlops per each core.

processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 37
model name      : Intel(R) Core(TM) i5 CPU       M 480  @ 2.67GHz
stepping        : 5
microcode       : 0x2
cpu MHz         : 2667.000
cache size      : 3072 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 2
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 11
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm
                  pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni dtes64
                  monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 popcnt lahf_lm ida arat dtherm tpr_shadow vnmi
                  flexpriority ept vpid
bogomips        : 5321.30
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

All benchmarks were compiled by GCC (version 5.3.0) with following optimization flags:

-std=gnu++11 -O2 -march=native -mtune=native -fomit-frame-pointer -fno-builtin -fno-inline

Numbers conversion

Numbers conversion library is the finite-state automaton that extracts number values from string, convert them to binary representation, and check numbers for overflow and underflow conditions. This is common task for importing data from CSV and TSV files.

For this test were generated 16,384 random numbers. They were converted to string format and then were extracted 1000 times from strings to get precise results. As you may see in following table, "sscanf" functions are very slow because they should recognize number format and then call associated core function to extract number value. "strtoul" and "strtod" work faster, but they are also not so very fast as assembly written variants, which can be much more effective for floating-point numbers.

Time conversion

Time conversion is not most used algorithm in opposite to other functions described in these benchmarks. When I was processing time series, I found that lot of time were spent in time stamp extraction procedure. It took too much time, so I decide to improve such procedure. I developed time conversion library, which provides such functional to time and date values and do it very fast.

Following benchmark generates 131,072 time stamps and then converts them 100 times from Unix time format to Gregorian time and date format and vice versa. LinAsm functions beat standard lib C time functions in many times.

Math library

Math library is excellent place for optimizations, especially if you work with data analysis algorithms and create models of real processes. Currently the Math library implements only basic math functions, I used for my projects. But I have plans to extend its functionality and add more functions to it.

This benchmark generates 131,072 random numbers and use them to calculate standard math functions, operating with these values as parameters. Each test runs in 1,000 round to get precise time, each function takes for calculation. Math functions guarantee precision loss no more than 2 less significant bits. It is enough for multimedia and data processing.

Scalar functions

Vectorized functions (single precision)

Vectorized functions (double precision)

Array library

Array library can improve trivial array operations and replace scalar code with vector code, written in assembly language, which uses SIMD extension of modern processors. To run this code your CPU should support SSE 4.2 extension (almost all modern processors were bought during last 5 years).

Array functions intensively use memory prefetch commands. It improves processing of really big portions of data, because of efficient use of cache memory. The main bottleneck of modern computers is memory subsystem, which is much slower than CPU, and require non trivial code optimization to get high performance. You also may see that single precision numbers take 2 times less CPU cycles to process. It is because of memory bandwidth. Single precision data are 2 times shorter than double precision and take 2 times less memory space.

Next benchmark generates 131,072 elements wide random arrays, and tests scalar and vector code for these arrays 10,000 times to get precise time values for scalar and vector code. Sort functions are ran only ones to sort random arrays in ascending sort order. To measure performance of integer operations was generated random array of bytes (uint8_t) and then scalar and vector operations were invoked.

Integer operations

Single precision operations

Double precision operations

Statistics library

Statistics library implements basic statistical functions, that process empirical data and return such values as data mean, standard deviation, skewness, kurtosis and robust parameters as median and inter-quartile range. They take regular arrays and process them to compute appropriate functions.

For this benchmark were generated 131,072 elements wide random arrays. The tests were ran 10,000 times to get precise time values. You may see, that the bottleneck for this benchmark is memory bandwidth, because single precision data has almost the same process time (see scalar code) as double precision data. But the vector code took 2 times less CPU cycles for single precision data, because of type size.

Single precision operations

Double precision operations

Object pool library

If you allocate and release a lot of small objects in your algorithm, then the Object Pool is a good idea to replace the standard lib C "malloc" and "free" functions. Object pool allocates predefined amount of objects, which also can be aligned by power of 2, and then returns them when you need a new object, or puts them back in the pool when the object is released. This operation is very fast and do not call heavy memory management functions.

This benchmark creates 16,384 objects of different sizes (from 8 to 256 bytes) and then allocate them and release 1,000 times.

Vector ADT

Vector is the first and very simple abstract data type. It is most used STL container that holds elements and may replace standard arrays. LinAsm implements it own vector container that around 2 times faster for most operations than STL vector. It has non STL interface, but much more optimized and cache friendly code. Benchmark just shows the speed (keys per seconds) you may expects for data processing algorithms, which are based on that data type.

For this benchmark were created 1,048,576 random keys in range [0, 131,072), then they were pushed and popped from the vector in single and concurrent threads. All other functions were also invoked in 16 rounds for filled vector in single and concurrent threads (4 threads) to measure the time each operation takes.

Deque ADT

Double ended queue is the second most popular abstract data type. Typically it is implemented as circular buffer or double licked list. LinAsm uses automatically extended circular buffer for deque. It makes it as fast as vector adt and around 2 times faster than deque from STL library. Benchmark creates 1,048,576 random keys with 8 duplicates (average case) in range [0, 131,072), then push them into tail and pop them from head in single and concurrent threads manner. Each deque operation is done 16 times to get precise time measurement. The result table is shown below. You may see how fast (keys per second) each function is.

Heap ADT

MinHeap and MaxHeap (also known as priority_queue in STL) is used when you require prioritization inside your service. Typicaly it is implemented by binary tree, projected onto plain array (vector). STL does not implement container priority_queue, but only the adaptor, which can be based on standard vector or queue. LinAsm uses regular array to store the keys. Instead of classic binary tree, it uses N-ary tree (currently each root node has 4 children, which are less or equal to the root). Child node (cluster of child elements) is aligned by CPU cache line, and all 4 children can be prefetched by one memory reading operation. It improves heap speed in 2 - 3 times in compare with standard array based binary tree.

Benchmark creates 1,048,576 random keys with 8 duplicates (average case) in range [0, 131,072), and put them into the heap in single thread and in concurrent threads manner (see the table below). Then it uses standard vector operations to find, count and check keys into the container. Multiple thread tests were ran in 4 threads on 2 cores CPU with hyper threading, enabled for each core. Concurrent threads were run in 16 rounds, to be sure that threads have worked in the same time. All the tests proved that cache aligned key store algorithm give you significant performance benefit.

List ADT

List abstract data type uses big nodes, which hold more than one element into the node. Neighbor elements are grouped together to allow very fast access to previous and next elements. This improvement tries to optimize usage of CPU cache memory and accelerates standard list operations. This benchmark creates 1,048,576 of random elements, puts them into the list object and then tests speed of standard list operations. Each test shows how many keys per second were handled by the operation.

Multiple thread tests simultaneously invoke associated function in 4 threads, iterating all elements 16 times per thread, and show cumulative result (keys per second) for all of them. As you may see again, the memory speed is main limiter of all multiple thread algorithms. And show even less performance than single thread read access to data. It is because of CPU cache. All processes is trying to use CPU cache exclusively, and push out data of another threads, which downgrade the result. This can be fixed with computation intensive code among read operations.

Hash table ADT

Hash table abstract data types (UniqueHash and MultiHash) provide the same functionality as STL "unordered_map" and "unordered_multimap" templates.

This benchmark creates 1,048,576 random keys in range [0, 131,072) (8 duplicates per key in average case) and put them into hash table. Then it invokes standard operations such as "find", "count", "unique", "remove" and iterates all the elements, using sequential iterators, to measure hash table performance. The result of each operation is represented as the number of keys divided by the total time, each operation has took.

Some functions were tested in both single and multiple thread modes. Actually they were ran in 4 simultaneous threads on 2 cores CPU, which support hyperthreading technology. Multiple thread tests used external iterators, which provide highly concurrent read only access to elements of hash table. Benchmark just cyclically invokes target functions for all hash table elements 8 times, to guarantee, that threads were run simultaneous all the time, and access the same memory blocks. As you may see the memory bandwidth is bottleneck for all multiple thread algorithms, if you do not sparse data access code with mathematical processing of found keys.

Tree ADT

Tree ADTs, are provided by the LinAsm library (UniqueTree and MultiTree), are equivalent to STL "map" and "multimap" classes. They are based on in-memory B-trees, instead of red-black trees, are used by the STL. B-trees hold neighbor keys grouped into one big node (cluster of keys). This trick reduces tree height and optimize cache memory usage. It also speed up sequential iteration procedure, because next and previous elements are grouped together, and do not require addition pointer operations, except for the first/last element into the node. This benchmark shows how many keys per seconds each operation can handle if you insert elements in ascending, descending or random order. All tests were ran for 1,048,576 elements wide trees.

Multiple thread tests do the same as multiple thread tests for hash table and list ADTs. Each benchmark was run in 4 threads in 8 rounds, to be sure that all process were running simultaneously. The result shows cumulative speed of all the processes. And again we see speed downgrade, because of cache concurrency. You can be sure in that fact, because STL implementation shows the same behavior in multiple thread mode. And again it may be fixed by mathematically intensive code among data access code.

Ascending keys

Descending keys

Random keys

Afterword and links

You may see that vectorized code and cache friendly algorithms may significantly improve performance of C and C++ programs, which do intensive calculations, or memory operations. The main reason of code slowdown on modern CPUs is slow memory access. And it is the place where we should do some kind of optimization, to get speed improvement. LinAsm can accelerate CPU intensive and memory intensive programs, using fast algorithms for common functions and optimized requests for memory reading/writing operations.

The source codes of all benchmarks and latest LinAsm release you may download by the links below. To reproduce these tests on your PC, a CPU should support SSE 4.2 operations. In other case you will get Invalid opcode error message.