Navigating Java Collections

As a followup to a posting a while back two articles about SortedSet and SortedMap made easier and the interfaces they implement, NavigableSet and NavigableMap. They are implemented by skip lists, Concurrent Skipt List Set and Concurrent Skip List Map.

The first article describes in more detail the poll, iteration and LHCF (lower (L), higher (H), ceiling (C) and floor (F)) methods. The later is useful returning elements in a sorted map less than, greather than, less than or equal to and greater than or equal to.

The second article, notes the lack of returning subsets based on values rather than keys: "The disadvantage with NavigableMap is that the subMap method has no provision for returning a map based on a range of values rather than on keys. Therefore, implementing something similar to database views is laborious."

The thing to remember with these skip list data structures is: "Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator."

Also, there's a recent article about being able to hotpatch in Java 6 (which Symantec Visual Cafe was doing back in 1997). Visual Cafe was an excellent IDE in its day, where many IDEs are still catching up although it was behind in things like refactoring.

Announcing Andrae

lca: Andrae Muys on RDF "On the first day of linux.conf.au, I ran into Andrae Muys. He hacks Java and RDF for clients who want semantic web hackery done. I have to admit that early Semantic Web hype put me off: it sounded too much like 1970s AI hype. Andrae was interesting, though, and completely free of the wide-eyed uncritical enthusiasm that characterized a lot of my early RDF engagement."

"Andrae runs the Mulgara project, a Java RDF store. His goal is to be able to deal with 1E13 statements (aka tuples, facts, assertions) in three years. It'll do 1E9 right now, next stop is 1E11. He refers to this goal as "3 Ts: three trillion triples". A consortium is forming around Mulgara to make this happen: if it coalesces, Andrae will be the coder to make it happen."

"The next version of Mulgara, 1.3, will ship in February and have this relational mapping in it. A quick Google search shows a lot of RDF-relational mappings going on, but the list of other mappings he had impressed me: Lucene, RSS, mbox, ID3."

"I think it's time I looked again at the world of RDF. They may yet be doing interesting things. I said as much to Andrae and he replied, "I am an engineer. In the early days it was scientists and logicians in RDF. Now the engineers have arrived, and we just want it to work and to scale." Bold claim! If you have a favourite RDF package or practice, let me know in the comments."

Andrae also announced the paper presented at linux.conf.au. Among other things it references David Wood's paper presented in 2004 "Scaling the Kowari Metastore" ("Makepeace" is a good search term).

Lazy Links

* MKSearch Beta 1 Released - includes web crawler, HTML metadata extractor, and RDF storage using Sesame. Also, MG4J (Managing Gigabytes for Java).
* Open Source Java Application Management: BlueGlue and MyJavaPack. A little different to Ivy (also interesting IvyCruise).
* Concurrency JSR-166 Interest Site includes interesting posts like Java Memory Model versus dotnet Memory Model mentions the forthcoming problems with Java code when multi-core systems are rolled out. Also, Concurrent Skip List Map (coming to Java 6).

A World Without Locks

Wikipedia defines lock-free and wait-free algorithms as allowing "...multiple threads to read and write shared data concurrently without corrupting it. "Lock-free" refers to the fact that a thread cannot lock up: every step it takes brings progress to the system."

LOCK-FREE LINKED LISTS AND SKIP LISTS "Developing a correct and efficient memory management scheme is important to make a data structure practical. Developing such a scheme for a lock-free data structure is often quite a challenging task. The difficulty lies in determining how and when memory that was once occupied by parts of the data structure (e.g. nodes of a linked list), can be freed and reused, so that the processes that might still be accessing those parts are able to complete their operations correctly...We presented new algorithms implementing a lock-free linked list and a lock-free skip list. We proved their correctness and lock-freedom."

Lock-Free Reference Counting The goal of this work, therefore, is to allow programmers to exploit the advantages of GC in designing their lock-free data structure implementations, while avoiding its drawbacks. To this end, we provide a methodology that allows programmers to first solve the easier problem of designing a GC-dependent implementation, and to then apply our methodology in order to achieve a GC-independent one.

An older article: Lock-free Parallel Garbage Collection by Mark&Sweep.

Related to Lock Free Programming.