Use Standard Iterator for TurboFilterList

[belugabehr]

logback/logback-classic/src/main/java/ch/qos/logback/classic/spi/TurboFilterList.java

Lines 55 to 64 in 04a7ba5

	Object[] tfa = toArray();
	final int len = tfa.length;
	for (int i = 0; i < len; i++) {
	// for (TurboFilter tf : this) {
	final TurboFilter tf = (TurboFilter) tfa[i];
	final FilterReply r = tf.decide(marker, logger, level, format, params, t);
	if (r == FilterReply.DENY || r == FilterReply.ACCEPT) {
	return r;
	}
	}

At one point (more than 17 years ago!) this used to use the iterator, the current implementation looks suspect in the current world of more advanced JDK JIT. Can you clean this up? If there are larger lists, this also adds additional overheard to the heap as it makes a copy of the array (v.s. one new Iterator that may be optimized away anyway).

I put together a simple JMH benchmark for the two approaches and got the following results:

Benchmark                                    (listSize)  Mode  Cnt   Score   Error  Units
CopyOnWriteIterationBenchmark.usingIterator           5  avgt    9   2.823 ± 0.129  ns/op
CopyOnWriteIterationBenchmark.usingIterator          10  avgt    9   4.390 ± 0.121  ns/op
CopyOnWriteIterationBenchmark.usingIterator          50  avgt    9  15.658 ± 0.749  ns/op
CopyOnWriteIterationBenchmark.usingIterator         100  avgt    9  31.177 ± 0.967  ns/op
CopyOnWriteIterationBenchmark.usingToArray            5  avgt    9   4.278 ± 0.071  ns/op
CopyOnWriteIterationBenchmark.usingToArray           10  avgt    9   5.203 ± 0.312  ns/op
CopyOnWriteIterationBenchmark.usingToArray           50  avgt    9  16.350 ± 0.536  ns/op
CopyOnWriteIterationBenchmark.usingToArray          100  avgt    9  32.647 ± 1.565  ns/op

The listSize is the number of elements in the list.

Note

When I restrict the memory to 128MB, the "usingToArray" test fails with OutOfMemory, thus confirming that the JDK can in-line the iterator and not actually created one on the heap.

# JMH version: 1.37
# VM version: JDK 17.0.16, OpenJDK 64-Bit Server VM, 17.0.16+8-Ubuntu-0ubuntu124.04.1
# VM invoker: /usr/lib/jvm/java-17-openjdk-amd64/bin/java
# VM options: -Xms128M -Xmx128M -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC

[ceki]

@belugabehr I am rather surprised by these results. Can you post the JMH code please?

[belugabehr]

Gladly! Pretty trivial!

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 3, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 3, time = 1, timeUnit = TimeUnit.SECONDS)
//@Fork(value = 3, jvmArgs = {"-Xms128M", "-Xmx128M", "-XX:+UnlockExperimentalVMOptions", "-XX:+UseEpsilonGC"})
@Fork(value = 3)
@State(Scope.Thread)
public class CopyOnWriteIterationBenchmark {

    @Param({"5", "10", "50", "100"})
    private int listSize;

    private CopyOnWriteArrayList<String> list;
    private int randomMultiplier;

    @Setup
    public void setup() {
        list = new CopyOnWriteArrayList<>();
        for (int i = 0; i < listSize; i++) {
            list.add("Element_" + i);
        }
        randomMultiplier = new Random(42).nextInt(1000) + 1;
    }

    @Benchmark
    public int usingToArray() {
        Object[] array = list.toArray();
        final int len = array.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += i * randomMultiplier;
        }
        return sum;
    }

    @Benchmark
    public int usingIterator() {
        int sum = 0;
        int i = 0;
        for (String element : list) {
            sum += i * randomMultiplier;
            i++;
        }
        return sum;
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(CopyOnWriteIterationBenchmark.class.getSimpleName())
                .build();

        new Runner(opt).run();
    }
}

[belugabehr]

And candidly, I was surprised to see this toArray() code since using a CopyOnWriteArrayList is supposed to negate the need to do that. The iterator will see a 'snapshot' of the backing array without having to copy it. so I have to assume it was a performance choice re: iterators.

[ceki]

@belugabehr Thank you for the update. The toArray() call now appears quite suboptimal. It should be getArray(). With that change the performance of the existing array loop code should be a little better than with the iterator. I'll test this claim and report back.

Update: CopyOnWriteArrayList.getArray() method is package private.

[ceki]

I don’t recall the exact reasoning for choosing toArray() over an iterator, but it was likely because cloning an array was considered faster than instantiating a COWIterator at the time.

That said, for the most common cases—zero or one TurboFilter in the list—the current implementation still performs quite well.

[belugabehr]

but it was likely because cloning an array was considered faster than instantiating a COWIterator at the time.

That is my suspicion as well, but I'm not so sure it's the case still today. And also, using a iterator, even if it is allocated on heap (which my testing implies does not happen) is still a fixed cost instead of copying an unbounded array.

To your point, the 0/1 optimization is nice, but it is not my use case. This little bit of code caught my eye because it was coming up from some internal performance testing. It was not a critical issue, but just something that caught my eye.

Thanks!

[belugabehr]

Just realized this is a dup of #944