CODEWITHSUNDEEP
javadata-structuresconcurrency
user1018513
user1018513

Reputation: 1682

Directly accessible data structure Java

I have the following situation:

  1. A data structure which can only ever be extended ( I only ever add things in the tail)
  2. I need to be able to keep track of which elements I have already seen (I have an index, and ideally I want to be able to start traversing the list again from this particular element)
  3. I would like the reads to never be blocking, and the addition of the new element to only ever lock the tail of the queue rather than the whole queue

This is a structure which is heavily modified by multiple threads.

What would be the best data structure for this?

ArrayList. This would be ideal to be able to directly access the last element seen using the index, but it leads to concurrent modifications exceptions. i could make it synchronised, but would like to avoid locking (or any locking apart from the very last element, as it is the only one where there might be concurrent writes to add new elements)

ConcurrentLinkedQueue. This would solve my concurrency problem, but has the problem that I would have to store the current position of the iteration rather than an integer index. This has the problem that it returns a weakly consistent iterator which is not guaranteed to return new objects that have been added to the list since the iterator was created (source: javadoc)

ConcurrentHashMap with index as keys. This has the benefit that I can access data corresponding to the correct index directly, but has the issue that there isn't a "getNext" operator that will allow me to efficiently traverse the elements from index, to index + 1, etc

Vectors This would solve most of my problems in allowing something that won't throw concurrent modification exceptions and allow for direct accessing. However, given all methods are synchronised, the performance is poor compared to arraylists. Given that I only ever want to extend the structure, and not insert records in the middle, I'm reluctant to go for this heavy weight solution, where reads also suffer a performance hit (whereas, given my usecase, the index of an element never actually changes, so there's no need to synchronise reads that are not the tail)

Custom data structure: keep an array of the objects I want to store and a pointer to the tail of this array (the last element set), when inserting a new object, lock the tail and the object pointed to by the tail. When the object exceeds its current size, to a locking resize operation.

What would be the best strategy/ any other more efficient implementation?

Upvotes: 42

Views: 2332

Answers (8)

Xaltar
Xaltar

Reputation: 1716

The CopyOnWriteArrayList structure could solve your problem (java.util.concurrent).

  • CopyOnWriteArrayLists is thread-safe because all mutative operations are implemented by creating a copy of the list.

  • The problem of ConcurrentModificationException is avoided because the array doesn't change while iterated. The so called snapshot style iterator uses a reference to the state of the array when the iterator was created.

  • If you have much more reads than writes, use CopyOnWriteArrayList, otherwise use Vector.

  • Vector introduces a small synchronization delay for each operation, when CopyOnWriteArrayList has a longer delay for write (due to copying) but no delay for reads.

  • Vector requires explicit synchronization when you are iterating it (so write operations can't be executed at the same time), CopyOnWriteArrayList doesn't.

Upvotes: 11

barclay
barclay

Reputation: 4552

Do you have to use a single data structure? What if you used two - one for the "active" portion of the list, and one for the "items you have seen" list? You could use a Vector for the "active" portion and some kind of manager that periodically moves items to the "items you have seen" list.

Upvotes: 0

Eugene
Eugene

Reputation: 120858

This very much sounds like you would need a distruptor or in simple words lock free queue. I wish I could add an example here, but I only started to work on it yesterday. I could also tell you how it works, or you can read a far better explanation here:

The general idea is that this is completely lock free, it only uses the CAS registers (in java AtomicXXX). I simply fell in love with the idea.

LMAX

Upvotes: 4

OliverS
OliverS

Reputation: 1271

Looking into this I came to the same solution as @MissingNumber.

Use a ConcurrentHashMap as backing data structure:

  • non-blocking-reads
  • thread-safe appending

To add the random access by index use an AtomicInteger to maintain the index and put it as the key to retrieve the map values.

public class ConcurrentListMap {

  private final ConcurrentHashMap<Integer, Object> backingMap;
  private final AtomicInteger index;

  public ConcurrentListMap() {
    backingMap = new ConcurrentHashMap();
    index = new AtomicInteger(0);
  }

  public int append(final Object value) {
    final int newIndex = index.incrementAndGet();
    backingMap.put(newIndex, value);
    return newIndex;
  }

  public Object get(final int entry) {
    return backingMap.get(entry);
  }

  public int getTailIndex() {
    return index.get();
  }
}

Upvotes: 4

Mikkel L&#248;kke
Mikkel L&#248;kke

Reputation: 3749

I'm going to offer up ConcurrentSkipListSet, because:

1) It's concurrent.

2) It's a Set.

3) It's also NavigableSet, thus also a SortedSet.

This gives you a lot of flexibility, much of which you probably won't need. But apart from "You can't add items that already exist" (which I don't know if is a problem, or a boon) it seems to satisfy all your requirements.

Upvotes: 0

MissingNumber
MissingNumber

Reputation: 1182

ConcurrentHashMap with index as keys could solve your problem , but you need to do litte more work to do so ..

Like following Pseudo Code .

Map<Integer , ConfiguredObject > myMap = new ConcurrentHashMap<Integer,ConfiguredObject >();

class ConfiguredObject 
{
   YourObject Object;// the object which you want to map for map[key];
   ConfiguredObject Next;//the object which you want to map for map[key+1];
   ConfiguredObject Previous;//the object which you want to map for map[key-1];
   YourObject NextObject;
   YourObject PrevObject;
}

So this should solve all your problems.

Concurrency Framework takes care .

Indexing Keys are your indexes .

Iteration , with this code if you have index you can use 

myMap.get(key).Next ;
myMap.get(key).Previous ;

All you need to do is define configurable object and write constructor accordingly with care .

Hope this help you.

Upvotes: 1

Markov Unchained
Markov Unchained

Reputation: 159

As sk2212 said, I think that java.util.Vector meets your three points.

  1. Vectors can be extended by using the method add, which adds elements at the end of the list.
  2. Vectors have the method get(index) to retrieve a concrete element at specific index.
  3. Vectors are thread-safe: java Vector and thread safety http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

Upvotes: 1

DeadlyJesus
DeadlyJesus

Reputation: 1533

ArrayList. This would be ideal to be able to directly access the last element seen using the index, but it leads to concurrent modifications exceptions. i could make it synchronised, but would like to avoid locking (or any locking apart from the very last element, as it is the only one where there might be concurrent writes to add new elements)

You could use a temporary List to put the objects to be added and when the read thing unblock, you add tmpList's content to the ArrayList.

Upvotes: 0

Related Questions