• Post Reply Bookmark Topic Watch Topic
  • New Topic

Concurrent Linked Lists  RSS feed

 
Winston Gutkowski
Bartender
Posts: 10574
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:This is also true of a doubly-linked list, but the mechanism is much more complex.

Actually, looking back at this statement, I'm not at all sure now that it is true - at least not with classic nested synchronized blocks - in fact I now suspect it's not .

TBH, I'm not even sure about single-linked lists but, from my database experience, it "feels" right, providing certain rules are followed (which can be built into the list class itself). Maybe someone can help me out.

I've moved this inquiry to a new thread because, as usual, I've gone off at a tangent from the post (and thread) that spawned it, which can be found here.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not sure what the question is. Are doubly linked lists much harder to make thread safe? I don't think so. What makes them different from singly linked lists, with the exception of having one more field for a node?
 
Winston Gutkowski
Bartender
Posts: 10574
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:I'm not sure what the question is. Are doubly linked lists much harder to make thread safe? I don't think so. What makes them different from singly linked lists, with the exception of having one more field for a node?

If you lock the entire structure for updates, none; but I'm pretty sure that single-direction linked lists only need to lock nodes. And if they're always locked in the same order, then you can't get a deadlock. In a double-linked list you have 3 affected nodes, and I don't think they can be locked in such a way as to prevent deadlock.

Winston
 
Rodion Gork
Ranch Hand
Posts: 47
1
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But it is anyway quite unclear how this structure can work and what for it can be used in concurrent context.

Seek operations on linked list are quite time consuming and it does not seem a good idea to use them in concurrency at all. While concurrent access to head / end could be easily governed by a single sinchronization.

The only "more complicated" use-case I can think of - if several threads have used iterators to seek to certain points of the list and start adding or removing items at these points. And here we theoretically may get into very curious problems. But I have no idea what for we may want to use such processing...

I know java has concurrent skip lists, but for sorted map/set implementation based on them.
 
Winston Gutkowski
Bartender
Posts: 10574
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rodion Gork wrote:But it is anyway quite unclear how this structure can work and what for it can be used in concurrent context...

You're quite right Rodion, And I kind of came to that conclusion myself independently.

The reason for my question is that linked lists appear to offer far more scope for limited (or optimistic) locking than lists based on arrays. And there's no doubt in my mind that this is, in fact, true, because a linked list can theoretically be updated safely by locking only the Nodes affected by the update rather than the entire structure - which I would categorise as "aggressive" locking.

However, the way that (or what) you lock is governed by the requirements of the structure that holds the Nodes. There may be some gains to be had from locking Nodes atomically (ie, synchronized methods on one or two Nodes, called in a specific sequence), but it's only the structure that contains those Nodes that can decide on a proper locking strategy.

Hope I've made myself a bit clearer ... I suspect not.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Would that be useful? If optimistic locking is going to make a difference, it's when different nodes of the list are accessed concurrently. This to me implies random access, for which a linked list would be a poor structure in the first place.
 
Winston Gutkowski
Bartender
Posts: 10574
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Would that be useful? If optimistic locking is going to make a difference, it's when different nodes of the list are accessed concurrently. This to me implies random access, for which a linked list would be a poor structure in the first place.

Sorry for delay in replying, but I had to think about your post ...hard.

And I'm not sure you're correct:
What about concurrent cursors (or Iterators) of a linked List? These can be (and in the case of Java's implementations ARE) "weakly" consistent in the face of concurrent update - ie, they will only return nodes that were part of the List at the time of arrival. And the great thing about linked lists is that once you know where you want to update, the updates themselves are extremely fast.

You also have structures like ConcurrentSkipListSet (and -Map) which are random and heavily "linked" both down and "sideways", probably because of the reasons already mentioned - ie, update to any of the internal lists doesn't disturb any concurrent traversals for the purpose of finding elements. They are also highly concurrent.

However, I'm starting to wonder if linked lists as a structure really are inherently "friendlier" to concurrent updates - particularly deletes. I suspect they are, but I'm clearly going to have to do more research on the subject before I can be too categorical about it.

Thanks a lot for your post though.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!