Hi Rahul, option 1) again this is a problem when you distribute a library across many machines (cluster), especially if it’s not a homogenous cluster. will you distribute all of those binaries… not to talk about maintaining and distributing these binaries.
option 2) converging to more optimal solution, but where does this idea comes from: "Consider this case - I want to transfer my data to GPU only once and run multiple linalg operations on it before transferring it back to CPU. This cannot be done with a plugin design” why cannot it be done? i mean yes, this is true when you design the thing badly, or to say less optimal. as shogun will be soon plugin-ized, i think the linalg should be plugin-ized as well. i.e. have a different backends to do the linalg and then based on the node (whether the host supports it or not), plugin availability and whether it’s worth to do it (e.g. transfer time of CPU<->GPU mem) will use the right plugin. i mean one obvious way to overcome the problem of virtual functions is using opaque pointer (for the backend) and define operations over that…see for example the whole gdk/gtk library. viktor > On Apr 18, 2016, at 9:07 AM, Rahul De <[email protected]> wrote: > > Hi guys, > > Let's come to an agreement about a few things. Our main goal is not to > glorify one design pattern over the other - as I am quite sure that both of > them exist for a reason. We just want to find out what's best for Shogun. All > these bench-marking and brainstorming are of no use if nothing constructive > comes out of this discussion. So let me try to point out a few things about > linalg and we can come to an agreement once and for all. > > (CC-ing Bjorn and Sergey as well) > > Option 1. We implement linalg as a header only library as it is right now, > with a few modifications. > > Modifications are: > (a) we don't automatically convert SGMatrix to GPUMatrix. [yes we can later > figure out whether the decision to transfer data CPU <--> GPU can be > automated, based on a set of rules. But let's not stop the present progress > of the current GSoC projects because of that. If this thing can be automated, > it will be an additional layer on top of this design]. > (b) All the methods in linalg would be simple overloaded methods, with their > corresponding types. > (c) For SGMatrix, we will use Eigen3 and for GPUMatrix we will use ViennaCL. > That's it. > (d) At places, when we need to add our custom implementation, we'll add our > native code. This thing can be done with a linalg interface, called "custom". > (e) The devs request for a GPU type when they want a GPU to compute. This > would return a GPU type with the data copied if ViennaCL is there, otherwise > the computation would go on with CPU. > > Pros: > (a) No overhead for the calls. > (b) Easy to read, easy to write, easy to execute. > (c) Since it is header only, the methods have a high change to be inlined by > the compiler. > > Cons: > (a) We release two different binaries of Shogun. One is with ViennaCL > enabled, and other is ViennaCL disabled. > > Option 2: We implement linalg with plugins. In absence of a ViennaCL plugin, > this would use Eigen3 always. If ViennaCL plugin is there, it would use GPU > methods where the devs want to use this. > > Pros: > (a) One binary for Shogun > > Cons: > (a) Since this would be implemented as a plugin, we have to design the API as > overridden methods. Each virtual method in linalg would have to take > SGMatrix/SGVector as a type. Then it will always transfer data from CPU > to/from GPU in each call. This would make it way too slow when ViennaCL > plugin is being used. Consider this case - I want to transfer my data to GPU > only once and run multiple linalg operations on it before transferring it > back to CPU. This cannot be done with a plugin design. (Bjorn, Sergey, I need > your inputs here). > (b) Can only be implemented once the plugin project is complete. > > Is there any way we can come up with something which (a) doesn't need two > binaries and (b) will not pose so much overhead? Please suggest, as we need > to plan for linalg soon. In absence of an alternative idea, I'd say we go on > with option 1 for now. We can add the ViennaCL plugin (if we think it's worth > doing it this way) once we have the plugin framework ready after this GSoC. > > Please suggest/discuss! > > > > On Mon, Apr 4, 2016 at 8:29 PM, Heiko Strathmann <[email protected]> > wrote: > Enjoy!! > > > On Monday, 4 April 2016, Viktor Gal <[email protected]> wrote: > Sorry guys im on vacation... Today is my last day... Will get back tomorrow > > On Apr 4, 2016, at 15:16, Heiko Strathmann <[email protected]> wrote: > >> any thoughts on the benchmark, Viktor? >> >> 2016-04-01 16:57 GMT+01:00 Heiko Strathmann <[email protected]>: >> It would also be interesting to run this within the Shogun framework. >> Say call two dot product methods (with say eigen backend) many many times >> where we multiply feature vectors that are extracted using the standard >> shogun mechanics >> >> 2016-04-01 16:54 GMT+01:00 Heiko Strathmann <[email protected]>: >> Rahul, are these findings consistent with the hayai test? >> >> 2016-04-01 16:53 GMT+01:00 Heiko Strathmann <[email protected]>: >> So Viktor, I think we should find out what is going on. But what about you >> help a bit here? >> >> 2016-04-01 16:49 GMT+01:00 Rahul De <[email protected]>: >> before I check perf, I just benchmarked with google benchmarking tool >> (https://github.com/google/benchmark) and here are the results - >> https://gist.github.com/lambday/ccc7f289e965223e48f5fbda5882313b. >> >> On Fri, Apr 1, 2016 at 9:00 PM, Rahul De <[email protected]> wrote: >> Looking into it right now. >> >> On Fri, Apr 1, 2016 at 8:57 PM, Viktor Gal <[email protected]> wrote: >> Have you tried to use perf to really profile wtf is happening? >> >> On Apr 1, 2016, at 17:07, Rahul De <[email protected]> wrote: >> >>> Hi, >>> >>> I just reran the benchmark that is mentioned in the >>> [3](http://eli.thegreenplace.net/2013/12/05/the-cost-of-dynamic-virtual-calls-vs-static-crtp-dispatch-in-c) >>> post earlier. Here is the driver program that I used >>> (https://gist.github.com/lambday/d31506225ce78759e1b5e5945f770bc8). >>> >>> As we can see, this gives roughly 6.8x better performance with compile-time >>> determined things (which is the same as the author of the blog mentioned in >>> his tests). >>> >>> A very interesting thing I noticed while I ran this benchmark - if I keep >>> the objects on stack and call the method, the difference between the two is >>> hardly noticeable. My guess would be - the compiler in this case performs >>> the devirtualization optimizations (which is by default on with -O3 I >>> suppose) and gets rid of all vtables stuff internally. But if the objects >>> are on heap (as the case with Shogun), the difference is quite significant. >>> >>> >>> On Fri, Apr 1, 2016 at 7:04 PM, Heiko Strathmann >>> <[email protected]> wrote: >>> Yeah definitely. >>> But as a first step, lets benchmark the linalg calls themselves. Then we >>> can measure the effect when being used in say KMeans. >>> >>> There was also this Kmeans thing where using a linalg call significantly >>> slowed the whole algorithm down. >>> >>> 2016-04-01 14:17 GMT+01:00 Viktor Gal <[email protected]>: >>> heheh this is a paper from 95. i mean many things changed since 95 in cpu >>> arch and compilers :) >>> so let’s try to put together a benchmarking for this, not only for linalg >>> but for whole shogun (this is strictly for design of the library but not >>> like how fast is kmeans or knn, as for that we already have a benchmark - >>> to compare with other libraries as well). >>> >>> viktor >>> >>> > On Apr 1, 2016, at 2:10 PM, Rahul De <[email protected]> wrote: >>> > >>> > [6] >>> > http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.578&rep=rep1&type=pdf >>> > >>> > On Fri, Apr 1, 2016 at 5:36 PM, Rahul De <[email protected]> >>> > wrote: >>> > I will say - it's easy way of doing things. But calling a virtual >>> > functions harms the locality of reference in L1 cache line. Looking at >>> > the way most compilers implement virtual functions [1], there are two >>> > extra load instructions per call, which, although doesn't look much, >>> > leads to cache miss and introduce non-determinism (check [2]), in >>> > addition to the extra storage per class, which, for the sake of >>> > discussion, can be ignored. On the other hand, if we use CRTP, the most >>> > significant difference comes from compiler optimizations and inlining, >>> > which the compiler is blind to in case of virtual functions (check [3]). >>> > >>> > I could find one benchmark I did >>> > (https://gist.github.com/lambday/73b9e68ec08e2da25967), which sort of >>> > supports these facts. Yes, I haven't used proper ways of benchmarking for >>> > this but post [3] does that really nicely. >>> > >>> > My point is: just because we do it all over Shogun, doesn't make it the >>> > right (or only) way to do it. We are not Java, we have a much powerful >>> > language in hand which can be super fast, if coded properly. Let's have a >>> > look at Eigen or ViennaCL or some other linalg libraries for that matter >>> > and we can hardly find any virtuals. Yes, some of them are header only, >>> > we are not, so we do need to keep virtuals in some places (you're right, >>> > they are nice to interface, goes nicely with SWIG), but for the >>> > performance critical portions in Shogun, e.g. linalg, why take the >>> > sub-optimal solution? :) >>> > >>> > In the latest code I have been working on (big-testing), I separated >>> > Shogun interfaces from most of the internals, which allows me to do some >>> > of those non-virtual templated stuffs, without breaking SWIG. If this >>> > concept is proven to give any extra edge, I think this policy can be >>> > adapted for other places in Shogun as well. >>> > >>> > [1] https://isocpp.org/wiki/faq/virtual-functions#dyn-binding2 >>> > [2] >>> > http://stackoverflow.com/questions/20439099/performance-variability-of-c-pure-virtual-function-calls >>> > [3] >>> > http://eli.thegreenplace.net/2013/12/05/the-cost-of-dynamic-virtual-calls-vs-static-crtp-dispatch-in-c >>> > >>> > Additional notes: >>> > [4] Section 5.3 of http://www.stroustrup.com/performanceTR.pdf >>> > [5] http://www.gotw.ca/publications/mill18.htm >>> > >>> > Best, >>> > >>> > >>> > On Fri, Apr 1, 2016 at 4:28 PM, Viktor Gal <[email protected]> wrote: >>> > 12:29 <@HeikoS> wiking: "if we can avoid virtual calls, why not do that?” >>> > >>> > because interfaces are a really clean and nice way to do things. >>> > >>> > so please could you provide me a benchmark that proves that virtual >>> > function calls are giving you a significant runtime overhead…? >>> > because till then i call plain bullshit about that… >>> > >>> > cheers, >>> > viktor >>> > >>> > >>> > >>> > >>> > -- >>> > Best, >>> > Rahul >>> > +919620408085 >>> > >>> > >>> > >>> > -- >>> > Best, >>> > Rahul >>> > +919620408085 >>> >>> >>> >>> >>> >>> -- >>> Best, >>> Rahul >>> +919620408085 >> >> >> >> -- >> Best, >> Rahul >> +919620408085 >> >> >> >> -- >> Best, >> Rahul >> +919620408085 >> >> >> >> > > > > -- > Best, > Rahul > +919620408085
