concurrentlyspeaking

[concurrentlyspeaking]

Link to github repository for XCore

Here is the promised link to the github repository containing ConcurrentBitSet (CBS). It is part of the xcore project under the package com.xavax.concurrent. Please be aware that I am still in the process of finishing the refactoring of CBS. If you want the last working version, check out tag 1.1.2. https://github.com/xavax/xcore.git

[concurrentlyspeaking]

Refactoring ConcurrentBitSet

The PMD static code analysis tool can seem overly meticulous, but I've learned it usually pays to heed its advice. Most recently, PMD warnings encouraged me to refactor ConcurrentBitSet (CBS).

CBS manages a dynamic array of segments. Each segment contains an array of pages. Each page encapsulates a portion of a bit set. Segments and pages are created on demand, which is to say the bit set is initially sparse and grows as we attempt to populate regions of the bit set. To facilitate concurrency, we only lock segment map entries when creating new segments, lock segments which making changes to the page map, and lock individual pages when an operation affects bits in that page.

If that all sounds complicated, it is! CBS had no less than five embedded static classes and was littered with @SuppressWarnings annotations, mostly to disable warnings about code complexity. A large part of the code in CBS has little to do with large bit sets and more to do with managing a hierarchy of sparse memory regions that get created on demand.

I have encouraged many clients and teams to use PMD, and I am one who believes in "eating your own dog food", so I decided to refactor CBS. The result was nine classes, many of which will be reusable for implementing other classes similar to CBS. The new classes which are independent of CBS and reusable are:

AbstractPage

AbstractPageableObject (the master coordinator)

AbstractSegment

Constants

Finder (an interface for finder methods and lambdas)

PageContext (used in finder operations)

SegmentMapEntry

The refactored classes that make up CBS are now:

BitSetPage

BitSetSegment

ConcurrentBitSet

While refactoring, I also removed most constants regarding page size, segment size, and overall size, so CBS and AbstractPageableObject are now more configurable. In addition to these classes, the CBS test case was refactored into many more granular test cases. All things considered, it was a big win and worth the effort.

Lessons Learned:

Always heed PMD warnings and suggestions.

If you think a PMD warning is superfluous, see rule #1.

[concurrentlyspeaking]

ConcurrentBitSet

One of my recent projects was developing an alternative to the BitSet class contained in java.util. The initial goal was to support searching for prime numbers using sieves such as the Sieve Of Eratosthenes algorithm. My alternative, called ConcurrentBitSet, supports larger bit sets, supports sparse bit sets, makes efficient use of memory, and reduces thread contention. I’ll be posting a link to the GitHub repository soon. Let me know if you might have a use for this.

[concurrentlyspeaking]

Why Concurrency Matters

Lately almost any microprocessor used in a personal computer has multiple cores. Even laptops use multi-core processors. I am currently composing this post on a Macbook Air with a dual-core intel Core i7, and that’s a laptop that was not top of the line even when new in mid-2012. Some microprocessors now feature  as many as 32 cores, and even some microcontrollers (embedded microprocessors) now have multiple cores. Needless to say multiple cores are here to stay. Each core is almost a complete CPU having it’s own register file(s), execution units, and Level 1 (L1) caches. Some also have private L2 caches. Each core runs one or more threads. About the only things shared are the L3 (and possibly L2) caches, the bus interface, and supervisory features. It’s like the old days of symmetric multiprocessors (SMP) except now it’s all on one chip. The existence of so many computing resources capable of operating in parallel makes it more important than ever that software be designed to take advantage of concurrency. The usual obstacles to concurrency and scalability are:

Thread contention for shared resources that must be locked to prevent access by other threads.

Contention for shared hardware resources such as cache memory and bus bandwidth.

This blog addresses both issues but especially issue #1. How can we develop software that minimizes the number of threads waiting for another thread to unlock a resource, and cores waiting for a thread ready to run.

[concurrentlyspeaking]

Welcome To Concurrently Speaking

Welcome to Concurrently Speaking! Much of my research and development is focused on achieving high levels of concurrency and parallelism. This blog will discuss problems I have encountered, solutions I have developed, and current trends in concurrency.