Iterating List while populating it
Christian Schmidt
I need to fill a container (e.g. a List), while iterating through it in
a parallel thread. If the fill method is too slow, the iterator should
wait until new data is available again.
I've implemented a version without locks that polls until the next item
is available. What would be a better way to achieve this?
Thanks for any advice,
Christian
// Simplified example (fill random and sum up)
class Program {
static void main() {
List<int> list = new List<int>(100000000);
FillDelegate fillDelegate = Fill;
IAsyncResult res = fillDelegate.BeginInvoke(list, list.Capacity,
null, null);
double sum = 0;
for (int i = 0; i < list.Capacity; i++) {
while (i >= list.Count) {
// poll for next item in list
}
sum += list[i];
} // for i
fillDelegate.EndInvoke(res);
} // main
delegate void FillDelegate(List<int> list, int num);
static void Fill(List<int> list, int num) {
Random rng = new Random();
for (int i = 0; i < num; i++) {
int x = rng.Next();
list.Add(x);
} // for i
} // Fill
}
Ben Voigt
"Christian Schmidt" <no...@locom.de> wrote in message
news:uU1%23bVczG...@TK2MSFTNGP06.phx.gbl...
> Hi all,
> I need to fill a container (e.g. a List), while iterating through it in a
> parallel thread. If the fill method is too slow, the iterator should wait
> until new data is available again.
> I've implemented a version without locks that polls until the next item is
> available. What would be a better way to achieve this?
An auto-reset event, set after you add items to the list (every n-th item).
When the iterator hits the end of what's available, it uses event.WaitOne to
enter an efficient sleep state.
Christian Schmidt
>> I need to fill a container (e.g. a List), while iterating through it in a
>> parallel thread. If the fill method is too slow, the iterator should wait
>> until new data is available again.
>> I've implemented a version without locks that polls until the next item is
>> available. What would be a better way to achieve this?
>
> An auto-reset event, set after you add items to the list (every n-th item).
> When the iterator hits the end of what's available, it uses event.WaitOne to
> enter an efficient sleep state.
Thanks. Works great! I only use AutoResetEvent.Set() every 1000th add.
These events seem to eat a lot of performance... It costs 2 seconds
compared to the 7 seconds for the polling variant.
If the initial capacity of the list has exceeded and a resizing occurs,
can the enumerator thread be hurt by this?
I fear yes :-(
Does anyone have an idea how to pause the enumerator during resizing?
Or do I have to change to a LinkedList?
Cheers,
Christian
Vadym Stetsyak
You wrote on Fri, 01 Sep 2006 23:24:05 +0200:
CS> Does anyone have an idea how to pause the enumerator during resizing?
CS> Or do I have to change to a LinkedList?
Yes, since changing capacity will result in internal array copy.
LinkedList<T> should suit you better.
--
Regards, Vadym Stetsyak.
Blog: http://vadmyst.blogspot.com
Greg Young
including http://www.boyet.com/Articles/LockfreeFreeList.html
Cheers,
Greg
"Vadym Stetsyak" <vad...@ukr.net> wrote in message
news:u1e63Snz...@TK2MSFTNGP03.phx.gbl...
Joe Seigh
> There are a few lock free linked list implementations laying around ...
> including http://www.boyet.com/Articles/LockfreeFreeList.html
>
That code seems to be subject to the ABA problem. Having GC doesn't
solve that problem for you.
>>Hello, Christian!
>>You wrote on Fri, 01 Sep 2006 23:24:05 +0200:
>>
>>CS> Does anyone have an idea how to pause the enumerator during resizing?
>>CS> Or do I have to change to a LinkedList?
>>
Take a look at java.util.concurrent.ConcurrentLinkedQueue. The techniques
should be portable provided you have the right stuff in your target
environment. There's also a CopyOnWriteArrayList if you're really fond
of arrays.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Christian Schmidt
> Take a look at java.util.concurrent.ConcurrentLinkedQueue. The techniques
> should be portable provided you have the right stuff in your target
> environment. There's also a CopyOnWriteArrayList if you're really fond
> of arrays.
If I can ensure that my array never gets resized I shouldn't have a
problem with one thread adding and another reading and writing (not
adding/deleting) items, right?
So if I organize my container as a linked list of arrays, i.e. if an
array is filled to it's capacity I add a new one to the linked list, I
shouldn't run into troubles, right?
The only thing I need is an event signaling my reader/writer that new
data is available.
Christian
Joe Seigh
You should be able to allocate a new array and atomically replace the old
array with it when it becomes full. GC will delete the old array when
previous readers are finished with it. That's what copy on write is basically.
Christian Schmidt
> You should be able to allocate a new array and atomically replace the old
> array with it when it becomes full. GC will delete the old array when
> previous readers are finished with it. That's what copy on write is
> basically.
Do I understand correctly: Given two threads, one adding, one reading
_and_ writing to an array, resizing is an atomic instruction, i.e. it
cannot happen that data to the "old" array is written, while the content
of the old one is copied to the new one?
Thanks,
Christian
Joe Seigh
There are two data classes here. The collection class, i.e. a list or an
array, and that of the objects which comprise the collection. It's the
collection class that's lock-free. If you want to access the objects
read/write then you have to take additional measures or precautions to
avoid multiple uncoordinated instances of these objects. One is to make
the collection one of references to objects which will work if you're
accessing the objects in situ. If you're doing copy on write for the objects,
you need to add an extra level of indirection, i.e. a collection of references
to references of objects. Copy on write relies on having single serialization
points to modify the objects with. This begs the question of how you're going
to coordinate the copy on writes though.