Difference between pages "r7.1.1:Binary Tree (add-only, unbalanced)" and "r7.1.1:Building Guide (benchmark)"

From liblfds.org
(Difference between pages)
Jump to navigation Jump to search
 
m (1 revision imported)
 
Line 1: Line 1:
{{DISPLAYTITLE:Binary Tree (add-only, unbalanced)}}
{{DISPLAYTITLE:Building Guide (benchmark)}}
==Source Files==
==Introducton==
  └───liblfds711
The ''benchmark'' binary is a thin command line veneer which provides convenient access to the benchmark functionality in ''libbenchmark''. The binary depends on ''liblfds711'', ''liblfds700'', ''libbenchmark'' and ''libshared''.
    ├───inc
    │  └───liblfds711
    │          lfds711_btree_addonly_unbalanced.h
    └───src
        └───lfds711_btree_addonly_unbalanced
                lfds711_btree_addonly_unbalanced_cleanup.c
                lfds711_btree_addonly_unbalanced_get.c
                lfds711_btree_addonly_unbalanced_init.c
                lfds711_btree_addonly_unbalanced_insert.c
                lfds711_btree_addonly_unbalanced_internal.h
                lfds711_btree_addonly_unbalanced_query.c


==Enums==
The ''benchmark'' library uses a porting abstraction layer to mask platform differences.  Building ''benchmark'' requires build files (makefile, etc) for your toolchain (GCC, gnumake, etc) and a port of the abstraction layer to your platform.
enum [[r7.1.1:enum lfds711_btree_au_absolute_position|lfds711_btree_au_absolute_position]];
enum [[r7.1.1:enum lfds711_btree_au_existing_key|lfds711_btree_au_existing_key]];
enum [[r7.1.1:enum lfds711_btree_au_insert_result|lfds711_btree_au_insert_result]];
enum [[r7.1.1:enum lfds711_btree_au_query|lfds711_btree_au_query]];
  enum [[r7.1.1:enum lfds711_btree_au_relative_position|lfds711_btree_au_relative_position]];


==Opaque Structures==
A small number of popular toolchains are supported out-of-the-box, along with porting abstraction layers which cover Windows (user-mode) and Linux (user-mode).
struct [[r7.1.1:struct lfds711_btree_au_element|lfds711_btree_au_element]];
struct [[r7.1.1:struct lfds711_btree_au_state|lfds711_btree_au_state]];


==Macros==
==Supported Toolchains==
  #define [[r7.1.1:macro LFDS711_BTREE_AU_GET_KEY_FROM_ELEMENT|LFDS711_BTREE_AU_GET_KEY_FROM_ELEMENT]]( btree_au_element )
The supported toolchains are;
  #define [[r7.1.1:macro LFDS711_BTREE_AU_SET_KEY_IN_ELEMENT|LFDS711_BTREE_AU_SET_KEY_IN_ELEMENT]]( btree_au_element, new_key )
 
   
* GCC and gnumake
#define [[r7.1.1:macro LFDS711_BTREE_AU_GET_VALUE_FROM_ELEMENT|LFDS711_BTREE_AU_GET_VALUE_FROM_ELEMENT]]( btree_au_element )
* MSVC and gnumake (yes, gnumake, not nmake)
  #define [[r7.1.1:macro LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT|LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT]]( btree_au_element, new_value )
 
Additionally, there is a second variant of the GCC and gnumake toolchain, which adds NUMA support in the form of ''libnuma''. All builds depend on releases 7.1.1 and 7.0.0 of ''liblfds''.  This is because the benchmark application benchmarks previous versions, as well as the current version, of ''liblfds'' data structures.  Releases 7.1.1 and 7.0.0 offer exactly the same platform support, so if 7.1.1 can compile, so can 7.0.0.
#define [[r7.1.1:macro LFDS711_BTREE_AU_GET_USER_STATE_FROM_STATE|LFDS711_BTREE_AU_GET_USER_STATE_FROM_STATE]]( btree_au_state )
 
The ''libnuma'' library is necessary under Linux to access NUMA functionality.  However, the library is an installed package and as such may or may not be installed.  It is not possible in C to optionally include header files, or to detect whether or not they are present; as such either something must detect the presence of absence of the libnuma library and its header file and then construct the makefile (the route taken with ''configure'') or the makefile must indicate to the build (through, say, a define passed to the compiler command line) whether or not libnuma is present.  The makefiles are intended to be platform indepedent, to support for example arbitrary embedded platforms, and so the presence of ''ldconfig'' cannot be assumed. As such, there is no obvious way to determine the presence of absence of ''libnuma'' - so as such, there is a seperate "toolchain" which is the normal GCC and gnumake makefile but with linking to ''libnuma'' and a define passed to the compiler.
 
