无内存分配游戏

Question

我的代码基本上没有分配，但是当在60fps时，GC每30秒运行一次。使用DDMS检查应用程序的分配显示有很多SimpleListIterator被分配。还有一些东西被分配，因为我使用了Exchanger。 SimpleListIterator来自于for each循环for (T obj : objs) {}。我原以为编译器/翻译器会优化那些不使用迭代器的类型（我基本上只使用ArrayList），但事实并非如此。

我该如何避免分配所有这些SimpleListIterators？一种解决方案是切换到常规for循环for (int i = 0; i < size; ++i) {}，但我喜欢for each循环:(

另一种方法是扩展ArrayList，返回仅分配一次的Iterator。

我想到的第三种方法是使用一个静态辅助函数，它返回一个重用 Iterator 的 Collection。我已经拼凑出了类似这样的东西，但强制转换感觉非常不安全和 hackish。但应该是线程安全的，因为我使用了 ThreadLocal。请参见下面的代码：

public class FastIterator {
    private static ThreadLocal<Holder> holders = new ThreadLocal<Holder>();

    public static <T> Iterable<T> get(ArrayList<T> list) {
        Holder cont = holders.get();

        if (cont == null) {
            cont = new Holder();

            cont.collection = new DummyCollection<T>();
            cont.it = new Iterator<T>();

            holders.set(cont);
        }

        Iterator<T> it = (Iterator<T>) cont.it;
        DummyCollection<T> collection = (DummyCollection<T>) cont.collection;

        it.setList(list);
        collection.setIterator(it);

        return collection;
    }

    private FastIterator() {}

    private static class Holder {
        public DummyCollection<?> collection;
        public Iterator<?> it;
    }

    private static class DummyCollection<T> implements Iterable {
        private Iterator<?> it;

        @Override
        public java.util.Iterator<T> iterator() {
            return (java.util.Iterator<T>) it;
        }

        public void setIterator(Iterator<?> it) {
            this.it = it;
        }
    }

    private static class Iterator<T> implements java.util.Iterator<T> {
        private ArrayList<T> list;
        private int size;
        private int i;

        @Override
        public boolean hasNext() {
            return i < size;
        }

        @Override
        public T next() {
            return list.get(i++);
        }

        @Override
        public void remove() {

        }

        public void setList(ArrayList<T> list) {
            this.list = list;
            size = list.size();
            i = 0;
        }

        private Iterator() {}
    }
}

- alexanderblom

---

嗯，如果我理解正确的话，黑客迭代器比在for循环中需要额外一行代码来获取值更好？... - Ivo Wetzel

明白了。我想我应该咬紧牙关放弃for循环？ :( - alexanderblom

我使用了“扩展ArrayList，返回仅分配一次的迭代器”版本。需要注意的一件事（对于您提到的所有迭代样式）是嵌套迭代。在我的版本中，我添加了一个显式的“释放”方法，并可以检查迭代器是否已经在使用中...以此方式捕获了一个严重的错误。另一个注意点：Iterator.remove抛出UnsupportedOperationException是合法的。 - Darrell

这实际上会影响性能吗，还是你只是因为一个你认为没有分配任何内存的程序最终却做了而感到烦恼？ - DJClayworth

垃圾回收器每 30 秒运行一次，暂停游戏约 100 毫秒，导致明显的卡顿。 - alexanderblom

Answer 1

在 Android 游戏开发中，不应使用 for each。我认为这个 官方视频 也讲到了这一点。

- mibollma

---

我决定将所有的循环都转换成普通的for循环。KISS。 - alexanderblom

Answer 2

最好的方法可能是使用装饰器设计模式。创建一个类，在构造函数中接收一个集合，并通过调用包装类并重用返回的迭代器来实现Iterable接口。

- Pace

---

我相信这个建议的核心是也要有一个reset()方法，它可以将迭代器返回到开头。 - Dilum Ranatunga

Answer 3

避免分配迭代器的另外两种方法。第一种是使用回调机制：

public interface Handler<T> {
  void handle(T element);
}

public interface Handleable<T> {
  void handleAll(Handler<T> handler);
}

public class HandleableList<T> extends ArrayList<T> implements Handleable<T> {
  public void handleAll(Handler<T> handler) {
    for (int i = 0; i < size(); ++i) {
      handler.handle(get(i));
    }
  }
}

这种方法仍然需要一个Handler实例来接收回调，但是当您尝试访问多个列表的元素时，这绝对可以减少分配。

第二种方法是使用游标惯用语：

public interface Cursor<T> {
  void reset();
  boolean next();
  T current();
}

public class CursoredList<T> extends ArrayList<T> implements Cursor<T> {
  private int _index = -1;

  public void reset() {
    _index = -1;
  }

  public boolean next() {
    return ++_index >= size();
  }

  public T current() {
    return get(_index);
  }
}

当然，这与在ArrayList的子类型上实现Iterable和Iterator相同，但这清楚地将游标位置显示为集合本身的状态。

- Dilum Ranatunga