[guice] Improve performance of internal DependencyStack collection (#911)
Stuart McCulloch
Recent changes to the internal dependency stack in InternalContext reduced memory consumption at the cost of overall performance (see cadabc1). The changes in 9be698d helped, but it's still not as good as the original implementation. One reason might be that ArrayList.removeRange will always trigger a call to System.arrayCopy, even when you're only removing a range at the end of the list.
Since the internal API needed from DependencyStack is minimal, I tried re-implementing it as a thin wrapper around an array. The following implementation is faster than the original (at least on my local machine) while still retaining the memory improvements.
WDYT? Note this is a bare-bones implementation, extra checks can be added as necessary.
You can view, comment on, or merge this pull request online at:
https://github.com/google/guice/pull/911
Commit Summary
- Improve performance of internal DependencyStack collection
File Changes
Patch Links:
—
Reply to this email directly or view it on GitHub.
Tavian Barnes
The comment
/** * Keeps track of the hierarchy of types needed during injection. * * <p>This is a pairwise combination of dependencies and sources, with dependencies or keys on * even indices, and sources on odd indices. This structure is to avoid the memory overhead of * DependencyAndSource objects, which can add to several tens of megabytes in large applications. */
could be moved down to the DependencyStack implementation. LGTM otherwise!
Sam Berlin
Nice, I like this. @lukesandberg, you made the recent change IIRC.. WDYT of this patch?
Sam Berlin
In core/src/com/google/inject/internal/InternalContext.java:
> @@ -106,10 +98,36 @@ public void popState() {
> return builder.build();
> }
>
> - private static final class DependencyStack extends ArrayList<Object> {
> - void pop() {
> - int sz = size();
> - removeRange(sz - 2, sz);
> + /**
> + * Keeps track of the hierarchy of types needed during injection.
> + *
> + * <p>This is a pairwise combination of dependencies and sources, with dependencies or keys on
> + * even indices, and sources on odd indices. This structure is to avoid the memory overhead of
> + * DependencyAndSource objects, which can add to several tens of megabytes in large applications.
> + */
> + private static final class DependencyStack {
> + private Object[] elements = new Object[10];
change this to 16 instead? thanks!
Tavian Barnes
In core/src/com/google/inject/internal/InternalContext.java:
> @@ -106,10 +98,36 @@ public void popState() {
> return builder.build();
> }
>
> - private static final class DependencyStack extends ArrayList<Object> {
> - void pop() {
> - int sz = size();
> - removeRange(sz - 2, sz);
> + /**
> + * Keeps track of the hierarchy of types needed during injection.
> + *
> + * <p>This is a pairwise combination of dependencies and sources, with dependencies or keys on
> + * even indices, and sources on odd indices. This structure is to avoid the memory overhead of
> + * DependencyAndSource objects, which can add to several tens of megabytes in large applications.
> + */
> + private static final class DependencyStack {
> + private Object[] elements = new Object[10];
I'm really sure what the usage patterns of InternalContext are like, but could it be worth delaying the allocation until the first dependency is pushed?
Sam Berlin
In core/src/com/google/inject/internal/InternalContext.java:
> @@ -106,10 +98,36 @@ public void popState() {
> return builder.build();
> }
>
> - private static final class DependencyStack extends ArrayList<Object> {
> - void pop() {
> - int sz = size();
> - removeRange(sz - 2, sz);
> + /**
> + * Keeps track of the hierarchy of types needed during injection.
> + *
> + * <p>This is a pairwise combination of dependencies and sources, with dependencies or keys on
> + * even indices, and sources on odd indices. This structure is to avoid the memory overhead of
> + * DependencyAndSource objects, which can add to several tens of megabytes in large applications.
> + */
> + private static final class DependencyStack {
> + private Object[] elements = new Object[10];
I think the vast majority of times (if not every time) a context is created, it's when there's a dependency that's going to be pushed on it. (Dependency tracking is basically the whole reason that the context exists.)
Tavian Barnes
In core/src/com/google/inject/internal/InternalContext.java:
> @@ -106,10 +98,36 @@ public void popState() {
> return builder.build();
> }
>
> - private static final class DependencyStack extends ArrayList<Object> {
> - void pop() {
> - int sz = size();
> - removeRange(sz - 2, sz);
> + /**
> + * Keeps track of the hierarchy of types needed during injection.
> + *
> + * <p>This is a pairwise combination of dependencies and sources, with dependencies or keys on
> + * even indices, and sources on odd indices. This structure is to avoid the memory overhead of
> + * DependencyAndSource objects, which can add to several tens of megabytes in large applications.
> + */
> + private static final class DependencyStack {
> + private Object[] elements = new Object[10];
Oh duh, I forgot that the current dependency would always be on the stack.
Sam Berlin
ping @mcculls -- I'll gladly merge this after the 10->16 update.
Stuart McCulloch
@sameb done, initial array size updated from 10->16
Sam Berlin
Merged #911.
Stéphane Nicolas
Did anyone measure the performance improvement ?