Thanks for the comments, Nick. Ever since you've become involved,
I've started
learning a lot more about Java high performance and parallel programming :-).
I've given some responses below.
On 4/18/2015 6:36 PM, Nick Hill wrote:
Thanks Marshall, have added some responses inline below
Quoting Marshall Schor <[email protected]>:
Re: supporting multiple implementations of the CAS.
The original implementation of the CAS picked a set of space/performance
trade-offs. Some of these were motivated by earlier frameworks
built in C++, by
the state-of-affairs of early Java implementations, etc. The goal
was to create
something that would be attractive to use by the community of
people working in
the field of NLP, who were often concerned with these kinds of things.
Later, JCas was added, to make things easier for people
comfortable in Java.
And later still, uimaFIT added more convenience things from the
world of Java
and related technologies (e.g. Spring, dependency injection,
running without
XML, etc.).
Still later, the platform has started paying more attention to
optimizations
around multi-core and L1/L2/L3 memory hierarchies, as those
technologies became
much more prevalent.
All along, there was close attention paid to backwards
compatibility; a main
reason was to create an "investable" platform - one where developers could
"invest" work in, and expect their work to have a long, useful
life, even as the
framework might evolve to keep up with hardware and software changes.
Another part of making UIMA an attractive place to invest work in annotator
development was the possibility of first developing your annotator in an
easy-to-use paradigm, and later "optimizing" it for speed / space.
This, for
example, recently happened in version 2.7.0 with the release of an
"upgrade" to
the CasCopier. The first version was completed using normal Java
APIs to the
CAS, and served for several years. When some applications began
noticing this
was becoming a bottleneck, an optimization was done which a)
greatly speeded it
up, and b) used much less Java heap space in the process, principally by
replacing CAS and index access and minipulations with their so-called
"low-level" equivalents. These low-level equivalents are there
just for this
reason; they typically create and use no Java objects at all, and
can be much
faster.
I'm not questioning historical design choices, I understand various things
were different in the past and that it has been an evolution; rather I'm
suggesting that the design as it stands now doesn't make sense.
I'm proposing the fact that complex low level API usage is needed by
developers to get better performance is primarily an artifact of the custom
heap implementation itself.
In other words, we're providing an implementation which is more complex and
slower than a simple object-based one and then saying if you want comparable
performance you need to rewrite your code using the cumbersome low
level APIs.
These are interesting points, and are driving some investigations into seeing
*why* the performance (space and time) of the object-based one is
better in some
cases. The results of this investigation (which hasn't been done
before due to
lack of focus/interest) could result in "fixes" that make the current
implementation faster, perhaps even substantially, than the object one.
Opinions on this vary :-), but some underlying fundamentals lead me to think
this is quite possible. These include well-known aspects of space
overhead for
Java objects, and the effect of compact representations on memory caching
aspects in modern computing (leading to favoring array-like data structures
versus representations based on linked lists).
One thing that was totally a surprise to me, and may yield some significant
performance benefits, is to untangle the various interfaces and
classes around
indexes and iterators, in a particular good (performant) way. I
tried one such
untangling - taking the two concepts of "ComparablePointerIterator" (an
IntIterator which can be compared with another IntIterator) and the
concept of
being able to report ConcurrentModificationExceptions, and split
these into two
interfaces (they were previously combined in the comparablePointerIterator
interface). This refactoring, by itself, resulting in the
performance on both
our test suite and a test run on a highly parallel large scale
pipeline, to drop
by 6 to 16%. (So I of course will not do that change...).
Would it not be better if the easy-to-use paradigm was already fast enough?
Of course. The problem though, it seems to me, is that fast enough
is a moving
target :-).
The CASCopier low-level rewrite example is a very good illustration - where
better performance was achieved *despite* the underlying impl, not
because of
it. The obj-based impl still uses the normal Java APIs (basically the
pre-rewrite CASCopier logic), and the "as-is" raw copying speed is
very close
to the super-optimized low level one(*). In a practical context
where copying
is done in conjunction with other CAS access, the obj impl appears
much faster
on aggregate.
On the backwards compatibility point - as already discussed in the
thread what
I'm proposing should have minimal if any impact on existing developer
investment. It's now been tested with various apps/frameworks without code
changes being needed (uimaFIT, Ruta, hopefully DKPro once binary
serialization
compatibility is there,..)
(*) This statement applies to copying with a shared typesystem. At first
glance it looks like some of the CASCopier optimization done was aimed
specifically at speeding up aspects of cross-typesystem copying which are
independent of the LL CAS aspects and I assume should be simple to transfer
over to the new impl.
I think Nick has several interesting ideas, all bundled up together in a
particular set of design choices, for an alternative CAS design. At a high
level, I think these are:
1) having the main data storage be within individual sets of Java Objects
(multiples for each Feature Structure Instance), and letting Java
manage the
space allocation and reclamation (via garbage collection) of these.
2) having the indexes index these Java structures (vs in the core:
they index
offsets in the heap, represented as "ints").
3) having the index structures themselves do a different trade-off
of space,
time, and concurrency support. In general, the trend seems to be
less concern
for space (as the cost per bit has dropped faster than the cost per
computation), and towards supporting more concurrency (as the
ability to run
multiple threads in parallel has grown).
4) Making more use of "standard" (but possibly new/evolving)
capabilities in
core Java, instead of doing lots of custom one-of-a-kind Java code. In
general, I think this is a very good idea :-). I foresee shifts in this
direction where
possible, but probably incrementally, in the core UIMA implementation.
I think these high level concepts have valuable ideas to consider
augmenting
core UIMA with. And the whole package might be, together, an interesting
design point for some users.
I don't think the ideas are so independent though. If you start with the
assumption that standard objects are a better choice than custom heaps, then
simple index implementations based on standard Java collection
impls are also
a natural thing to do.
Given that, I don't really understand how the existing impl would be
"augmented", could you elaborate on this? Which bit of what you summarized
would be considered disadvantageous and excluded? In my view all of these
things are advantageous, so why limit the improvement/simplification?
Here are some early thoughts; I suspect more will surface as the object
implementation details are explored.
The current design supports Feature Structure references which
includes a Java
cover class (either a JCas cover object, or a basic Java cover object having
only generalized methods for accessing Features), and a low level
reference, an
"int".
This "dual" nature requires conversion between these two forms;
going from the
int to the Java class form requires either generating a new Java object each
time this is done, or saving a previously generated object, and
"looking it up"
and reusing it (this is what's normally done for the JCas cover
objects). This
is a cause of some amount of "overhead", which could be eliminated
by moving to
an approach which puts the main impl as Java cover objects, and
"materializes"
as needed, the int form (for backward compatibility, as you do).
One would need
to be aware of performance issues for code that used the int form - this code
would likely run quite a bit slower.
The indexing support currently builds indexes around the int form of
reference
to the Feature Structures. This could be changed to build them
around the Java
form of reference. This would have the benefit of eliminating the
conversions
from the int form to the Java form.
The actual index implementation is a complex trade off between accessing,
iterating, and updating. The current implementation stores indexes in a
multitude of optimized data structures, which attempt to balance the trade
offs. This includes the famous rattling iterators - a design choice made to
have updates to a particular type affect index structures only for that type
(and not for all types), which, in turn, was traded off for array-like data
structures to store things (except for Sets). This design choice
led, though, to
the need to have iterators over a type and all its subtypes, for the Sorted
case, to have complex logic that set up iterators for all the
subtypes and the
type, sort those, and keep them in sorted order as the iterator moved through
the collection. In some use cases, we've seen where there are 100's or even
1000's of subtypes, and the maintenance of these lists of iterators becomes a
noticable overhead. Jira
https://issues.apache.org/jira/browse/UIMA-4356 speeds
things up noticably when a significant number of these subtype
indexes are empty.
I also think that many existing (and future) users like the idea
of a platform
which supports a sliding scale of space / time / optimization tradeoffs as
represented by the current UIMA design, so I don't currently think
it's a good
idea to drop the current UIMA internal design in favor of this new
design point.
Could you expand on the space / time / optimization tradeoffs you have in
mind? I think it's a big mis-assumption that the current custom heaps and
index implementations provide any meaningful benefit in terms of
speed/memory
usage over a simpler object impl.
In my experiments so far with some real-life usage, the obj-based
impl appears
to be better in terms of both speed and space. I'm also highly
skeptical that
there exist any real-life use cases where the magnitude of the "space"
difference is meaningful (whether that's a net increase or reduction).
In other words, what benefits would be "given up" by abandoning the custom
heaps/indices? If the object based impl satisfies (or can be easily made to
satisfy) the vast majority of practical use cases better, what's
really being
trading off and why would one choose to retain all of the complex
custom baggage?
In particular, what is the sliding scale of tradeoffs which the current impl
provides? I actually think the object based approach makes it simpler to
build/plug in different index datastructures that could provide usecase
specific tradeoffs (grouping by type within sorted indices being a prime
example). It's also trivial to swap concurrent collections with their
non-concurrent counterparts where threadsafety isn't required, etc.
There are other design points/choices that could be considered.
For example,
with today's technology, I think it is quite feasible to create Feature
Structures as Java objects where the features are "fields" in the
Java object.
This is enabled by the ability to compile Java classes as part of
the startup of
application instance. I'm thinking along these lines: the current
approach to
UIMA Type merging would be followed by a similar JCas cover class (optional
creation) and merging, followed by compiling the JCas cover classes during
startup. This could be a kind of just-in-time (JIT) running of
JCasGen at the
start of every run, on the fully merged type system. (I'm sure
there's issues I
haven't thought of; this is just the beginnings of an idea :-) ).
This is an interesting idea, but introducing on-the-fly code generation and
compilation as a standard runtime step sounds a bit precarious (but
maybe I'm
wrong). Would user code also require recompilation using the dynamically
generated classes?
It shouldn't.
I also can't envisage how it would retain backwards compatibility with
existing code (which I've learnt is a pretty big deal!),
particularly since as
you know there are some contexts where custom modifications to
generated JCas
classes are used extensively.
The generation of JCas cover classes has always allowed for custom
modifications
in the source. These are (and would continue to be) "merged" in as
part of JCasGen.
Furthermore it's also not clear how much benefit it would give beyond the
obj-based impl already done. From a CAS access point of view there would be
slightly less indirection by removing the arrays, but in generic APIs
reflection would be required. So I think we'd want to be confident this net
speed advantage was non-negligible before paying the above penalties. As
mentioned earlier, I'm fairly sure any additional "space saving" wouldn't be
significant in practical contexts.
I feel that there is a very wide usage of UIMA in many different
contexts, since
it's been out there for a decade. The space saving may be
significant in some
of the existing use cases.
Another reason space saving may be significant involves modern chip memory
management, where there's multiple levels of caching. IBM's P7, for example,
has an L1 cache size of 32K, and I think uses cache lines of 128
bytes, giving
256 cache slots in L1; L2 . (see
http://www-03.ibm.com/systems/resources/systems_power_software_i_perfmgmt_underthehood.pdf
). Having fewer Java objects, with less pointer-dereferencing among
them, can
result in much faster execution. I'm reminded of a problem noticed
in our form
6 deserialization speed when IBM Java was used - it was ~ 3x slower than the
Oracle Java. This was eventually traced to a buffer spec for the
built-in Java
unzipping code, see Jira https://issues.apache.org/jira/browse/UIMA-4283 .
Changing a buffer from a max of 32K to 1K (shrinking it) made the
IBM Java run
the same as the Oracle one. I think the unzipping code was "flushing" the L1
cache, and causing this effect (which was very big, for this part of
the system).
-Marshall
On 4/2/2015 3:55 PM, Nick Hill wrote:
Thanks Richard, more replies below...
Quoting Richard Eckart de Castilho <[email protected]>:
Hi Nick,
On 02.04.2015, at 01:37, Nick Hill <[email protected]> wrote:
From my point of view, it would be nice if it was possible to
configure the
UIMA framework to produce either this new kind of CAS or the old one
without having to exchange a JAR - doing so statically at
initialization
time or even dynamically at runtime. E.g. to allow easily running test
cases against both implementations.
When you say "produce", there shouldn't be any visible difference in
anything output or persisted, the impl is just how the CAS is stored
internally in memory while processing is happening.
It won't be possible to switch the impl being used at runtime. There are
classes for example with the same names but different impls
(e.g. CASImpl).
I know this isn't ideal for tests/comparisons between the two impls but
quite a lot of things are currently tightly-coupled to the heap
internals
and so switching a jar doesn't seem too big a price to pay
given no other
code changes are needed.
What do you plan to be the ultimate goal of this experiment? Is
it to support
different CAS implementations or is it to replace the existing CAS
implementation with a totally different one?
Most things in UIMA are created through factories (not the CAS
so far). So
theoretically, one could replace most classes by custom classes by
reconfiguring the framework to use different factory classes or
having the
factories produce different implementations. Can you imagine
that as well for
the CAS?
For users the implementation shouldn't matter. They shouldn't observe any
functional difference and therefore shouldn't really care if the
impl changes
underneath. All consuming code should work as-is, with the
exception of code
which accesses 'internals' directly - but I'd see this as analogous to
accessing private fields in some java SDK class, which breaks when those
fields change in a newer SDK version.
As such I don't think it would make sense (or be very practical from a
maintenance pov) to support two implementations concurrently or to have a
factory.
Does it mean that the UIMA-C++ implementation is going to be discontinued
officially?
No, just to clarify no agreements or plans have been made. I just
wanted to
initiate a discussion around this as a possible idea.
If we were to pursue this alternate implementation, I don't know
of any reason
why the C++ impl would be discontinued. I had just listed C++ AEs
as one of
the things which don't yet work with my current prototype.
Having to recompile the JCas classes is a bit of a blocker to
me - but I
remember that Marshall was contemplating about a way to generate JCas
classes at runtime, so this might just be a temporary blocker.
When I say recompile, I don't mean regenerate using JCasGen,
just recompile
.class files from the existing jcas .java files. I would expect that you
would typically only be using one version (other than for comparison
purposes - to validate functional equivalence and/or compare
performance),
and so this isn't something that would need to be done often.
Compiled JCas classes tend to be shipped as part of frameworks.
This means
that it will not be possible to switch to a new CAS impl just by
replacing a
JAR. It will also mean that components from different UIMA-based
frameworks
cannot be mixed and matched anymore unless some broker like
UIMA-AS is used.
The current JCas cover class format is quite old and
tightly-coupled to the
heap-based CAS internals. Saying that all new versions of UIMA must be
binary-compatible with these therefore imposes a (somewhat crippling)
restriction on possible internal improvements. You might say that
the current
JCas classes break standard abstraction/encapsulation principles if the
expectation is they will be forever forwards binary-compatible.
It would not be hard on the UIMA side to move to a simpler and
more abstract
JCas cover class format that should avoid this problem in future, but the
actual move to such a format would be even more disruptive than
requiring a
recompilation (would require a re-JCasGen), and would have the
same issues you
mention above.
I managed to make this object-based impl at least source-compatible with
existing jcas cover classes, by 'converting' the impl of methods
called that
were intended to make CAS heap changes to actually be manipulating the FS
objects directly.
In one context, we also rely heavily on CAS addresses serving as unique
identifiers of feature structures in the CAS. Does your implementation
provide any stable feature structure IDs, preferably ones that
are part of
the system and not actually declared as features?
Yes, there are various cases where an 'equivalent' of an FS address is
required (for example if the LL API is being used). In this
case the id gets
allocated on the fly and will subsequently be unique to that FS
within the
CAS. In many cases an FS might never have such an ID allocated (it's not
really part of the non-LL "public" APIs), but you can always
'request' one.
I imagine that IDs would be necessary to implement stuff like
delta-CAS later
on too.
Are any of the changes so far in any way related to potentially allowing
additions to the type system at runtime?
Not directly related; my goal was just to make the implementation
functionally
equivalent but threadsafe (and simpler, faster).
But it's possible (not certain) this new impl may impose fewer barriers to
enabling such capability.
What would be the incentive/benefit for the developer of a UIMA-based
framework/applications or for the users of such
frameworks/applications to
switch to the new implementation?
That was the "summary of advantages" I had in the original email, I've
included it again below. The primary "external" benefits I think
are the CAS
being thread-safe and faster to manipulate. I understand that many
users/developers might not care about these things, just as they likely
wouldn't care about the code footprint or complexity of the
internals, but it
also shouldn't adversely impact them to "upgrade" to a new UIMA
version based
on this implementation.
I feel that not being able to have more than one thread work on a
CAS at the
same time is a major limitation, especially given modern systems typically
have many CPU cores.
- Drastic simplification of code - most proprietary data structure impls
removed, many other classes removed, index/index repo impls are
about 25% of
the size of the heap versions (good for future
enhancements/maintainability)
- Thread safety - multiple logically independent annotators can
work on the
same CAS concurrently - reading, writing and iterating over feature
structures. Opens up a lot of parallelism possibilities
- No need for heap resizing or wasted space in fixed size CAS
backing arrays,
no large up-front memory cost for CASes - pooling them should no longer be
necessary
- Unlike the current heap impl, when a FS is removed from CAS indices it's
space is actually freed (can be GC'd)
- Unification of CAS and JCas - cover class instance (if it
exists) "is" the
feature structure
- Significantly better performance (speed) for many use-cases, especially
where there is heavy access of CAS data
- Usage of standard Java data structure classes means it can
benefit more "for
free" from ongoing improvements in the java SDK and from hardware
optimizations targeted at these classes
Cheers,
-- Richard
