You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@uima.apache.org by Bhavani Iyer <bh...@gmail.com> on 2008/07/08 15:58:59 UTC

Delta CAS

We're planning to start  the implementation to support Delta CAS as
described here:
http://cwiki.apache.org/UIMA/reducing-overhead-for-remote-service-calls.html

The current thinking on the design is described below and we would like some
feedback.
*
CAS Activity Journal*
In order to be able to export as XMI only the updates to the CAS, we need to
maintain
a journal associated with the CAS to track these update activities.  The
journal will
contain the following information:

1) To identify new FSs, the max FS id at the start of processing is saved .
New FS added
     would have ids above this high water mark.
2) To identify which pre-existing FSs were modified,, a list of ids of
pre-existing FSs that have been changed.
3)  To track updates to the Views, a list of FS ids added, removed and
reindexed in the index repository of pre-existing Views.

The CAS APIs  that set feature values as well as APIs that add or remove
from the
index repository will be modified to update the CAS activity journal.
The overhead is expected to be be minimal since it will simply add an FS id
to the
appropriate list as mentioned above.

*Delta CAS XMI serialization*
A more compact representation of the delta CAS data than the proposed
XMI:Difference format
would be preferred for transmitting CAS data when making calls to a remote
service.

Instead, we propose that CAS updates  be serialized in the same format as
the XMI CAS with one modification.
Additional attributes will be defined in the View element to contain the
list of
ids of FSs that were added, deleted and reindexed:

Example of current cas:View
<cas:View sofa="1" members="8 13 20 26 42"/>

Example of proposed cas:View to support delta CAS
<cas:View sofa="1" members_added="32"  members_deleted="13 20"
members_reindexed="26 42" />

XMI deserialization of the delta CAS  will update the CAS as follows:
1) create new FS for those elements where xmi:id is above the high water
mark.
2) update the FSs feature values for those elements where xmi:id is below
the high water mark. Note, features
    missing in the XMI will be set to null.
3) Process the view element to add, remove or reindex in the specified VIew
index repository.

Please note that this proposed XMI representation itself does not identify
or mark the CAS as a delta CAS.
In the context of UIMA AS services, additional properties in the request and
reply messages will
specify that the XMI contains a delta CAS.
Applications should not use the API to export a delta CAS to a file for
later processing without
taking additional steps to retain the format information.


*Delta CAS for debugging*
To support debugging UIMA aggregates as described here
 http://cwiki.apache.org/UIMA/improving-uima-debug-capabilities.html
the delta CAS implementation will be extended as follows:
1) the CAS activity journal will be maintained for each component that is
called during aggregate processing.
2) an API to enable/disable this extended journaling by component.
3) define the XMI representation of the CAS activity journal. Details on
this will be posted shortly.

We would appreciate comments and suggestions on the proposed changes.

Thanks,

Bhavani

Re: Delta CAS

Posted by Marshall Schor <ms...@schor.com>.
Bhavani Iyer wrote:
> We're planning to start  the implementation to support Delta CAS as
> described here:
> http://cwiki.apache.org/UIMA/reducing-overhead-for-remote-service-calls.html
>
> The current thinking on the design is described below and we would like some
> feedback.
> *CAS Activity Journal*
> In order to be able to export as XMI only the updates to the CAS, we need to
> maintain a journal associated with the CAS to track these update activities.  The 
> journal will contain the following information:
>
> 1) To identify new FSs, the max FS id at the start of processing is saved.
> New FS added would have ids above this high water mark.
> 2) To identify which pre-existing FSs were modified,, a list of ids of
> pre-existing FSs that have been changed.
> 3)  To track updates to the Views, a list of FS ids added, removed and
> reindexed in the index repository of pre-existing Views.
>   
I think of the View here as referring to the indexes.  The remote AE may 
not have the full set of indexes the client is using.  So no 
optimization can be reliably done based on analyzing changes to 
determine if they affect an index.
> The CAS APIs  that set feature values as well as APIs that add or remove
> from the index repository will be modified to update the CAS activity journal.
> The overhead is expected to be be minimal since it will simply add an FS id
> to the appropriate list as mentioned above.
>   
There will be both time and space overhead for this, of course; the 
space overhead might not be minimal.  Note that there are a lot of 
variations of the APIs to the CAS including so-called "low-level" ones, 
all of which need to be found and modified.
> *Delta CAS XMI serialization*
> A more compact representation of the delta CAS data than the proposed
> XMI:Difference format would be preferred for transmitting CAS data when making calls to a remote
> service. Instead, we propose that CAS updates  be serialized in the same format as
> the XMI CAS with one modification. Additional attributes will be defined in the View element to contain the
> list of ids of FSs that were added, deleted and reindexed:
>
> Example of current cas:View
> <cas:View sofa="1" members="8 13 20 26 42"/>
>
> Example of proposed cas:View to support delta CAS
> <cas:View sofa="1" members_added="32"  members_deleted="13 20"
> members_reindexed="26 42" />
>
> XMI deserialization of the delta CAS  will update the CAS as follows:
> 1) create new FS for those elements where xmi:id is above the high water
> mark.
> 2) update the FSs feature values for those elements where xmi:id is below
> the high water mark. Note, features missing in the XMI will be set to null.
>   
Not sure what this note means.  I guess it implies that the server must 
make sure to send back all features (including those *not* defined in 
its type system) for a FS, unless the feature value is null.  Is this 
also true for other values, like 0 for numbers?

-Marshall
> 3) Process the view element to add, remove or reindex in the specified VIew
> index repository.
>
> Please note that this proposed XMI representation itself does not identify
> or mark the CAS as a delta CAS. In the context of UIMA AS services, additional properties in the request and
> reply messages will specify that the XMI contains a delta CAS.
> Applications should not use the API to export a delta CAS to a file for
> later processing without taking additional steps to retain the format information.
>
>
> *Delta CAS for debugging*
> To support debugging UIMA aggregates as described here
>  http://cwiki.apache.org/UIMA/improving-uima-debug-capabilities.html
> the delta CAS implementation will be extended as follows:
> 1) the CAS activity journal will be maintained for each component that is
> called during aggregate processing.
> 2) an API to enable/disable this extended journaling by component.
> 3) define the XMI representation of the CAS activity journal. Details on
> this will be posted shortly.
>
> We would appreciate comments and suggestions on the proposed changes.
>
> Thanks,
>
> Bhavani
>
>   


Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
The journaling information is associated with a CAS but not part of the
CAS.  The marker object is fine for identify new FSs. To identify
modifications to  pre-existing FSs,  this activity has to be logged by the
CAS APIs  that set feature value and add/remove FS from the index
repository.

In addition, we'll need APIs to access this journalling information for XMI
serialization and for viewing activity by component for debugging.

Bhavani

On Thu, Jul 10, 2008 at 10:32 AM, Thilo Goetz <tw...@gmx.de> wrote:

> Eddie Epstein wrote:
>
>> On Thu, Jul 10, 2008 at 5:30 AM, Thilo Goetz <tw...@gmx.de> wrote:
>>
>>  I would like to lift this discussion to a higher
>>> level of abstraction, as Adam is trying to.  What
>>> are the actual requirements against the CAS?  Here's
>>> what I think I understood.
>>>
>>> You want to be able to obtain from the CAS a marker
>>> object.  Then you want to be able to query the CAS
>>> with the marker and an FS and ask if the FS was
>>> added before or after the marker was obtained.  Is
>>> that right?
>>>
>>
>>
>> That's right, for a simple delta CAS reply from a service, but actually
>> many
>> markers for journaling so that additions can be attributed to a specific
>> annotator.
>>
>
> Ok, I think that shouldn't make a difference.
>
>
>> Bhavani Iyer wrote:
>>
>>> If we are thinking of Delta CAS in the context of service the largest xmi
>>>> id
>>>> works. But
>>>> we were also using the same mechanism to support tracking CAS activity
>>>> by
>>>> component.
>>>> I suppose in the second case the additional overhead of maintaining a
>>>> list
>>>> of the FSs that
>>>> are added may be acceptable.
>>>>
>>>
>>>  A requirement for delta CAS is to identity new FS and modified FS. A low
>> cost way to get modified FS is to add the FS-id to a simple list each time
>> a
>> feature in a preexisting FS is set, then sort and remove duplicates. Being
>> able to identify and ignore new FS at setFeature() time allows huge
>> reduction in overhead because modifications are so much less frequent than
>> additions.
>>
>
> So you want to do this outside the CAS?  Or not?
>
>
>
>> Yes, spreading FS across [power of 2 size] segments should eliminate holes
>> and more complicated bookkeeping for large arrays.
>>
>> Eddie
>>
>>

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Eddie Epstein wrote:
> On Thu, Jul 10, 2008 at 5:30 AM, Thilo Goetz <tw...@gmx.de> wrote:
> 
>> I would like to lift this discussion to a higher
>> level of abstraction, as Adam is trying to.  What
>> are the actual requirements against the CAS?  Here's
>> what I think I understood.
>>
>> You want to be able to obtain from the CAS a marker
>> object.  Then you want to be able to query the CAS
>> with the marker and an FS and ask if the FS was
>> added before or after the marker was obtained.  Is
>> that right?
> 
> 
> That's right, for a simple delta CAS reply from a service, but actually many
> markers for journaling so that additions can be attributed to a specific
> annotator.

Ok, I think that shouldn't make a difference.

> 
> Bhavani Iyer wrote:
>>> If we are thinking of Delta CAS in the context of service the largest xmi
>>> id
>>> works. But
>>> we were also using the same mechanism to support tracking CAS activity by
>>> component.
>>> I suppose in the second case the additional overhead of maintaining a list
>>> of the FSs that
>>> are added may be acceptable.
>>
> A requirement for delta CAS is to identity new FS and modified FS. A low
> cost way to get modified FS is to add the FS-id to a simple list each time a
> feature in a preexisting FS is set, then sort and remove duplicates. Being
> able to identify and ignore new FS at setFeature() time allows huge
> reduction in overhead because modifications are so much less frequent than
> additions.

So you want to do this outside the CAS?  Or not?

> 
> Yes, spreading FS across [power of 2 size] segments should eliminate holes
> and more complicated bookkeeping for large arrays.
> 
> Eddie
> 

Re: Delta CAS

