JDK-8277156 : Compress and expand vector operations
  • Type: CSR
  • Component: core-libs
  • Priority: P4
  • Status: Closed
  • Resolution: Approved
  • Fix Versions: 19
  • Submitted: 2021-11-15
  • Updated: 2022-01-24
  • Resolved: 2022-01-24
Related Reports
CSR :  
Description
Summary
-------

Add two new cross-lane vector operations, `compress` and `expand`.

Problem
-------

It can be useful to leverage a cross lane operation that is an ordered movement up to the vector length of elements mapping from a source vector to a destination vector. Such an operation can be applied to query plan execution when results need to be filtered. 

This can be expressed using the existing and flexible `rearrange` operations with shuffles. However, the code tends to be less readable and hard for the compiler to optimize a loop consisting of compressed stores of vector results. Further, `compress` might be composed of an underlying primitive different to that of `rearrange`, related to sorting that we intend to explore in future enhancements.

Solution
--------

Add two new cross-lane vector operations, `compress` and its inverse `expand`. Complementary to the vector operation `compress`, add a vector mask operation, `compress`.

An example of such usage might be code that selects elements from array `a` and stores those selected elements in array `z`:

    int[] a = ...;
    int[] z = ...;
    int ai = 0, zi = 0;
    while (ai < a.length) {
        IntVector av = IntVector.fromArray(SPECIES, a, ai);
        // query over elements of vector av
        // returning a mask marking elements of interest
        VectorMask<Integer> m = interestingBits(av, ...);
        IntVector zv = av.compress(m);
        zv.intoArray(z, zi, m.compress());
        ai += SPECIES.length();
        zi += m.trueCount();
    }

Specification
-------------

The class documentation of `Vector` is updated to include the following new list item in the section on "Moving data across lane boundaries":
 
     * <li>The {@link #compress(VectorMask)} and {@link #expand(VectorMask)}
     * methods, which select up to {@code VLENGTH} lanes from an
     * input vector, and assemble them in lane order.  The selection of lanes
     * is controlled by a {@code VectorMask}, with set lane elements mapping, by
     * compression or expansion in lane order, source lanes to destination lanes.

Two new methods are added to `Vector`:

    /**
     * Compresses the lane elements of this vector selecting lanes
     * under the control of a specific mask.
     *
     * This is a cross-lane operation that compresses the lane
     * elements of this vector as selected by the specified mask.
     *
     * For each lane {@code N} of the mask, if the mask at
     * lane {@code N} is set, the element at lane {@code N}
     * of input vector is selected and stored into the output
     * vector contiguously starting from the lane {@code 0}.
     * All the upper remaining lanes, if any, of the output
     * vector are set to zero.
     *
     * @param m the mask controlling the compression
     * @return the compressed lane elements of this vector
     */
    public abstract Vector<E> compress(VectorMask<E> m);
    
    /**
     * Expands the lane elements of this vector
     * under the control of a specific mask.
     *
     * This is a cross-lane operation that expands the contiguous lane
     * elements of this vector into lanes of an output vector
     * as selected by the specified mask.
     *
     * For each lane {@code N} of the mask, if the mask at
     * lane {@code N} is set, the next contiguous element of input vector
     * starting from lane {@code 0} is selected and stored into the output
     * vector at lane {@code N}.
     * All the remaining lanes, if any, of the output vector are set to zero.
     *
     * @param m the mask controlling the compression
     * @return the expanded lane elements of this vector
     */
    public abstract Vector<E> expand(VectorMask<E> m);

Co-variant overrides are added to extending and specialized vector classes `ByteVector`, `ShortVector`, `IntVector`, `LongVector`, `FloatVector` and `DoubleVector`. 

One new method is added to `VectorMask`:

    /**
     * Compresses set lanes from this mask.
     *
     * Returns a mask which is a series of {@code N} set lanes
     * followed by a series of unset lanes, where {@code N} is
     * the true count of this mask.
     *
     * @return the compressed mask of this mask
     */
    public abstract VectorMask<E> compress();

Link to the java doc and specdiff:

http://cr.openjdk.java.net/~psandoz/panama/JDK-8277155-vector-api-compress-expand/


Comments
Moving to Approved; will do a broader re-review of the vector API as part of its next JEP iteration.
24-01-2022

Yes, for example see https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=compress&ig_expand=1367
23-11-2021

Moving to Provisional. I assume the names "compress" and "expand" are conventional in vector circles for these operations.
23-11-2021