Here are some initial off-the-cuff thoughts:
> I'd really like to be able to say something like A.append("Hello"),
> when A is a 1-D rectangular array, and A.append(key, value) (for an
> associative array). This kind of array flexibility is one of the main
> productivity advantages Perl or Python have over C.
Generally speaking, I'm more open to this concept than I was a few years
ago on the productivity argument. That said, I think there need to be
constraints as to which arrays it can be applied to -- in particular, I
think we need to avoid changing the binding between an array and its
domain dynamically, and continue to be nervous about the notion of
changing an array's domain when other arrays share it (which Michael's
proposals are mostly sensitive to).
I'm not entirely sure append() is the right name here -- because it
suggests "at the end" and I think it's useful in cases that don't have a
clear end like sparse and associative cases -- I'd probably use .add().
But let's ignore that for the time being.
> Anyway, back to the 1-D local rectangular case. There are two problems
> right now preventing total append satisfaction:
> 1) Using the domain to resize and then add an element to an array is not
> amortized O(1) - that is, it reallocates and copies the entire array;
> so building up an array in this manner would be O(n*n).
> 2) If you want to allow an array to be appended to, you have to pass
> around the domain for that array separately. You have to write:
> D = D.low..D.high+1
> A[D.high+1] = newElement;
> or for an associative array
> D += newKey;
> A[newKey] = newValue;
> and even if we wanted to provide a .append method, that method
> would need to also take in the array's domain, like this:
> proc Array.append(D:domain, newElement) {
> ... the code above...
> }
I view problem 2 as being the more fundamental one than problem 1 since
problem 1 is a property of a given domain map and not the language.
> Now, modules/standard/Containers.chpl includes Vector, which
> stores its array and domain separately and does the usual array-doubling
> so that appends are amortized O(1). The problems with this approach are:
> A) Chapel is carefully constructed to include a rich vocabulary of operations
> on arrays. These operations (like slicing, promotion, zippering,
> parallel iteration) are not available on a Vector (even though they have
> the same data representation).
> B) Routines that work with 1-D arrays now might have
> an obligation to also work with a Vector. For example, what if I want
> to sort my Vector that I built up one element at a time? Now I need
> the Sort module to support the Vector type, even though the Sort
> module is already generic with respect to the array representation.
> Chapel's strong generic programming mechanisms should take care of
> this problem - instead of forcing developers to create two or more
> versions of every routine (or adapter classes like you do in C++).
Here, I view problem B as being bigger than problem A. Vector's lack of
capabilities are more related to the lack of effort spent on it than a
lack of capability (I think). That said, I think that if we can make
arrays rich enough that there isn't a need to use Vectors, that seems
attractive. As Michael says, Chapel's arrays are designed to be rich; the
presence of Vector arguably says they aren't rich enough. Vector also
benefits from knowing it has a 1-1 correspondance between domain and array
which could be the missing link to providing operations like append() on
arrays directly.
Giving a quick read on my reaction to the following options:
> So, I think that we need to change the rule about arrays not being resizeable
> unless their domain is explicitly used to do so. I can think of the following
> options:
> 1) Let programmers resize Array.domain willy-nilly. It's arguably not the
> language's job to protect programmers from themselves.
When we decided to make Array.domain return a const ref to the domain, it
solved so many issues that we had wrestled with, I'm reluctant to undo
that change. At the very least, I'd need to try and recreate the
arguments in favor of it before undoing it.
A variant on this would be to permit cases that have a 1-1 domain:array
relationship return a (var) ref to the domain for A.domain and have the
1-many relationship return a const ref. I don't know how tractable this
is to implement, but if it could be done, it might preserve the benefits
that making A.domain provided.
> 2) Relax the rule in cases where the domain is only growing. That is, allow
> multiple arrays sharing a domain to change size if an Array.domain is
> modified
> but only if all of the old elements remain.
This feels like it will become an annoyance to programmers at some point.
"Why can't I remove things from this domain?" I'm also not sure it goes
far enough to protect the benefits of making A.domain const.
> 3) Make it a runtime error for domains that are used by multiple arrays to
> change
> when accessed through an Array.domain.
> I believe this would be straightforward to implement currently using
> the domain's reference counts. This would change the error from a
> compile-time
> one to a run-time one.
This feels similar to my 1B variant, with a shift from compile-time to
run-time (which seems suboptimal, so if we could do it at compile-time
through analysis or the type system, all the better)
> 4) When Array.domain changes, the array gets a private copy of the modified
> domain, so that the new domain applies to the array and not other arrays
> that
> were declared over the same domain. Other arrays initially declared to
> share
> the same domain would no longer share the domain.
This one is mostly off the table for me. The less the compiler can reason
about the relationship between arrays and domains, the less able it's
going to be to optimize things. Below, you talk about some simple
optimizations that can be done in the leader/follower framework, but
compiler analysis of domain/array relationships can lead to more advanced
optimizations that can't be done at runtime. For example: "If all these
arrays share the same domain, zippered iterations over them can reuse the
scalar values used to access or walk a pointer over the arrays, reducing
the register load (an optimization that we get users asking about)."
There are also communication optimizations (for example stencil
optimizations) that benefit greatly from knowing the relationship between
domains and arrays. Essentially, taking this path feels to me like it
throws out all these opportunities by making static comprehension of
domain-array relationships akin to alias analysis.
> 5) Create some sort of type annotation which indicates that an array owns its
> domain and that the domain cannot be shared with other arrays. Arrays
> declared
> in this manner would get their own copy of a domain. For example, you
> might
> declare such an array like this:
> var A:[owns 1..100] int; // owns, in, var, private are potential
> keywords
> and declare a procedure that needs such an array like this:
> proc doThingsInvolvingAppending(A:[owns ?D]) { ... }
I find this a little ugly, but am open to something like this. Part of me
wonders whether we could just interpret anonymous domains in array types
as implying ownership, but I think the downside to that is that there
would be additional benefit in knowing that they were const (maybe?) which
we would be throwing away if they could be either const or var. I need to
think about whether that additional benefit relates to the singularity of
their ownership, or their actual constness.
> Chapel is carefully designed to allow some optimizations over arrays and
> domains. In particular, when multiple arrays are declared over the same
> domain, we know that e.g. a forall loop zippering those arrays needs no
> communication. However, this is more of a fact of how it's built than a
> compiler analysis/optimization... although the compiler could avoid
> emitting communication calls in this case (saving some overhead of going
> through e.g. comm_get when the data is actually local).
It's not simply overhead that's saved. Squashing communication insertion
also removes control flow that guards function/system calls (often from
inner loops), and this makes it far more straightforward for the C
compiler to optimize the generated loops. Without analysis the only other
way to squash this communication is to generate specialized loops and
switch between them at runtime based on execution-time analysis, but this
requires either 2**#arrays-accessed loops or for the poor alignment of two
arrays to hurt the performance of all arrays accessed within the loop.
> Section 20.11 of the spec describes that constant domains might allow
> the compiler to optimize further; for example to avoid bounds checks,
> but I don't personally believe that's an important point (since --fast
> just turns off all the bounds checks anyway).
I think that the ultimate implementation of Chapel would be one in which
most bounds-checks could be proved away by the compiler for common idioms
(i.e., a user wouldn't have to take off the seatbelt and potentially run
into an execution-time error in a long-running program that didn't show up
in the debugging trials). The language was certainly designed that way.
> My feeling on these points is that the compiler should have an
> arrays-domain-is-modified analysis, and that such an analysis would
> provide more optimization opportunities while allowing choice 1,2, or 4
> from being reasonable. There are other optimizations that the compiler
> can apply in regions where it can be proved that the array's domain is
> not modified, including any optimization that keeps a pointer to an
> array element.
The reason I think #4 is off the table is that the analysis would need to
be "Is this array's domain modified (orphaned) anywhere in the program?"
so it's not a local analysis, it's necessarily a global one, and one that
thwarts separate compilation unless we put it into the user-level type
system (at which point, we're in something closer to option 5).
I'm not sure whether or not a local arrays-domain-is-modified analysis
would be useful or not. I think it relates to the reasons we benefitted
from making A.domain const other than user surprise... (so I need to
dredge up those rationales).
> One such optimization is strength-reduction - we could
> convert 1-D local array accesses to in this loop
> for i in 1..100 {
> A[i] = i;
> }
> to a pointer that we increment, like
> for ptr in A.base..A.base+A.len-1 by sizeof(A.eltType) { ... }.
I don't think there's anything deep preventing us from doing this today.
I've attempted it in my spare time a few times and gotten close. The last
time I tried was when _ddata was still unnecessarily complicated -- I've
been meaning to give it another go now that it's not. Similar rewrites
could be used for multidimensional loops (as in ZPL), though they will be
more effective in the leader-follower 2.0 world.
> But if the loop body contains a modification of A's domain, that optimization
> cannot apply.
I don't think we should be supporting modifications of an array's domain
within a loop over that array/domain. This seems similar to permitting a
hash table to take insertions/deletions while it's being traversed (which
is normally disallowed, no?). It feels inherently problematic/expensive
to me to permit this. I suppose a particular domain map could be
engineered to permit it, but I don't believe we're going to want to
require it to be supported for all domain maps. (What happens when a
domain is modified and concurrent operations are using an array/domain is
currently somewhat of an intentionally ignored aspect of the language
definition. My take on it is "user beware -- we won't guarantee anything"
and I don't know what we could do that would be better without being
prohibitively expensive).
> As for the many-arrays-sharing-the-same-domain optimization, it seems to me
> that it can be totally implemented at run-time in the implementation of the
> follower iterators (ie, the follower iterator would check if it can guarantee
> that what it is iterating over has the same distribution as what the leader
> is iterating over, and in that case, omit the communication calls). So I'm
> not totally convinced that it's necessary for the compiler to always know
> about these arrays-sharing-domains cases - and I think it might be OK
> to restrict the compilers knowledge to
> arrays-sharing-domains-that-aren't-modified-through-the-array.
I think you're focusing on too small a set of optimizations.
-Brad
------------------------------------------------------------------------------
CenturyLink Cloud: The Leader in Enterprise Cloud Services.
Learn Why More Businesses Are Choosing CenturyLink Cloud For
Critical Workloads, Development Environments & Everything In Between.
Get a Quote or Start a Free Trial Today.
http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
_______________________________________________
Chapel-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-developers
