lpd-epfl / ascylib Goto Github PK

ASCYLIB (with OPTIK) is a concurrent-search data-structure library with over 40 implementantions of linked lists, hash tables, skip lists, binary search trees, queues, and stacks.

Home Page: http://lpd.epfl.ch/site/ascylib

License: GNU General Public License v2.0

Makefile 1.63% C++ 1.04% C 86.65% Shell 4.36% R 0.42% Gnuplot 3.84% Java 2.04% Roff 0.02%

ascylib's Introduction

ASCYLIB + OPTIK

ASCYLIB (with OPTIK) is a concurrent data-structure library. It contains over 40 implementations of linked lists, hash tables, skip lists, binary search trees (BSTs), queues, priority queues, and stacks. ASCYLIB contains sequential, lock-based, and lock-free implementations for each data structure.

ASCYLIB works on x86, SPARC, and Tilera architectures and contains tests to evaluate the throughput, latency, latency distribution, and energy efficiency of the included data structures.

OPTIK is a new design pattern for easily implementing fast and scalable concurrent data structures. We have merged several concurrent data structures developed with OPTIK in ASCYLIB. More details can be found here: http://lpd.epfl.ch/site/optik.

Website : http://lpd.epfl.ch/site/ascylib - http://lpd.epfl.ch/site/optik
Authors : Vasileios Trigonakis [email protected], Tudor David [email protected]
Related Publications:
- Optimistic Concurrency with OPTIK,
  Rachid Guerraoui, Vasileios Trigonakis (alphabetical order),
  PPoPP 2016
- Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures,
  Tudor David, Rachid Guerraoui, Vasileios Trigonakis (alphabetical order),
  ASPLOS 2015

Algorithms

The following table contains the algorithms (and various implementations of some algorithms) included in ASCYLIB:

#	Name	Progress	Year	Referece
	Array Maps
1	Java's CopyOnWrite array map	lock-based	2004	[ORACLE+04]
2	Global-lock array map	lock-based	2016	[GT+16]
3	OPTIK global-lock array map	lock-based	2016	[GT+16]
	Linked lists
4	Sequential linked list	sequential
5	Hand-over-hand locking linked list	lock-based		[HS+12]
6	Pugh's linked list	lock-based	1990	[P+90]
7	Harris linked list	lock-free	2001	[H+01]
8	Michael linked list	lock-free	2002	[M+02]
9	Lazy linked list	lock-based	2006	[HHL+06]
10	Harris linked list with ASCY	lock-free	2015	[DGT+15]
11	Global-lock linked list with wait-free search	lock-based	2016	[GT+16]
12	OPTIK global-lock linked list	lock-based	2016	[GT+16]
13	OPTIK fine-grained linked list	lock-based	2016	[GT+16]
14	OPTIK fine-grained linked list with cache	lock-based	2016	[GT+16]
	Hash Tables
15	Sequential hash table	sequential
16	Sequential hash table - less pointer indirections	sequential
17	Hash table using hand-over-hand-locking lists	lock-based		[HS+12]
18	Hash table using Pugh's list	lock-based	1990	[P+90]
19	Hash table using Harris' list	lock-free	2001	[H+01]
20	Java's ConcurrentHashMap	lock-based	2003	[L+03]
21	Hash table using Java's CopyOnWrite array map	lock-based	2004	[ORACLE+04]
22	Intel's TBB hash table	lock-based	2006	[INTEL+06]
23	Hash table using lazy list	lock-based	2006	[HHL+06]
24	URCU hash table	lock-free	2012	[DMS+12]
25	Java's ConcurrentHashMap with OPTIK	lock-based	2016	[GT+16]
26	Hash table using fine-grained OPTIK list	lock-based	2016	[GT+16]
27	Hash table using global-lock OPTIK list	lock-based	2016	[GT+16]
28	Hash table using OPTIK array map	lock-based	2016	[GT+16]
	Skip Lists
29	Sequential skip list	sequential
30	Pugh skip list	lock-based	1990	[P+90]
31	Fraser skip list	lock-free	2003	[F+03]
32	Herlihy et al. skip list	lock-based	2007	[HLL+07]
33	Fraser skip list with Herlihy's optimization	lock-free	2011	[HLS+11]
34	Herlihy's skip list with OPTIK	lock-based	2016	[GT+16]
35	OPTIK skip list using trylocks (default OPTIK skip list)	lock-based	2016	[GT+16]
36	OPTIK skip list lock-version	lock-based	2016	[GT+16]
	Binary Search Trees (BSTs)