Posted by Eddie Epstein <ea...@gmail.com>.
On Thu, Jul 10, 2008 at 5:30 AM, Thilo Goetz <tw...@gmx.de> wrote:

> I would like to lift this discussion to a higher
> level of abstraction, as Adam is trying to.  What
> are the actual requirements against the CAS?  Here's
> what I think I understood.
>
> You want to be able to obtain from the CAS a marker
> object.  Then you want to be able to query the CAS
> with the marker and an FS and ask if the FS was
> added before or after the marker was obtained.  Is
> that right?


That's right, for a simple delta CAS reply from a service, but actually many
markers for journaling so that additions can be attributed to a specific
annotator.

Bhavani Iyer wrote:
>
>> If we are thinking of Delta CAS in the context of service the largest xmi
>> id
>> works. But
>> we were also using the same mechanism to support tracking CAS activity by
>> component.
>> I suppose in the second case the additional overhead of maintaining a list
>> of the FSs that
>> are added may be acceptable.
>
>
A requirement for delta CAS is to identity new FS and modified FS. A low
cost way to get modified FS is to add the FS-id to a simple list each time a
feature in a preexisting FS is set, then sort and remove duplicates. Being
able to identify and ignore new FS at setFeature() time allows huge
reduction in overhead because modifications are so much less frequent than
additions.

Yes, spreading FS across [power of 2 size] segments should eliminate holes
and more complicated bookkeeping for large arrays.

Eddie

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
I would like to lift this discussion to a higher
level of abstraction, as Adam is trying to.  What
are the actual requirements against the CAS?  Here's
what I think I understood.

You want to be able to obtain from the CAS a marker
object.  Then you want to be able to query the CAS
with the marker and an FS and ask if the FS was
added before or after the marker was obtained.  Is
that right?

--Thilo

Bhavani Iyer wrote:
> If we are thinking of Delta CAS in the context of service the largest xmi id
> works. But
> we were also using the same mechanism to support tracking CAS activity by
> component.
> I suppose in the second case the additional overhead of maintaining a list
> of the FSs that
> are added may be acceptable.
> 
> On Wed, Jul 9, 2008 at 3:48 PM, Adam Lally <al...@alum.rpi.edu> wrote:
> 
>>> Back to the high-water mark ... isn't it just the largest xmi id in the
>>> serialized CAS?  Its relationship to the CAS heap is a matter of
>>> implementation but presumably we can have a design that says any new FSs
>>> must be given an xmi id above the high-water mark when serialized back
>> from
>>> a service.  We already have the requirement that ids must be preserved
>> for
>>> the merging of parallel replies.
>>>
>> Yes - there are really two definitions of high-water mark floating
>> around in this thread and it would be good to split them apart.
>>
>> (1) the largest xmi:id in the serialized CAS.  This is a requirement
>> that the service protocol places on the CAS serializer.  This is what
>> we already have for merging, and I don't think Thilo is objecting to
>> this.
>>
>> (2) a dependency on the FS address being an indicator of which FS are
>> newer than others (an FS with a larger address is newer).
>>
>> As I think about it now I am actually unclear on whether we are doing
>> #2 right now at all.  Bhavani said we were, but that's not how I
>> recall that the serializer currently works.  It keeps a table of all
>> the incoming FS, which is necessary in order to have the xmi:ids going
>> out be the same as the ones coming in.  So I thought the serializer
>> just used the fact that an FS was missing from this table to determine
>> that it was new, and *not* a high water mark of the FS address.
>> Bhavani, can you clarify?
>>
>>  -Adam
>>
> 

Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
If we are thinking of Delta CAS in the context of service the largest xmi id
works. But
we were also using the same mechanism to support tracking CAS activity by
component.
I suppose in the second case the additional overhead of maintaining a list
of the FSs that
are added may be acceptable.

On Wed, Jul 9, 2008 at 3:48 PM, Adam Lally <al...@alum.rpi.edu> wrote:

> > Back to the high-water mark ... isn't it just the largest xmi id in the
> > serialized CAS?  Its relationship to the CAS heap is a matter of
> > implementation but presumably we can have a design that says any new FSs
> > must be given an xmi id above the high-water mark when serialized back
> from
> > a service.  We already have the requirement that ids must be preserved
> for
> > the merging of parallel replies.
> >
>
> Yes - there are really two definitions of high-water mark floating
> around in this thread and it would be good to split them apart.
>
> (1) the largest xmi:id in the serialized CAS.  This is a requirement
> that the service protocol places on the CAS serializer.  This is what
> we already have for merging, and I don't think Thilo is objecting to
> this.
>
> (2) a dependency on the FS address being an indicator of which FS are
> newer than others (an FS with a larger address is newer).
>
> As I think about it now I am actually unclear on whether we are doing
> #2 right now at all.  Bhavani said we were, but that's not how I
> recall that the serializer currently works.  It keeps a table of all
> the incoming FS, which is necessary in order to have the xmi:ids going
> out be the same as the ones coming in.  So I thought the serializer
> just used the fact that an FS was missing from this table to determine
> that it was new, and *not* a high water mark of the FS address.
> Bhavani, can you clarify?
>
>  -Adam
>

Re: Delta CAS

Posted by Adam Lally <al...@alum.rpi.edu>.
> Back to the high-water mark ... isn't it just the largest xmi id in the
> serialized CAS?  Its relationship to the CAS heap is a matter of
> implementation but presumably we can have a design that says any new FSs
> must be given an xmi id above the high-water mark when serialized back from
> a service.  We already have the requirement that ids must be preserved for
> the merging of parallel replies.
>

Yes - there are really two definitions of high-water mark floating
around in this thread and it would be good to split them apart.

(1) the largest xmi:id in the serialized CAS.  This is a requirement
that the service protocol places on the CAS serializer.  This is what
we already have for merging, and I don't think Thilo is objecting to
this.

(2) a dependency on the FS address being an indicator of which FS are
newer than others (an FS with a larger address is newer).

As I think about it now I am actually unclear on whether we are doing
#2 right now at all.  Bhavani said we were, but that's not how I
recall that the serializer currently works.  It keeps a table of all
the incoming FS, which is necessary in order to have the xmi:ids going
out be the same as the ones coming in.  So I thought the serializer
just used the fact that an FS was missing from this table to determine
that it was new, and *not* a high water mark of the FS address.
Bhavani, can you clarify?

  -Adam

Re: Delta CAS

Posted by Burn Lewis <bu...@gmail.com>.
I think we need another thread to discuss the heap.

Back to the high-water mark ... isn't it just the largest xmi id in the
serialized CAS?  Its relationship to the CAS heap is a matter of
implementation but presumably we can have a design that says any new FSs
must be given an xmi id above the high-water mark when serialized back from
a service.  We already have the requirement that ids must be preserved for
the merging of parallel replies.

Burn.

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Marshall Schor wrote:
> Some intermediate approach might help here - such as an application or 
> annotator being able to provide performance tuning hints to the 
> framework.  For instance, a tokenizer might be able to guesstimate the 
> number of tokens, based on some average token size estimate divided into 
> the size of the document, and provide that as a hint.

Tell me about it.  We've built a whole framework to try
and figure out ahead of time how much memory processing
a certain document is going to take, so we know how many
threads we can run in parallel before crashing the JVM.
This turns out to be quite difficult if you don't know
what kinds of documents you'll be getting, and you work
with many different languages.

--Thilo


Re: Delta CAS

Posted by Marshall Schor <ms...@schor.com>.
Thilo Goetz wrote:
>
>
> Eddie Epstein wrote:
>> On Wed, Jul 9, 2008 at 1:51 AM, Thilo Goetz <tw...@gmx.de> wrote:
>>
>>> Nothing so easy.  The CAS heap is one large int array.  We grow it
>>> by allocating a new array with the new desired size and copying the
>>> old values over to the new one.  There are several issues with this
>>> method:
>>>
>>> * Copying the data takes a surprisingly long time.  There's a test
>>> case in core that does nothing but add new FSs to the CAS, a lot of
>>> them.  Marshall complained about how long it took to run when I
>>> added it (about 20s on my machine).  If you profile that test case,
>>> you will see that the vast majority of time is spent in copying
>>> data from an old heap to a new heap.  If the CAS becomes sufficiently
>>> large (in the hundreds of MBs), the time it takes to actually add
>>> FSs to the CAS is completely dwarfed by the time it takes for the
>>> heap to grow.
>>>
>>> * The heap lives in a single large array, and a new single large
>>> array is allocated every time the heap grows.  This is a challenge
>>> for the jvm as it allocates this array in a contiguous block of
>>> memory.  So there must be enough contiguous space on the jvm heap,
>>> which likely means a full heap compaction before a new large array
>>> can be allocated.  Sometimes the jvm fails to allocate that
>>> contiguous space, even though there are enough free bytes on the
>>> jvm jeap.
>>>
>>> * Saved the best for last.  When allocating a new array, the old
>>> one hangs around till we have copied the data.  So we're using twice
>>> the necessary space for some period of time.  That space is often
>>> not available.  So any time I see an out-of-memory error for large
>>> documents (and it's not a bug in the annotator chain), it happens
>>> when the CAS heap grows; not because there isn't enough room for
>>> the larger heap, but because the old one is still there as well.
>>> The CAS can only grow to about half the size we have memory for
>>> because of that issue.
>>
>>
>> The situation is more complicated than portrayed. The heap does not 
>> have to
>> shrink, so the growth penalty is rare and can be eliminated entirely 
>> if the
>> max necessary size heap is specified at startup. FS allocated in the 
>> heap do
>
> You don't want to allocate a max heap size of 500M just because
> you may need one that big.  You don't even want to allocate 10M
> ahead of time because if you have many small documents, you can
> do more parallel processing.  So no, I can't specify a large enough
> heap at start-up and yes, the heap most certainly has to shrink
> on CAS reset.
Some intermediate approach might help here - such as an application or 
annotator being able to provide performance tuning hints to the 
framework.  For instance, a tokenizer might be able to guesstimate the 
number of tokens, based on some average token size estimate divided into 
the size of the document, and provide that as a hint.
>
>> not have any Java object memory overhead. Garbage collection for 
>> separate FS
>> objects would be [much?] worse than the time it takes currently to 
>> clear the
>> used part of a CAS heap.
>
> I won't believe this until I see it, but I wasn't suggesting
> this so I'm not going to argue the point, either.
>
>>
>> Going forward, one approach to this problem could be not one
>>> heap array, but a list of arrays.  Every time we grow the heap,
>>> we would just add another array.  That approach solves all the
>>> problems mentioned above while being minimally invasive to the
>>> way the CAS currently works.  However, it raises a new issue:
>>> how do you address cells across several arrays in an efficient
>>> manner?  We don't want to improve performance for large docs at
>>> the expense of small ones.  So heap addresses might stop being
>>> the linear sequence of integers they are today.  Maybe we'll
>>> use the high bits to address the array, and the low bits to
>>> address cells in a given array.  And there goes the watermark.
>>> Maybe this won't be necessary, I don't know at this point.
>>
>>
>> Each FS object could include an ID that would allow maintaining a 
>> high water
>> mark, of course at the expense of another 4 bytes per. With a heap
>> constructed from multiple discontiguous arrays, each array could 
>> include a
>> relative ID. This is not to say that the high water mark is always 
>> the right
>> approach :)
>
> I'm trying to decrease the memory overhead, not increase it.
Would there be a solution that would work for the multi-block heap, 
without adding 4 bytes per FS Object?
>>
>> Excellent suggestion, except why not have this discussion now?
>>> We just need to put our heads together and figure out how to address
>>> this requirement to everybody's satisfaction, case closed.  I'm
>>> not disagreeing with the requirement, just the proposed implementation
>>> thereof.  Doing this now may save us (ok, me) a lot of trouble later.
>>
>>
>> Who is against having the discussion now :)
>
> Marshall seemed to favor a discussion at a later point.  Maybe
> I misinterpreted.
I did not intend to express favoring a discussion at a later point 
versus now.  Discussions at any point are good, IMHO.
-Marshall
>
>>
>> Eddie
>>
>
>


Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.