Note that in 7.1.1, Visual Studio solution files are not provided.  This is because there are over ''liblfds'' and the ''benchmark'' and ''benchmark'' libraries and programmes (seven projects in all) in the end due to the multple build variants (debug, release, library, DLL, kernel library, kernel DLL, and repeated twice, once for VS2012 and once for VS2013) what comes to something like ten thousand settings, all of which have to be set using a mouse and a GUI, which is not only extraordinarily time-consuming and error-prone, but emotionally agonizing.
 
In all cases, the build files know where the various ''liblfds'' header and library files are, and so nothing needs to be installed for ''benchmark'' to build.
 
Mac support is not available due to lack of access to a Mac.
 
==Directory Structure==
  └── test_and_benchmark
    └── benchmark                                                : benchmark command line veneer
         ├── bin                                                  : output directory - the binary ends up here
         ├── build                                                : build configuration directory - contains one directory per platform
         │   ├── gcc_gnumake_hosted_liblfds711_liblfds700          : GCC, gnumake, hosted implementation, liblfds 7.1.1 and liblfds 7.0.0
         │   ├── gcc_gnumake_hosted_liblfds711_liblfds700_libnuma : GCC, gnumake, hosted implementation, liblfds 7.1.1, liblfds 7.0.0 and libnuma
         │   └── msvc_gnumake_liblfds711_liblfds700                : Microsoft Visual C (command line compiler), gnumake, liblfds 7.1.1 and liblfds 7.0.0
         ├── obj                                                  : temporary directory for object files
         └── src                                                  : the source files


==Prototypes==
==Building==
void [[r7.1.1:function lfds711_btree_au_init_valid_on_current_logical_core|lfds711_btree_au_init_valid_on_current_logical_core]]( struct lfds711_btree_au_state *baus,
The ''benchmark'' directory tree contains at its top level directory called ''build''.
                                                          int (*key_compare_function)(void const *new_key, void const *existing_key),
                                                          enum lfds711_btree_au_existing_key existing_key,
                                                          void *user_state );
void [[r7.1.1:function lfds711_btree_au_cleanup|lfds711_btree_au_cleanup]]( struct lfds711_btree_au_state *baus,
                                void (*element_cleanup_callback)(struct lfds711_btree_au_state *baus, struct lfds711_btree_au_element *baue) );
enum lfds711_btree_au_insert_result [[r7.1.1:function lfds711_btree_au_insert|lfds711_btree_au_insert]]( struct lfds711_btree_au_state *baus,
                                                              struct lfds711_btree_au_element *baue,
                                                              struct lfds711_btree_au_element **existing_baue );
int [[r7.1.1:function lfds711_btree_au_get_by_key|lfds711_btree_au_get_by_key]]( struct lfds711_btree_au_state *baus,
                                  int (*key_compare_function)(void const *new_key, void const *existing_key),
                                  void *key,
                                  struct lfds711_btree_au_element **baue );
int [[r7.1.1:function lfds711_btree_au_get_by_absolute_position_and_then_by_relative_position|lfds711_btree_au_get_by_absolute_position_and_then_by_relative_position]]( struct lfds711_btree_au_state *baus,
                                                                              struct lfds711_btree_au_element **baue,
                                                                              enum lfds711_btree_au_absolute_position absolute_position,
                                                                              enum lfds711_btree_au_relative_position relative_position );
int [[r7.1.1:function lfds711_btree_au_get_by_absolute_position|lfds711_btree_au_get_by_absolute_position]]( struct lfds711_btree_au_state *baus,
                                                struct lfds711_btree_au_element **baue,
                                                enum lfds711_btree_au_absolute_position absolute_position );
int [[r7.1.1:function lfds711_btree_au_get_by_relative_position|lfds711_btree_au_get_by_relative_position]]( struct lfds711_btree_au_element **baue,
                                                enum lfds711_btree_au_relative_position relative_position );
 
void [[r7.1.1:function lfds711_btree_au_query|lfds711_btree_au_query]]( struct lfds711_btree_au_state *baus,
                              enum lfds711_btree_au_query query_type,
                              void *query_input,
                              void *query_output );


