## speed-dreams-devel

 [Speed-dreams-devel] Optimization of calculation of torque from rads From: W.-D. Beelitz - 2010-06-20 10:56:56 Attachments: Message as HTML ```Hello all, what about optimization of calculation of torque from rads: (engine.cpp) tdble CalculateTorque (tEngine* engine, tdble rads) { tEngineCurve *curve = &(engine->curve); tdble Tq = curve->data[0].Tq; tdble Tmax = curve->data[0].Tq; tdble Tmin = curve->data[0].Tq * 0.5f; tdble rpm_max = curve->data[0].rads; tdble rpm_min = -1.0; tdble alpha = 0.0; for (int i = 0; i < curve->nbPts; i++) { if (rads > curve->data[i].rads) { Tmin = curve->data[i].Tq; rpm_min = curve->data[i].rads; if (icurve.nbPts) { Tmax = curve->data[i+1].Tq; rpm_max = curve->data[i+1].rads; } } } alpha = (rads - rpm_min) / (rpm_max - rpm_min); Tq = (float)((1.0-alpha) * Tmin + alpha * Tmax); return Tq; } Here the calculation starts with i = 0, means with the part of the torque characteristic that is nearly never used while racing and the search is done linear to higher values. Starting at the other side of the characteristic should reduce the time to find the correct value without changes to it. Regards Wolf-Dieter ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Jean-Philippe - 2010-06-20 11:37:40 ```Hi, Wolf-Dieter, and all. > what about optimization of calculation of torque from rads: > (engine.cpp) > what about optimization by avoiding config code in update functions: > > The simulation uses two typical functions, the config function and the > update function. The config function is called once, the update function > is called again and again while race. > > As example have a look to the transmission.cpp. > what about optimizations using precalculation of repeatedly used > constant values: > > There are some values that are computed again and again. To reduce the > cpu time consumption, we could precalculate it. I agree with you that these code sections could well be optimized ... But as always when talking about code optimizations, the real question is : are these code sections in the top 10 real bottle necks at run-time ? Because it's really no use optimizing a function that takes 0.1 % elapsed time at each simulation loop if other functions that really take more than 5 % are not fully optimized themselves ... That's why I believe we should continue on the profiling task before deciding what code sections we must work on : - Mart and I already published profiling results in doc/develdoc/profiling : these are compressed files in the linux Call Grind format ... anyone able to install KCacheGrind can examine these detailled results (don't know if other softwares can open these files ... ?) these result files are still to analyse ... Mart already noticed some functions in robottools that could be good targets ... to be continued ... - can anyone run profiling sessions and publish results under Windows ? (has anyone tried Very sleepy ? Very simple to setup and use, may be it could help ... see here for more references : http://stackoverflow.com/questions/67554/whats-the-best-free-c-profiler-for-windows-if-there-are Who can try ?) Cheers, Jean-Philippe. ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: W.-D. Beelitz - 2010-06-20 13:46:20 ```Hello Jean-Philippe, > Because it's really no use optimizing a function that takes 0.1 % elapsed time > at each simulation loop if other functions that really take more than 5 % > are not fully optimized themselves ... Yes, I fully agree, and this is why I ask for instead of just doing it. (But remember, all code that is in the simulation is called for each car each time step). While the last championships I did some research together with Daniel Schellhammer. His robot was consuming a lot of cpu time at my windows system. It was developed with linux and using our time functions we found, that this was only with windows. Using the code with linux the consumed time was not more than for other robots. So it is a pity, that valgrind is not usable for windows Cheers Wolf-Dieter -----Ursprüngliche Nachricht----- Von: Jean-Philippe [mailto:jpmeuret@...] Gesendet: 20 June 2010 13:46 An: speed-dreams-devel@...; Mart Kelder Betreff: Re: [Speed-dreams-devel] Optimization of calculation of torque from rads Hi, Wolf-Dieter, and all. > what about optimization of calculation of torque from rads: > (engine.cpp) > what about optimization by avoiding config code in update functions: > > The simulation uses two typical functions, the config function and the > update function. The config function is called once, the update function > is called again and again while race. > > As example have a look to the transmission.cpp. > what about optimizations using precalculation of repeatedly used > constant values: > > There are some values that are computed again and again. To reduce the > cpu time consumption, we could precalculate it. I agree with you that these code sections could well be optimized ... But as always when talking about code optimizations, the real question is : are these code sections in the top 10 real bottle necks at run-time ? Because it's really no use optimizing a function that takes 0.1 % elapsed time at each simulation loop if other functions that really take more than 5 % are not fully optimized themselves ... That's why I believe we should continue on the profiling task before deciding what code sections we must work on : - Mart and I already published profiling results in doc/develdoc/profiling : these are compressed files in the linux Call Grind format ... anyone able to install KCacheGrind can examine these detailled results (don't know if other softwares can open these files ... ?) these result files are still to analyse ... Mart already noticed some functions in robottools that could be good targets ... to be continued ... - can anyone run profiling sessions and publish results under Windows ? (has anyone tried Very sleepy ? Very simple to setup and use, may be it could help ... see here for more references : http://stackoverflow.com/questions/67554/whats-the-best-free-c-profiler-for- windows-if-there-are Who can try ?) Cheers, Jean-Philippe. ---------------------------------------------------------------------------- -- ThinkGeek and WIRED's GeekDad team up for the Ultimate GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the lucky parental unit. See the prize list and enter to win: http://p.sf.net/sfu/thinkgeek-promo _______________________________________________ Speed-dreams-devel mailing list Speed-dreams-devel@... https://lists.sourceforge.net/lists/listinfo/speed-dreams-devel ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Jean-Philippe - 2010-06-20 14:37:41 ```Wolf-Dieter, >His robot was consuming a lot of cpu time at my windows system. It was >developed with linux and using our time functions we found, that this was >only with windows. Using the code with linux the consumed time was not more >than for other robots. So it is a pity, that valgrind is not usable for >windows I agree (I have this problem at work too). I recently tried Very sleepy (Free and very simple to setup and use, but again simply a frame pointer sampler ; I fear its default sampling rate - 100 Hz - is too low for SD, and if we increase it to more than 1000 - needed at least in SD - we'd considerably slow down the game ... but may be useful yet in blind mode = result only mode (no graphics)). See here for more references : http://stackoverflow.com/questions/67554/whats-the-best-free-c-profiler-for-windows-if-there-are If you have an AMD processor, AMD Code Analyst is certainly a good processor level program counter sampler (like the one I used under Linux, that is OProfile). I'm not 100% sure it is free, but suppose so. It works under Windows and Linux. If you have an Intel CPU, VTune may be also good ... but not free for sure. Cheers, Jean-Philippe. ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Christos Dimitrakakis - 2010-06-20 20:08:39 ```For the torque curve, the best thing to do would be to re-use the spline code, which does a binary search. ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: W.-D. Beelitz - 2010-06-21 05:47:00 ```Hello Christos, what about starting with the last used segment of the torque characteristic? The value of rpms is changing "slowly" in most cases. Regards Wolf-Dieter -----Ursprüngliche Nachricht----- Von: Christos Dimitrakakis [mailto:olethros@...] Gesendet: 20 June 2010 22:15 An: speed-dreams-devel@... Betreff: Re: [Speed-dreams-devel] Optimization of calculation of torque from rads For the torque curve, the best thing to do would be to re-use the spline code, which does a binary search. ---------------------------------------------------------------------------- -- ThinkGeek and WIRED's GeekDad team up for the Ultimate GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the lucky parental unit. See the prize list and enter to win: http://p.sf.net/sfu/thinkgeek-promo _______________________________________________ Speed-dreams-devel mailing list Speed-dreams-devel@... https://lists.sourceforge.net/lists/listinfo/speed-dreams-devel ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Christos Dimitrakakis - 2010-06-21 07:19:49 ```On 21/06/10 07:46, W.-D. Beelitz wrote: > The value of rpms is changing "slowly" in most cases. Sure, you could do that and it might save a bit of time (though binary search already saves a lot). You'd need to start your binary search from the previous point. That would require modifying the search a little bit. This is only important as long as we are talking about torque curves with 100s of points though, really. :) ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Christos Dimitrakakis - 2010-06-21 07:21:47 ```On 21/06/10 07:46, W.-D. Beelitz wrote: > The value of rpms is changing "slowly" in most cases. PS. As you increase the number of points on the curve, then starting from the last used point does not help, since there can be arbitrarily many points between the new and last RPM value. So you'd only expect the 'last point' to give you, at best, a constant-factor speed-up. ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Christos Dimitrakakis - 2010-06-21 07:29:42 ```On 21/06/10 09:21, Christos Dimitrakakis wrote: > On 21/06/10 07:46, W.-D. Beelitz wrote: >> The value of rpms is changing "slowly" in most cases. PS2. So, the ideal way to implement this is as follows: 1. Assume we have r_1, ..., r_n rpm points on the spline, with values T_1, ..., T_n. 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval containing r (i.e. so that j = i + 1) 3. Let r' be the current rpm value. 4. If r' > r, do binary search on the interval [r_i, r_n], else do binary search on the interval [r_1, r_j]. 5. Obtain a new interval [r'_i, r'_j]. As you can see, this reduces computation by a factor of 2. So, original complexity: O(n), binary search O(log n), and this O(log sqrt(n)). Again, I wouldn't do a linear search because once the number of points n increases, the amount of search increases with rate O(n). ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: W.-D. Beelitz - 2010-06-21 12:06:58 ```Hello Christos, sorry but based on your proposal I would use: > 1. Assume we have r_1, ..., r_n rpm points with values T_1, ..., T_n. > 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval containing r (i.e. so that j = i + 1) > 3. Let r' be the current rpm value. 4. If r' > r_j, do a binary search on the interval [r_j, r_n] else if r' < r_i do a binary search on the interval [r_1,r_i] else interpolate T' in [r_i, r_j] at r'. 5. Obtain a new interval [r'_i, r'_j]. And caused by the context I would expect that if r' > r_j the resulting interval will be [r_j, r_j+1] and for r' < r_i [r_i-1, r_i]. So for |r'- r| < eps we should look at previous/next interval if not the current interval matches. For |r'- r| > eps we should use the binary search as described above. Having no r we should use the binary search on the interval [r_1,r_n]. Regards Wolf-Dieter -----Ursprüngliche Nachricht----- Von: Christos Dimitrakakis [mailto:olethros@...] Gesendet: 21 June 2010 09:31 An: speed-dreams-devel@... Betreff: Re: [Speed-dreams-devel] Optimization of calculation of torque from rads On 21/06/10 09:21, Christos Dimitrakakis wrote: > On 21/06/10 07:46, W.-D. Beelitz wrote: >> The value of rpms is changing "slowly" in most cases. PS2. So, the ideal way to implement this is as follows: 1. Assume we have r_1, ..., r_n rpm points on the spline, with values T_1, ..., T_n. 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval containing r (i.e. so that j = i + 1) 3. Let r' be the current rpm value. 4. If r' > r, do binary search on the interval [r_i, r_n], else do binary search on the interval [r_1, r_j]. 5. Obtain a new interval [r'_i, r'_j]. As you can see, this reduces computation by a factor of 2. So, original complexity: O(n), binary search O(log n), and this O(log sqrt(n)). Again, I wouldn't do a linear search because once the number of points n increases, the amount of search increases with rate O(n). ---------------------------------------------------------------------------- -- ThinkGeek and WIRED's GeekDad team up for the Ultimate GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the lucky parental unit. See the prize list and enter to win: http://p.sf.net/sfu/thinkgeek-promo _______________________________________________ Speed-dreams-devel mailing list Speed-dreams-devel@... https://lists.sourceforge.net/lists/listinfo/speed-dreams-devel ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Christos Dimitrakakis - 2010-06-21 20:21:00 ```On 21/06/10 14:06, W.-D. Beelitz wrote: > Hello Christos, > > sorry but based on your proposal I would use: > >> 1. Assume we have r_1, ..., r_n rpm points with values T_1, ..., T_n. >> 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval > containing r (i.e. so that j = i + 1) >> 3. Let r' be the current rpm value. > 4. If r'> r_j, do a binary search on the interval [r_j, r_n] > else if r'< r_i do a binary search on the interval [r_1,r_i] > else interpolate T' in [r_i, r_j] at r'. Yes, correct. > > 5. Obtain a new interval [r'_i, r'_j]. > > And caused by the context I would expect that if r'> r_j the resulting > interval will be [r_j, r_j+1] > and for r'< r_i [r_i-1, r_i]. > > So for |r'- r|< eps we should look at previous/next interval if not the > current interval matches. OK. But what if |r' - r|< eps and we don't find r' in the previous/next interval? > For |r'- r|> eps we should use the binary search as described above. Well, not really. If the interval is not contained in previous/next then we should look at either [r_1, r_{i-1}] or [r_{j+1}, r_n]. > Having no r we should use the binary search on the interval [r_1,r_n]. > OK, but the binary search should be in either [r_1, r_i] or [r_j, r_n] (with i-1/j+ 1 if we have already searched previous/next intervals). > Regards > > Wolf-Dieter > > -----Ursprüngliche Nachricht----- > Von: Christos Dimitrakakis [mailto:olethros@...] > Gesendet: 21 June 2010 09:31 > An: speed-dreams-devel@... > Betreff: Re: [Speed-dreams-devel] Optimization of calculation of torque from > rads > > On 21/06/10 09:21, Christos Dimitrakakis wrote: >> On 21/06/10 07:46, W.-D. Beelitz wrote: >>> The value of rpms is changing "slowly" in most cases. > > PS2. So, the ideal way to implement this is as follows: > > 1. Assume we have r_1, ..., r_n rpm points on the spline, with values > T_1, ..., T_n. > 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval > containing r (i.e. so that j = i + 1) > 3. Let r' be the current rpm value. > 4. If r'> r, do binary search on the interval [r_i, r_n], > else do binary search on the interval [r_1, r_j]. > 5. Obtain a new interval [r'_i, r'_j]. > > As you can see, this reduces computation by a factor of 2. So, original > complexity: O(n), binary search O(log n), and this O(log sqrt(n)). > > Again, I wouldn't do a linear search because once the number of points n > increases, the amount of search increases with rate O(n). > > > ---------------------------------------------------------------------------- > -- > ThinkGeek and WIRED's GeekDad team up for the Ultimate > GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the > lucky parental unit. See the prize list and enter to win: > http://p.sf.net/sfu/thinkgeek-promo > _______________________________________________ > Speed-dreams-devel mailing list > Speed-dreams-devel@... > https://lists.sourceforge.net/lists/listinfo/speed-dreams-devel > > > > ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: W.-D. Beelitz - 2010-06-21 18:45:15 ```Hello Christos, here a simple replacement for CalculateTorque in simuV3. tdble CalculateTorque2 (tEngine* engine, tdble rads) { //double StartTimeStamp = RtTimeStamp(); // To get used time tEngineCurve *curve = &(engine->curve); int i = engine->lastInterval; // Get last interval, is set to 0 at config engine tdble Tq; tdble rpm_min = curve->data[i].rads; // Current lower limit tdble rpm_max = curve->data[i+1].rads; // Current upper limit tdble alpha; // Ratio between limits if (rads > rpm_max) { if (i < engine->curve.nbPts) { rpm_min = rpm_max; engine->lastInterval = ++i; rpm_max = curve->data[i+1].rads; } } else if (rads < rpm_min) { if (i > 0) { rpm_max = rpm_min; engine->lastInterval = --i; rpm_min = curve->data[i].rads; } } alpha = (rads - rpm_min) / (rpm_max - rpm_min); Tq = (float)((1.0-alpha) * curve->data[i].Tq + alpha * curve->data[i+1].Tq); //SimTicks2 += RtDuration(StartTimeStamp); // To get used time return Tq; } The ratio of time consumed: CalculateTorque = 2.5 * CalculateTorque2. Regards Wolf-Dieter -----Ursprüngliche Nachricht----- Von: Christos Dimitrakakis [mailto:olethros@...] Gesendet: 21 June 2010 09:31 An: speed-dreams-devel@... Betreff: Re: [Speed-dreams-devel] Optimization of calculation of torque from rads On 21/06/10 09:21, Christos Dimitrakakis wrote: > On 21/06/10 07:46, W.-D. Beelitz wrote: >> The value of rpms is changing "slowly" in most cases. PS2. So, the ideal way to implement this is as follows: 1. Assume we have r_1, ..., r_n rpm points on the spline, with values T_1, ..., T_n. 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval containing r (i.e. so that j = i + 1) 3. Let r' be the current rpm value. 4. If r' > r, do binary search on the interval [r_i, r_n], else do binary search on the interval [r_1, r_j]. 5. Obtain a new interval [r'_i, r'_j]. As you can see, this reduces computation by a factor of 2. So, original complexity: O(n), binary search O(log n), and this O(log sqrt(n)). Again, I wouldn't do a linear search because once the number of points n increases, the amount of search increases with rate O(n). ---------------------------------------------------------------------------- -- ThinkGeek and WIRED's GeekDad team up for the Ultimate GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the lucky parental unit. See the prize list and enter to win: http://p.sf.net/sfu/thinkgeek-promo _______________________________________________ Speed-dreams-devel mailing list Speed-dreams-devel@... https://lists.sourceforge.net/lists/listinfo/speed-dreams-devel ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: Christos Dimitrakakis - 2010-06-21 20:25:29 ```On 21/06/10 20:44, W.-D. Beelitz wrote: > Hello Christos, > > here a simple replacement for CalculateTorque in simuV3. > I think you are missing a for or while loop here. See drivers/bt/spline.cpp for an example. ```
 Re: [Speed-dreams-devel] Optimization of calculation of torque from rads From: W.-D. Beelitz - 2010-06-21 20:35:10 ```Hello Christos, no, it works fine without ;-). The changes in rads are very small, so from time step to time step it never has to go more than one step back or forward (The min. delta rads in an interval is 500). Regards Wolf-Dieter -----Ursprüngliche Nachricht----- Von: Christos Dimitrakakis [mailto:olethros@...] Gesendet: 21 June 2010 22:31 An: W.-D. Beelitz Cc: speed-dreams-devel@... Betreff: Re: AW: [Speed-dreams-devel] Optimization of calculation of torque from rads On 21/06/10 20:44, W.-D. Beelitz wrote: > Hello Christos, > > here a simple replacement for CalculateTorque in simuV3. > I think you are missing a for or while loop here. See drivers/bt/spline.cpp for an example. ```