X10

Use dense memory layout for non-rectangular arrays

Details

  • Type: Improvement Improvement
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Won't Fix
  • Affects Version/s: X10 2.2.2
  • Fix Version/s: None
  • Component/s: Class Library: Array Library
  • Labels:
    None
  • Number of attachments :
    0

Description

x10.array.Region defines the method indexOf(Point), which maps each point in the region to a one-dimensional offset in the range 0..(N-1).
When allocating arrays, elements should be laid out in memory in the same order as is defined by this method. One consequence of this is that the array is dense in layout: exactly the same number of array elements are needed to store an array as there are points in its defining region.

Currently, non-rectangular arrays are not dense in layout. For example, the points in a triangular array are actually indexed using a rectangular layout, wasting half the memory.

Non-rectangular arrays should be laid out dense in memory in the manner specified in Region.indexOf(Point) by their defining region. If this is the case, the checks against {rect} in Array.fill(), Array.map(), Array.reduce() and the constructor can be removed. Of course, this has to be balanced against the need for efficient indexing of standard rectangular arrays.

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Vijay Saraswat added a comment -

but how do you define dense? Maybe it would be better to expose nnz, number of non-negative zeros, and permit the programmer to specify bounds <,> on arithmetic variables. (This i easy to add, and I hope we will add this real soon now..)

The real issue of course is how to compute nnz. What kind of operations do we need on regions to support sparse regions, and what kind of static reasoning can be done about them.

Show
Vijay Saraswat added a comment - but how do you define dense? Maybe it would be better to expose nnz , number of non-negative zeros, and permit the programmer to specify bounds <,> on arithmetic variables. (This i easy to add, and I hope we will add this real soon now..) The real issue of course is how to compute nnz . What kind of operations do we need on regions to support sparse regions, and what kind of static reasoning can be done about them.
Hide
Permalink
Josh Milthorpe added a comment -

Now I see that 'dense' is a terrible name as it suggests a dense matrix. What I actually mean is a dense layout in memory.

On further reflection, I can't see any good reason why a layout should not be dense in layout. An array should always be indexed using the same region that was used to create it, and regions define a mapping from the set of points to the range 0..(region.size()-1). The problem at the moment is that non-rectangular arrays aren't dense in layout, because we don't yet have an efficient way of supporting non-rectangular indexing. I will therefore change the title and description of this issue.

Show
Josh Milthorpe added a comment - Now I see that 'dense' is a terrible name as it suggests a dense matrix. What I actually mean is a dense layout in memory. On further reflection, I can't see any good reason why a layout should not be dense in layout. An array should always be indexed using the same region that was used to create it, and regions define a mapping from the set of points to the range 0..(region.size()-1). The problem at the moment is that non-rectangular arrays aren't dense in layout, because we don't yet have an efficient way of supporting non-rectangular indexing. I will therefore change the title and description of this issue.
Hide
Permalink
David Grove added a comment - - edited

The sticking point is that we can't afford a non-inlined function call in operator this() in Array. So the indexing calculation has to be fixed for all regions. Right now we get that by forcing indexing to be done wrt the indexOf operation on the bounding box of the "real" region of the Array. Since the boundingBox will be rect, we can hardcode the indexOf calculation and avoid the virtual function call(indexOf).

I don't see a way to change that while still preserving the performance of operator this(). We can't actually afford to call indexOf in the fast code path; having any non-inlined call (even on an off branch) makes it too slow.

Show
David Grove added a comment - - edited The sticking point is that we can't afford a non-inlined function call in operator this() in Array. So the indexing calculation has to be fixed for all regions. Right now we get that by forcing indexing to be done wrt the indexOf operation on the bounding box of the "real" region of the Array. Since the boundingBox will be rect, we can hardcode the indexOf calculation and avoid the virtual function call(indexOf). I don't see a way to change that while still preserving the performance of operator this(). We can't actually afford to call indexOf in the fast code path; having any non-inlined call (even on an off branch) makes it too slow.
Hide
Permalink
David Grove added a comment -

closing since I don't see any way to implement without crippling array indexing performance by injecting a virtual function call to Region.indexOf.

Show
David Grove added a comment - closing since I don't see any way to implement without crippling array indexing performance by injecting a virtual function call to Region.indexOf.
Hide
Permalink
David Grove added a comment -

bulk close of issues as part of making 2.2.3 release notes.

Show
David Grove added a comment - bulk close of issues as part of making 2.2.3 release notes.

People

  • Assignee:
    David Grove
    Reporter:
    Josh Milthorpe
Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: