ArrayDeque instead of LinkedList for buffers

Description

`LinkedList` is used as the underlying data-structure for all core.async buffers. However, looking closer reveals that what is really needed is a `Deque` (for its .addFirst/.removeLast methods). So naturally then it begs the question - why not `ArrayDeque` ? It should offer superior insertion/removal/traversing performance, and in the context of core.async it will never be resized (if initialised with `n`). Providing a trivial patch which doesn't break anything (i.e. tests pass).

Environment

None

Activity

Show:
Dimitrios Jim Piliouras
September 11, 2020, 10:33 PM

I 'm not sure if this helps at all, but linking my buffers implementation here for future reference:

It contains two sets of three buffers (the Deque-backed ones shown in the patch and ConcurrentLinkedDeque-backed ones). The dropping/sliding buffers also (optionally) support reacting-fns for the items dropped/slided, which is useful, especially for non thread-safe buffers.

Dimitrios Jim Piliouras
September 11, 2020, 6:59 PM

I also forgot to mention that switching to ArrayDeque changes the memory allocation profile for creating channels. With a LinkedList nodes are created as needed, whereas with an ArrayDeque the whole array is best to be allocated upfront (so it never has to be resized). However, I would argue that the latter is more appropriate for a data-structure acting as a buffer.

Dimitrios Jim Piliouras
September 10, 2020, 11:13 PM

I forgot to mention that I have already signed the contributor’s agreement.

Your pinned fields
Click on the next to a field label to start pinning.

Assignee

Unassigned

Reporter

Dimitrios Jim Piliouras

Patch

Code