Eddie Epstein wrote:
> On Wed, Jul 9, 2008 at 9:18 AM, Thilo Goetz <tw...@gmx.de> wrote:
> 
>> You don't want to allocate a max heap size of 500M just because
>> you may need one that big.  You don't even want to allocate 10M
>> ahead of time because if you have many small documents, you can
>> do more parallel processing.  So no, I can't specify a large enough
>> heap at start-up and yes, the heap most certainly has to shrink
>> on CAS reset.
> 
> 
> Sounds like your scenario has multiple threads, each with at least one CAS,

I don't usually have the luxury of running just UIMA on a server.
Other processes want memory, too.

> processing a mixed size of documents. Either there is enough Java heap space
> to process multiple large documents at the same time or not. Pre-allocating
> the CAS heap space and not letting them grow enables soft processing
> failures of large documents rather than the unfortunate failure of the
> entire JVM.
> 
> Can you say more about the scenario(s) we are optimizing for?

Variously sized documents, some of them very large, many very small.

Re: Delta CAS

Posted by Eddie Epstein <ea...@gmail.com>.
On Wed, Jul 9, 2008 at 9:18 AM, Thilo Goetz <tw...@gmx.de> wrote:

> You don't want to allocate a max heap size of 500M just because
> you may need one that big.  You don't even want to allocate 10M
> ahead of time because if you have many small documents, you can
> do more parallel processing.  So no, I can't specify a large enough
> heap at start-up and yes, the heap most certainly has to shrink
> on CAS reset.


Sounds like your scenario has multiple threads, each with at least one CAS,
processing a mixed size of documents. Either there is enough Java heap space
to process multiple large documents at the same time or not. Pre-allocating
the CAS heap space and not letting them grow enables soft processing
failures of large documents rather than the unfortunate failure of the
entire JVM.

Can you say more about the scenario(s) we are optimizing for?

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.

Eddie Epstein wrote:
> On Wed, Jul 9, 2008 at 1:51 AM, Thilo Goetz <tw...@gmx.de> wrote:
> 
>> Nothing so easy.  The CAS heap is one large int array.  We grow it
>> by allocating a new array with the new desired size and copying the
>> old values over to the new one.  There are several issues with this
>> method:
>>
>> * Copying the data takes a surprisingly long time.  There's a test
>> case in core that does nothing but add new FSs to the CAS, a lot of
>> them.  Marshall complained about how long it took to run when I
>> added it (about 20s on my machine).  If you profile that test case,
>> you will see that the vast majority of time is spent in copying
>> data from an old heap to a new heap.  If the CAS becomes sufficiently
>> large (in the hundreds of MBs), the time it takes to actually add
>> FSs to the CAS is completely dwarfed by the time it takes for the
>> heap to grow.
>>
>> * The heap lives in a single large array, and a new single large
>> array is allocated every time the heap grows.  This is a challenge
>> for the jvm as it allocates this array in a contiguous block of
>> memory.  So there must be enough contiguous space on the jvm heap,
>> which likely means a full heap compaction before a new large array
>> can be allocated.  Sometimes the jvm fails to allocate that
>> contiguous space, even though there are enough free bytes on the
>> jvm jeap.
>>
>> * Saved the best for last.  When allocating a new array, the old
>> one hangs around till we have copied the data.  So we're using twice
>> the necessary space for some period of time.  That space is often
>> not available.  So any time I see an out-of-memory error for large
>> documents (and it's not a bug in the annotator chain), it happens
>> when the CAS heap grows; not because there isn't enough room for
>> the larger heap, but because the old one is still there as well.
>> The CAS can only grow to about half the size we have memory for
>> because of that issue.
> 
> 
> The situation is more complicated than portrayed. The heap does not have to
> shrink, so the growth penalty is rare and can be eliminated entirely if the
> max necessary size heap is specified at startup. FS allocated in the heap do

You don't want to allocate a max heap size of 500M just because
you may need one that big.  You don't even want to allocate 10M
ahead of time because if you have many small documents, you can
do more parallel processing.  So no, I can't specify a large enough
heap at start-up and yes, the heap most certainly has to shrink
on CAS reset.

> not have any Java object memory overhead. Garbage collection for separate FS
> objects would be [much?] worse than the time it takes currently to clear the
> used part of a CAS heap.

I won't believe this until I see it, but I wasn't suggesting
this so I'm not going to argue the point, either.

> 
> Going forward, one approach to this problem could be not one
>> heap array, but a list of arrays.  Every time we grow the heap,
>> we would just add another array.  That approach solves all the
>> problems mentioned above while being minimally invasive to the
>> way the CAS currently works.  However, it raises a new issue:
>> how do you address cells across several arrays in an efficient
>> manner?  We don't want to improve performance for large docs at
>> the expense of small ones.  So heap addresses might stop being
>> the linear sequence of integers they are today.  Maybe we'll
>> use the high bits to address the array, and the low bits to
>> address cells in a given array.  And there goes the watermark.
>> Maybe this won't be necessary, I don't know at this point.
> 
> 
> Each FS object could include an ID that would allow maintaining a high water
> mark, of course at the expense of another 4 bytes per. With a heap
> constructed from multiple discontiguous arrays, each array could include a
> relative ID. This is not to say that the high water mark is always the right
> approach :)

I'm trying to decrease the memory overhead, not increase it.

> 
> Excellent suggestion, except why not have this discussion now?
>> We just need to put our heads together and figure out how to address
>> this requirement to everybody's satisfaction, case closed.  I'm
>> not disagreeing with the requirement, just the proposed implementation
>> thereof.  Doing this now may save us (ok, me) a lot of trouble later.
> 
> 
> Who is against having the discussion now :)

Marshall seemed to favor a discussion at a later point.  Maybe
I misinterpreted.

> 
> Eddie
> 

Re: Delta CAS

Posted by Eddie Epstein <ea...@gmail.com>.
On Wed, Jul 9, 2008 at 1:51 AM, Thilo Goetz <tw...@gmx.de> wrote:

> Nothing so easy.  The CAS heap is one large int array.  We grow it
> by allocating a new array with the new desired size and copying the
> old values over to the new one.  There are several issues with this
> method:
>
> * Copying the data takes a surprisingly long time.  There's a test
> case in core that does nothing but add new FSs to the CAS, a lot of
> them.  Marshall complained about how long it took to run when I
> added it (about 20s on my machine).  If you profile that test case,
> you will see that the vast majority of time is spent in copying
> data from an old heap to a new heap.  If the CAS becomes sufficiently
> large (in the hundreds of MBs), the time it takes to actually add
> FSs to the CAS is completely dwarfed by the time it takes for the
> heap to grow.
>
> * The heap lives in a single large array, and a new single large
> array is allocated every time the heap grows.  This is a challenge
> for the jvm as it allocates this array in a contiguous block of
> memory.  So there must be enough contiguous space on the jvm heap,
> which likely means a full heap compaction before a new large array
> can be allocated.  Sometimes the jvm fails to allocate that
> contiguous space, even though there are enough free bytes on the
> jvm jeap.
>
> * Saved the best for last.  When allocating a new array, the old
> one hangs around till we have copied the data.  So we're using twice
> the necessary space for some period of time.  That space is often
> not available.  So any time I see an out-of-memory error for large
> documents (and it's not a bug in the annotator chain), it happens
> when the CAS heap grows; not because there isn't enough room for
> the larger heap, but because the old one is still there as well.
> The CAS can only grow to about half the size we have memory for
> because of that issue.


The situation is more complicated than portrayed. The heap does not have to
shrink, so the growth penalty is rare and can be eliminated entirely if the
max necessary size heap is specified at startup. FS allocated in the heap do
not have any Java object memory overhead. Garbage collection for separate FS
objects would be [much?] worse than the time it takes currently to clear the
used part of a CAS heap.

Going forward, one approach to this problem could be not one
> heap array, but a list of arrays.  Every time we grow the heap,
> we would just add another array.  That approach solves all the
> problems mentioned above while being minimally invasive to the
> way the CAS currently works.  However, it raises a new issue:
> how do you address cells across several arrays in an efficient
> manner?  We don't want to improve performance for large docs at
> the expense of small ones.  So heap addresses might stop being
> the linear sequence of integers they are today.  Maybe we'll
> use the high bits to address the array, and the low bits to
> address cells in a given array.  And there goes the watermark.
> Maybe this won't be necessary, I don't know at this point.


Each FS object could include an ID that would allow maintaining a high water
mark, of course at the expense of another 4 bytes per. With a heap
constructed from multiple discontiguous arrays, each array could include a
relative ID. This is not to say that the high water mark is always the right
approach :)

