linkedhashmap.Iterator thread safety #141

New issue

Closed

opened 2020-08-10 09:05:49 +00:00 by juancki · 2 comments

juancki commented

2020-08-10 09:05:49 +00:00

(Migrated from github.com)

It is indicated in the linkedhasmap.go file, the linkedhashmap as a whole, is not thread safe.

In my case, I have:

Th1: A thread with a loop that iterates over with Iterator.
Th2: Another thread that will do Put / Remove operations.

Questions:

Is it possible to do it without adding locks?
Is there anyway to be able to iterate completely over the linked list from first element to the last, without locking completely during the time it takes to loop over?

What I try to avoid is start the loop and have an early finish due to an object being Removed while iterating.

Any help is much appreciated

It is indicated in the [linkedhasmap.go file](https://github.com/emirpasic/gods/blob/7e23495895315fb6a2a939b3f760a233e77dd282/maps/linkedhashmap/linkedhashmap.go#L9), the linkedhashmap as a whole, is not thread safe. In my case, I have: + Th1: A thread with a loop that iterates over with Iterator. + Th2: Another thread that will do Put / Remove operations. Questions: 1. Is it possible to do it without adding locks? 2. Is there anyway to be able to iterate completely over the linked list from first element to the last, without locking completely during the time it takes to loop over? What I try to avoid is start the loop and have an `early finish` due to an object being Removed while iterating. Any help is much appreciated

juancki commented

2020-08-11 08:25:58 +00:00

(Migrated from github.com)

I have been digging further on the lib and found a possible issue with the implementation of doublelinkedlist and its Iterator.

func TestRemovePrevIterator(t *testing.T){
    pool := linkedhasmap.New()
    for i := 0; i < 10; i++{
        pool.Put(i, nil)
    }
    it := pool.Iterator()
    outorder := make([]int,0)
    var j int  = 0;
    for it.Next() {
        if j == 5{ // Remove the first element when 
            pool.Remove(0)
        }
        key := (it.Key()).(int)
        outorder = append(outorder,key)
        if key != j {
	        t.Errorf("Expected key to be %d. Got %d.", j, key)
        }
        j++
    }
    if j != 10 {
	    t.Errorf("Expected iteration size to be 10. Got %d.", j)
    }
}

outorder is [0 1 2 3 4 5 6 7 8] where the element with key 9 is left out.

This is triggered by this if statement where the list is not supposed to be altered while the Iterator is working.

I have been digging further on the lib and found a possible issue with the implementation of doublelinkedlist and its Iterator. ``` func TestRemovePrevIterator(t *testing.T){ pool := linkedhasmap.New() for i := 0; i < 10; i++{ pool.Put(i, nil) } it := pool.Iterator() outorder := make([]int,0) var j int = 0; for it.Next() { if j == 5{ // Remove the first element when pool.Remove(0) } key := (it.Key()).(int) outorder = append(outorder,key) if key != j { t.Errorf("Expected key to be %d. Got %d.", j, key) } j++ } if j != 10 { t.Errorf("Expected iteration size to be 10. Got %d.", j) } } ``` `outorder` is `[0 1 2 3 4 5 6 7 8]` where the element with key `9` is left out. This is triggered by [this if statement](https://github.com/emirpasic/gods/blob/7e23495895315fb6a2a939b3f760a233e77dd282/lists/doublylinkedlist/iterator.go#L30) where the list is not supposed to be altered while the Iterator is working.

emirpasic commented

2022-04-12 03:52:30 +00:00

(Migrated from github.com)

As stated, there is no thread-safety in GoDS at the moment.

Also, removing elements while using iterator can lead to undefined behavior that is not currently tackled by GoDS. Not even locking mechanisms will prevent this. This is why in those cases in other languages you might get something like a ConcurrentAccessException or ConcurrentModificationException when you attempt this (try googling these exceptions to understand why e.g. Java simply throws this exception when you try to do so).

I will personally spend more time meditating if there is any way on doing something different here than what Java did.

As stated, there is no thread-safety in GoDS at the moment. Also, removing elements while using iterator can lead to undefined behavior that is not currently tackled by GoDS. Not even locking mechanisms will prevent this. This is why in those cases in other languages you might get something like a ConcurrentAccessException or ConcurrentModificationException when you attempt this (try googling these exceptions to understand why e.g. Java simply throws this exception when you try to do so). I will personally spend more time meditating if there is any way on doing something different here than what Java did.