==Overview==
This directory contains one directory per supported toolchain, where each such directory contains the files necessary to build for that toolchain.  Detailed descriptions of how to build for each toolchain are given below, with one heading per toolchain.
This data structure implements an add-only, unbalanced btree.  It supports any number of concurrent users, and internally implements exponential backoff to help deal with high load and so improve scalability (although being a btree it naturally acts to distribute memory access behaviour which helps scalability).


The implementation performs no allocations.  The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them.  As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store.  Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.
The ''benchmark'' binary depends on ''liblfds711'', ''liblfds700'', ''libbenchmark'' and ''libshared''.  The ''benchmark'' build files are hardcoded with relative paths to find the output from these libraries, so these libraries do not need to be installed.


General usage is that the user calls ''lfds711_btree_au_init_valid_on_current_logical_core'' to initialize a ''struct lfds711_btree_au_state'', and then calls ''lfds711_btree_au_link'' to add elements.  A btree element provides the ability to store a key (used to place elements in the btree) and a value, both of which are of type ''void *'' and can either point to data, or can be used directly, as key comparason is performed by a user-provided callback and the value is not touched by the btree code.
On all platforms, you need to clean between changing build types (debug, release, static, dynamic, profiled, etc), as there is only one directory used to hold object files.


(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)
==Per-Toolchain Build Instructions==


The key and value are get and set in elements by macros, such as ''LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT''. The key can only be set in elements before they are added to a tree.  The value can be set at any time, in elements both inside and outside of the tree.
===GCC and gnumake===
  └── test_and_benchmark
    └── benchmark
        └── build
            └── gcc_gnumake_hosted_liblfds711_liblfds700
                    Makefile


The state and element structures are both public, present in the ''lfds711_btree_au.h'' header file, so that users can embed them in their own structures (and where necessary pass them to ''sizeof'').  Expected use is that user structures which are to enter btrees contain within themselves a ''struct lfds711_btree_au_element'', where the user sets the key as necessary for the btree and the value to point to the user structure entering the btree.  This approach permits zero run-time allocation of store and also ensures the btree element is normally in the same memory page as the user data it refers to.
To build, install GCC and gnumake, enter the build directory and type;


When initializing the btree, the caller specifies the behaviour of the btree when the attempt is mde to add a new element which has a key already present in the btree. The btree can be configured to either fail to add the element, or it can be configured to overwrite the value in the existing element with the value of the new element.
  make


Finally, when all is said and done, use ''lfds711_btree_au_cleanup'' to cleanup the tree.  Once this function has returned, the user is then safe to deallocate all allocations.
The following targets are available;


