{"action":"reopened","issue":{"url":"https://api.github.com/repos/dmlc/mxnet/issues/2612","repository_url":"https://api.github.com/repos/dmlc/mxnet","labels_url":"https://api.github.com/repos/dmlc/mxnet/issues/2612/labels{/name}","comments_url":"https://api.github.com/repos/dmlc/mxnet/issues/2612/comments","events_url":"https://api.github.com/repos/dmlc/mxnet/issues/2612/events","html_url":"https://github.com/dmlc/mxnet/issues/2612","id":163699387,"number":2612,"title":"Slow speed of the AddTakeGradKernel in embedding layer","user":{"login":"sxjscience","id":5178350,"avatar_url":"https://avatars.githubusercontent.com/u/5178350?v=3","gravatar_id":"","url":"https://api.github.com/users/sxjscience","html_url":"https://github.com/sxjscience","followers_url":"https://api.github.com/users/sxjscience/followers","following_url":"https://api.github.com/users/sxjscience/following{/other_user}","gists_url":"https://api.github.com/users/sxjscience/gists{/gist_id}","starred_url":"https://api.github.com/users/sxjscience/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sxjscience/subscriptions","organizations_url":"https://api.github.com/users/sxjscience/orgs","repos_url":"https://api.github.com/users/sxjscience/repos","events_url":"https://api.github.com/users/sxjscience/events{/privacy}","received_events_url":"https://api.github.com/users/sxjscience/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dmlc/mxnet/labels/focus%20progress","name":"focus progress","color":"d4c5f9"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2016-07-04T15:34:23Z","updated_at":"2016-07-17T14:46:40Z","closed_at":null,"body":"The `AddTakeGradKernel` used in the embedding layer is not efficient. In fact, if our input contains lots of elements, e.g, embedding a matrix of size (128, 100), the for-loop here (https://github.com/dmlc/mshadow/blob/master/mshadow/cuda/tensor_gpu-inl.cuh#L461) will be costly. In this case, `ymax` is equal to `src.size(0)` (https://github.com/dmlc/mshadow/blob/master/mshadow/cuda/tensor_gpu-inl.cuh#L488), which is 12800.\r\n\r\nI've run a speed benchmark against Torch's `LookupTable` and find our kernel is far slower than theirs (possibly due to this expensive for-loop).\r\n\r\nTorch Code:\r\n```lua\r\nrequire 'cudnn'\r\nrequire 'cunn'\r\n\r\nlocal unpack = unpack or table.unpack\r\nlocal pl = require('pl.import_into')()\r\n\r\nlocal vocabsize = 100000\r\nlocal batchsize = 128\r\nlocal featuredim = 100\r\nlocal embedsize = 150\r\n\r\nlocal m = nn.Sequential()\r\nm:add(nn.LookupTable(vocabsize, embedsize))\r\nm:cuda()\r\n\r\nlocal N=100\r\n\r\ninput = torch.LongTensor(batchsize, featuredim):random(1, vocabsize):cuda()\r\ntimer = torch.Timer()\r\nfor i=1,N do\r\n     output = m:forward(input)\r\nend\r\ncutorch.synchronize()\r\nprint('Time elapsed for forward: ' .. timer:time().real/N .. ' seconds')\r\n\r\ngradOut = torch.FloatTensor(vocabsize, embedsize):random(0, 1):cuda()\r\ntimer = torch.Timer()\r\nfor i=1,N do\r\n     grad = m:backward(input, gradOut)\r\nend\r\ncutorch.synchronize()\r\nprint('Time elapsed for backward: ' .. timer:time().real/N .. ' seconds')\r\n```\r\n\r\nResult:\r\n```\r\nTime elapsed for forward: 0.00042492866516113 seconds\r\nTime elapsed for backward: 0.0012397193908691 seconds\r\n```\r\n\r\nMXNet Code:\r\n```python\r\nimport mxnet as mx\r\nimport numpy as np\r\nimport time\r\n_rng = np.random.RandomState(1234)\r\n\r\ndef check_speed(sym, ctx=mx.cpu(), scale=1.0, N=100, grad_req=None, rng=_rng, **kwargs):\r\n    if grad_req is None:\r\n        grad_req = 'write'\r\n    exe = sym.simple_bind(grad_req=grad_req, ctx=ctx, **kwargs)\r\n    init = {k:np.random.normal(size=arr.shape, scale=scale) for k, arr in exe.arg_dict.items()}\r\n    if \"embedding_weight\" in init:\r\n        init['data'][:] = np.random.randint(0, init['embedding_weight'].shape[0], size=init['data'].shape)\r\n\r\n    for name, iarr in init.items():\r\n        exe.arg_dict[name][:] = iarr.astype(exe.arg_dict[name].dtype)\r\n\r\n    # Warm up\r\n    exe.forward(is_train=True)\r\n    exe.backward(out_grads=exe.outputs)\r\n    for output in exe.outputs:\r\n        output.wait_to_read()\r\n    # Test Forward + Backward\r\n    tic = time.time()\r\n    for i in range(N):\r\n        exe.forward(is_train=True)\r\n        exe.backward(out_grads=exe.outputs)\r\n        for output in exe.outputs:\r\n            output.wait_to_read()\r\n    mx.nd.waitall()\r\n    toc = time.time()\r\n    forward_backward_time = (toc - tic) * 1.0 / N\r\n    return forward_backward_time\r\n\r\n\r\ndef check_prediction_speed(sym, ctx=mx.cpu(), scale=1.0, N=100, rng=_rng, **kwargs):\r\n    exe = sym.simple_bind(grad_req=\"null\", ctx=ctx, **kwargs)\r\n    init = {k: np.random.normal(size=arr.shape, scale=scale) for k, arr in exe.arg_dict.items()}\r\n    if \"embedding_weight\" in init:\r\n        init['data'][:] = np.random.randint(0, init['embedding_weight'].shape[0], size=init['data'].shape)\r\n\r\n    for name, iarr in init.items():\r\n        exe.arg_dict[name][:] = iarr.astype(exe.arg_dict[name].dtype)\r\n\r\n    # Warm up\r\n    exe.forward(is_train=False)\r\n    for output in exe.outputs:\r\n        output.wait_to_read()\r\n\r\n    # Test Forward Only\r\n    tic = time.time()\r\n    for i in range(N):\r\n        exe.forward(is_train=False)\r\n        for output in exe.outputs:\r\n            output.wait_to_read()\r\n    toc = time.time()\r\n    forward_time = (toc - tic) * 1.0 / N\r\n    return forward_time\r\n\r\ndata = mx.sym.Variable('data')\r\nembedding_weight = mx.sym.Variable('embedding_weight')\r\nembed = mx.sym.Embedding(data=data, weight=embedding_weight, input_dim=100000, output_dim=150)\r\n\r\nprint('Begin Benchmarking embedding')\r\nprint('GPU Forward+Backward')\r\nprint(check_speed(sym=embed, ctx=mx.gpu(), grad_req={'data': 'null', 'embedding_weight': 'write'},\r\n                  data=(128, 100), embedding_weight=(100000, 150)))\r\nprint('CPU Forward+Backward')\r\nprint(check_speed(sym=embed, ctx=mx.cpu(), grad_req={'data': 'null', 'embedding_weight': 'write'},\r\n                  data=(128, 100), embedding_weight=(100000, 150)))\r\nprint('GPU Forward Only')\r\nprint(check_prediction_speed(sym=embed, ctx=mx.gpu(), data=(128, 100), embedding_weight=(100000, 150)))\r\nprint('CPU Forward Only')\r\nprint(check_prediction_speed(sym=embed, ctx=mx.cpu(), data=(128, 100), embedding_weight=(100000, 150)))\r\n```\r\n\r\n```\r\nBegin Benchmarking embedding\r\nGPU Forward+Backward\r\n0.0140898990631\r\nCPU Forward+Backward\r\n0.0440792107582\r\nGPU Forward Only\r\n0.000231640338898\r\nCPU Forward Only\r\n0.000532569885254\r\n```\r\n\r\nWe may need to optimize the kernel."}}
{"actor":{"display_login":"sxjscience"}}