Excellent suggestion, except why not have this discussion now?
> We just need to put our heads together and figure out how to address
> this requirement to everybody's satisfaction, case closed.  I'm
> not disagreeing with the requirement, just the proposed implementation
> thereof.  Doing this now may save us (ok, me) a lot of trouble later.


Who is against having the discussion now :)

Eddie

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Pretty much what I had in mind.  Don't forget that
ints are signed, so unless you just drop the high
bit, the watermark may not work.  That's my concern.

I agree with Eddie that a fixed scheme may not work
for all deployments, so we would need to be flexible.

--Thilo

Marshall Schor wrote:
> Here's a suggestion suggested by previous posts, and common hardware 
> design for segmented memory.
> 
> Take the int values that represent feature structure (fs) references.  
> Today, these are positive numbers from 1 (I think) to around 4 billion.  
> These values are used directly as an index into the heap.
> 
> Change this to split the bits in these int values into two parts, let's 
> call them upper and lower.  For example
> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
> 
> where the xxx's are the upper bits (each x represents a hex digit), and 
> the y's the lower bits.  The y's in this case can represent numbers up 
> to 1 million (approx), and the xxx's represent 4096 values.
> 
> Then allocate the heap using multiple 1 meg entry tables, and store each 
> one in the 4096 entry reference array.  The heap reference would be some 
> bit-wise shifting and indexed lookup in addition to what we have now and 
> would probably be very fast, and could be optimized for the xxx=0 case 
> to be even faster.
> 
> This breaks heaps of over 1 meg into separate parts, which would make 
> them more managable, I think, and keeps the high-water mark method 
> viable, too.
> 
> Opinions?
> 
> -Marshall
> 

Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
On Tue, Jul 15, 2008 at 4:28 AM, Thilo Goetz <tw...@gmx.de> wrote:

> Bhavani Iyer wrote:
>
>> OK I agree. What's required is something like the following.
>>
>>  /** sets the high water mark and returns the marker object. */
>>  Marker getHighWaterMark();
>>
>
> How about just getMarker(), since that is what it does.
> Sounds good.
>
>>
>>  /** default to false (disabled) and enabled when high water mark is set
>> via
>> above api. */
>>  boolean isDeltaCasJournalingEnabled();
>>
>
> Why would getMarker() enable such a setting?  Why do we need this
> API at all?  The journaling should be enabled by a performance
> tuning setting, like the other global options we have.  Who else
> needs to know about it other than the CAS?
>


> You're right.
>
>>
>>  public interface Marker {
>>     boolean isAboveHighWaterMark(FeatureStructure fs);
>>  }
>>
>
> How about isNew()?


      This sounds good too.



>
> --Thilo
>
>   Bhavani

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Bhavani Iyer wrote:
> OK I agree. What's required is something like the following.
> 
>   /** sets the high water mark and returns the marker object. */
>   Marker getHighWaterMark();

How about just getMarker(), since that is what it does.

> 
>  /** default to false (disabled) and enabled when high water mark is set via
> above api. */
>   boolean isDeltaCasJournalingEnabled();

Why would getMarker() enable such a setting?  Why do we need this
API at all?  The journaling should be enabled by a performance
tuning setting, like the other global options we have.  Who else
needs to know about it other than the CAS?

> 
>   public interface Marker {
>      boolean isAboveHighWaterMark(FeatureStructure fs);
>   }

How about isNew()?

--Thilo


Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
OK I agree. What's required is something like the following.

  /** sets the high water mark and returns the marker object. */
  Marker getHighWaterMark();

 /** default to false (disabled) and enabled when high water mark is set via
above api. */
  boolean isDeltaCasJournalingEnabled();

  public interface Marker {
     boolean isAboveHighWaterMark(FeatureStructure fs);
  }

  The overhead is the call to isDeltaCasJournalingEnabled()

On Mon, Jul 14, 2008 at 10:40 AM, Thilo Goetz <tw...@gmx.de> wrote:

> Bhavani Iyer wrote:
>
>> OK sounds like the suggested improvements to the CAS heap design would
>> still
>> preserve the high water
>> mark mechanism for identifying new FSs as those added after the mark.  Is
>> this correct ?
>>
>
> No.  My conclusion was that we'll create a CAS API that returns
> a returns a marker object which may later be used to query the
> CAS about certain FSs and when they were created.  This object
> will be opaque to CAS users and transient in nature.  Please feel
> free to make a suggestion for such an API to make sure your
> requirements are covered.
>
> > If so, implementation can start. Should there a branch
>
>> created for this work ?
>>
>
> I don't see why we need a branch for this.
>
>
>> The other main concern discussed was the overhead for core UIMA use
>> without
>> remoting. There should be no
>> measureable overhead since there will be one int compare on calls to set
>> feature value and add to index
>> and no impact on accessing FS values.
>>
>
> Please explain your design.  I expect that there'll be a
> global setting, so at most a boolean is checked?
>
>
>
>> If the overhead turns out to an issue, we could still work around it with
>> a
>> separate class implementing
>> CAS with journaling or a wrapper class as suggested before.
>>
>> Bhavani
>>
>> On Thu, Jul 10, 2008 at 12:57 PM, Marshall Schor <ms...@schor.com> wrote:
>>
>>  Thilo Goetz wrote:
>>>
>>>  Eddie Epstein wrote:
>>>>
>>>>  No opinions, but a few observations:
>>>>>
>>>>> 1M is way too big for some applications that need very small, but very
>>>>> many
>>>>> CASes.
>>>>>
>>>>>  I agree.
>>>>
>>>>  How about treating the 1st 1 mb segment with the same approach as the
>>> heap
>>> is now - providing the ability to start small, and expanding it (by
>>> reallocating and copying) until it gets to 1 mb?
>>>
>>> -Marshall
>>>
>>>
>>>  Large arrays may be bigger than whatever segment size is chosen, making
>>>>> segment management a bit more complicated.
>>>>>
>>>>> There will be holes at the top of every segment when the next FS
>>>>> doesn't
>>>>> fit.
>>>>>
>>>>>  Not necessarily.  Why couldn't you spread FSs and arrays
>>>> across segments?
>>>>
>>>>
>>>>  Eddie
>>>>>
>>>>> On Wed, Jul 9, 2008 at 2:37 PM, Marshall Schor <ms...@schor.com> wrote:
>>>>>
>>>>>  Here's a suggestion suggested by previous posts, and common hardware
>>>>>
>>>>>> design
>>>>>> for segmented memory.
>>>>>>
>>>>>> Take the int values that represent feature structure (fs) references.
>>>>>>  Today, these are positive numbers from 1 (I think) to around 4
>>>>>> billion.
>>>>>>  These values are used directly as an index into the heap.
>>>>>>
>>>>>> Change this to split the bits in these int values into two parts,
>>>>>> let's
>>>>>> call them upper and lower.  For example
>>>>>> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
>>>>>>
>>>>>> where the xxx's are the upper bits (each x represents a hex digit),
>>>>>> and
>>>>>> the
>>>>>> y's the lower bits.  The y's in this case can represent numbers up to
>>>>>> 1
>>>>>> million (approx), and the xxx's represent 4096 values.
>>>>>>
>>>>>> Then allocate the heap using multiple 1 meg entry tables, and store
>>>>>> each
>>>>>> one in the 4096 entry reference array.  The heap reference would be
>>>>>> some
>>>>>> bit-wise shifting and indexed lookup in addition to what we have now
>>>>>> and
>>>>>> would probably be very fast, and could be optimized for the xxx=0 case
>>>>>> to be
>>>>>> even faster.
>>>>>>
>>>>>> This breaks heaps of over 1 meg into separate parts, which would make
>>>>>> them
>>>>>> more managable, I think, and keeps the high-water mark method viable,
>>>>>> too.
>>>>>>
>>>>>> Opinions?
>>>>>>
>>>>>> -Marshall
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>
>>

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Bhavani Iyer wrote:
> OK sounds like the suggested improvements to the CAS heap design would still
> preserve the high water
> mark mechanism for identifying new FSs as those added after the mark.  Is
> this correct ? 

No.  My conclusion was that we'll create a CAS API that returns
a returns a marker object which may later be used to query the
CAS about certain FSs and when they were created.  This object
will be opaque to CAS users and transient in nature.  Please feel
free to make a suggestion for such an API to make sure your
requirements are covered.

 > If so, implementation can start. Should there a branch
> created for this work ?

I don't see why we need a branch for this.

> 
> The other main concern discussed was the overhead for core UIMA use without
> remoting. There should be no
> measureable overhead since there will be one int compare on calls to set
> feature value and add to index
> and no impact on accessing FS values.

Please explain your design.  I expect that there'll be a
global setting, so at most a boolean is checked?

