{"action":"created","issue":{"url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab/issues/10","repository_url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab","labels_url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab/issues/10/labels{/name}","comments_url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab/issues/10/comments","events_url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab/issues/10/events","html_url":"https://github.com/hcho3/xgboost-fast-hist-perf-lab/issues/10","id":378675577,"node_id":"MDU6SXNzdWUzNzg2NzU1Nzc=","number":10,"title":"Worst case scenario example (using locks)","user":{"login":"Laurae2","id":9083669,"node_id":"MDQ6VXNlcjkwODM2Njk=","avatar_url":"https://avatars3.githubusercontent.com/u/9083669?v=4","gravatar_id":"","url":"https://api.github.com/users/Laurae2","html_url":"https://github.com/Laurae2","followers_url":"https://api.github.com/users/Laurae2/followers","following_url":"https://api.github.com/users/Laurae2/following{/other_user}","gists_url":"https://api.github.com/users/Laurae2/gists{/gist_id}","starred_url":"https://api.github.com/users/Laurae2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Laurae2/subscriptions","organizations_url":"https://api.github.com/users/Laurae2/orgs","repos_url":"https://api.github.com/users/Laurae2/repos","events_url":"https://api.github.com/users/Laurae2/events{/privacy}","received_events_url":"https://api.github.com/users/Laurae2/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-11-08T10:46:42Z","updated_at":"2018-11-10T10:15:39Z","closed_at":"2018-11-10T10:15:39Z","author_association":"COLLABORATOR","body":"Here is a sort of worst case scenario example:\r\n\r\n* 1 thread: 134.994 seconds\r\n* 2 threads: 132.259 seconds\r\n* 36 threads: 128.281 seconds\r\n\r\nUsing array locks which obviously should be avoided:\r\n\r\n```c\r\n#include <dmlc/omp.h>\r\n#include <perflab/build_hist.h>\r\n#include <omp.h>\r\n#include <vector>\r\n\r\nnamespace perflab {\r\n\r\nvoid GHistBuilder::BuildHist(const std::vector<GradientPair>& gpair,\r\n                             const std::vector<size_t>& instance_set,\r\n                             const GHistIndexMatrix& gmat,\r\n                             std::vector<GHistEntry>* hist) {\r\n  std::fill(data_.begin(), data_.end(), GHistEntry());\r\n\r\n  const auto nthread = static_cast<dmlc::omp_uint>(this->nthread_);\r\n  const size_t nrows = instance_set.size();\r\n  const uint32_t nbin = nbin_;\r\n  const dmlc::omp_uint nbin_omp = dmlc::omp_uint(nbin);\r\n  omp_lock_t locker1[nbin_]; // lock\r\n  omp_lock_t locker2[nbin_omp]; // lock\r\n  \r\n  for (uint32_t i = 0; i < nbin; i++) {\r\n    omp_init_lock(&(locker1[i]));\r\n  }\r\n  for (dmlc::omp_uint i = 0; i < nbin_omp; i++) {\r\n    omp_init_lock(&(locker2[i]));\r\n  }\r\n  \r\n#pragma omp parallel for num_threads(nthread) schedule(guided)\r\n  for (size_t i = 0; i < nrows; ++i) {\r\n    const size_t rid = instance_set[i];\r\n    const size_t ibegin = gmat.row_ptr[rid];\r\n    const size_t iend = gmat.row_ptr[rid + 1];\r\n    const GradientPair stat = gpair[rid];\r\n    for (size_t j = ibegin; j < iend; ++j) {\r\n      const uint32_t bin = gmat.index[j];\r\n      omp_set_lock(&(locker1[bin]));\r\n      data_[bin].Add(stat);\r\n      omp_unset_lock(&(locker1[bin]));\r\n    }\r\n  }\r\n\r\n  /* reduction */\r\n  #pragma omp parallel for num_threads(nthread) schedule(static)\r\n  for (dmlc::omp_uint bin_id = 0; bin_id < nbin_omp; ++bin_id) {\r\n    omp_set_lock(&(locker2[bin_id]));\r\n    (*hist)[bin_id].Add(data_[omp_get_thread_num() * nbin_ + bin_id]);\r\n    omp_unset_lock(&(locker2[bin_id]));\r\n  }\r\n}\r\n\r\n}  // namespace perflab\r\n```\r\n\r\nMaybe we could replace the nested loop with an array reduction, if the only interesting element is `data_`."},"comment":{"url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab/issues/comments/437573310","html_url":"https://github.com/hcho3/xgboost-fast-hist-perf-lab/issues/10#issuecomment-437573310","issue_url":"https://api.github.com/repos/hcho3/xgboost-fast-hist-perf-lab/issues/10","id":437573310,"node_id":"MDEyOklzc3VlQ29tbWVudDQzNzU3MzMxMA==","user":{"login":"Laurae2","id":9083669,"node_id":"MDQ6VXNlcjkwODM2Njk=","avatar_url":"https://avatars3.githubusercontent.com/u/9083669?v=4","gravatar_id":"","url":"https://api.github.com/users/Laurae2","html_url":"https://github.com/Laurae2","followers_url":"https://api.github.com/users/Laurae2/followers","following_url":"https://api.github.com/users/Laurae2/following{/other_user}","gists_url":"https://api.github.com/users/Laurae2/gists{/gist_id}","starred_url":"https://api.github.com/users/Laurae2/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Laurae2/subscriptions","organizations_url":"https://api.github.com/users/Laurae2/orgs","repos_url":"https://api.github.com/users/Laurae2/repos","events_url":"https://api.github.com/users/Laurae2/events{/privacy}","received_events_url":"https://api.github.com/users/Laurae2/received_events","type":"User","site_admin":false},"created_at":"2018-11-10T10:15:39Z","updated_at":"2018-11-10T10:15:39Z","author_association":"COLLABORATOR","body":"Don't try this."}}
{"actor":{"display_login":"Laurae2"}}