Quantcast

EventListIterator performance

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

EventListIterator performance

robeden
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

hbrands
Administrator
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

hbrands
Administrator
But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

robeden
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

hbrands
Administrator
I'd say if nobody is against it, go for it.

The question is, if we should keep the old EventListIterator,
so that someone who currently relies on its "special features" (see for example IteratorTest#testIterateWithExternalRemove)
can still make use of it?
I'm +1 for that, at least in 1.x versions.

Holger


2013/12/23 Rob Eden <[hidden email]>
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob




Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

robeden
I worked on this a bit a couple weeks back. The main problem is there is no facility for tracking concurrent modifications. For example, the built-in JUC implementations (ArrayList, etc.) have an integer counter to track when modifications are made. If the counter doesn’t match what the iterator expects, it knows a change has been made and throws a ConcurrentModificationException. We don’t currently have anything like that. It’s not strictly required by the interface, but I think we would want that behavior. Adding the behavior to BasicEventList is no big deal, but I’d have to look to see what impact there will be on subclasses.

However, our iterator() implementation (SimpleIterator) doesn’t deal with this either. So now that I think about it, maybe I’ll just correct the speed issues with the ListIterator and do ConcurrentModificationException handling separately.


Regarding someone who relies on the behavior, I don’t have a problem with leaving it if there’s no impact to underlying stuff (which I don’t think there would be). However, that can lead to library bloat with stuff people really shouldn’t use. Exhibit A: all the deprecated crud in the standard Java API.

Rob


On Jan 19, 2014, at 9:47 AM, Holger Brands <[hidden email]> wrote:

I'd say if nobody is against it, go for it.

The question is, if we should keep the old EventListIterator,
so that someone who currently relies on its "special features" (see for example IteratorTest#testIterateWithExternalRemove)
can still make use of it?
I'm +1 for that, at least in 1.x versions.

Holger


2013/12/23 Rob Eden <[hidden email]>
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob





Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

hbrands
Administrator
With regard to concurrent modification:
as we discussed earlier, if the Glazed Lists API is used correctly, there should be no ConcurrentModificationException:
While iterating over the list you should hold the read lock. A modifying thread should try to aquire a write lock first.
The only use case that would not be supported is start iterating some list elements, stop, remove and/or add elements, then continue iterating - all in the same thread.
But that's a rare case I suppose. For that, the old EventListiterator could be used:

EventListiterator oldIter = new EventListiterator(myList, 0);
// use oldIter

As this class is located inside the **/impl package it's not part of the public API.
In a 2.0 version, if we ever get there, we could remove this and other deprecated stuff.

Holger


2014/1/20 Rob Eden <[hidden email]>
I worked on this a bit a couple weeks back. The main problem is there is no facility for tracking concurrent modifications. For example, the built-in JUC implementations (ArrayList, etc.) have an integer counter to track when modifications are made. If the counter doesn’t match what the iterator expects, it knows a change has been made and throws a ConcurrentModificationException. We don’t currently have anything like that. It’s not strictly required by the interface, but I think we would want that behavior. Adding the behavior to BasicEventList is no big deal, but I’d have to look to see what impact there will be on subclasses.

However, our iterator() implementation (SimpleIterator) doesn’t deal with this either. So now that I think about it, maybe I’ll just correct the speed issues with the ListIterator and do ConcurrentModificationException handling separately.


Regarding someone who relies on the behavior, I don’t have a problem with leaving it if there’s no impact to underlying stuff (which I don’t think there would be). However, that can lead to library bloat with stuff people really shouldn’t use. Exhibit A: all the deprecated crud in the standard Java API.

Rob


On Jan 19, 2014, at 9:47 AM, Holger Brands <[hidden email]> wrote:

I'd say if nobody is against it, go for it.

The question is, if we should keep the old EventListIterator,
so that someone who currently relies on its "special features" (see for example IteratorTest#testIterateWithExternalRemove)
can still make use of it?
I'm +1 for that, at least in 1.x versions.

Holger


2013/12/23 Rob Eden <[hidden email]>
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob






Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

robeden
It is actually possible to modify the list in a way that would generate a ConcurrentModificationException without multiple threads. If you, for example, remove or add an element while hanging on to an iterator. It’s less common, but I’ve hit that case before.

Rob

On Jan 21, 2014, at 3:40 PM, Holger Brands <[hidden email]> wrote:

With regard to concurrent modification:
as we discussed earlier, if the Glazed Lists API is used correctly, there should be no ConcurrentModificationException:
While iterating over the list you should hold the read lock. A modifying thread should try to aquire a write lock first.
The only use case that would not be supported is start iterating some list elements, stop, remove and/or add elements, then continue iterating - all in the same thread.
But that's a rare case I suppose. For that, the old EventListiterator could be used:

EventListiterator oldIter = new EventListiterator(myList, 0);
// use oldIter

As this class is located inside the **/impl package it's not part of the public API.
In a 2.0 version, if we ever get there, we could remove this and other deprecated stuff.

Holger


2014/1/20 Rob Eden <[hidden email]>
I worked on this a bit a couple weeks back. The main problem is there is no facility for tracking concurrent modifications. For example, the built-in JUC implementations (ArrayList, etc.) have an integer counter to track when modifications are made. If the counter doesn’t match what the iterator expects, it knows a change has been made and throws a ConcurrentModificationException. We don’t currently have anything like that. It’s not strictly required by the interface, but I think we would want that behavior. Adding the behavior to BasicEventList is no big deal, but I’d have to look to see what impact there will be on subclasses.

However, our iterator() implementation (SimpleIterator) doesn’t deal with this either. So now that I think about it, maybe I’ll just correct the speed issues with the ListIterator and do ConcurrentModificationException handling separately.


Regarding someone who relies on the behavior, I don’t have a problem with leaving it if there’s no impact to underlying stuff (which I don’t think there would be). However, that can lead to library bloat with stuff people really shouldn’t use. Exhibit A: all the deprecated crud in the standard Java API.

Rob


On Jan 19, 2014, at 9:47 AM, Holger Brands <[hidden email]> wrote:

I'd say if nobody is against it, go for it.

The question is, if we should keep the old EventListIterator,
so that someone who currently relies on its "special features" (see for example IteratorTest#testIterateWithExternalRemove)
can still make use of it?
I'm +1 for that, at least in 1.x versions.

Holger


2013/12/23 Rob Eden <[hidden email]>
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob







Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

hbrands
Administrator
I think we mean the same thing when I said:
"The only use case that would not be supported is start iterating some list elements, stop, remove and/or add elements, then continue iterating - all in the same thread."
;-)

Holger


2014/1/21 Rob Eden <[hidden email]>
It is actually possible to modify the list in a way that would generate a ConcurrentModificationException without multiple threads. If you, for example, remove or add an element while hanging on to an iterator. It’s less common, but I’ve hit that case before.

Rob

On Jan 21, 2014, at 3:40 PM, Holger Brands <[hidden email]> wrote:

With regard to concurrent modification:
as we discussed earlier, if the Glazed Lists API is used correctly, there should be no ConcurrentModificationException:
While iterating over the list you should hold the read lock. A modifying thread should try to aquire a write lock first.
The only use case that would not be supported is start iterating some list elements, stop, remove and/or add elements, then continue iterating - all in the same thread.
But that's a rare case I suppose. For that, the old EventListiterator could be used:

EventListiterator oldIter = new EventListiterator(myList, 0);
// use oldIter

As this class is located inside the **/impl package it's not part of the public API.
In a 2.0 version, if we ever get there, we could remove this and other deprecated stuff.

Holger


2014/1/20 Rob Eden <[hidden email]>
I worked on this a bit a couple weeks back. The main problem is there is no facility for tracking concurrent modifications. For example, the built-in JUC implementations (ArrayList, etc.) have an integer counter to track when modifications are made. If the counter doesn’t match what the iterator expects, it knows a change has been made and throws a ConcurrentModificationException. We don’t currently have anything like that. It’s not strictly required by the interface, but I think we would want that behavior. Adding the behavior to BasicEventList is no big deal, but I’d have to look to see what impact there will be on subclasses.

However, our iterator() implementation (SimpleIterator) doesn’t deal with this either. So now that I think about it, maybe I’ll just correct the speed issues with the ListIterator and do ConcurrentModificationException handling separately.


Regarding someone who relies on the behavior, I don’t have a problem with leaving it if there’s no impact to underlying stuff (which I don’t think there would be). However, that can lead to library bloat with stuff people really shouldn’t use. Exhibit A: all the deprecated crud in the standard Java API.

Rob


On Jan 19, 2014, at 9:47 AM, Holger Brands <[hidden email]> wrote:

I'd say if nobody is against it, go for it.

The question is, if we should keep the old EventListIterator,
so that someone who currently relies on its "special features" (see for example IteratorTest#testIterateWithExternalRemove)
can still make use of it?
I'm +1 for that, at least in 1.x versions.

Holger


2013/12/23 Rob Eden <[hidden email]>
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob








Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: EventListIterator performance

robeden
Ahem… yes. Good point. (Sorry about that.) :-)

Rob

On Jan 22, 2014, at 12:45 PM, Holger Brands <[hidden email]> wrote:

I think we mean the same thing when I said:
"The only use case that would not be supported is start iterating some list elements, stop, remove and/or add elements, then continue iterating - all in the same thread."
;-)

Holger


2014/1/21 Rob Eden <[hidden email]>
It is actually possible to modify the list in a way that would generate a ConcurrentModificationException without multiple threads. If you, for example, remove or add an element while hanging on to an iterator. It’s less common, but I’ve hit that case before.

Rob

On Jan 21, 2014, at 3:40 PM, Holger Brands <[hidden email]> wrote:

With regard to concurrent modification:
as we discussed earlier, if the Glazed Lists API is used correctly, there should be no ConcurrentModificationException:
While iterating over the list you should hold the read lock. A modifying thread should try to aquire a write lock first.
The only use case that would not be supported is start iterating some list elements, stop, remove and/or add elements, then continue iterating - all in the same thread.
But that's a rare case I suppose. For that, the old EventListiterator could be used:

EventListiterator oldIter = new EventListiterator(myList, 0);
// use oldIter

As this class is located inside the **/impl package it's not part of the public API.
In a 2.0 version, if we ever get there, we could remove this and other deprecated stuff.

Holger


2014/1/20 Rob Eden <[hidden email]>
I worked on this a bit a couple weeks back. The main problem is there is no facility for tracking concurrent modifications. For example, the built-in JUC implementations (ArrayList, etc.) have an integer counter to track when modifications are made. If the counter doesn’t match what the iterator expects, it knows a change has been made and throws a ConcurrentModificationException. We don’t currently have anything like that. It’s not strictly required by the interface, but I think we would want that behavior. Adding the behavior to BasicEventList is no big deal, but I’d have to look to see what impact there will be on subclasses.

However, our iterator() implementation (SimpleIterator) doesn’t deal with this either. So now that I think about it, maybe I’ll just correct the speed issues with the ListIterator and do ConcurrentModificationException handling separately.


Regarding someone who relies on the behavior, I don’t have a problem with leaving it if there’s no impact to underlying stuff (which I don’t think there would be). However, that can lead to library bloat with stuff people really shouldn’t use. Exhibit A: all the deprecated crud in the standard Java API.

Rob


On Jan 19, 2014, at 9:47 AM, Holger Brands <[hidden email]> wrote:

I'd say if nobody is against it, go for it.

The question is, if we should keep the old EventListIterator,
so that someone who currently relies on its "special features" (see for example IteratorTest#testIterateWithExternalRemove)
can still make use of it?
I'm +1 for that, at least in 1.x versions.

Holger


2013/12/23 Rob Eden <[hidden email]>
I can work on this change.

Rob

On Dec 22, 2013, at 10:08 AM, Holger Brands <[hidden email]> wrote:

But if we do this, we need to adapt the internal indexes of the iterator, when the list is modified through the list iterator, of course...

Holger


2013/12/22 Holger Brands <[hidden email]>
I'm with Rob here.
When iterating over an EventList, the caller has to hold a read lock, so no modifications are possible for well behaving writers (trying to get a write lock first).
If you read and write from different threads without proper locking you're out of luck.

I just made a small test myself. A put of 10000 elements takes round about 1200 ms. on my machine.
With fixing 2.) above I'm down to 45 ms!

I think if we fix 2.), 1.) becomes obsolete. Only BasicEventList, FunctionList, SequenceLis and the threadproxy lists implement RandomAccess anyway.
I don't gain any notable speedup in my test anymore.

