Stream Compaction

[ethanabrooks]

How would you recommend performing stream compaction with this library? Using indexes?

[9prady9]

I believe stream compaction is equivalent to the following 3 steps in that order.

1. Generate boolean map indicating which elements are important if one doesn't exist already.
2. Perform scan operation on the boolean map.
3. Index the original input array using the scanned boolean map avoiding zero values.

Given below is the C++ equivalent of above steps.

array a = randu(10);    // input data
array b = a > 0.4;        // boolean map of relevant values
array c = scan(b);       // scan the boolean map
array i = c(where(b));  // gather scanned map values where the map wasn't zero originally
array dense = a(i);      // index original input array with gathered map values

The rust version would follow the exact same operations with syntactical difference and locate function replaces where.

[ethanabrooks]

The rust version does not have an operator equivalent to where, or at least I have not been able to find one.

[pavanky]

@lobachevzky It is called locate in rust.

[9prady9]

@lobachevzky I am sorry about not mentioning that locate is where's replacement in rust wrapper.

[ethanabrooks]

This is what I'm using currently:

fn filter(bools: &af::Array, array: &af::Array) -> af::Array {
    let mut idxr = af::Indexer::new();
    idxr.set_index(&af::locate(bools), 0, None);
    af::index_gen(array, idxr)
}

By the way, what does the batch argument for idxr.set_index mean?

[9prady9]

@lobachevzky
Many functions have this boolean batch argument. What it essentially tells the function is that there are multiple data-sets in af::Array that needs to undergo the same operation.

Ley us consider the function add as an example. Say, the input Arrays are of mismatched dimensions i.e. one Array is two dimensional and the other is three dimensional. In this case, if the is_batch is false, then the function will throw an error due to mismatch of dimensions. However, if the is_batch is true, then it will process the addition as though one matrix is being added to multiple matrices in a single call, thus returning a three dimensional Array.

[ethanabrooks]

Got it. Thanks you!

[ethanabrooks]

One note on this approach:
This will throw a segmentation fault if bool is all 0 / false. As a workaround, I tried first checking if af::locate(bools) was empty, but if it is, it does not seem possible to create a new empty array:

 Array::new(&[] as &[i32], Dim4::new(&[0, 0, 0, 0]))

throws:

thread 'main' panicked at 'Error message: Size is incorrect', /Users/ethan/.cargo/registry/src/github.com-1ecc6299db9ec823/arrayfire-3.4.2/src/error.rs:66

[pavanky]

@lobachevzky Try using the latest version of arrayfire libs. I think you are using v3.3 version of the libs.

[ethanabrooks]

I am using v3.3.2 for arrayfire:

~
❯ brew info arrayfire
homebrew/science/arrayfire: stable 3.3.2 (bottled)
General purpose GPU library
http://arrayfire.com
/usr/local/Cellar/arrayfire/3.3.2_1 (298 files, 81.5MB) *
  Poured from bottle on 2017-03-25 at 17:55:32
From: https://github.com/Homebrew/homebrew-science/blob/master/arrayfire.rb
==> Dependencies
Build: cmake ✔, boost ✔, boost-compute ✘, pkg-config ✔
Required: freeimage ✔, fftw ✘, clblas ✔, clfft ✔, fontconfig ✔, glfw ✔
==> Requirements
Build: git ✔
Required: macOS >= 10.9 ✔, x11 ✔

and v3.4.2 for the rust library:

[dependencies]
arrayfire = "3.4.2"

(this is from my Cargo.toml)

[pavanky]

@lobachevzky can you upgrade to v3.4.2 for the arrayfire libs and try again ?

[ethanabrooks]

Sorry for the delayed response. Getting the binary downloaded from the website to work took some doing. I am running v3.4.2 and I still get the exact same error message for empty arrays.

[polarathene]

array b = a > 0.4;        // boolean map of relevant values
array c = scan(b);       // scan the boolean map

I know that in Rust we can do a += b or a + b but conditionals like above don't seem to work. Can we only use the method versions like gt()?

