A word of caution - be very careful with cusparse, because for some routines it is calling cudaFree (grrrr!), which not only has performance implications, but will deadlock on multiGPU runs with nccl.

@martinraison has addressed all my comments for merge - I will try to speed up the GPU sparse operations necessary for lookup table this week, but that doesn't block merging this.

I'm still unsure about the meaning and handling of contiguous tensors. In dense libs, we never make the input contiguous for the user, because it could break sharing + it makes for a much less magical API. I'm also worried that someone will be adding non-linear ops, and they will forget that non-contiguous means not only that the indices aren't ordered, but they're duplicated too. These bugs will be hard to catch, because it's unlikely that someone will test with such inputs.

Is it true that right now we don't do any contiguous() calls on the tensors that are using for gradients in Embedding?

@apaszke

In dense libs, we never make the input contiguous for the user, because it could break sharing + it makes for a much less magical API

@fmassa also noticed it is surprising that contiguous operates in-place. We could just rename it to contiguous_. We might also be able to enforce that operations never make the input contiguous automatically (but either make a contiguous copy or throw an exception so that the user calls contiguous_ explicitly).

I'm also worried that someone will be adding non-linear ops, and they will forget that non-contiguous means not only that the indices aren't ordered, but they're duplicated too

I believe making indices unique is an O(NlogN) operation anyway, so if we're doing that we might as well make the tensor contiguous. However I think we'd be wasting a lot of computation if we were forcing all sparse tensors to always be contiguous. For example it means you would have to spend O(NlogN) time for every single sparse gradient aggregation, rather than doing a single O(NlogN) operation when applying the gradient update.

Is it true that right now we don't do any contiguous() calls on the tensors that are using for gradients in Embedding?

In the case of Adagrad, which is non-linear, we have to call contiguous on sparse gradients. Right now only SGD and Adagrad are supported with sparse gradients (which is why sparse=True is not the default for Embedding). We were discussing with @adamlerer about the best way to support other optimizers (it requires adjusting the maths a bit to support momentum without deviating too much from the dense formulation).

I dug into speeding up sparse for nn.Embedding based on my benchmark on GPU (https://gist.github.com/adamlerer/865c1a09000c7dc8208e1456255209c2). I think my findings apply more broadly though.

• Most importantly, the contiguous (or reorder) operation, which merges rows with the same index, is inevitably slow on GPU because it demands a host synchronization. The reason is that the number of unique rows (calculated on GPU) becomes the new nnz, i.e. indices.size[0] / values.size[0] (which is a CPU field). So, it ends up being much faster to compute operations like spcadd (the main op for Embedding update) directly on the non-'contiguous' tensor, using indexAdd or LookupTable_accGradParameters.
  The potential problem with never compacting sparse tensors is that they can grow to unbounded size if you repeatedly call cadd without ever calling contiguous. Maybe make it the user's responsibility to call contiguous when necessary? This can be problematic when the cadd is buried in a library somewhere e.g. in autograd backward. I don't have a good answer here... We could have heuristics for when to compact a tensor. Something like this would be kinda clever (too clever?):

void THCSTensor_(cadd)(r, a, b) {
...
r->minUnique = max(a->minUnique + b->minUnique);
...
if (r->nnz / r->minUnique > COMPACTION_THRESHOLD) {
  THCSTensor_(contiguous)(r);
  r->minUnique = r->nnz;
}

• LookupTable_accGradParameters is just computing indexAdd, yet it's implemented completely differently. The different implementation was due to a desire a couple years ago for LookupTable to be deterministic therefore not use atomicAdd. But then why does indexAdd still use atomicAdd? Either we care about determinism or we don't... my guess is that we don't any more since even cudnn isn't deterministic.
  I benchmarked then and the non-deterministic one is several times faster, regardless of how many index collision there are. We should pick if we care about determinism, use that to pick an indexAdd kernel in THC, and then delegate LookupTable, spcadd, etc. all to that.

• Autograd backwards on nn.Embedding spends about 1ms in Python autograd code, which after speeding things up takes >90% of the time for batch sizes below 1e4 (it was taking ~50% of the time before my kernel changes). So batch=1e3 isn't interesting, we should look at batch=1e4.

@adamlerer, a note about cudnn being non-deterministic

1. All convolution routines have deterministic variants (unfortunately, some of them are so slow they can not be used in production).
2. Maxpooling used to be non-deterministic if kernel is bigger than stride, but starting from cudnn v6 there's an option of using deterministic maxpooling (and cudnn maxpooling is not used in pytorch anyway).
   So I agree, for LookupTable, like in cudnn, there should be an option "deterministic and (possibly) slow" and "nondeterministic and fast"
   How did you benchmark autograd overhead on nn.Embedding? 1ms seems like a lot.

@apaszke re: contiguous, lets think about exactly what we mean by "weight sharing". I think you mean something like

A = torch.sparse.Tensor(...)
B = t.t() # A and B are shared views; you don't want to silently break this sharing
C = A[:10] # also a shared view

Except that this already doesn't work for sparse tensors! There's no way (at least currently) to have a view on a sparse tensor. So I don't think this matters. I'd like to think of sparse tensor reordering (which we really should give a new name than contiguous) as an internal optimization detail; so logically, reorder(A) === A (cf. C++ mutable keyword). This is not the case for dense tensors where contiguous is externally visible. Let me know if you can think of a counterexample.
Re: possibility of user error with contiguous and non-contiguous tensors, yes you're right. It's exactly the reason why non-contiguous tensors lead to so many errors in TH proper. No getting around that - if you're writing THCS functions, you need to be aware of contiguous vs non-contiguous.

@martinraison yes I agree we should have a deterministic variant. But notice that this extends to indexAdd as well. Currently LookupTable is deterministic, indexAdd is non-deterministic. So I think we should have a deterministic and non-deterministic variant of indexAdd, and LookupTable / spcAdd should just delegate to that.

I benchmarked autograd overhead like this, with small batch size like 10. It takes ~700us / batch, and CPU sits at 100%. perf top shows it's spending most of it's time in python functions as well as libTHC routines that look like they're in the memory allocator. Let me know if you have any suggestions for better profiling.

...
for i in range(N):
    emb.zero_grad()
    out = emb(vbatch)
    out.backward(out.data)
    optimizer.step()

@adamlerer so do you propose that only the reordering should be an implementation detail, or would you like to make sorting an internal thing too? The ordering isn't visible externally, is it?

The reorder function does a sort on indices followed by segmented reduction by index. I'm not sure what you mean by sorting vs. reordering.

My thought is that reorder should have no user-visible functional implications, i.e. the coalesced tensor version should be logically equivalent to the uncoalesced one. However, reorder should be exposed to the user because it may be necessary for efficiency (it's currently called contiguous() but should be called something different like coalesce_()).

this is now rebased to fewer commits and merged into master