Speed up opportunities?

[jsams]

Thanks for writing this! The interface is super easy to use. Unfortunately, finding this package with google seems impossible. I was literally searching for things like "inverted vector index julia" and didn't see your package on the first couple of pages of results in any of those variations. :(

Therefore, I wrote my own function, that has a terrible interface. However, it seems to do fewer allocations, but this might be more because of the way it is used than anything else.

The function:

# allows equivalent of A[-x] in R, assumes x is vector,
# assumes, without checking, that to_remove is sorted!!!!!
# assumes, without checking, that to_keep is precisely least n-length(to_remove) long!
@inbounds function inv_index!(to_keep, to_remove, n::Integer)
    if isempty(to_remove)
        to_keep[1:n] = 1:n
        return to_keep
    elseif length(to_remove) == n
        return to_keep # zero something out?
    end
    prev_r = 0
    to_keepidx = 0
    for ri in 1:length(to_remove)
        r = to_remove[ri]
        if prev_r + 1 != r
            next_to_keep_idx = to_keepidx + (r - prev_r) - 1
            to_keep[(to_keepidx + 1) : next_to_keep_idx] = (prev_r + 1) : (r - 1)
            to_keepidx = next_to_keep_idx
        end
        prev_r = r
    end
    if last(to_remove) != n
        to_keep[(to_keepidx + 1) : (n - length(to_remove))] = (last(to_remove) + 1) : n
    end
    return to_keep
end

Usage of it (like I said, your interface is great)

using StatsBase
y = rand(100, 10)
n = size(y, 1)
loops = 3
idxpool = zeros(Int64, n);
accum = [tuple(zeros(2,2), zeros(2,2)) for j in 1:3];
for j in 1:loops
    nidx = sample(1:n, 1)[1]
    to_invert = sort(sample(1:n, nidx, replace=false))
    r = n - length(to_invert)
    accum[j] = (y[to_invert, :], y[inv_index!(view(idxpool, 1:r), to_invert, n), :])
end

Anyway, i'm benchmarking some critical code and wanted to migrate to your version, but i was getting like 20% fewer allocations with mine. Maybe there is something in mine you can use to optimize? In any case, 9/10 times I will be reaching for this. Hope it gets more popular / integrated in to the language some how!

Maybe if you comment with your code here, it will get more traction? JuliaLang/julia#1032

[mbauman]

Ah, I see. Yes, Not(to_invert) right now just creates a new logical mask every time, which is where the allocations are occurring. It's extraordinarily simple and easy, but you're right — it is leaving some performance on the floor.

I think a slightly better idiom for you to use in code like that might be something like this (with a few bonus optimizations):

inverted_mask = BitVector(n) # or Vector{Bool} — benchmark to see which is faster
for …
    nidx = rand(1:n) # you can just use rand here
    to_invert = sort!(sample(1:n, nidx, replace=false)) # you can sort! in-place here
    inverted_mask[:] = true
    inverted_mask[to_invert] = false # you could even add @inbounds here
    ... = (y[to_invert, :], y[inverted_mask, :])

We could use a specialized internal type that simply wraps to_invert and the parent array's indices, and then generates the inverted indices on the fly… but this gets a little tricky to do without allocations since we need to ensure to_invert is sorted for the implementation to be fast. I'd be open to PRs here, but this isn't a high priority for me.

There seems to be a movement growing to make this easier, so I'll either register it or push for inclusion in the standard library in the next few weeks.

[jsams]

Thanks for the tips!

Since I'm working on my own array type, i've added the inversion pool to the type struct so that it doesn't need re-allocated for each lookup. Of course, this precludes parallel computation, but in my case, parallelism isn't really feasible. But, with inspiration from your interface, added NotRow/NotCol functions which work somewhat similarly.