On Jan 3, 9:10 pm, "Dhanji R. Prasanna" <[email protected]> wrote: > I think it can be improved to be much better in the average case, > currently it goes thru every binding in the injector which is linear > in the asymptotic tight bound (big Theta). > > I need to do something similar for ServletModule's multi-modules > support (i.e. registering servlets from everywhere). If getBindings() > was backed by a Multimap that bucketed bindings by primary type (i.e. > collected bindings that differ only by annotation), then I think both > these cases would be vastly improved in performance. > > The puts into the multimap can be amortized over each binding call and > remains in marginal constant time.
It's linear, but N isn't too large — even if it's a few thousand, iterating through that is quick. This could be even a net-loss since it changes Injector.getInstance() from O(N) to O(T) + O(A), where T is the number of bound types and A is the number of annotations-per-type. For certain values of T and A (such as T=N and A=1), this slows down the common case (calls to getInstance()) to speed up an uncommon one (iterating getBindings()). But there is an obvious improvement — we already have an API that builds and exposes the multimap! It's foolish that the Multibinder code doesn't use it. If you'd like, please change Multibinder to call this API: http://google-guice.googlecode.com/svn/trunk/latest-javadoc/com/google/inject/Injector.html#findBindingsByType(com.google.inject.TypeLiteral) On Optimization I'd want to optimize Guice, but I'd prefer a tool-driven approach. I suspect there will be a few places where changing an eagerly- initialized List into a Lazily-initialized one will have a measurable impact on performance. We should also set specific performance goals and decide what needs to be fast when there are tradeoffs. I think making the main injection loop fast is way more important than making injector-creation fast. I'm under the impression that we're sufficiently fast as-is. That isn't to say that there aren't gains to be made, but I don't believe anyone is deciding whether or not to use Guice (or even whether or not to use multibindings) based on performance. And I'd prefer to release Guice 2.0 sooner than wait until we've optimized the heck out of it. We've got to hold something back for 3.0! --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-guice-dev" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-guice-dev?hl=en -~----------~----~----~----~------~----~------~--~---
