I have some code that naïvely used TGraph::Eval in some tight loops, and I’m trying to get it to run faster. Eval does a linear inter/extrapolation if no spline is provided or requested, and for my purposes I think this is too slow (I used callgrind to profile, most of the time is spent in TGraph::Eval).
Is there a trick to efficiently get the nearest stored TGraph point given an arbitrary X value? Should I code up a linear search, or binary search of the X values?
Jean-François
I coded up something with std::lower_bound, and it does seem to be about 32% faster. Can someone comment on whether I am doing this in a reasonable manner? My attached script attempts to compare TGraph::Eval with the non-interpolating std::lower_bound.
Here’s what I get when I run it:
[code]$ root6 -b -q -l profile_eval.C+
root [0]
Processing profile_eval.C+…
Info in TMacOSXSystem::ACLiC: creating shared library /Users/jfcaron/Projects/Proto2BeamTest2/code_test/./profile_eval_C.so
Real time 0:00:17, CP time 17.060
Real time 0:00:11, CP time 11.610
(int) 0
[/code]
Jean-François
profile_eval.C (741 Bytes)
Since the big difference in the algorithms is the search (linear vs. binary), your implementation could be presented in a much better light by using a bigger array. And what comes to the tight loop aspect, virtual function GetPoint in the loop looks a bit questionable, although compared to the search perhaps it has little if any effect in practice.