[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 cadabc1aa1cbe30c48a7b730c2907c82abff6336). The changes in 9be698db4a8fa560cfae23795d629b018ad009cf 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 --

M core/src/com/google/inject/internal/InternalContext.java (35)

-- Patch Links --

https://github.com/google/guice/pull/911.patch
https://github.com/google/guice/pull/911.diff

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911

[Tavian Barnes]

The comment

```java
/**
* 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!

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911#issuecomment-84411426

[Sam Berlin]

Nice, I like this. @lukesandberg, you made the recent change IIRC.. WDYT of this patch?

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911#issuecomment-84443769

[Sam Berlin]

@@ -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!

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911/files#r27066562

[Tavian Barnes]

@@ -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?

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911/files#r27069718

[Sam Berlin]

@@ -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.)

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911/files#r27075126

[Tavian Barnes]

@@ -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.

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911/files#r27077348

[Sam Berlin]

ping @mcculls -- I'll gladly merge this after the 10->16 update.

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911#issuecomment-87888063

[Stuart McCulloch]

@sameb done, initial array size updated from 10->16

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911#issuecomment-90946046

[Sam Berlin]

Merged #911.

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911#event-276380564

[Stéphane Nicolas]

Did anyone measure the performance improvement ?

---
Reply to this email directly or view it on GitHub:
https://github.com/google/guice/pull/911#issuecomment-90985468