Re: RFR: JDK-8323760 putIfAbsent documentation conflicts with itself [v3]

[John Hendrikx]

> Update the documentation for `@return` tag of `putIfAbsent` to match the main 
> description. `putIfAbsent` uses the same wording as `put` for its `@return` 
> tag, but that is incorrect.  `putIfAbsent` never returns the **previous** 
> value, as the whole point of the method is not the replace the value if it 
> was present.  As such, if it returns a value, it is the **current** value, 
> and in all other cases it will return `null`.

John Hendrikx has updated the pull request incrementally with one additional 
commit since the last revision:

  Use new suggestion and remove original clarification

-

Changes:
  - all: https://git.openjdk.org/jdk/pull/17438/files
  - new: https://git.openjdk.org/jdk/pull/17438/files/3621be54..8c91f058

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=17438&range=02
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=17438&range=01-02

  Stats: 5 lines in 1 file changed: 0 ins; 3 del; 2 mod
  Patch: https://git.openjdk.org/jdk/pull/17438.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/17438/head:pull/17438

PR: https://git.openjdk.org/jdk/pull/17438

Re: RFR: JDK-8323760 putIfAbsent documentation conflicts with itself [v2]

[John Hendrikx]

On Tue, 13 Feb 2024 17:11:05 GMT, John Hendrikx  wrote:

>> Update the documentation for `@return` tag of `putIfAbsent` to match the 
>> main description. `putIfAbsent` uses the same wording as `put` for its 
>> `@return` tag, but that is incorrect.  `putIfAbsent` never returns the 
>> **previous** value, as the whole point of the method is not the replace the 
>> value if it was present.  As such, if it returns a value, it is the 
>> **current** value, and in all other cases it will return `null`.
>
> John Hendrikx has updated the pull request incrementally with four additional 
> commits since the last revision:
> 
>  - Add code block around argument
>  - Reword
>  - Reword to use put's previous value wording
>  - Reword more clearly

CSR is available now.

-

PR Comment: https://git.openjdk.org/jdk/pull/17438#issuecomment-1943040199

Re: RFR: JDK-8323760 putIfAbsent documentation conflicts with itself [v2]

[John Hendrikx]

On Tue, 16 Jan 2024 13:27:31 GMT, Chen Liang  wrote:

>> Yeah, I wasn't sure about that, I can make it more specific, I used 
>> `considered` here because both unmapped keys and keys mapped to `null` are 
>> considered to be absent.
>
> I think `absent or {@code null}` is no less concise yet it is way more 
> accurate than `considered absent`. So something like `@return {@code null} if 
> the mapping for the specified key is absent or has a {@code null} value`?

I used your wording @liach but changed the sentence to past tense.

-

PR Review Comment: https://git.openjdk.org/jdk/pull/17438#discussion_r1488255726

Re: RFR: JDK-8323760 putIfAbsent documentation conflicts with itself [v2]

[John Hendrikx]

> Update the documentation for `@return` tag of `putIfAbsent` to match the main 
> description. `putIfAbsent` uses the same wording as `put` for its `@return` 
> tag, but that is incorrect.  `putIfAbsent` never returns the **previous** 
> value, as the whole point of the method is not the replace the value if it 
> was present.  As such, if it returns a value, it is the **current** value, 
> and in all other cases it will return `null`.

John Hendrikx has updated the pull request incrementally with four additional 
commits since the last revision:

 - Add code block around argument
 - Reword
 - Reword to use put's previous value wording
 - Reword more clearly

-

Changes:
  - all: https://git.openjdk.org/jdk/pull/17438/files
  - new: https://git.openjdk.org/jdk/pull/17438/files/81276376..3621be54

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=17438&range=01
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=17438&range=00-01

  Stats: 5 lines in 1 file changed: 1 ins; 0 del; 4 mod
  Patch: https://git.openjdk.org/jdk/pull/17438.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/17438/head:pull/17438

PR: https://git.openjdk.org/jdk/pull/17438

Re: RFR: JDK-8323760 putIfAbsent documentation conflicts with itself

[John Hendrikx]

On Tue, 16 Jan 2024 10:41:04 GMT, Pavel Rappo  wrote:

>> Update the documentation for `@return` tag of `putIfAbsent` to match the 
>> main description. `putIfAbsent` uses the same wording as `put` for its 
>> `@return` tag, but that is incorrect.  `putIfAbsent` never returns the 
>> **previous** value, as the whole point of the method is not the replace the 
>> value if it was present.  As such, if it returns a value, it is the 
>> **current** value, and in all other cases it will return `null`.
>
> src/java.base/share/classes/java/util/Map.java line 820:
> 
>> 818:  * @param key key with which the specified value is to be associated
>> 819:  * @param value value to be associated with the specified key
>> 820:  * @return {@code null} if the specified key was considered absent, 
>> else returns
> 
> "Considered" feels out of place. No other method in Map uses it. Try to 
> rephrase that sentence or, if it helps, the complete `@return` tag. 
> (@stuart-marks might have more substantial feedback.)

Yeah, I wasn't sure about that, I can make it more specific, I used 
`considered` here because both unmapped and key maps to `null` is considered to 
be absent.

-

PR Review Comment: https://git.openjdk.org/jdk/pull/17438#discussion_r1453271276

RFR: JDK-8323760 putIfAbsent documentation conflicts with itself

[John Hendrikx]

Update the documentation for `@return` tag of `putIfAbsent` to match the main 
description. `putIfAbsent` uses the same wording as `put` for its `@return` 
tag, but that is incorrect.  `putIfAbsent` never returns the **previous** 
value, as the whole point of the method is not the replace the value if it was 
present.  As such, if it returns a value, it is the **current** value, and in 
all other cases it will return `null`.

-

Commit messages:
 - Improve putIfAbsent documentation

