Algorithms&DatastructuresinC++&GO(LockFreeQueue)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

//已实现 ( Implemented ):

Array shuffle	https://github.com/xtaci/algorithms/blob/master/include/shuffle.h
Prime test(trial division)	https://github.com/xtaci/algorithms/blob/master/include/prime.h
Prime test(Miller-Rabin's method)	https://github.com/xtaci/algorithms/blob/master/include/prime.h
2D Array	https://github.com/xtaci/algorithms/blob/master/include/2darray.h
Arbitrary Integer	https://github.com/xtaci/algorithms/blob/master/include/integer.h
Linear congruential generator	https://github.com/xtaci/algorithms/blob/master/include/random.h
Maximum subarray problem	https://github.com/xtaci/algorithms/blob/master/include/max_subarray.h
Bit-Set	https://github.com/xtaci/algorithms/blob/master/include/bitset.h
Queue	https://github.com/xtaci/algorithms/blob/master/include/queue.h
Stack	https://github.com/xtaci/algorithms/blob/master/include/stack.h
Binary Heap	https://github.com/xtaci/algorithms/blob/master/include/heap.h
Fibonacci Heap	https://github.com/xtaci/algorithms/blob/master/include/fib-heap.h
Priority Queue (list based)	https://github.com/xtaci/algorithms/blob/master/include/priority_queue.h
Bubble sort	https://github.com/xtaci/algorithms/blob/master/include/bubble_sort.h
Selection sort	https://github.com/xtaci/algorithms/blob/master/include/selection_sort.h
Insertion sort	https://github.com/xtaci/algorithms/blob/master/include/insertion_sort.h
Shell sort	https://github.com/xtaci/algorithms/blob/master/include/shell_sort.h
Radix sort	https://github.com/xtaci/algorithms/blob/master/include/radix_sort.h
Quicksort	https://github.com/xtaci/algorithms/blob/master/include/quick_sort.h
Merge sort	https://github.com/xtaci/algorithms/blob/master/include/merge_sort.h
Double linked list	https://github.com/xtaci/algorithms/blob/master/include/double_linked_list.h
Skip list	https://github.com/xtaci/algorithms/blob/master/include/skiplist.h
Largest common sequence	https://github.com/xtaci/algorithms/blob/master/include/lcs.h
Binary search tree	https://github.com/xtaci/algorithms/blob/master/include/binary_search_tree.h
AVL tree	https://github.com/xtaci/algorithms/blob/master/include/avl.h
Dynamic order statistics	https://github.com/xtaci/algorithms/blob/master/include/dos_tree.h
Red-black tree	https://github.com/xtaci/algorithms/blob/master/include/rbtree.h
Interval tree	https://github.com/xtaci/algorithms/blob/master/include/interval_tree.h
Prefix Tree(Trie)	https://github.com/xtaci/algorithms/blob/master/include/trie.h
Suffix Tree	https://github.com/xtaci/algorithms/blob/master/include/suffix_tree.h
B-Tree	https://github.com/xtaci/algorithms/blob/master/include/btree.h
Suffix Array	https://github.com/xtaci/algorithms/blob/master/include/suffix_array.h
Hash by multiplication	https://github.com/xtaci/algorithms/blob/master/include/hash_multi.h
Hash table	https://github.com/xtaci/algorithms/blob/master/include/hash_table.h
Universal hash function	https://github.com/xtaci/algorithms/blob/master/include/universal_hash.h
Perfect hash	https://github.com/xtaci/algorithms/blob/master/include/perfect_hash.h
Java's string hash	https://github.com/xtaci/algorithms/blob/master/include/hash_string.h
FNV-1a string hash	https://github.com/xtaci/algorithms/blob/master/include/hash_string.h
SimHash	https://github.com/xtaci/algorithms/blob/master/include/simhash.h
Bloom Filter	https://github.com/xtaci/algorithms/blob/master/include/bloom_filter.h
SHA-1 Message Digest Algorithm	https://github.com/xtaci/algorithms/blob/master/include/sha1.h
MD5	https://github.com/xtaci/algorithms/blob/master/include/md5.h
Base64	https://github.com/xtaci/algorithms/blob/master/include/base64.h
Strongly Connected Components(SCC)	https://github.com/xtaci/algorithms/blob/master/include/scc.h
Prim's minimum spanning tree	https://github.com/xtaci/algorithms/blob/master/include/prim_mst.h
Kruskal MST	https://github.com/xtaci/algorithms/blob/master/include/kruskal_mst.h
Breadth First Search	https://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Depth First Search	https://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Dijkstra's algorithm	https://github.com/xtaci/algorithms/blob/master/include/dijkstra.h
Bellman-Ford algorithm	https://github.com/xtaci/algorithms/blob/master/include/bellman_ford.h
Edmonds-Karp Maximal Flow	https://github.com/xtaci/algorithms/blob/master/include/edmonds_karp.h
Push–Relabel algorithm	https://github.com/xtaci/algorithms/blob/master/include/relabel_to_front.h
Huffman Coding	https://github.com/xtaci/algorithms/blob/master/include/huffman.h
Word segementation	https://github.com/xtaci/algorithms/blob/master/include/word_seg.h
A* algorithm	https://github.com/xtaci/algorithms/blob/master/include/astar.h
K-Means	https://github.com/xtaci/algorithms/blob/master/include/k-means.h
Knuth–Morris–Pratt algorithm	https://github.com/xtaci/algorithms/blob/master/include/kmp.h
Disjoint-Set	https://github.com/xtaci/algorithms/blob/master/include/disjoint-set.h
8-Queue Problem	https://github.com/xtaci/algorithms/blob/master/include/8queen.h
Palindrome	https://github.com/xtaci/algorithms/blob/master/include/palindrome.h
LCA using Binary Lifting	https://github.com/xtaci/algorithms/blob/master/include/LCA.h

go-queue

前一久看到一篇文章美团高性能队列——Disruptor，时候自己琢磨了一下；经过反复修改，实现了一个相似的无锁队列EsQueue，该无锁队列相对Disruptor，而言少了队列数量属性quantity的CAP操作，因此性能杠杠的，在测试环境：windows10，Core(TM) i5-3320M CPU 2.6G, 8G 内存，go1.8.3，下性能达到1460-1600万之间。现在把代码发布出来，请同行验证一下，代码如下：

注：请注意本方法已经通过 go test -race, 无警告。
go1.8.3 amd64, Grp:   1, Times:   10000000, miss:     0, use:   573.9109ms,     57ns/op
go1.8.3 amd64, Grp:   2, Times:   20000000, miss:     0, use:   1.1548186s,     57ns/op
go1.8.3 amd64, Grp:   3, Times:   30000000, miss:     0, use:   1.6787567s,     55ns/op
go1.8.3 amd64, Grp:   4, Times:   40000000, miss:     0, use:   2.2651588s,     56ns/op
go1.8.3 amd64, Grp:   5, Times:   50000000, miss:     0, use:   2.8762257s,     57ns/op
go1.8.3 amd64, Grp:   6, Times:   60000000, miss:     0, use:   3.4914045s,     58ns/op
go1.8.3 amd64, Grp:   7, Times:   70000000, miss:     0, use:   4.0040473s,     57ns/op
go1.8.3 amd64, Grp:   8, Times:   80000000, miss:     0, use:   4.5712089s,     57ns/op
go1.8.3 amd64, Grp:   9, Times:   90000000, miss:     0, use:      5.1765s,     57ns/op
go1.8.3 amd64, Grp:  10, Times:   10000000, miss:     0, use:    586.914ms,     58ns/op
go1.8.3 amd64, Grp:  11, Times:   11000000, miss:     0, use:   644.4879ms,     58ns/op
go1.8.3 amd64, Grp:  12, Times:   12000000, miss:     0, use:   694.4974ms,     57ns/op
go1.8.3 amd64, Grp:  13, Times:   13000000, miss:     0, use:   745.5212ms,     57ns/op
go1.8.3 amd64, Grp:  14, Times:   14000000, miss:     0, use:   822.6344ms,     58ns/op
go1.8.3 amd64, Grp:  15, Times:   15000000, miss:     0, use:   868.4927ms,     57ns/op
go1.8.3 amd64, Grp:  16, Times:   16000000, miss:     0, use:   943.6699ms,     58ns/op
go1.8.3 amd64, Grp: Sum, Times:  541000000, miss:     0, use:  31.0982489s,     57ns/op

awesome-lockfree

Libraries

Boost.Lockfree - Boost lock-free data structures.
ConcurrencyKit - Concurrency primitives.
Folly - Facebook Open-source Library (has good implementation of MPMC queue).
Junction - Concurrent data structures in C++.
MPMCQueue - A bounded multi-producer multi-consumer lock-free queue written in C++11.
SPSCQueue - A bounded single-producer single-consumer wait-free and lock-free queue written in C++11.
Seqlock - Implementation of Seqlock in C++.
Userspace RCU - liburcu is a userspace RCU (read-copy-update) library.
libcds - A C++ library of Concurrent Data Structures.

Websites

1024cores - Dmitry Vyukov's website on lock-free programming.
LMAX Disruptor
Wikipedia: Non-blocking algorithm
Wikipedia: Read-copy-update
Wikipedia: Seqlock

Blogs

Concurrency Freaks - A web site dedicated to Concurrent algorithms and patterns.
Dan Luu - Lots of info on modern computer architecture.
Locking in Webkit
Mechanical Sympathy
Paul E. McKenney
Preshing on Programming
Sutter's Mill - Herb Sutter on software development.

Books

Paul E. McKenney. Is Parallel Programming Hard, And, If So, What Can You Do About It?

Papers

A Tutorial Introduction to the ARM and POWER Relaxed Memory Models
Paul E. McKenney. Memory Barriers: a Hardware View for Software Hackers.
Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms - The Michael - Scott Queue
Ulrich Drepper. What Every Programmer Should Know About Memory
x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors

Talks

CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part I"
CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part II"
CppCon 2015: Fedor Pikus PART 1 “Live Lock-Free or Deadlock (Practical Lock-free Programming)"
CppCon 2015: Fedor Pikus PART 2 "Live Lock-Free or Deadlock (Practical Lock-free Programming)"
CppCon 2015: Michael Wong “C++11/14/17 atomics and memory model..."
CppCon 2015: Paul E. McKenney “C++ Atomics..."
CppCon 2014: Tony Van Eerd "Lock-free by Example"
CppCon 2016: Fedor Pikus "The Speed of Concurrency: is lock-free faster?"
CppCon 2016: Hans Boehm “Using weakly ordered C++ atomics correctly"
C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 1 of 2
C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 2 of 2
"Aeron: Open-source high-performance messaging" by Martin Thompson
Adventures with Concurrent Programming in Java: A Quest for Predictable Latency - Martin Thompson
Understanding the Disruptor, a Beginner's Guide to Hardcore Concurrency -Trisha Gee & Mike Barker