Projects

concurrentlinkedhashmap

A high performance version of java.util.LinkedHashMap for use as a software cache. DesignA concurrent linked list runs through a ConcurrentHashMap to provide eviction ordering. Supports insertion and access ordered eviction policies (FIFO, LRU, and Second Chance). StatusTesting new algorithm. ... [More] Original AlgorithmThe Sept. 2008 jar contains the initial version, which uses a concurrent deque that runs through a ConcurrentHashMap. For simplicity, the implementation used a lazy removal strategy to allow focusing on validating the doubly linked list. A backtracking eager removal strategy was initially prototyped, but not adopted due to concerns over management of the data races. According to Greg's benchmarks, he found up to a 92.5x performance gain when compared to the previous version of Ehcache (v1.5). Note: A rare race condition was uncovered by Greg Luck (Ehcache). This algorithm is deprecated. Current AlgorithmThe design document describes a newer approach based on per-node spin-locks. Note: The algorithm needs further testing and is not deemed production ready. It is functional under concurrent tests, but needs additional load testing to assert correctness. Production VersionDue to popular demand and accidental usages in production environments, a certified production-ready version is provided for download. This version is will provide the desired performance without using experimental code intended for personal education. The modifications are documented outside of the repository. FutureAfter the current algorithm is released, work will begin towards maturing it into a lock-free algorithm. A lock-free algorithm is non-blocking, maintains the list in an acceptable but not always perfect state, and coerces to the desired state. This changes the thought process of trying to block concurrent operations from corrupting shared state to making them work together to arrive at a final state. LicenseThe algorithms and code are provided as-is under the APL-2. They were built primarily for fun and as a hobby project. The main motivation was that the puzzle of how to implement a concurrent linked hashmap sounded quite enjoyable (and educational). To figure it out for myself, I avoided venturing into certain academic literature. While this may make progress slower, it allows me to understand the algorithms rather than copying them. That said, others are free to use this structure as a template and make the necessary changes to implement one of those algorithms. [Less]

d-phoenix

基于 D 2.0 + druntime，编译器推荐 DMD 2.0 最新版本(注意:目前 d-phoenix 仅兼容 Windows ，其他平台暂未列入计划中)。 初始版本 0.5.1 推荐使用 DMD 2.019，因为这个版本还没有移植到 druntime 上。 如果想要体验 druntime ，请使用 DMD 2.021 或 ... [More] DMD 2.0 最新版本并 Check out 最新版本。 老实说，我也不知道这个项目会做到什么地步。 现在已经完成常见数据结构，并发布初始版本 0.5.1。 并行/并发这块设计还没想好，可能会对 Thread 有些增改。 已经有了些概念，而且也做了些封装。 在做完数据结构这块，接下来会做一些国际化的准备。 因为线程是带有区域信息的，先做这些对以后的工作能提供莫大的便利。 目前在线程提供支持方面，仅仅实现 Windows 平台，并且优先考虑支持 Windows 平台，不过同时也保留了其他平台实现的接口，且有些函数已经兼容 Linux平台。 数据结构是平台独立的。 关于性能：只举一例，当年 STL 出世的时候，着实嘲笑了 C 库的 qsort 一把。本人也很自豪的说，d-phoenix 项目的排序功能性能完全可以媲美 STL 的 sort 函数。不客气的说，只高不低，哇哈哈~ Change Log: 2008-11-24 增加 API 文档(简体中文)。 2008-11-20 释出初始版本 0.5.1。这个版本中完成了大部分常见数据结构，以及部分编解码( 全部几种在 Unicode 上)和线程操作 API。 此外，还完成了 C Runtime 封装和基础函数功能。 详情请参见 Release Note 。 [Less]

nbds

C implementations of several scalable non-blocking data structures for x86 and x86-64. StatusOverall the package is pre-alpha. It is still under development. The skiplist is beta. There are no known bugs and it is feature complete. The hashtable is alpha. It has not been tuned for memory usage. ... [More] There are no known bugs and it is feature complete. The lock-free memory management and runtime support is pre-alpha. It is not feature complete. The transactional system is a toy implementation for now. Developers will find it mostly interesting for the concepts. Tested under Linux with gcc 4.1-4.3 with Ubuntu 8.10. Probably works on Mac OS 10.5 with gcc 4.1-4.2. NewsVersion 0.4.3 - 4/7/09 - bug fix in hash table iterator. bug fix for OS X in memory manager. add performance tests to measure steady state behavior. major performance tuning for skiplist. Version 0.4.2 - 1/18/09 - Linux support, gcc 4.1-4.3. Fixed major bug in skiplist. Memory manager re-write. Version 0.4.1 - 12/16/08 - support for 32 bit x86. iterators for hashtable, list, and skiplist Version 0.4.0 - 12/10/08 - lock-free transactional map Version 0.3.2 - 12/3/08 - support for arbitrary key types, with a fast path for integer keys. Version 0.3.1 - 11/29/08 - list and skiplist now support update operations and string type keys Version 0.3.0 - 11/23/08 - lock-free skiplist Version 0.2.1 - 11/15/08 - Started work on making the hash table transactional. Bug fixes too. Version 0.2.0 - 11/07/08 - Initial public release What's InsideLock-Free Transactional MapLock-free transactional key-value store. The transactional semantics follow database-style snapshot isolation using multi-version concurrency control. With snapshot isolation updates are versioned. Transactions are isolated from changes after they begin. They always see a consistent view of the structure. Conversely, a transaction's updates are invisible to all other transactions until it commits. When a transaction tries to commit its writes are checked for conflicts against any committed concurrent transactions. If the system detects a conflict then the committing transaction rolls back. Otherwise its updates become visible to future transactions. Lock-Free SkiplistThe lock-free skiplist data structure created by Maurice Herlihy, Yossi Lev, and Nir Shavit. See Herlihy's and Shavit's book "The Art of Multiprocessor Programming" and Kir Fraser's dissertation "Practical Lock Freedom" http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916/ http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf I've generalized the data structure to support update operations like set() and CAS() in addition to the normal add() and remove() operations, while preserving the lock-free property and linearizability. Lock-Free HashtableCliff Click's lock-free hash table from http://www.azulsystems.com/events/javaone_2008/2008_CodingNonBlock.pdf http://sourceforge.net/projects/high-scale-lib LicenseAll code in this project is public domain, except the unit test framework (which was not written by me). The hash function (murmur hash 2.0) is not written by me, but is public domain. ContactFeel free to email me with comments or questions: jdybnis at gmail. [Less]