You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@uima.apache.org by Richard Eckart de Castilho <re...@apache.org> on 2016/01/07 00:18:26 UTC
Performance and ALLOW_DUP_ADD_TO_INDEXES
>> I am starting to get suspicious of global flags for backwards compatibility.
>> E.g. since ALLOW_DUP_ADD_TO_INDEXES was introduced, we have people complaining
>> about a performance drop. ALLOW_DUP_ADD_TO_INDEXES can only be enabled/disabled
>> globally, but not specifically for individual indexes. Neither can it be
>> temporarily disabled, e.g. during deserialization or other bulk operations.
>> I wonder if local getters/setters or ThreadLocal variables initialized by
>> a global setting wouldn't be a more appropriate option.
>
> I was unaware of the performance issue; I may have missed some emails... Can
> you say how significant it is? If there were no performance issue, would the
> additional function be needed?
>
> I assume the performance drop is when duplicates are not allowed (the new
> default), and some users are wanting to restore the previous performance by
> turning on ALLOW_DUP .... Is this correct?
I didn't track it in detail, but apparently, some time back Peter noticed a
drop in XMI deserialization performance and more recently also in compressed
binary CAS deserialization. Some time later, I had a person claiming in
private mail that deserialization was O(n^2) with respect to the CAS size.
At that point, I had a look at the code and it appears that in the worst
case, the duplication check degrades to a linear CAS scan
(cf. FSIndexRepositoryImpl line 98ff and FSIntArrayIndex line 101ff).
That would if the CAS contains only items that are equal with respect
to the index criteria, but not actually equal.
Consider a hypothetical annotation type:
Metadata extends Annotation {
String key;
String value;
}
where the begin/end are always set to 0..documentLength() and
key/value have arbitrary values. I didn't try it, but if I
understood the code correctly, a CAS containing only such
annotations would suffer heavily during the addToIndexes().
Cheers,
-- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Marshall Schor <ms...@schor.com>.
On 1/7/2016 2:31 PM, Richard Eckart de Castilho wrote:
> On 07.01.2016, at 15:21, Marshall Schor <ms...@schor.com> wrote:
>> The trick is to use an augmented sort comparator for internal operations which
>> adds one more field, that differentiates the actual FSs, like the FS address.
>> This would be used when needing to find the "exact" match - and that operation
>> would also be a log-2(size) kind of operation because it would use the same
>> binary search algorithm.
> That wouldn't be functionally equivalent to the present implementation, would it?
I think it would. Perhaps I didn't explain this well enough...
>
> It would be able to quickly figure out if a specific FS instance has already been
> added to an index, but what we currently have is testing whether an equivalent
> (via feature-by-feature comparison, not via index features) annotation is being
> added, right? Maybe I misread the code.
We have "both" styles. The feature-by-feature comparison is the normal way, but
the (in)famous method
to (linearly) go to the exact match is the other style, I think.
>
> Anyway, I believe checking if a specific instance was added twice would be completely
> sufficient.
Yes, and the question is, how to do this (more efficiently). The current
approach does a linear scan, which could be giant, in the use case you cited
where all the begin / end features are the same.
-Marshall
>
> -- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Richard Eckart de Castilho <re...@apache.org>.
On 07.01.2016, at 15:21, Marshall Schor <ms...@schor.com> wrote:
>
> The trick is to use an augmented sort comparator for internal operations which
> adds one more field, that differentiates the actual FSs, like the FS address.
> This would be used when needing to find the "exact" match - and that operation
> would also be a log-2(size) kind of operation because it would use the same
> binary search algorithm.
That wouldn't be functionally equivalent to the present implementation, would it?
It would be able to quickly figure out if a specific FS instance has already been
added to an index, but what we currently have is testing whether an equivalent
(via feature-by-feature comparison, not via index features) annotation is being
added, right? Maybe I misread the code.
Anyway, I believe checking if a specific instance was added twice would be completely
sufficient.
-- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Marshall Schor <ms...@schor.com>.
The way this could be fixed is to use a trick I learned from Nick Hill in his
Cas Object approach.
Annotation Indexes are (in v2) implemented as a sorted int array, where the sort
comparator is what's defined by the index spec, e.g., keys "begin", "end"(in
reverse order), "type priority".
The trick is to use an augmented sort comparator for internal operations which
adds one more field, that differentiates the actual FSs, like the FS address.
This would be used when needing to find the "exact" match - and that operation
would also be a log-2(size) kind of operation because it would use the same
binary search algorithm.
The experimental Uima V3 switched to this style (but would take some work to
back port because it's written to work with Java Object feature structures and
depends on Java 8 facilities).
-Marshall
On 1/6/2016 8:38 PM, Marshall Schor wrote:
> Thanks for the information!
>
> It does look like there's a performance issue if not allowing duplicate adds, for
> exactly the use case you mentioned: lots of FSs which compare "equal" according
> to the
> sorted index keys, but which are not the same FS.
>
> This can be fixed I think.
>
> There's also a user-centered workaround, for some cases, when it's possible to
> re-define the type system somewhat.
>
> One kind of thing I've seen frequently, is that people define types having
> nothing to do with Annotation (e.g. they don't use begin / end, etc.) as
> subtypes of Annotation.
>
> If you are able to change the type system definitions so that these things no
> longer are subtypes of Annotation, then the problem might go away.
>
> -Marshall
> On 1/6/2016 6:18 PM, Richard Eckart de Castilho wrote:
>>>> I am starting to get suspicious of global flags for backwards compatibility.
>>>> E.g. since ALLOW_DUP_ADD_TO_INDEXES was introduced, we have people complaining
>>>> about a performance drop. ALLOW_DUP_ADD_TO_INDEXES can only be enabled/disabled
>>>> globally, but not specifically for individual indexes. Neither can it be
>>>> temporarily disabled, e.g. during deserialization or other bulk operations.
>>>> I wonder if local getters/setters or ThreadLocal variables initialized by
>>>> a global setting wouldn't be a more appropriate option.
>>> I was unaware of the performance issue; I may have missed some emails... Can
>>> you say how significant it is? If there were no performance issue, would the
>>> additional function be needed?
>>>
>>> I assume the performance drop is when duplicates are not allowed (the new
>>> default), and some users are wanting to restore the previous performance by
>>> turning on ALLOW_DUP .... Is this correct?
>> I didn't track it in detail, but apparently, some time back Peter noticed a
>> drop in XMI deserialization performance and more recently also in compressed
>> binary CAS deserialization. Some time later, I had a person claiming in
>> private mail that deserialization was O(n^2) with respect to the CAS size.
>>
>> At that point, I had a look at the code and it appears that in the worst
>> case, the duplication check degrades to a linear CAS scan
>> (cf. FSIndexRepositoryImpl line 98ff and FSIntArrayIndex line 101ff).
>> That would if the CAS contains only items that are equal with respect
>> to the index criteria, but not actually equal.
>>
>> Consider a hypothetical annotation type:
>>
>> Metadata extends Annotation {
>> String key;
>> String value;
>> }
>>
>> where the begin/end are always set to 0..documentLength() and
>> key/value have arbitrary values. I didn't try it, but if I
>> understood the code correctly, a CAS containing only such
>> annotations would suffer heavily during the addToIndexes().
>>
>> Cheers,
>>
>> -- Richard
>
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Richard Eckart de Castilho <re...@apache.org>.
> On 07.01.2016, at 21:34, Marshall Schor <ms...@schor.com> wrote:
>
> Looking at the code in CASImpl, I see
> (line 112) cas.impl.Serialization: public static void
> deserializeCASComplete(CASCompleteSerializer casCompSer ...) ->
> (line 1231) reinit(CASCompleteSerializer....) calls (line 1260)
> (line 1293) reinit( a bunch of arrays, including int[] fsIndex which is an array
> of things to add to indexes) calls (line 1307)
> (line 1730) reinitIndexedFSs(int[] fsIndex) which has a double loop - outer for
> views, inner for all indexed fs where it does
> (line 1770) addFS(fsIndex[i])
>
> which does a one element add of the feature structure to the indexes.
>
> Perhaps though I'm following the wrong code path ...
No, you're right. Wishful thinking on my side... :(
And to be sure I just tried CASCompleteSerializer
with a testcase that uses a degenerated CAS with all
annotations at 0,0 and it's dead slow.
-- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Marshall Schor <ms...@schor.com>.
Looking at the code in CASImpl, I see
(line 112) cas.impl.Serialization: public static void
deserializeCASComplete(CASCompleteSerializer casCompSer ...) ->
(line 1231) reinit(CASCompleteSerializer....) calls (line 1260)
(line 1293) reinit( a bunch of arrays, including int[] fsIndex which is an array
of things to add to indexes) calls (line 1307)
(line 1730) reinitIndexedFSs(int[] fsIndex) which has a double loop - outer for
views, inner for all indexed fs where it does
(line 1770) addFS(fsIndex[i])
which does a one element add of the feature structure to the indexes.
Perhaps though I'm following the wrong code path ...
-Marshall
On 1/7/2016 10:36 AM, Richard Eckart de Castilho wrote:
> On 07.01.2016, at 15:12, Marshall Schor <ms...@schor.com> wrote:
>> Thanks for explaining this "use case".
>>
>> I was a bit unclear on the two instances of deserialization time.
>> One (the 70%) was xmi, the other (2%) was S+. From reading the email chain, it
>> seems S+ is the "CasCompleteSerializer". This switches to plain binary mode.
>> So you would avoid the XML parsing overhead.
>>
>> But I think both deserializations would have the same issue around "allow_dups"
>> if that was where the substantial part of the slowdown was being spent, since
>> both would add all those annotations to the index. Perhaps that was another use
>> case though... Am I mixing these up?
> My understanding is that the CasCompleteSerializer is (de)serializing the heap
> structures and indexes as-is. So on loading, FSes are not passing through
> addToIndexes() and allow_dups at all. This should be what makes the S and S+
> faster than the other approaches that call addToIndexes().
>
> Btw. Cas(Complete)Serializer also has the nice effect that the addresses of
> FSes remain fully stable as even unindexed/unreachable FSes are stored and
> loaded. I think all other serializers drop unreachable which can cause addresses
> to change. I have a usecase in WebAnno where I'm absolutely relying on the
> stable addresses provided by the Cas(Complete)Serializer.
>
> Cheers,
>
> -- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Richard Eckart de Castilho <re...@apache.org>.
On 07.01.2016, at 15:12, Marshall Schor <ms...@schor.com> wrote:
>
> Thanks for explaining this "use case".
>
> I was a bit unclear on the two instances of deserialization time.
> One (the 70%) was xmi, the other (2%) was S+. From reading the email chain, it
> seems S+ is the "CasCompleteSerializer". This switches to plain binary mode.
> So you would avoid the XML parsing overhead.
>
> But I think both deserializations would have the same issue around "allow_dups"
> if that was where the substantial part of the slowdown was being spent, since
> both would add all those annotations to the index. Perhaps that was another use
> case though... Am I mixing these up?
My understanding is that the CasCompleteSerializer is (de)serializing the heap
structures and indexes as-is. So on loading, FSes are not passing through
addToIndexes() and allow_dups at all. This should be what makes the S and S+
faster than the other approaches that call addToIndexes().
Btw. Cas(Complete)Serializer also has the nice effect that the addresses of
FSes remain fully stable as even unindexed/unreachable FSes are stored and
loaded. I think all other serializers drop unreachable which can cause addresses
to change. I have a usecase in WebAnno where I'm absolutely relying on the
stable addresses provided by the Cas(Complete)Serializer.
Cheers,
-- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Marshall Schor <ms...@schor.com>.
Thanks for explaining this "use case".
I was a bit unclear on the two instances of deserialization time.
One (the 70%) was xmi, the other (2%) was S+. From reading the email chain, it
seems S+ is the "CasCompleteSerializer". This switches to plain binary mode.
So you would avoid the XML parsing overhead.
But I think both deserializations would have the same issue around "allow_dups"
if that was where the substantial part of the slowdown was being spent, since
both would add all those annotations to the index. Perhaps that was another use
case though... Am I mixing these up?
-Marshall
On 1/7/2016 2:38 AM, Peter Klügl wrote:
> Hi,
>
> rule engineering in ruta follows a paradigm where you spam annotations,
> also with same type and offsets. Additionally, and probably the most
> critical case, the explanation of the rule inference creates those
> annotations for debugging. Imaging something like an annotation of the
> type "Debug" for every text span where some rule tried to match (and did
> not even succeed).
>
> In one of my use cases, the time spent in deserialization in the CAS
> Editor was reduced from 70% (xmi) to 2% (binary).
>
> Here's the discussion:
> https://issues.apache.org/jira/browse/UIMA-4685
>
> Best,
>
> Peter
>
>
> Am 07.01.2016 um 02:38 schrieb Marshall Schor:
>> Thanks for the information!
>>
>> It does look like there's a performance issue if not allowing duplicate adds, for
>> exactly the use case you mentioned: lots of FSs which compare "equal" according
>> to the
>> sorted index keys, but which are not the same FS.
>>
>> This can be fixed I think.
>>
>> There's also a user-centered workaround, for some cases, when it's possible to
>> re-define the type system somewhat.
>>
>> One kind of thing I've seen frequently, is that people define types having
>> nothing to do with Annotation (e.g. they don't use begin / end, etc.) as
>> subtypes of Annotation.
>>
>> If you are able to change the type system definitions so that these things no
>> longer are subtypes of Annotation, then the problem might go away.
>>
>> -Marshall
>> On 1/6/2016 6:18 PM, Richard Eckart de Castilho wrote:
>>>>> I am starting to get suspicious of global flags for backwards compatibility.
>>>>> E.g. since ALLOW_DUP_ADD_TO_INDEXES was introduced, we have people complaining
>>>>> about a performance drop. ALLOW_DUP_ADD_TO_INDEXES can only be enabled/disabled
>>>>> globally, but not specifically for individual indexes. Neither can it be
>>>>> temporarily disabled, e.g. during deserialization or other bulk operations.
>>>>> I wonder if local getters/setters or ThreadLocal variables initialized by
>>>>> a global setting wouldn't be a more appropriate option.
>>>> I was unaware of the performance issue; I may have missed some emails... Can
>>>> you say how significant it is? If there were no performance issue, would the
>>>> additional function be needed?
>>>>
>>>> I assume the performance drop is when duplicates are not allowed (the new
>>>> default), and some users are wanting to restore the previous performance by
>>>> turning on ALLOW_DUP .... Is this correct?
>>> I didn't track it in detail, but apparently, some time back Peter noticed a
>>> drop in XMI deserialization performance and more recently also in compressed
>>> binary CAS deserialization. Some time later, I had a person claiming in
>>> private mail that deserialization was O(n^2) with respect to the CAS size.
>>>
>>> At that point, I had a look at the code and it appears that in the worst
>>> case, the duplication check degrades to a linear CAS scan
>>> (cf. FSIndexRepositoryImpl line 98ff and FSIntArrayIndex line 101ff).
>>> That would if the CAS contains only items that are equal with respect
>>> to the index criteria, but not actually equal.
>>>
>>> Consider a hypothetical annotation type:
>>>
>>> Metadata extends Annotation {
>>> String key;
>>> String value;
>>> }
>>>
>>> where the begin/end are always set to 0..documentLength() and
>>> key/value have arbitrary values. I didn't try it, but if I
>>> understood the code correctly, a CAS containing only such
>>> annotations would suffer heavily during the addToIndexes().
>>>
>>> Cheers,
>>>
>>> -- Richard
>
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Peter Klügl <pe...@averbis.com>.
Hi,
rule engineering in ruta follows a paradigm where you spam annotations,
also with same type and offsets. Additionally, and probably the most
critical case, the explanation of the rule inference creates those
annotations for debugging. Imaging something like an annotation of the
type "Debug" for every text span where some rule tried to match (and did
not even succeed).
In one of my use cases, the time spent in deserialization in the CAS
Editor was reduced from 70% (xmi) to 2% (binary).
Here's the discussion:
https://issues.apache.org/jira/browse/UIMA-4685
Best,
Peter
Am 07.01.2016 um 02:38 schrieb Marshall Schor:
> Thanks for the information!
>
> It does look like there's a performance issue if not allowing duplicate adds, for
> exactly the use case you mentioned: lots of FSs which compare "equal" according
> to the
> sorted index keys, but which are not the same FS.
>
> This can be fixed I think.
>
> There's also a user-centered workaround, for some cases, when it's possible to
> re-define the type system somewhat.
>
> One kind of thing I've seen frequently, is that people define types having
> nothing to do with Annotation (e.g. they don't use begin / end, etc.) as
> subtypes of Annotation.
>
> If you are able to change the type system definitions so that these things no
> longer are subtypes of Annotation, then the problem might go away.
>
> -Marshall
> On 1/6/2016 6:18 PM, Richard Eckart de Castilho wrote:
>>>> I am starting to get suspicious of global flags for backwards compatibility.
>>>> E.g. since ALLOW_DUP_ADD_TO_INDEXES was introduced, we have people complaining
>>>> about a performance drop. ALLOW_DUP_ADD_TO_INDEXES can only be enabled/disabled
>>>> globally, but not specifically for individual indexes. Neither can it be
>>>> temporarily disabled, e.g. during deserialization or other bulk operations.
>>>> I wonder if local getters/setters or ThreadLocal variables initialized by
>>>> a global setting wouldn't be a more appropriate option.
>>> I was unaware of the performance issue; I may have missed some emails... Can
>>> you say how significant it is? If there were no performance issue, would the
>>> additional function be needed?
>>>
>>> I assume the performance drop is when duplicates are not allowed (the new
>>> default), and some users are wanting to restore the previous performance by
>>> turning on ALLOW_DUP .... Is this correct?
>> I didn't track it in detail, but apparently, some time back Peter noticed a
>> drop in XMI deserialization performance and more recently also in compressed
>> binary CAS deserialization. Some time later, I had a person claiming in
>> private mail that deserialization was O(n^2) with respect to the CAS size.
>>
>> At that point, I had a look at the code and it appears that in the worst
>> case, the duplication check degrades to a linear CAS scan
>> (cf. FSIndexRepositoryImpl line 98ff and FSIntArrayIndex line 101ff).
>> That would if the CAS contains only items that are equal with respect
>> to the index criteria, but not actually equal.
>>
>> Consider a hypothetical annotation type:
>>
>> Metadata extends Annotation {
>> String key;
>> String value;
>> }
>>
>> where the begin/end are always set to 0..documentLength() and
>> key/value have arbitrary values. I didn't try it, but if I
>> understood the code correctly, a CAS containing only such
>> annotations would suffer heavily during the addToIndexes().
>>
>> Cheers,
>>
>> -- Richard
Re: Performance and ALLOW_DUP_ADD_TO_INDEXES
Posted by Marshall Schor <ms...@schor.com>.
Thanks for the information!
It does look like there's a performance issue if not allowing duplicate adds, for
exactly the use case you mentioned: lots of FSs which compare "equal" according
to the
sorted index keys, but which are not the same FS.
This can be fixed I think.
There's also a user-centered workaround, for some cases, when it's possible to
re-define the type system somewhat.
One kind of thing I've seen frequently, is that people define types having
nothing to do with Annotation (e.g. they don't use begin / end, etc.) as
subtypes of Annotation.
If you are able to change the type system definitions so that these things no
longer are subtypes of Annotation, then the problem might go away.
-Marshall
On 1/6/2016 6:18 PM, Richard Eckart de Castilho wrote:
>>> I am starting to get suspicious of global flags for backwards compatibility.
>>> E.g. since ALLOW_DUP_ADD_TO_INDEXES was introduced, we have people complaining
>>> about a performance drop. ALLOW_DUP_ADD_TO_INDEXES can only be enabled/disabled
>>> globally, but not specifically for individual indexes. Neither can it be
>>> temporarily disabled, e.g. during deserialization or other bulk operations.
>>> I wonder if local getters/setters or ThreadLocal variables initialized by
>>> a global setting wouldn't be a more appropriate option.
>> I was unaware of the performance issue; I may have missed some emails... Can
>> you say how significant it is? If there were no performance issue, would the
>> additional function be needed?
>>
>> I assume the performance drop is when duplicates are not allowed (the new
>> default), and some users are wanting to restore the previous performance by
>> turning on ALLOW_DUP .... Is this correct?
> I didn't track it in detail, but apparently, some time back Peter noticed a
> drop in XMI deserialization performance and more recently also in compressed
> binary CAS deserialization. Some time later, I had a person claiming in
> private mail that deserialization was O(n^2) with respect to the CAS size.
>
> At that point, I had a look at the code and it appears that in the worst
> case, the duplication check degrades to a linear CAS scan
> (cf. FSIndexRepositoryImpl line 98ff and FSIntArrayIndex line 101ff).
> That would if the CAS contains only items that are equal with respect
> to the index criteria, but not actually equal.
>
> Consider a hypothetical annotation type:
>
> Metadata extends Annotation {
> String key;
> String value;
> }
>
> where the begin/end are always set to 0..documentLength() and
> key/value have arbitrary values. I didn't try it, but if I
> understood the code correctly, a CAS containing only such
> annotations would suffer heavily during the addToIndexes().
>
> Cheers,
>
> -- Richard