Dynamic Batching is the exact advantage provided by Tensorflow Fold, which makes it possible to create different computation graph for each sample inside single mini-batch. @mrdrozdov tried to implement dynamic batching in PyTorch and succeed. However, the dynamic batching version of RNN is even slower than the padding version. After profiling his code I found that the hotspot that makes dynamic batching slow is torch.chunk. Result shows that this operation takes even more time than RNN forward pass:
Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
   108                                               @profile
   109                                               def forward(self, x, lengths):
   110       541         1331      2.5      0.0          batch_size = len(x)
   111     17853        20234      1.1      0.2          lengths = [len(s) for s in x]
   112
   113       541          514      1.0      0.0          outputs = [Variable(torch.zeros(1, self.model_dim).float(), volatile=not self.training)
   114     17853       231300     13.0      1.9                     for _ in range(batch_size)]
   115
   116     11522        14014      1.2      0.1          for t in range(max(lengths)):
   117     10981        19603      1.8      0.2              batch = []
   118     10981        15608      1.4      0.1              h = []
   119     10981        14756      1.3      0.1              idx = []
   120    362373       424946      1.2      3.5              for i, (s, l) in enumerate(zip(x, lengths)):
   121    351392       809330      2.3      6.7                  if l >= max(lengths) - t:
   122    267925       399322      1.5      3.3                      batch.append(s.pop())
   123    267925       307910      1.1      2.6                      h.append(outputs[i])
   124    267925       300516      1.1      2.5                      idx.append(i)
   125
   126     10981       316257     28.8      2.6              batch = np.concatenate(np.array(batch).reshape(-1, 1), 0)
   127     10981       161699     14.7      1.3              emb = Variable(torch.from_numpy(self.initial_embeddings.take(batch, 0)), volatile=not self.training)
   128     10981       522216     47.6      4.3              h = torch.cat(h, 0)
   129     10981      2529893    230.4     21.1              h_next = self.rnn(emb, h)
   130     10981      4748304    432.4     39.5              h_next = torch.chunk(h_next, len(idx))
   131
   132    278906       322694      1.2      2.7              for i, o in zip(idx, h_next):
   133    267925       474999      1.8      4.0                  outputs[i] = o
   134
   135       541        27823     51.4      0.2          outputs = torch.cat(outputs, 0)
   136       541       174478    322.5      1.5          h = F.relu(self.l0(F.dropout(outputs, 0.5, self.training)))
   137       541       152165    281.3      1.3          h = F.relu(self.l1(F.dropout(h, 0.5, self.training)))
   138       541        25429     47.0      0.2          y = F.log_softmax(h)
   139       541          585      1.1      0.0          return y

So, is there any other efficient alternative to torch.chunk? Is there any approach to implement dynamic batching in PyTorch efficiently?