Performance of ArrayRetainableByteBufferPool.acquire() can degenerate pathologically as the buckets grow in size

[lorban]

Jetty version(s)
12

Description
Since ArrayRetainableByteBufferPool.acquire() is backed by ConcurrentPool.acquire(), each execution requires iterating over a number of entries proportional to the usage level of the bucket, i.e.: a bucket that is 90% used requires iterating over 90% of the entries on average.

When the number of buffers in a single bucket is quite small (in the 100s), those iterations are so cheap they have a negligible cost as the array is small enough to fit into the CPU cache. But when that number of buffers reaches the 10s of thousands, these iterations become a pathological bottleneck.

[lorban]

This was found in MultiPartServletTest.testLargePart() when the default buffer pool is used as this test needs 262144 buffers (2GB split in 8KB) to complete.

With the ArrayRetainableByteBufferPool.acquire() implementation being:

1. ConcurrentPool.acquire()
2. if null, reserve and allocate

this means it would require 262144! (yes; factorial of 262144, which approaches infinity) compareAndSet calls for the test to eventually finish.

@lachlan-roberts could you please add a TODO referring to this issue to your test that uses a non-pooling pool as a workaround?

[lorban]

The root of this issue seems to be that the algorithm backing ConcurrentPool does not scale well to large sizes.

There are two major users of the ConcurrentPool:

1. connection pooling
   This seems to be less of a problem for this use-case as a connection pool sized at 1000 entries is quite substantial and very uncommon, and acquiring from it may not happen millions of times per second while it mostly contains busy connections sounds like a very niche use-case.
   It is nevertheless a possibility, even if a remote one.

2. buffer pooling
   Having 10's of thousands of buffers of a specific size (especially the small ones < 16KB) doesn't sound unrealistic nor very uncommon so solving this issue seems more pressing.
   Since ConcurrentPool is fully abstracted by ArrayRetainableByteBuffer we could add some mitigation strategies to handle this problem, like for instance:

   • hard capping the # of buffer per bucket to a few hundreds
   • adding another oeju.Pool with a different algorithm that scales well with large bucket sizes (e.g.: the previous queue-based pool algorithm would) and making ArrayRetainableByteBuffer to choose between the two based on a heuristic

Maybe we also should expose a constant like ConcurrentPool.MAX_REASONABLE_SIZE set to a few 100s and warn when a concurrent pool is instantiated with a size over that constant?

[lorban]

@gregw @sbordet

[sbordet]

Re-instating a Pool implementation based on a queue seems the best solution.

It would have the con that it will be either based on ConcurrentLinkedDeque (and hence a linked-list data structure, not particularly memory friendly), or on a locked queue (and it will be contended).

Another idea could be to see if using a bitmap would help, see class java.util.BitSet.
With simple binary operations (that typically are mapped to single CPU operations) would be possible to find the first idle entry in the list.
For example, let 1 be non-idle and 0 be idle, if the bitmap is 11111110000 would be possible to find quickly that the first 0 is at index 7 (from left).

[gregw]

There are 2 reasons for using a Pool:

1. to put a limit on the total number of resources that can be allocated
2. to avoid stressing the GC algorithm by frequently allocating/releasing objects that can easily be reused.

So for ByteBuffers we don't really want 1. because we don't want to block any allocation in any part of the code. Instead we police maximum memory commitment by other limits (on numbers/sizes).
Thus we are really only interested in 2., so if we start finding ourselves implementing algorithms with similar problems as GC (finding holes in large memory areas), then we should probably not bother and just delegate to the smart folks who write GCs

Let's setup a meeting to discuss the options.

[gregw]

Currently the algorithm in ArrayByteBufferPool (aka ArrayRetainableByteBufferPool is:

• if no Bucket for the size/type
  • return newly allocated buffer
• if we can acquire an entry from the bucket
  • return it's buffer
• if we can reserve an new entry from the bucket
  • return newly enabled entry with a newly allocated buffer and releaser
• return newly allocated buffer

I think there is scope to add in a queue as a "second level cache":

• if no Bucket for the size/type
  • return newly allocated buffer
• if we can acquire an entry from the bucket
  • return it's buffer
• if we can reserve an new entry from the bucket
  • return newly enabled entry with a newly allocated buffer and releaser
• if we can pop a buffer from the secondary queue (held by the bucket)
  • return it
• return newly allocated buffer

Using buffers from a queue not only saves on the allocation of the ByteBuffer, but also on the allocation of the retainable wrapper, potentially costing the allocation of the queue structure.

So we would configure this pool with:

• a maximum bucket pool size (possibly 0), which must be small enough to be efficient
• a maximum bucket queue size (possible 0 or infinite), to control how many buffers are in the secondary "cache"

[gregw]

See #9319 for a queued 2nd layer "cache" on the pool.

[gregw]

See also #9320 that is a Pool.Wrapper that can apply a queue over any other pool. I like this better, but it might not be as fast as #9319, but it is more general.

After chatting with Simone, I think the key thing to do now is to remove the bucket size from the ByteBufferPool constructor (or at least deprecate that constructor) and work out the pool size vs queue size heuristically.

[lorban]

I like #9320 better but we should probably benchmark the differences with #9319, possibly both with a micro-benchmark as well as a macro one (our perf test?) as the introduction of ArrayRetainableByteBuffer in 10.0.x was motivated because it brought a noticeable perf boost over the previous queue-based pool and we don't want to go back to the previous level of perf.

I agree that bucket size should be an internal-only concern that we should figure out with a heuristic.

It looks like such change to ArrayRetainableByteBuffer would slightly move it from the land of buffer pools to the land of memory allocators.

[gregw]

@lorban please take over those branches for further work on this.