==Lock-free Specific Behaviour==
cov    : coverage
The state initialization function, ''lfds711_btree_au_init_valid_on_current_logical_core'', as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro ''[[r7.1.1:define LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'', which will do that which its name suggests.
dbg    : debug
prof    : profiling
rel    : release
tsan    : thread sanitizer
vanilla : no specific-build arguments
  clean  : what you'd expect


Once a btree element structure has been linked to the btree, it cannot be deallocated (''free'', or stack allocation lifetimes ending due to say a thread ending, etc) until ''lfds711_btree_au_cleanup'' has returned.  Elements cannot be removed from the tree, or moved within the tree.  Their value however can be changed at any time.
When switching from one target to another, ''clean'' must be made.


The SET macro for the key in an element can only be correctly used on elements which are outside of a btree.  The SET macro for the value in an element can be used at any time, on any element.  By correctly is it meant to say that the GET macros will actually read the data written by the SET macros, and not some other data.  I don't have to tell you how much chaos will ensure if different logical cores are reading different keys for the same element...
If building ''*_ar_tsan'', ''libtsan'' must be installed.  This is not necessary if building ''*_so_tsan''.


If shared memory is used for allocations, the virtual addresses must be the same across different processes.
===GCC, gnumake and libnuma===
└── test_and_benchmark
    └── benchmark
        └── build
            └── gcc_gnumake_hosted_liblfds711_liblfds700_libnuma
                    Makefile


==Benchmark Results and Analysis==
To build, install GCC, gnumake and libnuma (package name is usually "numctl-dev" or "numactl-devel"), enter the build directory and type;
<html>
      <table border="1" cellpadding="8">
        <tr>
          <th class="header" colspan="4">btree (add-only, unbalanced)</th>
        <tr>


        <tr>
make
          <th class="header">ARM32</th>
          <th class="header">MIPS32</th>
          <th class="header" colspan="2">x64</th>
        </tr>


        <tr>
The following targets are available;
          <th class="header">Raspberry Pi 2 Model B</th>
          <th class="header">Ci20</th>
          <th class="header">AWS dedicated VM</th>
          <th class="header">Core i5</th>
        </tr>


        <tr>
cov    : coverage
          <td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Raspberry Pi 2 Model B (ARM32).1200x1800.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Raspberry Pi 2 Model B (ARM32).300x450.png"/></a></td>
dbg    : debug
          <td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Ci20 (MIPS32).800x1200.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Ci20 (MIPS32).300x450.png"/></a></td>
prof    : profiling
          <td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Amazon VM dedicated c4.4xlarge.4800x5400.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Amazon VM dedicated c4.4xlarge.300x337.png"/></a></td>
rel    : release
          <td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Core i5 (x64).1200x1800.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Core i5 (x64).300x450.png"/></a></td>
tsan    : thread sanitizer
        </tr>
vanilla : no specific-build arguments
      </table>
</html>
clean  : what you'd expect


The benchmark consists of a btree state which has 1024 elements per thread, where each element has a random integer key, where the benchmark loops, performing one read and then one write operation, where the key used for the read and the key used for the write are randomly selected from the pool of keys.  The pthread rwlock uses a read lock for reading, and a write lock for writing.  The locking versions of the btree have one lock for the entire btree, and so only one thread accesses the btree at a time (except in the case of rwlocks, where naturally any number of readers can access the tree at any time).
When switching from one target to another, ''clean'' must be made.


This beanchmark is in fact flawed.  As the number of elements in the btree increases the mean number of steps through the btree to find an element increases.  This means as the core count rises, the work being done by a single operation is increasing.
If building ''*_ar_tsan'', ''libtsan'' must be installed.  This is not necessary if building ''*_so_tsan''.


The btree data structure benefits massively from a lock-free implementation.  In locking implementations there is typically one lock per tree, so the entire tree is single-threaded. With rwlocks, there can be any number of readers, but only a single writer, and the rwlock itself is a point of contention.  With lock-free, any number of thread can execute concurrently, for read and for write, and the btree, by its distributed nature, inherently lacks particular memory locations which experience contention.  End result is excellent scalability, as demonstrated in the 16 core AWS dedicated VM gnuplot.
If building for ARM32 with shared object versions of the ''liblfds'' libraries, linking will fail, with the error ''"/usr/bin/ld: ../../bin/benchmark: hidden symbol `__aeabi_uidiv' in /usr/lib/gcc/arm-linux-gnueabihf/4.9/libgcc.a(_udivsi3.o) is referenced by DSO"''.  This means something has attempted to divide a 64 bit value by a 64 bit value, an operation which apparently is costly and usually unnecessary, a 32 bit divisor apparently is normally adequate, and as such is intentionally caught in a link-breaking way.


Version 7.0.0 was inefficient in its use of cache lines.  This actually led on the Raspberry Pi 2 Model B to the btree performing at about one tenth of the speed of the locking implementations!  fixing this implementation error returned the btree to its usual place, about three times faster (on up to four cores).
Unfortunately, as far as can be determined, ''liblfds'' itself is not performing this operation - and as such, it is not obvious how to fix it.


The autotuning exponential backoff hardly makes any difference to btree performance. Where the elements are spread out in a probabalistically balanced tree (the keys are random), threads are issuing highly dispersed memory accesses and rarely collide.
===MSVC and gnumake===
  └── test_and_benchmark
    └── benchmark
        └── build
            └── msvc_gnumake_liblfds711_liblfds700
                    makefile


==White Paper==
To build, install an MSVC command line compiler, enter the build directory and type;
There is no white paper for this data structure; it is native to ''liblfds''.


==License==
make
Standard ''liblfds'' license - there is no license. You are free to use this code in any way. Go forth and create wealth!


If however for legal reasons a licence is required, the license of your choice will be granted, and license for convenience is hereby granted up front for a range of popular licenses : the MIT license, the BSD license, the Apache license, the GPL and LPGL (all versions thereof) and the Creative Commons licenses (all of them).  Additionally, this library (which is to say, the source code, build files, documentation, everything) is placed in the public domain.
The following targets are available;


==Example==
dlldbg  : debug  (with ''liblfds'' libs built as DLLs)
  #include <stdio.h>
  dllrel  : release (with ''liblfds'' libs built as DLLs)
  #include <stdlib.h>
  libdbg  : debug  (with ''liblfds'' libs built as libs)
  #include "liblfds711.h"
  librel  : release (with ''liblfds'' libs built as libs)
   
   
  struct test_data
  clean   : what you'd expect
{
 
  int long long unsigned
When switching from one target to another, clean must be made.
    unique_id;
  char
    payload[64];
  struct lfds711_btree_au_element
    buae;
};
int key_compare_function( void const *new_key, void const *existing_key )
{
  int
    cr = 0;
  int long long unsigned
    *new_key = (int long long unsigned *) new_key,
    *existing_key  = (int long long unsigned *) existing_key;
  if( *new_key > *existing_key )
    cr = 1;
  if( *new_key < *existing_key )
    cr = -1;
  return( cr );
}
int main()
{
  enum lfds711_btree_au_insert_result
    bauir;
  int long long unsigned
    loop;
  struct lfds711_btree_au_element
    *buae = NULL;
  struct lfds711_btree_au_state
    baus;
    
  struct test_data
    *td,
    *temp_td;
 
  lfds711_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS711_BTREE_AU_EXISTING_KEY_FAIL, NULL );
  // TRD : allocate ten test elements, populate with dummy data and link to tree
  td = malloc( sizeof(struct test_data) * 10 );
  for( loop = 0 ; loop < 10 ; loop++ )
  {
    td[loop].unique_id = loop;
    sprintf( td[loop].payload, "the unique id is %llu", loop );
    LFDS711_BTREE_AU_SET_KEY_IN_ELEMENT( td[loop].baue, &td[loop].unique_id );
    LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT( td[loop].baue, &td[loop] );
    bauir = lfds711_btree_au_insert( baus, &td[loop].baue, NULL );
    if( bauir != LFDS711_BTREE_AU_INSERT_RESULT_SUCCESS )
      printf( "Well, bugger!  so much for quality control\n" );
  }
  // TRD : now in-order walk the tree
  while( lfds711_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS711_BTREE_AU_SMALLEST_IN_TREE, LFDS711_BTREE_AU_INORDER_WALK_FROM_SMALLEST_TO_LARGEST) )
  {
    temp_td = LFDS711_BTREE_AU_GET_VALUE_FROM_ELEMENT( *baue );
    printf( "element %llu has value \"%s\"\n", temp_td->unique_id, temp_id->payload );
  }
  lfds711_btree_au_cleanup( &baus, NULL );
  free( td );
  return( EXIT_SUCCESS );
}


