Algorithms & Data structures in C++& GO ( Lock Free Queue)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

https://github.com/xtaci/algorithms

//已实现 ( Implemented ):Array shufflehttps://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 Arrayhttps://github.com/xtaci/algorithms/blob/master/include/2darray.h
Arbitrary Integerhttps://github.com/xtaci/algorithms/blob/master/include/integer.h
Linear congruential generatorhttps://github.com/xtaci/algorithms/blob/master/include/random.h
Maximum subarray problemhttps://github.com/xtaci/algorithms/blob/master/include/max_subarray.h
Bit-Sethttps://github.com/xtaci/algorithms/blob/master/include/bitset.h
Queuehttps://github.com/xtaci/algorithms/blob/master/include/queue.h
Stackhttps://github.com/xtaci/algorithms/blob/master/include/stack.h
Binary Heaphttps://github.com/xtaci/algorithms/blob/master/include/heap.h
Fibonacci Heaphttps://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 sorthttps://github.com/xtaci/algorithms/blob/master/include/bubble_sort.h
Selection sorthttps://github.com/xtaci/algorithms/blob/master/include/selection_sort.h
Insertion sorthttps://github.com/xtaci/algorithms/blob/master/include/insertion_sort.h
Shell sorthttps://github.com/xtaci/algorithms/blob/master/include/shell_sort.h
Radix sorthttps://github.com/xtaci/algorithms/blob/master/include/radix_sort.h
Quicksorthttps://github.com/xtaci/algorithms/blob/master/include/quick_sort.h
Merge sorthttps://github.com/xtaci/algorithms/blob/master/include/merge_sort.h
Double linked listhttps://github.com/xtaci/algorithms/blob/master/include/double_linked_list.h
Skip listhttps://github.com/xtaci/algorithms/blob/master/include/skiplist.h
Largest common sequencehttps://github.com/xtaci/algorithms/blob/master/include/lcs.h
Binary search treehttps://github.com/xtaci/algorithms/blob/master/include/binary_search_tree.h
AVL treehttps://github.com/xtaci/algorithms/blob/master/include/avl.h
Dynamic order statisticshttps://github.com/xtaci/algorithms/blob/master/include/dos_tree.h
Red-black treehttps://github.com/xtaci/algorithms/blob/master/include/rbtree.h
Interval treehttps://github.com/xtaci/algorithms/blob/master/include/interval_tree.h
Prefix Tree(Trie)https://github.com/xtaci/algorithms/blob/master/include/trie.h
Suffix Treehttps://github.com/xtaci/algorithms/blob/master/include/suffix_tree.h
B-Treehttps://github.com/xtaci/algorithms/blob/master/include/btree.h
Suffix Arrayhttps://github.com/xtaci/algorithms/blob/master/include/suffix_array.h
Hash by multiplicationhttps://github.com/xtaci/algorithms/blob/master/include/hash_multi.h
Hash tablehttps://github.com/xtaci/algorithms/blob/master/include/hash_table.h
Universal hash functionhttps://github.com/xtaci/algorithms/blob/master/include/universal_hash.h
Perfect hashhttps://github.com/xtaci/algorithms/blob/master/include/perfect_hash.h
Java's string hashhttps://github.com/xtaci/algorithms/blob/master/include/hash_string.h
FNV-1a string hashhttps://github.com/xtaci/algorithms/blob/master/include/hash_string.h
SimHashhttps://github.com/xtaci/algorithms/blob/master/include/simhash.h
Bloom Filterhttps://github.com/xtaci/algorithms/blob/master/include/bloom_filter.h
SHA-1 Message Digest Algorithmhttps://github.com/xtaci/algorithms/blob/master/include/sha1.h
MD5https://github.com/xtaci/algorithms/blob/master/include/md5.h
Base64https://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 treehttps://github.com/xtaci/algorithms/blob/master/include/prim_mst.h
Kruskal MSThttps://github.com/xtaci/algorithms/blob/master/include/kruskal_mst.h
Breadth First Searchhttps://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Depth First Searchhttps://github.com/xtaci/algorithms/blob/master/include/graph_search.h
Dijkstra's algorithmhttps://github.com/xtaci/algorithms/blob/master/include/dijkstra.h
Bellman-Ford algorithmhttps://github.com/xtaci/algorithms/blob/master/include/bellman_ford.h
Edmonds-Karp Maximal Flowhttps://github.com/xtaci/algorithms/blob/master/include/edmonds_karp.h
Push–Relabel algorithmhttps://github.com/xtaci/algorithms/blob/master/include/relabel_to_front.h
Huffman Codinghttps://github.com/xtaci/algorithms/blob/master/include/huffman.h
Word segementationhttps://github.com/xtaci/algorithms/blob/master/include/word_seg.h
A* algorithmhttps://github.com/xtaci/algorithms/blob/master/include/astar.h
K-Meanshttps://github.com/xtaci/algorithms/blob/master/include/k-means.h
Knuth–Morris–Pratt algorithmhttps://github.com/xtaci/algorithms/blob/master/include/kmp.h
Disjoint-Sethttps://github.com/xtaci/algorithms/blob/master/include/disjoint-set.h
8-Queue Problemhttps://github.com/xtaci/algorithms/blob/master/include/8queen.h
Palindromehttps://github.com/xtaci/algorithms/blob/master/include/palindrome.h
LCA using Binary Liftinghttps://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