> 
> If the overhead turns out to an issue, we could still work around it with a
> separate class implementing
> CAS with journaling or a wrapper class as suggested before.
> 
> Bhavani
> 
> On Thu, Jul 10, 2008 at 12:57 PM, Marshall Schor <ms...@schor.com> wrote:
> 
>> Thilo Goetz wrote:
>>
>>> Eddie Epstein wrote:
>>>
>>>> No opinions, but a few observations:
>>>>
>>>> 1M is way too big for some applications that need very small, but very
>>>> many
>>>> CASes.
>>>>
>>> I agree.
>>>
>> How about treating the 1st 1 mb segment with the same approach as the heap
>> is now - providing the ability to start small, and expanding it (by
>> reallocating and copying) until it gets to 1 mb?
>>
>> -Marshall
>>
>>
>>>> Large arrays may be bigger than whatever segment size is chosen, making
>>>> segment management a bit more complicated.
>>>>
>>>> There will be holes at the top of every segment when the next FS doesn't
>>>> fit.
>>>>
>>> Not necessarily.  Why couldn't you spread FSs and arrays
>>> across segments?
>>>
>>>
>>>> Eddie
>>>>
>>>> On Wed, Jul 9, 2008 at 2:37 PM, Marshall Schor <ms...@schor.com> wrote:
>>>>
>>>>  Here's a suggestion suggested by previous posts, and common hardware
>>>>> design
>>>>> for segmented memory.
>>>>>
>>>>> Take the int values that represent feature structure (fs) references.
>>>>>  Today, these are positive numbers from 1 (I think) to around 4 billion.
>>>>>  These values are used directly as an index into the heap.
>>>>>
>>>>> Change this to split the bits in these int values into two parts, let's
>>>>> call them upper and lower.  For example
>>>>> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
>>>>>
>>>>> where the xxx's are the upper bits (each x represents a hex digit), and
>>>>> the
>>>>> y's the lower bits.  The y's in this case can represent numbers up to 1
>>>>> million (approx), and the xxx's represent 4096 values.
>>>>>
>>>>> Then allocate the heap using multiple 1 meg entry tables, and store each
>>>>> one in the 4096 entry reference array.  The heap reference would be some
>>>>> bit-wise shifting and indexed lookup in addition to what we have now and
>>>>> would probably be very fast, and could be optimized for the xxx=0 case
>>>>> to be
>>>>> even faster.
>>>>>
>>>>> This breaks heaps of over 1 meg into separate parts, which would make
>>>>> them
>>>>> more managable, I think, and keeps the high-water mark method viable,
>>>>> too.
>>>>>
>>>>> Opinions?
>>>>>
>>>>> -Marshall
>>>>>
>>>>>
>>>>>
>>>>>
>>>
> 

Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
OK sounds like the suggested improvements to the CAS heap design would still
preserve the high water
mark mechanism for identifying new FSs as those added after the mark.  Is
this correct ? If so, implementation can start. Should there a branch
created for this work ?

The other main concern discussed was the overhead for core UIMA use without
remoting. There should be no
measureable overhead since there will be one int compare on calls to set
feature value and add to index
and no impact on accessing FS values.

If the overhead turns out to an issue, we could still work around it with a
separate class implementing
CAS with journaling or a wrapper class as suggested before.

Bhavani

On Thu, Jul 10, 2008 at 12:57 PM, Marshall Schor <ms...@schor.com> wrote:

> Thilo Goetz wrote:
>
>> Eddie Epstein wrote:
>>
>>> No opinions, but a few observations:
>>>
>>> 1M is way too big for some applications that need very small, but very
>>> many
>>> CASes.
>>>
>>
>> I agree.
>>
> How about treating the 1st 1 mb segment with the same approach as the heap
> is now - providing the ability to start small, and expanding it (by
> reallocating and copying) until it gets to 1 mb?
>
> -Marshall
>
>
>>
>>> Large arrays may be bigger than whatever segment size is chosen, making
>>> segment management a bit more complicated.
>>>
>>> There will be holes at the top of every segment when the next FS doesn't
>>> fit.
>>>
>>
>> Not necessarily.  Why couldn't you spread FSs and arrays
>> across segments?
>>
>>
>>> Eddie
>>>
>>> On Wed, Jul 9, 2008 at 2:37 PM, Marshall Schor <ms...@schor.com> wrote:
>>>
>>>  Here's a suggestion suggested by previous posts, and common hardware
>>>> design
>>>> for segmented memory.
>>>>
>>>> Take the int values that represent feature structure (fs) references.
>>>>  Today, these are positive numbers from 1 (I think) to around 4 billion.
>>>>  These values are used directly as an index into the heap.
>>>>
>>>> Change this to split the bits in these int values into two parts, let's
>>>> call them upper and lower.  For example
>>>> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
>>>>
>>>> where the xxx's are the upper bits (each x represents a hex digit), and
>>>> the
>>>> y's the lower bits.  The y's in this case can represent numbers up to 1
>>>> million (approx), and the xxx's represent 4096 values.
>>>>
>>>> Then allocate the heap using multiple 1 meg entry tables, and store each
>>>> one in the 4096 entry reference array.  The heap reference would be some
>>>> bit-wise shifting and indexed lookup in addition to what we have now and
>>>> would probably be very fast, and could be optimized for the xxx=0 case
>>>> to be
>>>> even faster.
>>>>
>>>> This breaks heaps of over 1 meg into separate parts, which would make
>>>> them
>>>> more managable, I think, and keeps the high-water mark method viable,
>>>> too.
>>>>
>>>> Opinions?
>>>>
>>>> -Marshall
>>>>
>>>>
>>>>
>>>>
>>>
>>
>>
>

Re: Delta CAS

Posted by Marshall Schor <ms...@schor.com>.
Thilo Goetz wrote:
> Eddie Epstein wrote:
>> No opinions, but a few observations:
>>
>> 1M is way too big for some applications that need very small, but 
>> very many
>> CASes.
>
> I agree.
How about treating the 1st 1 mb segment with the same approach as the 
heap is now - providing the ability to start small, and expanding it (by 
reallocating and copying) until it gets to 1 mb?

-Marshall
>
>>
>> Large arrays may be bigger than whatever segment size is chosen, making
>> segment management a bit more complicated.
>>
>> There will be holes at the top of every segment when the next FS doesn't
>> fit.
>
> Not necessarily.  Why couldn't you spread FSs and arrays
> across segments?
>
>>
>> Eddie
>>
>> On Wed, Jul 9, 2008 at 2:37 PM, Marshall Schor <ms...@schor.com> wrote:
>>
>>> Here's a suggestion suggested by previous posts, and common hardware 
>>> design
>>> for segmented memory.
>>>
>>> Take the int values that represent feature structure (fs) references.
>>>  Today, these are positive numbers from 1 (I think) to around 4 
>>> billion.
>>>  These values are used directly as an index into the heap.
>>>
>>> Change this to split the bits in these int values into two parts, let's
>>> call them upper and lower.  For example
>>> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
>>>
>>> where the xxx's are the upper bits (each x represents a hex digit), 
>>> and the
>>> y's the lower bits.  The y's in this case can represent numbers up to 1
>>> million (approx), and the xxx's represent 4096 values.
>>>
>>> Then allocate the heap using multiple 1 meg entry tables, and store 
>>> each
>>> one in the 4096 entry reference array.  The heap reference would be 
>>> some
>>> bit-wise shifting and indexed lookup in addition to what we have now 
>>> and
>>> would probably be very fast, and could be optimized for the xxx=0 
>>> case to be
>>> even faster.
>>>
>>> This breaks heaps of over 1 meg into separate parts, which would 
>>> make them
>>> more managable, I think, and keeps the high-water mark method 
>>> viable, too.
>>>
>>> Opinions?
>>>
>>> -Marshall
>>>
>>>
>>>
>>
>
>


Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Eddie Epstein wrote:
> No opinions, but a few observations:
> 
> 1M is way too big for some applications that need very small, but very many
> CASes.

I agree.

> 
> Large arrays may be bigger than whatever segment size is chosen, making
> segment management a bit more complicated.
> 
> There will be holes at the top of every segment when the next FS doesn't
> fit.

Not necessarily.  Why couldn't you spread FSs and arrays
across segments?

> 
> Eddie
> 
> On Wed, Jul 9, 2008 at 2:37 PM, Marshall Schor <ms...@schor.com> wrote:
> 
>> Here's a suggestion suggested by previous posts, and common hardware design
>> for segmented memory.
>>
>> Take the int values that represent feature structure (fs) references.
>>  Today, these are positive numbers from 1 (I think) to around 4 billion.
>>  These values are used directly as an index into the heap.
>>
>> Change this to split the bits in these int values into two parts, let's
>> call them upper and lower.  For example
>> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
>>
>> where the xxx's are the upper bits (each x represents a hex digit), and the
>> y's the lower bits.  The y's in this case can represent numbers up to 1
>> million (approx), and the xxx's represent 4096 values.
>>
>> Then allocate the heap using multiple 1 meg entry tables, and store each
>> one in the 4096 entry reference array.  The heap reference would be some
>> bit-wise shifting and indexed lookup in addition to what we have now and
>> would probably be very fast, and could be optimized for the xxx=0 case to be
>> even faster.
>>
>> This breaks heaps of over 1 meg into separate parts, which would make them
>> more managable, I think, and keeps the high-water mark method viable, too.
>>
>> Opinions?
>>
>> -Marshall
>>
>>
>>
> 

Re: Delta CAS

Posted by Eddie Epstein <ea...@gmail.com>.
No opinions, but a few observations:

1M is way too big for some applications that need very small, but very many
CASes.

Large arrays may be bigger than whatever segment size is chosen, making
segment management a bit more complicated.

There will be holes at the top of every segment when the next FS doesn't
fit.

Eddie

On Wed, Jul 9, 2008 at 2:37 PM, Marshall Schor <ms...@schor.com> wrote:

> Here's a suggestion suggested by previous posts, and common hardware design
> for segmented memory.
>
> Take the int values that represent feature structure (fs) references.
>  Today, these are positive numbers from 1 (I think) to around 4 billion.
>  These values are used directly as an index into the heap.
>
> Change this to split the bits in these int values into two parts, let's
> call them upper and lower.  For example
> xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy
>
> where the xxx's are the upper bits (each x represents a hex digit), and the
> y's the lower bits.  The y's in this case can represent numbers up to 1
> million (approx), and the xxx's represent 4096 values.
>
> Then allocate the heap using multiple 1 meg entry tables, and store each
> one in the 4096 entry reference array.  The heap reference would be some
> bit-wise shifting and indexed lookup in addition to what we have now and
> would probably be very fast, and could be optimized for the xxx=0 case to be
> even faster.
>
> This breaks heaps of over 1 meg into separate parts, which would make them
> more managable, I think, and keeps the high-water mark method viable, too.
>
> Opinions?
>
> -Marshall
>
>
>

Re: Delta CAS

Posted by Marshall Schor <ms...@schor.com>.
Here's a suggestion suggested by previous posts, and common hardware 
design for segmented memory.

Take the int values that represent feature structure (fs) references.  
Today, these are positive numbers from 1 (I think) to around 4 billion.  
These values are used directly as an index into the heap.

Change this to split the bits in these int values into two parts, let's 
call them upper and lower.  For example
xxxx xxxx xxxx yyyy yyyy yyyy yyyy yyyy

where the xxx's are the upper bits (each x represents a hex digit), and 
the y's the lower bits.  The y's in this case can represent numbers up 
to 1 million (approx), and the xxx's represent 4096 values.