37	Sequential external binary search tree	sequential
38	Sequential internal binary search tree	sequential
39	Bronson et al. binary search tree	lock-based	2010	[BCH+10]
40	Ellen et al. binary search tree	lock-free	2010	[EFR+10]
41	Howley and Jones binary search tree	lock-free	2012	[HJ+12]
42	Natarajan and Mittal binary search tree	lock-free	2014	[NM+14]
43	Drachsler et al. binary search tree	lock-based	2014	[DVY+14]
44	BST-TK binary search tree	lock-based	2015	[DGT+15]
	Queues
45	Michael and Scott (MS) lock-based queue	lock-based	1996	[MS+96]
46	Michael and Scott (MS) lock-free queue	lock-free	1996	[MS+96]
47	Michael and Scott (MS) hybrid queue	lock-based	1996	[MS+96]
48	MS queue with OPTIK lock-version	lock-based	2016	[GT+16]
49	MS queue with OPTIK trylock-version	lock-based	2016	[GT+16]
50	MS queue with OPTIK trylock-version	lock-based	2016	[GT+16]
51	MS queue with OPTIK and victim queue	lock-based	2016	[GT+16]
	Priority Queues
52	Lotan and Shavit priority queue	lock-free	2000	[LS+00]
53	Alistarh et al. priority queue based on Fraser's skip list	lock-based	2015	[AKL+15]
54	Alistarh et al. priority queue based on Herlihy's skip list	lock-based	2015	[AKL+15]
55	Alistarh et al. priority queue based on Pugh's skip list	lock-based	2015	[AKL+15]
	Stacks
56	Global-lock stack	lock-based
57	Treiber stack	lock-free	1986	[T+86]
58	Treiber stack with OPTIK trylocks	lock-based	2016	[GT+16]

References

[AKL+15] D. Alistarh, J. Kopinsky, J. Li, N. Shavit. The SprayList: A Scalable Relaxed Priority Queue. PPoPP '15.
[BCH+10] N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A Practical Concurrent Binary Search Tree. PPoPP '10.
[DGT+15] T. David, R. Guerraoui, and V. Trigonakis. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. ASPLOS '15.
[DMS+12] M. Desnoyers, P. E. McKenney, A. S. Stern, M. R. Dagenais, and J. Walpole. User-level implementations of read-copy update. PDS '12.
[DVY+14] D. Drachsler, M. Vechev, and E. Yahav. Practical Concurrent Binary Search Trees via Logical Ordering. PPoPP '14.
[EFR+10] F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking Binary Search Trees. PODC '10.
[F+03] K. Fraser. Practical Lock-Freedom. PhD thesis, University of Cambridge, 2004.
[GT+16] R. Guerraoui, and V. Trigonakis. Optimistic Concurrency with OPTIK. PPoPP '16.
[H+01] T. Harris. A Pragmatic Implementation of Non-blocking Linked Lists. DISC '01.
[HHL+06] S. Heller, M. Herlihy, V. Luchangco, M. Moir, W. N. Scherer, and N. Shavit. A Lazy Concurrent List-Based Set Algorithm. OPODIS '05.
[HS+12] M. Herlihy and N. Shavit. The Art of Multiprocessor Programming, Revised First Edition. 2012.
[HLL+07] M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A Simple Optimistic Skiplist Algorithm. SIROCCO '07.
[HLS+11] M. Herlihy, Y. Lev, and N. Shavit. Concurrent lock-free skiplist with wait-free contains operator, May 3 2011. US Patent 7,937,378.
[HJ+12] S. V. Howley and J. Jones. A non-blocking internal binary search tree. SPAA '12.
[INTEL+06] Intel. Intel Thread Building Blocks. https://www.threadingbuildingblocks.org.
[L+03] D. Lea. Overview of Package util.concurrent Release 1.3.4. http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html, 2003.
[LS+00] I. Lotan and N. Shavit. Skiplist-based concurrent priority queues. IPDPS '00.
[M+02] M. M. Michael. High Performance Dynamic Lock-free Hash tables and List-based Sets. SPAA '02.
[MS+96] M. M. Michael and M. L. Scott. Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms. PODC '96.
[NM+14] A. Natarajan and N. Mittal. Fast Concurrent Lock-free Binary Search Trees. PPoPP '14.
[ORACLE+04] Oracle. Java CopyOnWriteArrayList. http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/CopyOnWriteArrayList.html.
[P+90] W. Pugh. Concurrent Maintenance of Skip Lists. Technical report, 1990.
[T+86] R. Treiber. Systems Programming: Coping with Parallelism. Technical report, 1986.