scanhas much more parameters according to the docs. Your input seems to be boolean values whereas the Rust version takes an Array, is restricted to a dimension, does an add,mul,min or max binary op and inclusive/exclusive flag..

Is the approach @lobachevzky mentions achieving the same with different methods? I've tried his filter method on an array with dims [1,3,1,1] and elements [2,5,6]. It outputs an array with dims [3,1,1,1] and elements [6,2,6]. The bools array is dims [1,3,1,1], elements [0,1,1].. though the elements values don't seem to matter as they always result in [6,2,6].

I've verified with print() that the output is the correct amount of index elements and expected values(although it's flattened to dims [3,1,1,1] which seems fine. If the indexes are provided without going through locate() it works fine. I suspect it's similar to the problem I had with eq()/neq() earlier that returns u8 array, printed fine but when sent from device to host my u32 vector got numbers that were not 0 or 1.

[polarathene]

extern crate arrayfire as af;
use af::*;


fn main() {

    let dims   = af::Dim4::new(&[1, 3, 1, 1]);
    let bools  = af::Array::new(&[1, 0, 1], dims);
    let values = af::Array::new(&[2, 5, 6], dims);

    print( &bools );
    print( &filter_edited(&values, &bools) );
    print( &af::locate(&bools) );
    print( &filter_edited(&values, &af::locate(&bools)) );

    print( &filter_original(&values, &bools) );

}

fn filter_edited(array: &af::Array, bools: &af::Array) -> af::Array {
    let mut idxr = af::Indexer::new();
    idxr.set_index(bools, 0, None);
    af::index_gen(array, idxr)
}

fn filter_original(array: &af::Array, bools: &af::Array) -> af::Array {
    let mut idxr = af::Indexer::new();
    idxr.set_index(&af::locate(bools), 0, None);
    af::index_gen(array, idxr)
}

Output:

[1 3 1 1]
         1          0          1 

[3 1 1 1]
         5 
         2 
         5 


[2 1 1 1]
         0 
         2 


[2 1 1 1]
         2 
         6 


[3 1 1 1]
         6 
         2 
         6 

Change Dims to [3, 1, 1, 1] however:

[3 1 1 1]
         1 
         0 
         1 


[3 1 1 1]
         5 
         2 
         5 


[2 1 1 1]
         0 
         2 


[2 1 1 1]
         2 
         6 

thread 'main' panicked at 'Error message: Input does not belong to the current device'

The original method by @lobachevzky fails on me. I've been using [1, 3, 1, 1] because of errors that dims of [3, 1, 1, 1] were giving me earlier. While @lobachevzky method doesn't crash it does produce unexpected results.

---

Filtering results to a smaller array to send back to the host is something I'd been spending quite a bit of time trying to figure out myself, this would make a good example to add :)

[polarathene]

It seems to work correctly if I change

idxr.set_index(&af::locate(bools), 0, None);

To this:

let x = &af::locate(bools);
idxr.set_index(x, 0, None);

I've been told the reason for this is:

The latter might be dropping the result of af::locate at the end of the expression, ie the same statement. So before the index_gen call
In safe Rust borrowck would've complained in some way, but the unsafe bindings are probably not communicating the lifetimes to borrowck for it to complain

I guess the Rust wrapper for ArrayFire has plenty of cases like this where the compiler could have picked up on the errors I've been running into like this and other methods. I'll raise this as a separate issue.

[9prady9]

@polarathene I haven't been able to reproduce the error you got in the comment that says thread 'main' panicked at 'Error message: Input does not belong to the current device

However, I do see the difference in output from changing bools from [3 1 1 1] dims to [1 3 1 1] dims. I am looking into it.

[9prady9]

@lobachevzky

W.r.t to your comment, you can create empty arrays ([0, 0, 0, 0] dims) using Array::new_empty(). This is not yet available in latest crate release but available on current HEAD of devel branch. Will try to do a fix release if 3.5.0 doesn't happen soon enough.

[9prady9]

@polarathene Moving the discussion related to potential bug in locate to #138