Algorithms & Data structures in C++& GO ( Lock Free Queue)的更多相关文章

1. 剪短的python数据结构和算法的书《Data Structures and Algorithms Using Python》

   按书上练习完,就可以知道日常的用处啦 #!/usr/bin/env python # -*- coding: utf-8 -*- # learn <<Problem Solving wit ...

2. CSIS 1119B/C Introduction to Data Structures and Algorithms

   CSIS 1119B/C Introduction to Data Structures and Algorithms Programming Assignment TwoDue Date: 18 A ...

3. CSC 172 (Data Structures and Algorithms)

   Project #3 (STREET MAPPING)CSC 172 (Data Structures and Algorithms), Spring 2019,University of Roche ...

4. 学习笔记之Problem Solving with Algorithms and Data Structures using Python

   Problem Solving with Algorithms and Data Structures using Python — Problem Solving with Algorithms a ...

5. [Data Structures and Algorithms - 1] Introduction & Mathematics

   References: 1. Stanford University CS97SI by Jaehyun Park 2. Introduction to Algorithms 3. Kuangbin' ...

6. Basic Data Structures and Algorithms in the Linux Kernel--reference

   http://luisbg.blogalia.com/historias/74062 Thanks to Vijay D'Silva's brilliant answer in cstheory.st ...

7. Choose Concurrency-Friendly Data Structures

   What is a high-performance data structure? To answer that question, we're used to applying normal co ...

8. Persistent Data Structures

   原文链接:http://www.codeproject.com/Articles/9680/Persistent-Data-Structures Introduction When you hear ...

9. 无锁数据结构（Lock-Free Data Structures）

   一个星期前,我写了关于SQL Server里闩锁(Latches)和自旋锁(Spinlocks)的文章.2个同步原语(synchronization primitives)是用来保护SQL Serve ...

随机推荐

1. diy文件系统上创建文件的流程

   [0]README 0.1) source code are from orange's implemention of a os , and for complete code , please v ...

2. DNS--域名系统 随笔

   定义:是一种用于TCP/IP应用程序的分布式数据库.(分布式数据库:指利用高速计算机网络将物理上分散的多个数据存储单元连接起来组成一个逻辑上统一的数据库.分布式数据库的基本思想是将原来集中式数据库中的 ...

3. 常用脚本--查看死锁和阻塞usp_who_lock(转)

   USE [master] GO /****** Object: StoredProcedure [dbo].[sp_who_lock] Script Date: 02/07/2014 11:51:24 ...

4. java中使用js函数

   JDK6已经发布很久了,很早就听过他已经支持脚本语言了,不过一直没有时间尝试,今天偷闲试了一下,感觉不错. javax.script包它是Java新增的操作脚本的工具包, 利用它我们可以对脚本语言进行 ...

5. pip3 Fatal error in launcher: Unable to create process using '"' [转]

   在新环境上安装python的时候又再次遇到了这个情况,这次留意了一下,发现原来的文章有错误的地方,所以来更新一下,应该能解决大部分的问题. 环境是win8,原来只安装了python2.7.后来因为要用 ...

6. 远程服务器上的weblogic项目管理（四）filelock not found错误解决方法

   重启weblogic时如果有残余进程没有kill,启动时便可能会造成filelock not found,文件锁未找到错误,解决方法如下: 删掉Domain下的*.lok文件:(如果不熟悉文件路径推荐 ...

7. 我的Android进阶之旅------>Android利用Sensor(传感器)实现水平仪功能的小例

   这里介绍的水平仪,指的是比较传统的气泡水平仪,在一个透明圆盘内充满液体,液体中留有一个气泡,当一端翘起时,该气泡就会浮向翘起的一端.    利用方向传感器返回的第一个参数,实现了一个指南针小应用. 我 ...

8. vue 组件与传值

   一.表单输入绑定(v-model 指令) 可以用 v-model 指令在表单 <input>.<textarea> 及 <select> 元素上创建双向数据绑定. ...

9. Appium移动自动化配置－ios&安卓

   官网安装参考:https://www.npmjs.com/package/appium Appium安装 1.安装nodejs 2.安装appium iOS侧环境安装 1.安装xcode 2.安装Xc ...

10. manacher小结

    P3805 [模板]manacher算法 题目大意 n个字符组成的字符串,求最长回文串 $O$$($$n^3$$)$ 枚举两端点,暴力往中间搜 $O$$($$n^2$$)$ 枚举回文串终点,暴力往两边 ...