{"action":"created","issue":{"url":"https://api.github.com/repos/casadi/casadi/issues/1971","repository_url":"https://api.github.com/repos/casadi/casadi","labels_url":"https://api.github.com/repos/casadi/casadi/issues/1971/labels{/name}","comments_url":"https://api.github.com/repos/casadi/casadi/issues/1971/comments","events_url":"https://api.github.com/repos/casadi/casadi/issues/1971/events","html_url":"https://github.com/casadi/casadi/issues/1971","id":214807095,"number":1971,"title":"Inefficient c-code generation?","user":{"login":"Mathadon","id":5970879,"avatar_url":"https://avatars3.githubusercontent.com/u/5970879?v=3","gravatar_id":"","url":"https://api.github.com/users/Mathadon","html_url":"https://github.com/Mathadon","followers_url":"https://api.github.com/users/Mathadon/followers","following_url":"https://api.github.com/users/Mathadon/following{/other_user}","gists_url":"https://api.github.com/users/Mathadon/gists{/gist_id}","starred_url":"https://api.github.com/users/Mathadon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Mathadon/subscriptions","organizations_url":"https://api.github.com/users/Mathadon/orgs","repos_url":"https://api.github.com/users/Mathadon/repos","events_url":"https://api.github.com/users/Mathadon/events{/privacy}","received_events_url":"https://api.github.com/users/Mathadon/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2017-03-16T19:03:20Z","updated_at":"2017-03-17T19:35:53Z","closed_at":null,"body":"I looked into the generated C code from casadi 3.1 when generating c code from an NLP solver. I have some suggestions based on an analysis of the code. It looks like the code generator could more efficiently formulate code that is inefficiently formulated by the user.\r\n\r\n\r\nCode snippets:\r\n```\r\n  if (arg[1])\r\n    copy(arg[1], 190, w4);\r\n\r\n-- removed some irrelevant code here\r\n\r\n  fill(w9, 25, 0.);\r\n  /* #27: @10 = @9; (@10[0] += @1) */\r\n  copy(w9, 25, w10);\r\n  for (rr=w10+0, ss=(&w1); rr!=w10+1; rr+=1) *rr += *ss++;\r\n  /* #28: @1 = 0 */\r\n  w1 = 0.;\r\n  /* #29: (@10[1] = @1) */\r\n  for (rr=w10+1, ss=(&w1); rr!=w10+2; rr+=1) *rr = *ss++;\r\n  /* #30: @1 = @4[46] */\r\n  for (rr=(&w1), ss=w4+46; ss!=w4+47; ss+=1) *rr++ = *ss;\r\n  /* #31: (@10[1] += @1) */\r\n  for (rr=w10+1, ss=(&w1); rr!=w10+2; rr+=1) *rr += *ss++;\r\n  /* #32: @1 = 0 */\r\n  w1 = 0.;\r\n  /* #33: (@10[2] = @1) */\r\n  for (rr=w10+2, ss=(&w1); rr!=w10+3; rr+=1) *rr = *ss++;\r\n  /* #34: @1 = @4[47] */\r\n  for (rr=(&w1), ss=w4+47; ss!=w4+48; ss+=1) *rr++ = *ss;\r\n  /* #35: (@10[2] += @1) */\r\n  for (rr=w10+2, ss=(&w1); rr!=w10+3; rr+=1) *rr += *ss++;\r\n\r\n--- more of the same code removed here\r\n\r\n  /* #117: (@10[23] = @1) */\r\n  for (rr=w10+23, ss=(&w1); rr!=w10+24; rr+=1) *rr = *ss++;\r\n  /* #118: @1 = @4[68] */\r\n  for (rr=(&w1), ss=w4+68; ss!=w4+69; ss+=1) *rr++ = *ss;\r\n  /* #119: (@10[23] += @1) */\r\n  for (rr=w10+23, ss=(&w1); rr!=w10+24; rr+=1) *rr += *ss++;\r\n  /* #120: @1 = 0 */\r\n  w1 = 0.;\r\n  /* #121: (@10[24] = @1) */\r\n  for (rr=w10+24, ss=(&w1); rr!=w10+25; rr+=1) *rr = *ss++;\r\n  /* #122: @1 = @4[69] */\r\n  for (rr=(&w1), ss=w4+69; ss!=w4+70; ss+=1) *rr++ = *ss;\r\n  /* #123: (@10[24] += @1) */\r\n  for (rr=w10+24, ss=(&w1); rr!=w10+25; rr+=1) *rr += *ss++;\r\n  /* #124: @5 = zeros(46x1, dense) */\r\n  fill(w5, 46, 0.);\r\n\r\n\r\n```\r\nthis code essentially copies inputs of the NLP into other vectors.\r\n\r\nThere are a few things that look like they could be simplified:\r\n\r\nFirst issue:\r\n```\r\n /* #28: @1 = 0 */\r\n  w1 = 0.;\r\n  /* #29: (@10[1] = @1) */\r\n  for (rr=w10+1, ss=(&w1); rr!=w10+2; rr+=1) *rr = *ss++;\r\n  /* #30: @1 = @4[46] */\r\n  for (rr=(&w1), ss=w4+46; ss!=w4+47; ss+=1) *rr++ = *ss;\r\n  /* #31: (@10[1] += @1) */\r\n  for (rr=w10+1, ss=(&w1); rr!=w10+2; rr+=1) *rr += *ss++;\r\n  /* #32: @1 = 0 */\r\n```\r\nThis looks like it essentially sets\r\n\r\n```\r\nw1 = 0\r\nw10[1] = w1\r\nw1 = w[46]\r\nw10[1] = w1\r\n```\r\nor equivalently\r\n```\r\nw10[1] = w[46]\r\n```\r\n\r\nSecond issue:\r\nThis block of code is repeated multiple times. So in the case where a for loop could actually be used, it's not used. \r\n\r\nI looks like these two issues are related to the slicing operations that I do and how I declare variables, which seems to be a 1 to 1 mapping. Code:\r\n\r\n```\r\nMX Uopt \t= MX::sym(\"Uopt\", n_optVarTot, 1);\r\nMX p \t\t= MX::sym(\"p\", n_timeVarTot + n_states, 1);\t\t\t\t\t// parameters: time-dependent inputs and initial states\r\nMX X0 \t\t= p(casadi::Slice(0, n_states));\t\t\t\t\t\t\t// initial states\r\nMX Utime \t= p(casadi::Slice(n_states, n_states+ n_timeVarTot));\r\n\r\nvector<MX> Ui = vector<MX>(intervals);\r\nvector<MX> Uopt_i = vector<MX>(intervals);\r\nvector<MX> Utime_i = vector<MX>(intervals);\t\r\n\r\nfor i = ...\r\n     Ui[i] = MX::zeros(n_inputs,1);\r\n     Uopt_i[i] = Uopt(Slice(n_optVar*i, n_optVar*(i+1)));\r\n     Utime_i[i] = Utime(Slice(n_timeVar*i, n_timeVar*(i+1)));\r\n     int nOpt_i = 0, nTime_i = 0;\r\n     for (int k = 0 ; k < n_inputs; k++){\r\n          if (someCondition) {\r\n               Ui[i](k,0) = someMXVector[nOpt_i]; \r\n               nOpt_i++;\r\n          }else{\t\r\n               Ui[i](k,0) = Utime_i[i](nTime_i,0);\t\r\n               nTime_i++;\r\n          }\r\n     }\r\n}\r\n```\r\n\r\nSo I may be able to avoid it as a user, but still, these operations (mostly the first issue) could be made more efficient when doing some analysis while generating code? After all, all this code excerpt just gets the correct indices for an input vector and there is no need to actually generate code for the temporary variable `Ui` that is declared and used in some operation. The indices are known at compilation time so they can just directly be stored as some index vector over which can be iterated afterwards, instead of copying all numerical values of the index vector.\r\n\r\n\r\nThird issue:\r\nIn snippet\r\n```\r\n  fill(w9, 25, 0.);\r\n  /* #27: @10 = @9; (@10[0] += @1) */\r\n  copy(w9, 25, w10);\r\n```\r\nwhy not just do?\r\n```\r\nfill(w10, 25, 0.);\r\n```\r\nVariable w9 is reused later on, but still it seems like extra overhead/memory is required for these operations. Why is this not omitted?\r\n\r\nDo these questions/suggestions make sense?\r\n\r\nedit: I tried to reformulate the code with a list access, but this does not seem to be supported in C++? I can't get a slice with a custom list (e.g. [0, 1, 5, 3]) of elements either? So then I can't simplify my code unless I reorder the elements in the vector?\r\n"},"comment":{"url":"https://api.github.com/repos/casadi/casadi/issues/comments/287451250","html_url":"https://github.com/casadi/casadi/issues/1971#issuecomment-287451250","issue_url":"https://api.github.com/repos/casadi/casadi/issues/1971","id":287451250,"user":{"login":"jaeandersson","id":2487645,"avatar_url":"https://avatars2.githubusercontent.com/u/2487645?v=3","gravatar_id":"","url":"https://api.github.com/users/jaeandersson","html_url":"https://github.com/jaeandersson","followers_url":"https://api.github.com/users/jaeandersson/followers","following_url":"https://api.github.com/users/jaeandersson/following{/other_user}","gists_url":"https://api.github.com/users/jaeandersson/gists{/gist_id}","starred_url":"https://api.github.com/users/jaeandersson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jaeandersson/subscriptions","organizations_url":"https://api.github.com/users/jaeandersson/orgs","repos_url":"https://api.github.com/users/jaeandersson/repos","events_url":"https://api.github.com/users/jaeandersson/events{/privacy}","received_events_url":"https://api.github.com/users/jaeandersson/received_events","type":"User","site_admin":false},"created_at":"2017-03-17T19:35:52Z","updated_at":"2017-03-17T19:35:52Z","body":"The auto-generated code is just that, auto-generated. There are a lot of optimizations that can be made, but the question is what makes sense to spend time on. An operation such as a copy is usually very fast and rarely a bottleneck in code. Even if it is a bottleneck, how much time should you spend on making something, what, 20 % faster?\r\n\r\nAbout list access and C++, you should be able to slice using a `std::vector<int>{0, 1, 5, 3}`.\r\n\r\nYour code is not structured in an efficient way. Rather than creating variables for \"Uopt\", \"p\" in the beginning and work with slices of them, you'd get more efficient code if you call \"MX::sym\" for each segment and collect them all in `std::vector<MX>` instances. And finally, define `Uopt` and `p` are a \"vertcat\" on those vectors. In general, slicing is not very efficient and should be avoided when possible."}}
{"actor":{"display_login":"jaeandersson"}}