Hi Brad -
Thanks for your feedback. I'll be brief in my response:
- Array.add would be fine with me, but we both agree that the
name of it really isn't the point.
- I'm surprised that modifying an array while traversing
it would be an error, although I can understand that viewpoint,
especially if it's within parallel traversal.
It's news to me though... and changes the possibilities here a
little bit, since many potential cases of domain-modified
during a strength-reduced loop over an array are not possible.
- It sounds like we agree that some of the benefits from a const domain
might actually be benefits from using a domain that isn't modified inside
a loop.. I'd like to know a little bit more about this (you mentioned
finding historical reasons to prefer const domains). A related
question is whether or not possible modification of the domain in an
array declared with a domain literal (ie the common case like
var A:[1..10] int) is a serious issue preventing optimization.
- I'd like to know a little bit more aboutcompiler optimizations
that are possible when the domain doesn't change. You described
one and alluded to others. More generally, I'd like to
know more about compiler optimizations that you know are possible in
the language but that havn't been implemented yet. Both these
points are more curiosity than essential to the present discussion.
- Of the options I presented, I think (given your response),
that option (3) - modification of an Array.domain is
legal at compile-time and throws a runtime error if the domain
is shared -the best of the alternatives. Do you see any
ways that this strategy would inhibit optimization?
Do you have further objections to it? Would it be sufficient
for the compiler to give a compile-time error in cases in which
it can prove that the domain is shared?
As you noted, this option is similar to your option 1B, but
I think the difference is whether we expect the compiler
to prove that an array and domain have a 1:1 relationship -
or to prove that they do not. Either question would seem
difficult to handle inter-procedurally,and since having
to pass in the array and the domain both to procedures was
one of my main objections, proving that the array and its
domain are 1-1 would have to be inter-procedural - and I
am not optimistic that can be done in full generality.
Thanks,
-michael
On 01/24/2014 01:31 PM, Brad Chamberlain wrote:
>
> 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