Changes: https://git.openjdk.org/jdk/pull/17438/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=17438&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8323760
  Stats: 4 lines in 1 file changed: 0 ins; 1 del; 3 mod
  Patch: https://git.openjdk.org/jdk/pull/17438.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/17438/head:pull/17438

PR: https://git.openjdk.org/jdk/pull/17438

Re: RFR: 8310929: Optimization for Integer.toString [v13]

[John Hendrikx]

On Tue, 18 Jul 2023 01:49:17 GMT, 温绍锦  wrote:

>> Optimization for:
>> Integer.toString
>> Long.toString
>> StringBuilder#append(int)
>> 
>> # Benchmark Result
>> 
>> 
>> sh make/devkit/createJMHBundle.sh
>> bash configure --with-jmh=build/jmh/jars
>> make test TEST="micro:java.lang.Integers.toString*" 
>> make test TEST="micro:java.lang.Longs.toString*" 
>> make test TEST="micro:java.lang.StringBuilders.toStringCharWithInt8"
>> 
>> 
>> ## 1. 
>> [aliyun_ecs_c8i.xlarge](https://help.aliyun.com/document_detail/25378.html#c8i)
>> * cpu : intel xeon sapphire rapids (x64)
>> 
>> ``` diff
>> -Benchmark   (size)  Mode  Cnt  Score   Error  Units (baseline)
>> -Integers.toStringBig   500  avgt   15  6.825 ± 0.023  us/op
>> -Integers.toStringSmall 500  avgt   15  4.823 ± 0.023  us/op
>> -Integers.toStringTiny  500  avgt   15  3.878 ± 0.101  us/op
>> 
>> +Benchmark   (size)  Mode  Cnt  Score   Error  Units (PR Update 
>> 04 f4aa1989)
>> +Integers.toStringBig   500  avgt   15  6.002 ± 0.054  us/op (+13.71%)
>> +Integers.toStringSmall 500  avgt   15  4.025 ± 0.020  us/op (+19.82%)
>> +Integers.toStringTiny  500  avgt   15  3.874 ± 0.067  us/op (+0.10%)
>> 
>> -Benchmark(size)  Mode  Cnt  Score   Error  Units (baseline)
>> -Longs.toStringBig   500  avgt   15  9.224 ± 0.021  us/op
>> -Longs.toStringSmall 500  avgt   15  4.621 ± 0.087  us/op
>> 
>> +Benchmark(size)  Mode  Cnt  Score   Error  Units (PR Update 04 
>> f4aa1989)
>> +Longs.toStringBig   500  avgt   15  7.483 ± 0.018  us/op (+23.26%)
>> +Longs.toStringSmall 500  avgt   15  4.020 ± 0.016  us/op (+14.95%)
>> 
>> -Benchmark   Mode  Cnt ScoreError  Units 
>> (baseline)
>> -StringBuilders.toStringCharWithInt8 avgt   1589.327 ±  0.733  ns/op
>> 
>> +BenchmarkMode  Cnt   Score   Error  Units (PR 
>> Update 04 f4aa1989)
>> +StringBuilders.toStringCharWithInt8  avgt   15  36.639 ± 0.422  ns/op 
>> (+143.80%)
>> 
>> 
>> 
>> ## 2. 
>> [aliyun_ecs_c8a.xlarge](https://help.aliyun.com/document_detail/25378.html#c8a)
>> * cpu : amd epc genoa (x64)
>> 
>> ``` diff
>> -Benchmark   (size)  Mode  Cnt  Score   Error  Units (baseline)
>> -Integers.toStringBig   500  avgt   15  6.753 ± 0.007  us/op
>> -Integers.toStringSmall 500  avgt   15  4.470 ± 0.005  us/op
>> -Integers.toStringTiny  500  avgt   15  2.764 ± 0.020  us/op
>> 
>> +Benchmark   (size)  Mode  Cnt  Score   Error  Units (PR Update 
>> 04 f4aa1989)
>> +Integers.toStringBig   500  avgt   15  5.036 ± 0.005  us/op (+...
>
> 温绍锦 has updated the pull request incrementally with one additional commit 
> since the last revision:
> 
>   assert bounds check

I'm wondering if a micro benchmark like this is very realistic.  They may score 
positive as eventually these helper tables are in the inner most cache level, 
but it may be a net negative for larger functions that only do integer 
conversion occasionally, and almost always have a cache miss when doing a 
conversion.  The tables may also be displacing other more useful cache lines.

In my opinion, cache is a limited resource, and having a low level function use 
a big chunk of it may be optimal for a micro benchmark, but seems unlikely to 
be optimal overall.  If you are only doing mass string to integer conversion, 
I'm sure it will do better.  If you are writing out JSON that sometimes 
contains integers, the integer conversions may now sometimes have cache misses 
(in which case a non-cached based conversion would perform better), or the 
conversion is displacing other more useful cache lines.

-

PR Comment: https://git.openjdk.org/jdk/pull/14699#issuecomment-1701138931

Re: Enrich the Lock interface

[John Hendrikx]

I couldn't find a discussion on openjdk, but for those interested (and 
to save others some searching) there is a JBS ticket:


https://bugs.openjdk.org/browse/JDK-8025597

--John

On 21/08/2023 14:37, Pavel Rappo wrote:

This is suggested every once in a while. I appreciate that openjdk mailing 
lists are not easily searchable, but with a bit of skill, you could find a few 
previous discussions on the topic.

This has also been discussed on concurrency-interest (at cs.oswego.edu 
), a dedicated mailing list for concurrency in Java. 
Sadly, that list has been defunct for quite some time now.

-Pavel


On 21 Aug 2023, at 13:18, Albert Attard  wrote:

Hello.

I hope all is well.

Do you believe it is a bad idea to enrich the Lock interface with a set of 
default methods that safely release the lock once ready?

Consider the following (dangerous) example.

final Lock lock = new ReentrantLock ();
lock.lock();
/* Code that may throw an exception */
lock.unlock();

This example will never release the lock if an exception is thrown, as the 
programmer didn’t wrap this up in a try/finally.

Adding a default method within the Lock interface, called withLock(Runnable) 
for example or any better name, would streamline this, as shown next.

default void withLock(final Runnable runnable) {
 requireNonNull(runnable, "Cannot run a null");
 lock();
 try {
 runnable.run();
 } finally {
 unlock();
 }
}

The caller can now simply change the above example into the following, without 
having to worry about this.

final Lock lock = new ReentrantLock ();
lock.withLock(() -> {
   /* Code that may throw an exception */
});

We can have more variants of these default methods, as shown next.

default  T getWithLock(final Supplier supplier) {
 requireNonNull(supplier, "The supplier cannot be null");
 lock();
 try {
 return supplier.get();
 } finally {
 unlock();
 }
}

Any thoughts?

With kind regards,
Albert Attard

Re: Questions about using `assert` in Java

[John Hendrikx]

On 17/07/2023 11:08, Alan Bateman wrote:

On 15/07/2023 17:53, Daohan Qu wrote:

:

Although the |assert|​ keyword has been around for a long time and
is handy for invariant checks, it does not seem to be widely used.
For example, in the famous |j.u.c|​ packages, nearly all |assert|​
statements are commented out [1].

My questions are, should |assert|​ be heavily used in Java programs,
especially in production code? And should we enable them in the
production code?

Asserts are very useful during development or when testing, e.g. the 
JDK tests run with -esa and can periodically help catch issues when 
testing a change.


You will find places in the JDK code, esp. in performance critical 
code, where assertions are commented out. The reason is that asserts, 
even if disabled, increase the method size and can impact inlining by 
the compiler at run-time.  So while useful when debugging some issue 
in such code, they are commended out to avoid increasing the method size.


I believe this can be partially alleviated by extracting the asserts to 
a method (partially as the call also increases method size).  The 
optimizer seems to be smart enough to not call the method if it does 
nothing (when ea is disabled).


--John

Re: RFR: 8287834: Add SymbolLookup::or method [v3]

[John Hendrikx]

On Tue, 16 May 2023 22:36:51 GMT, Maurizio Cimadamore  
wrote:

>> This patch adds a simpler method for composing symbol lookups. It is common 
>> for clients to chain multiple symbol lookups together, e.g. to find a symbol 
>> in multiple libraries.
>> 
>> A new instance method, namely `SymbolLookup::or` is added, which first 
>> searches a symbol in the first lookup, and, if that fails, proceeds to 
>> search the symbol in the provided lookup.
>> 
>> We have considered alternatives to express this, such as a static factory 
>> `SymbolLookup::ofComposite` but settled on this because of the similarity 
>> with `Optional::or`.
>
> Maurizio Cimadamore has updated the pull request incrementally with one 
> additional commit since the last revision:
> 
>   Tweak javadoc

Isn't it already possible to easily create a composed `SymbolLookup`?

 SymbolLookup lookUp = name -> library1.find(name)
  .or(() -> library2.find(name))
  .or(() -> loader.find(name));

The proposed method may be a bit nicer, but it is sort of duplicating what 
`Optional::or` was intended for.

-

PR Comment: https://git.openjdk.org/jdk/pull/13954#issuecomment-1550560151

Re: a plea for blocking peek

[John Hendrikx]

Hi,

I think it would help if you describe your problem a bit more directly.  
Currently there is a lot of mention of difficulty levels, usual 
approaches and "winning", which really doesn't help to ascertain what 
you are trying to achieve. For a good re-evaluation of your request, you 
are going to need to show some (pseudo) code so people can see if this 
indeed is a good use case, or that there is an elegant alternative solution.


It's really hard to glean from your post what you are trying to do.  It 
seems like you have a queue and a map.  Items you get from the queue 
need to be verified against the map.  The lock seems to protect the map 
structure against concurrent modification, and for some reason getting 
the lock after `take` isn't good enough.


--John

On 01/05/2023 19:12, mark.yagnatin...@barclays.com wrote:


I’m not sure if this I’m breaking etiquette for this list but I’m 
going to risk resending my first message because it got zero replies.  
If it was simply too long, please let me know and I’ll attempt a 
shorter version.


Here’s like to original:

https://mail.openjdk.org/pipermail/core-libs-dev/2023-April/104931.html

*From:* Yagnatinsky, Mark : Markets Pre Trade
*Sent:* Thursday, April 27, 2023 12:28 PM
*To:* core-libs-dev@openjdk.org
*Subject:* RE: blocking peek for blocking queues

Someone said this is the right list for this, so forwarding from 
jdk-dev with a small tweak


I’d like to make a case for adding a blocking variant of peek() to 
BlockingQueue.


This has apparently been suggested before:

https://bugs.openjdk.org/browse/JDK-6653412

At the time, the verdict was that the proposed use case for a blocking 
peek was not very compelling, but “If a compelling use case is 
available,we may reconsider and reopen this RFE”


For one thing, that use case was inherently racy, and ideally the 
standard library should not be encouraging races.


And for another thing, this was before the invention of default 
methods, so a new interface would be needed.


I’d like to present what might be a more sympathetic use case, where a 
blocking peek actually makes it easier to avoid races.


(This is not hypothetical; I’ve spent all day trying to cope with the 
lack of a blocking peek.  I think I succeeded, but it was tough.)


Let’s start at the beginning.  The game known as “multithreaded 
programming” can be played on 3 difficulty levels: easy, medium, and hard.


Easy mode is when the JDK happens to have a high-level tool (e.g., a 
Collection or an Executor or something) such as DelayQueue that does 
exactly what you want.


Sadly, the JDK is finite, and even Maven Central is finite, so this 
not guaranteed to happen, though it’s nice when it does.


At the other extreme is hard mode, when every nanosecond counts and 
you must resort to the sorts of mental gymnastics that were involved 
when String.hashCode was re-worked to avoid re-computing hash codes 
equal to zero.


This email is about the medium difficulty level.  In this mode, you 
must glue together two or three collections to get what you want.


To be concrete, suppose we want to glue a map together with a blocking 
queue, since that’s a simplified version of what I was doing.  (In 
particular I was using a DelayQueue and a HashMap.)


Since we’re not playing on hard mode, we’re going to allow ourselves 
to guard the entire data structure by one giant lock whenever it seems 
convenient, without worrying about performance.


In fact, let’s give a name to this lock. Since I’m not feeling very 
creative right now, let’s call it LOCK.  Similarly, let’s call our 
compound data structure STRUCT.


My usual heuristic to “win” (that is, to make sure my code is correct, 
or at least non-racy) on medium difficulty goes something like this.


First, figure out whether there is any way for STRUCT to be “invalid”.

For instance, maybe “it’s valid if and only if every entry in the 
queue has a corresponding entry in the map”.


One could then write a brief comment in the code explaining what 
“valid” means, or perhaps even write an “isValid()” method for testing 
purposes.


Once we’ve decided what it means for STRUCT to be “valid” (aka, 
non-corrupt), we can try to maintain the following invariant:


EITHER some thread holds the LOCK, and no other thread is using STRUCT 
right now,


OR ELSE the LOCK  is not held by any thread, and thus STRUCT is 
currently in a valid state.


Sometimes the invariant above is a bit too strong, and it’s convenient 
to weaken it slightly.  So we can instead consider the following rule:


RULE: we must never mutate STRUCT unless we hold the LOCK.

If we uphold the invariant, then we must be following the rule, but 
not vice versa.


(The rule doesn’t forbid queries without the lock; it only forbids 
writes.)


Finally, we come to the point.  The lack of a blocking peek in 
BlockingQueue has forced me to break the above “weakened” rule.


I had to invent a new much weaker rule, something like “please 
care

Re: Testing no memory leak occurs via references

[John Hendrikx]

On 08/03/2023 10:36, David Holmes wrote:

On 7/03/2023 8:16 pm, Kim Barrett wrote:
On Mar 6, 2023, at 10:11 AM, Aleksei Ivanov 
 wrote:


On 06/03/2023 13:51, Albert Yang wrote:
Upon a cursory inspection of ForceGC.java, it seems that the 
fundamental logic involves waiting for a certain duration and 
relying on chance. However, I am of the opinion that utilizing the 
WhiteBox API can provide greater determinism and potentially 
strengthen some of the assertions.


Yes, it calls System.gc in a loop and waits for a reference to 
become cleared.


WhiteBox.fullGC is better.


But is awkward to use within tests.

Makes me wonder whether System.gc() should do whatever 
WhiteBox.fullGC() actually does?


Would this be available to test code outside the JDK?

Outside the JDK, there also exists a need to ask the system if a 
reference can be cleared. This is usually part of test code to see if no 
memory is being leaked unexpectedly. System.gc() is currently our only 
hope to perform such tests, but it is clear it isn't intended for that 
purpose.


Perhaps there should be a more targetted solution; the intent isn't to 
run a GC (although that may be necessary depending on the 
implementation) but to test if a reference can be cleared. 
Implementations that can't or won't clear references could throw an 
exception to indicate this kind of test would not work with the current 
configuration.


--John





System.gc may not do a full GC; consider, for example, G1 with
-XX:+ExplicitGCInvokesConcurrent.

Because of potential cross-generational j.l.r.Reference and referent, 
one
invocation might not clear a Reference that would be cleared by a 
full GC, and

might in fact require many iterations.

Also, because of SATB requirements, G1 with 
-XX:+ExplicitGCInvokesConcurrent
might never clear a Reference if it is being checked for being 
cleared in the

traditional way (by ref.get() == null) rather than by using the newer
ref.refersTo(null).

WhiteBox.fullGC deals with both of those, and there's no need for 
looping.
The loops in functions like ForceGC are to deal with those kinds of 
issues.
And waiting for clearing is completely pointless.  A given GC 
invocation will

either clear or not, and there's not a delay afterward.

The ZGC equivalent of the second can still be a problem. Checking for a
cleared Reference really should be done using Reference.refersTo.

Re: RFR: JDK-8302323 Add repeat methods to StringBuilder/StringBuffer [v3]

[John Hendrikx]

On Tue, 28 Feb 2023 07:43:13 GMT, Tagir F. Valeev  wrote:

>> Jim Laskey has updated the pull request incrementally with one additional 
>> commit since the last revision:
>> 
>>   Optimize for empty CharSequence
>
> src/java.base/share/classes/java/lang/AbstractStringBuilder.java line 1903:
> 
>> 1901: throw new OutOfMemoryError("Required length exceeds 
>> implementation limit");
>> 1902: }
>> 1903: int total = count * length;
> 
> We may avoid division if we use the long type:
> 
> 
> long totalLong = ((long) count) * length;
> if (totalLong > Integer.MAX_VALUE - offset) {
> throw new OutOfMemoryError("Required length exceeds implementation 
> limit");
> }
> int total = (int) totalLong;
> 
> 
> Should be faster.

I'm a bit surprised this (and the original code) is throwing `OutOfMemoryError` 
when running into the max array size. It is not truly an out of memory error, 
but being an `Error`, it would evade standard catch `Exception` blocks.  I 
would think this is more of an `IllegalStateException` or perhaps something 
array specific.

`OutOfMemoryError` is documented pretty specifically that an object allocation 
failed after exhaustive GC, but no allocation or GC happened:

>Thrown when the Java Virtual Machine cannot allocate an object because it is 
>out of memory, and no more memory could be made available by the garbage 
>collector.

... which is not happening here at all. This leads me to believe the error is 
not used correctly here.

Other reasons I find it surprising: `StringBuilder` is not documented to throw 
this anywhere, it seems to just leak through from various methods implemented 
by `AbstractStringBuilder`.

-

PR: https://git.openjdk.org/jdk/pull/12728

NPE throwing behavior of immutable collections

[John Hendrikx]

TLDR; why does contains(null) not just return false for collections that 
don't allow nulls. Just because the interface allows it, does not mean 
it should do it as it devalues the usefulness of the abstraction 
provided by the interface.


Background:

I'm someone that likes to check correctness of any constructor or method 
parameter before allowing an object to be constructed or to be modified, 
in order to maintain invariants that are provided by the class to its users.


This ranges from simple null checks, to range checks on numeric values, 
to complete checks like "is a collection sorted" or is a list of nodes 
acyclic. Anything I can check in the constructor that may avoid problems 
further down the line or that may affect what I can guarantee on its own 
API methods.  For example, if I check in the constructor that something 
is not null, then the associated getter will guarantee that the returned 
value is not null.  If I check that a List doesn't contain nulls, then 
the associated getter will reflect that as well (assuming it is 
immutable or defensivily copied).


For collections, this is currently becoming harder and harder because 
more and more new collections are written to be null hostile.  It is 
fine if a collection doesn't accept nulls, but throwing NPE when I ask 
such a collection if it contains null seems to be counter productive, 
and reduces the usefulness of the collection interfaces.


This strict interpretation makes the collection interfaces harder to use 
than necessary. Interfaces are only useful when their contract is well 
defined. The more things an interface allows or leaves unspecified, the 
less useful it is for its users.


I know that the collection interfaces allow this, but you have to ask 
yourself this important question: how useful is an interface that makes 
almost no guarantees about what its methods will do? Interfaces like 
`List`, `Map` and `Set` are passed as method parameters a lot, and to 
make these useful, implementations of these interfaces should do their 
best to provide as consistent an experience as is reasonably possible.  
The alternative is that these interfaces will slowly decline in 
usefulness as methods will start asking for `ArrayList` instead of 
`List` to avoid having to deal with a too lenient specification.


With the collection interfaces I get the impression that recently there 
has been too much focus on what would be easy for the collection 
implementation instead of what would be easy for the users of said 
interfaces. In my opinion, the concerns of the user of interfaces almost 
always far outweigh the concerns of the implementors of said interfaces.


In the past, immutable collections were rare, but they get are getting 
more and more common all the time.  For example, in unit testing. 
Unfortunately, these immutable collections differ quite a bit from their 
mutable counterparts.  Some parts are only midly annoying (not accepting 
`null` as the **value** in a `Map` for example), but other parts require 
code to be rewritten for it to be able to work as a drop-in replacement 
for the mutable variant. A simple example is this:


    public void addShoppingItems(Collection shoppingItems) {
    if (shoppingItems.contains(null)) {  // this looks quite 
reasonable and safe...
    throw new IllegalArgumentException("shoppingItems should 
not contain nulls");

    }

    this.shoppingItems.addAll(shoppingItems);
    }

Testing this code is annoying:

 x.addShoppingItems(List.of("a", null"));   // can't construct 
immutable collection with null


 x.addShoppingItems(Arrays.asList("a", null"));  // fine, go back 
to what we did before then...


The above problems, I suppose we can live with it; immutable collections 
don't want `null` although I don't see any reason to not allow it as I 
can write a similar `List.of` that returns immutable collections that do 
allow `null`. For JDK code this is a bit disconcerting, as it is 
supposed to be as flexible as is reasonable without having too much of 
an opinion about what is good or bad.


This next one however:

     assertNoExceptionThrown(() -> x.addShoppingItems(List.of("a", 
"b")));  // not allowed, contains(null) in application code throws NPE


This is much more insidious; the `contains(null)` check has been a very 
practical way to check if collections contain null, and this works for 
almost all collections in common use, so there is no problem.  But now, 
more and more collections are starting to just throw NPE immediately 
even just to **check** if a null element is present. This only serves to 
distinguish themselves loudly from other similar collections that will 
simply return `false`.


I think this behavior is detrimental to the java collection interfaces 
in general, especially since there is a clear answer to the question if 
such a collection contains null or not. In fact, why `contains` was ever 
allowed to throw an exception aside from "Unsupp

Re: Sequenced Collections

[John Hendrikx]

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 extends Collection" 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" 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

Re: Proposal: Collection mutability marker interfaces

[John Hendrikx]

On 26/08/2022 18:54, Ethan McCue wrote:
If the collections would decide whether or not to copy, I don't think 
just requesting an immutable reference would be enough.


    static  List listCopy(Collection coll) {
        if (coll instanceof List12 || (coll instanceof ListN && ! 
((ListN)coll).allowNulls)) {

            return (List)coll;
        } else {
            return (List)List.of(coll.toArray()); // implicit 
nullcheck of coll

        }
    }

The two things that List.copyOf needs to know are that the list is 
immutable, but also that it isn't a variant that might contain a null.


I really don't care about the null problem, that's a problem that the 
designers of this basically brought upon themselves, not because of any 
real inherit limitation that an immutable collection can't contain 
`null`. What irks even more is that the `List` interface provides no way 
to determine if an implementation is actively null hostile meaning that 
this code is no longer safe (or strictly, never really was safe due to 
rather weak guarantees made in the `List` interface):


  List aList = ... ; // a list from somewhere

  if (aList.contains(null)) throw IllegalArgumentException();   // 
this is unsafe, and will cause a NPE depending on the list type


This unfortunate choice was never that visible, but since `List.of` it 
occurs more frequently in standard code, and highlights that a leniently 
specified interface is mostly a useless interface.


So, I don't see the reason to jump through hoops to use the same type of 
`List` that `List.of` or `List.copyOf` returns.  All that is required is 
that an immutable list is returned, which can be as simple as:


  return Collections.unmodifiableList(clone());

Or:

  return Collections.unmodifiableList(new ArrayList<>(this));

Or if already wrapped in the immutable wrapper simply `return this`.



So maybe instead of

     List y = x.immutableCopy();

It could be appropriate to use the spliterator approach and request a 
copy which has certain characteristics.


    static  List listCopy(Collection coll) {
        if (coll instanceof List list) {
            return list.copyWhere(EnumSet.of(IMMUTABLE, DISALLOW_NULLS));
        } else {
            return (List)List.of(coll.toArray()); // implicit 
nullcheck of coll

        }
    }

but that leaves open whether you would want to request the *presence* 
of capabilities or the *absence* of them.


Maybe

    List.of().copyWhere();

Could be defined to give a list where it is immutable and nulls aren't 
allowed. And then


   List.of(1, 2, 3).copyWhere(EnumSet.of(ADDABLE, NULLS_ALLOWED));

gives you a mutable copy where nulls are allowed.

This still does presume that making a copy if a capability isn't 
present is the only use of knowing the capabilities - which from the 
conversation so far isn't that unrealistic


I fear there are too many possibilities here to cover all use cases one 
could think of: Appendable, Prependable, Insertable, Removable, Popable, 
HeadRemovable(?), Permutable, Replacable, just to name a few.  A copy to 
create a modifiable version seems sufficient, and a custom solution is 
probably in order if that would cause performance issues (like a wrapper 
around an actual list that only allows specific functionality, like 
implements Appendable).


Perhaps with a method (or constructor) of the form:

   & Appendable> void giveMeAnAppendableList(T 
appendable);


--John



On Fri, Aug 26, 2022 at 11:20 AM John Hendrikx 
 wrote:



On 24/08/2022 15:38, Ethan McCue wrote:

A use case that doesn't cover is adding to a collection.
Say as part of a method's contract you state that you take
ownership of a List. You aren't going to copy even if the list is
mutable.

Later on, you may want to add to the list. Add is supported on
ArrayList so you don't need to copy and replace your reference,
but you would if the list you were given was made with List.of or
Arrays.asList


I don't think this is a common enough use case that should be
catered for.  It might be better handled with concurrent lists
instead.

The most common use case by far is wanting to make sure a
collection you've received is not going to be modified while you
are working with it.  I don't think another proposal which does
cover the most common cases should be dismissed out of hand
because it doesn't support a rather rare use case.

--John




On Wed, Aug 24, 2022, 8:13 AM John Hendrikx
 wrote:

Would it be an option to not make the receiver responsible
for the decision whether to make a copy or not?  Instead put
this burden (using default methods) on the various collections?

If List/Set/Map had a method like this:

 List immutableCopy();  // returns a (shallow)
immutable copy if 

Re: Proposal: Collection mutability marker interfaces

[John Hendrikx]

On 24/08/2022 15:38, Ethan McCue wrote:

A use case that doesn't cover is adding to a collection.
Say as part of a method's contract you state that you take ownership 
of a List. You aren't going to copy even if the list is mutable.


Later on, you may want to add to the list. Add is supported on 
ArrayList so you don't need to copy and replace your reference, but 
you would if the list you were given was made with List.of or 
Arrays.asList


I don't think this is a common enough use case that should be catered 
for.  It might be better handled with concurrent lists instead.


The most common use case by far is wanting to make sure a collection 
you've received is not going to be modified while you are working with 
it.  I don't think another proposal which does cover the most common 
cases should be dismissed out of hand because it doesn't support a 
rather rare use case.


--John




On Wed, Aug 24, 2022, 8:13 AM John Hendrikx  
wrote:


Would it be an option to not make the receiver responsible for the
decision whether to make a copy or not?  Instead put this burden
(using default methods) on the various collections?

If List/Set/Map had a method like this:

 List immutableCopy();  // returns a (shallow) immutable
copy if list is mutable (basically always copies, unless proven
otherwise)

Paired with methods on Collections to prevent collections from
being modified:

 Collections.immutableList(List)

This wrapper is similar to `unmodifiableList` except it implements
`immutableCopy` as `return this`.

Then for the various scenario's, where `x` is an untrusted source
of List with unknown status:

 // Create a defensive copy; result is a private list that
cannot be modified:

 List y = x.immutableCopy();

 // Create a defensive copy for sharing, promising it won't
ever change:

 List y = Collections.immutableList(x.immutableCopy());

 // Create a defensive copy for mutating:

 List y = new ArrayList<>(x);  // same as always

 // Create a mutable copy, modify it, then expose as immutable:

 List y = new ArrayList<>(x);  // same as always

 y.add(  );

 List z = Collections.immutableList(y);

 y = null;  // we promise `z` won't change again by clearing
the only path to mutating it!

The advantage would be that this information isn't part of the
type system where it can easily get lost. The actual
implementation knows best whether a copy must be made or not.

Of course, the immutableList wrapper can be used incorrectly and
the promise here can be broken by keeping a reference to the
original (mutable) list, but I think that's an acceptable trade-off.

--John

PS. Chosen names are just for illustration; there is some
discussion as what "unmodifiable" vs "immutable" means in the
context of collections that may contain elements that are mutable.
In this post, immutable refers to shallow immutability .

On 24/08/2022 03:24, Ethan McCue wrote:

Ah, I'm an idiot.

There is still a proposal here somewhere...maybe. right now non
jdk lists can't participate in the special casing?

On Tue, Aug 23, 2022, 9:00 PM Paul Sandoz
 wrote:

List.copyOf already does what you want.


https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/List.java#L1068

https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ImmutableCollections.java#L168

Paul.

> On Aug 23, 2022, at 4:49 PM, Ethan McCue 
wrote:
>
> Hi all,
>
> I am running into an issue with the collections framework
where I have to choose between good semantics for users and
performance.
>
> Specifically I am taking a java.util.List from my users and
I need to choose to either
> * Not defensively copy and expose a potential footgun when
I pass that List to another thread
> * Defensively copy and make my users pay an unnecessary
runtime cost.
>
> What I would really want, in a nutshell, is for List.copyOf
to be a no-op when used on lists made with List.of().
>
> Below the line is a pitch I wrote up on reddit 7 months ago
for a mechanism I think could accomplish that. My goal is to
share the idea a bit more widely and to this specific
audience to get feedback.
>
>

https://www.reddit.com/r/java/comments/sf8qrv/comment/hv8or92/?utm_source=share&utm_medium=web2x&context=3

<https://www.reddit.com/r/java/comments/sf8qrv/comment/hv8or92/?utm_source=share&utm_medium=web2x&context=3&g

Re: Proposal: Collection mutability marker interfaces

[John Hendrikx]

Would it be an option to not make the receiver responsible for the 
decision whether to make a copy or not?  Instead put this burden (using 
default methods) on the various collections?


If List/Set/Map had a method like this:

 List immutableCopy();  // returns a (shallow) immutable copy if 
list is mutable (basically always copies, unless proven otherwise)


Paired with methods on Collections to prevent collections from being 
modified:


 Collections.immutableList(List)

This wrapper is similar to `unmodifiableList` except it implements 
`immutableCopy` as `return this`.


Then for the various scenario's, where `x` is an untrusted source of 
List with unknown status:


 // Create a defensive copy; result is a private list that cannot 
be modified:


 List y = x.immutableCopy();

 // Create a defensive copy for sharing, promising it won't ever 
change:


 List y = Collections.immutableList(x.immutableCopy());

 // Create a defensive copy for mutating:

 List y = new ArrayList<>(x);  // same as always

 // Create a mutable copy, modify it, then expose as immutable:

 List y = new ArrayList<>(x);  // same as always

 y.add(  );

 List z = Collections.immutableList(y);

 y = null;  // we promise `z` won't change again by clearing the 
only path to mutating it!


The advantage would be that this information isn't part of the type 
system where it can easily get lost. The actual implementation knows 
best whether a copy must be made or not.


Of course, the immutableList wrapper can be used incorrectly and the 
promise here can be broken by keeping a reference to the original 
(mutable) list, but I think that's an acceptable trade-off.


--John

PS. Chosen names are just for illustration; there is some discussion as 
what "unmodifiable" vs "immutable" means in the context of collections 
that may contain elements that are mutable. In this post, immutable 
refers to shallow immutability .


On 24/08/2022 03:24, Ethan McCue wrote:

Ah, I'm an idiot.

There is still a proposal here somewhere...maybe. right now non jdk 
lists can't participate in the special casing?


On Tue, Aug 23, 2022, 9:00 PM Paul Sandoz  wrote:

List.copyOf already does what you want.


https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/List.java#L1068

https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ImmutableCollections.java#L168

Paul.

> On Aug 23, 2022, at 4:49 PM, Ethan McCue  wrote:
>
> Hi all,
>
> I am running into an issue with the collections framework where
I have to choose between good semantics for users and performance.
>
> Specifically I am taking a java.util.List from my users and I
need to choose to either
> * Not defensively copy and expose a potential footgun when I
pass that List to another thread
> * Defensively copy and make my users pay an unnecessary runtime
cost.
>
> What I would really want, in a nutshell, is for List.copyOf to
be a no-op when used on lists made with List.of().
>
> Below the line is a pitch I wrote up on reddit 7 months ago for
a mechanism I think could accomplish that. My goal is to share the
idea a bit more widely and to this specific audience to get feedback.
>
>

https://www.reddit.com/r/java/comments/sf8qrv/comment/hv8or92/?utm_source=share&utm_medium=web2x&context=3



>
> Important also for context is Ron Pressler's comment above.
> --
>
> What if the collections api added more marker interfaces like
RandomAccess?
>
> It's already a common thing for codebases to make explicit null
checks at error boundaries because the type system can't encode
null | List.
>
> This feels like a similar problem.
> If you have a List in the type system then you don't know for
sure you can call any methods on it until you check that its not
null. In the same way, there is a set of methods that you don't
know at the type/interface level if you are allowed to call.
>
> If the List is actually a __
> Then you can definitely call
> And you know other reference holders might call
> And you can confirm its this case by
> null
> no methods
> no methods
> list == null
> List.of(...)
> get, size
> get, size
> ???
> Collections.unmodifiableList(...)
> get, size
> get, size, add, set
> ???
> Arrays.asList(...)
> get, size, set
> get, size, set
> ???
> new ArrayList<>()
> get, size, add, set
> get, size, add, set
> ???
> While yes, there is no feasible way to encode these things in
the type system. Its not impossible to encode it at runtime though.
> interface FullyImmutable {
> // So you know the existenc

Re: JMH results for IndexedLinkedList

[John Hendrikx]

I'm curious, why isn't ArrayDeque or ConcurrentLinkedDeque used instead? 
Or is there another requirement?


ArrayDeque has amortized O(1) for inserts at head and tail (and faster 
and more memory efficient than LinkedList as it doesn't use nodes).


ConcurrentLinkedDeque would be useful in the face of multiple threads 
(it uses nodes though, so won't be as fast as ArrayDeque).


--John

On 11/07/2022 11:58, Maurizio Cimadamore wrote:


The implementation of the Foreign Function & Memory API uses an 
internal custom linked list to add native resources to a "memory 
session" abstraction (things that need to be cleaned up at a later point).


Linked list is quite critical in our use case because we need 
something that has a very fast insertion (in the head), and can scale 
gracefully to handle multiple threads.


In our case LinkedList is not good enough (because we want to deal 
with concurrent writes ourselves) - but aside from that, note that, at 
least looking at the numbers posted in your benchmarks, it seems that 
prepending an element to a classic LinkedList is 10x faster than 
ArrayList and 5x faster IndexList. Perhaps that's a case where 
IndexList has not been fully optimized - but for prepend-heavy code 
(and the javac compiler is another one of those), I think performance 
of addFirst is the number to look at.


As Tagir said, of course these use cases are very "niche" - and, at 
least in my experience, deevelopers in this "niche" tend to come up 
with ad-hoc specialized data structures anyways. So the return of 
investment for adding another collection type in this space seems 
relatively low.


Maurizio

On 09/07/2022 20:33, Tagir Valeev wrote:
Note that nobody these days cares about LinkedList. Use-cases where 
LinkedList outperforms careful use of ArrayList or ArrayDeque are 
next to none. So saying that your data structure is better than 
LinkedList is totally not a reason to add it to JDK. It should be 
better than ArrayList and ArrayDeque.


Having a single data structure that provides list and deque interface 
is a reasonable idea. However it would be much simpler to retrofit 
existing data structure like ArrayDeque, rather than create a new 
data structure. Here's an issue for this:

https://bugs.openjdk.org/browse/JDK-8143850

There were also discussions to enhance collections in general, adding 
more useful methods like getFirst() or removeLast() to ArrayList, 
etc. See for details:

https://bugs.openjdk.org/browse/JDK-8266572

To conclude, the idea of adding one more collection implementation 
looks questionable to me. It will add more confusion when people need 
to select which collection fits their needs better. It will require 
more learning. This could be justified if there are clear benefits in 
using it in real world problems, compared to existing collections. 
But so far I don't see the examples of such problems.


With best regards,
Tagir Valeev

сб, 9 июл. 2022 г., 11:22 Rodion Efremov :

Hello,

My benchmarking suggests, that, if nothing else, my
IndexedLinkedList outperforms gracefully the
java.util.LinkedList, so the use case should be the same (List
+ Deque -interfaces) for both of the aforementioned data
structures.

Best regards,
rodde


On Sat, Jul 9, 2022 at 11:19 AM Tagir Valeev 
wrote:

Hello!

Are there real world problems/use cases where
IndexedLinkedList would be preferred in terms of CPU/memory
usage over ArrayList?

сб, 9 июл. 2022 г., 07:18 Rodion Efremov :

Data structure repo:
https://github.com/coderodde/IndexedLinkedList

Benchmark repo:
https://github.com/coderodde/IndexedLinkedListBenchmark

I have profiled my data structure and it seems it’s more
performant than java.util.LinkedList or TreeList, if
nothing else.

So, is there any chance of including IndexedLinkedList to
JDK?

Best regards,
rodde

Re: JMH results for IndexedLinkedList

[John Hendrikx]

I think there might be room for another List implementation in the JDK, 
one that fits in between ArrayList and LinkedHashMap. I've been looking 
for something to manage lists of listeners (which allow arbitrary 
removal), must be called in order, and should handle duplicates (at 
their respective positions).  Both ArrayList and LinkedHashMap are 
close.  LinkedHashMap has quite some overhead (Entry instance per 
element) and poor cache locality while iterating and doesn't allow 
duplicates.  ArrayList has poor remove performance.


It should offer O(1) performance for add(Last), contains, remove(T) and 
near O(1) performance for operations that operate near the head/tail of 
the list (like getFirst, getLast, removeFirst, removeLast).  Iteration 
performance would be similar to ArrayList.  Basically an ArrayDeque, but 
with fast contains/remove(T).  The sacrifice made is poor index based 
access (with the exception of the head/tail).


It should be useful as a queue as well that allows quick removal (in 
order to cancel tasks for example, or to move a task up/down the queue).


--John

On 09/07/2022 21:33, Tagir Valeev wrote:
Note that nobody these days cares about LinkedList. Use-cases where 
LinkedList outperforms careful use of ArrayList or ArrayDeque are next 
to none. So saying that your data structure is better than LinkedList 
is totally not a reason to add it to JDK. It should be better than 
ArrayList and ArrayDeque.


Having a single data structure that provides list and deque interface 
is a reasonable idea. However it would be much simpler to retrofit 
existing data structure like ArrayDeque, rather than create a new data 
structure. Here's an issue for this:

https://bugs.openjdk.org/browse/JDK-8143850

There were also discussions to enhance collections in general, adding 
more useful methods like getFirst() or removeLast() to ArrayList, etc. 
See for details:

https://bugs.openjdk.org/browse/JDK-8266572

To conclude, the idea of adding one more collection implementation 
looks questionable to me. It will add more confusion when people need 
to select which collection fits their needs better. It will require 
more learning. This could be justified if there are clear benefits in 
using it in real world problems, compared to existing collections. But 
so far I don't see the examples of such problems.


With best regards,
Tagir Valeev

сб, 9 июл. 2022 г., 11:22 Rodion Efremov :

Hello,

My benchmarking suggests, that, if nothing else, my
IndexedLinkedList outperforms gracefully the java.util.LinkedList,
so the use case should be the same (List + Deque
-interfaces) for both of the aforementioned data structures.

Best regards,
rodde


On Sat, Jul 9, 2022 at 11:19 AM Tagir Valeev 
wrote:

Hello!

Are there real world problems/use cases where
IndexedLinkedList would be preferred in terms of CPU/memory
usage over ArrayList?

сб, 9 июл. 2022 г., 07:18 Rodion Efremov :

Data structure repo:
https://github.com/coderodde/IndexedLinkedList

Benchmark repo:
https://github.com/coderodde/IndexedLinkedListBenchmark

I have profiled my data structure and it seems it’s more
performant than java.util.LinkedList or TreeList, if
nothing else.

So, is there any chance of including IndexedLinkedList to JDK?

Best regards,
rodde