Hi, yes, this is the right place to discuss Sequenced Collections. I'm glad you find
it promising.
Note that Sequenced Collections actually has very little implementation in it, aside
from various reversed views of things. The actual data is still stored in existing
concrete collections such as ArrayList, ArrayDeque, LinkedHashMap, and TreeMap.
I think Sequenced Collections has the right set of abstractions in it as it stands,
and I don't want to expand its scope by talking about additional concepts like size
limits or eviction policy.
However, those things are quite reasonable to discuss independently of the current
Sequenced Collections proposal. Having a maximum size on a collection seems
independent of sequencing. An eviction policy *might* be based on the sequence, but
it might not; consider the various eviction policies available for a cache library
such as Caffeine [1].
[1] https://github.com/ben-manes/caffeine/wiki
However, I'm somewhat skeptical of trying to build things like eviction policies
directly into collections. It's tempting to add a simple thing like a size and just
throw away things in some well-defined order whenever the size is exceeded. The
problem is that if this policy doesn't do *exactly* what you want to do, then you're
out of luck.
The current (pre Sequenced Collections) LinkedHashMap is a good example of this.
It's suitable for a least-recently-inserted expiration policy; there's a method
removeEldestEntry() that programs can use to implement a simple policy, size-based
or otherwise. (Unfortunately they have to subclass-and-override, but whatever.) The
problem is that it allows removal of only one element -- the eldest (first) element.
If you want to change the policy of insertion order of an LHM, you have only one
alternative: access order. Enabling this has some weird side effects though. For
example, get() now rearranges the order of entries in the map, and is thus a
structural modification -- which means that it spoils any iterators over the map's
views.
These are both fairly common cases, which is probably why they were added. But
they're not very flexible, and if you want to do something slightly different,
you're on your own -- and it's pretty hard to implement your own policy, because LHM
lacks a bunch of essential operations.
Where the Sequenced Collections proposal helps is that instead of adding more
policies, it adds the missing primitive operations. You can add/get/remove at either
end, and you can reposition mappings to either end. If you have some different
recent-usage policy or some unusual cache eviction policy that I've never heard of,
you can use the primitives to implement it yourself. That's much better than trying
to bake a few more specific cases into LinkedHashMap or other collections.
Is there a discussion about making the SynchronizedCollection family of classes public?
No. Synchronizing on every collection operation is the wrong level of abstraction.
Typical collection usage involves too much external iteration and too much
check-then-act logic. Callers would have to wrap those in synchronized blocks, and
in general they don't know when that's necessary. Certain transaction-style
operations (like Map::computeIfAbsent) can be made to work, but those are all pretty
low level.
s'marks
On 9/21/22 9:32 AM, Ernie Rael wrote:
> I don't see why you think a general collection...
I thought the Subject would be sufficient to indicate that I was not talking about
collections in general. I should have been more precise with my words; guess I was
just excited by a bi-directional ordered set.
The MRU _example_ is useful; the current collections handle it poorly and Sequenced
Collections is ideal. Caches with an eviction policy are common; I suspect caches
will be a common use for SequencedSet family. Note there are fixed sized Collections
and SequencedCollection borrows heavily from that family. Perhaps this issue should
be considered in the context of adding an **Eviction Policy** to appropriate
collections.
MRU is a Collection; for example, I pass an MRU to a persistence mechanism that
takes a collection. Saying "all methods offered by `Collection` should [not] even be
part of an `MRU` interface" is innacurate, especially when considered in the context
of a SequencedCollection.
-ernie
PS - Loosely related is extending a Collection and providing a synchronized version.
Is there a discussion about making the SynchronizedCollection family of classes public?
On 9/21/22 4:22 AM, John Hendrikx wrote:
I don't see why you think a general collection, that is in 99.9% of the cases not
used to implement an MRU, should burden every call to #add with a check to see if
it isn't exceeding its maximum size or to see if a maximum size has been set.
This is much better done by composition, as I don't think all methods offered by
`Collection` should even be part of an `MRU` interface.
--John
On 20/09/2022 21:08, Ernie Rael wrote:
(There may be a better place to send this, let me know where)
Suggesting an option to limit the size of the collection, e.g "setMaxSize(int)",
default of zero means no limit.
I put together "interface MRU<E> extends Collection<E>" some months ago, it has
two implementations based on LinkedList and LinkedHashSet. The code can be seen
at
https://sourceforge.net/p/jvi/raelity-lib/ci/default/tree/lib/src/main/java/com/raelity/lib/
A SequencedCollection, as outlined in the JEP draft 2020/09/01, would be almost
perfect to implement MRU; I've run into most of the problems/issues discussed in
the JEP draft.
The MRU is a cache, as I use it; it typically has a max size for the collection.
Handling this natively in the collection would be ideal; if an add operation
would overflow, remove the item at the other end. Note that addAll() is used when
initializing from backing store.
FYI, I use a "Supplier<Integer>" to the constructor to provide maxSize, but a
property makes much more sense. I'll make that change in MRU for sanity, and get
rid of the trim() method. setMaxSize can do the trim.
-ernie