So, I vote for fixing 2.) and documenting the change here:
http://www.glazedlists.com/documentation/upgrade-from-19-to-110

Holger



2013/12/18 Rob Eden <[hidden email]>
Hi guys -

Today I rediscovered an issue that has bitten me in the past: EventListIterator is horrendously inefficient. The problem is it registers as a ListEventListener to the root list. This causes a lot of work to be done setting up the publisher and such.

The place this is really seen is when using a FunctionListMap (via GlazedLists.syncEventListToMap). The “put” method uses a ListIterator to loop over the source map to find the right slot to replace. This makes the map exceedingly slow.

To work around the issue in my code I overrode the put method and changed this:

        // try to find the old value by identity in the valueList and replace it
        for (ListIterator<V> i = valueList.listIterator(); i.hasNext();) {
            if (i.next() == toReplace) {
                i.set(value);
                return toReplace;
            }
        }

...to this:

// try to find the old value by identity in the valueList and replace it
for ( int i = 0; i < source.size(); i++ ) {
V index_value = source.get( i );
if ( index_value == toReplace ) {
source.set( i, value );
return toReplace;
}
}

Doing so resulting in almost 2 orders of magnitude speed increase (10+ sec to ~200 ms) in our use case where we’re doing a “significant” number of puts (a couple thousand, I believe).

I see two possible fixes:
  1. FunctionListMap is using an overly heavy-weight object for RandomAccess lists. We should probably check for “implementation” of that interface and use a simple “for” loop in that case.
  2. I don’t see why EventListIterator should listen for list events. It’s trying to be really smart and follow concurrent list changes, but surely that’s a Really Bad Thing(TM). That would mean performing modifications and reads on a list without proper locking, which we wouldn’t support with any of the built-in lists. It seems to me that it’s just way over-engineered.

Rob









Loading...