==See Also==
==See Also==
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]
* [[r7.1.1:Building Guide (benchmarking)|Building Guide (benchmarking)]]

Latest revision as of 20:16, 17 February 2017

Introducton

The benchmark binary is a thin command line veneer which provides convenient access to the benchmark functionality in libbenchmark. The binary depends on liblfds711, liblfds700, libbenchmark and libshared.

The benchmark library uses a porting abstraction layer to mask platform differences. Building benchmark requires build files (makefile, etc) for your toolchain (GCC, gnumake, etc) and a port of the abstraction layer to your platform.

A small number of popular toolchains are supported out-of-the-box, along with porting abstraction layers which cover Windows (user-mode) and Linux (user-mode).

Supported Toolchains

The supported toolchains are;

  • GCC and gnumake
  • MSVC and gnumake (yes, gnumake, not nmake)

Additionally, there is a second variant of the GCC and gnumake toolchain, which adds NUMA support in the form of libnuma. All builds depend on releases 7.1.1 and 7.0.0 of liblfds. This is because the benchmark application benchmarks previous versions, as well as the current version, of liblfds data structures. Releases 7.1.1 and 7.0.0 offer exactly the same platform support, so if 7.1.1 can compile, so can 7.0.0.

The libnuma library is necessary under Linux to access NUMA functionality. However, the library is an installed package and as such may or may not be installed. It is not possible in C to optionally include header files, or to detect whether or not they are present; as such either something must detect the presence of absence of the libnuma library and its header file and then construct the makefile (the route taken with configure) or the makefile must indicate to the build (through, say, a define passed to the compiler command line) whether or not libnuma is present. The makefiles are intended to be platform indepedent, to support for example arbitrary embedded platforms, and so the presence of ldconfig cannot be assumed. As such, there is no obvious way to determine the presence of absence of libnuma - so as such, there is a seperate "toolchain" which is the normal GCC and gnumake makefile but with linking to libnuma and a define passed to the compiler.