New Algorithms

BST-TK is a new lock-based BST, introduced in ASCYLIB. Additionally, CLHT is a new hash hash table, introduced in ASCYLIB. We provide lock-free and lock-based variants of CLHT as a separate repository (https://github.com/LPD-EPFL/CLHT). Details of the algorithms and proofs/sketches of correctness can be found in the following technical report: https://infoscience.epfl.ch/record/203822

We have developed the following algorithms using OPTIK:

A simple array map (in src/hashtable-map_optik).
We use this map in a hash table (in src/hashtable-optik0);
An optimistic global-lock-based linked list (in src/linkedlist-optik_gl).
We use this list in a hash table (in src/hashtable-optik1);
A fine-grained linked list (in src/linkedlist-optik).
We use this list in a hash table (in src/hashtable-optik0);
A skip list algorithm (in src/skiplist-optik1).
We also provide a variant of the same algorithm (in src/skiplist-optik).

Additionally, we have optimized existing algorithms using OPTIK:

Java's ConcurrentHashMap algorithm (insrc/hashtable-java_optik);
Herlihy's optimistic skip list (in src/skiplist-optik2);
The classic Michael-Scott queues: * lock-based push, pop optimized with optik_lock_version_backoff (in src/queue-optik0) * lock-based push, pop optimized with optik_trylock_version (in src/queue-optik1) * lock-free push, pop optimized with optik_trylock_version (in src/queue-optik2)

Finally, we have introduced two optimization techniques inspired by OPTIK:

Node caching for optimizing lists (in src/linkedlist-optik_cache);
Victim queue for optimizing push in queues (in src/queue-optik3).

Compilation

ASCYLIB requires the ssmem memory allocator (https://github.com/LPD-EPFL/ssmem). We have already compiled and included ssmem in external/lib for x86_64, SPARC, and the Tilera architectures. Still, if you would like to create your own build of ssmem, take the following steps. Clone ssmem, do make libssmem.a and then copy libssmem.a in ASCYLIB/external/lib and smmem.h in ASCYLIB/external/include.

Additionally, the sspfd profiler library is required (https://github.com/trigonak/sspfd). We have already compiled and included sspfd in external/lib for x86_64, SPARC, and the Tilera architectures. Still, if you would like to create your own build of sspfd, take the following steps. Clone sspfd, do make and then copy libsspfd.a in ASCYLIB/external/lib and sspfd.h in ASCYLIB/external/include.

Finally, to measure power on new Intel processors (e.g., Intel Ivy Bridge), the raplread library is required (https://github.com/LPD-EPFL/raplread). We have already compiled and included raplread in external/lib. Still, if you would like to create your own build of raplread, take the following steps. Clone raplread, do make and then copy libraplread.a in ASCYLIB/external/lib and sspfd.h in ASCYLIB/external/include.

To build all data structures, you can execute make all. This target builds all lock-free, lock-based, and sequential data structures.

The last two structures, RCU and TBB, are based on external libraries. The RCU-based hash table requires an installation of the URCU library (http://urcu.so/). You need to set the URCU_PATH in common/Makefile.common to point to the folder of your local URCU installation, or alternatively, you can install URCU globally. The TBB-based hash table requires an installation of Intel's TBB library (https://www.threadingbuildingblocks.org/). You need to set the TBB_LIBS and the TBB_INCLUDES variables in common/Makefile.common, or alternatively, you can install TBB globally.

To build all data structures except from those two, you can issue make.

ASCYLIB includes a default configuration that uses gcc and tries to infer the number of cores and the frequency of the target/build platform. If this configuration is incorrect, you can always create a manual configurations in common/Makefile.common and include/utils.h (look in these files for examples). If you do not care about pinning threads to cores, these settings do not matter. You can compile with make SET_CPU=0 ... to disable thread pinning.

ASCYLIB accepts various compilation parameters. Please refer to the COMPILE file.

Tests

Building ASCYLIB generate per-data-structure benchmarks in the bin directory. Issue ./bin/executable -h for the parameters each of those accepts.

Depending on the compilation flags, these benchmarks can be set to measure throughtput, latency, and/or power-consumption statistics.

Scripts

ASCYLIB includes tons of usefull scripts (in the scripts folders). Some particularly useful ones are:

scalability.sh and scalability_rep.h: run the given list of executable on the given (list of) number of threads, with the given parameters, and report throughput and scalability over single-threaded execution.
scripts in apslos/ directory: they were used to create the plots for the ASPLOS '15 paper. In particular, apslos/run_scy.sh accepts configuration files (see asplos/config) so it can be configured to execute almost any per-data-structure scenario.
scripts in ppopp/ directory: they were used to create the plots for the PPoPP '16 paper. In particular, ppopp/run_and_plot.sh can run and plot graphs for all the tests in the paper.

Thanks

Some of the initial implementations used in ASCYLIB were taken from Synchrobench (https://github.com/gramoli/synchrobench - V. Gramoli. More than You Ever Wanted to Know about Synchronization. PPoPP 2015.).

ascylib's People

Contributors

Stargazers

Watchers

ascylib's Issues

Something wrong with the Algorithms declaration in README

As far as I know, the Howley tree is the first lock-free(non-blocking) internal BST, while in README it is claimed as lock-based.

I don't know whether I missed something?

Correct hardware-independent thread pinning

Have you thought about using hwloc to do hardware independent thread pinning? It would add a dependency on the one hand, but make things much easier for people running this lib on the other. It'd also let allow you to remove the horrible the_cores hack ;)

A quick draft of the required changes below:

diff --git a/common/Makefile.common b/common/Makefile.common
index d8bba15..f51050b 100644
--- a/common/Makefile.common
+++ b/common/Makefile.common
@@ -248,7 +248,7 @@ CFLAGS += -Wall
 CFLAGS += -fno-strict-aliasing
 CFLAGS += -I$(LIBAO_INC) -I$(ROOT)/include -I$(LIBSSMEM)/include

-LDFLAGS += -lpthread -lrt -lm
+LDFLAGS += -lpthread -lrt -lm -lhwloc

 ######################
 # compilation settings
diff --git a/include/utils.h b/include/utils.h
index 609fe5a..c5e4f92 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -655,36 +655,25 @@ static __attribute__ ((unused)) double eng_per_test_iter_nj[40][5] =
     return (double)t.tv_sec + ((double)t.tv_usec)/1000000.0;
   }

+#include <hwloc.h>
+  hwloc_topology_t m_topology;
+
   static inline 
   void set_cpu(int cpu) 
   {
-#ifndef NO_SET_CPU
-#  ifdef __sparc__
-    processor_bind(P_LWPID,P_MYID, cpu, NULL);
-#  elif defined(__tile__)
-    if (cpu>=tmc_cpus_grid_total()) {
-      perror("Thread id too high");
+    const int depth = hwloc_get_type_or_below_depth(m_topology, HWLOC_OBJ_CORE);
+    const int ncores = hwloc_get_nbobjs_by_depth(m_topology, depth);
+
+    const hwloc_obj_t obj = hwloc_get_obj_by_depth(m_topology, depth, cpu % ncores);
+
+    hwloc_cpuset_t cpuset = hwloc_bitmap_dup(obj->cpuset);
+    hwloc_bitmap_singlify(cpuset);
+
+    if (hwloc_set_cpubind(m_topology, cpuset, HWLOC_CPUBIND_THREAD) != 0) {
+        fprintf(stderr, "Could not bind to core: %s\n", strerror(errno));
     }
-    // cput_set_t cpus;
-    if (tmc_cpus_set_my_cpu(cpu)<0) {
-      tmc_task_die("tmc_cpus_set_my_cpu() failed."); 
-    }    
-#  else
-    cpu %= (NUMBER_OF_SOCKETS * CORES_PER_SOCKET);
-
-    cpu_set_t mask;
-    CPU_ZERO(&mask);
-    CPU_SET(cpu, &mask);
-#    if defined(PLATFORM_NUMA)
-    numa_set_preferred(get_cluster(cpu));
-#    endif
-    pthread_t thread = pthread_self();
-    if (pthread_setaffinity_np(thread, sizeof(cpu_set_t), &mask) != 0) 
-      {
-   fprintf(stderr, "Error setting thread affinity\n");
-      }
-#  endif
-#endif
+
+    hwloc_bitmap_free(cpuset);    
   }


diff --git a/src/priorityqueue-alistarh/test_simple.c b/src/priorityqueue-alistarh/test_simple.c
index 03099f7..5c1ebdc 100755
--- a/src/priorityqueue-alistarh/test_simple.c
+++ b/src/priorityqueue-alistarh/test_simple.c
@@ -130,7 +130,7 @@ test(void* thread)
   thread_data_t* td = (thread_data_t*) thread;
   uint32_t ID = td->id;
   int phys_id = the_cores[ID];
-  set_cpu(phys_id);
+  set_cpu(ID);
   ssalloc_init();

   DS_TYPE* set = td->set;
@@ -295,10 +295,16 @@ test(void* thread)
   pthread_exit(NULL);
 }

+#include <hwloc.h>
+extern hwloc_topology_t m_topology;
+
 int
 main(int argc, char **argv) 
 {
-  set_cpu(the_cores[0]);
+  hwloc_topology_init(&m_topology);
+  hwloc_topology_load(m_topology);
+
+  set_cpu(0);
   ssalloc_init();
   seeds = seed_rand();

@@ -398,8 +404,6 @@ main(int argc, char **argv)
    }
     }

-
-
   if (!is_power_of_two(initial))
     {
       size_t initial_pow2 = pow2roundup(initial);
@@ -608,6 +612,8 @@ main(int argc, char **argv)
   RR_PRINT_UNPROTECTED(RAPL_PRINT_POW);
   RR_PRINT_CORRECTED();
   RETRY_STATS_PRINT(total, putting_count_total, removing_count_total, putting_count_total_succ + removing_count_total_succ);
+
+  hwloc_topology_destroy(m_topology);

   pthread_exit(NULL);

Write a correct implementation of harris linked list

Vincent's implementation breaks (wrong size) once in a while. I also tried 2 implementations from students, but they also do break.

Include as external library

I was able to compile the library itself. However, I'm lost in including the library to an external project. Please share the advice.

undocumented algorithms

Thanks for releasing such a great project.
In the src directory, I find some undocumented algorithms.
Those following are not list in the table in README.

/src/linkedlist-lazy_orig/
/src/linkedlist-lazy_cache/
/src/linkedlist-lazy_sp/
/src/skiplist-pugh-string/
/src/stack-optik1/
/src/stack-optik2/
/src/queue-hybrid/
/src/queue-optik2a/
/src/queue-optik4/
/src/queue-optik5/

Could you add some explanation for those code?
Additional question:
What is the lock file in some directories? How to use it? (such as src/linkedlist-lazy/lock)
Thanks a lot!

torn reads/writes during optimistic handling phase

Hi,
I have looked through some of the examples included in the library specifically the hashtable, as I am looking to replace traditional mutex based locking in my own hashtable implementation, which resizes dynamically and uses open addressing for collision resolution, with optik lock. It seems to me there is more to it than the simple semantics of version lookup, validation, etc... It seems I have to now convert some of my variables into atomic types in order to avoid torn reads/writes. For example, inserting new element I'd need to check the current size of the table, reading off the value without the safetynet of a mutex or atomic load can result in torn read. How do you deal with that under the optik pattern?
I was hoping to be able to resize optimistically, and apply the lock only when i am ready to rehash items, because that's an expensive operation to have to restart upon version pdates, but if my snapshot of the original size is torn, that is an issue, to state it mildly. I could very well be missing something totally basic, though.

regards

Try to make lock-free skip list implementation more efficient

The URCU hash table is lock-free

The one in the Linux kernel is not exactly the one in the URCU. We probably need the implementation from the kernel as well

lfll - michael is not an exact representation of the code in the paper

Michael, M. M. (2002). High performance dynamic lock-free hash tables and list-based sets.

Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures
- SPAA ’02, 73. doi:10.1145/564879.564881

About your implementations

Hi, all!

This project is wonderful, I have been searching for a concurrency library implemented in C for long time. Before I find this project, I study the code from "the art of multiprocessor programming", while all of them are in Java.

But questions still left, one is that have you implemented all the features from the paper?

For example, I read Bronson's practical concurrent BST. I find that he has incorporated "fast clone" technique, but I cannot find a similar one in your code.

The other thing is about your correctness testing program, can you explain what's the idea behind the code?

Thank you very much!

../../include/measurements.h:335:10: fatal error: 'malloc.h' file not found

Hi, I tried to type "make all" in ASCYLIB folder principal, and I got this error:

/Applications/Xcode.app/Contents/Developer/usr/bin/make "STM=LOCKFREE" src/linkedlist-harris src/linkedlist-harris_opt src/linkedlist-michael src/hashtable-harris src/skiplist-fraser src/skiplist-herlihy_lf src/bst-ellen src/bst-howley src/bst-aravind src/priorityqueue-alistarh src/priorityqueue-lotanshavit_lf src/priorityqueue-alistarh-herlihyBased src/queue-ms_lf src/stack-treiber
/Applications/Xcode.app/Contents/Developer/usr/bin/make -C src/linkedlist-harris 
cat: /sys/devices/system/cpu/cpu0/cpufreq/cpuinfo_max_freq: No such file or directory
(standard_in) 1: parse error
make[2]: nproc: Command not found
********************************** Using as a default number of cores:  on 1 socket
********************************** Using as a default frequency      :  GHz
********************************** If incorrect, create a manual entry in common/Makefile.common
make[2]: nproc: Command not found
cc -O3 -D_GNU_SOURCE -DLOCKFREE -DDEFAULT -DCORE_NUM= -DFREQ_GHZ= -m64 -Wall -fno-strict-aliasing -I../../src/atomic_ops -I../../include -I../../external/include -DGC=2 -DINITIALIZE_FROM_ONE=1 -c -o ../../build/measurements.o ../../src/measurements.c
In file included from ../../src/measurements.c:29:
../../include/measurements.h:335:10: fatal error: 'malloc.h' file not found
#include <malloc.h>
         ^
1 error generated.
make[2]: *** [measurements.o] Error 1
make[1]: *** [src/linkedlist-harris] Error 2
make: *** [lockfree] Error 2

After I copied my usr/include/malloc/malloc.h file and put on ASCYLIB/include folder, now terminal showing:

/Applications/Xcode.app/Contents/Developer/usr/bin/make "STM=LOCKFREE" src/linkedlist-harris src/linkedlist-harris_opt src/linkedlist-michael src/hashtable-harris src/skiplist-fraser src/skiplist-herlihy_lf src/bst-ellen src/bst-howley src/bst-aravind src/priorityqueue-alistarh src/priorityqueue-lotanshavit_lf src/priorityqueue-alistarh-herlihyBased src/queue-ms_lf src/stack-treiber
/Applications/Xcode.app/Contents/Developer/usr/bin/make -C src/linkedlist-harris 
cat: /sys/devices/system/cpu/cpu0/cpufreq/cpuinfo_max_freq: No such file or directory
(standard_in) 1: parse error
make[2]: nproc: Command not found
********************************** Using as a default number of cores:  on 1 socket
********************************** Using as a default frequency      :  GHz
********************************** If incorrect, create a manual entry in common/Makefile.common
make[2]: nproc: Command not found
cc -O3 -D_GNU_SOURCE -DLOCKFREE -DDEFAULT -DCORE_NUM= -DFREQ_GHZ= -m64 -Wall -fno-strict-aliasing -I../../src/atomic_ops -I../../include -I../../external/include -DGC=2 -DINITIALIZE_FROM_ONE=1 -c -o ../../build/measurements.o ../../src/measurements.c
make[2]: nproc: Command not found
cc -O3 -D_GNU_SOURCE -DLOCKFREE -DDEFAULT -DCORE_NUM= -DFREQ_GHZ= -m64 -Wall -fno-strict-aliasing -I../../src/atomic_ops -I../../include -I../../external/include -DGC=2 -DINITIALIZE_FROM_ONE=1 -c -o ../../build/ssalloc.o ../../src/ssalloc.c
../../src/ssalloc.c:117:17: warning: implicit declaration of function 'memalign'
      is invalid in C99 [-Wimplicit-function-declaration]
  ret = (void*) memalign(alignement, size);
                ^
../../src/ssalloc.c:117:9: warning: cast to 'void *' from smaller integer type
      'int' [-Wint-to-void-pointer-cast]
  ret = (void*) memalign(alignement, size);
        ^
2 warnings generated.
make[2]: nproc: Command not found
cc -O3 -D_GNU_SOURCE -DLOCKFREE -DDEFAULT -DCORE_NUM= -DFREQ_GHZ= -m64 -Wall -fno-strict-aliasing -I../../src/atomic_ops -I../../include -I../../external/include -DGC=2 -DINITIALIZE_FROM_ONE=1 -c -o ../../build/linkedlist.o linkedlist.c
In file included from linkedlist.c:24:
In file included from ./linkedlist.h:36:
../../include/atomic_ops_if.h:169:37: error: invalid use of a cast in a inline
      asm context requiring an l-value: remove the cast or build with
      -fheinous-gnu-extensions
        :"=r" ((unsigned long long) x)
               ~~~~~~~~~~~~~~~~~~~~~^
../../include/atomic_ops_if.h:180:27: error: invalid use of a cast in a inline
      asm context requiring an l-value: remove the cast or build with
      -fheinous-gnu-extensions
        :"=r" ((uint64_t) x)
               ~~~~~~~~~~~^
../../include/atomic_ops_if.h:190:27: error: invalid use of a cast in a inline
      asm context requiring an l-value: remove the cast or build with
      -fheinous-gnu-extensions
        :"=r" ((uint32_t) x)
               ~~~~~~~~~~~^
../../include/atomic_ops_if.h:200:27: error: invalid use of a cast in a inline
      asm context requiring an l-value: remove the cast or build with
      -fheinous-gnu-extensions
        :"=r" ((uint16_t) x)
               ~~~~~~~~~~~^
../../include/atomic_ops_if.h:210:26: error: invalid use of a cast in a inline
      asm context requiring an l-value: remove the cast or build with
      -fheinous-gnu-extensions
        :"=r" ((uint8_t) x)
               ~~~~~~~~~~^
In file included from linkedlist.c:24:
In file included from ./linkedlist.h:39:
In file included from ../../include/utils.h:43:
../../include/random.h:56:28: warning: implicit declaration of function
      'memalign' is invalid in C99 [-Wimplicit-function-declaration]
  seeds = (unsigned long*) memalign(64, 64);
                           ^
../../include/random.h:56:11: warning: cast to 'unsigned long *' from smaller
      integer type 'int' [-Wint-to-pointer-cast]
  seeds = (unsigned long*) memalign(64, 64);
          ^
In file included from linkedlist.c:24:
In file included from ./linkedlist.h:39:
../../include/utils.h:664:38: error: expected expression
    return thread_id/CORES_PER_SOCKET;
                                     ^
../../include/utils.h:696:2: error: use of undeclared identifier 'cpu_set_t'
        cpu_set_t mask;
        ^
../../include/utils.h:697:2: warning: implicit declaration of function
      'CPU_ZERO' is invalid in C99 [-Wimplicit-function-declaration]
        CPU_ZERO(&mask);
        ^
../../include/utils.h:697:12: error: use of undeclared identifier 'mask'; did
      you mean 'umask'?
        CPU_ZERO(&mask);
                  ^~~~
                  umask
/usr/include/sys/stat.h:359:8: note: 'umask' declared here
mode_t  umask(mode_t);
        ^
In file included from linkedlist.c:24:
In file included from ./linkedlist.h:39:
../../include/utils.h:698:2: warning: implicit declaration of function 'CPU_SET'
      is invalid in C99 [-Wimplicit-function-declaration]
        CPU_SET(cpu_use, &mask);
        ^
../../include/utils.h:698:20: error: use of undeclared identifier 'mask'; did
      you mean 'umask'?
        CPU_SET(cpu_use, &mask);
                          ^~~~
                          umask
/usr/include/sys/stat.h:359:8: note: 'umask' declared here
mode_t  umask(mode_t);
        ^
In file included from linkedlist.c:24:
In file included from ./linkedlist.h:39:
../../include/utils.h:703:6: warning: implicit declaration of function
      'pthread_setaffinity_np' is invalid in C99
      [-Wimplicit-function-declaration]
        if (pthread_setaffinity_np(thread, sizeof(cpu_set_t), &mask) != 0) 
            ^
../../include/utils.h:703:44: error: use of undeclared identifier 'cpu_set_t'
        if (pthread_setaffinity_np(thread, sizeof(cpu_set_t), &mask) != 0) 
                                                  ^
5 warnings and 10 errors generated.
make[2]: *** [linkedlist.o] Error 1
make[1]: *** [src/linkedlist-harris] Error 2
make: *** [lockfree] Error 2

Thanks.
Sincerely.