Then allocate the heap using multiple 1 meg entry tables, and store each 
one in the 4096 entry reference array.  The heap reference would be some 
bit-wise shifting and indexed lookup in addition to what we have now and 
would probably be very fast, and could be optimized for the xxx=0 case 
to be even faster.

This breaks heaps of over 1 meg into separate parts, which would make 
them more managable, I think, and keeps the high-water mark method 
viable, too.

Opinions?

-Marshall



Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Eddie Epstein wrote:
> On Tue, Jul 8, 2008 at 4:32 PM, Thilo Goetz <tw...@gmx.de> wrote:
> 
>> Precisely.  It's an implementation detail of the CAS heap that
>> we should be able to change -- that we must be able to change
>> if we would like to improve on the heap.  The CAS heap and
>> in particular the way it grows is a major performance bottleneck
>> for large documents.  If we have other parts of UIMA depend on
>> the (bad) implementation details now, we'll never be able to
>> improve on the design.
> 
> 
> Can you give details on how CAS heap growth is a major bottleneck for large
> documents? Do we have specific scenarios that can be used to measure current
> heap performance and potential fixes?
> 

Nothing so easy.  The CAS heap is one large int array.  We grow it
by allocating a new array with the new desired size and copying the
old values over to the new one.  There are several issues with this
method:

* Copying the data takes a surprisingly long time.  There's a test
case in core that does nothing but add new FSs to the CAS, a lot of
them.  Marshall complained about how long it took to run when I
added it (about 20s on my machine).  If you profile that test case,
you will see that the vast majority of time is spent in copying
data from an old heap to a new heap.  If the CAS becomes sufficiently
large (in the hundreds of MBs), the time it takes to actually add
FSs to the CAS is completely dwarfed by the time it takes for the
heap to grow.

* The heap lives in a single large array, and a new single large
array is allocated every time the heap grows.  This is a challenge
for the jvm as it allocates this array in a contiguous block of
memory.  So there must be enough contiguous space on the jvm heap,
which likely means a full heap compaction before a new large array
can be allocated.  Sometimes the jvm fails to allocate that
contiguous space, even though there are enough free bytes on the
jvm jeap.

* Saved the best for last.  When allocating a new array, the old
one hangs around till we have copied the data.  So we're using twice
the necessary space for some period of time.  That space is often
not available.  So any time I see an out-of-memory error for large
documents (and it's not a bug in the annotator chain), it happens
when the CAS heap grows; not because there isn't enough room for
the larger heap, but because the old one is still there as well.
The CAS can only grow to about half the size we have memory for
because of that issue.

Now these things may not be issues for everybody.  You may not
process large documents.  Your analysis may be so slow that you
don't notice those things.  You may be serializing CASes to XML
and sending them over the network, which completely dwarfs the
performance issues mentioned above.

I live in a world where both memory and CPU cycles are at a
premium, *and* we process large documents.  So I do care.

Going forward, one approach to this problem could be not one
heap array, but a list of arrays.  Every time we grow the heap,
we would just add another array.  That approach solves all the
problems mentioned above while being minimally invasive to the
way the CAS currently works.  However, it raises a new issue:
how do you address cells across several arrays in an efficient
manner?  We don't want to improve performance for large docs at
the expense of small ones.  So heap addresses might stop being
the linear sequence of integers they are today.  Maybe we'll
use the high bits to address the array, and the low bits to
address cells in a given array.  And there goes the watermark.
Maybe this won't be necessary, I don't know at this point.

Now what?  Let me quote Adam from another message:

"I think what's happening here is that XmiCasSerializer has a
requirement on the CAS that it can efficiently know which FS are new
(created since some mark - when the CAS was received at a service in
this case).  Currently this is doable using the FS addresses, but if
that were no longer the case, we could build a different marking
mechanism that does the same thing.  So I think I'm agreeing with
Marshall there."

Excellent suggestion, except why not have this discussion now?
We just need to put our heads together and figure out how to address
this requirement to everybody's satisfaction, case closed.  I'm
not disagreeing with the requirement, just the proposed implementation
thereof.  Doing this now may save us (ok, me) a lot of trouble later.

--Thilo




Re: Delta CAS

Posted by Eddie Epstein <ea...@gmail.com>.
On Tue, Jul 8, 2008 at 4:32 PM, Thilo Goetz <tw...@gmx.de> wrote:

> Precisely.  It's an implementation detail of the CAS heap that
> we should be able to change -- that we must be able to change
> if we would like to improve on the heap.  The CAS heap and
> in particular the way it grows is a major performance bottleneck
> for large documents.  If we have other parts of UIMA depend on
> the (bad) implementation details now, we'll never be able to
> improve on the design.


Can you give details on how CAS heap growth is a major bottleneck for large
documents? Do we have specific scenarios that can be used to measure current
heap performance and potential fixes?

Re: Delta CAS

Posted by Adam Lally <al...@alum.rpi.edu>.
On Tue, Jul 8, 2008 at 6:08 PM, Marshall Schor <ms...@schor.com> wrote:
>> The CAS heap and
>> in particular the way it grows is a major performance bottleneck
>> for large documents.  If we have other parts of UIMA depend on
>> the (bad) implementation details now, we'll never be able to
>> improve on the design.
>
> Hmmm, I guess I was thinking that if we wanted to change this in the future,
> we could.  I agree it would be more difficult;  we've changed things like
> this before using the refactoring tools that let you see pretty clearly
> various dependencies...
>

I think what's happening here is that XmiCasSerializer has a
requirement on the CAS that it can efficiently know which FS are new
(created since some mark - when the CAS was received at a service in
this case).  Currently this is doable using the FS addresses, but if
that were no longer the case, we could build a different marking
mechanism that does the same thing.  So I think I'm agreeing with
Marshall there.

That said, if checking an FS against a set of known FS's that were
input to the service isn't a significant performance hit, then maybe
that is a more flexible way to go, which would avoid having a problem
with this in the future.  (That set already exists - it is built by
the deserializer and used to ensure consistent ids.)

Hm - I seem to have added one more voice to the chorus of people
recently requesting seeing some performance numbers before making a
design decision. ;)

  -Adam

Re: Delta CAS

Posted by Marshall Schor <ms...@schor.com>.
Thilo Goetz wrote:
> Marshall Schor wrote:
>> Thilo Goetz wrote:
>>> Bhavani Iyer wrote:
>>>> Hi Thilo,
>>>>
>>>> There are two separate requirements being addressed here:
>>>> 1) delta CAS for optimizing remote services.
>>>>      Here its agreed that there should be no measurable overhead 
>>>> when there
>>>> is no remoting.
>>>>      There will be a single test against the high water mark.  The 
>>>> high
>>>> water mark defaults to 0.  Only when the high
>>>>      water mark is set to a value greater than 0 is logging of  CAS
>>>> operations on FSs below the high water mark enabled.
>>>> 2)  Journaling for debugging  aggregate components.
>>>>     This capability is for Core UIMA as well as for remote 
>>>> services. This
>>>> will have some additional overhead and will be have to be 
>>>> explicitly enabled
>>>> by the aggregate controller for a component. Basically the aggregate
>>>> controller enables journaling by setting the high water mark before 
>>>> the call
>>>> to process.
>>>>
>>>> Regarding using the high water mark, this is already being used for 
>>>> merging
>>>> CAS.
>>>
>>> That's not a good thing, and certainly no justification of using
>>> the same design here.  
>> Can you say more about why this is not a good thing?  I see it as an 
>> internal design detail.
>
> Precisely.  It's an implementation detail of the CAS heap that
> we should be able to change -- that we must be able to change
> if we would like to improve on the heap.  
We could change it if we found a better approach.
> The CAS heap and
> in particular the way it grows is a major performance bottleneck
> for large documents.  If we have other parts of UIMA depend on
> the (bad) implementation details now, we'll never be able to
> improve on the design.
Hmmm, I guess I was thinking that if we wanted to change this in the 
future, we could.  I agree it would be more difficult;  we've changed 
things like this before using the refactoring tools that let you see 
pretty clearly various dependencies...

-Marshall

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Marshall Schor wrote:
> Thilo Goetz wrote:
>> Bhavani Iyer wrote:
>>> Hi Thilo,
>>>
>>> There are two separate requirements being addressed here:
>>> 1) delta CAS for optimizing remote services.
>>>      Here its agreed that there should be no measurable overhead when 
>>> there
>>> is no remoting.
>>>      There will be a single test against the high water mark.  The high
>>> water mark defaults to 0.  Only when the high
>>>      water mark is set to a value greater than 0 is logging of  CAS
>>> operations on FSs below the high water mark enabled.
>>> 2)  Journaling for debugging  aggregate components.
>>>     This capability is for Core UIMA as well as for remote services. 
>>> This
>>> will have some additional overhead and will be have to be explicitly 
>>> enabled
>>> by the aggregate controller for a component. Basically the aggregate
>>> controller enables journaling by setting the high water mark before 
>>> the call
>>> to process.
>>>
>>> Regarding using the high water mark, this is already being used for 
>>> merging
>>> CAS.
>>
>> That's not a good thing, and certainly no justification of using
>> the same design here.  
> Can you say more about why this is not a good thing?  I see it as an 
> internal design detail.

Precisely.  It's an implementation detail of the CAS heap that
we should be able to change -- that we must be able to change
if we would like to improve on the heap.  The CAS heap and
in particular the way it grows is a major performance bottleneck
for large documents.  If we have other parts of UIMA depend on
the (bad) implementation details now, we'll never be able to
improve on the design.

>> I thought you needed to keep a list of the
>> added FSs anyway.
> I don't think such a list is kept.  There is a list of modified FSs 
> below below the high water mark, and a list of things 
> added/removed/modified with the indexes (in other words, if new feature 
> structures were added, but not indexed, they would not be in any list).
> 
> -Marshall


Re: Delta CAS