Note that in 7.1.1, Visual Studio solution files are not provided. This is because there are over liblfds and the benchmark and benchmark libraries and programmes (seven projects in all) in the end due to the multple build variants (debug, release, library, DLL, kernel library, kernel DLL, and repeated twice, once for VS2012 and once for VS2013) what comes to something like ten thousand settings, all of which have to be set using a mouse and a GUI, which is not only extraordinarily time-consuming and error-prone, but emotionally agonizing.

In all cases, the build files know where the various liblfds header and library files are, and so nothing needs to be installed for benchmark to build.

Mac support is not available due to lack of access to a Mac.

Directory Structure

└── test_and_benchmark
    └── benchmark                                                 : benchmark command line veneer
        ├── bin                                                   : output directory - the binary ends up here
        ├── build                                                 : build configuration directory - contains one directory per platform
        │   ├── gcc_gnumake_hosted_liblfds711_liblfds700          : GCC, gnumake, hosted implementation, liblfds 7.1.1 and liblfds 7.0.0
        │   ├── gcc_gnumake_hosted_liblfds711_liblfds700_libnuma  : GCC, gnumake, hosted implementation, liblfds 7.1.1, liblfds 7.0.0 and libnuma
        │   └── msvc_gnumake_liblfds711_liblfds700                : Microsoft Visual C (command line compiler), gnumake, liblfds 7.1.1 and liblfds 7.0.0
        ├── obj                                                   : temporary directory for object files
        └── src                                                   : the source files

Building

The benchmark directory tree contains at its top level directory called build.

This directory contains one directory per supported toolchain, where each such directory contains the files necessary to build for that toolchain. Detailed descriptions of how to build for each toolchain are given below, with one heading per toolchain.

The benchmark binary depends on liblfds711, liblfds700, libbenchmark and libshared. The benchmark build files are hardcoded with relative paths to find the output from these libraries, so these libraries do not need to be installed.

On all platforms, you need to clean between changing build types (debug, release, static, dynamic, profiled, etc), as there is only one directory used to hold object files.

Per-Toolchain Build Instructions

GCC and gnumake

└── test_and_benchmark
    └── benchmark
        └── build
            └── gcc_gnumake_hosted_liblfds711_liblfds700
                    Makefile

To build, install GCC and gnumake, enter the build directory and type; 

make

The following targets are available; 

cov     : coverage
dbg     : debug
prof    : profiling
rel     : release
tsan    : thread sanitizer
vanilla : no specific-build arguments

clean   : what you'd expect

When switching from one target to another, clean must be made.

If building *_ar_tsan, libtsan must be installed. This is not necessary if building *_so_tsan.

GCC, gnumake and libnuma

└── test_and_benchmark
    └── benchmark
        └── build
            └── gcc_gnumake_hosted_liblfds711_liblfds700_libnuma
                    Makefile

To build, install GCC, gnumake and libnuma (package name is usually "numctl-dev" or "numactl-devel"), enter the build directory and type; 

make

The following targets are available; 

cov     : coverage
dbg     : debug
prof    : profiling
rel     : release
tsan    : thread sanitizer
vanilla : no specific-build arguments

clean   : what you'd expect

When switching from one target to another, clean must be made.

If building *_ar_tsan, libtsan must be installed. This is not necessary if building *_so_tsan.

If building for ARM32 with shared object versions of the liblfds libraries, linking will fail, with the error "/usr/bin/ld: ../../bin/benchmark: hidden symbol `__aeabi_uidiv' in /usr/lib/gcc/arm-linux-gnueabihf/4.9/libgcc.a(_udivsi3.o) is referenced by DSO". This means something has attempted to divide a 64 bit value by a 64 bit value, an operation which apparently is costly and usually unnecessary, a 32 bit divisor apparently is normally adequate, and as such is intentionally caught in a link-breaking way.

Unfortunately, as far as can be determined, liblfds itself is not performing this operation - and as such, it is not obvious how to fix it.

MSVC and gnumake

└── test_and_benchmark
    └── benchmark
        └── build
            └── msvc_gnumake_liblfds711_liblfds700
                    makefile

To build, install an MSVC command line compiler, enter the build directory and type; 

make

The following targets are available; 

dlldbg  : debug   (with liblfds libs built as DLLs)
dllrel  : release (with liblfds libs built as DLLs)
libdbg  : debug   (with liblfds libs built as libs)
librel  : release (with liblfds libs built as libs)

clean   : what you'd expect

When switching from one target to another, clean must be made.

See Also

Retrieved from ‘https://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Binary_Tree_(add-only,_unbalanced)&oldid=1086’