Posted by Marshall Schor <ms...@schor.com>.
Thilo Goetz wrote:
> Bhavani Iyer wrote:
>> Hi Thilo,
>>
>> There are two separate requirements being addressed here:
>> 1) delta CAS for optimizing remote services.
>>      Here its agreed that there should be no measurable overhead when 
>> there
>> is no remoting.
>>      There will be a single test against the high water mark.  The high
>> water mark defaults to 0.  Only when the high
>>      water mark is set to a value greater than 0 is logging of  CAS
>> operations on FSs below the high water mark enabled.
>> 2)  Journaling for debugging  aggregate components.
>>     This capability is for Core UIMA as well as for remote services. 
>> This
>> will have some additional overhead and will be have to be explicitly 
>> enabled
>> by the aggregate controller for a component. Basically the aggregate
>> controller enables journaling by setting the high water mark before 
>> the call
>> to process.
>>
>> Regarding using the high water mark, this is already being used for 
>> merging
>> CAS.
>
> That's not a good thing, and certainly no justification of using
> the same design here.  
Can you say more about why this is not a good thing?  I see it as an 
internal design detail.
> I thought you needed to keep a list of the
> added FSs anyway.
I don't think such a list is kept.  There is a list of modified FSs 
below below the high water mark, and a list of things 
added/removed/modified with the indexes (in other words, if new feature 
structures were added, but not indexed, they would not be in any list).

-Marshall

Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
That's not a good thing, and certainly no justification of using
the same design here.

     Not sure what you are refering to here.

I thought you needed to keep a list of the
added FSs anyway.  Why do you need to rely on the max FS ID?

    Not if  we use the high water mark (max FS is at start) which is less
overhead
    The list is implicit in that the added FSs are those with ids over the
high water mark

On Tue, Jul 8, 2008 at 3:06 PM, Thilo Goetz <tw...@gmx.de> wrote:

> Bhavani Iyer wrote:
>
>> Hi Thilo,
>>
>> There are two separate requirements being addressed here:
>> 1) delta CAS for optimizing remote services.
>>     Here its agreed that there should be no measurable overhead when there
>> is no remoting.
>>     There will be a single test against the high water mark.  The high
>> water mark defaults to 0.  Only when the high
>>     water mark is set to a value greater than 0 is logging of  CAS
>> operations on FSs below the high water mark enabled.
>> 2)  Journaling for debugging  aggregate components.
>>    This capability is for Core UIMA as well as for remote services. This
>> will have some additional overhead and will be have to be explicitly
>> enabled
>> by the aggregate controller for a component. Basically the aggregate
>> controller enables journaling by setting the high water mark before the
>> call
>> to process.
>>
>> Regarding using the high water mark, this is already being used for
>> merging
>> CAS.
>>
>
> That's not a good thing, and certainly no justification of using
> the same design here.  I thought you needed to keep a list of the
> added FSs anyway.  Why do you need to rely on the max FS ID?
>
> --Thilo
>
>
>
>> Bhavani
>> On Tue, Jul 8, 2008 at 10:22 AM, Thilo Goetz <tw...@gmx.de> wrote:
>>
>>  My immediate reactions are:
>>>
>>> - you should be forced to turn this on if you want to
>>> use it.  By default it should be off.  There should be
>>> no overhead for UIMA instances that don't do any remoting.
>>> You could implement a CAS wrapper that delegates to the
>>> real CAS and does the bookkeeping.  The newCAS() functions
>>> can return the wrapper CASes when DeltaCAS is enabled.
>>>
>>> - I've gotten over wanting to improve the CAS implementation,
>>> but I think the watermark thing is not a good idea.  It
>>> totally relies on the current CAS heap implementation and
>>> will prevent any improvements in this area.  If there is
>>> another way of doing it, that would be great.
>>>
>>> --Thilo
>>>
>>>
>>> Bhavani Iyer wrote:
>>>
>>>  We're planning to start  the implementation to support Delta CAS as
>>>> described here:
>>>>
>>>>
>>>> http://cwiki.apache.org/UIMA/reducing-overhead-for-remote-service-calls.html
>>>>
>>>> The current thinking on the design is described below and we would like
>>>> some
>>>> feedback.
>>>> *
>>>> CAS Activity Journal*
>>>> In order to be able to export as XMI only the updates to the CAS, we
>>>> need
>>>> to
>>>> maintain
>>>> a journal associated with the CAS to track these update activities.  The
>>>> journal will
>>>> contain the following information:
>>>>
>>>> 1) To identify new FSs, the max FS id at the start of processing is
>>>> saved
>>>> .
>>>> New FS added
>>>>    would have ids above this high water mark.
>>>> 2) To identify which pre-existing FSs were modified,, a list of ids of
>>>> pre-existing FSs that have been changed.
>>>> 3)  To track updates to the Views, a list of FS ids added, removed and
>>>> reindexed in the index repository of pre-existing Views.
>>>>
>>>> The CAS APIs  that set feature values as well as APIs that add or remove
>>>> from the
>>>> index repository will be modified to update the CAS activity journal.
>>>> The overhead is expected to be be minimal since it will simply add an FS
>>>> id
>>>> to the
>>>> appropriate list as mentioned above.
>>>>
>>>> *Delta CAS XMI serialization*
>>>> A more compact representation of the delta CAS data than the proposed
>>>> XMI:Difference format
>>>> would be preferred for transmitting CAS data when making calls to a
>>>> remote
>>>> service.
>>>>
>>>> Instead, we propose that CAS updates  be serialized in the same format
>>>> as
>>>> the XMI CAS with one modification.
>>>> Additional attributes will be defined in the View element to contain the
>>>> list of
>>>> ids of FSs that were added, deleted and reindexed:
>>>>
>>>> Example of current cas:View
>>>> <cas:View sofa="1" members="8 13 20 26 42"/>
>>>>
>>>> Example of proposed cas:View to support delta CAS
>>>> <cas:View sofa="1" members_added="32"  members_deleted="13 20"
>>>> members_reindexed="26 42" />
>>>>
>>>> XMI deserialization of the delta CAS  will update the CAS as follows:
>>>> 1) create new FS for those elements where xmi:id is above the high water
>>>> mark.
>>>> 2) update the FSs feature values for those elements where xmi:id is
>>>> below
>>>> the high water mark. Note, features
>>>>   missing in the XMI will be set to null.
>>>> 3) Process the view element to add, remove or reindex in the specified
>>>> VIew
>>>> index repository.
>>>>
>>>> Please note that this proposed XMI representation itself does not
>>>> identify
>>>> or mark the CAS as a delta CAS.
>>>> In the context of UIMA AS services, additional properties in the request
>>>> and
>>>> reply messages will
>>>> specify that the XMI contains a delta CAS.
>>>> Applications should not use the API to export a delta CAS to a file for
>>>> later processing without
>>>> taking additional steps to retain the format information.
>>>>
>>>>
>>>> *Delta CAS for debugging*
>>>> To support debugging UIMA aggregates as described here
>>>>  http://cwiki.apache.org/UIMA/improving-uima-debug-capabilities.html
>>>> the delta CAS implementation will be extended as follows:
>>>> 1) the CAS activity journal will be maintained for each component that
>>>> is
>>>> called during aggregate processing.
>>>> 2) an API to enable/disable this extended journaling by component.
>>>> 3) define the XMI representation of the CAS activity journal. Details on
>>>> this will be posted shortly.
>>>>
>>>> We would appreciate comments and suggestions on the proposed changes.
>>>>
>>>> Thanks,
>>>>
>>>> Bhavani
>>>>
>>>>
>>>>
>>
>

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
Bhavani Iyer wrote:
> Hi Thilo,
> 
> There are two separate requirements being addressed here:
> 1) delta CAS for optimizing remote services.
>      Here its agreed that there should be no measurable overhead when there
> is no remoting.
>      There will be a single test against the high water mark.  The high
> water mark defaults to 0.  Only when the high
>      water mark is set to a value greater than 0 is logging of  CAS
> operations on FSs below the high water mark enabled.
> 2)  Journaling for debugging  aggregate components.
>     This capability is for Core UIMA as well as for remote services. This
> will have some additional overhead and will be have to be explicitly enabled
> by the aggregate controller for a component. Basically the aggregate
> controller enables journaling by setting the high water mark before the call
> to process.
> 
> Regarding using the high water mark, this is already being used for merging
> CAS.

That's not a good thing, and certainly no justification of using
the same design here.  I thought you needed to keep a list of the
added FSs anyway.  Why do you need to rely on the max FS ID?

--Thilo

> 
> Bhavani
> On Tue, Jul 8, 2008 at 10:22 AM, Thilo Goetz <tw...@gmx.de> wrote:
> 
>> My immediate reactions are:
>>
>> - you should be forced to turn this on if you want to
>> use it.  By default it should be off.  There should be
>> no overhead for UIMA instances that don't do any remoting.
>> You could implement a CAS wrapper that delegates to the
>> real CAS and does the bookkeeping.  The newCAS() functions
>> can return the wrapper CASes when DeltaCAS is enabled.
>>
>> - I've gotten over wanting to improve the CAS implementation,
>> but I think the watermark thing is not a good idea.  It
>> totally relies on the current CAS heap implementation and
>> will prevent any improvements in this area.  If there is
>> another way of doing it, that would be great.
>>
>> --Thilo
>>
>>
>> Bhavani Iyer wrote:
>>
>>> We're planning to start  the implementation to support Delta CAS as
>>> described here:
>>>
>>> http://cwiki.apache.org/UIMA/reducing-overhead-for-remote-service-calls.html
>>>
>>> The current thinking on the design is described below and we would like
>>> some
>>> feedback.
>>> *
>>> CAS Activity Journal*
>>> In order to be able to export as XMI only the updates to the CAS, we need
>>> to
>>> maintain
>>> a journal associated with the CAS to track these update activities.  The
>>> journal will
>>> contain the following information:
>>>
>>> 1) To identify new FSs, the max FS id at the start of processing is saved
>>> .
>>> New FS added
>>>     would have ids above this high water mark.
>>> 2) To identify which pre-existing FSs were modified,, a list of ids of
>>> pre-existing FSs that have been changed.
>>> 3)  To track updates to the Views, a list of FS ids added, removed and
>>> reindexed in the index repository of pre-existing Views.
>>>
>>> The CAS APIs  that set feature values as well as APIs that add or remove
>>> from the
>>> index repository will be modified to update the CAS activity journal.
>>> The overhead is expected to be be minimal since it will simply add an FS
>>> id
>>> to the
>>> appropriate list as mentioned above.
>>>
>>> *Delta CAS XMI serialization*
>>> A more compact representation of the delta CAS data than the proposed
>>> XMI:Difference format
>>> would be preferred for transmitting CAS data when making calls to a remote
>>> service.
>>>
>>> Instead, we propose that CAS updates  be serialized in the same format as
>>> the XMI CAS with one modification.
>>> Additional attributes will be defined in the View element to contain the
>>> list of
>>> ids of FSs that were added, deleted and reindexed:
>>>
>>> Example of current cas:View
>>> <cas:View sofa="1" members="8 13 20 26 42"/>
>>>
>>> Example of proposed cas:View to support delta CAS
>>> <cas:View sofa="1" members_added="32"  members_deleted="13 20"
>>> members_reindexed="26 42" />
>>>
>>> XMI deserialization of the delta CAS  will update the CAS as follows:
>>> 1) create new FS for those elements where xmi:id is above the high water
>>> mark.
>>> 2) update the FSs feature values for those elements where xmi:id is below
>>> the high water mark. Note, features
>>>    missing in the XMI will be set to null.
>>> 3) Process the view element to add, remove or reindex in the specified
>>> VIew
>>> index repository.
>>>
>>> Please note that this proposed XMI representation itself does not identify
>>> or mark the CAS as a delta CAS.
>>> In the context of UIMA AS services, additional properties in the request
>>> and
>>> reply messages will
>>> specify that the XMI contains a delta CAS.
>>> Applications should not use the API to export a delta CAS to a file for
>>> later processing without
>>> taking additional steps to retain the format information.
>>>
>>>
>>> *Delta CAS for debugging*
>>> To support debugging UIMA aggregates as described here
>>>  http://cwiki.apache.org/UIMA/improving-uima-debug-capabilities.html
>>> the delta CAS implementation will be extended as follows:
>>> 1) the CAS activity journal will be maintained for each component that is
>>> called during aggregate processing.
>>> 2) an API to enable/disable this extended journaling by component.
>>> 3) define the XMI representation of the CAS activity journal. Details on
>>> this will be posted shortly.
>>>
>>> We would appreciate comments and suggestions on the proposed changes.
>>>
>>> Thanks,
>>>
>>> Bhavani
>>>
>>>
> 


Re: Delta CAS

Posted by Bhavani Iyer <bh...@gmail.com>.
Hi Thilo,

There are two separate requirements being addressed here:
1) delta CAS for optimizing remote services.
     Here its agreed that there should be no measurable overhead when there
is no remoting.
     There will be a single test against the high water mark.  The high
water mark defaults to 0.  Only when the high
     water mark is set to a value greater than 0 is logging of  CAS
operations on FSs below the high water mark enabled.
2)  Journaling for debugging  aggregate components.
    This capability is for Core UIMA as well as for remote services. This
will have some additional overhead and will be have to be explicitly enabled
by the aggregate controller for a component. Basically the aggregate
controller enables journaling by setting the high water mark before the call
to process.

Regarding using the high water mark, this is already being used for merging
CAS.

Bhavani
On Tue, Jul 8, 2008 at 10:22 AM, Thilo Goetz <tw...@gmx.de> wrote:

> My immediate reactions are:
>
> - you should be forced to turn this on if you want to
> use it.  By default it should be off.  There should be
> no overhead for UIMA instances that don't do any remoting.
> You could implement a CAS wrapper that delegates to the
> real CAS and does the bookkeeping.  The newCAS() functions
> can return the wrapper CASes when DeltaCAS is enabled.
>
> - I've gotten over wanting to improve the CAS implementation,
> but I think the watermark thing is not a good idea.  It
> totally relies on the current CAS heap implementation and
> will prevent any improvements in this area.  If there is
> another way of doing it, that would be great.
>
> --Thilo
>
>
> Bhavani Iyer wrote:
>
>> We're planning to start  the implementation to support Delta CAS as
>> described here:
>>
>> http://cwiki.apache.org/UIMA/reducing-overhead-for-remote-service-calls.html
>>
>> The current thinking on the design is described below and we would like
>> some
>> feedback.
>> *
>> CAS Activity Journal*
>> In order to be able to export as XMI only the updates to the CAS, we need
>> to
>> maintain
>> a journal associated with the CAS to track these update activities.  The
>> journal will
>> contain the following information:
>>
>> 1) To identify new FSs, the max FS id at the start of processing is saved
>> .
>> New FS added
>>     would have ids above this high water mark.
>> 2) To identify which pre-existing FSs were modified,, a list of ids of
>> pre-existing FSs that have been changed.
>> 3)  To track updates to the Views, a list of FS ids added, removed and
>> reindexed in the index repository of pre-existing Views.
>>
>> The CAS APIs  that set feature values as well as APIs that add or remove
>> from the
>> index repository will be modified to update the CAS activity journal.
>> The overhead is expected to be be minimal since it will simply add an FS
>> id
>> to the
>> appropriate list as mentioned above.
>>
>> *Delta CAS XMI serialization*
>> A more compact representation of the delta CAS data than the proposed
>> XMI:Difference format
>> would be preferred for transmitting CAS data when making calls to a remote
>> service.
>>
>> Instead, we propose that CAS updates  be serialized in the same format as
>> the XMI CAS with one modification.
>> Additional attributes will be defined in the View element to contain the
>> list of
>> ids of FSs that were added, deleted and reindexed:
>>
>> Example of current cas:View
>> <cas:View sofa="1" members="8 13 20 26 42"/>
>>
>> Example of proposed cas:View to support delta CAS
>> <cas:View sofa="1" members_added="32"  members_deleted="13 20"
>> members_reindexed="26 42" />
>>
>> XMI deserialization of the delta CAS  will update the CAS as follows:
>> 1) create new FS for those elements where xmi:id is above the high water
>> mark.
>> 2) update the FSs feature values for those elements where xmi:id is below
>> the high water mark. Note, features
>>    missing in the XMI will be set to null.
>> 3) Process the view element to add, remove or reindex in the specified
>> VIew
>> index repository.
>>
>> Please note that this proposed XMI representation itself does not identify
>> or mark the CAS as a delta CAS.
>> In the context of UIMA AS services, additional properties in the request
>> and
>> reply messages will
>> specify that the XMI contains a delta CAS.
>> Applications should not use the API to export a delta CAS to a file for
>> later processing without
>> taking additional steps to retain the format information.
>>
>>
>> *Delta CAS for debugging*
>> To support debugging UIMA aggregates as described here
>>  http://cwiki.apache.org/UIMA/improving-uima-debug-capabilities.html
>> the delta CAS implementation will be extended as follows:
>> 1) the CAS activity journal will be maintained for each component that is
>> called during aggregate processing.
>> 2) an API to enable/disable this extended journaling by component.
>> 3) define the XMI representation of the CAS activity journal. Details on
>> this will be posted shortly.
>>
>> We would appreciate comments and suggestions on the proposed changes.
>>
>> Thanks,
>>
>> Bhavani
>>
>>

Re: Delta CAS

Posted by Thilo Goetz <tw...@gmx.de>.
My immediate reactions are:

- you should be forced to turn this on if you want to
use it.  By default it should be off.  There should be
no overhead for UIMA instances that don't do any remoting.
You could implement a CAS wrapper that delegates to the
real CAS and does the bookkeeping.  The newCAS() functions
can return the wrapper CASes when DeltaCAS is enabled.

- I've gotten over wanting to improve the CAS implementation,
but I think the watermark thing is not a good idea.  It
totally relies on the current CAS heap implementation and
will prevent any improvements in this area.  If there is
another way of doing it, that would be great.

--Thilo

Bhavani Iyer wrote:
> We're planning to start  the implementation to support Delta CAS as
> described here:
> http://cwiki.apache.org/UIMA/reducing-overhead-for-remote-service-calls.html
> 
> The current thinking on the design is described below and we would like some
> feedback.
> *
> CAS Activity Journal*
> In order to be able to export as XMI only the updates to the CAS, we need to
> maintain
> a journal associated with the CAS to track these update activities.  The
> journal will
> contain the following information:
> 
> 1) To identify new FSs, the max FS id at the start of processing is saved .
> New FS added
>      would have ids above this high water mark.
> 2) To identify which pre-existing FSs were modified,, a list of ids of
> pre-existing FSs that have been changed.
> 3)  To track updates to the Views, a list of FS ids added, removed and
> reindexed in the index repository of pre-existing Views.
> 
> The CAS APIs  that set feature values as well as APIs that add or remove
> from the
> index repository will be modified to update the CAS activity journal.
> The overhead is expected to be be minimal since it will simply add an FS id
> to the
> appropriate list as mentioned above.
> 
> *Delta CAS XMI serialization*
> A more compact representation of the delta CAS data than the proposed
> XMI:Difference format
> would be preferred for transmitting CAS data when making calls to a remote
> service.
> 
> Instead, we propose that CAS updates  be serialized in the same format as
> the XMI CAS with one modification.
> Additional attributes will be defined in the View element to contain the
> list of
> ids of FSs that were added, deleted and reindexed:
> 
> Example of current cas:View
> <cas:View sofa="1" members="8 13 20 26 42"/>
> 
> Example of proposed cas:View to support delta CAS
> <cas:View sofa="1" members_added="32"  members_deleted="13 20"
> members_reindexed="26 42" />
> 
> XMI deserialization of the delta CAS  will update the CAS as follows:
> 1) create new FS for those elements where xmi:id is above the high water
> mark.
> 2) update the FSs feature values for those elements where xmi:id is below
> the high water mark. Note, features
>     missing in the XMI will be set to null.
> 3) Process the view element to add, remove or reindex in the specified VIew
> index repository.
> 
> Please note that this proposed XMI representation itself does not identify
> or mark the CAS as a delta CAS.
> In the context of UIMA AS services, additional properties in the request and
> reply messages will
> specify that the XMI contains a delta CAS.
> Applications should not use the API to export a delta CAS to a file for
> later processing without
> taking additional steps to retain the format information.
> 
> 
> *Delta CAS for debugging*
> To support debugging UIMA aggregates as described here
>  http://cwiki.apache.org/UIMA/improving-uima-debug-capabilities.html
> the delta CAS implementation will be extended as follows:
> 1) the CAS activity journal will be maintained for each component that is
> called during aggregate processing.
> 2) an API to enable/disable this extended journaling by component.
> 3) define the XMI representation of the CAS activity journal. Details on
> this will be posted shortly.
> 
> We would appreciate comments and suggestions on the proposed changes.
> 
> Thanks,
> 
> Bhavani
>